Lazy and Nondeterministic Evaluators

42.1 A Lazy Evaluator (SICP 4.2)

Change m-apply so compound procedure arguments become thunks (delayed expressions with their environment), forced only when a primitive needs the value. Then (define (unless c usual exceptional) (if c exceptional usual)) works as an ordinary procedure, and lists become lazy streams automatically.

(define (delay-it exp env) (list 'thunk exp env))
(define (force-it obj)
  (if (tagged? obj 'thunk)
      (actual-value (cadr obj) (caddr obj))
      obj))
(define (actual-value exp env) (force-it (m-eval exp env)))
;; In m-apply: primitives get (map (lambda (e) (actual-value e env)) args);
;; compound procedures get (map (lambda (e) (delay-it e env)) args).
;; (A real implementation memoizes evaluated thunks.)

42.2 The amb Evaluator (SICP 4.3)

An evaluator in which every expression produces values through success and failure continuations, making amb a special form. It's used for puzzle solving and natural-language parsing.

;; Using the amb macro from Module 26 for a logic puzzle (SICP 4.3.2 "multiple dwelling")
(define (distinct? items)
  (cond ((null? items) #t)
        ((member (car items) (cdr items)) #f)
        (else (distinct? (cdr items)))))

(define (multiple-dwelling)
  (let* ((baker (amb 1 2 3 4 5)) (cooper (amb 1 2 3 4 5))
         (fletcher (amb 1 2 3 4 5)) (miller (amb 1 2 3 4 5)) (smith (amb 1 2 3 4 5)))
    (amb-require (distinct? (list baker cooper fletcher miller smith)))
    (amb-require (not (= baker 5)))
    (amb-require (not (= cooper 1)))
    (amb-require (not (= fletcher 5)))
    (amb-require (not (= fletcher 1)))
    (amb-require (> miller cooper))
    (amb-require (not (= (abs (- smith fletcher)) 1)))
    (amb-require (not (= (abs (- fletcher cooper)) 1)))
    (list (list 'baker baker) (list 'cooper cooper) (list 'fletcher fletcher)
          (list 'miller miller) (list 'smith smith))))
(multiple-dwelling)
;; ((baker 3) (cooper 2) (fletcher 4) (miller 5) (smith 1))