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.
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.
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)))
[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)
[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'printIt'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