Multi-stage Relational Programming
summary
Implements a multi-stage extension of miniKanren that compiles known parts of relational interpreters and defers unknown holes to a runtime relational evaluator, so interpreters become faster compilers for synthesis tasks. Adds two annotation strategies (fall back for unknown program text, gather for runtime branching), preserves an erasure property so staged code yields a runtime evaluator, and ships reusable artifacts. Reports ~26× average speedup across 21 benchmarks on Racket, miniKanren, and CFG recognizers.
AI-written summary · about
chapters (8)
- 0:00Multi-stage relational programming intro
- 1:46Relational programming basics
- 5:39Staging in relational context
- 7:22Holes and non-determinism in staging
- 10:15Disjunction and staging in interpreters
- 13:27Performance benchmarks
- 14:30Language synthesis and future work
- 15:47Q&A
related talks
19mSome Novel miniKanren Synthesis Tasks
20mKanren Light
14mRelational Synthesis for Pattern Matching
26mtypedKanren: Statically Typed Relational Programming with Exhaustive Matching in(…)
15mAn Empirical Study of Partial Deduction for miniKanren
22mA Case Study in Functional Conversion and Mode Inference in miniKanren
26mCommitting to the bit: Relational programming with semiring arrays and SAT solving
14mOn Fair Relational Conjunction