Efficient fair conjunction for structurally-recursive relations

Peter Lozov, Dmitry Boulytchev

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

We present a new, fair, conjunction evaluation strategy for relational programming language miniKanren. Unlike the original left-biased conjunction, our approach controls the order of conjunct execution based on the intrinsic properties of relation definitions. We present both the formal study of conjunction fairness and practical evaluation, which demonstrates the essential improvement in terms of both performance and convergence.

Original languageEnglish
Title of host publicationPEPM 2021 - Proceedings of the 2021 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, Co-located with POPL 2021
PublisherAssociation for Computing Machinery
Pages58-73
Number of pages16
ISBN (Electronic)9781450383059
DOIs
StatePublished - 18 Jan 2021
Event2021 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, PEPM 2021, co-located with the Annual Symposium on Principles of Programming Languages, POPL 2021 - Virtual, Online, Denmark
Duration: 18 Jan 202119 Jan 2021

Publication series

NamePEPM 2021 - Proceedings of the 2021 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, Co-located with POPL 2021

Conference

Conference2021 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, PEPM 2021, co-located with the Annual Symposium on Principles of Programming Languages, POPL 2021
CountryDenmark
CityVirtual, Online
Period18/01/2119/01/21

Scopus subject areas

  • Computer Graphics and Computer-Aided Design
  • Computer Science Applications

Keywords

  • evaluation strategies
  • miniKanren
  • operational semantics
  • relational programming

Fingerprint

Dive into the research topics of 'Efficient fair conjunction for structurally-recursive relations'. Together they form a unique fingerprint.

Cite this