"An Introduction to Combinator Compilers and Graph Reduction Machines" by David Graunke

David Graunke explains how to compile lambda calculus to pure combinators and implement a graph reduction algorithm for lazy functional languages.

Graph reducing interpreters combined with compilation to combinators creates a "virtual machine" compilation target for pure lazy functional programs that is extremely concise, simple in its semantics, and naturally parallelizable. In their simple forms these techniques are a useful introduction to compiling and interpeting functional languages. In much more sophisticated forms, they illustrate how large-scale compilers are implemented in used in languages like Idris. We'll walk through the process of compiling programs in the lambda calculus to pure combinators and a simple implementation of the most straightforward graph reduction algorithm. With that context, we'll look at the history of graph reduction, from a surge of interest and excitement in the 80s and 90s to serious reservations in the 2000s. We'll look at concrete examples of combinator compilation and graph reduction, and compare with alternative techniques in Haskell's Spineless Tagless G-Machine.