HighlightJS

Showing posts with label functional. Show all posts
Showing posts with label functional. Show all posts

Wednesday, April 18, 2012

Playing the game as if you meant it

"Acting has to do with saying it as if you meant it, so for me the words are always very important. It's very important for me to know my lines, know them so well that I don't have to think about them." - Christopher Walken

A few weeks back, I did the Game of Life kata in Ruby. After the first two times, I got bored of implementing eql? and hash methods for the Location class I ended up with. So, the third time, I tried to make it more interesting by doing the exercise in a 'TDD as if you meant it' style. I'd been very intrigued by the idea ever since I read about it, but hadn't really tried it myself. Here's a quick recap of the rules:
  1. write exactly ONE failing test
  2. make the test from (1) pass by first writing implementation code IN THE TEST
  3. create a new implementation method/function by:
    1. doing extract method on implementation code created as per (2), or
    2. moving implementation code as per (2) into an existing implementation method 
  4. only ever create new methods IN THE TEST CLASS
  5. only ever create implementation classes to provide a destination for extracting a method created as per (4).
  6. populate implementation classes by doing move method from a test class into them
  7. refactor as required
  8. go to (1)
I've published my code, and tried to make it so that following the commits from the first to the last should give one a good idea of almost every step I followed. The rest of this post is a walk through the micro-process of TDD as if you meant it (TAIYMI) as I applied it to the Game of Life. So, here we go...

The first five commits are quite unremarkable, except that, in accordance with rules 1-4 above, all the implementation code is in the rspec "test class".


describe "In the next gen, a grid with" do
  [[], [[0,0]], [[0,0], [0,1]]].each do |cells|
    context "#{cells.size} live cells" do
      it "should have no live cells" do
        g = cells
        ng = next_gen(g)
        ng.should == []
      end
    end
  end

  def next_gen(grid)
    []
  end
end
At this stage, I have tests for grids with 0, 1 and 2 cells, all of which become empty (of any live cells) in the next generation. The next step, where I write a test for 3 live cells in a diagonal, is where it starts to become interesting.


context "3 live cells in a diagonal" do
  it "should have only the middle cell alive" do
    g = [[0,0],
                [1,1],
                       [2,2]]
    ng = next_gen(g)
    pending "calculation of neighbors"
    ng.should == [[1,1]]
  end
end

I need to keep it pending "calculation of neighbors". Traditionally, at this point, I think I might've stubbed a call to calculate neighbors of a Cell/Location to make this test pass, and later gone on to test-drive the calculation of neighbors. But the "rules of the game" prohibit me from doing so. So, I'll calculate neighbors first.

The test for "neighbors of origin" looks quite silly, but I don't know how else to write it "as if I meant it".


describe "a location's neighbors" do
  it "should be all locations offset by a single row and/or column" do
    location = [0,0]
    neighbors = [[-1,-1], [-1,0], [-1,1],
                 [ 0,-1],         [ 0,1],
                 [ 1,-1], [ 1,0], [ 1,1]]
    neighbors.should =~ [[-1,-1], [-1,0], [-1,1],
                         [ 0,-1],         [ 0,1],
                         [ 1,-1], [ 1,0], [ 1,1]]
  end
end

I probably already have something in mind about how my next test will look. But first, I extract neighbors_of(location) and the test doesn't look that silly anymore, while laying the ground for the next test, which is to find the neighbors of location [1,2].


describe "neighbors of location" do
  it "[0,0] should be [-1,-1], [-1,0], [-1,1], [ 0,-1], [ 0,1], [ 1,-1], [ 1,0], [ 1,1] in any order" do
    location = [0,0]
    neighbors_of(location).should =~ [[-1,-1], [-1,0], [-1,1],
                                      [ 0,-1],         [ 0,1],
                                      [ 1,-1], [ 1,0], [ 1,1]]
  end

  it "[1,2] should be [0,1], [0,2], [0,3], [1,1], [1,3], [2,1], [2,2], [2,3] in any order" do
    location = [1,2]
    neighbors = neighbors_of(location).map { |loc| [loc[0] + location[0], loc[1] + location[1]] }
    neighbors.should =~ [[0,1], [0,2], [0,3],
                         [1,1],        [1,3],
                         [2,1], [2,2], [2,3]]
  end

  def neighbors_of(location)
    [[-1,-1], [-1,0], [-1,1],
     [ 0,-1],         [ 0,1],
     [ 1,-1], [ 1,0], [ 1,1]]
  end
end

The one thing I don't like about the two neighbors_of tests now, is that the tests don't read it "should ..." anymore. And worse, the "it" declarations duplicate the programmatic assertions. That's one thing I dislike often about rspec tests which include expected data (rather than a statement about the expected state) in the it declaration. In cases like this, I don't know how to avoid that (and I'd love to hear suggestions).

With the ability to find neighbors_of(location), I can now go and finish that pending test for 3 live cells. I make it pass by writing code in the test method first, and then extracting it into a method, so that I end up with next_gen(grid).


context "3 live cells in a diagonal" do
  it "should have only the middle cell alive" do
    g = [[0,0],
                [1,1],
                       [2,2]]
    ng = next_gen(g)
    ng.should == [[1,1]]
  end
end

def next_gen(grid)
  grid.select { |location| neighbors_of(location).select { |neighbor| grid.include?(neighbor) }.count == 2 }
end

Extracting the alive? method next pushes me for the first time towards rules 5 and 6 (to create implementation classes as destination for moving a method).


def next_gen(grid)
  @grid = grid
  @grid.select { |location| live_neighbors_of(location).count == 2 }
end

def live_neighbors_of(location)
  neighbors_of(location).select { |neighbor| alive?(neighbor) }
end

def alive?(location)
  @grid.include?(location)
end

I now have an instance variable, indicating the need for an object that can hold it. In preparation for a move method, I convert grid from an instance variable to a method parameter (aside: I think the variable grid should've been called live_locations in the first place).


def next_gen(grid)
  grid.select { |location| live_neighbors_of(location, grid).count == 2 }
end

def live_neighbors_of(location, grid)
  neighbors_of(location).select { |neighbor| alive?(neighbor, grid) }
end

def alive?(location, grid)
  grid.include?(location)
end

Creation of the Grid class with the next_gen method next isn't quite an atomic refactoring, but I think it's simple enough that I can spare myself the tedium of writing each individual step.


class Grid
  attr_reader :live_locations

  def initialize(live_locations)
    @live_locations = live_locations 
  end

  def next_gen
    live_locations.select { |location| live_neighbors_of(location).count == 2 }
  end

  def live_neighbors_of(location)
    neighbors_of(location).select { |neighbor| alive?(neighbor) }
  end

  def alive?(location)
    live_locations.include?(location)
  end
end

That's followed by another test (and, of course, implementation and refactoring) for live cells with 3 live neighbors. That takes care of all the rules relating to live cells. Handling the dead cells is easily done. I'm pleasantly surprised that I can still make the test pass by writing the implementation code in the test method first.


context "3 live cells in a row" do
  it "should have instead 3 live cells in a column, with the middle cell unchanged" do
    g = [[0,0], [0,1], [0,2]]
    grid = Grid.new(g)
    ng = grid.next_gen + g.flat_map { |location| neighbors_of(location) }.select { |location| grid.live_neighbors_of(location).count == 3 }.uniq
    ng.should =~ [[-1,1], [0,1], [1,1]]
  end
end

After moving the flat_map into next_gen and a little bit of refactoring, we're done implementing all the rules of the game (of life) following the rules of the game (of TAIYMI). With tests to keep me in check, I can now go wild with refactoring. And I do, and come up with the following:


class Grid
  attr_reader :live_cells

  def initialize(live_cells)
    @live_cells = live_cells.uniq
  end

  def next_gen
    surviving(live_cells) + vivifying(dead(neighbors_of_all(live_cells)))
  end

  def neighbors_of_all(cells)
    cells.flat_map { |cell| neighbors_of(cell) }.uniq
  end

  def vivifying(cells)
    cells.select { |cell| vivifying?(cell) }
  end

  def vivifying?(cell)
    live(neighbors_of(cell)).count == 3 
  end

  def dead(cells)
    cells.reject { |cell| alive?(cell) }
  end

  def surviving(cells)
    cells.select { |cell| surviving?(cell) }
  end

  def surviving?(cell)
    [2, 3].include?(live(neighbors_of(cell)).count)
  end

  def live(cells)
    cells.select { |cell| alive?(cell) }
  end

  def alive?(cell)
    live_cells.include?(cell)
  end
end

Note that in the next_gen method, I don't really need to pass around live_cells as a method parameter, since it's there in the instance state for any method to grab. But I choose to pass it, simply because


surviving(live_cells) + vivifying(dead(neighbors_of_all(live_cells)))

is a much more explicit and complete formulation of the solution than, say

surviving + vivifying(dead(neighbors_of_all))

The latter is terser, but the former, even with its superfluousness, is more succinct.

Note that I've now replaced all uses of 'location' with 'cell', because the distinction I had to maintain in my earlier OO solution between them (a cell has a location and is either alive or dead, while a location is simply the coordinate of a cell) is no longer necessary to maintain. Usage of 'cell' enables the framing of the entire solution in terms of terms coming straight from the domain language.

Just for good measure, I throw in another pair of tests for live and dead cells with 4 live neighbors, respectively. But now, I don't like how the spec declaration for those two tests read. Here's the rspec output documentation for the grid:
In the next gen, a grid with
  0 live cells
    should have no live cells
  1 live cells
    should have no live cells
  2 live cells
    should have no live cells
  3 live cells in a diagonal
    should have only the middle cell alive
  4 live cells in a square block
    should remain unchanged
  3 live cells in a row
    should have instead 3 live cells in a column, with the middle cell unchanged
  5 live cells forming a +
    should have instead 8 live cells forming a hollow square
  8 live cells forming a hollow square
    should have instead 8 live cells forming a diamond
Those last two tests don't quite serve as documentation, I'm afraid, because they make neither the initial nor the expected state obvious. While that's true to some extent even for the other tests, I don't terribly mind the slight mental computation they require. Also, the special way in which I've been laying out the arrays to visually represent the grid has the potential to be misleading, in that the coordinate values don't have to match up with their visual placement. But (hint, hint), suggestions for improvement anywhere in my solution, approach, or process are highly welcome.

In conclusion, though, a comparison of my earlier solution - with its classes for Cell, Location and Grid - to this one seems to support the observation that classes developed like this tend to have very little or no state, coming much closer to the functional programming paradigm.

Sunday, November 14, 2010

Maybe foreach is the new if

"Maybe . . . Maybe not. But at least it would be something real." - Nikita, in La Femme Nikita

Last weekend, I spent some time translating Nat Pryce's implementation of a Maybe type for Java to C#. You can find the motivation behind, and an introduction to, the construct in his blog post. He also suggests some better ways of avoiding nulls, BTW. But I'll stick to Maybe for now, and jump directly to some questions, observations and thoughts that arose from a discussion I had with my colleague, Victor, about the type and its usage.

First came the question of how to introduce such a construct into an already long-running project. My answer would be: piecemeal. You simply use it in new code you write, or code you refactor or otherwise modify in the normal course of work. You don't have to touch code you wouldn't have otherwise touched. So, there'll be some methods that declare they may return a nonexistent value (through the use of Maybe), and some others that'll hand you a null without bothering to set expectations. But having even a few methods that'll declare the possibility of nonexistence is better than having none, since you have that many fewer surprises to deal with.

Next, there were some questions about the how code using the type would look. So, here's an if-else structure using a null value:


@Test
public void ifThen() throws Exception {
    Maybe foo = "foo";

    if (foo != null) {
        assertThat(foo, equalTo("foo"));
    }
    else {
        fail("should not have been called");
    }
}

Here's the same structure using a Maybe:


@Test
public void ifThen() throws Exception {
    Maybe foo = definitely("foo");

    if (foo.isKnown()) for (String s : foo) {
        assertThat(s, equalTo("foo"));
    }
    else {
        fail("should not have been called");
    }
}

They look quite similar, but the Maybe example is interesting for two reasons. The first is the use of the Iterable interface (through the for loop) for accessing the 'wrapped' value. It may feel itchy to use a for loop to access what you know is a single value, but we'll address that soon. The second is the clever placement of the for statement on the same line as the if, effectively de-emphasizing the iteration aspect, and making the overall structure look no(t much) different from a regular if-else structure. Too bad, none of the automatic code formatters I've used is clever enough to see the cleverness of the formatting and retain it.

Getting back to the itchiness of the for loop for accessing the single value. After the discussion with Victor, I felt as uncomfortable with the single-element-iteration as he did. Even though it hadn't bothered me at all earlier, it now bothered me enough that I had to find an alternative. Since we were talking about my C# version of Maybe, on my way home, it struck me that one could use the .First() LINQ extension method like this:


if (foo.IsKnown())
{
    Assert.That(foo.First(), Is.EqualTo("foo"))
}

instead of:


if (foo.IsKnown()) foreach (s in foo)
{
   Assert.That(s, Is.EqualTo("foo")
}

In case of an unknown value, .First() would throw an exception. Just what you'd expect. So, that's a solution if you don't like the for loop. As an aside, the if check in the last foreach example is redundant. It's needed only if it's to be followed by an else clause. Maybe foreach is the new if.

What's so wrong with the for loop, though? I realized the reason the iteration felt awkward to me is because I knew there'll never be more than one value. Isn't an iteration really meant for multiple values? Somehow, despite the fact that Maybe implements Iterable, I expected it to hide that fact from me. I assumed the iterability is more or less a hack to be exploited by collections APIs (Guava for Java, LINQ for .net). But reflecting further, these assumptions and expectations seemed to be based on a fuzzy feeling about the form of an iterable, not on a published contract, or even some kinda logic, for that matter.

For methods that return a collection of objects, an empty collection is an acceptable - I'd even say, the only acceptable - return value (some people return a null... ouch!). Returning an empty collection as a NullObject in such cases allows one to avoid the clutter of the SentinelPattern. The iterable/collection interface allows client code to treat all return values - whether with zero, one or many elements - uniformly. So, if a collection with zero or many is fine, a collection with zero or one should be just as fine. Which is exactly what the Maybe type is - an iterable that promises to yield exactly either zero or one element. But instead of being ashamed of being an iterable, it's proud of being one with a stronger guarantee.

BTW, Maybe would definitely() be a worthy type addition to the Babbage language, next to its MIGHT DO and WHY NOT? statements.