μKanren

[gilch]

One of my original goals for Hissp was that it be powerful enough to easily implement a microKanren, which becomes a lot more useful with helper macros, something Python struggles with, but easy in a Lisp.

You can see the original Scheme version here.

Understanding what that code is doing is a lot easier than understanding why it is doing it, but enough on that topic has been written elsewhere.

Here's a rough first attempt in Python. I think it more or less works, but maybe I missed some edge cases.

from functools import reduce
from operator import concat

class Var(int): pass
class State:
    def __repr__(self):
        return f"State({self.subs}, {self.count})"
    def __init__(self, subs=None, count=0):
        self.subs = subs or {}
        self.count = count
    def __eq__(self, other):
        return (isinstance(other, State)
                and self.subs == other.subs
                and self.count == other.count)
    def next(self):
        self.count += 1
        return Var(self.count)

def walk(t, subs):
    b = isinstance(t, Var) and t in subs
    return walk(subs[t], subs) if b else t

def extend_subs(source, target, subs):
    return subs | {source: target}

def eq(u, v):
    return lambda s: [State(d, s.count)] if (d:=unify(u, v, s.subs)) else []

def unify(u, v, s):
    u, v = [walk(x, s) for x in [u, v]]
    match (u, v):  # Requires Python 3.10+.
        case (Var(), Var()) if u == v:
            return s
        case (Var(), _):
            return extend_subs(u, v, s)
        case (_, Var()):
            return extend_subs(v, u, s)
        case _ if u == v:
            return s

def fresh(f):
    return lambda state: f(state.next())(state)

def disj(*goals):
    return lambda state: reduce(concat, [g(state) for g in goals])

def conj(*goals):
    return lambda state: reduce(bind, goals[1:], goals[0](state))

def bind(s, g):
    return g(s[0]) + bind(s[1:],g) if s else []

Hissp can, of course, import this and layer macros on top of it, but I'd also like to try rewriting it in Lissp to begin with.

This version is about the same length as the Scheme one. Some things were easier with Python's data structures and comprehensions, but other things felt less natural.