Optimal reduction is an innovative graph reduction technique for functional expressions that solves the sharing problem. This is an unusual book that will interest the functional programming community.

The authors’ intention is to cover optimal implementation issues, from the most theoretical to the most pragmatic. It is about optimal sharing in functional programming languages, but also covers the theory of optimal reductions in the lambda calculus: permutation equivalences, redex families, labeled lambda calculus, extraction of canonical redexes, balanced paths, context semantics and readback, sharing graphs, and the complexity of sharing.

The authors include an implementation of the Bologna Optimal Higher-Order Machine (BOHM) as a basis for an efficient implementation of functional programming languages. BOHM is a prototype implementation of an extension of Lamping’s optimal graph reduction techniques. Its source language is sugared lambda calculus enriched with booleans, integers, lists, and basic operations on these data types. Thus, it can be a good, comprehensive introduction to this topic, although quite a bit of previous knowledge is required.

This is a research book, not a textbook, though the material is presented rather accessibly. It is important for a specific audience, namely, people involved in functional languages and their implementations. Instructors can use it for advanced courses, software developers will use it when they want to use some sharing mechanisms in their implementations, and theoreticians will find a lot of ideas for manipulating languages with bound variables. Even postgraduate students can read it, but they will need a background in the lambda calculus and basic implementation techniques via graph-sharing. A knowledge of intuitionistic and linear logic will also be beneficial for an understanding of some chapters.

The length of the book is appropriate, and all the issues covered are relevant. The authors go straight to the point, using an unusual approach. The book presents a nice application of the theory to practical issues. The correctness of the algorithms is proven, and the authors make a good effort toward resolving optimization of expression evaluation.

In spite of the book’s technical quality, there are a significant number of errors in lambda expressions, inconsistencies between the diagrams and the text, and other errors that make the book more difficult for readers who are new to the field. The authors’ convention for the use of parentheses in lambda expressions is confusing: it is definitely not the one used by the functional programming community.

The authors cite many appropriate references, including many important books and papers. The index is not long, but this is not a textbook.

This approach seems interesting and attractive, but, although it is theoretically appealing, it seems not to have been proven in practice yet.