Staged Selective Parser Combinators
summary
Compiler for parser combinators that converts typed combinator trees into a CPS-style instruction machine and partially evaluates it with typed staging, implemented as the Parsley library. Monadic bind is removed so staging can eliminate static structure, while selective functors recover necessary context-sensitive choices. Generated code is simple continuation-passing functions and benchmarks show 3–4× faster than other combinator libraries and even beats Happy, a parser generator.
AI-written summary · about
chapters (9)
- 0:00Staged selective parser combinators
- 1:05Parser combinators in Haskell
- 3:41Performance and control flow
- 6:10Type-safe stack representation
- 8:36Staging as meta-programming
- 10:20Staging machine state evaluation
- 12:47Generating optimized code
- 13:09Limitations of bind
- 13:52Performance benchmarks
related talks
41mParser Combinators
53mUnderstanding parser combinators: a deep dive
26mParser Combinators in Swift
40mAn Introduction to Combinator Compilers and Graph Reduction Machines
01h 48mBoost.Parser (Part 2 of 2) - A Parser Combinator Library for C++
15mStaged Compilation with Two-Level Type Theory
33mLightning Talks II
01h 27mBoost.Parser (Part 1 of 2) - A Parser Combinator Library for C++