Bringing declarative programming to Life

From Spivey's Corner
Jump to: navigation, search

A talk written for the Computing at School conference, Birmingham, Saturday 18th June 2016.

Summary

We look at three attempts to implement a simulation of Conway's Game of Life. The first, a program in the Wolfram language, turns out to be nothing more than the invocation of an inscrutable library routine. The second, using procedural programming, fails because of the temptation to build a too-deeply nested structure, and because of a mismatch between the meaning of array update and the simultaneous nature of time steps in the game. The third attempt is a functional program, consisting of several very small and often reusable pieces working together, using an abstract data type of images to represent the states.

Slides

CAS Conf 2016.001.png

[1] I’m not a schoolteacher, and I have very little idea of the problems teachers face in teaching computing in schools. But I do spend a huge fraction of my time thinking about how to teach university students to think about programming in a productive way, and it’s in that spirit that I’ve come to talk to you today.

A lot of our teaching, in Oxford as in many other universities, focuses on using a declarative approach to programming – and specifically, using functional programming – as a tool to encourage clear thinking about the essentials of designing programs.

It’s often thought that functional programming is too difficult for beginners, because it’s too far from the basic notion of putting together a sequence of commands that the computer obeys. Our experience, over twenty years of teaching programming to university students, has been the opposite: and in fact our approach has been to use functional programming as a way of explaining properly what is happening in the imperative programs that come later.

Our experience with undergraduates has been paralleled by experience with part-time, industrially-sponsored Masters students who come to us for intensive one-week courses. They find that learning some functional programming causes a revolution in the way they think about programming in any language or domain, so that whatever programs they subsequently write, they are looking for the functional program that is lurking behind them. In short, they find that you can write a functional program in any language.

What I thought might be useful today is if I showed you an example of thinking about a programming problem in a declarative style. If what I have to say is new to, you, all well and good. If not, perhaps we can use it as a springboard to talk about other things. Do feel free to stop me and ask questions.

CAS Conf 2016.002.png

[2] As an example, I’m going to use the game called Life, invented by John Conway. He describes it as a zero-player game, because there’s no room for strategy, and the game is just to watch how the situation evolves move by move. The game is played on a rectangular grid of cells, with each cell either occupied or not at each stage in the game. If an occupied cell had 2 or 3 occupied neighbours, then it feels comfortable, and remains occupied in the next generation. With only one occupied neighbour, or none at all, the cell feels lonely and dies: likewise, if it has four or more neighbours, it feels overcrowded and also dies. An unoccupied cell with exactly three occupied neighbours is fertile, and will become occupied in the next generation.

CAS Conf 2016.003.png

[3] Here you can see that four unoccupied cells, each with three occupied neighbours in the previous state, have become occupied. The overcrowded cell and the lonely one have died, and the population has gone up from 7 to 9.

CAS Conf 2016.004.png

[4] In another generation still, three fertile cells have become occupied, and two cells have died through overcrowding, so the population is now 10. If we carry on from one generation to the next, will the population grow larger and larger, or will it stabilise, or even shrink away to nothing? The only way to find out is to try it and see; and for that it is nice to use a computer instead of working it out by hand. So let’s think about writing our own program to do it.

CAS Conf 2016.005.png

[5] In the Wolfram language, we’re told, it’s easy and can be done in three lines. Here’s a program I found on the Wolfram website. The first line sets out the rules of Life, as number 224 in the list of all possible sets of rules. The second line makes a random 50 x 50 array of cells as the starting point. The third line invokes the predefined subroutine CellularAutomaton to do the real work. I don’t know about you, but I find that a bit unsatisfying. So let’s try really to build our own program for the problem.

CAS Conf 2016.006.png

[6] Following a conventional approach, we could write a loop that will iterate once for each generation.

CAS Conf 2016.007.png

[7] Then in each generation, we could iterate over all the cells in an N x N grid, first counting how many neighbours of the cell are alive, then using that to compute whether the cell will be alive in the next generation.

CAS Conf 2016.008.png

[8] And to count the live neighbours, we can write two more loops that iterate over them by row and column. Already, though, this program is starting to look unpromisingly complicated, and is rapidly disappearing towards the bottom right corner of the screen. I don’t know about you, but I find that programs like this are what my students write if they start programming without thinking things through first.

CAS Conf 2016.009.png

[9] Having computed the score for a cell, we can decide whether the cell is alive in the next generation. There’s a trick we can use: if we count the cell itself as 1/2, then the cell will be alive in the next generation if the score is higher than 2 and less than 4. We’ll exploit this trick later.

it’s tempting to update the cell straight away. But that would introduce a horrendous bug into the program: by the time we came to update the second row of the board, we would have already destroyed the old values in the first row, and those values are needed to update the second row correctly. Although the game of Life is described in terms of changes of state from one generation to the next, the simultaneous nature of the changes does not fit well with the incremental nature of array update in conventional programming languages. To be sure, we could program our way around this problem, perhaps by having two arrays, and computing the new state in a separate array from the old one, before copying it over once the calculation is complete. But, bearing in mind the temptation we’ve already suffered to make the program too deeply nested and therefore inflexible, let’s try out a different approach.

CAS Conf 2016.010.png

[10] As an antidote to the deeply nested structure, let’s set ourselves the somewhat ridiculous restriction that we won’t make any definition in our program that is longer than three lines. “How long is a line?” I hear you ask. Let me say, as much text as you can fit on a punched card. Is that alright?

Second, in order to get over the problem of the mismatch between incremental update and simultaneous change of state, let’s agree that we won’t use any variables in our program that take different values at different times. That’s the declarative programming part!

Third, though we saw in the Wolfram language that you can do anything in one line if you’re allowed to call on a big enough library of predefined stuff, we’ll let ourselves call predefined library routines, or even invent new ones, provided they are generally useful, and not evidently dreamed up for this specific purpose.

To do all this, we’re going to need to use a language that provides the facilities we need without making us break our rules to use them. I will be using the language of my own GeomLab system, which combines functional programming with the sort of graphics we will need. But the programs we write will be very much in the style of Haskell. And (though I haven’t tried it) I think you could write the same programs in Python, if first you wrote some wrappers to hide the imperative parts of Python behind a functional interface.

CAS Conf 2016.011.png

[11] Here’s the master plan: we are going to define a function next(state) that takes one state of the game as a parameter, and returns the next state of the game as its result. Then we will describe the initial state of the game as a value init, so that the entire history of the game can be assembled as a list, beginning with init, and with each subsequent element of the list obtained from the preceding one by applying the function next.

CAS Conf 2016.012.png

[12] At this point, we can exploit the predefined function repeat, which takes a count n, a function f and a starting value x, and constructs a list of length n+1 by starting with x and repeatedly applying f. For example, we can start with 3 and make a list containing 3 and ten more elements by always adding 2 to the previous value. And the entire history of a game of Life might be obtained by beginning with init and applying next two hundred times, collecting the results into a list. To fill in the details, we will represent the states of the game as images, rectangular arrays of pixels, each defined by a colour.

CAS Conf 2016.013.png

[13] So let’s look at the way colours can be used in GeomLab. There are a few predefined names in the language such as black, white and red, but we can also make our own colours by using a predefined function rgb that puts together red, green and blue components. Most computers allow 256 different levels for each component, but to be more machine-independent, GeomLab uses three fractional values between 0 and 1. We will find that black is rgb(0, 0, 0), white is rgb(1, 1, 1), and red is rgb(1, 0, 0). Let’s try it out.

CAS Snap 1.png
black $ white $ red $ rgb(3/4, 1/4, 1/2)
CAS Conf 2016.014.png

[14] Images are rectangular arrays of pixels, so if we have an image we can ask for its width and height, using two functions that are built in to the GeomLab system. We can also represent a point within the image by a pair of (integer) coordinates, and ask for the colour of the pixel at that point: it will be a value just like the red or white or black on the previous slide. Although we may know that each colour is, in the end, represented inside the computer by a 24-bit number containing three 8-bit fields, there’s no reason for us to refer to this fact explicitly. If we have two such 24-bit numbers, it makes no sense at all to try multiplying them together.

CAS Conf 2016.015.png

[15] The functions we have so far will allow us to find out all about an existing image, but how can we make new ones? It’s here that GeomLab moves away from what might happen in conventional languages, because there is no way to modify an image that already exists: we are forced to make a completely new one. The function image takes a desired width and height, together with a rule for computing the pixels of an image, and it returns an image whose pixels have been computed according to that rule. We specify the rule as a function f that maps coordinate pairs to colours, and we can explain the effect of the image function by saying that the result img has the property that its pixel at coordinates [x, y] is the same as the colour returned by the function f for those coordinates.

As you will see in the example, we can create an image by giving an explicit rule for computing each pixel from scratch. But we can also take images that exist, perhaps because they have been loaded from photos, and compute new ones by selecting certain pixels, applying coordinate transformations, or modifying the colour that appears as each pixel.

CAS Snap 2.png
image(200, 200,
    function ([x, y]) rgb(x/200, 0, y/200))

It’s worth pausing for a moment to think about just what radical ideas are being introduced here. First, the function image is higher-order (as was the function repeat that we already met): the rule f that it receives as a parameter is a function and that function is (we imagine) called many times from within image to compute the colour of each pixel. Because our program contains no assignable variables, these calls to f are entirely independent of each other, and we neither know nor care when or in what order they happen.

Also because of the absence of change in our program, the equation that specifies the pixels of the resulting image is a genuine equation: both sides can be read as mathematical expressions depending on unknowns x and y, and the equation is telling us that the two expressions always have values that are identical as colours. The desire to read equations as genuine equations is what motivates the badge where x = x+1 is crossed out. If you wear the badge to enough parties, you will eventually be challenged by an expert programmer, who will condescendingly explain that the x on one side of the equation is not the same x as on the other side. The temptation to play dumb at that point is almost irresistible.

Now, you could complain that the idea of making a completely new image whenever you want to change something will make our programs hopelessly inefficient, and my response to that is to say, “let’s try it and see”. Perhaps, in the end, we will find out that our program is too slow and have to give in and start making programs with modifiable images. But at least by that point, we will know that the program we have does what we want, even if it needs speeding up. And what’s more, we will have analysed our problem in a way that does not unnecessarily depend on sequential changes, and that puts us in a much stronger position if we want to find a way of calculating the results on a parallel computer.

CAS Conf 2016.016.png

[16] Now we know how to make images, we can carefully construct one that is mostly white, but has a few black pixels in a carefully chosen pattern.

(That definition is on four lines, but it would fit on three if we made the font smaller. And it does fit on three punched cards.)

You can see here that we’ve exploited a language feature that lets us write the rule for computing the pixels without making it into a named function.

function (p) if member(p, c) then black else white

The name p refers to the coordinate pair that identifies a pixel, and we produce the colour black of that is one of the chosen pixels, and white otherwise.

This feature is not essential to programming in a functional style, because we could name the function perfectly well (let’s call it f ). But what is essential is that functions can be nested, so that the rule for computing pixels can refer to the list c of chosen cells.

CAS Snap 3.png
init
CAS Conf 2016.017.png

[17] If we look at the image corresponding to the initial state, it is too tiny to make out the detail, because each live pixel is a tiny black speck. So here is a function that takes an image and replaces each pixel by a coloured blob.

CAS Snap 4.png
blobify(init)

The graphics system of GeomLab will enlarge the result to fill the window for a more pleasing display. Time is pressing, so let’s leave the details for another occasion.

CAS Conf 2016.018.png

[18] Now let’s define the promised function next that takes from generation to generation. The idea is simple: a cell is occupied in the next generation if it is viable in this one. Again, we use an anonymous function to give the rule for choosing colours.

And what do we mean by viable?

CAS Conf 2016.019.png

[19] Well, we count the number of occupied pixels in the region of the cell, and as before add a half if the cell itself is occupied, and look for a result strictly between 2 and 4.

This time, we take care to make our definition of the region around a point into a separate function, so as to obey our three line rule. Functional programming makes that easy, because it lets us represent the region as a list of coordinate pairs.

CAS Snap 5.png
blobify(next(init))

There are a couple more notations that help us here.

[ val(q) | q <- region(p) ]

First, we can form a list of the scores for the neighbours with this list comprehension: it it the list of values taken by val(q) as q ranges over the region around p. This construct conceals what might have been a loop in a conventional program; but because the calculation for each value q is independent and does not affect the calculations for other values of q, much of the complexity of understanding the cumulative effect of iterations of a normal loop is avoided here.

Second, we can make use of a predefined function sum that takes any list of numbers and adds them up. We could define that function for ourselves, but it’s better to have a library of functions that perform common, well-understood tasks.

Is it wasteful to make an explicit list of scores only to add them up and discard the list? Perhaps so: but as before, let’s try it first, and do something about it only if the program turns out to be too slow for our needs.

CAS Conf 2016.020.png

[20] There’s a final piece of the program still to make, in that although we can make a list showing the state of the game through history by starting with the state init and repeatedly applying next under control of the repeat function, we want to see the results evolving through time.

We could perfectly well have built in to GeomLab something that takes a list of pictures and shows them as frames in an animation, but we preferred to give some control to the viewer, and instead we provided a facility to show a picture that depends on the value of a slider control. The predefined function slide takes a rule for computing a picture based on the slider value t, and shows the results on the display.

CAS Snap 6a.png

We can use it to show an animation by calculating the appropriate frame, selecting it from the list of frames making up the animation, and returning that as the picture to display. This way you can stop the animation or make it go slower or faster or even backwards as you like.

CAS Conf 2016.021.png

[21] Now all the pieces are in place for us to build our Life program – in one line of code. Starting with the chosen initial state, we make a list of states by repeatedly applying the next-state function. Then we turn each state into a picture with blobs for the cells, and we show the list of pictures as a slider-controlled animation.

I’ve not been able to resist adding another three lines of code that colour the occupied cells according to their age.

CAS Snap 7a.png
CAS Snap 7b.png
CAS Snap 7c.png
CAS Conf 2016.022.png

[22] In this talk, we’ve seen the use of a declarative programming style – actually, functional programming – to build a program from parts. A key part of our success is the things we 
have denied ourselves: by avoiding assignable variables, we have been able to stick with statements that have a clear, mathematical meaning, avoiding nonsense like x = x+1. But more importantly, avoiding destructive change (side effects) has meant that we have not needed to worry about unforeseen interactions between parts of our program.

We have also avoided loops that explicitly sequence multiple iterations in favour of recursively defined functions, which focus on the simpler situation of recurrence relations, with a static validity not related to sequences of actions. And in fact, we have not defined any recursive functions explicitly in our program, but instead relied on predefined functions like repeat, map, and sum that package common patterns of recursion. Only one of these, repeat, embodies the notion of sequencing, and that we used because a sequence of states is explicitly part of the game of Life we are simulating.

CAS Conf 2016.023.png

[23] Another powerful idea we have exploited is abstract data types, like images, and also colours. We do not need to know how images are represented, only what operations allow us to make them and to fetch the colours of various pixels. And we don’t need to know how those operations are implemented, only what they do.

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.

When we start to study programming more seriously, we become interested in the relationship between the abstract and concrete meanings of operations on an abstract data type, and in criteria that allow us to judge that a concrete implementation faithfully satisfies an abstract specification, independently of any use to which the abstract data type may subsequently be put.

CAS Conf 2016.024.png

[24] We have a website where you can find the GeomLab program and a set of worksheets, though not yet the Life example I’ve used in 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. 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.

The Life program in GeomLab

define N = 30;

{ init -- initial state }
define init = 
  let c = [[6,2], [7,3], [8,1], [8,2], [8,3], [19,15], [20,15], [21,15]] in
  image(N, N, function (p) if member(p, c) then black else white);

{ blobify -- make circular pixels }
define blobify(img) = above([ beside([ pixel(img, [x, y]) 
  | x <- [0..width(img)-1] ]) | y <- reverse([0..height(img)-1]) ]);

{ next -- compute next state }
define next(state) = 
  image(N, N, function (p) 
    if viable(p, state) then fade(pixel(state, p)) else white);

{ viable -- test if cell is alive in next state }
define viable(p, img) =
  let val(q) = if pixel(img, q) <> white then 1 else 0 in
  let s = sum([ val(q) | q <- region(p) ]) + val(p)/2 in s > 2 and s < 4;

{ region -- neighbours of a cell }
define region([x, y]) = 
  [ [u, v] | u <- [x-1..x+1], v <- [y-1..y+1] when u <> x or v <> y ];

{ fade -- fade from red to black }
define fade(c) =
  if c = white then red else rgb(rpart(c)*3/4, 0, 0);

{ animate -- show frames under slider control }
define animate(frames) =
  let n = length(frames) in
  slide(function (t) nth(int((n-0.001)*t), frames));

let life = map(blobify, repeat(200, next, init)) in animate(life)

Note: I wrote this program using the latest development version of GeomLab. It's very likely that the version currently on the website is missing some of the functions I've used. I will look into that when I get the chance – most likely by updating the web version.

Downloads

  • Slides.
  • Handout.
  • An article about GeomLab and functional programming from the Computing at School newsletter.

Links

Personal tools

Variants
Actions
Navigation
Tools