Abstract

Logic Programming, Semantics, and a Bit of Cleverness or How to Speed Up a Relational Interpreter or Bubbletea-Driven Programming

Wouldn’t it great if we could take an operational semantics (or typing judgments, or whatever), directly express the semantics in a high-level logic programming language, and get an interpreter that acts as a relation instead of a function? Such a “relational interpreter” could perform program synthesis and other interesting and useful tasks “for free.”

The good news it is possible to write a relational interpreter in a pure subset of miniKanren or Prolog! The bad news, of course, is that the resulting interpreter is unbelievably slow! The better news is that we can use a variety of techniques to radically speed up a relational interpreter (by at least 8 orders of magnitude), and there is reason to think we’ll be able to speed it up much more in the near future.

Learn how we do it! Better yet, collaborate with us! Much of this work is being done right here at Cambridge.