6.001 Recitation – May 14, 2003

RI: Konrad Tollmar

http://www.ai.mikt.edu/~konrad/6001

• Final review

1. Iterative vs. Recursive Processes and Order of Growth

Consider the two procedures below. Assume the arguments passed in are always positive integers.

(define (odd? x)

(if (= x 1)

#t

(even? (- x 1))))

(define (even? x)

(not (odd? x)))

Given the above definitions, when the expression (odd? 24) is evaluated, does that generate a recursive or iterative process? Why?

Ans: This generates a recursive process because the not operations are delayed.

What is the order of growth of in time of the procedure even??

Ans: Ordo(x)

What is the order of growth of in space of the procedure odd??

Ans: Ordo(x)

Change one of the two functions above to make the process the opposite of what it currently is (eg. If it's a recursive process, make it iterative and if it's an iterative process, make it recursive).

Ans:

(define (even? x)

(if (= x 1)

#f

(odd? (- x 1))))

Consider the function below:

(define (power-of-2? n)

(cond ((= n 1) #t)

((< n 1) #f)

(else

(power-of-2? (/ n 2)))))

Does the function power-of-2? generate a recursive or iterative process? Why?

Ans: Iterative. No delayed operations.

What is the order of growth of in time of the procedure power-of-2??

Ans: Ordo(log(n))

What is the order of growth of in space of the procedure power-of-2??

Ans: Ordo(1)

2. Implementing Put and Get

Assume that we have one global put and get table called *global-put-table*. Define (a simplified version of) put and get as follows.

(put keys value) -- Places the value in the global table indexed by keys

(get keys) ==> value

For example,

(put '(6001 is) 'fun)

(get '(6001 is)) ==> fun

(put '(But soon is 6001) '(almost over))

(get '(But soon is 6001)) ==> (almost over)

Complete the following three definitions for put and get.

(define *global-put-table* ?? )

(define (put keys value) ?? )

(define (get keys) ?? )

--

(define *global-put-table* '() )

(define (put keys value)

(set! *global-put-table* (cons (cons key value) *global-put-table*))

)

(define (get keys)

(define (iter table)

(cond ((null? table) #f)

((equal? (caar table) keys)

(cdar table))

(else (iter (cdr table)))))

(iter *global-put-table*))

)

(define (put key value)

(let ((x (getp key)))

(if x

(set-cdr! x value)

(set! *global-put-table* (cons (cons key value) *global-put-table*)))))

(define (getp keys)

(define (iter table)

(cond ((null? table) #f)

((equal? (caar table) keys)

(car table))

(else (iter (cdr table)))))

(iter *global-put-table*))

3. Streams and Higher Order Procedures

For each of the following sets of expressions, write down what the last one will return. If it returns an error, or doesn't return at all, say so. You can assume each set of expressions is evaluated in a fresh Scheme buffer.

Set 1:

(define s1 (cons-stream 1 s1))

(define s2 (cons-stream 1 (add-streams s1 s2)))

(define s3 (cons-stream 0 (add-streams s2 s3)))

(stream-car

(stream-cdr (stream-cdr (stream-cdr (stream-cdr s3)))))

S1: (1 1 1 1 1 1…)

S2: (1 2 3 4 5 6…)

S2: (1 2 3 4 5 6…)

´+ S3: (0 1 3 6 10 …)

--------------------------

S3: (0 1 3 6 10 15 …)

--> 10

Set 2:

(define (map2 p s1 s2)

(cons-stream (p (stream-car s1) (stream-car s2))

(map2 p (stream-cdr s1) (stream-cdr s2))))

(define x (cons-stream 2 x))

(define y (cons-stream 3 (map2 - y (stream-cdr x))))

(stream-car (stream-cdr (stream-cdr (stream-cdr y))))

x: (2 2 2 2 2 ..)

y: (3 1 –1 –3 –5 ..)

--> -3

Set 3:

(empty-stream? (stream-filter odd? (stream-filter even? integers)))

Although it seems that this would evaluate to true, this expression will never return. Specifically, trying to filter the odds from an infinite stream which contains no odd numbers will fail to return, since no first value can be found. (Look at the definition of stream-filter to see why....)

(define (stream-filter pred s)

(cond ((stream-null? s) the-empty-stream)

((pred (stream-car s))

(cons-stream (stream-car s)

(stream-filter pred (stream-cdr s))))

(else (stream-filter pred (stream-cdr s)))))

(define (stream-ref s n)

(if (= n 0)

(stream-car s)

(stream-ref (stream-cdr s) (- n 1))))

(define (stream-map proc s)

(if (stream-null? s)

the-empty-stream

(cons-stream (proc (stream-car s))

(stream-map proc (stream-cdr s)))))

4. Eval

We want a special form called while with the following behavior:

(while <text-exp> <exp1> <exp1> ... <expn>)

will first evaluate the <test-exp> expression. If it is true, then while will evaluate each of the consequence expressions in turn and recurse. If the <test-exp> is false, then the while returns the value false immediately.

A. Add the while special form to the metacircular evaluator.

((while? exp) (eval-while exp env))
 (define (eval-while exp env) (let ((test (while-test exp)) (body (while-body exp))) (if (eval test env) (begin (eval-sequence body env) (eval-while exp env)) #f))) (define (while-test exp) (cadr exp)) (define (while-body exp) (cddr exp))

 

B. Add the while special form to the explicit control evaluator.

 (test (op while?) (reg exp))(branch (label ev-while)) ev-while (save exp) (save env) (save continue) (assign continue (label ev-while-test)) (assign exp (op while-test) (reg exp)) (goto (label eval-dispatch))ev-while-test (restore continue) (restore env) (restore exp) (test (op true?) (reg val)) (branch (label ev-do-while-stuff))ev-while-done (assign val (const #f)) (goto (reg continue))ev-do-while-stuff (save exp) (save env) (save continue) (assign unev (op while-body) (reg exp)) (assign continue (label ev-after-do-while-stuff)) (goto (label ev-sequence))ev-after-do-while-stuff (restore continue) (restore env) (restore exp) (goto (label ev-while))

5. Meta Circular Evaluator

We would like to introduce a new special form to our evaluator called same?. Same? always takes three arguments, and returns #t if all three arguments are eq?. Same?, however is smart in that if the first two arguments are different, then the third argument is not evaluated. Here are some examples of using same?. 

 (same? 'x 'x 'x) ==> #t(same? 'x 'x 'y) ==> #f(same? 'x 'y 'y) ==> #f(same? 'x 'y (/ 1 0)) ==> #f(same? 'x 'x (/ 1 0)) ==> Divide by Zero Error 

To add this special form to the evaluator, we need to define some data abstraction. Define the function same?? that checks to see if an expression is a same? expression. 

 (define (same?? exp) (tagged-list? exp 'same?))  

Define the functions same?-first and same?-second that select out the first and second sub-expressions (assume someone else defined same?-third). 

 (define (same?-first exp) (cadr exp))  (define (same?-second exp) (caddr exp)) 

 

Next, write the appropriate clause to add to the cond clause of eval, assuming that we have the function eval-same? that will evaluate a same? expression. 

 ((same?? exp) (eval-same? exp env))  

Finally, write the eval-same? function that takes a same? expression and an environment and implements the special form as described above. 

 (define (eval-same? exp env) (let ((val1 (eval (same?-first exp) env)) (val2 (eval (same?-second exp) env))) (if (eq? val1 val2) (eq? val1 (eval (same?-third exp) env)) #f))) 

We need to make same? a special form in our language because our language has evaluation. If, instead, our language had lazy-evaluation, then we could simply define same? as a function. Assuming our Scheme has the alternative method of evaluation (stated in the previous paragraph), define same? as a function. 

 (define (same? a b c) (if (eq? a b)  (eq? b c) 

   #f))

6. Register Machines

Draw the Data Paths AND Controller for a machine to compute whether the input x is odd by successively subtracting 1 from the input. You can assume that the input will be a positive integer. Assume the only primitive operations you have are subtraction, logical not, and testing equality. After your machine finishes running, the result in the answer register should be either #t or #f. 

 

Ans:

 



 

(controller

 (assign answer (const #f))

loop

 (test (op = ) x (const 0))

 (branch (label done))

 (assign x (op -) (reg x) (const 1))

 (assign answer (op not ) (reg answer))

 (goto (label loop))

done)

7. Decompiling

Consider the following code output by the compiler:

 


 (assign val (op make-compiled-procedure) (label entry24) (reg env))
 (goto (reg continue))
 entry24
 (assign env (op compiled-procedure-env) (reg proc))
 (assign env (op extend-environment) (const (f)) (reg argl) (reg env))
 (assign val (op make-compiled-procedure) (label entry25) (reg env))
 (goto (reg continue))
 entry25
 (assign env (op compiled-procedure-env) (reg proc))
 (assign env (op extend-environment) (const (x)) (reg argl) (reg env))
 (assign proc (op lookup-variable-value) (const f) (reg env))
 (save continue)
 (save proc)
 (assign proc (op lookup-variable-value) (const f) (reg env))
 (assign val (op lookup-variable-value) (const x) (reg env))
 (assign argl (op list) (reg val))
 (test (op primitive-procedure?) (reg proc))
 (branch (label primitive-branch28))
 compiled-branch27
 (assign continue (label after-call26))
 (assign val (op compiled-procedure-entry) (reg proc))
 (goto (reg val))
 primitive-branch28
 (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
 after-call26
 (assign argl (op list) (reg val))
 (restore proc)
 (restore continue)
 (test (op primitive-procedure?) (reg proc))
 (branch (label primitive-branch31))
 compiled-branch30
 (assign val (op compiled-procedure-entry) (reg proc))
 (goto (reg val))
 primitive-branch31
 (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
 (goto (reg continue))
 after-call29


 

A. What source code expression was compiled to produce lines 14-25 of the object code?

(f x)

B. What source code expression was compiled to produce lines 11-35 of the object code?

 (f (f x)) 

C. What source code expression was compiled to produce lines 6-35 of the object code?

(lambda (x) (f (f x)))

D. What is the overall expression that compiled into the object code shown?

(lambda (f) (lambda (x) (f (f x))))

E. This code was compiled in such a way that a tail recursive call was produced. How would it differ if a simpler compiler had ignored that optimization?

The key difference would have been apparent before line 32. Comparing this to line 20, we see that NO new continue register is specified for the overall body expression, while it was specified for the intermediate expression (f x). Thus, once we've done (f (f x)), we return to the surrouding continue, and not BACK into the procedure to see if there are any more deferred operations. If this code had been completely recursive, we would have also had to save the continue register before the new assign, and thus would have consumed more space on the stack. 

F. How can you hand optimize out the need for binding x in the environment?

Note that line 10 pulls x out of the argument list and sticks it into the (extended) environment. Then the only place where that environment is used is in line 15, where the variable x is looked up in the environment, and stuffed into register val. Then in line 16, we take val and recreate argl to hold it! Since there were no intervening uses of the environment, and particularly no change to argl, this extra work is useless! We can safely optimize out lines 10, 15, and 16. 

G. Can you do the same for f?

We can't do quite the same optimization -- that is, eliminate the binding for f. The problem is that we really do need to get f into the environment, because we may be doing quite a lot with it. In particular, we will build a new procedure, the (lambda (x) ...), that depends on the surrounding environment defining the variable f. There is, however, a different optimization we can do. In line 11 we lookup f and put this in the proc register. Well, it is still there at line 14, where we do the same lookup again! We can safely delete line 14.