Mainly for teachers
Overview
In this activity, participants use a computer to explore a language for describing pictures that are made up from a given set of tiles. The language has names for the tiles that are provided, and also allows more complex pictures to be built up by combining simpler pictures vertically or horizontally and applying rotations and reflections. Beginning with simple combinations of stick figures, the participants are led into exploring more complex patterns that are described by recurrence relations, then on to the patterns that are behind self-embedding pictures in the style of the Dutch artist M. C. Escher. These pictures are characterised by sequences of organic shapes that lead off to infinity, getting smaller and smaller, so that an infinite amount of detail is contained in a finite space. In the final session of the activity, participants are shown how the simple language of pictures can be used to capture the structure of one of Escher's designs, and to reproduce it on the computer screen at any desired level of detail. The final challenge is to describe another picture that is related to Escher's design but leads off to infinity in a new way.
- An article in the newsletter of the Computing at School organisation.
- A review of GeomLab from the magazine Mathematics Today.
Links with Mathematics
The activity links with topics from school mathematics and beyond: transformational geometry lies behind the operations by which complex pictures are built up; algebra is involved both in the scaling operations that make pictures fit together, and in a deeper way because the operations on pictures form an abstract algebra with its own laws; logical deduction is needed to predict the effect of different combinations of operations on pictures; inductive reasoning governs the behaviour of the recursive structures that are found in the Escher designs.
Links with more advanced mathematics are also there to be found. Several of the worksheets include limiting behaviour of one kind or another. You can ask, for example, whether the area of the n'th Sierpinski carpet tends to a limit as n tends to infinity.
The Hilbert curve that is described on another worksheet is an example of a space-filling curve. The important point here is that, if the family of curves is viewed as a family of functions from the closed interval [0, 1] to the unit square, then they converge uniformly to a limit function, and that limit function is therefore continuous. It can be shown that the limit function is in fact (contrary to intuition) a continuous bijection between [0, 1] and the unit square.
Links with Computer Science
The activity explores themes that are pervasive in computer programming, and the language that is used to describe pictures is actually a miniature programming language, similar to the functional languages that we use in Oxford to teach programming and reasoning about programs to our undergraduate students. The computer science themes that are implicitly explored are: the use of a formalised language to describe complex objects, including defining functions to simplify and structure the descriptions; the use of recursive definitions to express repetition and self-embedding; the use of data types to represent abstractly the essential features of a problem domain, whilst suppressing irrelevant details. The task addressed in the activity is the frivolous one of drawing pleasing patterns, but the same methods have been used for the much more serious task of describing the layout of components on the surface of integrated circuits.
Because the results of programs written in the miniature language are pictures that the computer shows on the screen, participants get immediate feedback on their work. The first few programs give pictures that can be visualised in advance, but quickly the programs produce pictures that are surprising in their complexity, showing that complex behaviours result from the action of even simple sets of rules. The challenge for participants is then to understand enough of the structure of the pictures they wish to create for them to describe the pictures as a program in the language. Mistakes are bound to happen (as they do in any non-trivial programming project), but the interactive, visual nature of the activity makes it easy to see when a program is wrong, and easy to mend it by trying slightly different expressions.
About the GeomLab language
GeomLab has been designed as a functional programming language -- one where programs are like mathematical functions that compute outputs from inputs, rather than being sets of instructions that modify the contents of storage cells, as they are in conventional, imperative languages. This way of programming has a long history, beginning with the language LISP, developed by John McCarthy and co-workers in the late 1950's. We use similar ideas, but with a more modern notation. A crucial difference between functional and imperative programs is that complex structures can be built imperatively by repetition -- to draw a row of men, draw the first man then repeat a certain number of times -- but in a functional program, they must be expressed recursively, by exploiting a recurrence relation -- such as the fact that a row of n men consists of a man drawn next to a row of n-1 men.
I've chosen to base the activity on functional programming for several reasons: first and foremost, because doing so makes it possible even for beginners to understand how to generate something as complex as the Escher picture within a single day. But also because functional programming exposes in a very simple way the links between computer programming and mathematics that I believe are essential to good programming. And finally, the choice of a language and a style of programming that will be unfamiliar to almost all participants means that everyone starts off on an even footing, both those who have dabbled in computer programming before and those who have never tried it.
These advantages of functional programming as a teaching medium are ones that we embrace in our undergraduate curriculum at Oxford. The power of functional programming, liberated from the step-by-step grind of expressing programs as sequences of instructions, allows our undergraduates to describe structures and to write programs of astonishing power within a few weeks of starting our course. The direct connection between programming and mathematics that is exposed in functional programming makes it possible for them to derive programs from precise, mathematical specifications, and to apply algebraic properties of programs to classify them, to simplify them and to make them more efficient. Later, the concepts and notations of functional programming become a language that undergraduates can use to describe other programs, including ones written in a conventional, imperative style.
In our part-time Masters degree programme, experienced programmers from industry come and learn about functional programming in the same way as our first year students. Hardly any of them will ever write a functional program after they finish their course, but they tell us that just knowing about this way of programming revolutionises the way they think about the other programs they work with, allowing them to see beyond the details of what those programs do line by line. We are delighted to be able to offer the same benefits to our undergraduate students.
About the GeomLab implementation
The GeomLab language is implemented by a compiler that generates code
for a very simple abstract machine, together with either an
interpreter (written in Java) for the abstract machine language,
or a lower-level translator that produces code for the Java Virtual
Machine. For the most part, the compiler and interpreter use standard
techniques of language implementation that would be taught in a
typical undergraduate computer science curriculum. GeomLab expressions
are parsed by a hand-written recursive descent parser into abstract
syntax trees, and these trees are then translated into the machine
code in a recursive process. The interpreter contains a 'big switch'
inside a loop that executes the machine code one instruction at a
time. The lower-level translator transliterates the same sequence of operations into JVM code, consulting a database of rules for more efficient translation of calls to known primitives. It assembles in memory exactly the same sequence of bytes that would be present in a .class file for the object code, then presents the byte sequence to the Java Virtual Machine as a new class to be loaded.
The implementation is structured so that new kinds of values, together with their associated primitives, can be introduced by dynamically loading Java classes. In fact, pictures and operations on pictures are implemented in exactly this way. The implementation uses Swing for the GUI, and needs to be compiled in version 1.6 or later of JDK. Some of the development was carried out using Eclipse, but released binary versions are compiled using OpenJDK.
Languages used
It's fun to make a list of the different programming languages that I used in implementing GeomLab.