Summer 2003 Final Review Problems

1.  LAZY

    Assume we change FORCE-IT from what it was before:

    (define (force-it obj)
      (if (thunk? obj)
          (actual-value (thunk-exp obj) (thunk-env obj))
          obj))

    To this new version:
    
    (define (force-it obj)
      (if (thunk? obj)
          (mc-eval (thunk-exp obj) (thunk-env obj))
	obj))


    Assume the following functions are typed at the lazy prompt:

    (define (identity x) x)

    (define (foo a b)
      (+ (bar a) b))

    (define (bar a) (* a a))  

    Fill in the blanks with the value returned by the lazy evaluator
    for each of the following expressions (if something abnormal
    happens, please describe): 

    (bar 3)


    ((lambda (x) (* x x)) ((lambda (x) x) 5))


    (foo 6 7)
    

    (let ((a +) (b 4))
       (+ b b))


    (identity (identity 6))

2.  QUERY

    Write logic rules for the following relation:
 
    ;;; Query input:
    (removing 2 from (1 2 3 2) yields ?what)
    
    ;;; Query results:
    (removing 2 from (1 2 3 2) yields (1 3))
 
3.  AMB

    Write a function AN-ATOM-OF that dispenses the atomic elements of
    a deep list (not including empty lists) in some unspecified
    order. For example: 

    ;;; Amb-Eval input:
    (an-atom-of '((a) ((b (c)))))
    
    ;;; Starting a new problem 
    ;;; Amb-Eval value:
    a
    
    ;;; Amb-Eval input:
    try-again
    
    ;;; Amb-Eval value:
    b
    
    ;;; Amb-Eval input:
    try-again
    
    ;;; Amb-Eval value:
    c
    
    ;;; Amb-Eval input:
    try-again
    
    ;;; There are no more values of
    (an-atom-of (quote ((a) ((b (c))))))
            
    Then use this function to write DEEP-MEMBER using AMB. 

4.  QUERY

    Write logic rules for the following relation:

    ;; Query input:
    (the fib of (a a a a) is ?what)
    
    ;; Query results:
    (the fib of (a a a a) is (a a a a a a a a))   ;; 1 1 2 3 5 8 
    
    ;; Query input:
    (the fib of () is ?what)
    
    ;; Query results:
    (the fib of () is (a)) 

5.  TREES     
          
    tree1 --> (1)
             / | \
          (2) (3) (4)
           |      / \ 
          (5)  (6)   (7)

    (path-to 5 tree1) => (1 2 5)
    (path-to 3 tree1) => (1 3)
    (path-to 8 tree1) => #f

    Write PATH-TO. It returns either a path to the node, or #f if none
    exists. 

6.  AMB

    A Stanford guy changes EVAL-ASSIGNMENT by commenting out a line:
    
    (define (eval-assignment exp env succeed fail)
      (ambeval (assignment-value exp)
	       env
	       (lambda (val fail2)
		 (let* ((var (assignment-variable exp))
			(old-value
			 (lookup-variable-value var env)))
		   (set-variable-value! var val env)
		   (succeed 'ok
			    (lambda ()
			      (set-variable-value! var old-value env)
			      ;;(fail2)
			      ))))
	       fail))

	
    Fill in the blank in the following interaction with the amb evaluator:

    ;;; Amb-Eval input:
    (define a 3)

    ;;; Starting a new problem 
    ;;; Amb-Eval value:
    ok

    ;;; Amb-Eval input:
    (set! a 100)

    ;;; Starting a new problem 
    ;;; Amb-Eval value:
    ok

    ;;; Amb-Eval input:
    try-again



    ___________________________________________________

7.  MUTATION
    
    Fill in the blanks to define FLATTEN!, which takes a (possibly)
    nested list that is non-null and flattens it destructively. Do not 
    allocate new pairs (do not call CONS). Use APPEND! if you need to.
 
    STk> (define list1 (list (list 1 (list 2 3 'four) (list 'five))))	
    ((1 (2 3 four) (five)))
    STk> (flatten! list1)
    (1 2 3 four five)
    STk> list1
    (1 2 3 four five)
    STk> (define list2 (list (list (list 3))))
    STk> (define list3 list2)
    STk> (flatten! list2)
    (3)
    STk> list2
    (3)
    STk> list3
    (3)
 
    (define (flatten! lst)
      (cond ((not (pair? lst)) lst)
            ((pair? (car lst))
             (let ((flat-car (flatten! (car lst))))
	      

	     
            (else


      lst)    

8.  QUERY

    Write logic rules for the following relation:

    ;;; Query input
    (the max of (a a a a) and (a a) is ?what)
    
    ;;; Query results:
    (the max of (a a a a) and (a a) is (a a a a))

9.  QUERY

    Write logic rules for the following relation:

    ;;; Query input:
    ((a b c d) interleaved with (1 2) is ?what)

    ;;; Query results:
    ((a b c d) interleaved with (1 2) is (a 1 b 2 c d))

    ;;; Query input:
    ((cs61a cool) interleaved with ?what is (cs61a is cool))

    ;;; Query results:
    ((cs61a cool) interleaved with (is) is (cs61a is cool))

    Wow! This logic interpreter is so smart it knows that CS61A is cool!

10. AMB

    Add a new special form to the amb evaluator called NEVER-FAIL. It
    takes one argument and ensures that it never fails.

    ;;; Amb-Eval input:
    (never-fail 2)
 
    ;;; Amb-Eval value:
    2
   
    ;;; Amb-Eval input:
    try-again

    ;;; Amb-Eval value:
    2
        
    Typing "try-again" any number of times should cause 2 to be
    returned. This special form is not very useful. It helps you to
    create infinite loops:

    ;;; Amb-Eval input:
    (let ((a (never-fail 4)))
      (amb))


    ... bye bye