Logic Programming

miniKanren (Friedman, Byrd, Kiselyov) embeds relational/logic programming in a few hundred lines of Scheme. core.logic brings it to Clojure. Common Lisp has Prolog embeddings (PAIP's Prolog, Allegro Prolog) and Screamer (nondeterministic programming).

Book: *The Reasoned Schemer*.

;; miniKanren (Racket: (require minikanren) or faster-minikanren)
(run* (q) (== q 5))                       ; (5)
(run* (q) (conde ((== q 'tea)) ((== q 'coffee))))   ; (tea coffee)

(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 '(1 2) '(3 4) q))      ; ((1 2 3 4))
(run* (x y) (appendo x y '(1 2 3)))       ; all ways to split the list: running "backwards"!
;; ((() (1 2 3)) ((1) (2 3)) ((1 2) (3)) ((1 2 3) ()))