Adventures In Declarative Programming: Conway's Game Of Life

My first blog post about declarative programming explained how to write a Sudoku solver in the logic programming language Prolog. This time I'll show you how to implement Conway's Game of Life in the functional programming language Clojure.

But before that, let me explain a few general things. The first three paragraphs are for readers who are not familiar with certain concepts. People who already know what Clojure or Conway's Game of Life is, may feel free to skip those paragraphs. It starts getting serious at "Game of Life in Clojure".

Functional Programming

Functional Programming is a style of programming (a so called programming paradigm), that tries to avoid state and mutable data and emphasizes writing and using functions that have small or no side effects. This results in programs which are easier to test, maintain, understand and predict. One result of this rules is that functions are first-class, which means that they are treated like any other data. They can be created, passed around and modified just like a string.

Some languages, such as Lisp, are made for using this paradigma. Others may not be made for it, but they still can profit from this style.

Lisp

In order to understand the code below, I have to tell you a few things about how to write code in Lisp.
The code consists of s-expressions, which can be looked at as a list. This is the root of Lisp's syntax or , better say, lack of syntax. This is what allows Lisp to treat everything as data and manipulate it - even code itself. And that's the heart of the powerful macro system, which is as far as I know unique to Lisp. We will not care too much about the macro system now, but it's basically another level of abstraction which most other programming languages lack.

A s-expression can be as simple as:

(+ 1 1)
=> 2

which just adds 1 to 1. As you can see, s-expressions are written in prefix notation. Most other (imperative) languages use infix notation, but Lisp does everything for a reason. It's also strictly regular about its notation, unlike many other languages. A more complex s-expression could look like this:

(* (+ 1 (- 4 3)) (/ 6 (+ 2 1)))
=> 4

This notation might seem awkward at first, but as I said it has its cause. Since all those expressions are just simple lists, they can also be treated like that and hence manipulated by macros just like a normal list. This gives Lisp great metaprogramming and code generation capabilities.

Clojure

Clojure is a young Lisp dialect which can run in the Java Virtual Machine, the Common Language Runtime and JavaScript Engines. Since it's a Lisp, it's a functional programming language, but not purely functional such as Haskell, which means that certain functions can have side effects. It also has the beloved macro system known from other Lisp's, but we won't see that in action in this article.

One more thing rather special to Clojure as a Lisp dialect is the massive use of lazy sequences. Lazy sequences are only evaluated as far as they are needed, which avoids needless calculations and allows constructing potentially infinite data structures. We'll see them throughout the code.

Conway's Game of Life

This zero-player "game" basically consist of a cellular automaton following four rules which were devised by John Horton Conway. These rules together with the initial input determine the whole evolution of the cells in this game.

The world in which the evolution of those cells takes place is an infinite two-dimensional grid. Each cell is either dead or alive and has exactly eight neighbours.

The four rules are:

1. Any live cell with fewer than two live neighbours dies, as if caused by under-population.
2. Any live cell with two or three live neighbours lives on to the next generation.
3. Any live cell with more than three live neighbours dies, as if by overcrowding.
4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

The game starts by giving the world an initial state with certain cells being alive. Then those four rules are applied and by doing so, one of three things happen to each cell: Nothing, death or birth. After applying those rules the first time, we have the second generation of our world. The same procedure starts over and over again, until either we decide to stop it or all cells are dead.

There are some special patterns which are known to have certain behaviour. There are still lifes, oscillators, spaceships and so on. Some fancy graphics to visualize them:

Still lifes Block Boat

Oscillators Blinker Pulsar

Spaceships Glider Lightweight spaceship

You can find some more patterns at Wikipedia.

Game of Life in Clojure

I'm currently learning Clojure with the book Clojure Programming and the authors decided to show how you can work with Clojure's collection by implementing Conway's Game of Life.
Let's go through a slightly modified version of the code in the book.

The first thing we need is a representation of the world, which is a two-dimensional grid. The most obvious and simple one is just a vector of vectors (or array of arrays in other languages). Inside these vectors dead cells are indicated by a whitespace (" ") and living cells by a "X" (just because it's nicer to print them later on). Let's start by writing a function that creates an the world, which optionally accepts a set of y/x coordinates to settle living cells.

(defn create-world
  "Creates rectangular world with the specified width and height.
  Optionally takes coordinates of living cells."
  [w h & living-cells]
  (vec (for [y (range w)]
         (vec (for [x (range h)]
                (if (contains? (first living-cells) [y x]) "X" " "))))))

Line 1: Use uf defn to define a function. The form is (defn name "optional doc-string" [arguments] body).

Line 4: Argument list consisting of two fixed arguments w and h. The & allows us to create the optional argument living-cells, which is then wrapped into a list, because there could be more variables than just living-cells. This is why we have to use first at line 7.

Line 5-6: vec creates a new vector from a given collection (in this case from a lazy sequence). for is a list comprehension with the form (for [bindings] body). We use both of them twice in order to create our nested vector of vectors.

Line 7: if has the form (if test then-form else-form). If the test statement evaluates to true, the then-form is executed and otherwhise the else-form. (contains? (first living-cells) [y x])checks whether the living-cells collection contains? the [y x] coordinates of our current position. If it does, we set that cell to "X" and otherwhise to " ".

We now can generate empty worlds and worlds with certain cells being alive:

(create-world 4 4)
=> [[" " " " " " " "] [" " " " " " " "] [" " " " " " " "] [" " " " " " " "]]

(create-world 4 4 #{[0 0], [1 1], [2 2], [3 3]})
=> [["X" " " " " " "] [" " "X" " " " "] [" " " " "X" " "] [" " " " " " "X"]]

The next two functions are the core of this implementation. In order to determine the next generation, we need a function that manipulates the cells according to the rules. Since the rules always depend on the neighbours of a given cell, we need a function to determine all neighbours of a cell. The neighbours function looks like this:

(defn neighbours
  "Determines all the neighbours of a given coordinate"
  [[x y]]
  (for [dx [-1 0 1] dy [-1 0 1] :when (not= 0 dx dy)]
    [(+ dx x) (+ dy y)]))

Line 4: Usage of for to create a lazy sequence using two variables, which iterate over -1, 0 and 1. :when both of those variables are not equal to 0, the body form is executed. The rightmost binding, dy, is iterated as the fastest one.

Line 5: Calculating new coordinates based on the offsets dx and dy given by the for bindings.

What are all the neighbours of the location (1/1)?

(neighbours [1 1])
=> ([0 0] [0 1] [0 2] [1 0] [1 2] [2 0] [2 1] [2 2])

Now, instead of writing a function which behaves exactly according to the rules of Conway's Game of Life, we could write a high-order function that takes three arguments: A function to determine the neighbours, a predicate which determines whether a cell shall be given life (e.g. #{3} for Conway's rules) and one predicate that determines whether a cell survives to the next generation (#{2 3}). It then returns a function which calculates the next generation according to the given rules.

(defn stepper
  "Returns a step function for Life-like cell automata.
   neighbours takes a location and return a sequential collection
   of locations. survive? and birth? are predicates on the number
   of living neighbours."
  [neighbours birth? survive?]
  (fn [cells]
    (set (for [[loc n] (frequencies (mapcat neighbours cells))
               :when (if (cells loc) (survive? n) (birth? n))]
           loc))))

Line 7: Use of fn to create and then return a new, unnamed function. The form is (fn [arguments] body).

Line 8: Creating a set from the return value of the list comprehension which iterates over the locations loc and the number of living neighbours n. mapcat returns the concatanated list of the result of calling neighbours on all coordinates in cells. frequencies then returns a hash table (map) of each distinct item returned by the mapcat and associates it with the number of occurence.

Line 9: :when makes sure only those coordinates loc are returned that pass the if test. If loc is in cells and the number of living neighbours n is high enough according to the predicate survive?, the loc is returned. If loc is not in cells, only those loc are returned that have enough living neighbours n according to the preidcate birth? to give that cell life.

Line 10: Just return those loc that apply to the rules described before.

Let's try to generate the second state of a blinker pattern. To do so, we give our stepper the coordinates of the livings cells for the vertical position of the blinker ( --- ):

((stepper neighbours #{3} #{2 3}) #{[1 0] [1 1] [1 2]})
=> #{[2 1] [1 1] [0 1]}

As we can see, we end up with the coordinates of the horizontal position of the blinker ( | ).

#{} is a set, which can be used as a predicate (#{3} and #{2 3}) to check whether the arguments given to it are in that set. For example: (#{2 3} 3) => 3 and (#{2 3} 1) => nil

Those two functions are quite straighforward in Clojure and actually everything you need to solve Conway's Game of Life. create-world is just for the representation of the world.
For the sake of a nicer interface, we will create some definitions.

(def glider #{[2 0] [2 1] [2 2] [1 2] [0 1]})
(def light-spaceship #{[2 0] [4 0] [1 1] [1 2] [1 3] [4 3] [1 4] [2 4] [3 4]})

(def conway-stepper (stepper neighbours #{3} #{2 3}))

Line 1: def has the form (def name body). name is then assigned the value of evaluating body. In this case a set of vectors containing two integers each, which are the coordinates of the living cells.

We now have two patterns, a glider and a lightweight spaceship, and one function that manipulates cells according to the rules of Conway. The last function, which we will write now, just helps us to determine the evolution according to Conway's Game of Life by giving it the size of the world, an initial pattern and the number of the generation we want to see.

(defn conway
  "Generates world of given size with initial pattern in specified generation"
  [[w h] pattern iterations]
   (->> (iterate conway-stepper pattern)
        (drop iterations)
        first
        (create-world w h)
        (map println)))

Line 4: ->> inserts the first form as the last item into the second form, then this new form as the last item into the third form and so on. iterate has the form (iterate function value) and returns the lazy sequence value, (function value), (function (function value)), etc.

Line 5: drop has the form (drop n collection) and returns a lazy sequence of all but the first n items of collection.

Line 6: first has the form (first collection) and returns only the first item of the collection.

Line 7: Usage of our self-defined function create-world to create the world with the living cells given by the 3 lines above.

Line 8: map calls println over all the rows in our world. println just prints out the row and then a newline.

So, let's see whether all those brackets can actually generate the evolution of some cells.

(conway [5 15] light-spaceship 0)

Output:

[                             ]
[  X X X X                    ]
[X       X                    ]
[        X                    ]
[X     X                      ]

(conway [5 15] light-spaceship 1)

Output:

[    X X                      ]
[  X X X X                    ]
[  X X   X X                  ]
[      X X                    ]
[                             ]

(conway [5 15] light-spaceship 2)

Output:

[  X     X                    ]
[          X                  ]
[  X       X                  ]
[    X X X X                  ]
[                             ]

(conway [5 15] light-spaceship 3)

Output:

[                             ]
[        X X                  ]
[    X X   X X                ]
[    X X X X                  ]
[      X X                    ]

(conway [5 15] light-spaceship 4)

Output:

[                             ]
[      X X X X                ]
[    X       X                ]
[            X                ]
[    X     X                  ]

And the glider:

(conway [4 4] glider 0)

Output:

[  X    ]
[    X  ]
[X X X  ]
[       ]

(conway [4 4] glider 1)

Output:

[       ]
[X   X  ]
[  X X  ]
[  X    ]

(conway [4 4] glider 2)

Output:

[       ]
[    X  ]
[X   X  ]
[  X X  ]

(conway [4 4] glider 3)

Output:

[       ]
[  X    ]
[    X X]
[  X X  ]

(conway [4 4] glider 4)

Output:

[       ]
[    X  ]
[      X]
[  X X X]

You can download the full source code here or copy it from here:

(ns conways-game-of-life.core)

(defn create-world
  "Creates rectangular world with the specified width and height.
  Optionally takes coordinates of living cells."
  [w h & living-cells]
  (vec (for [y (range w)]
         (vec (for [x (range w)]
                (if (contains? (first living-cells) [y x]) "X" " "))))))

(defn neighbours
  "Determines all the neighbours of a given coordinate"
  [[x y]]
  (for [dx [-1 0 1] dy [-1 0 1] :when (not= 0 dx dy)]
    [(+ dx x) (+ dy y)]))

(defn stepper
  "Returns a step function for Life-like cell automata.
   neighbours takes a location and return a sequential collection
   of locations. survive? and birth? are predicates on the number
   of living neighbours."
  [neighbours birth? survive?]
  (fn [cells]
    (set (for [[loc n] (frequencies (mapcat neighbours cells))
               :when (if (cells loc) (survive? n) (birth? n))]
           loc))))

; patterns
(def glider #{[2 0] [2 1] [2 2] [1 2] [0 1]})
(def light-spaceship #{[2 0] [4 0] [1 1] [1 2] [1 3] [4 3] [1 4] [2 4] [3 4]})

; steppers
(def conway-stepper (stepper neighbours #{3} #{2 3}))

(defn conway
  "Generates world of given size with initial pattern in specified generation"
  [[w h] pattern iterations]
   (->> (iterate conway-stepper pattern)
        (drop iterations)
        first
        (create-world w h)
        (map println)))

Game of Life in Functional Python

Since I'm coming from Python, I was curious whether this solution could be implemented in Python. Python does support functional programming to some extent. This might also help some people understanding the Clojure code above a bit better.

Note that this is NOT idiomatic Python code and probably no real-world Python developer would write code like this. I was just curious how far you can push functional programming in Python, which was actually not designed to be used this way.

The code is almost a transliteration of the Clojure code, so I don't have to explain all the functions again:

from collections import Counter
from itertools import chain

def mapcat(func, iter):
    "Maps func over iter and returns concanated list"
    return chain.from_iterable(func(*args) for args in iter)

def create_world(w, h, living_cells=()):
    """Creates a rectangular world with the specified width and height.
    Optionally takes coordinates of living cells. """
    return [["X" if (y, x) in living_cells else " " for x in range(h)] for y in range(w)]

def neighbours(y, x):
    "Determines all the neighbours of a given coordinate"
    return [(dy + y, dx + x) for dy in [-1, 0, 1] for dx in [-1, 0, 1]
            if not (dy == 0 and dx == 0)]

def stepper(neighbours, birth, survive):
    """Returns a step function for Life-like cell automata.
   neighbours takes a y/x-coordinates and returns a sequential collection
   of locations. survive and birth are constraints on the number
   of living neighbours."""
    return lambda cells: set(
        [loc for (loc, n) in Counter(mapcat(neighbours, cells)).items()
                   if (loc in cells and n == birth) or n == survive])

# pattern definitions
glider = set(((2, 0), (2, 1), (2, 2), (1, 2), (0, 1)))
light_spaceship = set(((2, 0), (4, 0), (1, 1), (1, 2), (1, 3), (4, 3), (1, 4), (2, 4), (3, 4)))

# steppers
conway_stepper = stepper(neighbours, 2, 3)

def conway(w, h, pattern, iterations):
    "Generates world of given size with initial pattern in specified generation"
    cells = pattern
    
    for unused in range(iterations):
        cells = conway_stepper(cells)
        
    for row in create_world(w, h, living_cells=cells):
        print(row)

Thanks to nedbat from #python for helping me with this.

None of the functions have side effects (beside conway(), which does printing), as emphasized by the functional programming style. Also, no function depends on some global state - hence they are all deterministic. This means that those functions always return the same output when called with a specific input. They are a mapping of input to output.

You can download the full Python source code here.

Conclusion

I hope I could make you interested in functional programming and Lisp, while giving you a vague idea what these things are about. The most widely used Lisp at the moment is probably Common Lisp and there is a good and free book out there called Practical Common Lisp.

Depending on what you want to do with Lisp, it might be a good idea to take a closer look at Clojure too. It has the potential to be more widely used in the "real world", since it's running in the JVM and is often used for things like web developing. Two good books on Clojure would be Clojure Programming and The Joy Of Clojure.



Discussion on Hacker News (thanks to samrat for submitting)
Discussion on Reddit: r/coding

Massive Open Online Classes With Udacity

One part of my first 30 day challenge was doing classes on Udacity. Now, after I finished CS101 and created a search engine, I decided to blog about Udacity and the experience I made.

About Udacity

Udacity is a kind of online university, where you can attend to classes and learn new things. The main topic is computer science, but they also offer some classes about math and physics (see here). According to Sebastian Thrun, it all started after he saw this TED Talk from the founder of Khan Academy.

Udacity evolved from the online AI class, which is/was basically the same class that the students at Stanford University took - just online, available when you want and for free.

Even though I'm not a teacher or professor, I can feel Sebastian's excitement too. Imagine you could educate and therefore help thousands or even millions of people around the world.

People, who do not have free higher education in their own country. People, who are running away from war. People, who want to make their own and the life of their families a better one.

How It Works

The classes are based on YouTube videos, which are mostly between 0.5 - 5 minutes long. After you learnt a new concept, you are asked to answer questions about what you've just learnt.

Many people might think that teaching in a real class room is much better, because there is an interaction between the students and the professor, which can't really happen in those YouTube videos. When you're one student in a class room of 200 students, do you really have an interaction with your professor? The professor can't pause or explain things over and over again to each student. But you can pause and rewind the video of a professor.

And you're not totally lost on your own. There is a community of students inside Udacity, in which you are encouraged to participate. This not only allows one to ask questions because he/she didn't fully understand a concept, but also let's the more experienced students help other students. The result is a deeper understanding for everyone.

My Experience

I'm really interested in education and I do like new and different approaches, but Udacity is definitely not for everyone. Here are some of the reasons why I enjoyed taking CS101:

• Feeling of being tutored one-to-one (which leads to best results)
• Python as the programming language (very simple to read, suitable for beginners)
• Lots of quizzes (keeps you going)
• Start, stop, pause, rewind and forward whenever you want
• No deadlines - learn at your very own pace

Even though I didn't learn a lot of new technical things in this class, since I'm Python programmer who developed a few web crawlers already, I learnt a lot about myself and I want to encourage everybody to sign up at Udacity and give it a try.
You won't regret it.