One thing I love about this wonderful story is that it shows you can use constraint logic programming to solve a problem (in a hilariously roundabout way), by u

One thing I love about this wonderful story is that it shows you can use constraint logic programming to solve a problem (in a hilariously roundabout way), by using a tower of languages: 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 https://dl.acm.org/doi/10.1145/3110252 and http://io.livecode.ch/learn/gregr/icfp2017-artifact-auas7pp http://io.livecode.ch/learn/gregr/icfp2017-artifact-auas7pp