Saturday, August 20, 2011

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 "" ("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)
(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)
(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)
(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)
(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.


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