Reproduce “An Empirical Study of Rational Tree Unification for miniKanren” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Eridan Domoratskiy, Dmitrii Kosarev, Dmitry Boulytchev
Researchers at St. Petersburg State University developed and empirically evaluated a rational tree unification algorithm for miniKanren. The work improved equirecursive type inference performance and provided critical insights into effective implementation strategies and occurs check behaviors within non-deterministic relational programming.
Key insights
- Complex data structures like path-compression or union-find for equation systems did not offer significant performance benefits over simpler map-based approaches and added substantial complexity.
- The "attributed variable" optimization was essential, and a novel "variable comparing" heuristic consistently improved performance while also reducing variable numbers in answers.
- An immediate "Trivial" occurs check strategy vastly outperformed delayed strategies in miniKanren's non-deterministic search, preventing wasted computation on invalid cyclic paths.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.