CS1 -- Fall 2008 -- Lab 7

CS 1 Fall 2008

Lab 7: Mutants Demand Environmental Evolution

Assigned: Monday, November 10, 2008
Due: Friday, November 21, 2008, 18:00:00

You should have read through section 3.2 of SICP before beginning this lab.

For the drawing component of these exercises, you may use any drawing program you like, as long as the final drawings are output in PostScript format (.ps file extensions) or PDF format (.pdf file extensions). We recommend the xfig or the dia programs, both of which are installed on the CS cluster computers. Submit the drawings as separate files to CS1man. Hand-written diagrams are not acceptable.

Part @: Time Synopsis

As you answer the problems below, make a note on how long you spent on each of the sections.
If any of the individual problems took you notably more time than the rating stated, please identify them and write down your actual time spent. This will help us calibrate future problem sets.

Part A: Exercises

This lab is heavily weighted towards part A. Therefore, we don't expect you to complete all of these exercises before your recitation section, but you should at least attempt some of them. Should you have any difficulties working through these exercises, bring your questions to recitation.

Complete the environment diagrams for the Scheme code given, with the following stipulations:.
- Please do not "clean up" any frames that you create along the way during the evaluation, even if they're no longer accessible.
- You don't have to create frames when evaluating built-in procedures like +, *, etc.
- However, if you use built-in procedures as arguments to other procedures, you should represent them as lambda pairs with the environment pointer pointing to the global environment. You can call the parameters whatever you like (as long as you have the right number of parameters), and for the body you should just write [built in]. The name of the built-in procedure should be put into the global environment, pointing to the appropriate lambda pair.
You should be able to load the partial environment diagrams given here into xfig and edit them. NOTE: there may be features in the partial environment diagrams which you do not need. Here are instructions for xfig for this lab. Of course, you're free to use a different drawing program (e.g. Dia or Visio or even Adobe Illustrator) as long as you save the results as a Postscript or PDF file . This should be submitted to CS1man as usual.
1. [10] Show the environment after executing this code.
  [Partial environment diagram] [xfig file]
```
(define (a x)
  (- 5 (/ x (+ x 1))))
(define (b x)
  (* x x (a (+ x 3))))
(b 11)
```
2. [20] Show the environment after executing this code.
  [Partial environment diagram] [xfig file]
```
(define (compose f g)
   (lambda (arg) (f (g arg))))
(define sqrt-plus1 (compose (lambda (x) (+ x 1)) sqrt))
```
  Hint: Be careful with the environment pointers of the lambda pairs; it's easy to point them to the wrong environment. Think about the order in which expressions get evaluated, and which environment each expression gets evaluated in.
3. [30] Show the environment after executing this code.
  [Partial environment diagram] [xfig file]
```
(define curry3op (lambda (x) (lambda (y) (lambda (z) (+ x y z)))))
(define c1op ((curry3op 3) 4))
```
4. [20] Show the environment after executing this code.
  [Partial environment diagram] [xfig file]
```
(define (make-accum)
  (let ((val 0))  (lambda (x) (set! val (+ val x)))))
(define a1 (make-accum))
(define a2 (make-accum))
(define a3 a1)
```
  Hint: (make-accum) is a function call, and a function call always creates a frame, even if no bindings need to be created in that frame.
  
  Hint 2: A let expression just creates a frame, immediately binds some values, and executes the code in its body. If you desugar it to a lambda you'll get the same effect. See the environment model cheat sheet for more on let in environment diagrams.
5. [20] Show the environment after executing this code:
  [Partial environment diagram] [xfig file]
```
(define (make-counter) 
  (let ((val 0))
    (cons (lambda () val) 
          (lambda () (set! val (+ val 1))))))
(define a (make-counter))
(define a-count (cdr a))
(define a-value (car a))
```
  Hint: Remember that lambda expressions always have their environment pointer set to the environment in which they were evaluated, so you should keep track of the current environment at all times.
For each of the following environment structures, give Scheme code which could produce it. NOTE: You are free to write code which would add other things in the environment beyond what is shown. Also, note that for each problem there may be more than one correct answer.
1. [20]
2. [30]
3. [20]
4. [30]
  
  NOTE: This one is slightly tricky. Hint: Can you make a data structure (not shown) that contains both lambda pairs?
[20] What's wrong with these expressions?
1. (set! 5 3)
2. (set! (cons 3 4) (cons 4 5))
3. ```
(define a 42)
(set! 'a 10)
```
4. ```
(define a 42)
(define (symbol) 'a)
(set! (symbol) 10)
```
5. ```
(define a (cons 1 2))
(set! (car a) 10)
```
After figuring out what's wrong with them, type them into the Scheme interpreter and see how the interpreter will respond to these "bugs".

Part B: Book Exercises

Please work the following exercises from the textbook.

[30] Exercise 3.2 (encapsulating a function to count number of uses). You can skip the contract here, because the function doesn't have a very coherent contract, but do include a comment describing how the function is to be used.
[30] Exercise 3.8 (significance of evaluation order)

HINT: Your function should have some local state variable that gets updated on every function call. You can skip the contract and comment for this problem.

This shows why having set! in the language makes the evaluation of an expression depend on the order in which operands are evaluated.

Part C: Message-Passing Data Structures with Mutable Objects

[60] The mean and variance are two useful statistical values often computed over a set of numeric data. Without going deeply into what variance is or why it's so important (ask a friend, Google it, wait for Ma2, or go to this page), here are functions to compute each over an input list of numbers:

;; mean: list-of numbers -> number
;; Compute the mean of a list of numbers.
;; N.B. length is a built-in Scheme function which computes the
;; length of a list.
(define (mean values)   
  (/ (apply + values)   ;; sum a list of numbers (note clever use of "apply")
     (length values)))  ;; and divide by the length of the list

;; variance: list-of numbers -> number
;; Compute the variance of a list of numbers.
(define (variance values)
  (define (square x) (* x x))
  (- (mean (map square values)) ;; subtract the mean of the squares
     (square (mean values))))   ;; from the square of the mean

Often, when collecting data, we receive it one element at a time instead of all at once. It might, then, be useful to be able to determine the mean and variance "on-the-fly" as we add values to the list. (Many scientific calculators let you do this.)

Your job is to create a message-passing statistics object to provide this functionality. Your statistics object should adhere to the following interface:

The constructor should be called make-stat. This should create a new statistics object with no data, but which is capable of storing an internal list of data that it can update as needed.
You should provide an 'add message to insert an additional data value into the list.
You should provide messages to obtain the current mean and variance of the numbers stored in the internal list: 'mean and 'variance. Sending either of these messages to a stat object that has no data should result in an error message.
You should have a 'clear message which removes all the stored numbers from the internal list.

Note that you shouldn't provide any messages to return the internal list itself -- it should stay internal.

You're allowed to use the definitions of mean and variance given above in your code. You should also write a contract and a comment describing the usage of the message-passing object created by the make-stat function.

Here are some example interactions with a statistics object.

(define mystat (make-stat))
(mystat 'mean)
;; --> error message of some sort
(mystat 'add 1)
(mystat 'add 2)
(mystat 'add 3)
(mystat 'mean)      ;; should --> 2
(mystat 'add 4)
(mystat 'variance)  ;; should --> 5/4
(mystat 'clear)
(mystat 'add 1)
(mystat 'mean)      ;; should --> 1