A micro-Kanren implementation in Common Lisp
sī-Kanren, a microKanren implementation in Common Lisp, with disequality constraint
sī-Kanren is based on the 2013 Scheme Workshop paper by Jason Hemann and Dan Friedman. Other resources are available on the miniKanren website. It's written in "pure" and simple Common Lisp, without external libraries like pmatch, guard or things like that, nor record types or structs. The constraint store in fact, as a whole, has the form:
cs = '(((s) . c) . (d))
s is the substitution,
c the counter and
d the disequality store.
For more information:
- Excellent survey paper on unification: Kevin Knight.
- Disunification papers: Hubert Comon , Pierre Lescanne.
- Combining Unification and Disunification Algorithms: Klaus U. Schulz.
- And, above all, the miniKanren uncourse series, by William Byrd!
- core miniKanren (
=/=constraint, and thus it's the first microKanren written in Common Lisp with this feature (at
least, as far as I know).
3. Reification of all the logic queries variables
x x0... in
(run _ (x x0...)...). It looks
like a trick of magic too beautiful to not include it. :magic_wand:
4. Interactive request of a solution/s, with
5. Pretty formatting of the answer/s.
Many examples can be found in the playground file.
Inspiration for a simple implementation in Common Lisp, from cl-microkanren.
Inspiration for the implementation of the disequality store, from microKanren-sagittarius.
I took the Zebra Puzzle example here[^1].
The version of the nlet-tail macro (among others things), from Let Over Lambda, by Doug Hoyte (@hoytech).
And, of course, last but not least, many thank's to @webyrd for his sensational work!
As for the name, sī is the Chinese unit of measurement for 10 micrometers: since compared to microKanren sī-Kanren also contains the disequality store, it seemed to me a fair way to give credit to this system. :grin: And since I think it can be pronounced like a c (more or less...), as in Common Lisp, the circle closes[^2].
[^0]: Tested on SBCL v. 2.3.0 [^1]: @alex-hhh Hope it's ok for you! Here's the CC BY-NC-SA 4.0 license link. [^2]: Cit.: The Stand, Stephen King