Improving stableKanren’s Backward Compatibility

on YouTube ↗23m

" summary

stableKanren gains two concrete changes to run legacy miniKanren code: a syntactic analyzer has-negation that skips heavyweight stable-model contradiction checks for definite and non-negated relations, and a new execution API run-partial that returns answers for define/defineo relations even when unsatisfiable stableKanren rules coexist. Implementation converts defino handling into local negation checks and preserves full checking only when negation appears. Empirical result: stratified examples drop from 32.6s to 0.01s, and standard infinite-result miniKanren relations now produce answers.

AI-written summary · about

" chapters (11)

1. 0:00stableKanren introduction
2. 1:06Preliminaries on miniKanren and stableKanren
3. 3:59Backward compatibility issues
4. 6:27stableKanren semantics
5. 11:27Handling contradictions
6. 13:13Current limitations
7. 13:58Proposed fix
8. 16:09Solutions implemented
9. 16:50Performance gains
10. 19:40Performance results
11. 20:02Conclusion

" related talks

• 44mA Vision for Relational Programming in miniKanrenWilliam E. Byrd · Code Mesh 2015
• 43mPost FunctionalDavid Nolen · Tech Mesh 2012
• 23mmediKanren: A System for Bio-medical ReasoningByrd · miniKanren 2020
• 50mA Relational Exploration of the Chomsky HierarchyDaniel Friedman, William E. Byrd · Strange Loop 2013
• 22mDependency-aware Code NaturalnessJunjie Chen, Chen Yang, Jiajun Jiang, Yuliang Huang · OOPSLA 2024
• 36mEnhanced and Efficient Reasoning in Large Language ModelsLes Valiant · The Role of TCS in Modern Machine Learning
• 55mLearning Safe Action ModelsBrendan Juba · Lower Bounds, Learning, and Average-Case Complexity
• 21mOptimizing Optimizations, Declaratively: Optimizing the Higher-Order Functions in(…)Hiromi Ishii · EGRAPHS 2026