Book Review: Implementing Functional Languages. A Tutorial

3 Mar 2019

Hey there! Today I'm giving a short review to a small, but an interesting book: "Implementing Functional Languages. A Tutorial" by Simon Peyton Jones and David Lester. This is a shorter and more practical version of the famous "The Implementation of Functional Programming Languages" by Simon Peyton Jones. Both books are quite old (1992 and 1987 correspondingly), albeit the things they cover haven't changed too much. It is still possible to extract a lot of precious knowledge from these books, even if a historical one. I'd be glad to read "The Implementation" instead, but unable to find its printed version, I decided to go with "A Tutorial". Can't say that I'm disappointed, quite the opposite.

The book covers several implementations of runtime for a functional language: simple, interpreted template instantiation; compiled G-machine, TIM and parallelized version of G-machine. It devotes one chapter to a specification of the language and building of its parser, but the rest of the book is about runtimes and optimizations only. The text is easy to read as it has only a necessary minimum of theory. The authors do a great job of distilling the main idea of a particular implementation or optimization down to a couple of paragraphs. If you're curious, however, there are always references to other places where you can find more information.

Each chapter starts with a simple implementation of a particular runtime, usually not even supporting arithmetics, only plain lambda calculus. Later it is renewed by adding support for arithmetics, let(rec) bindings, data structures, and several optimizations. The code is written in Miranda, a predecessor of Haskell. I find it a bit weird to read, though it is understandable. I'd be happy to have it written in Haskell instead, as some chapters have quite interesting exercises for the reader, but I guess it's easier to find a more recent book on the topic than to renew this one.

In the end, I think it is a good book for the people interested in the roots of what's under the hood of contemporary lazy, purely functional programming languages, but not willing to spend too much time reading all the papers behind these algorithms.