;; 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.