4 ms·

Wait--it does run backwards!? I had thought that the non-logical features at the Prolog-implementation-of-Lisp level would lose relationality. And it does, at

Wait--it does run backwards!? 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!

will_byrd 6y ago
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
abeppu 6y ago
I wanna say that I really appreciate that the one of the deities to whom Vidrun prays participates in (enlightening) discussion around fanfic about his work.

will_byrd 6y ago

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

abeppu 6y ago

I wanna say that I really appreciate that the one of the deities to whom Vidrun prays participates in (enlightening) discussion around fanfic about his work.