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

Thu 27 Aug

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

15:30 - 17:10
Afternoon SessionminiKanren at miniKanren
Chair(s): Nada Amin Harvard University, Weixi Ma Indiana University
15:30
20m
Talk
mediKanren: A System for Bio-medical Reasoning
miniKanren
Michael Patton University of Alabama at Birmingham, Gregory Rosenblatt University of Alabama at Birmingham, USA, William E. Byrd University of Alabama at Birmingham, USA, Matthew Might University of Alabama at Birmingham | Harvard Medical School
Link to publication
15:50
20m
Talk
Relational Synthesis for Pattern Matching
miniKanren
Dmitrii Kosarev JetBrains Research, Saint Petersburg State University, Dmitri Boulytchev St. Petersburg State University, St. Petersburg, Russia
Link to publication
16:10
20m
Talk
Some Novel miniKanren Synthesis Tasks
miniKanren
Jason Hemann Northeastern University, United States, Daniel P. Friedman Indiana University, USA
Link to publication
16:30
20m
Talk
A Relational Interpreter for Synthesizing JavaScript
miniKanren
Artem Chirkov University of Toronto Mississauga, Gregory Rosenblatt University of Alabama at Birmingham, USA, Matthew Might University of Alabama at Birmingham | Harvard Medical School, Lisa Zhang University of Toronto Mississauga
Link to publication
16:50
20m
Talk
dxo: A System for Relational Algebra and Differentiation
miniKanren
Julie Steele Georgetown Day School, William E. Byrd University of Alabama at Birmingham, USA
Link to publication