Towards Bottom-Up Enumeration in miniKanren via Pruning and Memoization
summary
Two small combinators implement bottom‑up enumeration with observational deduplication on an unmodified miniKanren core: prune deduplicates answers by a user‑supplied key (here a host interpreter on ground terms) and defrel/bank memoizes canonical calls so a single pruned stream is replayed at every call site; a weighted variant defrel/bank-w adds admissible upper bounds. On toy PBE tasks using inputs 2,3,4, naive enumeration touches ~500k candidates and finds 1+x^3 in ~7s while 1+x^4 times out at 30s; bank speeds most deep targets but regresses on a right‑biased family.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 0:20Bottom-up enumeration motivation
- 3:06Program synthesis challenges
- 7:23Prune combinator for duplication
- 12:01Nested pruning and variables
- 15:43Memoization with defrail/bank
- 17:10Recursive relations tricks
- 18:13Best-first search with defro/bank-w
- 20:52Benchmarks and results
- 23:43Approaches comparison
- 25:08Future work
- 26:54Conclusion
- 27:58Q&A
related talks
15mAn Empirical Study of Partial Deduction for miniKanren
28mOriented Metrics for Bottom-Up Enumerative Synthesis
40mminiKanren Philosophy
40mμKanren: Running the Little Things Backwards
14mRelational Synthesis for Pattern Matching
22mA Case Study in Functional Conversion and Mode Inference in miniKanren
14mMicroKanren in J
14mOn Fair Relational Conjunction