SICP 2.50 - 2.51: Transforming and Combining Painters

From SICP section 2.2.4 Example: A Picture Language

Just as we did in exercises 2.44, 2.45, and 2.49, we can use the PLT Scheme SICP Picture Language package to run the solutions to the following exercises. You can load the picture package by putting the following (require...) expression at the beginning of your Scheme file.

(require (planet "sicp.ss" ("soegaard" "sicp.plt" 2 1)))

Exercise 2.50 asks us to define the transformation flip-horiz, which flips painters horizontally, and transformations that rotate painters counterclockwise by 180 degrees and 270 degrees.

We're expected to use the transform-painter procedure defined earlier in section 2.2.4 of the text. Since we're using the PLT Scheme SICP Picture Language package, we'll be using a version of transform-painter that's defined slightly differently than the one in the text. This procedure does not take the painter to be transformed as an argument, as does the version given in the text. Instead it takes the points that specify the corners of the new frame as arguments and returns a procedure that takes the painter as its argument.

For example, instead of defining flip-vert as:

(define (flip-vert painter)
   (transform-painter painter
             (make-vect 0.0 1.0)   ; new origin
             (make-vect 1.0 1.0)   ; new end of edge1
             (make-vect 0.0 0.0))) ; new end of edge2

We would instead pass the painter as an argument to the procedure returned from transform-painter as follows:

(define (flip-vertical painter)
   ((transform-painter (make-vect 0.0 1.0)
                       (make-vect 1.0 1.0)
                       (make-vect 0.0 0.0))
    painter))

The arguments to transform-painter are points (represented as vectors) that specify the corners of the new frame. The first point specifies the new frame's origin and the other two specify the ends of its edge vectors. Remember that the origin point in a frame is normally in the lower left hand corner. The first edge vector is the bottom edge of frame and the second edge vector is the left edge of the frame.



These edges are defined by the points (0, 0) for the origin, (1, 0) for the end point of the first edge, and (0, 1) for the end point of the second edge. In order to transform a painter we just need to redraw the figure above in the desired orientation, then call transform-painter with the new positions of the origin and the end points of the edges.

To flip a painter horizontally we just move the origin and left edge to the right.



This gives the bottom edge a new endpoint as well. The procedure (based on flip-vert) would be:

(define (flip-horizontal painter)
   ((transform-painter (make-vect 1.0 0.0)   ; origin
                       (make-vect 0.0 0.0)   ; corner1
                       (make-vect 1.0 1.0))  ; corner2
    painter))

The following images show the locations of the origin and edges when we rotate an image counterclockwise by 180 and 270 degrees.





We can implement the procedures using the origin and endpoints shown in the figures above.

(define (rotate-180 painter)
   ((transform-painter (make-vect 1.0 1.0)
                       (make-vect 0.0 1.0)
                       (make-vect 1.0 0.0))
    painter))

(define (rotate-270 painter)
   ((transform-painter (make-vect 0.0 1.0)
                       (make-vect 0.0 0.0)
                       (make-vect 1.0 1.0))
    painter))

Use the einstein painter provided by the PLT Scheme SICP Picture Language package to check the output of the procedures above.




Exercise 2.51 asks us to define the below operation for painters. The below procedure takes two painters as arguments. The resulting painter draws the first painter in the bottom of the frame and the second painter in the top. We're asked to define below in two different ways -- first by writing a procedure that is analogous to the beside procedure given in the text, and again in terms of beside and suitable rotation operations like the ones we defined in exercise 2.50.

Translating the beside procedure from the text to create the first below procedure is a simple matter of applying what we learned in exercise 2.50 above.

(define (beside painter1 painter2)
   (let ((split-point (make-vect 0.5 0.0)))
   (let ((paint-left
         (transform-painter painter1
                            (make-vect 0.0 0.0)
                            split-point
                            (make-vect 0.0 1.0)))
         (paint-right
         (transform-painter painter2
                            split-point
                           (make-vect 1.0 0.0)
                           (make-vect 0.5 1.0))))
   (lambda (frame)
     (paint-left frame)
     (paint-right frame)))))

The beside procedure first defines a split-point at the bottom center of the frame that splits the frame vertically. It then transforms the two painters provided so that they each fit into one half of the frame. Finally, it returns a procedure that, when given a frame, paints the two images in the left and right halves of the frame. Here's the analogous below procedure:

; 2.51a
(define (below-a painter1 painter2)
   (let ((split-point (make-vect 0.0 0.5)))
   (let ((paint-bottom
        ((transform-painter (make-vect 0.0 0.0)
                            (make-vect 1.0 0.0)
                            split-point)
         painter1))
        (paint-top
        ((transform-painter split-point
                            (make-vect 1.0 0.5)
                            (make-vect 0.0 1.0))
         painter2)))
   (lambda (frame)
     (paint-bottom frame)
     (paint-top frame)))))

We need to redefine the split-point so that it divides the frame horizontally instead of vertically. We then transform the painters so that they fit into the bottom and top halves of the frame. Finally, we return a procedure that draws the two halves.

The second implementation of below is even simpler than the first. We just need to draw the two painters beside each other then rotate the frame by 90 degrees. When we do that the two images will be draw on their side, so we need to rotate the individual images 90 degrees in the opposite direction inside their smaller frames. This is equivalent to rotating them 270 degrees in the same direction.

; 2.51b
(define (rotate-90 painter)
 ((transform-painter (make-vect 1.0 0.0)
                     (make-vect 1.0 1.0)
                     (make-vect 0.0 0.0))
   painter))

(define (below-b painter1 painter2)
   (rotate-90 (beside (rotate-270 painter1) (rotate-270 painter2))))

Once again, we can test with einstein to verify that these two procedures both give us the desired output.




Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

The "N Days of Christmas" Solution

A few days ago in The "N Days of Christmas" Puzzle I asked if you could figure out how many gifts you receive in total for all twelve days (not just on the twelfth day) of the song "The Twelve Days of Christmas," and to find an elegant way to calculate the number of gifts you'd receive if the number of days is extended beyond twelve.

First we need to figure out how many gifts we receive on a given day. It is a cumulative song, so you receive one partridge in a pear tree on the first day, then on the second day you receive two turtle doves and another partridge in a pear tree, and so on for twelve days. So the sequence for each day is:

1
1 + 2 = 3
1 + 2 + 3 = 6
1 + 2 + 3 + 4 = 10
1 + 2 + 3 + 4 + 5 = 15
...

That's probably enough terms that you'll start to recognize a pattern is forming. Each number in the sequence is just the sum of the first n integers, which you may recognize as the triangle numbers. For a small number of days like 12 we can just continue adding terms to the sequence and have the answer in about a minute. We could look up the formula for the nth triangle number, but with a little bit of intuition we can come up with one ourselves. (When you write your own blog, you get to pretend you're a little bit smarter and less lazy than you really are.) Sometimes it helps to draw a picture like the following:



Notice that the circles form the same sequence that we're after. Also note that since the circles are arranged in a triangle we can calculate the total number of circles by multiplying the height of the enclosing rectangle (n) by the width (n + 1) and dividing by 2. This gives us the formula for the nth triangle number.

$T_n = \frac{n(n + 1)}{2}$

That only gives us the number of gifts on the last day though. We wanted to know the number of gifts on all days combined, and we wanted to know it for any number of days. So what we really want isn't the nth triangle number (the sum of the first n integers), but the sum of the first n triangle numbers. That's a formula that we can derive from what we already know.

$\sum_{k=1}^{n}\frac{k(k + 1)}{2}$

$\frac{1}{2}\sum_{k=1}^{n}k(k + 1)$

$\frac{1}{2}\sum_{k=1}^{n}(k^2 + k)$

$\frac{1}{2}\sum_{k=1}^{n}k^2 + \frac{1}{2}\sum_{k=1}^{n}k$

At this point we should take a moment to say out loud what the two terms in this equation mean in plain English. On the left we have one-half of the sum of the first n squares, and on the right we have one-half of the sum of the first n integers. We already found a formula for the sum of the first n integers, and it seems like there ought to be a similar formula for the sum of the first n squares. There is, and to save us some time I’ll just substitute it here¹.

$\frac{1}{2}\frac{n (n + 1) (2n + 1)}{6} + \frac{1}{2}\frac{n (n + 1)}{2}$

$\frac{(n^2 + n)(2n + 1)}{12} + \frac{n(n + 1)}{4}$

$\frac{(2n^3 + 3n^2 + n)}{12} + \frac{(n^2 + n)}{4}$

$\frac{(2n^3 + 3n^2 + n)}{12} + \frac{(3n^2 + 3n)}{12}$

$\frac{(2n^3 + 6n^2 + 4n)}{12}$

$\frac{(n^3 + 3n^2 + 2n)}{6}$

$\frac{n(n^2 + 3n + 2)}{6}$

$\frac{n(n + 1)(n + 2)}{6}$

That gives us our formula for the sum of the first n triangle numbers, which is also known as a tetrahedral number. This is the number you get when you turn the first n triangles on their side and stack them in a pyramid.

So if we plug 12 into the formula above, we find out that in total there are

$\frac{12 \times 13 \times 14}{6} = 364$

total gifts given in the Twelve Days of Christmas.

Happy Holidays!

---

¹ The sequence given by the sum of the first N squares is called the square pyramidal numbers.

The "N Days of Christmas" Puzzle

I received an interesting puzzle in an email from my friend Tim recently. See if you can figure it out.

My dad and I were bored at a Christmas concert lately, so we started
talking about how many items you receive in the 12 days of Christmas.

You get 1 item on day 1, 3 items on day 2, 6 on day 3, etc. We
figured that out pretty easily, but then we were trying to come up
with a closed form solution for any number of days.

When I got home and had some paper to work with I managed to do it,
but I felt like my approach wasn't very nice.

So, can you find a solution, and more importantly do you know an
elegant way to do it?

If you're not familiar with the song, you can find the basic structure of the lyrics on Wikipedia, or just Google "the 12 days of Christmas" and you'll find it.

Just to be clear, it is a cumulative song, so you receive one partridge in a pear tree on the first day, then on the second day you receive two turtle doves and another partridge in a pear tree, for a total of four items on the first two days, and so on for twelve days. The puzzle is to find out how many gifts you receive in total for all twelve days (not just on the twelfth day), and to find an elegant way to calculate the number of gifts you'd receive if the number of days is extended beyond twelve.

You can see the solution here.

SICP 2.49: Defining Primitive Painters

From SICP section 2.2.4 Example: A Picture Language

Exercise 2.49 asks us to use segments->painter to define the following primitive painters:

1. The painter that draws the outline of the designated frame.
2. The painter that draws an "X'' by connecting opposite corners of the frame.
3. The painter that draws a diamond shape by connecting the midpoints of the sides of the frame.
4. The wave painter.

Just as we did in exercises 2.44 & 2.45, we can use the PLT Scheme SICP Picture Language package to run the exercises. You can load the picture package by putting the following (require...) expression at the beginning of your Scheme file.

(require (planet "sicp.ss" ("soegaard" "sicp.plt" 2 1)))

Since segments->painter takes a list of segments as its input parameter, each solution is just a matter of figuring out the coordinates of the endpoints of each required segment. Recall that the (0.0, 0.0) coordinate is the bottom left corner in the frame, not the top left corner as it is in many GUI environments. For each solution, we can define the list of segments first, then define a painter.

; 2.49 a.
; The painter that draws the outline of the designated frame.
(define outline-segments
 (list
  (make-segment
   (make-vect 0.0 0.0)
   (make-vect 0.0 0.99))
  (make-segment
   (make-vect 0.0 0.0)
   (make-vect 0.99 0.0))
  (make-segment
   (make-vect 0.99 0.0)
   (make-vect 0.99 0.99))
  (make-segment
   (make-vect 0.0 0.99)
   (make-vect 0.99 0.99))))

(define outline (segments->painter outline-segments))

Note that I used 0.99 instead of 1.0 for the edges of the frame. This is because the top and right edges won't be displayed if you use 1.0.

; 2.49 b.
; The painter that draws an ``X'' by connecting opposite corners of the frame.
(define x-segments
 (list
  (make-segment
   (make-vect 0.0 0.0)
   (make-vect 0.99 0.99))
  (make-segment
   (make-vect 0.0 0.99)
   (make-vect 0.99 0.0))))

(define x-painter (segments->painter x-segments))

; 2.49 c.
; The painter that draws a diamond shape by connecting the midpoints of the sides of the frame.
(define diamond-segments
 (list
  (make-segment
   (make-vect 0.0 0.5)
   (make-vect 0.5 0.0))
  (make-segment
   (make-vect 0.0 0.5)
   (make-vect 0.5 0.999))
  (make-segment
   (make-vect 0.5 0.999)
   (make-vect 0.999 0.5))
  (make-segment
   (make-vect 0.999 0.5)
   (make-vect 0.5 0.0))))

(define diamond (segments->painter diamond-segments))

The wave painter in the last part of the exercise is the image shown in Figure 2.10 of the text. It consists of 17 separate segments.

; 2.49 d.
; The wave painter.
(define wave-segments
 (list
  (make-segment
   (make-vect 0.006 0.840)
   (make-vect 0.155 0.591))
  (make-segment
   (make-vect 0.006 0.635)
   (make-vect 0.155 0.392))
  (make-segment
   (make-vect 0.304 0.646)
   (make-vect 0.155 0.591))
  (make-segment
   (make-vect 0.298 0.591)
   (make-vect 0.155 0.392))
  (make-segment
   (make-vect 0.304 0.646)
   (make-vect 0.403 0.646))
  (make-segment
   (make-vect 0.298 0.591)
   (make-vect 0.354 0.492))
  (make-segment
   (make-vect 0.403 0.646)
   (make-vect 0.348 0.845))
  (make-segment
   (make-vect 0.354 0.492)
   (make-vect 0.249 0.000))
  (make-segment
   (make-vect 0.403 0.000)
   (make-vect 0.502 0.293))
  (make-segment
   (make-vect 0.502 0.293)
   (make-vect 0.602 0.000))
  (make-segment
   (make-vect 0.348 0.845)
   (make-vect 0.403 0.999))
  (make-segment
   (make-vect 0.602 0.999)
   (make-vect 0.652 0.845))
  (make-segment
   (make-vect 0.652 0.845)
   (make-vect 0.602 0.646))
  (make-segment
   (make-vect 0.602 0.646)
   (make-vect 0.751 0.646))
  (make-segment
   (make-vect 0.751 0.646)
   (make-vect 0.999 0.343))
  (make-segment
   (make-vect 0.751 0.000)
   (make-vect 0.597 0.442))
  (make-segment
   (make-vect 0.597 0.442)
   (make-vect 0.999 0.144))))

(define wave (segments->painter wave-segments))

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP 2.46 - 2.48: Frames & Painters

From SICP section 2.2.4 Example: A Picture Language

A frame can be described by three vectors -- an origin vector and two edge vectors. The origin vector specifies the offset of the frame's origin from some absolute origin in the plane, and the edge vectors specify the offsets of the frame's corners from its origin. If the edges are perpendicular, the frame will be rectangular. Otherwise the frame will be a more general parallelogram. A two-dimensional vector v running from the origin to a point can be represented as a pair consisting of an x-coordinate and a y-coordinate.

Exercise 2.46 asks us to implement a data abstraction for vectors by giving a constructor make-vect and corresponding selectors xcor-vect and ycor-vect. In terms of these selectors and constructor, we'll also implement procedures add-vect, sub-vect, and scale-vect that perform the operations for vector addition, vector subtraction, and multiplying a vector by a scalar:

(x1, y1) + (x2, y2) = (x1 + x2, y1 + y2)
(x1, y1) - (x2, y2) = (x1 - x2, y1 - y2)
s * (x, y) = (sx, sy)

The solution for the constructor and selectors uses cons, car, and cdr in the same pattern we've seen at least a dozen times by now.

(define (make-vect x y)
   (cons x y))

(define (xcor-vect v)
   (car v))

(define (ycor-vect v)
   (cdr v))

Once we have those procedures in place, we can use them to build the vector operations specified.

(define (add-vect u v)
   (make-vect
     (+ (xcor-vect u) (xcor-vect v))
     (+ (ycor-vect u) (ycor-vect v))))

(define (sub-vect u v)
   (make-vect
     (- (xcor-vect u) (xcor-vect v))
     (- (ycor-vect u) (ycor-vect v))))

(define (scale-vect s v)
   (make-vect
     (* s (xcor-vect v))
     (* s (ycor-vect v))))

We can test these procedures out with a few known values before moving on to the next step.

> (define u (make-vect 2 4))
> u
(2 . 4)
> (define v (make-vect 3 1))
> v
(3 . 1)
> (define w (add-vect u v))
> w
(5 . 5)
> (define x (sub-vect w u))
> x
(3 . 1)
> (define y (scale-vect 3 w))
> y
(15 . 15)

Exercise 2.47 gives us the following constructors for frames, one using list and the other using cons:

(define (make-frame origin edge1 edge2)
   (list origin edge1 edge2))

(define (make-frame origin edge1 edge2)
   (cons origin (cons edge1 edge2)))

We're asked to supply the appropriate selectors to produce an implementation for frames for each of the two constructors. Like any selector implementation, the task here is simply to extract each piece from the assembled object. We'll follow the naming convention from the previous exercise and call our selectors origin-frame, edge1-frame, and edge2-frame. Let's start with the version that uses list.

; 2.47a
(define (make-frame origin edge1 edge2)
   (list origin edge1 edge2))

(define (origin-frame frame)
   (car frame))

(define (edge1-frame frame)
   (car (cdr frame)))

(define (edge2-frame frame)
   (car (cdr (cdr frame))))

The selectors simply use the right combinations of car and cdr to extract the appropriate elements from the list. We can test it with some of the same values used in the previous exercise, but we'll need to add an origin vector.

> (define f (make-frame (make-vect 0 0) (make-vect 2 4) (make-vect 3 1)))
> f
((0 . 0) (2 . 4) (3 . 1))
> (origin-frame f)
(0 . 0)
> (edge1-frame f)
(2 . 4)
> (edge2-frame f)
(3 . 1)

Because the internal representation of a frame is different in the second implementation of make-frame, one of the selectors will have to change for the second part of the exercise. The original origin-frame and edge1-frame implementations will still work, but the edge2-frame procedure causes an error if you try to use it.

; 2.47b
(define (make-frame origin edge1 edge2)
   (cons origin (cons edge1 edge2)))

(define (edge2-frame frame)
   (cdr (cdr frame)))

Run exactly the same test from above to verify that you get the same results (except for the internal structure of the frame in the second step).

> (define f (make-frame (make-vect 0 0) (make-vect 2 4) (make-vect 3 1)))
> f
((0 . 0) (2 . 4) 3 . 1)
> (origin-frame f)
(0 . 0)
> (edge1-frame f)
(2 . 4)
> (edge2-frame f)
(3 . 1)

Exercise 2.48 asks us to define a representation for segments using our vector representation from exercise 2.46 above. We'll need to define the constructor make-segment and the selectors start-segment and end-segment.

(define (make-segment v1 v2)
   (cons v1 v2))

(define (start-segment segment)
   (car segment))

(define (end-segment segment)
   (cdr segment))

Again, these use the same pattern we've seen before. In the next exercise, we'll take a closer look at the procedures above by drawing pictures with line segments using The SICP Picture Language package.


Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP 2.44 & 2.45: A Picture Language

From SICP section 2.2.4 Example: A Picture Language

The next section of SICP is an extended example that illustrates the features of the picture language introduced in SICP Lecture 3A: Henderson Escher Example. I'm going to be using the PLT Scheme SICP Picture Language package to run the examples and exercises. You can load the picture package by putting the following (require...) expression at the beginning of your Scheme file.

(require (planet "sicp.ss" ("soegaard" "sicp.plt" 2 1)))

The painter primitive in the PLT package behaves slightly differently than the one presented in the text, in that it doesn't display itself. To display a painter you must call the paint procedure, which takes a painter as its argument.

> (paint einstein)





> (paint diagonal-shading)

The einstein and diagonal-shading painter values are built in to the PLT Scheme Picture Language package. The package also includes procedures for flipping, rotating and combining painter values, similar to those discussed in the lecture.

> (paint (flip-horiz einstein))





> (paint (flip-vert einstein))





> (paint (rotate90 einstein))





> (paint (beside einstein einstein))





> (paint (below einstein einstein))

Now that we can work with painters, we can start to combine them in ways that form patterns. For example, the text shows us how we can combine an image beside a flipped representation of itself, then draw the resulting painter below itself.

(define (flipped-pairs painter)

   (let ((painter2 (beside painter (flip-vert painter))))

     (below painter2 painter2)))



> (paint (flipped-pairs einstein))

We can also define recursive operations, like right-split, which makes painters split and branch towards the right as many times as we specify.

(define (right-split painter n)

   (if (= n 0)

       painter

       (let ((smaller (right-split painter (- n 1))))

         (beside painter (below smaller smaller)))))



> (paint (right-split einstein 3))

Exercise 2.44 asks us to define the procedure up-split. It's similar to right-split, except that it switches the roles of below and beside.

(define (up-split painter n)

   (if (= n 0)

       painter

       (let ((smaller (up-split painter (- n 1))))

         (below painter (beside smaller smaller)))))



> (paint (up-split einstein 3))

Once we have both right-split and up-split defined, we can create balanced patterns by branching in both directions.

(define (corner-split painter n)

   (if (= n 0)

      painter

       (let ((up (up-split painter (- n 1)))

            (right (right-split painter (- n 1))))

         (let ((top-left (beside up up))

               (bottom-right (below right right))

               (corner (corner-split painter (- n 1))))

           (beside (below painter top-left)

                   (below bottom-right corner))))))



> (paint (corner-split einstein 1))





> (paint (corner-split einstein 2))

By combining four copies of the corner-split pattern, we can create the square-limit pattern from the Escher drawing that we saw in the lecture.

(define (square-limit painter n)

   (let ((quarter (corner-split painter n)))

     (let ((half (beside (flip-horiz quarter) quarter)))

       (below (flip-vert half) half))))



> (paint (square-limit einstein 4))

Exercise 2.45 points out that right-split and up-split can be expressed as instances of a general splitting operation. We are to define a split procedure, and then rewrite right-split and up-split in terms of split as follows:

(define right-split (split beside below))

(define up-split (split below beside))

We already noted the similarity between the two procedures right-split and up-split when we solved exercise 2.44 above. The only real difference between them is in which direction they split the painter first. Given the amount of duplication between the two, we can use either one of these procedures as a template for split.

(define (split dir1 dir2)

   (lambda (painter n)

     (if (= n 0)

         painter

         (let ((smaller ((split dir1 dir2) painter (- n 1))))

           (dir1 painter (dir2 smaller smaller))))))

The biggest change is that split uses a lambda to return the procedure that it creates. Once you're done substituting the new definitions for right-split and up-split, you can run the square-limit procedure again to verify that the output hasn't changed.


Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP Lecture 3A: Henderson Escher Example

Structure and Interpretation of Computer Programs
Henderson Escher Example
Covers Text Section 2.2.2

You can download the video lecture or stream it on MIT's OpenCourseWare site. It's also available on YouTube.

This lecture is presented by Professor Harold Abelson.

This lecture starts out with a review of the material covered in the previous lecture on compound data. The main points covered are pairs and the closure property (the things we make by forming pairs can also be combined to form pairs).

We're then shown how cons can be used to create lists of primitive elements in Scheme.

(cons 1
    (cons 2
         (cons 3
              (cons 4 nil))))

is the same as

(list 1 2 3 4)

A common pattern in programming is to write procedures that takes a list, do something to every element of that list, and return a list containing the results. We saw an example, scale-list, that takes a list and a factor and returns the result of each element in the list multiplied by the factor.

(define (scale-list items factor)
   (if (null? items)
       nil
       (cons (* (car items) factor)
             (scale-list (cdr items) factor))))

In Scheme terms, the general pattern here is to recursively do something to the cdr of the list and cons that on to actually doing something to the first element of the list.

The very fact that there's a general pattern there means I shouldn't be writing this procedure at all.

Instead of embedding a general pattern in each procedure that uses it, we should write a procedure that's the general pattern itself and write our procedure in terms of that higher-order procedure. For this example, that higher-order procedure is map. (See SICP 2.21 - 2.23: Mapping over lists for examples.)

(define (map proc items)
   (if (null? items)
       nil
       (cons (proc (car items))
             (map proc (cdr items)))))

The important idea here is that we stop thinking about control structures and start thinking about applying operations to aggregates.


Henderson Escher Example

The remainder of the lecture talks about one particular example, the Henderson Escher Example, that summarizes everything that's been covered in the course so far, list structure, abstraction, representation, and capturing commonality with higher-order procedures. It also goes into the third major theme of the course, meta-linguistic abstraction.

Meta-linguistic abstraction:

• Primitives
• Means of Combination
• Means of Abstraction

The example is a language developed by Peter Henderson for describing images that are composed of repeated elements that are shifted and scaled, like the M. C. Escher woodcut "Square Limit" pictured below.


The other theme illustrated by this example is the issue that there is no real difference between procedures and data.

The language operates on primitives called pictures. A picture is a procedure that draws a figure scaled to fit a rectangle that you specify. The following operations are supported in the language.

• rotate - Rotate a picture 90 degrees.
• flip - Flip a picture horizonally or vertically.
• beside - Draw two pictures beside one another.
• above - Draw two pictures, one above the other.

The closure property allows you to build complex pictures with just these few operations and one primitive (the picture itself). When you combine two pictures with beside or above, the result is itself a picture, which can be combined with other pictures.

We're going to see a lot of details concerning the implementation of the picture language illustrated in this example as we go through the exercises in the next section of the text, so I won't reproduce those details here. The gist is that we define one set of procedures to draw pictures inside of rectangles, another set of procedures that do the geometric manipulations of those pictures listed above (rotate, flip, beside, and above), then a higher-order set of procedures that combine those manipulated pictures in different ways to make an image like the Escher drawing above..


Software Design Methodologies

The last part of the lecture talks about the common software design methodology of decomposing a problem into discrete components, which are themselves decomposed into discrete components, and so on until you reach a design that looks like the tree structure below.


Each component in this kind of design is created to do one specific task, and the components only communicate with direct parent or child components in the hierarchy. Contrast this with the way the picture language was developed in the Henderson Escher example. First, a language for drawing primitive pictures was presented, then on top of that we build a language for geometric rotations, and finally, on top of that we built a language for schemes of combination.


This scheme gives you a full range of linguistic power at each level.

Lisp is a lousy language for doing any particular problem. What it's good for is figuring out the right language that you want and embedding that in Lisp.

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.