SICP amb

amb.clj

;; missionary implementation of SICP's [amb](http://sarabander.github.io/sicp/html/4_002e3.xhtml#g_t4_002e3)

(ns amb
  (:refer-clojure :exclude [require eval])
  (:require [missionary.core :as m]))

(deftype FlowIterator [^:unsynchronized-mutable iterator
                       ^:unsynchronized-mutable pending?]
  clojure.lang.IFn
  (invoke [this]
    (set! iterator
          (iterator (partial this false)
                    (partial this true)))
    this)
  (invoke [this done?]
    (locking this
      (set! pending? false)
      (when done? (set! iterator nil))
      (.notify this)))
  java.util.Iterator
  (hasNext [this]
    (locking this
      (while pending?
        (try (.wait this)
             (catch InterruptedException _
               (iterator))))
      (some? iterator)))
  (next [this]
    (locking this
      (set! pending? true)
      @iterator)))

(defmacro eval [& body]
  `((->FlowIterator (m/ap ~@body) true)))

(defn try-again [^java.util.Iterator it]
  (if (.hasNext it) (.next it) :done))

(defmacro require [form]
  `(when-not ~form (m/amb>)))

(defmacro an-element-of [items]
  `(loop [items# (seq ~items)]
     (require items#)
     (m/amb> (first items#)
          (recur (next items#)))))

(defmacro an-integer-starting-from [n]
  `(loop [n# ~n] (m/amb> n# (recur (+ n# 1)))))

(defn find-divisor
  ([n] (find-divisor n 2))
  ([n d]
   (cond
     (< n (* d d)) n
     (zero? (mod n d)) d
     :else (recur n (inc d)))))

(defn prime? [n]
  (= n (find-divisor n)))

(defn prime-sum-pair [l1 l2]
  (eval
    (let [a (an-element-of l1)
          b (an-element-of l2)]
      (require (prime? (+ a b)))
      (list a b))))

(comment

  (def i1 (prime-sum-pair '(1 3 5 8) '(20 35 110)))
  (try-again i1)                                            ;; (3 20)
  (try-again i1)                                            ;; (3 110)
  (try-again i1)                                            ;; (8 35)
  (try-again i1)                                            ;; :done

  (def i2 (prime-sum-pair '(19 27 30) '(11 36 58)))
  (try-again i2)                                            ;; (30 11)
  (try-again i2)                                            ;; :done

  )