Efficient Nanopass Compilers using Cats and Matryoshka
summary
Claims a new recursion-scheme library, Matryoshka, lets many tiny, safe AST transformations be written independently but fused into a few efficient passes using Cats coproducts and Inject (plus kind-projector and simulacrum). Uses cata/ana/trans forms (notably transCata), hylo/saigo patterns and attribute/cofree tricks to avoid building intermediates, regaining single-pass performance while keeping nano‑pass modularity. Library is production‑used at SlamData/Sunday and the approach measurably cuts repeated tree traversals.
AI-written summary · about
chapters (14)
- 0:00Intro
- 0:51What is a compiler
- 1:38Language
- 2:30Monolithic
- 5:42Unsafe
- 7:48Duplicate
- 10:14Fix
- 16:59Matryoshka
- 18:16Folds unfold transformations
- 21:57Algebraic version
- 23:37Transcata
- 26:30Annotation
- 28:41Inference
- 30:07Wrapup
related talks
37mGoing bananas with recursion schemes for fixed point data types
02h 00mUsing Corecursion Schemes
51mGoing bananas with recursion schemes for fixed point data types
23mTyped, Concise, Nanopass (pick 3) (Extended Abstract)
40mType-safe Nanopasses: How to write a safe and modern compiler front-end
41mWriting a Nanopass Compiler
25mNano-parsing: A Data-parallel Architecture for Perverse Parsing Environments
29mNanopass Attribute Grammars