Extreme Enthusiasm

We have some files containing sequences of integers, one number per line. We want to compute the sum of the numbers. The catch is that the numbers are written as roman numerals.

This code works, but there is a problem: every time we run the tests, a nasty error message appears on standard error. We’d like to be able to turn off the error message when we run the tests. The error message should still appear when the code is run in production.

Your job: make it so that the error message does not appear when the tests are run.

See here the starting code. Copy it in a file pesky.rb and run it with the commmand ruby pesky.rb.

class RomanNumeral
  def initialize(string)
    @value = string
  end

  def to_i
    case @value
    when "I"; 1
    when "II"; 2
    when "III"; 3
    when "IV"; 4
    else
      STDERR.puts("Invalid numeral '#{@value}'")
      0
    end
  end
end

class RomanSequence
  def initialize(input)
    @input = input
  end

  def sum
    result = 0
    @input.lines.each do |line|
      roman = RomanNumeral.new(line.chomp)
      result += roman.to_i
    end
    return result
  end  
end

require "minitest/autorun"
require "stringio"

class RomanSequenceTest < MiniTest::Unit::TestCase
  def test_adds_roman_numerals
    input = StringIO.new("I\nII\nIII\n")
    assert_equal 6, RomanSequence.new(input).sum
  end

  def test_skips_invalid_numerals
    input = StringIO.new("I\nY\nIII\n")
    assert_equal 4, RomanSequence.new(input).sum
  end  
end

PLEASE

Solve the exercise before continuing.

(more…)

Most papers in computer science describe how their author learned what someone else already knew. — Peter Landin

And blog posts too. — Matteo

This is a follow-up to my previous post.

In his Responsive Design presentation, Kent Beck talks about the Stepping Stone strategy. He talks about two kinds of stepping stones: one is about building abstractions that might make your work easier.

The first kind of Stepping Stone

He talks about the abstractions that allow Google people to perform their magic, like BigTable which is built upon Google File System, which is built upon a Distributed Lock Manager. I can relate with this view of “design”. It’s powerful. I like this quote from Daniel Jackson

Part of what allowed thousands of engineers to build scalable systems at Google is that really smart engineers like Jeff Dean and Sanjay Ghemawat built simple but versatile abstractions like MapReduce, SSTable, protocol buffers, and the like. Part of what allowed Facebook engineering to scale up is the focus on similarly core abstractions like Thrift, Scribe, and Hive. And part of what allows designers to build products effectively at Quora is that Webnode and Livenode are fairly easy to understand and build on top of.

Keeping core abstractions simple and general reduces the need for custom solutions and increases the team’s familiarity and expertise with the common abstractions. The growing popularity and reliability of systems like Memcached, Redis, MongoDB, etc. have reduced the need to build custom storage and caching systems. Funneling the team’s focus onto a small number of core abstractions rather than fragmenting it over many ad-hoc solutions means that common libraries get more robust, monitoring gets more intelligent, performance characteristics get better understood, and tests get more comprehensive. All of this helps contribute to a simpler system with reduced operational burden.

The interesting thing about this strategy is that it’s the one that you *don’t* do when you TDD. Kent Beck is saying, in effect, “you can do plenty of work with TDD, but sometimes it’s beneficial to stop doing TDD, and try instead to guess that you will need some intermediate or related thing. Then you build that something, and the original problem that you had might be much easier to solve.”

Let’s have an example, shall we? The Sudoku Solver, for instance. What Stepping Stones could be useful? From Artificial Intelligence classes taken long ago, and from Peter Norvig’s excellent article on the subject, I know that two ways to solve a Sudoku are depth-first search and constraint propagation. If I wanted to try depth-first search, my Stepping Stone would be the depth-first search algorithm itself.

Aside. What is depth-first search? Depth-first search means that you model your problem as a search through the space of possible moves. Given any position you’re in, you try the first possible move, which brings you in a new position.

1. If the new position is a winning position, you’re done.
2. If the new position is not a winning one, you make the first possible move from here, and repeat.
3. If there are no possible moves in the new position, then you back-track to the previous one, and try the second possible move.

This algorithm is very simple. It works for a huge variety of problems; all you need is that you can enumerate moves from any position. It does not always find a solution; for instance, on some problems it can enter an infinite loop. But this can’t happen with Sudoku, so depth-first is an excellent algorithm to try with Sudoku.

The depth-first algorithm is easy to test-drive. Once I have this algorithm, the original problem “solve Sudoku” is reduced to “from any given Sudoku board, enumerate possible moves”, which is much simpler.

Not only the problem is made simpler; it’s also easier to check that I implemented it correctly.

What about the second way to solve Sudoku, that is constraint propagation? This brings us to the next section.

The second kind of Stepping Stone

The other kind of Stepping Stone that Kent Beck mentions in the video is related to the old Lisp maxim

Q. How do you solve a difficult problem?
A. You implement a language in which the problem is trivial to solve.

This is the opposite of the Simplification strategy. Sometimes, the easiest way to solve a problem is to generalize it. Let’s make an example. The Http access log report problem from my last post would be easy to solve with SQL. Assuming that the access log lines are in a database table, I could do

select date,
  sum(if(status >= 200 and status < 300, 1, 0)) as 2xx-results,
  sum(if(status >= 300 and status < 400, 1, 0)) as 3xx-results,
  sum(if(status >= 400 and status < 500, 1, 0)) as 4xx-results,
  sum(if(status >= 500 and status < 600, 1, 0)) as 5xx-results,
from access_log
group by date

How’s that for simplicity? But why couldn’t I write a similar program in Ruby? I would start by imagining what the solution would look like:

Report.new(access_log).
  group_by(:date).
  select(:date).
  sum(:2xx_results) {|x| (200...300) === x.status ? 1 : 0 }.
  sum(:3xx_results) {|x| (300...400) === x.status ? 1 : 0 }.
  sum(:4xx_results) {|x| (400...500) === x.status ? 1 : 0 }.
  sum(:5xx_results) {|x| (500...600) === x.status ? 1 : 0 }  

Then I could implement the various needed features of Report one by one. That would give me a nice list of small, safe steps to implement.

It seems a paradox that solving a more general problem may be easier, but we can see from this example how this can be true. Another example is in my post Feeling like carrying bags of sand.

Getting back to the Sudoku solver, a possible Stepping Stone of the second variety could be to implement a simple constraint propagation system. If you’re interested, there is a nice discussion in Structure and Interpretation of Computer Programs.

Conclusion

Stepping Stone is an antidote to the tendency to carry YAGNI too far, to the point that we refuse to write anything that is even slightly more general than what is exactly required. We’re not violating YAGNI when it’s simpler to write a Domain-Specific Language than trying to solve a complicated problem directly.

XP warns against premature abstraction. Let’s leave aside for the moment the observation that generalization is not the same thing as abstraction. It is true that by creating abstractions you run the risk of creating things that turn out not to be needed. Kent Beck warns against this in the video. Yet, I believe Stepping Stones are a very important dimension to design, one that is not used when we do TDD and that should be considered whenever we have a difficult programming problem.

Further reading

The idea of “layers of abstractions” is (I believe) due to Edsger Dijkstra. See his paper The Structure of the “THE”-Multiprogramming System. It’s interesting to compare how his idea of powerful abstractions differs from the weaker concept of “layers” in business applications.

I finally got round to watching Kent Beck’s video on Responsive Design. It’s a very interesting video, for me. I mean, it’s very interesting from the point of view of someone who has been doing test-driven development for years, and who for years has watched people work with TDD.

I’d like to comment on an interesting part of this video, the one where he talks about the Four Strategies, which are: Leap, Parallel, Stepping Stone and Simplification. Carlo Pescio says he is unsure about the difference between Stepping Stone and Simplification; but I think I grok what Kent means. I think that Simplification is a crucial strategy that is enabled by TDD; it would be too difficult and expensive to do without tests. On the other hand, if you do TDD, you need to understand Simplification, otherwise your tests will not sing.

So what is the Simplification strategy? Kent says (around 00:58)

I can imagine that I want to get over here, so what is the least I can do that would be progress? Suppose I want a big multi-threaded application, so I think, I can’t do a big multi-threaded application in one step. It’s too big a step, it’s not a safe step. So what am I going to do? Well, there are different possibilities, but the one I do all the time is to say, “Well, which of those am I going to eliminate? Is it going to be a multi-threaded application doing something trivial, or is it going to be a single-threaded application doing something more substantial?” […] I do this *further* than most people that I encounter. Someone says “I want a Sudoku solver and I do a 16 by 16 grid” and I say “Well, how about a 1 by 1 grid?”

I think that the Sudoku example nails it. Let’s see where the “one-cell Sudoku” leads. What would the test look like? I suppose it would be like

def test_solve_one_cell_sudoku
  sudoku = Sudoku.new(1)
  sudoku.solve
  assert_equal "1", sudoku[0,0]
end

Any number would solve the one-cell Sudoku, so I arbitrarily chose “1” as the solution. What would the next test look like? I would write a two-cell Sudoku. Mind you, not a 2-by-2 Sudoku; that would contain four cells! Just a non-square, two cells Sudoku:

def test_solve_two_cells_sudoku
  sudoku = Sudoku.new(1, 2) # one row, two columns
  sudoku.solve
  assert_equal "1", sudoku[0,0]
  assert_equal "2", sudoku[0,1]
end

Again, any two numbers would solve the two-cell Sudoku, as long as they are different. So I arbitrarily chose “1” and “2”.

Now, these arbitrary choices are starting to bug me. If it’s true that any other two distinct numbers would do, why do I over-constrain the test? By forcing “1” and “2” I’m placing an extra constraint that might make things more difficult later. I could make my tests less brittle by specifying exactly what I want:

def test_solve_one_cell_sudoku
  sudoku = Sudoku.new(1)
  sudoku.solve
  assert_is_digit sudoku[0,0]
end

def assert_is_digit(string)
  assert_match /\d/, string
end

and

def test_solve_two_cells_sudoku
  sudoku = Sudoku.new(1, 2) # one row, two columns
  sudoku.solve
  assert_is_digit sudoku[0,0]
  assert_is_digit sudoku[0,1]
  assert_not_equal sudoku[0,0], sudoku[0,1]
end

OK, now the tests are less brittle, but they are also much less clear! I like my tests to by very simple examples of what the production code does. I don’t like it when I have to think about what the tests mean…

Big flash!

I now understand that the indeterminacy of the original tests is in the fact that the solver can choose from an alphabet of symbols that is larger that the Sudoku problem. If I constrain the first test to “choose” its symbol from the alphabet that contains only the “1” symbol, then the indeterminacy disappears.

def test_solve_one_cell_sudoku
  sudoku = Sudoku.new(["1"], 1)
  sudoku.solve
  assert_equal "1", sudoku[0,0]
end

Same for the second test:

def test_solve_two_cells_sudoku
  sudoku = Sudoku.new(["1", "2"], 1, 2)
  sudoku.solve
  assert_equal "1", sudoku[0,0]
  assert_equal "2", sudoku[0,1]
end

So the Simplification strategy led me to discover a concept, the alphabet, that I was previously ignoring. Continuing along this route, I will probably be led to “discover” the concept of constraint, that will be a useful Stepping Stone to solve the whole Sudoku; not to mention that constraints will be useful to solve Sudoku variants as well. On the other hand, if I try to solve the whole 9×9 Sudoku problem from the start, I will probably end up writing procedural crap, just as I previously did :-)

Let me give another example of Simplification: suppose that you have to write a batch command that produces a report out of web access log files. This is not a theoretical example; I had to do that more than once myself, and the team I’m currently coaching had to solve this exact problem. Suppose that the output we want looks like this:

date          2xx-results    3xx-results   4xx-results   5xx-results
29/Jul/2011          1223             23           456            12
01/Aug/2011          1212             24            11           123

As a TDD beginner I would have started with testing an empty report (that is easy to do, but does not teach you much) and then, for a second test, a one line report like this:

date          2xx-results    3xx-results   4xx-results   5xx-results
29/Jul/2011             1              0             0             0

The nasty thing is that this second test contains most of the complexity of the whole problem. It’s too big a step. If I try to solve it in one Leap, it will probably lead to procedural crap. It is better to use the Child Test pattern (from TDD By Example, p. 143). But I don’t have much guidance on how to choose my Child Test. What objects do I need? As a TDD beginner I would often come up with silly objects that would be just procedural crap disguised by objects.

Here is where I would do best to use a Strategy. The Stepping Stone strategy could help: for instance, I could invent a DSL for web access reports. If I did that, then writing my original report would be easy!

Or I could use the Simplification strategy: start with a one-column, one-row report. That would give me the guidance I need to find the next small, safe step. I prepared a kata for this problem; I will probably publish it on github some day.