MacGyver's Haskell Compiler

on YouTube ↗01h 01m

" summary

Builds a working Haskell-to-combinators compiler that converts Haskell AST to lambda terms, uses Scott encoding for data and a fixed‑point (Y combinator) trick for recursion, then applies a bracket‑abstraction algorithm to emit S and K combinators. Runs a tiny VM and a browser demo that evaluates examples (four factorial reduces to 24 in about 1m17s in the demo), includes a reduction visualizer, and publishes the repo; core pipeline works but some features (mutual recursive modules, full pattern matching) remain unfinished.

AI-written summary · about

" chapters (9)

1. 0:00Introduction
2. 2:06Boolean logic to combinators
3. 10:16Combinators as building blocks
4. 17:23Live demo
5. 25:14Compiling to combinators
6. 36:46Recursion and Y combinator
7. 44:52Bootstrapping and demos
8. 52:29Tips and lessons
9. 56:13Q&A

" related talks

• 40mAn Introduction to Combinator Compilers and Graph Reduction MachinesDavid Graunke · Strange Loop 2016
• 42mThe Power of Function CompositionConor Hoekstra · Lambda World 2024
• 45mFunctional Programming bits and piecesZuzanna Kruszczynska · Software Crafters Barcelona 2019
• 01h 33mComposition Intuition IIConor Hoekstra · CppNorth 2024
• 53mIntro to Haskell for ErlangersBob Ippolito · Erlang Factory SF Bay Area 2014
• 01h 01mLive Lambda CalculusEinar W. Høst, Jonas Winje · NDC Oslo 2017
• 01h 01mFunction Composition in Programming LanguagesConor Hoekstra · CppNorth 2023
• 59mMercury: An Odd Amalgam of Haskell and Prolog - Part 1 of 2Alex Feldman-Crough · LambdaConf 2017