Write a Blog >>
ICFP 2020
Thu 20 - Fri 28 August 2020
Thu 27 Aug 2020 15:50 - 16:10 at miniKanren - Afternoon Session Chair(s): Nada Amin, Weixi Ma

We apply relational programming techniques to the problem of synthesizing efficient implementation for pattern matching construct. Although in principle pattern matching can be implemented in a trivial way, the result suffers from inefficiency in terms of both performance and code size. Thus, in practice of functional languages implementation alternative, more elaborated, approaches are widely used. However, as there are multiple kinds and flavors of pattern matching construct, these approaches have to be specifically developed and justified for each concrete inhabitant of pattern matching “zoo”. We formulate pattern matching synthesis problem in relational terms and develop a few optimizations which improve the efficiency of the synthesis and guarantee the optimality of the result. Our approach is based on relational representation of both high-level semantics of pattern matching and the semantics of an intermediate-level implementation language which makes it, in principle, more scalable as we only need to modify the high-level semantics in order to synthesize the implementation of a new feature. Our evaluation on a set of small samples, partially taken from existing literature, shows, that our framework is capable of synthesizing optimal implementations in a negligible time. The in-depth stress evaluation on a number of artificial benchmarks, however, has shown the need for future improvements

Conference Day
Thu 27 Aug

Displayed time zone: Eastern Time (US & Canada) change

15:30 - 17:10
Afternoon SessionminiKanren at miniKanren
Chair(s): Nada AminHarvard University, Weixi MaIndiana University
15:30
20m
Talk
mediKanren: A System for Bio-medical Reasoning
miniKanren
Michael PattonUniversity of Alabama at Birmingham, Gregory RosenblattUniversity of Alabama at Birmingham, USA, William E. ByrdUniversity of Alabama at Birmingham, USA, Matthew MightUniversity of Alabama at Birmingham | Harvard Medical School
Pre-print
15:50
20m
Talk
Relational Synthesis for Pattern Matching
miniKanren
Dmitrii KosarevJetBrains Research, Saint Petersburg State University, Dmitri BoulytchevSt. Petersburg State University, St. Petersburg, Russia
Pre-print
16:10
20m
Talk
Some Novel miniKanren Synthesis Tasks
miniKanren
Jason HemannNortheastern University, United States, Daniel P. FriedmanIndiana University, USA
Pre-print
16:30
20m
Talk
A Relational Interpreter for Synthesizing JavaScript
miniKanren
Artem ChirkovUniversity of Toronto Mississauga, Gregory RosenblattUniversity of Alabama at Birmingham, USA, Matthew MightUniversity of Alabama at Birmingham | Harvard Medical School, Lisa ZhangUniversity of Toronto Mississauga
Pre-print
16:50
20m
Talk
dxo: A System for Relational Algebra and Differentiation
miniKanren
Julie SteeleGeorgetown Day School, William E. ByrdUniversity of Alabama at Birmingham, USA
Pre-print