Level 0: PROLOG
Level 1: (non-relational implementation of) LISP
Level 2: (purely functional? implementation of) microKanren
Level 3: (purely relational implementation of) tree balancing
In [0] we invert this approach, also arriving at code that behaves relationally:
Level 0: LISP
Level 1: (purely functional implementation of) miniKanren
Level 2: (purely relational implementation of) LISP
Level 3: (purely functional implementation of) tree balancing (or whatever)
At first glance it may seem goofy to implement LISP-within-miniKanren-within-LISP. After all, we started with LISP! However, the LISP we end up with inherits the relationality of its miniKanren implementation, which means we can encode our problem in LISP, but have miniKanren apply the search and constraint solving under the hood.
The last example in [0] goes further:
Level 0: LISP
Level 1: (purely functional implementation of) miniKanren
Level 2: (purely relational implementation of) LISP
Level 3: (purely functional implementation of) LISP
The extra level of LISP interpretation allows us to put logic variables representing unknown values in new positions, giving us increased expressivity, at a significant performance cost.
If we can figure out how to apply staged evaluation/partial evaluation/supercompilation/etc. effectively to these towers of interpreters to reduce the interpretive overhead, these "jokes" may turn out to be surprisingly useful.
[0] https://dl.acm.org/doi/10.1145/3110252 and http://io.livecode.ch/learn/gregr/icfp2017-artifact-auas7pp
I had thought that the non-logical features at the Prolog-implementation-of-Lisp level would lose relationality. And it does, at the level of the Lisp implementation. But you gain relationality at the microKanren level!
I love it!