Logic Programming and miniKanren

Introduce logic variables Disjunction (each clause is a conjunction) run n, run* Get up to n / all answers =/=, symbolo, numbero, absento Disequality and type constraints

SICP 4.4 builds a logic query language (Prolog-like) on top of streams. *The Reasoned Schemer* teaches miniKanren in depth.

;; miniKanren: relational programming embedded in Scheme
;; (load faster-miniKanren or use the minikanren package: (import (minikanren)) in many systems)
(run* (q) (== q 'cat))                       ; (cat)
(run* (q) (conde ((== q 1)) ((== q 2))))     ; (1 2)
(run* (q) (fresh (x y) (== x 1) (== y 2) (== q (list x y))))   ; ((1 2))

(define (appendo l s out)
  (conde
    ((== '() l) (== s out))
    ((fresh (a d res)
       (== `(,a . ,d) l)
       (== `(,a . ,res) out)
       (appendo d s res)))))

(run* (q) (appendo '(a b) '(c d) q))         ; ((a b c d))
(run* (q) (appendo q '(d) '(a b c d)))       ; ((a b c)): running "backwards"
(run 3 (q) (fresh (x y) (appendo x y '(1 2)) (== q (list x y))))
;; ((() (1 2)) ((1) (2)) ((1 2) ()))

(define (membero x l)
  (fresh (a d)
    (== `(,a . ,d) l)
    (conde ((== a x)) ((membero x d)))))
(run* (q) (membero q '(x y z)))              ; (x y z)