TDD & Functional Testing: from collections to scalars
I’ve been fiddling around with top-down (mock-style) TDD of functional programs off-and-on for a few months. I’ve gotten obsessed with deferring the choice of data structures as long as possible. That seems appropriate in a functional language, where we should be talking about functions more than data. (And especially appropriate in Clojure, my language of choice, since Clojure lets you treat maps/dictionaries as if they were functions from keys to values.)
That is, I like to write these kinds of tests:
(example-of "saturating a terrain"
(saturated? (... terrain ...)) => true
(because
(span-between-markers (... terrain ...)) => (... sub-span ...)
(saturated? (... sub-span ...)) => true
)
… instead of committing to what a terrain or sub-span look like. That’s been working reasonably well for me.
I’ve also been saying that “maps are getters”. By that, I mean that—given that you’ve test-driven raise-position—it really makes no more sense to test-drive this:
(defn raise [terrain] (map raise-position terrain))
… than it does to test a getter: it’s too obvious. That leads to a nice flow of testing: I’m always testing the transformation of things to other things. I don’t have to worry, until the very end of test-driving, that the “things” are actually complex data.
The problem I’ve been running into recently, though, is handling cases where complex data structures are converted into single values. For example, I’ve been trying to show a top-down TDD of Conway’s Life. In that case, I have to reduce a set of facts about the neighborhood of a cell into a single yes-or-no decision: should that cell be alive or dead in the next iteration? But expressing that fact is rather awkward when you don’t want to say precisely what a “cell” is or how you know it’s “alive” or “dead” (other than that there’s some function from a cell and its environment to a boolean).
To be concrete, here’s something I want to claim: a cell is alive in the next iteration if (1) it is alive now and (2) exactly two of the cells in its neighborhood are alive. How do you say that while being not-specific? I’ve not found a way that makes me happy.
Part of the problem, I think, is that when you start talking about individual elements of collections, you’re moving from the Land of TDD, which is a land of functions-of-constants to a Land of Quantified Variables (like “there exists an element of the collection such that…”). That way lies madness.
April 18th, 2010 at 10:14 pm
BTW, when logging in to comments without having a user name, it does not allow you to register. Work-around is to forget password, then register link shows up.
Conway’s Life is nothing more than cellular automata. Don’t get hung-up on neighbors and alive/dead. Think of it as a function that has a state-table that not only uses its own internal state and states from other inputs. Each new state will take the entire state and select specific indexes into the state-table.
This way you can have the state-table based on more than binary state and more than just nearest neighbors.
Also, this is dangerous territory it can lead you down to studying NK Boolean networks.
April 19th, 2010 at 1:59 pm
This was an exercise in trying out different styles of coding as a way of generating ideas. Getting a good implementation of Life wasn’t the goal.
April 19th, 2010 at 3:50 pm
I don’t really get the final paragraph of your blog post. If you can think of a way to elaborate on it, I could use the help. Thanks.
April 19th, 2010 at 9:04 pm
I believe I get what your saying TDDing being about designing for behavior, not designing for collections. Maybe you would describe what your trying to get to is a ‘hold off to the last possible responsible (concrete) moment’. Similar to never testing against database or presentation. So you you could say, never TDD for concrete objects, but TDD for abstract behavior.
The one thing that I noticed when working with a functional language you end up wanting to design a language that abstracts away the actual underlying concrete data.
April 20th, 2010 at 10:07 am
Tracy: Suppose I have a cell and its neighborhood and I want to test the Life rule that a living cell stays living if it has two living neighbors. If I were using concrete data, I could just say something like:
The neighborhood is ({0,0}:living {0,1}:living {0,2}:dead {1,0}:dead {1,2):dead)
But I don’t. So I found myself wanting to say:
There exists a cell X in the neighborhood for which living(X) => truthy
There exists a cell Y in the neighborhood for which living(Y) => truthy
For any cell Z in the neighborhood that’s not X or Y, living(Z) => falsey
Translating statements like that into executable mocks is not, I think, a profitable approach to take.
I came up with a better structure for the flow of testing in the shower yesterday, then forgot it. It’ll come back to me.
April 20th, 2010 at 10:21 am
Thank you, Brian. This really closes in on the most interesting difficulty I’ve had with testing.
At the point where we can write a wholly generalized test, such as you described, how does this differ from having written the program itself? What occurs when we go from a statement (”The function is f”) to a question (”Is it so that the function is f?”). In writing the latter, the former appears as an included clause.
This seems closely related to the way “x is the case” or “x is true” has the same meaning as “x”.
April 22nd, 2010 at 10:15 pm
Your choice of example has led me to keep thinking about a simpler variation of Conway’s Life, which I find easy to work with for its familiarity. (My blog post http://bit.ly/9sNybV discusses the whole program.)
The thing you found yourself wanting to say, but deciding not to mock, seems parallel to the English statement I made describing the heart of this cellular automaton.
Here’s that English statement:
“The cell in question lives in the next generation if the total across the three cells equals two.”
Here’s the corresponding code:
(3(2=+/\)])
The English can be read as either prescription (a program) or description (a test). If I seek to write a test at this level of abstraction, it seems natural to include, in that unit of testing, code that expresses the relationship. The code I posted above does just that. But this is the very same code we’d be wanting to test! It can’t serve as a test of functionality if the generalization it contains is the same generalization as the unit of functionality.
Does what I wrote here fit what you had in mind when you decided to not mock at a high level of abstraction when writing in a functional style?
April 23rd, 2010 at 8:51 am
Hi Brian,
can’t you just postulate that there is “sum-of-living-neighbor” function on cells? You can mock that function and describe what happens when the sum is 0, 1, … 8. That will also open the door for separating the survival rule in two parts: “how I compute neighborhood” and “what happens as a function on neighborhood”. (For instance, in Go problems, neighborhood does not include diagonals. As another example, you might want to define Life over an hex grid.)