OO vs. functional: the Game of Life

During my adventures with the Game of Life implementation, I tried and carried to completion both approaches, functional and OO. What follows is my findings, considering I only chose two possible points of the solution space, and that OOP or functional masters may find simpler or more flexible solutions.

Disclaimer

When I solved the problem in the OO way, I was trying it out OO for the first time: I have a minor knowledge of the problem, being familiar with the rules but not with the data structures needed to make it work.

The functional solutions also came out after ruminating over the problem all day in a code retreat, so it is possible that my unconscious thoughts may have crafted it for me (you know, that a-ha moment when you invent a new algorithm under the shower or while starting your car in the morning.)

I'm not considering the time needed to implement visualization while comparing the different solutions: displaying a fixed window over the infinite plane is the fastet visualization for both cases, and it's orthogonal to the implementation.

Note that I'm an OO guy who preaches about interfaces, not Paul Graham, so I'm not keen on pointing out how cool functional programming is.

Object-oriented

Simulations are one of the best metaphors for OO programming, and this time we are implementing a real simulation of Game of Life's evolution.
Here are some notes on the design I developed:

• Game and Generation were the classes to start from, with the latter being an immutable object that can generate the next Generation.
• Generation has many Cell(x, y) Value Objects, but only stores the ones which are alive in that discrete moment.
• Internally, Cell objects are stored inside a CellSet, an object that can offer some algebraic operations on the Cells, such as the union or intersection of sets.

Note how many functional concepts we are using: sets, immutable objects, union and other operations over cells and cells "lists" (or sequences). The real breakthrough is in the data structure for this problem, not in the collaborations between objects, since there are no variations to the rules.

The code for this solution is on GitHub: it asks each Generation to compute the next one. The Generation considers the union set of all alive cells and of their 8-cell neighborhoods, and applies to them the rules to generate the new set of alive cells. Each not considered cells remain dead, but cells may also become dead because of the rules.

Functional

The generational approach strikes me as object-oriented: we have a current state of the system as a set of objects, and we ask it to evolve up to a point in the future, with discrete messages that mark the passing of time. Every state where a snapshot is not taken will be lost, and Game will contain the most recent state. During the evolution, Game could send out events of which cells become alive or dead.

My functional solution instead exposes a single closure: game(x, y, t). The boolean value of this closure is the dead or alive state of Cell(x, y) in the plane at time t.

Of course the closure needs a seed for initialization; to build it, you need to specify the values for game(x, y, 0), but again just for the alive cells as the dead are an infinite set and can be considered such when missing from the alive set.

The closure is recursive, and applies the rules over the values of game(x+-1, y+-1, t-1) and game(x, y, t-1). We actually implemented it as an object because of the easier syntax for recursion and initialization with a constructor, but it could really be a single closure if you use the Y combinator.

I'm not sure of what monads are, but I ensure you they're not involved in this solution :). The code has been deleted as it was a rule of the Code Retreat, but it can be written down with acceptance TDD in 20 minutes.

This solution strikes me as functional with respect to the OOP one: there is no notion of time passing, but instead there is a mathematical model that describes the whole plane at any point in infinite time. There is the potential for the memoization (automated caching of the results) in a smart-enough language, since the closure does not have side effects. We are actually building an infinite data structure that is unbounded on 3 sides (dimensions and time), but we are only computing the part of it that is of interest for the current problem.

Findings

Is this problem more aligned with a functional approach? I guess so, if only because we arrived at the end result in much less time, even discounting the new knowledge of the problem. It will always be really less work to use a recursive function than an evolving simulation over Cell objects.
Note that I always said a functional approach over a functional language: a PHP immutable object acted as a perfect closure. The solution it's still functional because of the API, and its openness of data structure versus the encapsulation of all Cell objects, its recursion preference, and its mathematical model.

That said, functional languages have better support for functional approaches; in this particular case, for caching the result of game(x, y, 0); or for lazy evaluation, making no difference from the invocation of a function and its result, which is really the concept behind this solution.

Note however that there are no non-functional requirements expressed in the problem. For example, the functional approach is quadratic even when caching the results of game(x, y, t) (which is badly necessary for getting it to run efficiently, at least in imperative languages.) The OO one is very efficient, only storing alive cells and calculating a minimum set of cells at each round; but if you're producing gliders or other moving patterns, you will calculate them forever even when they're out of the current screen scope.

Let's not even start with variation to the rules (maintainability): the functional solution is probably more open to considering different neighborhoods and numbers of alive cells, while the OO one to more complex evolution processes, like intermediate steps between one generation and the next.

Conclusions

We can try to align the approach we use with the problem, even when being stuck in a single language which is imperative. Most imperative languages support closures and functional constructs by now.
However, alignment consists not only of development speed but also of non-functional requirements, like performance, security, maintainability. How many of your colleagues are functional programmers that will be able to evolve that code? How fast will be the algorithm implementation?