Strange Loop

Write the Other Half of Your Program: From Functional to Logic Programming

It is an unfortunate fact that there exists still a divide between the logic- and functional-programming communities. This is despite the fact that they are both attempting to achieve similar ends: declarative programming, where we specify what, not necessarily how, a value is computed.

In order to help bridge the gap between these communities, we aim to show functional programmers how easy it is to transform non-trivial functional programs into relations, or logic programs. To do so, we demonstrate a process for hand-compiling, through a series of correctness-preserving transformations, a program written in a subset of Scheme to an equivalent miniKanren program. We will describe steps for improving the behavior of the resultant miniKanren program, and we expect to demonstrate an automated system capable of performing part of this compliation automatically.

Jason Hemann

Jason Hemann is a fourth-year doctoral student at Indiana University specializing in programming languages. His interests include functional and constraint-logic programming. He is currently an Associate Instructor for the Programming Languages course at Indiana University.

Daniel Friedman

Indiana University

Daniel P. Friedman is Professor of Computer Science at Indiana University. He is co-author of The Little Schemer, The Seasoned Schemer, The Reasoned Schemer, Scheme and the Art of Programming, and Essentials of Programming Languages, 3rd Edition, all published by MIT Press.