Oregano: Staging Regular Expressions with Moore Cayley Fusion
summary
Oregano implements regular expressions as Moore machines with a Cayley/CPS compilation pipeline and staged meta-programming to emit specialized matcher code that returns structured applicative results. The pipeline generates raw pattern-match code, eliminates runtime automaton construction, and applies Cayley transformation and staged Fusion to remove dead code. Benchmarks show about 60× speedup versus text-ICU and ~5–6× versus regex-tdfa for common cases, sometimes worse on pathological backtracking; Oregano beats Parsley at -O1 but Parsley is faster at -O2. Artifacts are available.
AI-written summary · about
chapters (5)
- 0:00Introduction
- 0:14What are regular expressions
- 4:48Nondeterministic finite automata
- 13:41Stage meta programming
- 20:18Benchmarks
related talks
28mDesign Patterns for Parser Combinators (Functional Pearl)
01h 38mGHC Core Optimisations
55mDeforestation and Program Fusion
28mExpress: applications of dynamically typed Haskell expressions
23mHigher order Patterns in Rewrite Rules
44mRevisiting pattern match overlap checks in Haskell
47mLogic Programming à la Carte
32mCode as Data: Extracting & Analyzing Info from Haskell Codebases