;; Solutions for Midterm 3
;; CS 61A: Spring 1998
;; -----------------------------------
;; QUESTION 1 (6 points): all versions
;; Part 1
(define str
(define (enumerate-list x y)
(if (> x y)
'()
(cons x (enumerate-list (1+ x) y))))
(define (str-helper n)
(cons-stream (enumerate-list 1 n) (str-helper (1+ n))))
(str-helper 1))
; Explanation:
; (enumerate-list x y) returns the list of integers from x to y, both
; inclusive. (str-helper n) returns the stream:
; { (1 2 ... n) (1 2 ... n+1) (1 2 ... n+2) ... }
; We want the stream (str-helper 1)
; Grading:
; 2 if correct, 0 if wrong
; 1 for mistakes like treating the inner list as a stream
;; Part 2a
(stream-maker 0 (lambda (x) (if (= x 0) 1 0)))
;; Part 2b
(stream-maker b (lambda (x) (word x 'an)))
; Explanation:
; The function that you pass must be something that can generate the
; (n+1)'th element of the stream given the n'th element of the stream
; as argument.
; Grading:
; 1 point for each part
;; Part 3
(define binary
(cons-str 0
(cons-str 1
(interleave
(stream-map (lambda (x) (word x 0)) binary)
(stream-map (lambda (x) (word x 1)) binary)))))
; The above solution generates 0, 00, 000 ... in the stream - although
; we should have only one zero in the stream to represent the binary
; number 0. The following solution fixes this problem.
(define binary
(cons-str 0 binary-from-1))
(define binary-from-1
(cons-str 1
(interleave
(stream-map (lambda (x) (word x 0)) binary-from-1)
(stream-map (lambda (x) (word x 1)) binary-from-1))))
; Explanation:
; Given a binary number of length n, there are two ways to construct a
; binary number of length (n+1) - add 0 at the end and add 1 at the
; end. When this is done recursively, using the interleave & the
; stream-map, we get all the binary numbers.
; An alternate solution is to generate the stream of integers in
; decimal & convert each of them (using stream-map) to binary.
; Grading:
; 2 if correct, 0 if wrong
; 1 if partially correct e.g. when some base case is not taken care of
;; -----------------------------------
;; QUESTION 2 (4 points): version A
;; 1. Which of the following three sets require a stream representation?
;; (underline the ones that do; 1 mark)
;; * the non-negative even numbers
;; -----------------------------
;; --> The reason for this is because there are an infinite number of
;; non-negative even numbers, so we can't make them all at once, but we
;; can make them as necessary.
;; * the prime numbers
;; -----------------
;; --> The same reasoning applies for this as for the non-negative even
;; numbers.
;; * the even prime numbers
;; --> The only even prime number is 2. So we don't need to delay
;; anything here.
;; 2. Eva writes a program that produces an infinite stream whose elements
;; are randomly chosen integers in the range 0 to n inclusive; all of the
;; numbers in this range appear in the stream. Louis claims to write a
;; program that sorts this tream In one English sentence, explain why Louis
;; is lying. (1 mark)
;; The problem is vague in that it doesn't say what type of sort algorithm
;; Louis claims to use. For the question it doesn't really matter how it's
;; sorted, just that there are an infinite number of numbers to be sorted
;; and that would take an infinite amout of time to sort.
;; You cannot sort an infinite stream of integers from 0 to n because
;; there will be an infinite number of 0's and an infinite number of
;; every other integer as well.
;; 3. Explain why Louis can write a program that looks as though it does
;; this; Eva cannot tell whether it has sorted her stream or not. (1 marks)
;; Louis can write a program that looks like it sorts Eva's list only if
;; that sort is from the lowest value to highest value. If the sort was
;; anything other than that, it wouldn't know for certain what the highest
;; or middle values were since it would have to take an infinite number of
;; samples to be sure the number didn't randomly pop up thousands of cdrs
;; within the stream. Since Louis knows before hand that the stream definitely
;; has a zero in it, if he made a stream of only zeros, then Eva wouldn't
;; know the difference since there would be an infinite number of zeros
;; in a stream of random values between 0 to n.
;; (The answer doesn't have to be this in depth, just as long as you say
;; that an stream of an infinite number of zeros is what does the job, and
;; why.)
;; 4. Write a program that returns a stream that is indistinguishable from
;; a sorted version of Eva's stream. (1 mark)
(define (sort-eva-stream stream)
(cons-stream 0 (sort-eva-stream stream)))
;; or maybe
(define (sort-eva-stream stream)
(define stream-of-0
(cons-stream 0 stream-of-0))
stream-of-0)
;; or anything that returns an infinite stream of zeros.
;; This looks like you are considering Eva's stream but you aren't.
;; -----------------------------------
;; QUESTION 2 (4 points): version B
;; 1. Which of the following three sets require a stream representation?
;; (underline the ones that do; 1 mark)
;; * the powers of two
;; -----------------------------
;; --> The reason for this is because there are an infinite number of
;; powers of two numbers, so we can't make them all at once, but we can
;; make them as necessary.
;; * the prime numbers
;; -----------------
;; --> The same reasoning applies for this as for the power of two numbers.
;; * the even prime numbers
;; --> The only even prime number is 2. So we don't need to delay anything
;; here.
;; 2. Eva writes a program that produces an infinite stream whose elements
;; are randomly chosen integers in the range 0 to n inclusive; all of the
;; numbers in this range appear in the stream. Louis claims to write a
;; program that sorts this tream In one English sentence, explain why Louis
;; is lying. (1 mark)
;; The problem is vague in that it doesn't say what type of sort algorithm
;; Louis claims to use. For the question it doesn't really matter how it's
;; sorted, just that there are an infinite number of numbers to be sorted
;; and that would take an infinite amout of time to sort.
;; You cannot sort an infinite stream of integers from 0 to n because
;; there will be an infinite number of 0's and an infinite number of
;; every other integer as well.
;; 3. Explain why Louis can write a program that looks as though it does
;; this; Eva cannot tell whether it has sorted her stream or not. (1 marks)
;; Louis can write a program that looks like it sorts Eva's list only if
;; that sort is from the lowest value to highest value. If the sort was
;; anything other than that, it wouldn't know for certain what the highest
;; or middle values were since it would have to take an infinite number of
;; samples to be sure the number didn't randomly pop up thousands of cdrs
;; within the stream. Since Louis knows before hand that the stream definitely
;; has a zero in it, if he made a stream of only zeros, then Eva wouldn't
;; know the difference since there would be an infinite number of zeros
;; in a stream of random values between 0 to n.
;; (The answer doesn't have to be this in depth, just as long as you say
;; that an stream of an infinite number of zeros is what does the job, and
;; why.)
;; 4. Write a program that returns a stream that is indistinguishable from
;; a sorted version of Eva's stream. (1 mark)
(define (sort-eva-stream stream)
(cons-stream 0 (sort-eva-stream stream)))
;; or maybe
(define (sort-eva-stream stream)
(define stream-of-0
(cons-stream 0 stream-of-0))
stream-of-0)
;; or anything that returns an infinite stream of zeros.
;; This looks like you are considering Eva's stream but you aren't.
;; -----------------------------------
;; QUESTION 3 (9 points): version A
;; (The left bubble is not filled in because of space.)
;; GLOBAL ENV:
;; +------------+
;; | |
;; | x ---> 100 |
;; | |<------+
;; | | |
;; | foo ---------->(*)(*)
;; | |
;; | |<------+
;; | | |
;; | | E1: |
;; | | +---------+
;; | | | x --> 3 |
;; | | | |<--------+
;; | | | | |
;; | | +---------+ E2: |
;; | | +---------+
;; | | | x --> 5 |
;; | | | y --> 3 |
;; | | | |<------+
;; | | | | ||
;; | | | bar ------->(*)(*)
;; | | | |<--------------------+
;; | | | | |
;; | | | |<------+ |
;; | | | | | |
;; | | | | (*)(*) |
;; | | | |<------+ |
;; | | | | E3: | E4: |
;; | | | | +---------+ +---------+
;; | | | | | x --> 4 | | y --> 4 |
;; | | | | | | | |
;; | | | | | | | |
;; | | +---------+ +---------+ +---------+
(define x 100)
(define (foo x)
(let ((x 5) (y x))
(define (bar y)
(* x y))
(lambda (x)
(if (= x y)
(+ x (bar y))
(+ y (bar x))))))
;; Version A (1 point each)
((foo 3) 4)
;; 1. 23
;; 2. 4
;; 3. 4
;; 4. 1
;; 5. x, foo
;; 6. no
;; 7. n/a
;; 8. yes
;; 9. no
;; -----------------------------------
;; QUESTION 3 (9 points): version B
;; (The left bubble is not filled in because of space.)
;; GLOBAL ENV:
;; +------------+
;; | |
;; | x ---> 100 |
;; | |<------+
;; | | |
;; | foo ---------->(*)(*)
;; | |
;; | |<------+
;; | | |
;; | | E1: |
;; | | +---------+
;; | | | x --> 6 |
;; | | | |<--------+
;; | | | | |
;; | | +---------+ E2: |
;; | | +---------+
;; | | | x --> 5 |
;; | | | y --> 6 |
;; | | | |<------+
;; | | | | ||
;; | | | bar ------->(*)(*)
;; | | | |<--------------------+
;; | | | | |
;; | | | |<------+ |
;; | | | | | |
;; | | | | (*)(*) |
;; | | | |<------+ |
;; | | | | E3: | E4: |
;; | | | | +---------+ +---------+
;; | | | | | x --> 4 | | y --> 4 |
;; | | | | | | | |
;; | | | | | | | |
;; | | +---------+ +---------+ +---------+
(define x 100)
(define (foo x)
(let ((x 5) (y x))
(define (bar y)
(* x y))
(lambda (x)
(if (= x y)
(+ x (bar y))
(+ y (bar x))))))
;; Version B (1 point each)
((foo 6) 4)
;; 1. 26
;; 2. 4
;; 3. 4
;; 4. 1
;; 5. x, foo
;; 6. no
;; 7. n/a
;; 8. yes
;; 9. no
;; -----------------------------------
;; QUESTION 4 (4 points): version A
;; Please see .ps files for environment diagrams.
(define (f)
(let ((a 3))
(lambda (x) (set! a (+ x a)) a)))
(define my-f (f))
(define my-f2 (f))
(define g
(let ((a 3))
(lambda (x) (set! a (+ a x)) a)))
(define my-g1 g)
(define my-g2 g)
(my-f 5) ;; 8
(my-f 4) ;; 12
(my-f2 5) ;; 8
(my-f2 4) ;; 12
(my-g1 5) ;; 8
(my-g1 4) ;; 12
(my-g2 5) ;; 17
(my-g2 4) ;; 21
;; -----------------------------------
;; QUESTION 4 (4 points): version B
;; 8
;; 12
;; 7
;; 12
;; 8
;; 12
;; 16
;; 21
;; -----------------------------------
;; QUESTION 5 (7 points): all versions
;; Please see .ps files of environment diagrams.
(define a (list 'a 'b 'c))
(define b (list 1 2 3))
(define (f x)
(set! b (cdr b))
(set-cdr! (cdr a) x))
(define g
(let ((a (cddr a)))
(lambda (b) (set-car! b a))))
(define (h x)
(f x)
(g x)
(set-cdr! x b)
(set-cdr! (car x) b))
(h a)
;; Evaluate:
a ;; ((c 2 3) 2 3)
b ;; (2 3)
;; a -->+---+---+
;; | + | + |
;; +-|-+-|-+
;; | |
;; V |
;; +-+-+ |
;; |+|+| |
;; +|+|+ |
;; | | |
;; V | |
;; c | |
;; V V
;; b ----->+-+-+ +-+-+
;; |+|+-->|+|/|
;; +|+-+ +|+-+
;; | |
;; V V
;; 2 3
;; 4 frames
;; 4 bubbles
;; 1 set of bubbles does not point to the global environment
;; -----------------------------------
;; QUESTION 6 (4 points): version A
;; 1.
;; (ask staff 'help) ==> error because staff is a class, not an object
;; (ask paul 'help) ==> "Did you try this yourself?" (version A)
;; (ask rjf 're-grade) ==> "See me later"
;; (ask rjf 'help) ==> "let me check"
;; 2. Respect the data abstraction.
;; -----------------------------------
;; QUESTION 6 (4 points): version B
;; 1.
;; (ask staff 'help) ==> error because staff is a class, not an object
;; (ask paul 're-grade) ==> "I'll give you 1 more point" (version B)
;; (ask rjf 're-grade) ==> "See me later"
;; (ask rjf 'help) ==> "let me check"
;; 2. Respect the data abstraction.
;; -----------------------------------
;; QUESTION 7 (5 points): version A
;; 1. 4, 8, 16
;; 2. 16
;; 3. underline 2
;; Deadlock occurs if one process tries to grab serializer s1 then s2
;; and the other tries to grab s2 then s1, and if each of the processes
;; succeeds on that first grab only.
;; -----------------------------------
;; QUESTION 7 (5 points): version B
;; 1. 81
;; 2. 9,27,81
;; 3. underline 1
;; Deadlock occurs if one process tries to grab serializer s1 then s2
;; and the other tries to grab s2 then s1, and if each of the processes
;; succeeds on that first grab only.