CS61A		MIDTERM I REVIEW SOLUTIONS			SPRING 2004

1.   (butfirst '(help!))  ==> ()

     (lambda (x) (/ x 0)) ==> procedure

     (+ 27 '(word 1 0)) ==> Error: + not a number: (word 1 0)

     (and 127 ((lambda (y) #f))) ==> Error: too few arguments to: ((lambda (y) #f))
    
     ((lambda (foo)
        (lambda (for)
	   (foo for)))
     (lambda (x) (* x x)))  ==> procedure
     
     ((lambda (x) (* 2 (x x))) (lambda (y) (* 4 (y y)))) ==> infinite loop

     (cond (first '(1 2 3))
           (else 'foo))      ==> (1 2 3)

     (if (23) (23) (23)) ==> error: 23 not a procedure
 
     ((let ()
      (lambda () 2)))  ==> 2

     (every (lambda (x) (word (first x) '- x)) '(waiting for my rocket to come))
       ==> (w-waiting f-for m-my r-rocket t-to c-come)
     
     (compose compose compose) ==> procedure



2.   a)  NORMAL
         (foo (square (* 1 1)) (square (* 1 1)))
         (square (* 1 1))
         (* (* 1 1) (* 1 1))    ;; 3 calls to *
         1

         APPLICATIVE
         (foo (square (* 1 1)) (square (* 1 1)))
         (foo (square 1) (square 1))       ;; 2 calls to *
         (foo 1 1)                         ;; 2 more cals, 4 in total
         1

      b) NORMAL
         (bar (square (* 1 1)) (square (* 1 1)))
         (* (square (* 1 1)) (square (* 1 1)) (square (* 1 1)))
         (* (* (* 1 1) (* 1 1)) (* (* 1 1) (* 1 1)) (* (* 1 1) (* 1 1)))  ;; 10 calls
         1 
        
         APPLICATIVE  
         (bar (square (* 1 1)) (square (* 1 1)))
         (bar (square 1) (square 1))      ;; 2 calls 
         (bar 1 1)                        ;; 2 more calls
         (* 1 1 1)                        ;; last one, 5 all together



3.  Theta (2^n)   ;; 2*2^n also okay
    Theta (1)
    Theta (2^n)   
    Theta (n)     ;; 2n also ok



4. (define (interleave sent1 sent2)
     (if (empty? sent1) 
	 sent2
	 (se (first sent1) (interleave sent2 (bf sent1))))))
         



5.  You'll probabaly need a helper. Ours breaks up a word into pairs:

    STk> (pair-up 'foo)
    (fo oo)

    ;; break up word into pairs of adjacent letters
    (define (pair-up wd)
       (if (= (count wd) 2)
           (se wd)
           (se (word (first wd) (first (bf wd)))
	       (pair-up (bf wd)))))

    ;; run through the word stopping when the first two-letter substring
    ;; --in reverse order--is in (breakup wd)
    (define (for-and-rev? wd)
       (if (empty? (bf wd))
           #f
           (or (member? (word (first (bf wd)) (first wd))
	                (pair-up wd))
               (for-and-rev? (bf wd)))))



6.  (define (good-enuf? a b c)
       (or (equal? a b)
           (sentence? c)
           (and (odd? (+ a b c)) (equal? (- a b) -2))))



7.  (a) (define (make-keeper func)
           (lambda (sent) (keep func sent)))

    (b) (define (make-keeper func)
	   (lambda (sent)
	      (cond ((empty? sent) '())
		    ((func (first sent))
		     (se (first sent) ((make-keeper func) (bf sent))))
		    (else ((make-keeper func) (bf sent))))))



8.  STk> (every (lambda (x) '()) '(cs61a 12 his))
    ()
    STk> ((lambda (x) (x x x)) (lambda (a b) 'silver))
    silver



9.  (define doublet? wd1 wd2)
      (cond ((or (empty? wd1) (empty? wd2)) #f)
            ((equal? (first wd1) (first wd2))
             (doublet? (bf wd1) (bf wd2) ))
  	    (else (equal? (bf wd1) (bf wd2)) )))
   
    The trick is that once you find the point at which the two wor ds
    differ, the rest had better be the same or they're not doublet s. 



10. (define (count-to n)
       ((repeated (lambda (x) (se x (+ (last x) 1))) (- n 1)) '(1)))



11. (define (constant-fn? funct sent)
       (cond ((or (empty? sent) (empty? (bf sent)))
              #t)
	     ((equal? (funct (first (first sent)) 
		      (funct (first (bf sent)))))
	      (constant-fn? funct (bf sent)))
	     (else #f)))

            

12. Without constant-fn?
    (define (make-constant-checker test)
       (lambda (sent)
          (cond ((or (empty? sent) (empty? (bf sent)))
                 #t)
	        ((equal? (test (first (first sent)) 
	  	         (test (first (bf sent)))))
	         ((make-constant-checker test) (bf sent)))
	        (else #f)))

    With constant-fn?
    (define (make-constant-checker test)
       (lambda (sent)
          (constant-fn? test sent)))