2025/10/03 by Rafaello Sanna, William E. Byrd, Sanna, Rafaello +3
Computer Science · #Logic, programming, and type systems #Constraint Satisfaction and Optimization #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.2510.03170
We present Kanren (read: set-Kanren), an extension to miniKanren with constraints for reasoning about sets and association lists. Kanren includes first-class set objects, a functionally complete family of set-theoretic constraints (including membership, union, and disjointedness), and new constraints for reasoning about association lists with shadowing and scoped lookup. These additions allow programmers to describe collections declaratively and lazily, without relying on structural encodings and eager search over representation spaces. The result is improved expressiveness and operational behavior in programs that manipulate abstract data -- particularly interpreters -- by supporting set equality based on contents, enabling finite failure. We describe the design and implementation of Kanren in a constraint-enabled miniKanren system and illustrate its use in representative examples.