I’ve spent the better part of my free time the last two months understanding and implementing my own version of miniKanren - the relational programming paradigm described in The Reasoned Schemer. 

The Logos 0.2 release now contains a version of miniKanren where I’ve rewritten the goal and goal constructor code  from scratch. In 0.1 that code was mostly adapted from the implementation in William Byrd’s dissertation. However that implementation assumed the presence of Scheme’s mandatory tail call optimization (TCO).

I was burned Clojure’s lack of TCO when solving the classic Zebra Puzzle with miniKanren. Efficient orderings worked fine, but less efficient orderings resulted in the much dreaded StackOverflow Exception.

I pondered this for a bit - since the Scheme implementation used a stream model, why not convert the Clojure code to use lazy sequences? This ended being quite a bit more difficult than I had anticipated.

Why? Because it actually forced me to understand what the Scheme implementation was actually doing, not what I thought it was doing. I had up to that point only a cursory understanding since my code was a port. The original implementation of the goal and goal constructor code is quite subtle, in fact, I would claim it’s pretty darn hard to reason about at all (I think I’ve read the description in William Byrd’s thesis about twenty times now).

After a considerable number of iterations (most failures) I came up with a workable design. Along the way I came to a perhaps controversial realization:

The most important thing about macros is their ability to allow you to naturally embed other programming paradigms. DSLs are a very weak variant of this concept.

The new version of Logos is twice as fast as the old one and much less susceptible to stack overflow. Check it out.