In [1]: 
# This notebook is a semi top-down explanation. This cell needs to be
# executed first so that the operators and helper functions are defined
# All of this is explained in the later half of the notebook

using Compose, Interact
Compose.set_default_graphic_size(2inch, 2inch)

points_f = [
    (.1, .1),
    (.9, .1),
    (.9, .2),
    (.2, .2),
    (.2, .4),
    (.6, .4),
    (.6, .5),
    (.2, .5),
    (.2, .9),
    (.1, .9),
    (.1, .1)
]

f = compose(context(), stroke("black"), line(points_f))

rot(pic) = compose(context(rotation=Rotation(-deg2rad(90))), pic)
flip(pic) = compose(context(mirror=Mirror(deg2rad(90), 0.5w, 0.5h)), pic)
above(m, n, p, q) =
    compose(context(),
            (context(0, 0, 1, m/(m+n)), p),
            (context(0, m/(m+n), 1, n/(m+n)), q))

above(p, q) = above(1, 1, p, q)

beside(m, n, p, q) =
    compose(context(),
            (context(0, 0, m/(m+n), 1), p),
            (context(m/(m+n), 0, n/(m+n), 1), q))

beside(p, q) = beside(1, 1, p, q)

over(p, q) = compose(context(),
                (context(), p), (context(), q))

rot45(pic) =
    compose(context(0, 0, 1/sqrt(2), 1/sqrt(2),
        rotation=Rotation(-deg2rad(45), 0w, 0h)), pic)

# Utility function to zoom out and look at the context
zoomout(pic) = compose(context(),
                (context(0.2, 0.2, 0.6, 0.6), pic),
                (context(0.2, 0.2, 0.6, 0.6), fill(nothing), stroke("black"), strokedash([0.5mm, 0.5mm]),
                    polygon([(0, 0), (1, 0), (1, 1), (0, 1)])))

function read_path(p_str)
    tokens = [try parsefloat(x) catch symbol(x) end for x in split(p_str, r"[\s,]+")]
    path(tokens)
end

fish = compose(context(units=UnitBox(260, 260)), stroke("black"),
            read_path(strip(readall("fish.path"))))

rotatable(pic) = @manipulate for θ=0:0.001:2π
    compose(context(rotation=Rotation(θ)), pic)
end

blank = compose(context())

fliprot45(pic) = rot45(compose(context(mirror=Mirror(deg2rad(-45))),pic))

# Hide this cell.
display(MIME("text/html"), """<script>
var cell = \$(".container .cell").eq(0), ia = cell.find(".input_area")
if (cell.find(".toggle-button").length == 0) {
ia.after(
    \$('<button class="toggle-button">Toggle hidden code</button>').click(
        function (){ ia.toggle() }
        )
    )
ia.hide()
}
</script>""")

Functional Geometry

Functional Geometry is a paper by Peter Henderson (original (1982), revisited (2002)) which deconstructs the MC Escher woodcut Square Limit

Square Limit

A picture is an example of a complex object that can be described in terms of its parts. Yet a picture needs to be rendered on a printer or a screen by a device that expects to be given a sequence of commands. Programming that sequence of commands directly is much harder than having an application generate the commands automatically from the simpler, denotational description.

A picture is a denotation of something to draw.

e.g. The value of f here denotes the picture of the letter F

In [2]: 
f
Out[2]:

Basic Operations on Pictures

We begin specifying the algebra of pictures we will use to describe Square Limit with a few operations that operate on pictures to give other pictures, namely:

  • rot : picture → picture
  • flip : picture → picture
  • rot45 : picture → picture
  • above : picture × picture → picture
  • above : int × int × picture × picture → picture
  • beside : picture × picture → picture
  • beside : int × int × picture × picture → picture
  • over : picture → picture

Rotate and flip

rot : picture → picture

Rotate a picture anti-clockwise by 90°

In [3]: 
rot(f)
Out[3]:

flip : picture → picture

Flip a picture along its virtical center axis

In [4]: 
flip(f)
Out[4]:
In [5]: 
rot(flip(f))
Out[5]:

fliprot45 : picture → picture

rotate the picture anti-clockwise by 45°, then flip it across the new virtical axis. In the paper this is implemented as $flip(rot45(fish))$. This function is rather specific to the problem at hand.

In [6]: 
fliprot45(fish)              |> zoomout # zoomout shows the bounding box
Out[6]:

Juxtaposition

above : picture × picture → picture

place a picture above another.

In [7]: 
above(f, f)
Out[7]:

above : int × int × picture × picture → picture

given m, n, picture1 and picture2, return a picture where picture1 is placed above picture2 such that their heights occupy the total height in m:n ratio

In [8]: 
above(1, 2, f, f)
Out[8]:

beside : picture × picture → picture

Similar to above but in the left-to-right direction.

In [9]: 
beside(f, f)
Out[9]:

beside : int × int × picture × picture → picture

In [10]: 
beside(1, 2, f, f)
Out[10]:
In [11]: 
above(beside(f, f), f)
Out[11]:

Superposition

over : picture → picture

place a picture upon another

In [12]: 
over(f, flip(f))
Out[12]:

Square Limit

The Fish

We will now study some of the properties of the fish.

In [13]: 
fish |> zoomout
Out[13]:
In [14]: 
rotatable(fish |> zoomout)
Out[14]:
In [15]: 
over(fish, rot(rot(fish))) |> zoomout
Out[15]:

Tiles

There is a certain kind of arrangement that is used to tile parts of the image. We call it t

In [16]: 
fish2 = fliprot45(fish)
fish3 = rot(rot(rot(fish2)))

t = over(fish, over(fish2, fish3))

t |> zoomout
Out[16]:

There is another kind of arrangement of fish which lies at the very center and regions on the diagonals. We will call it u.

In [17]: 
u = over(over(fish2, rot(fish2)),
         over(rot(rot(fish2)), rot(rot(rot(fish2)))))

u |> zoomout
Out[17]:

A few useful higher level functions

quartet tiles 4 images in a 2x2 grid

In [18]: 
quartet(p, q, r, s) =
    above(beside(p, q), beside(r, s))

quartet(f,flip(f),rot(f),f)
Out[18]:
In [19]: 
# 2inch x 2inch canvas is no more sufficient, so let's blow it up a bit
Compose.set_default_graphic_size(5inch, 5inch)
In [20]: 
quartet(u, u, u, u)     |> zoomout
Out[20]:

Notice how the fish interlock without leaving out any space in between them. Escher FTW.

cycle is a quartet of the same picture with each successive tile rotated by 90° anti-clockwise

In [21]: 
cycle(p) =
    quartet(p, rot(p), rot(rot(p)), rot(rot(rot(p))))

cycle(f)
Out[21]:

A nonet is a grid of 9 pictures.

In [22]: 
nonet(p, q, r,
      s, t, u,
      v, w, x) =
        above(1,2,beside(1,2,p,beside(1,1,q,r)),
        above(1,1,beside(1,2,s,beside(1,1,t,u)),
        beside(1,2,v,beside(1,1,w,x))))
Out[22]:
nonet (generic function with 1 method)
In [23]: 
nonet(f, f, f, f, f, f, f, f, f)
Out[23]:

More parts

Note: blank denotes a blank picture

There is a certain pattern which makes up the mid region of each of the four edges of the image. We will call this arrangement side

the 1 in side1 represents 1 level of recursion. This is the simplest side.

In [24]: 
side1 = quartet(blank, blank, rot(t), t)

side1 |> zoomout
Out[24]:

A side that is 2 levels deep.

In [25]: 
side2 = quartet(side1,side1,rot(t),t)

side2 |> zoomout
Out[25]:

A side that is n level deep.

In [26]: 
side(n) =
    if n == 1 side1 # basis
    else quartet(side(n-1),side(n-1),rot(t),t) # induction
    end

side(3) |> zoomout
Out[26]:
In [27]: 
# @manipulate lets us watch what happens as the levels increase
@manipulate for level=slider(1:4, value=1)
    side(level) |> zoomout
end
Out[27]:

Similarly, there is a certain kind of arrangement which makes up the corners of the artwork.

A corner level 1 deep is simply

In [28]: 
corner1 = quartet(blank,blank,blank,u)

corner1 |> zoomout
Out[28]:

A corner 2 levels deep, it is built using corner1, side1 and u.

In [29]: 
corner2 = quartet(corner1,side1,rot(side1),u)

corner2 |> zoomout
Out[29]:

An n level deep corner.

In [30]: 
corner(n) =
    n == 1 ? corner1 :
             quartet(corner(n-1), side(n-1), rot(side(n-1)), u)

corner(3) |> zoomout
Out[30]:
In [31]: 
# Touring the corners with a slider:

@manipulate for level=slider(1:4, value=1)
    corner(level) |> zoomout
end
Out[31]:

Square Limit

We are almost there.

Square limit is a nonet of various rotations of corner at the corners, side at the sides and u in the center.

The following equation puts this precisely:

In [32]: 
squarelimit(n) =
    nonet(corner(n), side(n), rot(rot(rot(corner(n)))),
          rot(side(n)), u, rot(rot(rot(side(n)))),
          rot(corner(n)), rot(rot(side(n))), rot(rot(corner(n))))
Out[32]:
squarelimit (generic function with 1 method)
In [33]: 
# We render a level-3 square limit on a 10inch x 10inch SVG for maximum awesome.
draw(SVG(10inch, 10inch), squarelimit(3))

Implementing the primitives with Compose

We will now implement the basic operators rot, flip, fliprot45, above, below and over with Compose.jl. (this explanation is taken mostly from the Compose website)

Compose graphics are created as a tree data structure. There are 3 types of objects that make up the nodes of the tree:

  1. Context: An internal node, defines the transformation matrix to be applied for its children
  2. Form: A leaf node that defines some geometry, like a line or a polygon
  3. Property: A leaf node that modifies how its parent's subtree is drawn, like fill color, font family, or line width.

The all-important function in Compose, is called, not surprisingly, compose. Calling compose(a, b) will return a new tree rooted at a and with b attached as a child.

That's enough to start drawing some simple shapes.

In [34]: 
Compose.set_default_graphic_size(2inch, 2inch) # switch back to smaller output

compose(context(), rectangle(), fill("tomato"))
Out[34]:

Furthermore, more complex trees can be formed by grouping subtrees with parenthesis.

In [35]: 
tomato_bisque =
    compose(context(),
        (context(), circle(), fill("bisque")),
        (context(), rectangle(), fill("tomato")))
Out[35]:

We can introspect this object with the introspect function. It returns a tree depiction of the picture

In [36]: 
introspect(tomato_bisque)
Out[36]:

The circles represent contexts, the triangles represent properties (fill color in our case) and the square represents a Form (one is a circle another is a rectangle)

When a picture needs to be drawn, Compose walks the tree, setting up the correct transformation matrices and resolving the forms into absolute coordinate system depending on the size of the canvas being drawn on.

These trees can be really big, but that's OK. Compose will draw them just fine. Let's introspect the tile .

In [37]: 
introspect(u)
Out[37]:

Let us now describe the picture of the letter F.

Notice that we use relative coordinates, where the width of the image is 1 width unit, and the height is 1 height unit

In [38]: 
points_f = [
    (.1, .1),
    (.9, .1),
    (.9, .2),
    (.2, .2),
    (.2, .4),
    (.6, .4),
    (.6, .5),
    (.2, .5),
    (.2, .9),
    (.1, .9),
    (.1, .1)
]

# line function takes a list of points and returns a Line form
f = compose(context(), stroke("black"), line(points_f))
Out[38]:

Rotating a picture involves wrapping in a context with a rotation.

In [39]: 
# rotate anti-clockwise by 90deg
rot(pic) =
    compose(context(rotation=Rotation(-Ï€/2)), pic)

rot(f)
Out[39]:

Flipping an image about the vertical center axis involves mirroring it across the axis. The axis is defined with a point on the axis and the slope of the axis in radians.

In [40]: 
flip(pic) =
    compose(context(mirror=Mirror(deg2rad(90), 0.5, 0.5)), pic)

flip(f)
Out[40]:
In [41]: 
rot45(pic) =
    compose(context(0, 0, 1/sqrt(2), 1/sqrt(2),
        rotation=Rotation(-Ï€/4, 0, 0)), pic)

rot45(f)
Out[41]:

fliprot45 involves wrapping the picture in a context which is mirrored about an axis at 45° (anti-clockwise), and then applying rot45 to it to rotate and scale appropriately.

In [42]: 
fliprot45(pic) =
    rot45(compose(context(mirror=Mirror(deg2rad(-45))),
            pic))

fliprot45(f) |> zoomout
Out[42]:

to place a picture above another, we create two child contexts which have their heights in the ratio m:n, context(x0, y0, w, h) sets up a context beginning at the point (x0, y0), with width w, and height h.

In [43]: 
above(m, n, p, q) =
    compose(context(),
            (context(0, 0, 1, m/(m+n)), p),
            (context(0, m/(m+n), 1, n/(m+n)), q))
Out[43]:
above (generic function with 2 methods)

above(p, q) is a specific case of above where m:n = 1:1

In [44]: 
above(p, q) = above(1, 1, p, q)
Out[44]:
above (generic function with 2 methods)
In [45]: 
above(f, f)
Out[45]:

beside is similar but now we divide the width instead of the height in the m:n ratio.

In [46]: 
beside(m, n, p, q) =
    compose(context(),
            (context(0, 0, m/(m+n), 1), p),
            (context(m/(m+n), 0, n/(m+n), 1), q))

beside(p, q) = beside(1, 1, p, q)

beside(f, f)
Out[46]:

To overlay an image, we simply create two child contexts (contexts fill up the parent context by default)

In [47]: 
over(p, q) = compose(context(),
                (context(), p), (context(), q))

over(f, flip(f))
Out[47]:

The Fish

The fish is stored as an SVG path in the fish.path file. We read it, tokenize it and create a path Form from it.

In [48]: 
function read_path(p_str)
    tokens = [try parsefloat(x) catch symbol(x) end for x in split(p_str, r"[\s,]+")]
    path(tokens)
end

# The fish was drawn on a canvas of 260x260 units, we will specify this
# by wrapping the path in a Unit box of this dimension

fish = compose(context(units=UnitBox(260, 260)), stroke("black"),
            read_path(strip(readall("fish.path"))))
Out[48]:

The zoomout function draws its argument in a smaller context in the middle of the canvas, and marks the extents of the smaller context with a dotted rectangle.

In [49]: 
# Utility function to zoom out and look at the context
zoomout(pic) = compose(context(),
                (context(0.2, 0.2, 0.6, 0.6), pic),
                (context(0.2, 0.2, 0.6, 0.6), fill(nothing), stroke("black"), strokedash([0.5mm, 0.5mm]),
                    polygon([(0, 0), (1, 0), (1, 1), (0, 1)])))

zoomout(fish)
Out[49]:
In [50]: 
rotatable(pic) = @manipulate for θ=0:0.001:2π
    compose(context(rotation=Rotation(θ)), pic)
end
Out[50]:
rotatable (generic function with 1 method)
In [51]: 
rotatable(fish |> zoomout)
Out[51]:

In conclusion

We described Escher's Square Limit from the description of its smaller parts, which in turn were described in terms of their smaller parts.

This seemed simple because we chose to talk in terms of an algebra to describe pictures. The primitives rot, flip, fliprot45, above, beside and over fit the job perfectly.

We were able to describe these primitves in terms of compose contexts, which the Compose library knows how to render.

Denotation can be an easy way to describe a system as well as a practical implementation method.

Abstraction barriers are useful tools that can reduce the cognitive overhead on the programmer. It entails creating layers consisting of functions which only use functions in the same layer or layers below in their own implementation. The layers in our language were:

------------------[ squarelimit ]------------------
-------------[ quartet, cycle, nonet ]-------------
---[ rot, flip, fliprot45, above, beside, over ]---
-------[ compose, context, line, path,... ]--------

Drawing this diagram out is a useful way to begin building any library.