CS 1 Fall 2007

Lab 8: Building a model environment

Assigned: Monday, November 19, 2007
Due: Thursday, November 29, 2007, 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

  1. As you answer the problems below, make a note on how long you spent on each of the sections.

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

  1. [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.

  2. [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)

  3. [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.

  4. [45] You have already seen box-and-pointer diagrams for cons pairs and lists. These box-and-pointer diagrams can also be used in environment diagrams in exactly the same way as you have seen before. This exercise will give you practice doing just that.

    Complete the environment diagram for the structures resulting from: [Partial environment diagram] [xfig file] (N.B. you may not need exactly the elements shown in the partial diagram, and you may want to rearrange the elements.)

    (define (make-twocount)
  (let ((count0 0)) 
    (cons (lambda () count0) ;; no arguments ==> empty frame
          (append  ;; note that append is non-destructive
           (let ((count1 0)) 
             (list 
              (lambda () count1)
              (lambda () (set! count1 (+ count1 1))
                         (set! count0 (+ count0 1)) )))
           (let ((count1 0)) 
             (list
              (lambda () count1)
              (lambda () (set! count1 (+ count1 1))
                         (set! count0 (+ count0 1)) )))
           ))))
(define a2cnt (make-twocount))

  5. [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:

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

    Recursive: [Partial environment diagram] [xfig file]

    Iterative: [Partial environment diagram] [xfig file]

  2. [40] Exercise 3.11 (message passing and environment models)

    [Partial environment diagram] [xfig file]

Part C: Mutation and message-passing

  1. [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:

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

    2. 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:

    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

Part D: Good code, bad code.

There is no part D this week.

Part E: Exposure: do loop

NOTE: This section is optional. It is intended to fill out your understanding of Scheme, and cover some useful and practical aspects of the language that we don't have time to deal with in lecture. To repeat: YOU DO NOT HAVE TO DO THIS SECTION. If you are pressed for time, feel free to skip it. If you submit it, it will be graded but the mark will not count towards your lab grade.

In our examples, we have been using recursion in order to define iterative procedures. In constrast, most computer languages (e.g. C or Java) have special iteration constructs which are used to define iterative procedures (e.g. "for loops" or "while loops"). Scheme also has a special iteration construct called a "do loop". We haven't introduced it before this point because it would have had little utility before we introduced side effects. Consider the following piece of code:

(define (side-effect-based-factorial n)
  (let ((res 1))
    (do ((i 1 (+ i 1))) ; initialization, update
        ((> i n) res)   ; test, return value
      (set! res (* res i))
    )
  ))

The do loop says to initialize variable i with the value 1. On each iteration, we update the value of i by adding 1 to it. We execute the body of the loop (in this case the set!) until the exit condition (> i n) is true, in which case we return the value in the exit clause, in this case res.

In general, the do loop has the following form:

(do ((var1 init-value1 step-expression1)
     (var2 init-value1 step-expression2)
     .
     .
     )
    (exit-condition exit-value)
  body
)

A do loop can have any number of loop variables, all of which are updated on each loop iteration (in some unspecified order). The form is similar to that of a let expression. For instance, var1 will initially be set to init-value1 and will be mutated every time through the loop using step-expression1. So if we have

(do ((i 0 (+ i 1)))
    ...

then the loop variable i starts at 0 (which is init-value1), and each time through the loop i gets set to be (+ i 1) i.e. the old value of i + 1. So i goes up by 1 each time through the loop.

The body of the loop may contain more than one expression, each of which is evaluated in order each time through the loop.

For example, we could also print the various factorial values by changing the code to:

(define (side-effect-based-factorial n)
  (let ((res 1))
    (do ((i 1 (+ i 1)))
        ((> i n) res)
      (set! res (* res i))
      (display res)
      (newline)
    )
  ))

  1. [20] Write a procedure to compute the length of a list using a do loop. Try doing this without using set!.

  2. [20] Write a procedure to compute the sum of the squares of the integers from 1 to n using a do loop.