Conway's Game of Life using Bow and SwiftUI

• by Tomás Ruiz López
• •
• November 18, 2019
• •
• swift• functional programming• bow
• |
• 14 minutes to read.

This article is part of our series on Functional Programming solutions for the Global Day of Coderetreat challenge.

The Global Day of Coderetreat asked participants to solve the Conway’s Game of Life challenge using various languages and toolsets. Today, we’re going to look at how we tackled this using Swift and Functional Programming (FP). In addition, we are using Bow to enhance our FP support and SwiftUI to render the result of the game.

While resolving this challenge, I also wanted to take a look at Comonads. Monads are usually much more popular than their duals, but Comonads have proven very useful for our purposes here. If you are curious about how we’re using them to solve the Game of Life, keep reading!

An intuition behind Comonads

As mentioned above, Comonads are dual to Monads. While the intuition of a Monad is to provide some context of an effect, the intuition behind Comonads is the opposite: they let us run a query over a context to obtain a value. Moreover, they let us explore a space of possibility and analyze them.

If we take a look at the definition of Comonad in Bow, we can see this intuition is easily reflected in its methods:

protocol Comonad: Functor {
  static func extract<A>(_ fa: Kind<Self, A>) -> A
  static func coflatMap<A, B>(_ fa: Kind<Self, A>, _ f: @escaping (Kind<Self, A>) -> B) -> Kind<Self, B>
}

The extract method lets us query the context implementing the Comonad to obtain a value, whereas the coflatMap method lets us explore the space of possible values with a function. Let’s take a look at how we can leverage this.

A grid with a focus

The description of the challenge states that we have cells in an orthogonal 2D grid, where each position represents a cell that can either be alive or dead. We can model this using an array of arrays, all of the same length. However, this won’t let us run a query over this context if we try to implement its Comonad instance, as we won’t know what value we can retrieve. To be able to do so, we can add a focus on a specific position of the grid. Then, we have the following type:

public final class ForFocusedGrid {}
public typealias FocusedGridOf<A> = Kind<ForFocusedGrid, A>

public final class FocusedGrid<A>: FocusedGridOf<A> {
  let focus: (x: Int, y: Int)
  let grid: [[A]]

  // Rest of the implementation
}

Swift does not have native support for Higher-Kinded Types (HKT), but we can get an emulation of this feature thanks to Bow! The first two lines above are the boilerplate we need to write in order to make FocusedGrid a type with HKT support. This is necessary to be able to provide instances for type classes.

Having this type, we can now provide an instance of Comonad. The extract function is pretty straightforward; we just need to return the value pointed by the focus:

public static func extract<A>(_ fa: Kind<ForFocusedGrid, A>) -> A {
  (fa^)[fa^.focus]
}

The coflatMap function is a bit more complex. It has two parameters: an initial FocusedGrid<A> and a function (FocusedGrid<A>) -> B, and it needs to provide a FocusedGrid<B>.

public static func coflatMap<A, B>(_ fa: Kind<ForFocusedGrid, A>,
                                   _ f: @escaping (Kind<ForFocusedGrid, A>) -> B) -> Kind<ForFocusedGrid, B>

If we pay closer attention to the function f, we can see that it provides a single value that makes sense for corresponding with the focus of the grid. Therefore, if we know how to get one item of the resulting FocusedGrid for the focused position, it seems we need a way of having a grid where each position contains the current grid but focused on the position it occupies. That is, we duplicate the structure of the grid, where position (x, y) of the grid contains the original grid, but focused on (x, y), and from there, we can map the function f, to get each value in its right position.

public static func coflatMap<A, B>(_ fa: Kind<ForFocusedGrid, A>,
                                   _ f: @escaping (Kind<ForFocusedGrid, A>) -> B) -> Kind<ForFocusedGrid, B> {
  let grid = fa^.grid.enumerated().map { x in
    x.element.enumerated().map { y in
      FocusedGrid(focus: (x.offset, y.offset),
                  grid: fa^.grid)
    }
  }
  return FocusedGrid(focus: fa^.focus, grid: grid).map(f)
}

These two functions provide our type with an instance of Comonad that will be handy to solve Conway’s Game of Life.

Think local, act global

Let’s focus now on the rules of the problem. The state of a cell in the next generation depends on its own state and the number of alive neighbors it has. Therefore, we can provide a function that focuses only on a single position of the grid and provides us the next state for that position. This makes it very easy to encode the rules of Game of Life:

func conwayStep(_ grid: FocusedGridOf<Int>) -> Int {
  let liveNeighbors = grid^.localSum()
  let cell = grid.extract()

  if cell == 1 {
    return (liveNeighbors >= 2 && liveNeighbors <= 3) ? 1 : 0
  } else {
    return (liveNeighbors == 3) ? 1 : 0
  }
}

Assuming we represent alive cells as number 1 and dead cells as 0, the rules of the game boil down to counting the number of alive neighbors, extracting the focused cell, and returning the next state based on these two values - just as easy!

This lets us think locally to determine the next state of a cell, but what do we need to do to compute the entire grid? Given an initial grid, the next one can be obtained by:

let initialGrid: FocusedGrid<Int> = // ...
let nextGrid = initialGrid.coflatMap(conwayStep)

If we need to obtain further generations, we just need to keep applying coflatMap(conwayStep) to get the next generation.

Testing everything is correct

Now that we have a working implementation let’s see how we can test it. We will use SwiftCheck, a library for Property-based Testing written in Swift. The rules of Conway’s Game of Life are straightforward to encode into properties that test our conwayStep function:

property("An alive cell with two or three alive neighbors remains alive") <- forAll(aliveWith2or3AliveNeighbors()) { grid in
  conwayStep(grid) == 1
}

property("An alive cell with another number of alive neighbors will die") <- forAll(aliveWithOtherAliveNeighbors()) { grid in
  conwayStep(grid) == 0
}

property("A dead cell with exactly three alive neighbors comes back to life") <- forAll(deadWith3AliveNeighbors()) { grid in
  conwayStep(grid) == 1
}

property("A dead cell with another number of neighbors remains dead") <- forAll(deadWithOtherNumberOfAliveNeighbors()) { grid in
  conwayStep(grid) == 0
}

As you can see, the tests are very easy to write; however, the important stuff is in the generators that we provide to the properties to constrain the initial state. As the conwayStep is acting locally on a cell and considering just its immediate orthogonal neighbors, we can create generators of 3x3 grids, focused on the center position with a specific number of alive neighbors. This is achieved with:

func grid(center: Int, withAliveNeighbors n: Int) -> Gen<FocusedGrid<Int>> {
  let alive = Array(repeating: 1, count: n)
  let dead = Array(repeating: 0, count: 8 - n)
  let all = alive + dead

  return Gen.pure(()).map { all.shuffled() }
    .map { array in
      FocusedGrid(focus: (1, 1),
                  grid: toGrid(center: center, neighbors: array)) }
}

func toGrid(center: Int, neighbors x: [Int]) -> [[Int]] {
  [ [x[0], x[1], x[2]],
    [x[3], center, x[4]],
    [x[5], x[6], x[7]] ]
}

This lets us test the function that acts locally on a single cell and its neighbors. For ensuring correctness on the global behavior of the process, we need to test coflatMap is working correctly.

To do this, Bow provides the BowLaws module, which lets us verify that the implementation we have provided for the Comonad instance of FocusedGridis follows the laws that govern all Comonads. Testing this is as easy as:

func testComonadLaws() {
  ComonadLaws<ForFocusedGrid>.check()
}

All these tests pass, so we can guarantee our implementation is correct!

An image is worth a thousand words

Visualizing a grid of numbers is not as cool as drawing proper cells! We can model cells easily with a Swift enum and give it a textual description with an emoji to represent if they are alive or dead:

public enum Cell {
  case alive
  case dead
}

extension Cell: CustomStringConvertible {
  public var description: String {
    switch self {
    case .alive: return "🦠"
    case .dead: return "💀"
    }
  }
}

Then, we can render the grid of cells using SwiftUI:

import SwiftUI

func grid(_ cells: [[Cell]]) -> some View {
  VStack {
    ForEach(cells, id: \.self) { row in
      HStack {
        ForEach(row, id: \.self) { cell in
          Text(cell.description).font(.title)
        }
      }
    }
  }
}

The VStack and HStack components let us pile up views vertically or horizontally, respectively. The ForEach components let us iterate over collections; we use them to iterate over rows, which we stack vertically, and over cells of a row, which we stack horizontally. Finally, the Text component lets us have a visualization of the emoji representation of a cell; we use the .font(.title) modifier to increase its size. This is all you need to render a grid of cells into a user interface, regardless of the environment (iOS, macOS) that you are targeting. For brevity, I am omitting the rest of the implementation of the UI, but the result looks like:

Conclusions

You can take a look at the entire implementation at my Conway’s Game of Life repository. The repo includes material in addition to what we covered here, like a rough version of a Redux-like architecture that plays very nicely with SwiftUI.

The solution explained here has a different approach than the usual OOP-based solution you may usually encounter, and I may dare to say, that it looks even simpler! However, it has an important caveat: memory consumption can be pretty high since we didn’t pay too much attention to that on the coflatMap implementation. We would need to revisit that implementation to avoid a full duplication of the grid, but we will leave that as an exercise for the reader.

We hope you enjoyed this exercise and look forward to seeing your takes on this challenge using Swift, so please, share them with us!

Please check out the following Bow resources. Comments and questions are welcome and encouraged!

• bow-swift.io
• @Bow_Swift on Twitter

The active development of Bow is proudly sponsored by 47 Degrees, a Functional Programming consultancy with a focus on the Scala, Kotlin, Haskell, and Swift Programming languages.