Data Loading...
University of Massachusetts Lowell - Computer Science Flipbook PDF
University of Massachusetts Lowell 91.301: Organization of Programming Languages Fall 2002 Sample Final Exam Before star
114 Views
86 Downloads
FLIP PDF 51.14KB
University of Massachusetts Lowell 91.301: Organization of Programming Languages Fall 2002
Sample Final Exam
Before starting, please write your name in the blank below. Start the quiz only when instructed to do so. You may use any written resources you wish, but you may not consult another student, nor use a computer, nor a calculator. You will have three hours to finish this quiz.
Name:
Fall 2002
Sample Final Exam
2
91.301
Problem 1: 10 points Examine the functions enigma, mystery, and conundrum given below. (define (enigma m) (m 2)) (define (mystery p q) (lambda (z) (p (enigma q) z))) (define (conundrum a) (lambda (x) (mystery x a))) What will be the result of evaluating the following Scheme expressions? Write “procedure” if a procedure object would be returned, and write “error” if an error would be generated. Otherwise, write the value resulting from evaluating the expression. Assume that our familiar definition (define (square x) (* x x)) has been already evaluated.
(enigma inc)
(enigma ’square)
(mystery list square)
((mystery list square) 3)
(((conundrum square) list) 2)
Sample Final Exam
Fall 2002
91.301
3
Problem 2: 10 points (A) Assume that we have defined a variable x which contains a list structure. Later we use set! to assign a completely new value to x. Under what circumstances is it safe to garbage collect the list stucture from old value of x.
(B) Given the following diagram of memory locations where root is P2, 0 N5 E0
1 P4 N2
2 P3 P7
3 N4 P0
4 P7 E0
5 N3 E0
6 P2 P4
7 P0 P4
how many free cells will there be after garbage collection?
(C) What is one advantage of the stop-and-copy garbage collection method over mark-and-sweep?
(D) What is one advantage of the mark-and-sweep garbage collection method over stop-and-copy?
Fall 2002
Sample Final Exam
4
91.301
Problem 3: 10 points
(A) Assume that we have evaluated the following four expressions.
(define a ’(1 2 3)) (set! a ’(3 4 5)) (set-car! a ’b) (set-cdr! a ’(c d)) What will be the result of evaluating a ?
(B) Assume a structure corresponding to the box and pointer diagram below has been bound to the variable s. Write a 1-line expression which when evaluated will replace the symbol b3 with the symbol x.
a
3 b
4
5
c
d
1-line expression:
Sample Final Exam
Fall 2002
91.301
5
Problem 4: 10 points Ben Bitdiddle, ever curious, finds an obscure implementation of Scheme where delay is not memoized (sometimes called “Really Repulsively Reluctant and Slow Scheme” or R3 S Scheme). He executes the following snippets of code as a series of experiments. His function (display-stream s n) prints out the first n elements of the stream s. (define *ones-count* 0) (define ones (cons-stream 1 (begin (set! *ones-count* (inc *ones-count*)) ones))) (display-stream ones 10) (A) What will the value of *ones-count* be in R3 S Scheme?
(B) Then, he evaluates the same code in MIT Scheme. What value does he get for *ones-count*?
Fall 2002
Sample Final Exam
6
91.301
Problem 5: 15 points (A) Write a procedure called map-two-streams which takes a procedure of two arguments and two streams. It will return the stream that results from applying the procedure to corresponding elements in the two streams. For example, (map-two-streams + ones integers) would return the stream 2 3 4 5 6 7 8 . . . .
(B) Use map-two-streams to write a procedure called min-two-streams, which takes two streams and returns a stream consisting of the smaller of the two elements at each stream position. You may use the min primitive from MIT Scheme.
Sample Final Exam
Fall 2002
91.301
7
Problem 6: 20 points (A) We want to add a new uml:when special form to our metacircular evaluator. The new special form has the following behavior: (uml:when pred e1 e2 ... en ) tests the predicate pred and executes the expressions e1 through en if and only if the predicate returned a true value. The value returned by the entire expression is the value returned by en if it was evaluated, and #f otherwise. Add uml:when to mc-eval, which is given on the last page of this exam as a convenient tear-off sheet. Tell us where you would insert your code using the line numbers on the tear-off sheet, e.g. by writing “after line X.” Assume that the appropriate predicate and selectors for when expressions exist: when, when-predicate, and when-exps.
(B) Now we want to add uml:not as a primitive to our system. Briefly discuss where in the code you would do this, and what approach you would take.
Fall 2002
Sample Final Exam
8
91.301
Problem 7: 15 points Let us add a videotape to our game system from Problem Set 8 (you may ask a staff member for a copy of the code if you do not have one). A videotape will be a type of thing. Its only method will be self-destruct, where it will move to the location nowhere and have the owner nobody. We could write the following code: (define (make-videotape name location) (let ((e1 e2 )) (lambda (message) (cond ((eq? message ’self-destruct) e3 ) (else e4 ))))) Write the missing sections of code.
e1 :
e2 :
e3 :
e4 :
Sample Final Exam
Fall 2002
91.301
9
Convenient Tear-Off Sheet This page contains a copy of the definition of mc-eval for use with Problem 6. This is the same definition as appeared in Problem Set 9 (you may ask a staff member for a copy of the remainder of the code from the problem set if you would like).
(define (mc-eval exp env) ; (1) (cond ((self-evaluating? exp) ; (2) exp) ; (3) ((variable? exp) ; (4) (lookup-variable-value exp env)) ; (5) ((quoted? exp) ; (6) (text-of-quotation exp)) ; (7) ((assignment? exp) ; (8) (eval-assignment exp env)) ; (9) ((definition? exp) ; (10) (eval-definition exp env)) ; (11) ((if? exp) ; (12) (eval-if exp env)) ; (13) ((and? exp) ; (14) (eval-and exp env)) ; (15) ((lambda? exp) ; (16) (make-procedure (lambda-parameters exp) (lambda-body exp) env)) ; (17) ((begin? exp) ; (18) (eval-sequence (begin-actions exp) env)) ; (19) ((cond? exp) ; (20) (mc-eval (cond->if exp) env)) ; (21) ((application? exp) ; (22) (mc-apply (mc-eval (operator exp) env) ; (23) (list-of-values (operands exp) env))) ; (24) (else (error "Unknown expression type -- MC-EVAL")))) ; (25)
Fall 2002
Sample Final Exam