GeomLab - exploring Computer Science

Michael Spivey
Department of Computer Science
University of Oxford

Introduction

[2] I’ve been thinking about how we can show young people something of the fascination that computer programming can have: to let them understand what it’s like to design and build a software system, and how that can be an absorbing and creative process.

One view of computer programming that’s often given to beginners is a bit old-fashioned. It emphasizes the idea that a computer carries out a program by obeying a sequence of instructions, written down as a list. Before being written as instructions, the program might be designed by drawing a flowchart (though I know of now real project where flowcharts have actually been used as a creative medium, or even kept up to date as the software evolves).

Because the instructions in the program act by changing the state of the computer, it’s important in this view of programming to explain that the memory of the computer consists of a series of boxes, each containing a number that can change. And the command by which the content of a box is changed seems paradoxical: in many programming languages, we write x = x + 1 to increment the number stored in box x, and mathematically that looks like nonsense: an equation that can have a solution only if 1 = 0.

And almost nobody can finish a talk or a television programme about this reductive view of computing without mentioning that all the information in the computer – numbers, text, pictures, sounds, and even the instructions that the computer obeys – are all stored as a sequence of binary digits. I look forward to an episode of Spooks where they hack into a computer network without looking at ones and zeros flashing past on the screen in green-on-black.

[3] Let’s look for a more constructive way to think about computer programs that expresses better the experience of creating one to solve an interesting problem.

Of course, most of the programs that are written in the world today are not at all interesting: they do boring jobs like working out the total of your Amazon order, or keeping track of the amount of stock in a shop. Then again, most of the English prose that is written holds no interest to students of literature: it is shopping lists and letters to the bank. So let’s be selective!

One sense that programmers have very strongly as a program starts to come together is that the program itself represents an artificial world. Early stages of the project have produced the building blocks from which that world can be constructed, and now with that work done, it becomes possible to choose the layout of this new world in many different ways. There’s a great feeling in a project when things suddenly begin to get simpler, because the building blocks are right and start to fit together properly. It would be lovely to find a way to get beginning students past the initial stages, so that they can see this creative part of programming.

What makes those building blocks fit together is that they behave, they have been designed to behave, according to precise and simple rules. Even with a simple idea, it can be a huge amount of work to make the idea function correctly and efficiently as a building block; but is that work has been done well, then that building block can be used in many different ways.

An example: in a text editor application, it’s wise to devote effort to finding a really flexible and robust way of storing texts and fragments of text. Once that’s done, writing the rest of the editor becomes relatively easy. In teaching larger-scale programming, I often show the students a number of implementations of text editors, some where the storage of texts is dealt with in a single part of the program text, and others where the details about storing texts are spread out over the whole of the program. Both of these ways of organizing the program make acceptably effective us of computer resources, but one of them requires much more use of human resources when we try to understand the program.

The goal is to construct the right, simple, building blocks, and then be able to put them together to get the complex behaviours we want from our programs, paradoxically without having to make the programs themselves unmanageably complex.

And the key to it all is something I call the learner driver’s principle: that you can drive a car without knowing or even being interested in how the engine works. That’s the mark of successful technology, so long as the car doesn’t break down. We need to do the same thing in computer programming: to make our building blocks and then to forget how they work inside and just use them.

The key observation here is that what matters most in any sizeable programming project is not the instructions that go to make up all the pieces of the program, but the high level structure; how the pieces fit together. That’s what experienced developers spend their time thinking about; a lot of the hard work they can delegate to others, but the big picture is something that can’t be delegated.

GeomLab

[4] So let me introduce you to a very simple artificial world, and a language for describing it.

The language has a vocabulary that includes the constants man and woman, which stand for stick figures of a man and a woman.

If you take any two expressions in the language and join them with a $ sign, that corresponds to putting one picture be$ide the other; and if you use an &, that means to put one &bove the other.

The interest in this little world is enhanced by the fact that there’s a computer system, GeomLab, developed in Oxford, that lets you type in these expressions and see the picture that results.

[5] I said that these operations, $ for beside and & for above, could be applied to any pictures, and here we see each of them being applied to a result made by the other one.

The first thing we notice is that, in an expression like man $ woman & tree, it matters in what order we read the operations, so that it is helpful to be able to use brackets to make the order precise.

And we also notice here a new rule about the behaviour of pictures with these operators: when one picture is put beside another, the two pictures are adjusted in size until they have the same height, with each picture being scaled in a way that preserves its proportions. The same behaviour affects the widths of pictures that are stacked one on top of the other.

Already we can begin to ask questions that seem mathematically natural: are the two operations associative, so that if we put three pictures in a row, it doesn’t matter how we place the brackets? Yes, as we can demonstrate with an experiment. Are they commutative? No, because it matters which picture is on the left and which on the right, or which is on the top and which on the bottom.

We can also use mathematics in another way to understand and explain what is happening. If we put two pictures together and allow each of them to be scaled freely, then we have a system with two degrees of freedom. Imposing the constraint that the heights match removes one of these degrees of freedom, leaving just one degree, and that is the size of the picture as a whole. GeomLab always draws the picture as large as it can whilst still fitting it in the window. When multiple pictures are put together with repeated applications of $ and &, there are initially as many degrees of freedom as there are pictures. But one degree of freedom disappears into the constraint associated with each operators, so after combining n pictures with n-1 operators, we are left only to resolve the final degree of freedom by setting the size of the whole picture. It’s pretty clear that some linear algebra must be going on behind the scenes to determine the sizes of all the pictures in such a way that all the constraints are satisfied.

If we define the aspect ratio of a picture to be its width divided by its height, then the aspect ratio stays the same when the picture is scaled, so long as the scaling preserves the proportions of the picture. When two pictures are put together with the $ operator, the width of the result is the sum of the widths of the scaled pictures, while the height of both scaled pictures is the same. So the aspect ratio of the result is simply the sum of the aspect ratios of the two pictures taken separately.

What happens when one picture is placed above another? In that case, the widths are the same, but the heights add up. So instead of adding the aspect ratios, we must add their reciprocals to get the reciprocal of the aspect ratio of the result. That’s exactly the same algebra as applies when electrical resistances are connected in parallel rather than in series. Isn’t that nice?

[6] The next idea is that, instead of writing similar expressions over and over again, we can give a name (here, f) to an expression, and allow it to depend on a placeholder (here, x) that is filled in when we subsequently use the name.

So having defined the function f with the definition shown here, we can ask to see the picture f(man), where the man picture has been substituted for the placeholder x. Equally, we can ask to see the picture f(woman), and see the same pattern but with the woman picture appearing in place of the man.

It also works to supply an argument value that is itself a complex picture. Here we see a picture that has three copies of the man beside the tree, a large copy at the left and two smaller ones at the right.

[7] What happens if we write f(f(man))? Well, f(man) is a picture with three men in it, so f(f(man)) consists of three copies of that picture: one with a man and two boys, and two copies with a boy and two toddlers.

So what does f(f(f(man))) look like?

You probably thought there’d be four sizes of figure. But if you’re like me, you’ll find it a bit surprising that the figures don’t get steadily smaller as we go from left to right. This is the easiest example I know of an unexpectedly complex behaviour emerging from the systematic application of a simple rule.

If we count, f(man) contains 3 figures, and f(f(man)) contains 9, and f(f(f(man))) contains 27: it’s clear that the pattern is that fn(man) contains 3ⁿ figures, and it’s clear why that should be so.

Also, we can see that f(f(man)) contains 1 column with a man, 2 containing boys and 1 containing four toddlers, a pattern that goes 1, 2, 1. In f3(man), the number of columns of different kinds is 1, 3, 3, 1. And if we try f4(man), we find the pattern 1, 4, 6, 4, 1. There’s a pattern here that I leave it to you to specify and explain.

Again, in f(f(man)), we find 1 man, 4 boys and 4 toddlers – and a square has 1 face, 4 edges and 4 vertices. In f3(man) the pattern is 1, 6, 12, 8; and 1 cube has 6 faces, 12 edges and 8 vertices. The pattern continues. Why?

[8] Another idea: we can describe a sequence of pictures by means of a recurrence relation. Or, in programming terms, we can use a recursive function to put together a row of copies of a picture.

In this definition, the basic picture is called p. We can write a recurrence saying that a row of n copies of p is a single instance of p beside a row of n-1 copies of p. We also need a boundary condition, here that a row of one copy of p is just that: a single copy of p.

With that definition, we can make a row of 4 or 6 or 10 men just be changing the number we specify as an argument to the function row. Small boys, of course, can’t resist asking to see a row of 1000 men, and we are happy to oblige, though the resemblance to a VHF television that’s just been switched off is striking. Next they ask to see a row of a million men, and this time we are less obliging. There’s a limit to everything!

Mathematically minded members of the audience will be asking, “couldn’t you start at 0 instead of 1?” And of course they’re right to ask. We could have begun by saying row(0, p) is the null picture, a magical invisible picture whose aspect ratio is 0/0. It is as real as the resistance that has no effect whether you wire it into your circuit in parallel or in series with others.

[9] Although recursion in programming has a reputation of being hard to understand, in this setting it is very easy. We can take an expression like row(4, man) and (seeing that 4 > 1) apply the rule to rewrite it as man $ row(3, man). Since this still contains an occurrence of row, we apply the rule again, and we keep on applying it until we reach row(1, man), which is just a man on its own.

The whole calculation can be expressed in terms of symbolic expressions, not in terms of the internal state of a computer. This makes it much more simple to imagine what is going on.

What makes recursive subroutines hard to understand is not recursion itself, but the idea of a subroutine as a process that suspends the ‘main program’ in order to resume it later. If the subroutine suspends one activation in order to activate another copy of itself, and if the copies can interact by means of shared updatable cells, than that gets complicated. Subroutines might be implemented that way but in our simple world without assignable variables, they behave in the way that is described here by symbolic expressions.

For us, a recursive subroutine is just a rule that might need to be used several times in a calculation. We can see that the chain of calculations must come to an end because the argument n in row(n, p) gets smaller each time we apply the recurrence, until at last the boundary condition applies.

[10] The function row produced a row of identical pictures. Here’s a function that produces a varying collection of rows that have more and more copies of a picture as we go up the page.

So crowd(a, b, p) is a crowd with a copies of p in the front row, a+1 in the second row, and so on until there are b in the back row. If a and b are the same, then the crowd consists of only one row; and if a is less than b, then the front row (at the bottom of the picture) is a row of a copies of p, and the rest is a smaller crowd with rows going from a+1 to b.

A cynic might say this was a picture of the audience at a typical Computer Science lecture. It’s a better exercise to write a function that produces a picture of a mixed audience!

[11] The worksheets that come with GeomLab suggest a series of exercises in describing pictures recursively. Here’s another example, showing how a spiral can be created by taking a smaller spiral, rotating it through 180 degrees (rot2) and adding an arm at the side and a slightly longer arm on top.

The fundamental units here are small, square tiles that show a straight connection or a right-angle bend. The helper function arm also has a recursive definition: it’s a row of n-1 straights with a bend at the left-hand end.

[12] Here’s the tenth in a series of more and more complex spirals, and the tenth of a family of zigzag shapes that are also described in the worksheets. These are quite tricky to get right, but one of the nice things about computer graphics is that even if your program is slightly wrong, you usually still get a picture of some kind. Sometimes that picture is more interesting than the one you wanted to draw!

[13] Now for the big challenge that was the original motivation for creating GeomLab, based on an idea originally due to Peter Henderson. These four tiles are provided; they fit together in various ways …

[14] One of the ways is to construct a larger, square tile T like this, with A beside B on the top and C beside D on the bottom.

[15] The remarkable thing about these tiles is that if we take a copy of T and scale it down by a factor of 2, then the reduced copy fits perfectly next to the original. We can make the scaled-down copy by stacking it on top of a blank square, so that the scaling rules force the height to be halved.

[16] It looks better if we colour in the picture; that can be done using a rule that determines the colour of a fish according to whether its nose is pointing North, South, East or West. As we’ll see, rotating a picture will also rotate the colours appropriately.

[17] Now another, rotated, copy of T fits below. I’ve used here a function rot that rotates its argument, a picture, anti-clockwise by 90 degrees.

Note how the colour of the turquoise fish is different because of the colour rotation.

[18] If we can fit one layer next to T, then it ought to be possible (it is!) to add a second layer, with copies of T at one quarter of the original size.

Actually, I’ve defined a function side(n), so that what we’re seeing here is side(2) next to T, and we could use side(3) or side(4) or any depth we wanted.

[19] The picture T is not symmetrical, but it’s possible to put four copies of tile A together to make a symmetrical tile that’s called U here. Then it’s possible to arrange four of our patterns side(2) – or any side(n) – around it.

The function frame used here is not recursive: it’s just a convenience for arranging four (rotated) copies of a side picture and four copies of a corner around a central square.

[20] It’s not too hard to find a pattern, again made from the tiles A, B, C and D, that fits in the corner.

We’ve recreated a woodcut of the Dutch artist M. C. Escher that he gave the title ‘Square Limit’. Actually, his picture showed just one stage in the development of the limit, because he made only one picture. We have made a recurrence that shows how to draw any picture in the sequence; the features quickly merge into indistinctness, but the detail is all there in the program.

There are instructions in the GeomLab worksheets to reproduce the construction that you’ve just seen, but it’s up to you to fill in the details. When you do try it out, you’ll find that a neat slider appears; and of course, you can’t resist moving it, just to see what happens.

With a couple more tiles, it’s also possible to draw a picture where the fish get smaller towards the middle instead of the outsides.

More to explore

[21] The Escher pictures are in some ways the most spectacular that we have made with GeomLab, but there’s no shortage of other ideas to explore.

Some of these ideas have been written up as worksheets, and others are just nice ideas that perhaps we will describe one day.

It’s worth noticing that, simple though the GeomLab language is, it is a general-purpose programming language that can be used for numerical calculations too. Some of my colleagues have used it to run investigations into primes and code breaking. Such uses have become more interesting recently, now that the language is implemented with snazzy technology that makes it super-fast.

The snazzy technology is a compiler that translates programs in the GeomLab language into code for the Java Virtual Machine, making it possible for the JIT on any host to generate machine code from it. This makes it possible for programs in GeomLab to run with a speed comparable to that of similar Java programs, orders of magnitude faster than could be achieved with an interpreter. We are Computer Scientists, so we have written the compiler itself in the GeomLab language, which we of course use to compile itself. Actually, it's only the functions in a GeomLab program that are compiled; top level expressions are evaluated by an interpreter, also written in the GeomLab language.

[22] Escher pictures aren’t the only recursive tiling patterns, or even the most difficult. This pattern, based on a space-filling curve due to David Hilbert, is particularly challenging to make. There are two basic tiles, the straight segment and 90-degree bend that we used earlier to make spirals and zig-zags; and it’s easy to see that the picture is made up of four smaller ones. But the thing that’s hard to get right is the places where the smaller pictures join together.

I’ve watched young people on our activity days spend an hour or more trying to get the picture to come out exactly right. It’s good to experience the frustration of trying to get a computer to do exactly what you wanted, and even better to experience the satisfaction when you succeed.

[23] Turtle graphics has long been popular as a way of introducing computer programming in an appealing way. Usually, the behaviour of the turtle is linked with the idea that the computer (and the turtle with it) is carrying out a list of instructions.

But if we separate the process of creating the list of instructions in our computer program from the task of following those instructions with (a simulation of) a robot, then interesting new possibilities emerge. We can take a list of instructions and ask the robot to carry them out backwards, or to turn to the left whenever the instructions say to turn to the right, or to put in a bit of straight driving after every command in the list. This reveals new symmetries and a new simplicity in programs that draw figures like this dragon curve.

[24] It’s no accident that many of these examples have a fractal character, because the self-embedding nature of fractal pictures arises naturally from simple recurrence relations. The recursive structure of this fractal plant was computed by a simple GeomLab program, and GeomLab has a built-in function for rendering the structure as a picture.

[25] A colour picture is nothing but a function that takes points in the plane and maps them to colours.

This picture of the Mandelbrot set was computed with the GeomLab software by specifying the function that takes a point in the complex plane and tests the behaviour of a mathematical sequence with that point as a parameter. The sequence itself is described as a recurrence; but it’s important to note that no instructions for drawing the picture needed to be given, only the function that maps coordinates to colour values.

[26] If pictures can be generated by describing them as functions from points (x, y) to colours, then pictures loaded from a camera can be described in the same way. We can modify the photo by altering the function, changing its shape by applying a linear or (as here) a non-linear transformation to the coordinates before they go into the function. In order to apply a transformation to the picture, it’s necessary to apply the inverse transformation to the coordinates before applying the image function.

Or we can change the colours in the picture by applying a function on colours to the result returned by the picture function. In the demo, I’ve used a function that swaps the green and blue components of the colour, to discover that a dark green shirt suits me quite well, but the world would not be as beautiful a place if blue grass appeared under a green sky.

The picture is 400 by 500 pixels, so each update as the slider moves requires the function describing the picture to be evaluated at 20,000 argument pairs.

[27] And if a picture is a function from (x, y) coordinates to colours, then a moving picture is nothing more than a function that takes triples (x, y, t) and yields colours. In this way we can describe distracting animations.

You are now feeling very sleepy ...

In conclusion

[28] GeomLab exploits a couple of ideas which are also at the heart of the way we teach Computer Science as a university subject in Oxford. The first of these is that, as I’ve explained, programming is not necessarily tied to the notion of a sequence of actions. In functional programming, we avoid this notion. The variables that appear in programs are the same as variables in mathematics: they are names for quantities that are unknown at the time an equation is written, and they may take different values each time the equation is used. This is different from the variables in conventional programming languages, which are names for storage cells that can change over time. We replace the nonsensical equation x = x + 1 with the equation f(x) = x + 1, which clearly defines a simple function.

We also avoid the idea of repeating a set of commands until they produce the desired result. That idea allows us to understand the working of a computer program only in terms of a sequence of destructive actions that modify one state of the computer to reach another one. It is much simpler to write programs in terms of a recurrence, which can be understood as a relationship between independent, timeless quantities. As we’ve seen, you can think about the meaning of a functional program in terms of an unfolding chain of calculations with equations, with the only difference between what the computer does and what we can do on paper being that the computer has infinitely more patience than we have to carry out very long calculations.

By moving away from variables and commands, we gain two benefits. First, it becomes easier to see how programs can be made from independent pieces. Much of the difficulty of understanding conventional programs comes from unplanned interactions between different parts of the program, mediated by shared access to modifiable state. In functional programming, the need to deal with such interactions vanishes, and it becomes possible to build programs from much smaller and simpler pieces and have the pieces work together. For example, the idea that images are functions from coordinates to pixels makes it possible to reshape a rectangular photo with transformations on the coordinates going into the function, or recolour it with transformations on the colours coming out.

With the added simplicity comes behaviour that can be described in mathematical terms, making it possible to reason explicitly and mathematically about what a program will do, or (perhaps even more important) to develop a mathematical intuition for what will happen when pieces of the program are combined.

Of course, the view of computers that involves commands and changes of state has its place, and the functional programming ideas that are used in GeomLab in the end have their implementation in terms of the ordinary instructions of the computer. (That’s my business rather than yours!) But as regards thinking about programs, which is what we’d like to teach our students to do, there’s a tremendous advantage in first developing a language that allows us to talk about what we’d like to compute, even if later we want to look closely at the sequence of events that represents how the calculation is carried out.

This liberation of programming from the idea of a single sequence of actions is increasingly important in a world where more and more of the computing that happens is concurrent rather than sequential – either because it involves computers at many places on a world-wide network, or because it needs more computing power than could ever be provided by a single, sequential processor.

[29] The other Computer Science idea that’s exploited in GeomLab is abstract data types, collections of values that support a set of operations. What’s abstract about them is that we can use them through the operations, without having to be concerned with how values in the collection are represented in the computer, or how the operations are implemented.

What makes it possible to understand and use abstract data types is that the operations are related to each other by rules. At least in the functional programming world of GeomLab, it’s possible to state these rules as algebraic equations. These rules give the operations an abstract meaning that is quite separate from the concrete meaning that is their implementation on the computer.

If we write programs that use the abstract data type through the operations alone, then the program can be understood without having to delve into the details of how the abstract data type is implemented.

[30] In GeomLab, pictures are an abstract data type. The operations, such as $, & and rot, allow us to construct complex pictures from simpler ones. They obey equations like the ones shown here that let us work out what the result of a sequence of operations will be, or allow us to see that two programs that use the abstract operations will have the same result.

Inside, GeomLab’s pictures are represented by lists of coordinates and transformation matrices, but that fact is hidden from someone using the language. Actually, the pictures have multiple implementations, including a way of showing them on the screen and a way of saving them as a Postscript picture to be included in a document.

Abstract data types have an important role to play in the design of any substantial computer system, because they allow us to control the complexity of a design, splitting it into largely independent pieces that can be understood separately.

[31] I hope it’s clear that GeomLab provides a way of exploring Computer Science ideas in an interesting way. But we’ve also designed it so that it touches the Maths curriculum in many places.

First of all, the pictures (as an abstract data type) form a kind of abstract algebra, and make it possible to explore algebraic ideas without ever explicitly saying that’s what is going on. As we’ve seen, it matters where you put the brackets in a picture expression; but also the operations obey algebraic laws that make sense visually. In some ways, this is advanced algebra that is never seen at school level, but the pictures make it accessible in a way that does not threaten.

Complex patterns in GeomLab are described by recursive functions, and that makes them comparable to the recurrences that crop up in school maths as rules for forming sequences of numbers. We’ve taken special care in designing the GeomLab language to allow recurrences to be stated in whatever terms are most convenient, but we tend to choose the form that is most often used in Maths texts. As a general-purpose programming language, GeomLab allows us to explore numerical recurrences just as easily as pictorial ones. But the pictures make the whole enterprise compelling in a way that plain numbers do not.

And one of the most appealing things about GeomLab is that, for some people at least, trying to reproduce a picture on the worksheet becomes almost obsessive. For the more complex patterns, it can only be done by thinking through the mathematics of how the pictures behave; trial and error won’t get you there. So in a sense, survival in the world of GeomLab does depend on mathematics. And that makes it an ideal world that in one way perfectly mirrors reality. Doesn’t it?

[32] We have a website where you can find the GeomLab program and a set of worksheets, including most of the pictures that are part of this talk.

The GeomLab program is based on Java and the Java Virtual Machine, so it will run on almost any computer, usually without the need to install any special software, provided your computer has Java installed (it probably has). The software works in exactly the same way on Windows computers, on Macs, and even with Linux. It’s enough to click on the Big Green Arrow on the web page and start using the program.

The website has worksheets that we generally find to be enough for a 1-2 day activity: ideal for extension work at the end of term. We often run shorter sessions to give a taste of what is possible. Others report that they have used the worksheets for a computer club in weekly sessions over the course of a term.