Matthias Felleisen - The Little MLer

There are many ways of trying to understand programs. People often rely too much on one way, which is called "debugging" and consists of running a partly-understood program to see if it does what you expected. Another way, which ML advocates, is to install some means of understanding in the very programs themselves. Standard ML was designed with this in mind. There are two particular ways-ofunderstanding built in to Standard ML; one is types for understanding data, the other is the module system for understanding the structure of the large-scale programs. People who program in a language with a strong type system, like this one, often say that their programs have fewer mistakes, and they understand them better.

The authors focus upon these features of Standard NIL. They are well equipped to help you to understand programming; they are experienced teachers as well as researchers of the elegant and simple ideas which inspire good programming languages and good programming style. Above all they have written a book which is a pleasure to read; it is free of heavy detail, but doesn't avoid tricky points. I hope you will enjoy the book and be able to use the ideas, whatever programming language you use in the future.

Once the types are formulated, the design of the program follows naturally. Its shape will reflect the shape of the types and type definitions. Most collections of data, and hence most type specifications, are inductive, that is, they are defined in terms of themselves. Hence, most programs are recursive; again, they are defined in terms of themselves. The first and primary goal of this book is to teach you to think recursively about types and programs. Perhaps the best programming language for understanding types and recursive thinking is ML.

It has a rich, practical type language, and recursion is its natural computational mechanism. Since our primary concern is the idea of recursion, our treatment of ML in the first eight chapters is limited to the whys and wherefores of just a few features: types, datatypes, and functions. The second goal of this book is to expose you to two important topics concerning large programs: dealing with exceptional situations and composing program components. Managing exceptional situtations is possible, but awkward, with recursive functions. Consequently, ML provides a small and pragmatic sublanguage, i.e., exception, raise, and handle, for dealing with such situations. The exception mechanism can also be used as a control tool to simplify recursive definitions when appropriate.

Typically, programs consist of many collections of many types and functions. Each collection is a progam component or module. Constructing large programs means combining modules but also requires understanding the dependencies among the components. ML supports a powerful sublanguage for that purpose. In the last chapter, we introduce you to this language and the art of combining program components. The module sublanguage is again a functional programming language, just like the one we present in the first eight chapters, but its basic values are modules (called structures) not integers or booleans.

While The Little MLer provides an introduction to the principles of types, computation, and program construction, you should also know that ML itself is more general and incorporates more than we could intelligibly cover in an introductory text. After you have mastered this book, you can read and understand more advanced and comprehensive books on ML. ACKNOWLEDGMENTS We are indebted to Benjamin Pierce for numerous readings and insightful suggestions on improving the presentation and to Robert Harper for criticisms of the book and guidance concerning the new module system of ML. Michael Ashley, Cynthia Brown, Robby Findler, Matthew Flatt, Jeremy Frens, Steve Ganz, Daniel Grossman, Erik Hilsdale, Julia Lawall, Shinn-Der Lee, Michael Levin, David MacQueen, Kevin Millikin, Jon Riecke, George Springer, and Mitchell Wand read the book at various stages of development and their comments helped produce the final result. We also wish to thank Robert Prior at MIT Press who loyally supported us for many years. The book greatly benefited from Dorai Sitaram's incredibly clever Scheme typesetting program Finally, we would like to thank the National Science Foundation for its continued support and especially for the Educational Innovation Grant that provided its with the opportunity to collaborate for the past year.

WHAT You NEED TO KNOW TO READ THIS BOOK You must be comfortable reading English and performing rudimentary arithmetic. A willingness to use paper and pencil to ensure understanding is absolutely necessary. READING GUIDELINES Do not rush through this book. Read carefully; valuable hints are scattered throughout the text. Do not read the first eight chapters in fewer than three sittings. Allow one sitting at least for each of the last two chapters.

Read systematically. If you do not fully understand one chapter, you will understand the next one even less. The book is a dialogue about interesting examples of NIL programs. If you can, try the examples while you read. Since NIL implementations are predominantly interactive, the programmer can immediately participate in and observe the behavior of expressions. We encourage you to use this interactive read-evaluate-and-print loop to experiment with our definitions and examples.

Some hints concerning experimentation are provided below. We do not give any formal definitions in this hook. We believe that you can form your own definitions and thus remember and understand them better than if we had written them out for you. But be sure you know and understand the morals that appear at the end of each chapter. We use a few notational conventions throughout the text, primarily changes in typeface for different classes of symbols. Variables are in italic.

Basic data, including numbers. booleans, constructors introduced via datatypes, are set in sans serif. Keywords, e.g., datatype, of, and, fun, are in boldface. When you experiment with the programs, you may ignore the typefaces but not the related framenotes. To highlight this role of typefaces, the ML fragments in framenotes are set in a typewriter face. Food appears in many of our examples for two reasons.