An Introduction to Combinator Compilers and Graph Reduction Machines
summary
Shows that compilation to combinators plus graph reduction yields a tiny virtual‑machine target for pure lazy lambda programs with simple semantics and natural parallelism. Explains SKI and Turner combinators, normal‑order lazy rewrites, and a straightforward graph‑reducer implementation that rewrites local pointers rather than scanning trees. Reviews history: Miranda’s ~10‑year heyday, later reservations, and hardware work like the reducer on FPGA that performs multiple reductions in parallel; contrasts with GHC’s closure reduction / STG approach used for performance.
AI-written summary · about
chapters (26)
- 0:00Introduction
- 2:18Graph Production Machines
- 2:30What is a Combinator Compiler
- 2:49Graph Reduction
- 3:11Virtual Machines
- 5:06Computing by Rewriting
- 5:32Function Application
- 8:52Graph Reduction Machine
- 11:11Lazy Evaluation
- 12:59Simplify
- 14:27Point Free Expressions
- 16:28Definition of Combinator
- 17:43Calculable Functions
- 18:01Combinator Calculus
- 18:13Skee Calculus
- 24:15Simplifying Graph Reduction
- 24:31Local Rewrites
- 24:41Graph Representation
- 26:20Graph Transformation
- 26:53Lazy Evaluation Normal Order
- 28:13Calculus
- 28:29Combinators
- 30:44Implementations
- 30:54Miranda
- 33:33Custom Hardware
- 37:28Interaction Nets
related talks
01h 01mMacGyver's Haskell Compiler
01h 00mTheory and Models of Lambda Calculus Untyped and Typed - Part 1 of 5
15mStaged Selective Parser Combinators
15mMetaprogramming with Combinators
42mThe Power of Function Composition
41mConcatenative programming and stack-based languages
30mCalculating Compilers for Concurrency
09mCompilers for nothing, executables for free!