April 7, 2025

The Reasoned Schemer

I dove into relational programming with "The Reasoned Schemer" and built a miniKanren library in Elm!

During my Christmas vacation I started reading The Reasoned Schemer (2nd Edition) by Daniel P. Friedman, William E. Byrd, Oleg Kiselyov, and Jason Hemann. It explores the fascinating world of relational programming.

In Elm, functions have inputs and a single output. You provide the inputs and the function produces an output. For e.g. square : Int -> Int multiplies a given integer by itself, square 5 produces 25. It's not possible to use square to go in the other direction, i.e. give it a square and have it compute its square root. You'd have to write a separate function to do that.

What's interesting about relational programming is that you can write a relation, say squareo, that generalizes square by relating pairs of integers. For e.g. squareo 4 16 relates 4 with 16. A relation supplied with arguments, such as squareo 4 16, is called a goal and a goal can either succeed, fail, or have no value. The great advantage of squareo over square is that you can pass a variable representing an unknown value, rather than a concrete integer, to squareo. This allows you to express a variety of problems involving integers and their squares. For e.g.

• The goal squareo 3 x succeeds by associating 9 with the variable x.
• The goal squareo y 9 succeeds twice, by separately associating -3 and then 3 with y.
• The goal squareo z 5 fails since there is no integer whose square is 5.
• The goal squareo w v succeeds an unbounded number of times , enumerating all pairs of integers such that v = w * w.
• Used together, the goals squareo x y and squareo -3 x succeed, regardless of the ordering of the goals, by associating 9 with x and 81 with y.

Isn't that cool?

Needless to say the book was enjoyable to read and I was overly excited to understand how it all worked. The fascinating part for me was learning that it could all be built as a library on top of a functional programming language. I jumped at the opportunity to figure out how to make it work in Elm. The result of that work was dwayne/elm-trs2, i.e. "The Reasoned Schemer (2nd Edition) in Elm".

dwayne/elm-trs2 implements and embeds the relational programming language, miniKanren, using Elm. You can use it alongside the book to explore relational programming for yourself. In addition to learning about relational programming, I learned a lot about building domain specific languages with Elm which I hope to use in future projects.

I've paused on the work for now but when I return to it, maybe next Christmas, I want to build a constraint logic programming library on top of it and implement a declarative Sudoku solver. So, stay tuned for that adventure!