Improving Refutational Completeness of Relational Search via Divergence Test

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

Аннотация

We describe a search optimization technique for implementation of relational programming language miniKanren which makes more queries converge. Specifically, we address the problem of conjunction non-commutativity. Our technique is based on a certain divergence criterion that we use to trigger a dynamic reordering of conjuncts. We present a formal semantics of a miniKanren-like language and prove that our optimization does not compromise already converging programs, thus, being a proper improvement. We also present the prototype implementation of the improved search and demonstrate its application for a number of realistic specifications.
Язык оригиналаанглийский
Название основной публикацииProceedings of the 20th International Symposium on Principles and Practice of Declarative Programming
ИздательAssociation for Computing Machinery
Число страниц20
ISBN (электронное издание)978-1-4503-6441-6
СостояниеОпубликовано - 3 сен 2018

Fingerprint Подробные сведения о темах исследования «Improving Refutational Completeness of Relational Search via Divergence Test». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Булычев, Д. Ю., & Rozplokhas, D. (2018). Improving Refutational Completeness of Relational Search via Divergence Test. В Proceedings of the 20th International Symposium on Principles and Practice of Declarative Programming Association for Computing Machinery.