mukanren.js

const emptyState = null;

// `var` in muKanren.
const v = c => Symbol(c);
// `var?` in muKanren.
const isVar = c => typeof c === 'symbol';

const walk = (u, s) => {
  if (s === null) {
    return u;
  }
  let pr = s(u);
  if (isVar(pr)) {
    return walk(pr, s);
  } else if (pr instanceof Array) {
    return pr.map(v => walk(v, s));
  }
  return pr;
};

const extS = (x, v, s) => c => (x === c ? v : s === null ? x : s(x));

const unit = s =>
  (function*() {
    yield s;
  })();

const mzero = Symbol('mzero');

const unify = (u, v, s) => {
  u = walk(u, s);
  v = walk(v, s);

  if (u === v) {
    return s;
  } else if (isVar(u)) {
    return extS(u, v, s);
  } else if (isVar(v)) {
    return extS(v, u, s);
  } else if (u instanceof Array && v instanceof Array) {
    if (u.length !== v.length) {
      return false;
    }
    for (let i = 0; i < u.length; i++) {
      s = unify(u[i], v[i], s);
      if (s === false) {
        return false;
      }
    }
    return s;
  }
};

const eqeq = (u, v) => s => {
  s = unify(u, v, s);
  if (s !== false) {
    return unit(s);
  }
  return mzero;
};

const callFresh = f => f(new Array(f.length).fill(0).map(v));

const disj = (g1, g2) => s => mplus(g1(s), g2(s));
const conj = (g1, g2) => s => bind(g1(s), g2);

const mplus = function*(s1, s2) {
  if (typeof s1 === 'function') {
    yield* mplus(s1(), s2);
    return;
  }
  if (typeof s2 === 'function') {
    yield* mplus(s1, s2());
    return;
  }
  let n;
  while (true) {
    n = s1.next();
    if (!n.done) yield n.value;
    n = s2.next();
    if (!n.done) yield n.value;
  }
};

const bind = function*(s, g) {
  if (typeof s === 'function') {
    return () => bind(s(), g);
  }
  for (let sub of s) {
    yield* g(s);
  }
};

let run = function*(f, numResults = false) {
  let result = v();
  let stream = f(result)(emptyState);
  let i = 0;
  for (let r of stream) {
    if (i >= numResults) {
      return;
    }
    yield walk(result, r);
    i++;
  }
};

let fives = x => disj(eqeq([x], [5]), s => () => fives(x)(s));
let sixes = x => disj(eqeq([x], [6]), s => () => sixes(x)(s));
let fivesAndSixes = x => disj(fives(x), sixes(x));

for (let result of run(fivesAndSixes, 5)) {
  console.log(result);
}