Beyond Cons: Purely Relational Data Structures
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908574664359936 |
|---|---|
| author | Sanna, Rafaello Byrd, William E. Amin, Nada |
| author_facet | Sanna, Rafaello Byrd, William E. Amin, Nada |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_03170 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Beyond Cons: Purely Relational Data Structures Sanna, Rafaello Byrd, William E. Amin, Nada Programming Languages 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. |
| title | Beyond Cons: Purely Relational Data Structures |
| topic | Programming Languages |
| url | https://arxiv.org/abs/2510.03170 |