next up previous




MASSACHVSETTS INSTITVTE OF TECHNOLOGY
Department of Electrical Engineering and Computer Science
6.001--Structure and Interpretation of Computer Programs
Fall Semester, 1998


Problem Set 3

A Graphics Design Language1

The goal of this problem set is to reinforce ideas about data abstraction and higher-order procedures, and to emphasize the expressive power that derives from appropriate primitives, means of combination, and means of abstraction. We'll do this by working with Peter Henderson's ``square-limit'' graphics design language, which is described in section 2.2.4 of the textbook. You should study that section before beginning work on this assignment.2

1. Tutorial exercises

Tutorial exercise 1:

Do exercises 2.46, 2.47, and 2.48 of the textbook, which ask you to define selectors and constructors that implement data structures for vectors (make-vect, xcor-vect, ycor-vect), for frames (make-frame, origin-frame, edge1-frame, edge2-frame), and for line segments (make-segment, start-segment, end-segment), as well as some basic vector operations (add-vect, sub-vect, scale-vect). You need not try these on the computer now (although you'll need to do this as part of the programming assignment). Note that there are different possible answers for these: the choice of representation is up to you. In tutorial, expect that your tutor will ask you to draw box-and-pointer diagrams to describe some of these data structures, and also to discuss how these structures are printed by the Scheme interpreter.

Type signatures

In this problem set, you will be dealing with several data types as well as higher order procedures, and it can get confusing. Knowing the type signatures of various procedures will help you tell when you can use which procedure and with what arguments.

Two basic types of Scheme values are numbers (Sch-Num) and booleans (Sch-Bool). The procedure

(define multiply-by-2 (lambda (x) (* 2 x))),

for example, takes as input a Sch-Num and returns a Sch-Num. In type notation, this is represented as: multiply-by-2: Sch-Num $\rightarrow$ Sch-Num. This is known as a type signature.

When a procedure takes more than one argument, its type signature can reflect this:

$\mbox{{\tt ; multiply-by-each-other: (Sch-Num, Sch-Num) $\rightarrow$\space Sch-Num.}} \\ \mbox{{\tt (define multiply-by-each-other (lambda (a b) (* a b))),}}$

Tutorial exercise 2:

In tutorial exercise 1, you wrote constructors and selectors for data types called vectors, frames and line segments. Assuming the types of these are Vector, Frame and Segment respectively, what are the type signatures for the following procedures: make-vect, make-frame, origin-frame, make-segment and end-segment?


Recall that in Scheme, procedures can be passed in as arguments and can be returned as values as well. Consider:

$\mbox{{\tt ; multiply-by-creator: Sch-Num $\rightarrow$\space (Sch-Num $\righta... ...\tt (define multiply-by-creator (lambda (factor) (lambda (x) (* x factor)))),}}$

Here is a procedure that takes a Sch-Num as input and returns a procedure that takes a Sch-Num as input and returns a Sch-Num. Note that you can think about the earlier procedure multiply-by-2 as being equivalent to (multiply-by-creator 2). As a convenience, the type signature above could also have been written as multiply-by-creator: Sch-Num $\rightarrow$ F, where F is shorthand for a type signature corresponding to a single-argument Scheme mathematical ``function'' F = (Sch-Num $\rightarrow$ Sch-Num).

Painters themselves are procedures that when given a frame as input, display some image within that frame. So if the painter type is Painter, we have Painter = (Frame $\rightarrow$ irrelevant). There is a returned value, but it is irrelevant and not important here: all we care about is the side-effect of painting the picture.

Tutorial exercise 3:

What are some procedures in the Henderson language (section 2.2.4 of the text) that have a type signature of Painter $\rightarrow$Painter, which represents a procedure that takes a painter as input and returns a painter as output?

Tutorial exercise 4:

What are the type signatures of the following procedures: right-split, transform-painter, squash-inwards and square-of-four?

Tutorial exercise 5:

An interesting higher order procedure is compose which is defined as: 

(define (compose f g) 
   (lambda (x) (f (g x))))

If inc is the name of a procedure that adds one to its input, e.g. (define (inc x) (+ 1 x)), what is the value returned when each of the following is evaluated? 

(compose inc square)

((compose inc square) 5)

((compose square inc) 5)

((compose (compose inc square) inc) 5)

In the last example, we were able to use the result of one compose as the argument to another compose. Indeed, if we choose the types of the procedures carefully we can nest compose calls (in either argument) arbitrarily deeply, because the type of the compose return value is the same type as its inputs. To see this closure property clearly, what is the type signature for compose as it is used in the first example (compose inc square) above?

2. Programming assignment

We won't provide any general explanation of the square-limit language here, since this is covered in section 2.2.4 of the textbook. One thing that is not explained in the book, however, is how primitive painters are implemented (see the book, pages 136-137) and how to actually use a painter to draw something on the screen.

Primitive painters

The code for this assignment includes five ways to create primitive painters.

The simplest painters are created with the procedure number->painter, which takes a number as argument. These painters fill a frame with a solid shade of gray. The number specifies a gray level: 0 is black, 255 is white, and numbers in between are increasingly lighter shades of gray. Here are some examples: 

(define black (number->painter 0))
(define white (number->painter 255))
(define gray (number->painter 150))

You can also specify a painter using procedure->painter, which takes a procedure as argument. The procedure determines a gray level (0 to 255) as a function of (x,y) position, for example: 

(define vertical-shading
  (procedure->painter (lambda (x y) (* 255 y))))

The x and y arguments run from 0 to 1 and specify the fraction that each point is offset from the frame's origin along the frame's edges. Thus, the frame is filled out by the set of points (x,y)such that $0\leq x,y \leq 1$.

A third kind of painter is created by segments->painter, as described in the textbook. This takes a list of line segments as argument. This paints the line drawing specified by the list segments. For example, the wave painter shown in figure 2.10 of the book is generated by 

(define wave
  (segments->painter
   (list (make-segment (make-vect .25 0) (make-vect .35 .5))
         (make-segment (make-vect .35 .5 ) (make-vect .3 .6))
         (make-segment (make-vect .3 .6) (make-vect .15 .4))
         (make-segment (make-vect .15 .4) (make-vect 0 .65))
         (make-segment (make-vect .4 0) (make-vect .5 .3))
         (make-segment (make-vect .5 .3) (make-vect .6 0))
         (make-segment (make-vect .75 0) (make-vect .6 .45))
         (make-segment (make-vect .6 .45) (make-vect 1 .15))
         (make-segment (make-vect 1 .35) (make-vect .75 .65))
         (make-segment (make-vect .75 .65) (make-vect .6 .65))
         (make-segment (make-vect .6 .65) (make-vect .65 .85))
         (make-segment (make-vect .65 .85) (make-vect .6 1))
         (make-segment (make-vect .4 1) (make-vect .35 .85))
         (make-segment (make-vect .35 .85) (make-vect .4 .65))
         (make-segment (make-vect .4 .65) (make-vect .3 .65))
         (make-segment (make-vect .3 .65) (make-vect .15 .6))
         (make-segment (make-vect .15 .6) (make-vect 0 .85))
         )))

Another way to create a primitive painter is from a stored image. The procedure pgm-file->painter uses an image from the 6001 image collection to create a painter.3 For instance: 

(define rogers (pgm-file->painter "fovnder"))

will create the William Barton Rogers painter shown on page 130 of the textbook and give it the name rogers.

The final way to create a primitive painter is to use vectors->painter which takes a list of vectors as input and creates a painter which will draw the individual points corresponding to the endpoint of each vector. (That is, you can think of a vector as a means for defining the location of a point to be drawn.)

Using this, for example, you can draw the following pinwheel-like spiral: 

(define spiral (vectors->painter (spiral-points)))

(define (spiral-points)
  (define (helper t pointlist)
    (if (= t 100)
      pointlist
      (helper (+ t 1) (cons (make-vect  (/ (+ (*  t (cos t)) 100) 200)
                                        (/ (+ (*  t (sin t)) 100) 200))
                            pointlist))))
  (helper 0 nil))

Drawing on the screen

When the problem set code is loaded (don't load it yet!), it will create three graphics windows, named g1, g2, and g3. To paint a picture in a window, use the procedure paint. Paint takes a graphics window and a painter, determines the frame for the graphics window, and gives the frame to the painter. For example, 

(paint g1 rogers)

will show a picture of William Barton Rogers in window g1.

There is also a procedure called paint-hi-res, which paints the images at higher resolution ( $256 \times 256$ rather than $128\times 128$). Painting at a higher resolution produces better looking images, but takes four times as long. Depending on how fast your computer is, you may want to work on this problem viewing images using paint, and reserve paint-hi-res to see the details of images that you find interesting.4 When you print images, we suggest that you print only images created with paint-hi-res, not paint.

Computer exercise 1:

Load the code for problem set 3 using M-x load-problem-set. Before you can do anything else, you'll need to define the data representations and operations that you designed for tutorial exercise 1. Type in these definitions now, in a file that will hold all your answers for this problem set, and evaluate them.

If these are correct, you should be able to evaluate the expression (setup). This will create the three graphics windows and load the rest of the problem set code, which includes all of the code from section 2.2.4 of the textbook and the primitive painters black, white, gray, vertical-shading, and rogers described above. If setup works, you should be able to use paint and paint-hi-res to view images of the primitive painters.5 If you work on the problem set in multiple sessions, be sure that you reload your data abstraction definitions each time, before doing setup. You need not turn in anything for this exercise.

Computer exercise 2:

Make a collection of primitive painters to use in the rest of this lab. In addition to the ones predefined for you, define at least one new painter of each of the five primitive types: (1) a uniform grey level made with number->painter; (2) something defined with procedure->painter; (3) a line-drawing made with segments->painter; (4) an image of your choice that is loaded from the 6001 image collection with pgm-file->painter; and (5) something that draws points made with vectors->painter. Turn in a listing of your definitions.

Computer exercise 3:

Do exercise 2.50 of the textbook, which asks you for the definitions of flip-horiz, rotate180 and rotate270. The way to think about these transformations is to keep in mind where the new origin and edges of the frame should be. It will help to make a sketch. If you are confused by this, study the definition of rotate90 on page 139. Turn in a listing of your three procedures.

Computer exercise 4:

Do exercise 2.51 of the textbook, which asks for two different definitions of the procedure below. The first definition can be tricky--make sure you understand how beside works. Turn in listings of both definitions.

Computer exercise 5:

Do exercise 2.44 of the textbook, which asks you to define the procedure up-split. Turn in a listing of your up-split procedure. If you do this correctly (and also exercise 4), then corner-split and square-limit (both of which have been pre-defined for you) should work. You should now be able to duplicate the designs in figures 2.9 and 2.14 of the textbook.

Computer exercise 6:

Examine the procedure squash-inwards (and also the diamond-shaped images in figures 2.10 and 2.11). You should be able to duplicate these, since squash-inwards is predefined in the problem set code. Define a couple of procedures that, like squash-inwards, draws in a non-rectangular frame. It's also interesting to make the corners of the diamond go outside the original square. Turn in a listing of your procedure.

Computer exercise 7:

Do exercise 2.45 of the textbook, which defines the general splitting operation split. In order not to overwrite the existing definitions of right-split and up-split, test your procedure by defining
(define new-right-split (split beside below))
(define new-up-split (split below beside))
Turn in a listing of split. Hint: This exercise will really test your understanding of higher-order procedures. The thing to keep in mind is that the result returned by split is a procedure that takes as arguments a painter and a number.

Computer exercise 8:

The primitive painter creator vectors->painter allows us to specify a list of points to be painted. We can elect to display only some of these points by using a technique known as cropping. Your goal is to write a procedure crop-points that takes as input a list of points6 and a crop frame, and returns a list of only those points that fall within the crop frame. Only the points contained in this filtered list are then painted (see Figure 1).


  
Figure 1: Cropping a given a set of points results in only those points within the crop frame being displayed.
\begin{figure} \mbox{\epsfbox{crop.eps}} \epsfysize=1.5in \end{figure}

We need to be able to test if a point lies within a crop frame. We've provided you with a procedure called find-checkers-for-frame which takes a crop frame and returns a list of ``checkers'' for that frame. You can think of a checker as a test, and the test is invoked when the checker is applied to a point. The checker returns a boolean result that indicates whether or not the test was passed. A point is within the crop frame if and only if it passes each of the crop frame's checkers. 

;; given a frame, find the checkers for that frame; return them as a list
(define (find-checkers-for-frame frame)
  (let ((origin (origin-frame frame))
        (edge1  (edge1-frame frame))
        (edge2  (edge2-frame frame)))
    (let ((between-bottom-top? (lambda (point)
                                  (point-between-lines? point
                                                        origin
                                                        (add-vect origin edge2)
                                                        edge1)))
          (between-left-right? (lambda (point)
                                  (point-between-lines? point
                                                        origin
                                                        (add-vect origin edge1)
                                                        edge2))))
      (list between-bottom-top? between-left-right?))))

Given two parallel lines (e.g. the opposite sides of the crop frame for example), the procedure point-between-lines? is able to tell whether a point lies between these lines or to one side of both lines. To check if a point is within the crop frame, the point must be within both sets of parallel lines that comprise the sides of the crop frame. You do not need to worry about the details of this procedure, but it is provided in the problem set code in case you are curious.

(a) Write the procedure (in-frame? point frame-checkers) which takes a point and a list of checkers and tests whether or not the point is in the frame by seeing if the point passes all of the crop frame checker tests.

(Note that frame-checkers may contain any number of checkers, and your code should be general enough to handle this.)

(b) Now you should be able to complete the following definition:

(define (crop-points list-of-points crop-frame)
  (let ( (frame-region-checkers (find-checkers-for-frame crop-frame)) )
    <??>
  ))

Once you have defined these procedures, show what happens when you crop spiral using the crop-frame spiral-frame, both of which have been predefined for you in the problem set code.

Computer exercise 9:

Spend some time playing with the Henderson Language. Some things you might try:

1.
Create some images using your primitive painters, together with the operations you've defined so far in this problem set such as beside, squashes, flips, and rotations.

2.
Define one or two other (interesting) means of combination that takes two painters as arguments and produces a painter. You can use these (together with beside, below, and superpose) in conjunction with split, to produce new recursive designs. Explore some of these.

3.
Invent a new higher-order combiner (like split) and see what interesting images you can create.

Turn in a listing of your procedures, together with a printout of some interesting design you've made, and the code that produced it.

PS3 Design contest (Optional):

Hopefully, you generated some appealing designs in doing this problem set. You are invited to enter printouts of your best designs in the 6.001 PS3 design contest. Turn in your design collection together with your homework, but stapled separately, and make sure your name is on the work. For each design, show the expression you used to generate it. Designs will be judged by the 6.001 staff and other internationally famous art critics, and fabulous prizes will be awarded in lecture. There is a limit of two entries per student. Make sure to turn in not only the pictures, but also the procedure(s) that generated them.


Turn in answers to the following questions along with your answers to the questions in the problem set:

1.
About how much time did you spend on this homework assignment? (Reading and preparing the assignment plus computer work.)

2.
Which scheme system(s) did you use to do this assignment (for example: 6.001 lab, your own NT machine, your own Win95 machine, your own Linux machine)?

3.
We encourage you to work with others on problem sets as long as you acknowledge it (see the 6.001 General Information handout).

About this document ...

This document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998)

Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html ps3-hend.

The translation was initiated by Tony Eng on 1998-09-21

next up previous
Tony Eng
1998-09-21