In the languages we’ve examined so far, when we have a high-level problem like “see if a list contains an interesting element,” we can define a high-level, problem-specific function like exists?. But we can’t yet define problem-specific data; no matter what problem we’re working on, our code is written in terms of representations like numbers, symbols, Booleans, lists, S-expressions, and constructed data. We should hope for better; if we’re implementing high-level actions like “find the rule in the table,” “multiply two 50-digit numbers,” or “stop recording when the event is over,” then our code should be written in terms of abstractions like tables, large numbers, and events. Such abstractions can be defined by the language features described in the last two chapters of this book.

A running μScheme program continually allocates fresh locations. How are they supplied? Memory is limited, and malloc will eventually run out. Memory can be recovered using free, but if a programmer must call free, as in C and C++, they risk memory errors: leaks, locations that are freed multiple times, and misuse of freed locations (so-called dangling-pointer errors). Memory errors can make a program crash—or, worse, silently produce wrong answers. But in languages like μScheme, full Scheme, Java, and JavaScript, which are memory-safe, such errors are impossible. The errors are prevented because the implementation of μScheme, not the μScheme programmer, figures out when it is safe to reuse a location. The techniques used to reuse locations safely are demonstrated in this chapter.

The languages of the preceding chapters, Impcore and μScheme, are dynamically typed, which is to say that many faults, such as applying a function to the wrong number of arguments, adding non-numbers, or applying car to a symbol, are not detected until run time. Dynamically typed languages are very flexible, but on any given execution, a fault might surprise you; even a simple mistake like typing cdr when you meant car might not have been detected on previous runs. And using cdr instead of car doesn’t cause a fault right away: cdr simply returns a list in a context where you were expecting an element. But if, for example, you then try to add 1 to the result of applying cdr, that is a checked run-time error: adding 1 to a list instead of a number. To rule out such errors at compile time, without having to run the faulty code, a programming language can use static typing.

The interpreters in Chapters 1 to 4 are written in C, which has much to recommend it: C is relatively small and simple; it is widely known and widely supported; its perspicuous cost model makes it is easy to discover what is happening at the machine level; and it provides pointer arithmetic, which makes it a fine language in which to write a garbage collector. But for implementing more complicated or ambitious languages, C is less than ideal. In this and succeeding chapters, I therefore present interpreters written in the functional language Standard ML.

Typed Impcore and Typed ρScheme represent two extremes. Typed Impcore is easy to program in and easy to write a type checker for, but because it is monomorphic, it cannot accept polymorphic functions, and it can accommodate new type constructors and polymorphic operations only if its syntax and type checker are extended. Typed μScheme is also easy to write a type checker for, and as a polymorphic language, it can accept polymorphic functions, and it can accommodate new type constructors and polymorphic functions with no change to its syntax or its type checker. But Typed μScheme is difficult to program in: as Milner observed, supplying a type parameter at every use of every polymorphic value soon becomes intolerable. To combine the expressive power of polymorphism with great ease of programming, this chapter presents a third point in the design space: nano-ML. Nano-ML is expressive, easy to extend, and also easy to program in. This ease of use is delivered by a new typing algorithm: instead of type checking, nano-ML uses type inference.

presents applicative programming in μScheme. But μScheme doesn’t just support applicative programming; it also supports the procedural programming style described in . In particular, it provides while, set, and begin. In the procedural style, while and if account for most control flow. But loops typically also use such control operators as break, continue, and return.

This book is about programming languages—and also about programming. Eachof these things is made better by the other. If you program but you don’t know about programming languages, your code may be longer, uglier, less robust, and harder to debug than it could be. If you know about programming languages but you don’t program, what is your knowledge for? To know a language is good, but to use it well is better.