Beyond Cons: Purely Relational Data Structures

on YouTube ↗25m

" summary

Adds a constraint-enabled extension to miniKanren that implements first-class set objects and association-list constraints, giving membership, set union/disjointness and scoped lookup as declarative constraints rather than structural encodings. Implements Dovier-style rewriting and integrates with a modern faster-miniKanren backend, resolving the free-variable example that previously caused infinite enumeration and restoring finite failure and more compositional search. Unification can yield multiple alternative bindings, forcing adjustments to common optimizer assumptions, but the prototype works and demonstrates improved interpreter encodings and practical association-list support.

AI-written summary · about

" chapters (15)

1. 0:00Purely relational data structures
2. 1:26Intentional definitions in data structures
3. 3:35Extensional sets in MiniKanren
4. 6:04List-based set problems
5. 9:16Functional data structures limits
6. 10:20Relational data structure requirements
7. 11:43Set constraints in Setlog
8. 13:55Setlog’s unification benefits
9. 15:21Core set constraints
10. 17:26Setlog in MiniKanren
11. 18:30Faster MiniKanren challenges
12. 20:41MiniKanren’s unification impact
13. 21:45Key takeaways and future
14. 22:09Q&A: Set constraint primitives
15. 23:33Q&A: Finite maps and environments