University of California, Berkeley - College of Engineering

Department of Electrical Engineering and Computer Sciences

Instructor: Kurt Meinz

Summer 2003

2003-08-08

CS 61A Midterm #3

Personal Information

Instructions

-Partial credit may be given for incomplete / wrong answers, so please write down as much of the solution as you can.

-Feel free to use any Scheme function that was described in lecture or sections of the textbook we have read without defining it yourself. Do not use functions or constructs that we have not yet covered. Unless specifically prohibited, you are allowed to use helper functions on any problem.

-Please use "true" instead of #t, and "false" instead of #f. We have found that handwritten #t and #f unfortunately look too much alike.

-Please write legibly! If we can't read it, we won't grade it!

- Feel free to draw funny pictures/messages on the exam.

Grading Results

Question 1: Mutation (8 points)

Write a function insert-after! which takes three arguments:

- An atomic element e after which to insert something.

- An element x  to insert.

- A flat list.

The job of insert-after! is to insert x after each occurrence of e in the list using mutation. Although you may call cons to perform an insertion, you should not construct a whole new list! The return value of insert-after! should be the number of insertions made. Here are some sample calls:

STK> (define nums (list 1 2 1 3 1 2 1 4))

STK> (insert-after! 1 'one nums)

4

STK> nums

(1 one 2 1 one 3 1 one 2 1 one 4)

STK> (insert-after! 4 'foo nums)

1

STK> nums

(1 one 2 1 one 3 1 one 2 1 one 4 foo)

STK> (insert-after! 15 'viagra nums)

0

STK> nums

(1 one 2 1 one 3 1 one 2 1 one 4 foo)

(define (insert-after! e x lst)

Question 2: Metacircular Evaluator (8 points)

Consider the following modification of the metacircular evaluator. We change the procedure eval-assignment  from how it was before:

(define (eval-assignment exp env)

    (set-variable-value! (assignment-variable exp)

                         (mc-eval (assignment-value exp) env)

                         env)

    'ok)

To this new version:

(define (eval-assignment exp env)

    (set-variable-value! (mc-eval (assignment-variable exp) env)

                         (mc-eval (assignment-value exp) env)

                         env)

    'ok)

Try to understand the implications of this change, then fill in what this new version of the evaluator will return in response to the following commands. Note that we haven't made a similar change to the eval-definition function. (Assume each of the following five sets of expressions constitutes a separate session with the metacircular evaluator. If you think an error occurs as a result of an evaluation, briefly describe the error and skip any remaining blanks in that set.)

;;; M-Eval input:

(define sloth 'stupid)

;;; M-Eval input:

(define stupid 0)

;;; M-Eval input:

(set! sloth 2)

;;; M-Eval input:

sloth

;;; M-Eval value:

______________________________________________

;;; M-Eval input:

stupid

;;; M-Eval value:

______________________________________________

;;; M-Eval input:

((lambda (elt) (set! (car '(elt)) (* elt elt)) elt) 5)

;; M-Eval value:

_______________________________________________

;;; M-Eval input:

(define carlos 'david)

;;; M-Eval input:

(define david 17)

;;; M-Eval input:

(set! carlos (+ carlos 1))

;;; M-Eval value:

_________________________________________________

;;; M-Eval input:

carlos

;;; M-Eval value

__________________________________________________

;;; M-Eval input:

(set! (+ 3 15) 'eighteen)

;;; M-Eval value:

___________________________________________________

;;; M-Eval input:

18

;;; M-Eval value:

___________________________________________________

;;; M-Eval input:

(let ((sent '(in the usa)))           ;; assume let is transformed into lambda

    (let ((temp (car sent)))

        (set! temp (cadr sent))

        sent))

;;; M-Eval value:

_____________________________________________________

Question 3: Streams (8 points)

Write the function call-on-prev which takes a function f  and some Scheme value x. The function must be able to take any number of arguments. It should generate the infinite stream whose first element is x, and subsequent elements are created by applying f  to all the previous elements of the stream (in the order they appear in the stream.) More abstractly, the stream should look like this:

                        x, f(x), f(x, f(x)), f(x, f(x), f(x, f(x)))...

Here are some examples:

STK> (ss (call-on-prev + 1))

(1 1 2 4 8 16 32 64 128 256 ...)

STK> (define funny-str (call-on-prev list 'foo))

STK> (ss funny-str 4)

(foo (foo) (foo (foo)) (foo (foo) (foo (foo))) ...)

STK> (define (first-arg x . rest) x)

STK> (ss (call-on-prev first arg 'kurt))

(kurt kurt kurt kurt kurt kurt kurt kurt kurt kurt ...)

(define (call-on-prev func x)

Question 4: Metacircular Evaluator (8 Points)

We'd like you to add a special form to the metacircular evaluator that will implement a looping construct currently not present in Scheme called a "for loop." Informally, the job of for is to keep track of a single changing value as a body is evaluated over and over again while a condition holds. A for expression has the following form:

            (for (<variable> <initial> <condition> <increment>)

        <body>)

The fist thing for does is perform some setup. It creates a local variable called <variable> and sets it to the value of <initial>. Next, <condition> is evaluated, and if it is found to be true <body> is evaluated also. After evaluating the body, evaluate <increment>, an arbitrary Scheme expression which should generally set <variable> to a value that will bring the loop closer to termination. Then do it all over again: re-evaluate <condition>, and if it is true run <body> and run <increment>. Do this until <condition> is no longer true. The return value of for is the word ok.

Here are some examples:

;;; M-Eval input:

(for (x 0 (< x 10) (set! x (+ x 3)))

    (display x)

    (newline))

0

3

6

9

;;; M-Eval value:

ok

The iteration variable in a for loop need not hold a numeric value. Watch:

;;; M-Eval input:

(define (length lst)

    (let ((result 0))

        (for (temp lst (not (null? temp)) (set! temp (cdr temp)))

            (set! result (+ 1 result)))

        result))

;;; M-eval value

ok

;;; M-eval input:

(length (list 'i 'can 'only 'show 'you 'the 'door))

;;; M-Eval value:

7

Make sure that <variable> is available t be looked up and changed within <body>, <increment> and <condition>. Also, remember to evaluate <condition> before <body>. In the following loop, <body> and <increment> are never evaluated:

;;; M-Eval input:

(for (x 'hello #f (first '()))

    (display "This should not be displayed!"))

;;; M-Eval value:

ok

We have added the following clause to mc-eval:

((for? exp) (eval-for exp env))

Please define the following functions, which operate on the for expression. They should not call mc-eval  or manipulate the environment:

(define (for? exp)

;; use this to extract (<variable <initial> <condition> <increment>)

(define (for-nonbody exp) (cadr exp))

(define (for-variable exp)

(define (for-initial exp)

(define (for-condition exp)

(define (for-increment exp)

(define (for-body exp)

Use the rest of the space on this page to write eval-for, which will implement this special form. You will get zero points for making for a derived expression.

(define (eval-for exp env)

Question 5: Lazy Evaluator (8 points)

We would like to merge the lazy and metacircular evaluators by changing the lazy evaluator to "thunkify" only some of the arguments to a given compound procedure. It will be up to the programmer to explicitly say which arguments should be strict (should be evaluated) and which should be non-strict (should be delayed). The programmer shall make this decision when defining procedures by labeling each formal parameter. Consider the following definition:

    (define (foo (strict a) (non-strict b) (non-strict c))

        (bar a b)

        c)

It states that the first argument to foo should be evaluated and the last two arguments should be delayed. In this hybrid evaluator, all formal parameters must be labeled as either "strict" or "non-strict." Evaluation of the body of foo should proceed as it usually does (it is the same for both evaluators). Here is a sample session with the new lazy evaluator. Please study it carefully. Assume the following procedures have been typed at the prompt:

        (define (id (non-strict x)) (display x) (newline) x)

        (define (foo (strict a) (non-strict b) (non-strict c)) (bar a b) c)

        (define (bar (strict x) (strict y)) 43)

;;; L-Eval input:

(bar (id 'ex) (id 'why))

ex

why

;;; L-Eval value:

43

(define greg (foo (id 'aye) (id 'bee) (id 'sea)))

aye

bee

;;; L-Eval value:

ok

;;; L-Eval input:

(list 'blue greg)

sea

;;; L-Eval value:

(blue sea)

We would like you to make the necessary changes to the lazy evaluator. The only function that should be modified is mc-apply, reproduced on the following page. No changes to eval-definition or make-procedure are needed--the parameters of a procedure will simply be a list of lists now. For example, here is how foo looks like:           

;;; L-Eval input:

foo

;;; L-Eval value

(compound-procedure ((strict a) (non-strict b) (non-strict c)) ((bar a b) c) <procedure-env>)

You may assume that all parameters will be labeled "strict" or non-strict," so no error-checking is required.

Please show you changes to mc-apply on this page. Tell us which lines should be changed and what they should be changed to. Use the remaining space for any additional code you need to write. While you may modify other parts of the interpreter, you are probably on the wrong track if you do.

1. (define (mc-apply procedure arguments env)

2.    (cond ((primitive-procedure? procedure)

3.            (apply-primitive-procedure

4.              procedure

5.              (list-of-arg-values arguments env)))

6.         ((compound-procedure? procedure)

7.            (eval-sequence

8.                (procedure-body procedure)

9.                (extend-environment  

10.                    (procedure-parameters procedure(

11.                    (list-of-delayed-args arguments env)

12.                    (procedure-environment procedure)))

13.        (else

14.            (error "Unknown procedure type -- APPLY" procedure))))