Eli Bendersky’s website » Blog Archive

SICP section 4.3.3

January 11th, 2008 at 6:38 pm

I’ve implemented the amb evaluator fully before starting with section 4.3 – it can be downloaded here

Exercise 4.50

I will use the existing amb, passing it a shuffled list of choices:

(defun ramb? (exp) (tagged-list? exp 'ramb))

(defun analyze-ramb (exp)
  (analyze-amb
    (cons 'ramb
          (shuffle-list (amb-choices exp)))))

shuffle-list is this naive¹ procedure:

(defun shuffle-list (lst)
  (sort lst #'(lambda (x y) (zerop (random 2)))))

And finally, this has to be added to the cond in analyze.:

  ((ramb? exp)
    (analyze-ramb exp))

Exercise 4.51

Adding this to the cond in analyze.:

  ((permanent-set? exp)
    (analyze-permanent-set exp))

And this is the implementation:

(defun permanent-set? (exp) (tagged-list? exp 'permanent-set!))

(defun analyze-permanent-set (exp)
  (let ((var (assignment-variable exp))
        (vproc (analyze. (assignment-value exp))))
    (lambda (env succeed fail)
      (funcall vproc
        env
        (lambda (val fail2)
          (set-variable-value! var val env)
          (funcall succeed
            'ok
            (lambda ()
              (funcall fail2))))
        fail))))

Note that it’s very similar to analyze-assignment, except taht it doesn’t roll back the old value in the fail continuation passed to vproc.

Exercise 4.52

(defun analyze-if-fail (exp)
  (let ((pproc (analyze. (if-predicate exp)))
        (cproc (analyze. (if-consequent exp))))
    (lambda (env succeed fail)
      (funcall pproc
        env
        (lambda (pred-value fail2)
          (if (true? pred-value)
            pred-value
            (funcall fail)))
        (lambda ()
          (funcall cproc env succeed fail))))))

With the usual additions to the evaluator:

(defun if-fail? (exp) (tagged-list? exp 'if-fail))

And into analyze.:

  ((if-fail? exp)
    (analyze-if-fail exp))

Exercise 4.53

It prints:

((8 35) (3 110) (3 20))

Although the let form always fails (it calls (amb) as its last statement), the pairs get added into pairs, because permanent-set! doesn’t roll assignments back from failed paths.

Exercise 4.54

(defun analyze-s-require (exp)
  (let ((pproc (analyze. (s-require-predicate exp))))
    (lambda (env succeed fail)
      (funcall pproc
        env
        (lambda (pred-value fail2)
          (if (not (true? pred-value))
            (funcall fail)
            (funcall succeed 'ok fail2)))
        fail))))

¹ It’s naive because it’s inefficient and doesn’t produce a perfect shuffle. Rather, the shuffle depends on the sorting algorithm. However, for our needs here, this shuffle is fine.

This entry was posted on Friday, January 11th, 2008 at 18:38 and is filed under SICP. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

3 Responses to “SICP section 4.3.3”

Flávio Cruz Says:
February 6th, 2008 at 18:35
In exercise 4.53 you have:
((8 35) (3 100) (3 20) (1 100))

but 100 isn’t in any list (typing error?).

My interpreter printed:
((8 35) (3 110) (3 20))
eliben Says:
February 8th, 2008 at 08:01
Yes, this is a typo (I mistakingly provided 100 and not 110 to the evaluator in the second list).
I’ve fixed it now.

Thanks

PShin

Says:
October 23rd, 2009 at 20:42

I think your solution to Exercise 4.52 is flawed. In particular, succeed is never called when pproc evaluates to true, thereby failing to continue to the next statement. For example, the following code will fail to print ‘done:

(define (test)
  (if-fail (let ((a (amb 1 2 3 4 5)))
	     (require (even? a))
	     a)
	   'failed)
  'done)
(test)

My suggestion for a fix is as follows:

(defun analyze-if-fail (exp)
  (let ((pproc (analyze. (if-predicate exp)))
        (cproc (analyze. (if-consequent exp))))
    (lambda (env succeed fail)
      (funcall pproc
        env
        succeed
        (lambda ()
          (funcall cproc env succeed fail))))))