Computing Reviews, October 1997, pages 472-3. Review 9710-0743

Copyright© 1997 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page or initial screen of the document. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept., ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.

The trend in computer science education--even in the better universities--seems to be toward what was once called vocation/technical education, where the focus is primarily on teaching people what the market wants. This results in course offerings in C, C++, Windows 95, and similarly "useful" subjects. Other subjects with less immediate applications are glossed over or omitted altogether. The usual justification is that the other topics do not help graduates get jobs. All too often, these graduates are then unwilling to learn much beyond what has already been force-fed to them.

A suggestion that this kind of policy is shortsighted is often countered with the observation that there are few texts supporting anything but the currently popular languages. This book is an excellent counterexample. It does not just focus on teaching the syntax of ML; it teaches the way a programmer should think in that language and offers many good examples to help the reader along. Even better, the book can be profitably read by anyone with a decent background in computer science.

The book is an excellent introduction to ML, but even better, it provides a good overview of functional programming. Functional programming, unlike the more conventional imperative model (as exemplified by C, Pascal, C++, and so on) provides no variables (in the usual sense) or operations with side effects (ML does provide for limited operations with side effects). This simplifies reasoning about programs, since the same function with the same input will always produce the same output. There are tradeoffs, however--algorithms that are easy in a language with variables are sometimes more difficult without variables. Interestingly enough, some algorithms that are hard in conventional languages are much easier in functional languages (or in functional style). Compare the usual array-based quicksort with a list-based quicksort in a functional language. The functional version is much shorter, much easier to read, and much easier to write and get right. Furthermore, with a good compiler the efficiency of the functional version compares well with that of the imperative version.

The book covers the basic syntax of ML and gives more advanced examples showing the workings of ML in detail, suggesting ways to use the language well. It is readable, and the examples are clear and cogent. Chapter 1, "Standard ML," is a brief overview of functional programming and ML. Chapter 2, "Names, Functions and Types," presents a basic overview of ML as a language and introduces the basic datatypes. Chapter 3, "Lists," introduces the basic list datatype and gives a number of examples using lists (including quicksort). Chapter 4, "Trees and Concrete Data," shows more ways to construct datatypes, including trees, dictionaries, and functional arrays. Chapter 5, "Functions and Infinite Data," delves into some of the more powerful aspects of functional programming, including functions as values and "infinite" data structures. Chapter 6, "Reasoning about Functional Programs," discusses basic proof techniques as applied to functional programs. Chapter 7, "Abstract Types and Functors," covers modules and functions that manipulate functions. This chapter is likely to be very difficult for programmers used to imperative styles, but with a bit of work it is very illuminating. Chapter 8, "Imperative Programming in ML," explains how to perform operations with side effects, and in particular, how to build and use arrays. In chapter 9, "Writing Interpreters for the Lambda Calculus," the author constructs a parser and a simple interpreter. In chapter 10, "A Tactical Theorem Prover," he builds a small theorem prover.

The book contains plenty of ML code, mostly in bite-sized fragments, which are nicely typeset and which, fortunately, omit comments (with one or two exceptions). There are few long listings, and the commentary on the code is excellent. This comes as a welcome change, indeed, from texts that seem to consist of little but code listings.

A few sections are particularly worth noting. The discussion of infinite lists is excellent and well worth reading, probably more than once. The chapter on abstract types and functors is both challenging and rewarding. It took me a couple of readings to understand the details, but the result was a much better understanding of the process of building programs with abstractions, which I managed to apply to a project (in another language) almost at once.

I do have a few quibbles with the book. The first is not so much with the book as with ML implementations. There are several dialects of ML in use, so when trying some of the code in the book, I needed to try several ML compilers before I found one that would accept the book's syntax. The compiler that was the most useful for me used a very different syntax. This difficulty is likely to prevent many people from understanding why functional programming is worth learning.

I would also have liked to see more on lazy languages and why they differ from ML. While ML is not lazy, it is easy enough to construct lazy lists in ML, and the section on infinite lists is excellent. But lazy lists in Haskell, for example, are a bit different, and some information on why they differ in the two languages and what the difference means would have been of interest. Finally, while part of the book's title is "for the working programmer," the extended examples in the last two chapters seem aimed more at a theoretician (in logic) than at a working programmer. A few more examples that might be more accessible or interesting to those working in fields other than logic would be helpful.

These few minor problems should not deter anyone from studying this excellent book. Even if the reader never actually uses a functional language, some of the ideas and techniques can be useful in almost any language. A bit of functional style can go a long way toward making programs readable and extensible.

--Jeffrey Putnam, Sedona, AZ