CS61A Week 11 solutions LAB: ---- 4.27 Lazy vs. mutation The first time you type COUNT you get 1; the second time you get 2. Why? When you say (define w (id (id 10))) the DEFINE special form handler eval-definition EVALs its second argument (id (id 10)). Given an application, EVAL calls APPLY to invoke ID for the outer invocation, but the inner invocation is providing an argument to a compound procedure, so it's delayed. That's why COUNT is 1 -- the outer call to ID has actually happened, but not the inner one. The value of W is therefore a promise to compute (id 10), since ID returns its argument. When you ask the evaluator to print W, that promise is fulfilled, and so COUNT becomes 2. 4.29 Memoizing or not You'd expect a program that uses the same argument repeatedly to be most strongly affected. For example, I wrote (define (n-copies n stuff) (if (= n 0) '() (cons stuff (n-copies (- n 1) stuff)))) Then if you use n-copies with something requiring a fair amount of computation, such as (n-copies 6 (factorial 7)) you can see a dramatic difference. About their square/id example, remember to (set! count 0) before each experiment. Then the memoizing version leaves count at 1, whereas the non-memoizing version sets count to 2. 4.35 an-integer-between (define (an-integer-between low high) (if (> low high) (amb) (amb low (an-integer-between (+ low 1) high)))) 4.38 adjacent floors Remove the line (require (not (= (abs (- smith fletcher)) 1))) [The continuation part of the lab was just try-this.] HOMEWORK: --------- 4.25 UNLESS in normal vs. applicative order In ordinary (applicative order) Scheme, this version of FACTORIAL will be an infinite loop, because the argument subexpression (* n (factorial (- n 1))) is evaluated before UNLESS is called, whether or not n is 1. In normal order Scheme it'll work fine, because the argument subexpressions aren't evaluated until they're needed. What will actually happen is that each use of the special form IF within UNLESS will force the computation of (= n 1), but no multiplications will happen until the evaluator tries to print the result. In effect, (factorial 5) returns the thunk (lambda () (* 5 (* 4 (* 3 (* 2 (* 1 1)))))) and that gets evaluated just in time to print the answer. 4.26 Normal order vs. special forms For Ben's side of the argument we must implement UNLESS as a derived expression: (define (unless->if exp) (make-if (unless-predicate exp) (unless-consequent exp) (unless-alternative exp))) (define unless-predicate cadr) (define unless-alternative caddr) (define unless-consequent cadddr) Notice that we reversed the order of the last two subexpressions in the call to make-if. Then we just add a clause ((unless? exp) (eval (unless->if exp) env)) to the ordinary metacircular evaluator, or ((unless? exp) (analyze (unless->if exp))) to the analyzing evaluator. For Alyssa's side of the argument, we need a case in which it's useful to have a Scheme special form available as an ordinary procedure. The only thing we can do with ordinary procedures but not with special forms is use them as arguments to higher-order procedures. An example using UNLESS will be a little strained, so first we'll look at a more common situation involving a different special form, namely AND. We'd like to be able to say (define (all-true? tf-list) (accumulate and tf-list)) Now, here's the strained example using UNLESS: Suppose we have a list of true-false values and we'd like to add up the number of true ones. Here's a somewhat strange way to do it: (define zero-list (cons 0 '())) (set-cdr! zero-list zero-list) (define one-list (cons 1 '())) (set-cdr! one-list one-list) (define (howmany-true tf-list) (apply + (map unless tf-list zero-list one-list))) Zero-list is an infinite list of zeros; one-list is an infinite list of ones. We make use of the fact that MAP's end test is that its first argument is empty, so MAP will return a list the same size as the argument tf-list. For example, if tf-list is (#t #t #f #t) then map will return (1 1 0 1) created, in effect, this way: (list (unless #t 0 1) (unless #t 0 1) (unless #f 0 1) (unless #t 0 1)) And so + will return 3, the number of trues in the list. 4.28 Why force the operator of a combination? Thunks are made by APPLY, representing arguments to defined procedures. So we need a case in which the operator of an expression is the returned argument of a defined procedure. Here's an example: (((lambda (a b) a) + -) 2 3) 4.30 Side effects vs. lazy evaluation (a) Why is Ben right about for-each? For-each includes the expression (proc (car items)). As we discussed in ex. 4.28, the lazy evaluator will force the operator of that expression, i.e., PROC. The resulting procedure has two invocations of primitives, NEWLINE and DISPLAY. Evaluating those invocations will actually call the procedures, and the argument X to DISPLAY will be evaluated because DISPLAY is primitive. (b) What happens in Cy's example? First of all, in ordinary Scheme both (p1 1) and (p2 1) give the result (1 2). With the book's version of eval-sequence, (p1 1) is still (1 2) but (p2 1) is 1, because the SET! will never happen. The subprocedure P has a two-expression sequence as its body, and the first expression will never be evaluated. With Cy's version both (p1 1) and (p2 1) are (1 2), as in ordinary Scheme. (c) Why doesn't Cy's version change part (a)? The change isn't as dramatic as it may seem. Don't think that the original eval-sequence calls delay-it! It calls EVAL, and most of the time EVAL does return a value, not a thunk. In particular, a procedure call is carried out right away; it's only the *arguments* to the procedure that are delayed. That's why Cy had to use a weird example in which a SET! expression is used as an argument to a procedure in order to get the wrong result. (d) What's the right thing to do? The combination of lazy evaluation and mutation in the same language is so confusing that programmers would be surprised no matter which choice we made. That's why, in the real world, the languages that use normal order evaluation are *functional* languages in which there is no mutation or other side effects. In such a language, there are no sequences (if there are no side effects, what would be the point?) and the problem doesn't arise. But if we really wanted to have a normal-order Scheme, we'd probably want to change the semantics of the language as little as possible -- programs that work in ordinary Scheme should work in lazy Scheme too. So I think Cy is right. 4.32 Lazy trees One possibility is to use doubly-lazy lists as an alternative to interleaving, when dealing with a naturally two-dimensional problem. For example, to get pairs of integers, we could say (define (pairs a b) (cons (map (lambda (x) (cons (car a) x)) b) (pairs (cdr a) b))) Then we could use this data structure with two-dimensional versions of the usual higher order procedures. For example: (define (2dfilter pred s) (if (null? s) '() (cons (filter pred (car s)) (2dfilter pred (cdr s))))) 4.33 Quoted lazy lists Instead of ((quoted? exp) (text-of-quotation exp)) we need a more complicated treatment to turn the ordinary lists of the underlying Scheme into lazy lists. ((quoted? exp) (process-quotation (text-of-quotation exp) env)) (define (process-quotation quoted env) (if (pair? quoted) (lazy-cons (process-quotation (car quoted) env) (process-quotation (cdr quoted) env) env) quoted)) (define (lazy-cons x y env) (make-procedure '(m) (list (list 'm x y)) env)) or alternatively (define (lazy-cons x y env) (apply (lookup-variable-value 'cons env) (list x y))) This lazy-cons is the below-the-line equivalent of the above-the-line CONS on page 409. 4.36 all Pythagorean triples Replacing an-integer-between with an-integer-starting-from won't work because the AMB that provides the value for K will never fail, and so I and J will always be 1 forever. To make this work, we note that K must always be larger than I or J, so I and J can be restricted to finite ranges if we choose a value for K first: (define (a-pythgorean-triple) (let ((k (an-integer-starting-from 1))) (let ((i (an-integer-between 1 (- k 1)))) (let ((j (an-integer-between i (- k 1)))) (require (= (+ (* i i) (* j j)) (* k k))) (list i j k))))) 4.42 liars (define (liars) (define (onetrue? x y) (if x (if y #f #t) y)) (let ((betty (amb 1 2 3 4 5)) (ethel (amb 1 2 3 4 5)) (joan (amb 1 2 3 4 5)) (kitty (amb 1 2 3 4 5)) (mary (amb 1 2 3 4 5))) (require (distinct? (list betty ethel joan kitty mary))) (require (onetrue? (= kitty 2) (= betty 3))) (require (onetrue? (= ethel 1) (= joan 2))) (require (onetrue? (= joan 3) (= ethel 5))) (require (onetrue? (= kitty 2) (= mary 4))) (require (onetrue? (= mary 4) (= betty 1))) (list (list 'betty betty) (list 'ethel ethel) (list 'joan joan) (list 'kitty kitty) (list 'mary mary)))) As in the multiple dwelling puzzle, this program can be made much more efficient by checking for distinct values as we go along instead of after all values have been assigned: (let ((betty (amb 1 2 3 4 5)) (ethel (amb 1 2 3 4 5))) (require (distinct? (list betty ethel))) (let ((joan (amb 1 2 3 4 5))) (require (distinct? (list betty ethel joan))) ... 4.45 ambiguous sentence (sentence (simple-noun-phrase (article the) (noun professor)) (verb-phrase (verb lectures) (prep-phrase (prep to) (noun-phrase (simple-noun-phrase (article the) (noun student)) (prep-phrase (prep in) (noun-phrase (simple-noun-phrase (article the) (noun class)) (prep-phrase (prep with) (simple-noun-phrase (article the) (noun cat))))))))) This version means that a cat is a student in the class, and the professor lectures to another student in the class. (sentence (simple-noun-phrase (article the) (noun professor)) (verb-phrase (verb lectures) (prep-phrase (prep to) (noun-phrase (noun-phrase (simple-noun-phrase (article the) (noun student)) (prep-phrase (prep in) (simple-noun-phrase (article the) (noun class)))) (prep-phrase (prep with) (simple-noun-phrase (article the) (noun cat))))))) This version means that the professor lectures to a student, and that that student is in the class and has a cat, which may or may not be present. (sentence (simple-noun-phrase (article the) (noun professor)) (verb-phrase (verb-phrase (verb lectures) (prep-phrase (prep to) (noun-phrase (simple-noun-phrase (article the) (noun student)) (prep-phrase (prep in) (simple-noun-phrase (article the) (noun class)))))) (prep-phra
;; Programming with constraints, from section 3.3.5 of Abelson and Sussman.

;; Syntactic interface to contraint and probe objects.
;; These operations inform them that a value has become defined or undefined;
;; they have to figure out which value is involved.

(define (inform-about-value constraint)
  ((constraint 'I-have-a-value)))

(define (inform-about-no-value constraint)
  ((constraint 'I-lost-my-value)))

;; Types of constraints defined here: adder, multiplier and constant;
;; also define probe, which is a pseudo-constraint.

(define (adder a1 a2 sum)
  (define (process-new-value)
    (cond ((and (has-value? a1) (has-value? a2))
	   (set-value! sum
		       (+ (get-value a1) (get-value a2))
		       me))
	  ((and (has-value? a1) (has-value? sum))
	   (set-value! a2
		       (- (get-value sum) (get-value a1))
		       me))
	  ((and (has-value? a2) (has-value? sum))
	   (set-value! a1
		       (- (get-value sum) (get-value a2))
		       me))))
  (define (process-forget-value)
    (forget-value! sum me)
    (forget-value! a1 me)
    (forget-value! a2 me)
    (process-new-value))

  (define (me request)
    (cond ((eq? request 'I-have-a-value)
	   process-new-value)
	  ((eq? request 'I-lost-my-value)
	   process-forget-value)
	  (else
	   (error "Unknown request -- ADDER" request))))

  (connect a1 me)
  (connect a2 me)
  (connect sum me)
  me)

(define (multiplier m1 m2 product)
  (define (process-new-value)
    (cond ((or (if (has-value? m1) (= (get-value m1) 0) #f)
	       (if (has-value? m2) (= (get-value m2) 0) #f))
	   (set-value! product 0 me))
	  ((and (has-value? m1) (has-value? m2))
	   (set-value! product
		       (* (get-value m1) (get-value m2))
		       me))
	  ((and (has-value? m1) (has-value? product))
	   (set-value! m2
		       (/ (get-value product) (get-value m1))
		       me))
	  ((and (has-value? m2) (has-value? product))
	   (set-value! m1
		       (/ (get-value product) (get-value m2))
		       me))))
  (define (process-forget-value)
    (forget-value! product me)
    (forget-value! m1 me)
    (forget-value! m2 me)
    (process-new-value))

  (define (me request)
    (cond ((eq? request 'I-have-a-value)
	   process-new-value)
	  ((eq? request 'I-lost-my-value)
	   process-forget-value)
	  (else
	   (error "Unknown request -- MULTIPLIER" request))))

  (connect m1 me)
  (connect m2 me)
  (connect product me)
  me)

(define (constant value connector)
  (define (me request)
    (error "Unknown request -- CONSTANT" request))
  (connect connector me)
  (set-value! connector value me)
  me)

(define (probe name connector)
  (define (process-new-value)
    (display "Probe: ")
    (display name)
    (display " = ")
    (display (get-value connector))
    (newline))

  (define (process-forget-value)
    (display "Probe: ")
    (display name)
    (display " = ")
    (display "?")
    (newline))

  (define (me request)
    (cond ((eq? request 'I-have-a-value)
	   process-new-value)
	  ((eq? request 'I-lost-my-value)
	   process-forget-value)
	  (else
	   (error "Unknown request -- PROBE" request))))
  (connect connector me)
  me)

;; syntactic interface to connector objects

(define (has-value? connector)
  (connector 'has-value?))

(define (get-value connector)
  (connector 'value))

(define (forget-value! connector retractor)
  ((connector 'forget) retractor))

(define (set-value! connector new-value informant)
  ((connector 'set-value!) new-value informant))

(define (connect connector new-constraint)
  ((connector 'connect) new-constraint))


;; connector object generator.

(define (make-connector)
  (let ((value #f) (informant #f) (constraints '()))

    (define (set-my-value newval setter)
      (cond ((not (has-value? me))
	     (set! value newval)
	     (set! informant setter)
	     (for-each-except setter
			      inform-about-value
			      constraints))
	    ((not (= value newval))
	     (error "Contradict