Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

SICP exercise 2.49

From Drewiki
Jump to: navigation, search
Comment The solution for this exercise requires the use of the PLT Scheme DrScheme graphical environment. Ensure the DrScheme language is set to Module before running the program.
Comment The picture language implemented by the PLT Scheme SICP picture package is slightly different than the picture language described in the text. The PLT package lacks the wave and rogers pictures; the solution provided here will use the diagonal-shading and einstein pictures provided by the PLT package instead. Also, painters in the PLT picture package don't know how to draw themselves. In order to draw a painter in the DrScheme graphical environment, use the paint procedure: it takes a single argument, the painter to draw, e.g.,

(paint einstein)

The (require ...) expression at the beginning of the program automatically loads the PLT picture package from the DrScheme web site. It may not work if you're attempting to run the program from behind a proxy or outbound firewall.

For more information on the PLT SICP picture package, see here.

Problem

Use segments->painter from the text to define the following primitive painters:

a. The painter that draws the outline of the designated frame.

b. The painter that draws an "X" by connecting opposite corners of the frame.

c. The painter that draws a diamond shape by connecting the midpoints of the sides of the frame.

d. The wave painter.

Solution

Once again, for this problem we'll use the DrScheme graphical environment along with the sicp.plt package. The package includes all of the procedures we need to implement these painters (including segments->painter), so we only need to provide the implementations for the 4 requested painters.

A painter is a procedure that takes a frame as an argument and draws itself. segments->painter takes a list of line segments and returns a painter procedure that, given a frame, will draw that list of segments in the frame. So each one of the painters we'll define takes a frame argument, creates a painter by applying segments->painter to a list of segments that draw the appropriate figure, and then applies that painter to the frame.

Here are some preliminaries. We load the package into DrScheme and define the vertices of the unit frame (these will be convenient for use with two of the painters):

#lang scheme
(require (planet "sicp.ss" ("soegaard" "sicp.plt" 2 1)))
 
(define nil '())
 
(define one 0.99)
 
(define origin (make-vect 0 0))
 
(define lower-right (make-vect one 0))
 
(define upper-left (make-vect 0 one))
 
(define upper-right (make-vect one one))
Comment Either DrScheme or sicp.plt appears to have a bug that causes it not to draw the right and top edges of the unit frame. (I used versions 4.1.3 and 2.1, respectively, for this exercise.) Edges defined using the value of one given above are drawn correctly for the examples given in this exercise, but are not in some other cases.

Here's a definition for the first painter, the one that draws the outline of a frame.

(define (outline frame)
  ((segments->painter (list (make-segment origin lower-right)
                            (make-segment lower-right upper-right)
                            (make-segment upper-right upper-left)
                            (make-segment upper-left origin)))
   frame))

The definition is straightforward: it makes a list of 4 segments, each of which is an edge of the unit frame, creates a segments->painter from this list, and then applies it to its frame argument. Let's test it using the paint procedure from the sicp.plt package:

(paint outline)

unit-frame


This definition works well enough, but it can be improved in at least two ways.

First, all of the segments that it draws are connected in sequence, i.e., the end vertex of one segment is the starting vertex of the next. It might be useful to have a procedure that takes a sequence of vertices and produces a sequence of connected line segments.

Second, note that the painter created by outline is the same every time outline is called, because segments->painter takes a list of segments, and the list always the same one. It's inefficient to create the painter each time when we could just create it once and save the result in a variable, like so:

(define outline
  (segments->painter (list (make-segment origin lower-right)
                           (make-segment lower-right upper-right)
                           (make-segment upper-right upper-left)
                           (make-segment upper-left origin))))

However, as noted on p.86 of the text in footnote 3, while this style of definition is more efficient than the original, it's less attractive for other reasons (e.g., debugging). In this solution, I'll stick with the debugging-friendly style of definition instead of the more efficient style.

Getting back to the other improvement, here's the procedure we need to implement it:

(define (connect vect-list)
  (define (iter segment-list remaining)
    (if (null? (cdr remaining))
        (reverse segment-list)
        (iter (cons (make-segment (car remaining)
                                     (cadr remaining))
                       segment-list)
                 (cdr remaining))))
  (iter nil vect-list))

connect takes a list of two or more vectors (vertices) and returns the list of connected segments defined by those points. It cdrs down the list of vertices, building a list of segments using the car and cadr of the list to define the current segment, until it reaches the last vertex in the list, at which point it returns the reverse of the segment list.

Let's test connect:

(connect (list origin
               lower-right
               upper-left
               upper-right))

Output:

(((0 . 0) 0.99 . 0) ((0.99 . 0) 0 . 0.99) ((0 . 0.99) 0.99 . 0.99))


That looks like a reasonable representation of a list of segments defining the unit frame.

Now we can change the definition of outline to the slightly more readable

(define (outline frame)
  ((segments->painter (connect (list origin
                                     lower-right
                                     upper-right
                                     upper-left
                                     origin)))
   frame))

It's not a major improvement in this case, but connect will be much more valuable when we get to the implementation of the wave painter.

Test this definition:

(paint outline)

unit-frame


The output is identical to the original version's, which is a good thing.

The "X" painter is even simpler: it draws two unconnected line segments, so we don't need the connect procedure for this definition:

(define (x-marks-the-spot frame)
  ((segments->painter (list (make-segment origin upper-right)
                            (make-segment lower-right upper-left)))
   frame))

Test:

(paint x-marks-the-spot)

x


The diamond painter isn't much harder. We make use of connect again here:

(define (diamond frame)
  (let ((start (make-vect 0.5 0)))
    ((segments->painter (connect (list start
                                       (make-vect one 0.5)
                                       (make-vect 0.5 one)
                                       (make-vect 0 0.5)
                                       start)))
     frame)))

Test:

(paint diamond)

diamond


The wave painter is a bit tedious to define, but again, not very difficult. It would be much more tedious without the convenience provided by the connect procedure!

(define (wave frame)
  ((segments->painter (append (connect (list (make-vect 0.4  0.0)
                                             (make-vect 0.5  0.33)
                                             (make-vect 0.6  0.0))) ;inside legs
                              (connect (list (make-vect 0.25 0.0)
                                             (make-vect 0.33 0.5)
                                             (make-vect 0.3  0.6)
                                             (make-vect 0.1  0.4)
                                             (make-vect 0.0  0.6))) ;lower left
                              (connect (list (make-vect 0.0  0.8)
                                             (make-vect 0.1  0.6)
                                             (make-vect 0.33 0.65)
                                             (make-vect 0.4  0.65)
                                             (make-vect 0.35 0.8)
                                             (make-vect 0.4  1.0))) ;upper left
                              (connect (list (make-vect 0.75 0.0)
                                             (make-vect 0.6  0.45)
                                             (make-vect 1.0  0.15)));lower right
                              (connect (list (make-vect 1.0  0.35)
                                             (make-vect 0.8  0.65)
                                             (make-vect 0.6  0.65)
                                             (make-vect 0.65 0.8)
                                             (make-vect 0.6  1.0)))));upper right
   frame))

Note that this definition appends multiple segment lists, each created by connect, to create a master segment list. It then applies segment->painter to this master list. It's a good demonstration of the expressive power of closure and conventional interfaces: connect returns a list of segments that just happen to be connected, and this list can be further combined with an arbitrary number of other segment lists, irrespective of their "connected-ness." It's all the same to the segment->painter procedure.

Test:

(paint wave)

wave


That's a reasonable facsimile of the "wave" image shown in the text.

Personal tools