Koopman offers another response to the question of how functional programming languages (and especially lazy functional languages) can be implemented efficiently on stock hardware. This debate began with Turner’s important work on combinator interpretation mechanisms [1], which has been followed up by Johnsson’s G-machine [2], Fairbairn and Wray’s TIM [3], and Peyton Jones’s spineless tagless G-machine [4].

Koopman gives a new methodology, which he calls  TIGRE  (Threaded Interpretive Graph Reduction Engine), for implementing combinator graph reduction. TIGRE is a development of the G-machine with a number of improvements inspired by work on interpreters for threaded code [5]. These improvements seem to carry the machine close to other optimized versions of the G-machine such as the spineless tagless machine.

After discussing the abstract machine, the author looks at implementations on particular hardware, including the VAX and the MIPS R2000 processor. One of his most important conclusions is given in the introduction, where he states,

The results shown here suggest that the advanced programming languages being explored by computer scientists do not adhere to the normal expectations of computer architects, and may eventually force a re-evaluation of architectural tradeoffs in system design. An important point of the findings presented here is that the combination of architectural features required for efficiency may be relatively inexpensive, yet omitted from even recent machines because of relative unimportance for conventional language execution.

The account of the work, which formed the author’s doctoral thesis, is clear, but the presentation of the combinator graph reduction in Appendix A leaves a lot to be desired. The author’s notation varies: function applications are denoted f x and f(x) on adjacent pages, the relative binding powers of the operations in the lambda calculus are not discussed, function applications are said to associate to the right (p. 103), and so on. The general standard of presentation is poor. The titles for many of the figures are incomplete (see figures 3-4 and 3-6) and many of the references are missing. These problems should have been ironed out during editing, and seem ridiculous in an age when bibliographies can be prepared automatically and typesetting receives computer support, or perhaps this automation is precisely the problem.

Nonetheless, the book contains a number of ideas that contribute to the search for an efficient implementation of a lazy functional programming language. It will be interesting to see how research in this area evolves in the years to come.