Writing Game of Life in Elm

Introduction

In this article, we will walk through the steps for writing an implementation of Conway's Game of Life in the Elm programming language.

In doing so, we will learn about the basic principles involved with writing programs in Elm, while grounding them in a concrete problem. We will be building a single program in steps, so much of the source will be repeated between the examples, but it will be more clear to present each step in its entirety.

I first became interested in Elm after seeing Evan Czaplicki's talk from mloc.js 2013, where he presented an overview of Elm and the compelling example of how one would write a simple side-scroller in an extremely straight forward fashion as a consequence of the core concept in Elm: signals.

Elm is a functional reactive programming language, a paradigm concerned with using an explicit model of time. Elm uses signals as its abstraction of time-varying values, including various time functions (e.g. every second), constants (e.g. constant True), which are invariant over time, and user input (e.g. Mouse.clicks). These, and other, signals can be combined and manipulated in various ways to achieve vastly complex results, clearly and concisely. It is this expressive power of Elm that I find especially interesting. The overview of FRP on the Elm site is excellent resource for these core concepts.

For this reason, I chose Elm to explore Conway's Game of Life. Having seen that Life can be written concisely, to an almost absurd degree, in APL, it seems to me to be a very interesting problem by which to compare different languages. I have only dabbled with Elm in the past, writing a toy for LD 28, but have always wanted to spend some more time getting to know the language.

Without further ado, let us begin writing Conway's Game of Life.

First Steps

We will begin by writing a very simple static grid, the foundation for our game. I often begin writing Elm programs with all my signals planned out, interacting in complex ways, since that seems the more interesting part of the problem, as compared with some boringly simple display components. The fact of the matter is, however, that, lacking in experience with static typing and the concepts of signals, I often find myself in a mess and have to back out.

I, in fact, did that with this program. Several times. I believe I come to understand the core concepts much more, but the fact remains: start with a solid base and build on top of it. This first example will simply a grid of a predetermined size. It has support for cells being turned on and off, but they are all on to begin with.

static_grid.elm

Source
import List

import Color (rgb)
import Graphics.Element (Element, flow, right, down, container, topLeft, spacer, color)

cellSize = 5
(columns, rows) = (35, 35)

main : Element
main = renderGrid generateGrid

generateGrid : List (List Bool)
generateGrid = List.repeat rows (List.repeat columns True)

renderGrid : List (List Bool) -> Element
renderGrid grid =
  grid
    |> List.map renderRow
    |> List.map (flow right)
    |> flow down
    |> container (cellSize * columns) (cellSize * rows) topLeft

renderRow : List Bool -> List Element
renderRow row = List.map renderCell row

renderCell : Bool -> Element
renderCell on =
  spacer cellSize cellSize
    |> color (if on then (rgb 0 0 0) else (rgb 255 255 255))
Result

The crux of this program is that we want to turn a nested list of boolean values (List (List Bool)) into an Element, one of two possible types for the main function in an Elm program. We use the Element API to achieve this in a few steps.

This first example is, beyond those points, only really interesting syntactically. It should feel somewhat familiar to anyone who has worked with other functional languages. One point worth mentioning is the forward function application helper (|>). This helps clarify the program (at least to my eye), when a value passes through a number of functions sequentially. The following are equivalent: (c (b a)) and a |> b |> c.

Seeding the Grid

The next step is to take the grid we created in the first example and seed it with randomly generated examples. In Elm, the Random component has three functions, all of which are a Signal. This means that, we can no longer be concerned with simply taking one value and mutating it into another, but instead, with taking a signal and converting it into another signal. The main function can also be of the type Signal Element, which, in a sense, becomes the goal of our program - we have an input of type Signal (List Int) we will be taking from Random.list, and we want to convert it into a Signal Element that Elm can consume.

Herein lies a core concept - that of maping a signal. The map function has the type (a -> b) -> Signal a -> Signal b; it takes a function from type a to type b and a signal of type a and returns a signal of type b. This function is the primay means by which signals are converted from one type to another.

As a consequence of the way lift works, by taking a function to convert a signal, rewriting our static example to one that is randomly generated involves very few steps. These are as follows:

  1. Change the type of main from Element to Signal Element.
  2. Write an initialSeed function of type Siganl Random.Seed
  3. Write a seededGrid function of type Random.Seed -> List (List Bool)
  4. Change generateGrid from List (List Bool) to List Int -> List (List Bool)
  5. map our seededGrid function through our existing renderGrid function.

random_grid.elm

Source
import Signal ((<~), Signal)
import Signal

import List ((::))
import List

import Time
import Random

import Color (rgb)
import Graphics.Element (Element, flow, right, down, container, topLeft, spacer, color)

cellSize = 5
(columns, rows) = (35, 35)

main : Signal Element
main = renderGrid <~ (seededGrid <~ initialSeed)

initialSeed : Signal Random.Seed
initialSeed = (\(time, _) -> Random.initialSeed (round time)) <~ Time.timestamp (Signal.constant ())

seededGrid : Random.Seed -> List (List Bool)
seededGrid seed =
  let (lst, _) = Random.generate (Random.list (columns * rows) (Random.int 0 1)) seed
  in generateGrid lst

generateGrid : List Int -> List (List Bool)
generateGrid seeds = List.map generateRow (groupInto rows seeds)

generateRow : List Int -> List Bool
generateRow seeds = List.map (\n -> n == 1) seeds

renderGrid : List (List Bool) -> Element
renderGrid grid =
  grid
    |> List.map renderRow
    |> List.map (flow right)
    |> flow down
    |> container (cellSize * columns) (cellSize * rows) topLeft

renderRow : List Bool -> List Element
renderRow row = List.map renderCell row

renderCell : Bool -> Element
renderCell on =
  spacer cellSize cellSize
    |> color (if on then (rgb 0 0 0) else (rgb 255 255 255))

groupInto : Int -> List a -> List (List a)
groupInto groups initial =
  let
    len = List.length initial
    n = len // groups
  in
    List.repeat groups []
      |> List.indexedMap (\i _ ->
          List.take n (List.drop (n * i) initial))
Result

We do write two other helper functions, generateRow and groupInto, but neither change is essential for the example. In fact, the rendering we wrote before, the helpers, and now the basic seeding never needs to change again.

These core input and output signals will remain constant, but we will have to add some additional transitions in order to make life evolve.

Adding Generations

This final piece of the puzzle is to make the grid evolve from one generation to the next. Elm makes this exceptionally easy with its concept of past dependent signals. The function foldp, of type (a -> b -> b) -> b -> Signal a -> Signal b takes a function of two values, a default value for the output signal, and an input signal. The function takes two arguments: the current value of the input signal, and the past value (or the default on the first event).

We can use this construct to take our initialSeed of Signal (List (List Bool)) and step it from generation to generation. This is, again, a comparatively simple process, consisting primarily of the following steps:

  1. Update the main function to make use of foldp.
  2. Create a step function of type List (List Bool) -> List (List Bool) -> List (List Bool).
  3. Create an evolve function of type List (List Bool) -> List (List Bool).

game_of_life.elm

Source
import Signal ((<~), Signal)
import Signal

import List ((::))
import List

import Time
import Random

import Color (rgb)
import Graphics.Element (Element, flow, right, down, container, topLeft, spacer, color)

cellSize = 5
(columns, rows) = (35, 35)

main : Signal Element
main =
  Signal.sampleOn (Time.every Time.second) (seededGrid <~ initialSeed)
    |> Signal.foldp (step) [[]]
    |> Signal.map renderGrid

step : List (List Bool) -> List (List Bool) -> List (List Bool)
step current past = if (List.isEmpty (List.head past)) then current else (evolve past)

initialSeed : Signal Random.Seed
initialSeed = (\(time, _) -> Random.initialSeed (round time)) <~ Time.timestamp (Signal.constant ())

seededGrid : Random.Seed -> List (List Bool)
seededGrid seed =
  let (lst, _) = Random.generate (Random.list (columns * rows) (Random.int 0 1)) seed
  in generateGrid lst

generateGrid : List Int -> List (List Bool)
generateGrid seeds = List.map generateRow (groupInto rows seeds)

generateRow : List Int -> List Bool
generateRow seeds = List.map (\n -> n == 1) seeds

evolve : List (List Bool) -> List (List Bool)
evolve generation =
  List.indexedMap (\y row ->
    List.indexedMap (\x _ ->
      descend generation x y) row) generation

descend : List (List Bool) -> Int -> Int -> Bool
descend grid x y =
  List.concatMap (\n -> List.map (\m -> (x + n, y + m))
                   [-1, 0, 1]) [-1, 0, 1]
    |> List.filter (\p -> (fst p) > -1 && (fst p) < columns &&
                          (snd p) > -1 && (snd p) < rows &&
                          (not ((fst p) == x && (snd p) == y)))
    |> List.filter (\p -> (itemAt (fst p)
                            (itemAt (snd p) grid)) == True)
    |> List.length
    |> (\l -> ((itemAt x (itemAt y grid))
                && l > 1 && l < 4) || l == 3)

renderGrid : List (List Bool) -> Element
renderGrid grid =
  grid
    |> List.map renderRow
    |> List.map (flow right)
    |> flow down
    |> container (cellSize * columns) (cellSize * rows) topLeft

renderRow : List Bool -> List Element
renderRow row = List.map renderCell row

renderCell : Bool -> Element
renderCell on =
  spacer cellSize cellSize
    |> color (if on then (rgb 0 0 0) else (rgb 255 255 255))

itemAt : Int -> List a -> a
itemAt i lst = List.head (List.drop i lst)

groupInto : Int -> List a -> List (List a)
groupInto groups initial =
  let
    len = List.length initial
    n = len // groups
  in
    List.repeat groups []
      |> List.indexedMap (\i _ ->
          List.take n (List.drop (n * i) initial))
Result

The only real nuance here is that we must sampleOn seed (every second), which updates the signal with the constant initial value. We use an empty default to determine whether we should return the value from the seed, or whether we should evlove the past value.

We use an indexedMap for the evolve function, because we will need to have the index of the cell available when calling the descend function. Aside from these points, it is simply gathering all the neighboring cells, filtering invalid ones, counting live neighbors, and mapping to a new boolean value.

Conclusion and Futher Steps

Elm is a wonderful and extremely expressive language, and my experiences with it have been overwhelmingly positive. I think it is excellent for these types of applications, and its core concepts are very solid. While neophytes may struggle with the type system - I know I have had my share of problems - this can be solved through experience. The community, moreover, is both knowledgeable and willing to help. When I had a question, Evan responded almost immediately and Jeff Smits elucidated my misconceptions.

In terms of this example, I think it is clear so long as the core concepts are in place. It may be longer than the APL example, but I did also err on the side of clarity over brevity. I have a feeling this could be condensed considerably were that the goal of the exercise.

As such, the most interesting way to proceed with this start would be to add interactive elements. Allowing a user to control things like cell size and count, duration of a generation, to flip individuals cells, to pause the game. The list could probaby go on and on, and combining signals from many different inputs is one of the strengths of Elm. I intend on revisiting this example and improving upon it in the near future, so wach out for that update.

(This post was updated for Elm 0.14 on 13 Dec 2014)

Lazy Ruby

Lazy Evaluation and Recursive Lists

In Haskell, it is possible to construct infinite lists via recursive definition. This is only possible because Haskell uses lazy evaluation rather than eager evaluation. Otherwise, the entire list would need to be calculated and the program would never terminate.

Because Haskell makes it easy to define lists and is lazy, the code for defining an infinite series is very simple. The following list represents the fibonacci sequence.

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

The list is defined recursively; the first two values are one, and every subsequent value is the sum of zipping the entire list with the tail of the list, evaluating to the sum of the two previous number for any position beyond the second. Pulling numbers off the list is as easy as the following.

> take 10 fibs
[1,1,2,3,5,8,13,21,34,55]

I was originally exposed to this concept while reading the book Programming Languages: Application and Interpretation which provides a more thorough introduction to the topic of lazy evaluation.

Spurious Examples and Limitations in Ruby

Ruby 2 introduced lazy evaluation to its Enumarable module, accessible via #lazy. The method returns a new instance of a lazy enumerator.

We can use these additions to create the same sort of infinite lists that are possible in Haskell. First, we start by generating a simple infinite series, upon which we can build further abstractions.

> inf = (1..Float::INFINITY).lazy
=> #<Enumerator::Lazy: 1..Infinity>

Now we have an enumerator, upon which we can build additional abstractions. In fact, you can represent any countable set using abstractions on this enumerator.

Unfortunately, Enumerator::Lazy#zip is limited, such that it is not possible to pass it a block without eager evaluation being triggered. This is easy, albeit inelegent, to circumvent by #maping subsequent to a #zip call. For instance, to get the sum of all adjacent numbers, the following never completes.

> adjacents = inf.zip(inf.drop(1)) { |a, b| a + b }

But by simply interposing a #map, it becomes possible.

> adjacents = inf.zip(inf.drop(1)).map { |a, b| a + b }
=> #<Enumerator::Lazy: #<Enumerator::Lazy: #<Enumerator::Lazy: 1..Infinity>:zip(#<Enumerator::Lazy: #<Enumerator::Lazy: 1..Infinity>:drop(1)>)>:map>

> adjacents.take(10).force
=> [3, 5, 7, 9, 11, 13, 15, 17, 19, 21]

Note that it is necessary to forece the evaluation, otherwise Ruby continues to return lazy enumerators to allow chaining.

Fibonacci in Lazy Ruby

We now have all the pieces we need to replicate the Haskell example. Ruby allows us to define a new infinite enumerator based on the original one, but lacks expressiveness for a few of the features Haskell as. As such, we need to map the infinite series onto another one using a block, which is analogous to defining a new infinite series, but does not read as cleanly.

Regardless of how well it reads, functionally, the following example accomplishes the same as the Haskell version.

> fibs = inf.map do |n|
    if n < 3
      1
    else
      fibs.zip(fibs.drop(1)).map { |a, b| a + b }.first(n - 2).last
    end
  end
=> #<Enumerator::Lazy: #<Enumerator::Lazy: 1..Infinity>:map>

> fibs.take(10).force
=> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Fast & Lazy Fibonacci

This implementation is, unsurprisingly, painfully slow since it needs to reevaluate every single preceeding term in order to calculate a given term. This is a canonical issue with the naive recursive definition of fibonacci number calculations.

My original exposure to the following approach manipulates the fibonacci function by using a fixed point and a general memoization strategy based on the y combinator. For this particular example, a simple caching strategy will do, but it is worth knowing about the more general solution.

> fibs = -> {
    cache = []

    inf.map do |n|
      if cache[n]
        cache[n]
      elsif n < 3
        1
      else
        cache[n] = fibs.zip(fibs.drop(1)).
                        map { |a, b| a + b }.
                        first(n - 2).
                        last
      end
    end
  }.call

This allows us to calculate much higher values of the fibonacci sequence in a reasonable amount of time. Retrieving the 200th number happens instantly.

> fibs.take(200).force.last
=> 280571172992510140037611932413038677189525

Of course, this is not particularly idiomatic Ruby, since it uses a closure to bind the cache variable. It would be possible to rewrite this as a class (and I had, admittedly, originally done so), but the resulting code is over twice as long and amounts to a great deal of boilerplate and little else.

The way I see it, as long as we are abusing Ruby for its lazy evaluation, we may as well abuse it functionally as well.

Hooks in AngularJS Controllers

The Situation

Sometimes when working with nested scopes, you may encounter a situation in which some scope action depends on the status of some arbitarily nested controller. This could be a multi-part form built from reusable components, preventing the user from proceeding until complete, for example.

An architecture that allows scopes nested within another scope to influence the life cycle of the latter has one primary advantage, namely, greater separation of concerns. A nested controller can supply functions for data validation and formatting, while the parent controller defines functions for navigation and accumulation of results. This leads to better modularity, as the parent controller is isolated from the implementation of nested controllers, while the latter are able to be used modularly in more contexts.

A Simple Example

Open in Plunkr

As the structure of the following example indicates, we have three controllers - one that coordinates and two that handle user input. We have taken the liberty of using underscore to simplify checking if all conditions are met.

Here, the FormCheckboxCtrl has no validation, but does coerce its results to be human readible, while FormTextInputCtrl returns the text input and is invalid if none is provided.

What remains is, simply, to make it work.

<body ng-app="HookExample">
  <div ng-controller="FormPageCtrl">
    <p>Please enter some text below.</p>

    <span ng-controller="FormCheckboxCtrl">
      <input type="checkbox" ng-model="checkbox" />
    </span>

    <span ng-controller="FormTextInputCtrl">
      <input type="text" ng-model="textInput" />
    </span>

    <div ng-show="showResults()"></div>
  </div>
</body>
var HookExample = angular.module("HookExample", []);

HookExample.controller("FormPageCtrl", function($scope, RegisterHook) {
  $scope.showResults = function() {
    return RegisterHook("isDataValid", $scope, _.every);
  };

  $scope.results = function() {
    return RegisterHook("getResults", $scope, function(results) {
      return results.join(" - ");
    });
  };
});

HookExample.controller("FormTextInputCtrl", function($scope) {
  $scope.isDataValid = function() {
    return $scope.textInput && $scope.textInput !== "";
  };

  $scope.getResults = function() {
    return $scope.textInput;
  };
});

HookExample.controller("FormCheckboxCtrl", function($scope) {
  $scope.getResults = function() {
    return $scope.checkbox ? "Yes" : "No";
  };
});

A Hook Implementation

By recursively traversing the $$childHead and $$nextSibling properties of the scope, we can give ask if any controller nested within the heirarchy wishes to respond to the hook, thereby influincing the life cycle of our parent controller.

HookExample.factory("RegisterHook", function() {
  return function(name, scope, callback) {
    var results = [];

    (function traverse(scope) {
      if (!scope) {
        return;
      }

      if (_.(scope, name)) {
        results.push(scope[name]());
      }

      traverse(scope.$$childHead);
      traverse(scope.$$nextSibling);
    })(scope.$$childHead);

    return callback(results);
  }
});

This simple implemnation will look for and call the name function on any scope, starting from the $$childHead of the scope passed in. Once all the results have been accumulated, the callback is called with those results, allowing for a nice functional interface, as in the case of passing in _.every.

Since the callback is required in this naive implementation, it would be possible to pass in angular.noop as the callback to discard the results, thereby issuing some call to arbitrarily nested controllers. In that case, however, a more reasonable approach would be to $broadcast an event.

Hooks vs. Events vs. Services

When is this approach of registering hooks more appropriate than using events? Primarily when you need to get the data back from the user via collaborating controllers. The way event broadcasting requires an event to the child controllers, each of which must call another event for the parent controller to handle quickly becomes brittle. In cases where the data is not transient, it is likely best to use a service object to store all the data and have the collaborators reference it directly.

That said, there is certainly still a place for hooks like the one outlined above, but it is necessary to use it in appropriate situations. Littering our code with hooks that would be best treated as services for their persistence or events for their unidirectionality will not be an improvement.

But in cases where data transience and bidirectional collaboration between controllers at different levels of nesting is present, hooks reign supreme by exposing carefully selected points of interaction.

Improvements

Herein, we have only examined a very simple hooking mechanism, which can certainly be built out to have some additional interesting properties. Optional callbacks and the ability to handle arguments would be straight forward changes. More interesting is the possiblity to return more than just a single function for accumulating results, but instead having a more robust interface. This could include functionality akin to that in ActiveRecord callbacks, wherein returning false prevents future hooks from running and prevents some default action.