Menu

- Chapter 1 Distilled
- Introduction
- 1.1 - The Elements Of Programming
- Expressions
- Naming and the Environment
- Evaluating Combinations
- Defining New Functions
- The Substitution Model
- Exercises
- Predicates
- Conditional Expressions
- Example: Newton’s Method
- Functions as Black-Box Abstractions
- 1.2 - Procedures and the Processes They Generate
- Linear Recursion and Iteration
- Tree Recursion
- Orders of Growth
- Exponentiation
- Example: Testing For Primality
- 1.3 Higher Order Functions
- Project - Blackjack

- Chapter 2 Distilled
- Introduction
- Data Abstraction
- Everything From Nothing
- Abstractions In Clojure
- Clojure's Data Structures
- Data Abstraction, Revisited
- Escher
- Project - Escher
- Symbolic Data
- Representing Sets
- Huffman Encoding Trees
- Zippers

This section presents a simple language for drawing pictures that illustrates the power of data abstraction and closure, and also exploits higher-order functions in an essential way. The language is designed to make it easy to experiment with patterns such as the ones in the Escher picture above, which are composed of repeated elements that are shifted and scaled. Just as cons , which satisfies the closure property, allowed us to easily build arbitrarily complicated list structure, the operations in this language, which also satisfy the closure property, allow us to easily build arbitrarily complicated patterns.

The picture language is based on the language Peter Henderson created to construct images like M.C. Escher’s “Square Limit” woodcut (see Henderson 1982)

Here is our first picture, a stick man we will call George.

```
(draw george)
```

We have used a function, `draw`

, to draw the picture.

Now another picture, made using a function called `beside`

that takes
two pictures and combines them left to right.

```
(draw (beside george george))
```

```
(draw (beside george (flip-horiz george)))
```

```
(draw (above (beside george (flip-horiz george))
(beside george (flip-horiz george))))
```

```
(draw (rotate george))
```

Given that `above`

, `beside`

and `rotate`

are functions that act on
pictures, we can make new functions that also act on pictures
ourselves.

```
(defn rotate180 [p]
(rotate (rotate p)))
(defn rotate270 [p]
(rotate (rotate (rotate p))))
(defn above [p]
;; ...
)
```

`above`

is left as an exercise, see the project

We can even use recursive functions to draw more complex pictures:

`right-split`

```
(defn right-split [p n]
(if (= n 0)
p
(let [smaller (right-split p (dec n))]
(beside p (above smaller smaller)))))
```

```
(draw (right-split george 4))
```

`corner-split`

```
(defn corner-split [p n]
(if (= n 0)
p
(let [up (up-split p (dec n))
right (right-split p (dec n))
top-left (beside up up)
bottom-right (above right right)
top-right (corner-split p (dec n))]
(beside (above top-left p)
(above top-right bottom-right)))))
```

```
(draw (corner-split george 4))
```

`quartet`

```
(defn quartet [p1 p2 p3 p4]
(above (beside p1 p2)
(beside p3 p4)))
```

```
(draw (quartet george box man bruce))
```

In addition to abstracting patterns of combining pictures, we can work at a higher level, abstracting patterns of combining picture transforming operations. That is, we can view the picture transformations as elements to manipulate and can write means of combination for these elements—functions that take picture transformations as arguments and create new picture transformations.

```
(defn square-of-four [tl tr
bl br]
(fn [p]
(let [top (beside (tl p) (tr p))
bottom (beside (bl p) (br p))]
(above top
bottom))))
```

Takes 4 operations and returns a function of a picture that draws the picture transformed by them, each in a quarter of the frame

```
(draw ((square-of-four identity flip-vert
flip-horiz rotate)
george))
```

We have thus far treated `draw`

as a primitive function and `george`

as a primitive picture (whatever that means).

Before we get started: a note on Quil, a wonderful Clojure(script) drawing library.

We instantiate a 'sketch' as follows, naming it `Escher`

and setting
it's dimensions. It will call a function called `draw-image`

to
update the picture.

```
(q/defsketch escher
:title "Escher"
:draw draw-image
:size [width height])
```

As we are using quil, we have functions for drawing lines on our sketch

```
quil.core/line ([p1 p2]
[x1 y1 x2 y2]
[x1 y1 z1 x2 y2 z2])
Draws a line (a direct path between two points) to the screen. The
version of line with four parameters draws the line in 2D. ...
```

`quil/draw`

can be used in a few different ways,
we will be mostly calling it with 2 points

Using destructuring and Clojures vector type we define functions to add, subtract and 'scale' (ie increase the length of) vectors.

```
(defn add-vec [[x1 y1] [x2 y2]]
[(+ x1 x2) (+ y1 y2)])
(defn sub-vec [[x1 y1] [x2 y2]]
; ...
)
(defn scale-vec [[x y] s]
; ...
)
```

Are just pairs of vectors

```
[[0 0] [1 1]]
```

A path is a sequence of line segments

```
(path [0 0] [1 1] [0 1] [0 0])
=> (([0 0] [1 1]) ([1 1] [0 1]) ([0 1] [0 0]))
(defn path [& veclist]
; ...
)
```

We have seen the line between code and data blur, most strongly with
the Church Numerals or with `cons`

, `car`

and `cdr`

implemented as
functions, now we do a similar thing again.

*Our pictures are also functions*, more precisely:

A picture is a function that takes a "frame" as an argument and draws itself inside it.

A frame is a rectangle, described precisely by an origin vector and 2 of it's edge vectors.

```
{:origin [100 50]
:e1 [300 100]
:e2 [150 200]})
```

This function is a picture, in that it takes a frame as an argument and draws something within the frame. It actually draws 4 lines, one along each edge of the frame.

```
(defn frame-painter [{:keys [origin e1 e2]}]
(let [corner (add-vec origin (add-vec e1 e2))]
(draw-line origin (add-vec origin e1))
(draw-line origin (add-vec origin e2))
(draw-line (add-vec origin e2) corner)
(draw-line (add-vec origin e1) corner)))
(def frame1 {:origin [200 50]
:e1 [200 100]
:e2 [150 200]})
(def frame2 {:origin [50 50]
:e1 [100 0]
:e2 [0 200]})
```

```
(frame-painter frame1)
(frame-painter frame2)
```

You can see from using `frame-painter`

on `frame1`

and `frame2`

what
the shape of the frames is. We will draw more interesting things on
them soon.

Note that the `[0,0]`

for our drawing is in the top left corner, and
`y`

increases downwards. This is standard for 2D canvases.

This function takes a list of segments and returns a picture (which remember is a function of a frame that draws things inside the frame).

This one is harder to understand:

Ignoring `frame-coord-map`

for now, you can see it calls `draw-line`

for each segment in `segment-list`

with a transformed `start`

and
`end`

(transformed by `m`

, which is `(frame-coord-map frame)`

)

```
(defn segment-painter [segment-list]
(fn [frame]
(let [m (frame-coord-map frame)]
(doseq [[start end] segment-list]
(draw-line (m start) (m end))))))
(defn frame-coord-map
[{:keys [origin e1 e2]}]
(fn [[x y]]
(add-vec origin
(add-vec (scale-vec e1 x)
(scale-vec e2 y)))))
```

`frame-coord-map`

doing?Take a look at the drawing below:

```
(def diag (segment-painter [[[0 0] [1 1]]]))
(frame-painter frame1)
(frame-painter frame2)
(diag frame1)
(diag frame2)
```

We have drawn `frame-painter`

again for `frame1`

and `frame2`

, but we
have also drawn `diag`

for each.

`diag`

is a `segment-painter`

for the segment `[[0 0] [1 1]]`

I hope this gives a clue to how `segment-painter`

works, each segment
passed in should be within the 'unit square' (the square with corners
`[0,0]`

, `[1,0]`

, `[1,1]`

and `[0,1]`

) and each is scaled using
`frame-coord-map`

to be within the frame, so that `[0,0]`

is one
corner and `[1,1]`

is the opposite corner.

`draw`

functionSo, we have pictures (which are functions of frames), but what exactly
was our `draw`

function, that we treated as primitive for a while,
doing?

Simple, `draw`

takes a picture and passes it a frame that is the whole
window (we `dec`

`height`

and `width`

here because we want boxes etc
to draw on the outside edges)

```
(def whole-window {:origin [0 0]
:e1 [(dec width) 0]
:e2 [0 (dec height)]})
(defn draw [picture]
(picture whole-window))
```

```
(defn transform-picture [p origin e1 e2]
(fn [frame]
(let [map (frame-coord-map frame)
new-origin (map origin)]
(p {:origin new-origin
:e1 (sub-vec (map e1) new-origin)
:e2 (sub-vec (map e2) new-origin)}))))
```

TODO: Describe `transform-picture`

`flip-`

and `rotate`

```
(defn flip-vert [p]
(transform-picture p [0 1] [1 1] [0 0]))
(defn flip-horiz [p]
; ...
)
(defn rotate [p]
; ...
)
```

`beside`

and `above`

```
(defn beside [p1 p2]
(let [split [0.5 0]
left (transform-picture p1 [0 0] split [0 1])
right (transform-picture p2 split [1 0] [0.5 1])]
(fn [frame]
(left frame)
(right frame))))
(defn above [p1 p2]
; ...
)
```

We used 4 pictures in the `quartet`

example above: `george`

, `box`

,
`man`

and `bruce`

. Clearly `bruce`

and `man`

are not made up of line
segments like our pictures so far. They are made using Quil's
`load-image`

function and a function called `image-painter`

that you
have to complete as an exercise.

```
(def bruce (image-painter (q/load-image "data/bruce.jpg")))
(bruce frame1)
(bruce frame2)
```

```
(defn image-painter [img]
(fn [{[ox oy] :origin
[e1x e1y] :e1
[e2x e2y] :e2
}]
(let [width (.width img)
height (.height img)]
; ...
)))
```

See the docs for Quil transforms

Just call `q/save`

inside the draw function to save an image

```
(q/save "5.png")
```

We have all we need to draw Square Limit now, it is just 4 of our
`corner-split`

's rotated and reflected and arranged as below with
`combine-four`

```
(def combine-four (square-of-four flip-horiz
identity
rotate180
flip-vert))
(defn square-limit [p n]
(combine-four (corner-split p n)))
```

```
(draw (square-limit bruce 4))
```

```
(draw (square-limit angels 4))
```

- Henderson's wonderful paper
- Frank Buss (You might want to use his tiles and do a line-segment square-limit
- Escher In JS canvas
- Geomlab Great intro to FP for kids based on these ideas
- My talk on DSLs (and my Geomlab in Clojure)