Part 1 of this book deals with practice, and Part 2 covers theory. Part 1 begins with the use of first-order functions and gradually leads to the use of higher-order functions. Part 2 begins with a presentation of the lambda calculus and gradually leads to other calculi. The language used for writing functional programs is standard mathematical notation, but the author calls it “phi” and provides a formal syntax for it.

Part 1 consists of chapters 1 through 7. Chapter 1 points out the advantages of assignment-less programming over programming with assignments (such as the ease of common-subexpression elimination and the independence of evaluation order); explains the terms “referential transparency” and “manifest” and “hidden” interfaces; presents methods for defining functions (enumeration, composition, finite number of fixed compositions, and recursion); and distinguishes between implicit definitions, which can result in nonterminating computations, and explicit definitions, which are rewrite rules that are guaranteed to result in terminating computations. Chapter 1 also traces the history of functional programming and explains the need to embed a functional programming language in an imperative shell. Chapter 2 introduces data types and operations that are used throughout the book. Chapter 3 develops the reader’s skill in applicative programming. Chapter 4 uses sequences to construct prototype implementations of two abstract data types: finite sets and finite functions. Chapter 5 introduces data types analogous to records, variant records, tuples, and recursively defined data types such as trees along with applications such as tree evaluation and unification. Chapter 6 covers programming with higher-order functions. Chapter 7 deals with infinite data structures; it includes a discussion of delayed evaluation and streams.

Part 2 consists of chapters 8 through 13. Chapter 8 introduces the lambda calculus and argues that this applicative model of computation is complete in the sense that it can compute any computable function. MacLennan makes the argument by developing a universal function for phi in the lambda calculus; he makes no attempt in this chapter to show that the lambda calculus is equivalent in power to the Turing machine, the imperative model of computation. Chapter 9 demonstrates the consistency of the lambda calculus by proving the Church-Rosser Theorem; this chapter also proves the undecidability of the halting problem for the lambda calculus. Chapter 10 presents calculi that are more specialized and therefore more efficient than the lambda calculus. Chapter 11 develops a universal function for the lambda calculus in phi and shows how the application of correctness-preserving transformations to the universal function can yield an efficient and practical interpreter. Together with the results of chapter 8, chapter 11 demonstrates the equivalence of phi and the lambda calculus. Chapter 12 explains various evaluation orders and explains how the interpreted language inherits the evaluation order of the interpreting language; it then discusses ways to decouple the evaluation orders of the interpreted and interpreting languages. Chapter 13 compares the functional programming paradigm with other programming paradigms and states the problems that need to be addressed if the functional programming paradigm is to advance.

The book concludes with a list of references, three appendices (dealing with the syntax of phi, collected archetypes, and functional programming in LISP and Scheme), an index of notation, and an index. It provides clear and comprehensive coverage of both the practice and the theory of functional programming. The author provides a large number of exercises but no solutions. The book does not deal with the implementation of functional programming languages in detail. On the whole, however, it is a valuable addition to the literature on functional programming.