CS1 -- Fall 2008 -- Lab 8

CS 1 Fall 2008

Lab 8: Building a model environment

Assigned: Monday, November 17, 2008
Due: Thursday, November 27, 2008, 00:02:00

Before starting this lab, you should have read through the end of Section 3.2 in the text. Also read through this page on the rules for drawing environment model diagrams.

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

Please complete the following exercises before your recitation section. Should you have any difficulties working these basic exercises, bring your questions to recitation.

We have provided you with template files for use with the drawing program xfig that you can modify in order to build your environment diagrams more quickly. xfig instructions are here and (in much more detail) here. Alternatively, you can use Dia.

[90] Draw the environment diagram of the structures resulting from the following code:

[Partial environment diagram] [xfig file]

(define (make-point x y) ;; two-dimensional point data type
  ;; helper functions

  (define (dist-from-origin x y)
    (sqrt (+ (* x x) (* y y))))

  (define (dist x-low y-low x-high y-high)
    (let ((dx (- x-low x-high))
          (dy (- y-low y-high)))
      (sqrt (+ (* dx dx) (* dy dy)))))

  ;; Note: This is another way to do message-passing.
  ;; The only difference with the (lambda (op) ...) form
  ;; is that we give the lambda expression the name "dispatch".
  ;; This allows a message-passing object to send a message to
  ;; itself (although that isn't done here).

  (define (dispatch op)
    (cond ((eq? op 'get-x) x)
          ((eq? op 'get-y) y)
          ((eq? op 'print) 
           (display "POINT: ")
           (display x)
           (display ", ")
           (display y)
           (newline))
          ((eq? op 'dist-from-origin) ;; distance from origin
           (dist-from-origin x y))
          ((eq? op 'dist) ;; distance from another point
           (lambda (p)
             (let ((px (p 'get-x))
                   (py (p 'get-y)))
               (dist x y px py))))
          (else "unknown operation on points: " op)))

  ;; Now we return the dispatch function.
  dispatch)

(define p1 (make-point 10.0 12.5))
(define p2 (make-point 22.4 -43.9))
(p1 'dist-from-origin)
((p1 'dist) p2)

Do not "clean up" any un-bound/unnamed frames that you create along the way during the evaluation.

[15] Re-write the make-point procedure from the above example using a different style of message-passing. Instead of returning an explicit dispatch procedure, return a lambda expression that can take arbitrary numbers of arguments. Now the code that uses make-point will look like this:
```
(define p1 (make-point 10.0 12.5))
(define p2 (make-point 22.4 -43.9))
(p1 'dist-from-origin)
(p1 'dist p2)
```
[30] Consider the following code: [Partial environment diagram] [xfig file]
```
(define (funny x y z)
  (let ((x (+ x y))
        (y (+ y z))
        (z (+ z x)))
    ;; Note implicit "begin" in body of "let" expressions.
    (set! x (+ x y))
    (set! y (+ y z))
    (set! z (+ z x))
    (+ x y z)))

(funny 10 20 30)
```
Draw the environment diagram for the structures resulting from this code. Once again, do not clean up any un-bound/unnamed frames that you create along the way during the evaluation. Write a much simpler function that does the same thing as funny from an input/output standpoint (i.e. it produces exactly the same outputs when given the same inputs). This new function should not use let or set!.

Hint: See rule 8 in the environment model cheat sheet.

[20] Provide the result for the following piece of Scheme code (this problem must be done offline):

(define a 3)
(define b 4)
(define c 5)
(define (f a) 
  (lambda (x) 
    (set! a (- x 1)) 
    (set! b (+ x 1))))
(define fi1 (f c))
(define fi2 (f b))
(append 
 (begin (fi1 10) (list a b c))
 (begin (fi2 12) (list a b c)))

Part B: Book Exercises

Please work the following exercises from the textbook:

[30] Exercise 3.9 (environment model of iteration vs. recursion)

Recursive: [Partial environment diagram] [xfig file]

Iterative: [Partial environment diagram] [xfig file]
[40] Exercise 3.11 (message passing and environment models)

[Partial environment diagram] [xfig file]

Part C: Mutation and message-passing

[90] In this section, you will design a message-passing rectangle object which uses the make-point procedure described above in part A.1. The object will respond to the following messages:

message name	what it does
`'get-x-low`	returns the lowest x coordinate of the rectangle
`'get-x-high`	returns the highest x coordinate of the rectangle
`'get-y-low`	returns the lowest y coordinate of the rectangle
`'get-y-high`	returns the highest y coordinate of the rectangle
`'set-x-low!`	changes the lowest x coordinate of the rectangle
`'set-x-high!`	changes the highest x coordinate of the rectangle
`'set-y-low!`	changes the lowest y coordinate of the rectangle
`'set-y-high!`	changes the highest y coordinate of the rectangle
`'get-upper-left`	return a point object corresponding to the upper left corner of the rectangle
`'get-upper-right`	return a point object corresponding to the upper right corner of the rectangle
`'get-lower-left`	return a point object corresponding to the lower left corner of the rectangle
`'get-lower-right`	return a point object corresponding to the lower right corner of the rectangle
`'get-height`	return the height of the rectangle (i.e. the span in the y direction)
`'get-length`	return the length of the rectangle (i.e. the span in the x direction)
`'get-area`	return the area of the rectangle
`'get-overlap`	takes one argument (another rectangle) and returns a new rectangle which is the overlap of the two rectangles, or `#f` if there is no overlap.
`'print`	prints a representation of the rectangle by printing the four corners, correctly labelled; send the `'print` message to points to print the individual points

Here is a template for the code you will be writing. Sections marked ... are to be filled in with working code.

(define (make-rectangle x-low x-high y-low y-high)
  ; x-low, x-high are the lowest and highest x coordinates
  ; y-low, y-high are the lowest and highest y coordinates
  (define (dispatch op . args)
    (cond ((eq? op 'get-x-low)  ...)
          ((eq? op 'get-x-high) ...)
          ((eq? op 'get-y-low)  ...)
          ((eq? op 'get-y-high) ...)
          
          ; N.B. Don't worry about error checking for the length of 
          ; the argument list.
          ((eq? op 'set-x-low!)  ...)
          ((eq? op 'set-x-high!) ...)
          ((eq? op 'set-y-low!)  ...)
          ((eq? op 'set-y-high!) ...)
          
          ((eq? op 'get-upper-left)  ...)
          ((eq? op 'get-upper-right) ...)
          ((eq? op 'get-lower-left)  ...)
          ((eq? op 'get-lower-right) ...)
          
          ((eq? op 'get-length) ...)
          ((eq? op 'get-height) ...)
          ((eq? op 'get-area)   ...)
          ((eq? op 'overlap) ;; returns new rectangle if overlap, #f otherwise
           ...)
          ((eq? op 'print) ...)
          (else (error "invalid operation on rectangles: " op))))
  ;; Rudimentary consistency check.
  (if (or (< x-high x-low) (< y-high y-low))
      (error "Invalid arguments to make-rectangle: " x-low x-high y-low y-high))
      ;; else-clause is optional if only using 'if' for side-effects.
  dispatch)

Build two different implementations of this procedure:

where there is no additional state to store the internal representation of the rectangle -- use the arguments to the make-rectangle procedure i.e. x-low, x-high, y-low, and y-high to store the internal state of the rectangle. Mutate these as necessary.
where the internal representation consists of four points: the points corresponding to all of the corners of the rectangle. Use the arguments to the make-rectangle procedure only to initialize the internal state of the rectangle. Do not mutate these arguments. In this case, you will want to put the definition of dispatch inside a let expression.

Call the first procedure make-rectangle-1 and the second procedure make-rectangle-2.

Since you want to do as little work as possible (the mark of a good programmer!), design your implementations so that they share as much code as possible. In particular, the code corresponding to these messages should be identical for the two procedures:

'get-height
'get-length
'get-area
'get-overlap
'print

It's OK to duplicate the code corresponding to these messages in the two procedures. Note that you can send a message to the object being defined by doing a recursive call to dispatch from within the dispatch code.

For the messages which return a point object, recall that point objects are message-passing objects, so you will want to call the constructor function for points (defined above) with the appropriate arguments.

Here is some code illustrating the use of the make-rectangle procedures:

(define r1 (make-rectangle-1 0 10 0 10))
((r1 'get-lower-left) 'print)

; result:
;
; POINT: x = 0, y = 0

(r1 'print)

; result:
;
; RECTANGLE: 
; UPPER LEFT POINT: POINT: x = 0, y = 10
; UPPER RIGHT POINT: POINT: x = 10, y = 10
; LOWER RIGHT POINT: POINT: x = 10, y = 0
; LOWER LEFT POINT: POINT: x = 0, y = 0
; END OF RECTANGLE

(r1 'get-area)

; result: 100

(define r2 (make-rectangle-2 5 15 5 15))
(define r3 (r1 'overlap r2))
(r3 'print)

; result:
;
; RECTANGLE: 
; UPPER LEFT POINT: POINT: x = 5, y = 10
; UPPER RIGHT POINT: POINT: x = 10, y = 10
; LOWER RIGHT POINT: POINT: x = 10, y = 5
; LOWER LEFT POINT: POINT: x = 5, y = 5
; END OF RECTANGLE