6.001, Spring 2006—Recitation 25 — 5/17/2006 1MASSACHVSETTS INSTITVTE OF TECHNOLOGYDepartment of Electrical Engineering and Computer Science6.001—Structure and Interpretation of Computer ProgramsSpring 2006Recitation 25 — 5/17/2006Final ReviewRandom StreamsAssume that ran is a primitive Scheme procedure that generates random numbers in the range -to 1, e.g.(ran)0.486726(ran)0.929204(ran)0.08849(ran)0.283186Assume that successive calls to RAN never produce the same number.Louis Reasoner wants to define a stream whose elements consist of different random numbers, asin the sequence above. He attempts to define a stream of random numbers as follows:(define random-stream(cons-stream (ran)random-stream))Lem E. Tweakit isn’t sure that Louis’ definition will work, and he suggests the following:(define (make-random-stream)(cons-stream (ran)(make-random-stream)))(define random-stream (make-random-stream))The two friends show their work to Alyssa P. Hacker who suggests that they use PRINT-STREAMto examine the first few elements of their streams. Furthermore she suggests that they run theircode on two different Scheme interpreters, one that implements lazy pairs using memoization, andone that does not.6.001, Spring 2006—Recitation 25 — 5/17/2006 2Lous and Lem take her advice, and just to be sure, they print out their streams twice. Shownbelow are pairs of printouts, of the sort that either Louis or Lem might have produced.Possible Outcomes:(print-stream random-stream) ;;; OUTCOME A0.486726 0.929204 0.008849 0.283186 ...(print-stream random-stream)0.486726 0.929204 0.008849 0.283186 ...(print-stream random-stream) ;;; OUTCOME B0.486726 0.929204 0.008849 0.283186 ...(print-stream random-stream)0.486726 0.521080 0.297045 0.991644 ...(print-stream random-stream) ;;; OUTCOME C0.486726 0.929204 0.008849 0.283186 ...(print-stream random-stream)0.365913 0.521080 0.297045 0.991644 ...(print-stream random-stream) ;;; OUTCOME D0.486726 0.486726 0.486726 0.486726 ...(print-stream random-stream)0.486726 0.486726 0.486726 0.486726 ...(print-stream random-stream) ;;; OUTCOME E0.486726 0.486726 0.486726 0.486726 ...(print-stream random-stream)0.591003 0.591003 0.591003 0.591003 ...List all of the Possible outcomes (chosen from A,B,C,D,E) that could have been produced in eachof the following cases, or indicate none if none of these outcomes is possible.1. Louis’ definition; no memoization2. Louis’ definition; with memoization3. Lem’s definition; no memoization4. Lem’s definition; with memoization6.001, Spring 2006—Recitation 25 — 5/17/2006 3EvaluatorSuppose we want to add some simple type-checking to our language, that is, to specify conditionsor constraints on the types of arguments that a procedure may take, with the idea that before weapply the procedure, we ensure that the supplied arguments meet those constraints. For example,we could extend our syntax to allow:(define (foo (number? x ) (list? y) z)some-body)The idea is that when we are about to appl foo to some arguments, we will ensure that the firstargument satisfies number? and the second argument satisfies list? before proceeding. Sincethere are no constraints specified on the last agument, anything is acceptable.We will do this by making two changes to our evaluator. First, when creating a lambda, we will getthe actual procedure object associated with each type checking clause (e.g., the procedure objectfor number?). Second, when we get to m-apply we will actually use those procedure objects toensure that the arguments meets the constraints. We change the dispatch clause in m-eval to:((lambda? exp))(make-procedure (CONVERT (lambda-parameters exp) env)(lambda-body exp)env))Here is the framework for convert, which given a list of parameters (each of which is eithera name, or a list of a procedure name and a variable name), should return a list of the sameform, in which each name is kept, but the procedure name is replaced by the actual proce-dure. Thus ((number? x) (list? y) z) would be converted to ((<actual procedure boundto number?> x) (<actual procedure bound to list?> y) z):(define (convert params env)(cond ((null? params)’())(symbol? (car params)(cons (car params) (convert (cdr params) env)))(else (cons QUESTION-1(convert (cdr params) env)))))1. What expression should be provided for QUESTION-1?Next, we change the standard version of m-apply (which in a real final exam would be attacned atthe end for reference) to handle the type checking as follows:6.001, Spring 2006—Recitation 25 — 5/17/2006 4(define (m-apply procedure arguments)(cond ((primitive-procedure? procedure)(apply-primitive-procedure procedure arguments))((compound-procedure? procedure)(let ((params (procedure-parameters procedure)))(if (type-ok? params arguments)(eval-sequence(procedure-body procedure)(extend-environment(map (lambda (x) (if (symbol? x) x (cadr x)))params)arguments(procedure-environment procedure)))(error "incorrect argument type" procedure))))(else (error "Unknown procedure type -- APPLY" procedure))))To complete this change, we need to implement type-ok? which should check that each argumentmeets the specified type constraint:(define (type-ok? params args)(cond ((null? params)QUESTION-2)((null? args) #f)((symbol? (car params))QUESTION-3)(QUESTION-4(type-ok? (cdr params) (cdr args)))(else #f)))2. What expression should be used for QUESTION-2?3. What expression should be used for QUESTION-3?4. What expression should be used for QUESTION-4?Lexical vs dynamic scope(let ((x 20))(let ((f (lambda (y) (- y x))))(let ((x 10))(f 30))))1. Value in a dynamically-scoped Scheme:2. Value in a lexically-scoped Scheme:6.001, Spring 2006—Recitation 25 — 5/17/2006 5ObjectsThis problem explores a small object-oriented world, consisting of Documents, Folders and Cabi-nets. The properties of the classes (defined by the code below) are as follows:• a Document is an object with a name, and a number of sheets.• a Folder is a collection of documents.• a Cabinet is a structure that can hold Folders. It behaves as if it were a giant folder.(define (create-document name sheets)(create-instance document name sheets))(define (document self name sheets)(let ((root-part (root-object self)))(make-handler’document(make-methods’NAME (lambda () name)’INSTALL (lambda () ’installed)’SHEETS (lambda () sheets))root-part)))(define (folder self name)(let ((root-part (root-object self))(contents ’()))(make-handler’folder(make-methods’NAME
View Full Document
Unlocking...