Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.26016 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915586640969728 |
|---|---|
| author | Arntzenius, Michael |
| author_facet | Arntzenius, Michael |
| contents | miniKanren's key semantic advance over Prolog is to implement a complete yet efficient search strategy, fairly interleaving execution between disjuncts. This fairness is accomplished by bounding how much work is done exploring one disjunct before switching to the next. We show that the same idea -- fairness via bounded work -- underlies an elegant compositional approach to implementing worst-case optimal joins using a seekable iterator interface, suitable for shallow embedding in functional languages. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_26016 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fair intersection of seekable iterators Arntzenius, Michael Programming Languages miniKanren's key semantic advance over Prolog is to implement a complete yet efficient search strategy, fairly interleaving execution between disjuncts. This fairness is accomplished by bounding how much work is done exploring one disjunct before switching to the next. We show that the same idea -- fairness via bounded work -- underlies an elegant compositional approach to implementing worst-case optimal joins using a seekable iterator interface, suitable for shallow embedding in functional languages. |
| title | Fair intersection of seekable iterators |
| topic | Programming Languages |
| url | https://arxiv.org/abs/2510.26016 |