ICFP 2021
Sun 22 - Sat 28 August 2021
Thu 26 Aug 2021 20:05 - 20:35 at miniKanren - Session A Chair(s): William E. Byrd

We study the worst-case time complexity of relational programs for the canonical implementation of miniKanren. We propose a model that breaks the evaluation time in miniKanren into several different parts and provides methods to estimate the complexity of these parts. These methods can be combined into an approach for analyzing the complexity of recursive relations using the ideas originating from symbolic execution. Our approach puts a number of limitations on the program being analyzed but we show that is still practically applicable by applying it to a number of typical relations in miniKanren.

Thu 26 Aug

Displayed time zone: Seoul change

20:00 - 21:30
Session AminiKanren at miniKanren
Chair(s): William E. Byrd University of Alabama at Birmingham, USA
20:00
5m
Day opening
Opening Remarks
miniKanren

20:05
30m
Paper
A Complexity Study for Interleaving Search
miniKanren
Dmitry Rozplokhas , Dmitri Boulytchev Saint Petersburg State University / JetBrains Research
Pre-print Media Attached
20:35
30m
Paper
metaKanren: Towards a Metacircular Relational Interpreter
miniKanren
Bharathi Ramana Joshi IIIT Hyderabad, William E. Byrd University of Alabama at Birmingham, USA
Pre-print Media Attached
21:05
25m
Paper
A New Higher-order Unification Algorithm for ╬╗Kanren
miniKanren
Weixi Ma , Daniel P. Friedman Indiana University, USA
Pre-print Media Attached