RI: Konrad Tollmar

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

The final quiz will cover all the material through this course.

You may bring 3 sheets of notes to the exam. 

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?

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

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

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).

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?

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

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

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 '(6001 is now) '(almost over))
(get '(6001 is now)) ==> (almost over)

Complete the following three definitions for put and get.

(define *global-put-table* )
(define (put keys value) )
(define (get keys))

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)))))

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))))

Set 3:

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

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.

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

5. Introduce a new special form

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

A. 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.

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

C. 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.

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

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.

7. Decompiling

Consider the following code output by the compiler:

1.    (assign val (op make-compiled-procedure) (label entry24) (reg env))

2.    (goto (reg continue))

3.    entry24

4.    (assign env (op compiled-procedure-env) (reg proc))

5.    (assign env (op extend-environment) (const (f)) (reg argl) (reg env))

6.    (assign val (op make-compiled-procedure) (label entry25) (reg env))

7.    (goto (reg continue))

8.    entry25

9.    (assign env (op compiled-procedure-env) (reg proc))

10.(assign env (op extend-environment) (const (x)) (reg argl) (reg env))

11.(assign proc (op lookup-variable-value) (const f) (reg env))

12.(save continue)

13.(save proc)

14.(assign proc (op lookup-variable-value) (const f) (reg env))

15.(assign val (op lookup-variable-value) (const x) (reg env))

16.(assign argl (op list) (reg val))

17.(test (op primitive-procedure?) (reg proc))

18.(branch (label primitive-branch28))

19.compiled-branch27

20.(assign continue (label after-call26))

21.(assign val (op compiled-procedure-entry) (reg proc))

22.(goto (reg val))

23.primitive-branch28

24.(assign val (op apply-primitive-procedure) (reg proc) (reg argl))

25.after-call26

26.(assign argl (op list) (reg val))

27.(restore proc)

28.(restore continue)

29.(test (op primitive-procedure?) (reg proc))

30.(branch (label primitive-branch31))

31.compiled-branch30

32.(assign val (op compiled-procedure-entry) (reg proc))

33.(goto (reg val))

34.primitive-branch31

35.(assign val (op apply-primitive-procedure) (reg proc) (reg argl))

36.(goto (reg continue))

37.after-call29

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

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

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

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

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?

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

G. Can you do the same for f?