This preview shows page 1-2-3-27-28-29 out of 29 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

6.001, Fall Semester, 2006—Final Exam 1MASSACHVSETTS INSTITVTE OF TECHNOLOGYDepartment of Electrical Engineering and Computer Science6.001—Structure and Interpretation of Computer ProgramsFall Semester, 2006Final ExamClosed Book – three sheets of notesThroughout this exam, we have set aside space in which you should write your answers. Pleasetry to put all of your answers in the designated spaces, as we will look only in this spaces whengrading.Note that any procedures or code fragments that you write will be judged not only on correctfunction, but also on clarity and good programming practice. Also note that while there may be alot of reading to do on a problem, there is relatively little code to write, so please take the time toread each problem carefully.NAME:Section Time: Tutor’s Name:PART Value Grade PART Value Grade1 18 6 162 27 7 183 16 8 184 25 9 225 15 10 25Total 200No grades for 6.001 will be available until December 22nd. After that time, you may (1) wait untilgrades are mailed by the Registrar; (2) access your grades via WEBSIS (http://student.mit.edu/),or (3) contact the course secretary, Donna Kaufman, in 38-401. No grades will be given out byphone; you must appear in person with ID if selecting the third option.Completed final exams will not be handed back to students, but will be available starting onDecember 22nd for students to look at (but not remove from) Donna Kaufman’s office, Room38-401.6.001, Fall Semester, 2006—Final Exam 2Part 1 (18 points): EvaluatorsSuppose that we want to add a new special form let* to our meta-circular evaluator. Recall thatwe have two approaches: direct addition or syntactic transformation. In this part, we’ll add thespecial form let* directly by extending our toplevel m-eval procedure.The semantics of our new form let* has some similarity to let. The primary difference is thatlet* binds each of its parameters in order, rather than in parallel. For example:(let* ((x 3)(y (* 2 x)))(set! x (+ y 1))(list x y))would first bind x to 3, and then bind y to the value of (* 2 x) or 6, before evaluating the body.As with a let, a let* could have a body that consists of more than one expression, and the valueof the let* expression is the value of the last expression in its body.Question 1:We will need some procedures for handling the syntax of a let*. Complete the following procedures,where it is expected that exp is a let* expression:(define (let*-clauses exp) ANSWER1)(define (let*-body exp) ANSWER2)ANSWER1:ANSWER2:6.001, Fall Semester, 2006—Final Exam 3Question 2:When we add a new special form to our evaluation procedure, m-eval, we check for the specialform, then call a special evaluation procedure. The procedure for checking for an let* expressionwould be:(define (let*? exp) (tagged-list? exp ’let*))If a call to this procedure evaluates to true, then the procedure eval-let* is called:(define (m-eval exp env)(cond ((self-evaluating? exp) exp).((let*? exp) (eval-let* exp env)).((application? exp)(m-apply (m-eval (operator exp) env)(list-of-values (operands exp) env)))(else (error "Unknown expression type -- EVAL" exp))))You need to complete the procedure eval-let*(define (eval-let* exp env)(let*-aux (let*-clauses exp) (let*-body exp) env))(define (let*-aux clauses body env)ANSWER3)Write the procedure let*-aux by providing the code for ANSWER3. For your convenience, a copyof m-eval is attached at the end of the exam.6.001, Fall Semester, 2006—Final Exam 4Part 2 (27 points): Syntactic TransformsIn the Meta-Circular evaluator, we saw that one way to add new forms to our language was tocreate syntactic transformations, in which a special form was converted, using manipulation of thesyntactic representation (e.g., list structure of the expression), into a form that the evaluator couldalready handle. For example, a cond can be transformed into a nested set of if expressions.Question 3:Write the following and expression as a set of nested if expressions.(and (< x 0) (> y 14) z)6.001, Fall Semester, 2006—Final Exam 5Question 4:Write a syntactic transformation that converts an and expression into a set of if expressions.Remember that an and expression evaluates each argument in turn, return false if it reaches anargument that is false, otherwise return true when it has evaluated all of the arguments.(define (and? exp) (tagged-list? exp ’and))(define (m-eval exp env)(cond ((self-evaluating? exp) exp).((and? exp) (m-eval (and->if exp) env))((application? exp) (m-apply (m-eval (operator exp) env)(list-of-values (operands exp) env)))(else (error "Unknown expression type -- EVAL" exp))))(define (and->if exp)(and-aux (cdr exp)))Write and-aux. Assume that and has at least one clause.6.001, Fall Semester, 2006—Final Exam 6Question 5:Now, let’s add a syntactic transformation for handling let* expressions. We can do this by con-verting a let* expression into a set of nested let expressions. For example, the expression(let* ((x 3)(y (* 2 x)))(set! x (+ y 1))(list x y))could be converted into(let ((x 3))(let ((y (* 2 x)))(set! x (+ y 1))(list x y)))Thus we would have(define (m-eval exp env)(cond ((self-evaluating? exp) exp).((let*? exp) (m-eval (let*->let exp) env))((application? exp) (m-apply (m-eval (operator exp) env)(list-of-values (operands exp) env)))(else (error "Unknown expression type -- EVAL" exp))))(define (let*->let exp)(let*-help (let*-clauses exp) (let*-body exp)))(define (let*-help clauses body) ANSWER4)Provide the code for ANSWER4. Assume that let* has at least one clause.6.001, Fall Semester, 2006—Final Exam 7Part 3 (16 points): Models of EvaluationQuestion 6:Consider the following code:(define (create-list proc start end)(define (helper where end lst)(if (= where end)lst(helper (+ where 1) end (cons (proc where) lst))))(helper start end ’()));Example output:(create-list (lambda (x) (* x x)) 2 5);Value: (4 9 16 25)(define (gather-up)(let ((running-sum 0))(lambda (x)(set! running-sum (+ x running-sum))running-sum)))What is the value of the statement(create-list (gather-up) 2 6)in the ordinary (applicative order) evaluator?What about in the lazy, non-memoized evaluator?6.001, Fall Semester, 2006—Final Exam 8Consider the following procedures and definitions:(define x 3)(define (proc1) (set! x (+ x 2)))(define (proc2) (set! x (* x x)))Question 7:Suppose that proc1 and proc2 are being applied asynchronously, with no serialization. What isthe set of possible values for x at the completion of both evaluations?Question


View Full Document

MIT 6 001 - Final Exam

Documents in this Course
Quiz 1

Quiz 1

6 pages

Databases

Databases

12 pages

rec20

rec20

2 pages

Quiz II

Quiz II

15 pages

Streams

Streams

5 pages

Load more
Download Final Exam
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Final Exam and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Final Exam 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?