Exploration Through Example

Introduction

This is a draft. Worth continuing the series? Let me know.

Critter4Us is a webapp used to schedule teaching animals at the University of Illinois Vet School. Its original version was a Ruby/Sinatra application with a Cappuccino front end. Cappuccino lets you write desktop-like webapps using a framework modeled after Apple’s Cocoa. I chose it for two reasons: it made it easy to test front-end code headlessly (which was harder back then than it is now), and it let me reuse my RubyCocoa experience.

Earlier this year, I decided it was time for another bout of experimentation. I decided to switch from Cappuccino to jQuery, Coffeescript, Haml because I thought they were technologies I should know and because they’d force me to develop a new TDD workflow. I’d never gotten comfortable with the testing—or for that matter, any of the design—of “traditional” front-end webapp code and the parts of the backend from the controller layer up.

I now think I’ve reached a plateau at which I’m temporarily comfortable, so this is a good time to report. Other people might find the approach and the tooling useful. And other people might explain places where my inexperience has led me astray.
(more…)

While waiting for my product owner to get back to me, I was going through open browser tabs. I read this from Swizec Teller:

The problem is one of turning a list of values, say, [A, B, C, D] into a list of pairs with itself, like so [[A,B], [A,C], [A,D], [B, C], [B,D], [C,D]].

He had problems coming up with a good solution. “I can do that!” I said, launched a Clojure REPL, and started typing the whole function out. I quickly got bogged down.

This, I think, is a problem with a common functional approach. Even with this kind of problem—the sort of list manipulation that functional programming lives for—there’s a temptation to build a single function bottom up. “I need to create the tails of the sequence,” I thought, “because I know roughly how I’ll use them.”

For me (and let’s not get into all that again), it usually works better to go top down, mainly because it lets me think of discrete, meaningful functions, give them names, and write facts about how they relate to one another. So that’s what I did.

First, what am I trying to do? Not create all the pairs, but only ones in which an element is combined with another element further down the list. Like this:

As I often do when doing list-manipulation problems, I lay things out to visually emphasize the “shape” of the solution. That helps me see more clearly what has to be done to create that solution. There’s one set of pairs, each headed by the first element of the list, then another set, each headed by the second element. That is, I can say the above fact is true provided two other facts are true:

It’s easy to see how I get the heads—just map down the list (maybe I have to worry about the last element, maybe not—I’ll worry about it if it comes up). What are those heads combined with? Just the successive tails of the original list: [2 3], [3]. I’ll assume there’s a function that does that for me. That gives me this entire fact-about-the-world-of-this-program:

Given all that, downward-pairs is easy enough to write:

It’s important to me that I have reached a stable point here. When building up a complicated function from snippets in a REPL, I more often create the wrong snippets than when I define what those snippets need to do via a function that uses them. (I’m not saying that I never backtrack: I might find a subfunction too hard to write, or I may have carved up the world in a way that leads to gross inefficiency, etc. I’m saying that I seem to end up with correct answers faster this way.)

Now I just have to solve two simpler problems. Tails I’ve done before, and here’s a solution I like:

For those who don’t know Clojure well, this produces this sequence of calls to drop:

This does roughly the same work as an iteration would do because of how laziness is implemented.

That leaves me headed-pairs, which is a pretty straightforward map:

This seems like a reasonable solution, doesn’t strike me as being terribly inefficient (given laziness), has a readability that I like, doubtless took me less time than developing it bottom-up would have, and comes with tests (including an end-to-end test that I won’t bother showing).

The whole solution is here.

UPDATE: Yes, I could have used do or even gotten explicit with the sequence-m monad, but that wouldn’t have addressed the original poster’s point, which I took to be how to think about functional problems.

After around 11 months of not working on it, I needed to make a change to Critter4us, an app I wrote for the University of Illinois vet school. The change was simple. When I tried to push it to Heroku, though, I discovered that my Ruby gems were too out of date. So, I ended up upgrading from Ruby 1.8 to 1.9, to Sinatra 1.3 from a Sinatra less than 1.0, to a modern version of Rack, etc. etc. In essence, I replaced all the turtles upon which my code-world was resting. There were some backwards-compatibility problems.

One incompatibility was that I was sending an incorrectly formatted URI to fetch some JSON data. The old version of Rack accepted it, but the new one rejected it. The easy fix was to split what had been a single `timeslice` parameter up into multiple parameters. [Update: I later did something more sensible, but it doesn’t affect the point of this post.] “Crap!”, I thought. “I’m going to have to convert who knows how much test data.” But I was pleased when I looked at the first test and saw this:

The key point here is that neither the format of the URI parameters nor the resulting timeslice object is given in its real form. Instead, they’re represented by strings that basically name their type. (In my Clojure testing framework, Midje, I refer to these things as “metaconstants“.)

The only responsibility this code has toward timeslices is to pass them to another object. That object, the `internalizer`, has the responsibility for understanding formats. The test (and code) change is trivial:

The test is even (and appropriately) less specific than before. It says only that the GET parameters (a hash) will contain some key/value pairs of use to the internalizer. It’s up to the internalizer to know which those are and do the right thing.

The point here is that the size of the test change is in keeping with the size of the code change. It is unaffected by the nature of the change to the data—which is as it should be.

This application is the one where I finally made the important decision to use mocks heavily in the Freeman and Pryce “London” style and—most importantly—to not fall into the trap of thinking “Mocks are stupid!” when I ran into problems. Instead, I said “I’m stupid!” and, working on that assumption, figured out what I was doing wrong.

I made that decision halfway through writing the app. One of the happy results of the mocking that followed was that a vast amount of test setup code devoted to constructing complete data structures went away. No more “fixtures” or “object mothers” or “test factories.”

I’ve recorded a 43-minute screencast. It’s a decent example of my current style of TDD for Clojure. It emphasizes:

• The use of Midje prerequisites (mocks) to support top-down development.

• Using metaconstants to make tests more abstract and readable.

There are two sources for the video:

• Vimeo: http://www.vimeo.com/19404746
• Download: https://github.com/marick/Midje-videos/raw/master/robozzle.mov (If that fails with “blob too big”, go here and select Downloads:

  

  You’ll get a zip file containing the video in its own directory.

UPDATE

Alert watcher Mark Derricutt notices that I got east and west mixed up. I, um, I… I did that deliberately (no, really!) to illustrate an important point about TDD. TDD helps you do what you intended. It is not particularly good at helping you intend the right thing. Indeed, the flow experience it can induce probably makes you worse at noticing you’re proceeding smoothly in the wrong direction.

For example, I had a niggling feeling throughout that I was getting the orientation wrong. That, plus general principle, made me shy away from just copying the answers from the tests into the rotation maps—instead, I recreated them. All for naught: the incorrect mental image I used when I calculated the first left turn had captured my mind.

This getting stuck in a rut is one of the reasons why you still need testing with a fresh mind (either someone else’s or your own, after a rest).

It’s interesting to speculate whether this bug would ever become visible. If, just after finishing the kata, I’d wired up a UI and chosen four ship images, I’d probably again get east and west flipped, meaning all would look well to the user. It’d be like using y as the variable representing horizontal position and x for vertical position: functionally correct if you do it consistently, but death to any sane mind reading the code.

If I chose ship images later, I’d be more likely to get them right (that is, wrong given the bug). I do at times know east from west.

I’ve created a mailing list for Midje, my Clojure TDD framework.

Here’s a simplified example of a Ruby test:

  def test_queuing
    during {
      @sut.sendMail(:ignored_sender)
    }.behold! {
      @mailPayload.receives(:attachment_path) { “attachment path” }
      @allContacts.receives(:selectedContact) { “contact” }
      listeners_receive_notification_with_info(News::QueueOutgoingAttachment,
                                               :source_path => “attachment path”,
                                               :recipient => “contact”)
      listeners_receive_notification(News::CheckOutboxQueue)
    }
  end

I find this annoying. It obscures what the test is about because the “definition” of the attachment path is far away from its use. If you were using your native tongue to describe what’s happening, you would not say:

First, let’s say that there’s a thing called “the attachment path”. You get it by asking the Mail Payload for its attachment path. There’s also a “contact”. It’s the contact selected in the list of All Contacts.

When the “send mail” button is clicked, a notification is generated. Its “source path” is the attachment path and the “recipient” is the contact.

(Well, you might if you were so completely corrupted by years of mathematics training that its definition-theorem-proof style seems natural.) If I were listening to you, I’d prefer to hear something like this:

When the “send mail” button is clicked, a notification is generated. (Key fact comes first.) Its “source path” is the Mail Payload’s attachment path and the “recipient” is the contact currently selected in All Contacts. (Definitions and uses in the same place.)

In code, that’d look more like this:

  def test_queuing
    during {
      @sut.sendMail(:ignored_sender)
    }.behold! {
      listeners_receive_notification_with_info(News::QueueOutgoingAttachment,
                                               :source_path => @mailPayload.attachment_path,
                                               :recipient => @allContacts.selectedContact)
      listeners_receive_notification(News::CheckOutboxQueue)
    }
  end

That emphasizes an important fact: that I don’t really care what the attachment path or selected contact are, because whatever they produce gets stuffed into the recipient. Indeed, the real selected contact isn’t anything like a string. In the first example, I can use “contact” to represent it because the code treats it as any-old opaque object, and a string is easy for me to type. (It’d probably be better to use symbols for this, I just now realize, because they’re less likely to be taken to be an example of the actual object.)

In OO Land, you could make an argument that my annoyance is a sign I’m Doing It Wrong: I’ve given responsibilities to the wrong objects. I think that’s certainly so in some cases, though (probably) not this one.

But the same thing happens in Functional Land, where the responsibility argument is harder to make because dumb objects are more natural. Here’s an example that uses my Midje TDD library for Clojure:

(fact "unless overridden, each procedure can be used with each animal"
  (all-procedures-no-exclusions) => { ...procedure-name... [] }
  (provided
    (procedures) => [ …procedure… ]
    (procedure-names […procedure… ]) => [ …procedure-name…]))

This is a little terser, but I have the same pattern of two expectation-statements to express one idea — in this case, the idea that the program wants to reach out and grab a list of all the names of all the procedures.

I’m thinking of allowing this kind of fact in Midje:

(fact "unless overridden, each procedure can be used with each animal"
  (all-procedures-no-exclusions) => { ...procedure-name... [] }
  (provided
    (procedure-names (procedures)) => [ … procedure-name … ]))

You’d get an expectation failure for line 4 if either (1) procedures was never called or (2) procedure-names didn’t use what procedures produced.

Comments? (from residents of either land) Who’s done things like this before? How has it worked out? Gotchas? (Replies might go in the Midje mailing list.)

The devoted reader will recall that I earlier sketched a “little language” for mocking Clojure functions. I’ve finished implementing a usable–perhaps even pleasant–subset of it. I invite you to take a look. In keeping with my whole “work with ease” thing, I’ve made it dirt simple to try it out: one click and two shell commands. You don’t even have to have Clojure installed.

Part 1
Part 2

All that remains is to add the locations of bordering cells to a given sequence of locations. A small wrinkle is that a border location may be next to more than one of the input locations, so duplicates need to be prevented. I could write the test this way:

I don’t like that. When the test fails, it’ll likely be hard to discover how the expected and actual values differ. And I bet that a failure would more likely be due to a typo in the expected value than to an actual bug. The test is just awkward.

I like this version better:

It is a clearer statement of the relationship between two concepts: a location’s neighborhood and the border of a set of locations. More pragmatically, it’s less typing. (When I first started coding in this style, it surprised me how much test setup clutter went away. I had much less need for “factories” or “fixtures” or “object mothers“.)

Given either test, the code is straightforward:

Onward

No matter how satisfying the individually-tested pieces, the whole has to work, which is why everything ends by running at least one end-to-end test. A test like the one we started with:

Because I’m making up my test notation as I go, I’ve been running all the tests manually in the REPL. Now I can run the whole file:

If you look carefully, you’ll see that the test would fail because the locations are in the wrong order. But that’s a quick fix:

Done. Ship it!

Development order - Test-down or REPL-up?

It’s often said that the Lisps are bottom-up languages, that you test out expressions in the REPL, discover good functions, and compose them into programs. A lot of people do work that way. A lot of people who use TDD to write object-oriented code also work that way: when implementing a new feature, they start at low-level objects, add whatever new code the top-level feature seems to demand of them, then use those augmented objects in the testing of next-higher-level objects.

For I guess about a year now, I’ve been experimenting with being strictly top-down in some projects. I find that leads to less churn. Too often, when I go bottom-up, I end up discovering that those low-level changes are not in fact what the feature needs, so I have to revisit and redo what I did.

I get less disrupted by rework when I go from the top down (or from user interface in). It’s not that I don’t blunder—we saw one of those in the previous installment—but those blunders seem easier to recover from.

That’s not to say that I don’t use the REPL. We saw that a little bit in this program, when I was writing neighbors. It’s perfectly sensible to do even more in the REPL. I think of the REPL as a handy tool for what XP calls a spike solution and the Pragmatic Programmers call tracer bullets. When I’m uncertain what to do next, the REPL is a tool to let me try out possibilities. So I might be stuck in a certain function and go to the REPL to see how it feels to build up parts of what might lie under it. After I’m more confident, I can continue on with the original function, test-driven, reusing REPL snippets when they seem useful.

I don’t claim everyone should work that way. I do claim it’s a valid style that you’d be wise to try.

Notation

I’m something of an obsessive about test notation, and I’ve been endlessly fiddling with a Clojure mock notation. I implemented its first version as a facade on top of clojure.contrib.mock. As I experimented, though, I found that keeping my facade up to date with my notational variants slowed me down too much, so I put the code aside until the notation settled down.

I’m pretty happy with what you’ve seen here. Are you? If so, I may start on another mock package. I’ve got the most important parts: a name and sketch of a logo. (”Midje” and someone flying safely between the sun [of abstraction without examples] and the sea [of overwhelming detail].)

Tests and code together

You can see the completed program here. It mixes up tests and code. I’ve tried that on-and-off over the years and always reverted to separate test files. This time, it’s seemed to work better. I probably want an Emacs keystroke that lets me hide all tests, though. I’d also want alternate definitions of the test macros so that I can compile them out of the production system

What next?

I’ll write a web app in this style, using Compojure.

Part 1
Part 3

I ended Part 1 saying that my next step would be to implement a function that counts the number of living neighbors a cell has. Given that we’re already pretending (through stubbing) that a living? function exists, living-neighbor-count is pretty trivial if we also pretend we’ve got a neighbors function:

Following my “mapping, like accessors, is too simple to test” guideline, I almost didn’t write a test. But what the heck:

Once the test passes, we need to write neighbors. To implement it, we’re going to have to take cells apart (to get x and y coordinates) and put them back together (to create neighbors). So I don’t see any point to using stubs and dummy variables like ...cell... in this test:

Boldly, I will here use one test to define both cell-at and neighbors (as well as the test helper have-coordinates that checks a list of cells against a list of coordinates).

(If I were more sensitive to that small voice in my head that warns I’m going astray, I would have heard something around now, but I ignored it. So we will too.)

Enter the REPL

The concrete representation of the cell — and disaster

When I wrote that, I remember that the still small voice of conscience objected to the way I was both stashing the bordered-world away as background and simultaneously picking it apart with map. That just felt weird, but I argued myself into thinking it was harmless. It was not.

Really, since my whole program takes input [x y] pairs (such as *vertical-blinker*) and turns them into a different set of [x y] pairs, most of my work ought to be done with those pairs. I should be thinking about locations of cells, not cells themselves. In that way of thinking, border shouldn’t produce “cells”. It should take locations of living cells and produce locations that point to both living cells and adjacent dead cells.

Further, I shouldn’t repeat those locations in a world function. Instead, I need something that can answer questions about cells, given their locations. It should be a… (I’m bad with names)… an oracle about cells. I first imagined this:

using-cell-oracles-from should produce any wise and oracular functions we need. So far, that’s just living?.

I realized something more. Locations are flowing into the pipeline, locations are flowing out, and in this version, locations won’t be transformed into cells anywhere within the pipeline. That makes unborder, which was originally supposed to convert a mixture of living and dead cells into only living locations, seem kind of stupid. If tick produces only living locations, unborder can go away. (The name unborder always bugged me, because it didn’t really describe what the function would have to do. Once again, I should have paid attention.)

That leads to this top-level function:

That wasn’t so bad…

As it turns out, changing my mind about such a fundamental decision was easy.

What did I have to do to the code? I had to write using-cell-oracles-from. Here’s a test.

I won’t show the code that passes this test—it’s a somewhat grotty macro (but a simple transformation of the earlier against-background). You can see it in the complete source for this post.

I did a quick global-replace of “cell” with “location” and tweaked a couple of the resulting names. Although both you and I know that locations are just pairs, I retained the functions make-location (formerly cell-at), x, and y to keep the code insulated from the potential of another change of mind.

I had to convert the successor function to dead-in-next-generation?. That was pretty simple. I had to change two lines in the test. Here’s one:

To make that test pass, I had to rewrite successor. It used to be this:

Now it’s this:

That was just a matter of inverting the logic and deleting killed and vivified. (Before I ever got around to writing them!)

The ease of this change makes me happy. Even though I blundered at the very beginning of my design, the way stub-heavy TDD lets me defer decisions—and forces me to encapsulate them so that I have something to stub—made the blunder a not-catastrophe. I wish I could say that I blundered deliberately to demonstrate that property of this style of TDD, but that would be a lie.

Enough for today

Only one function remains: add-border-to. That’ll be pretty easy, but this post is already too long. The next one will finish up the implementation and add whatever grand summary I can come up with.

Part 2

I continue to use little experiments to help me think through TDD in Clojure. (I plan to begin a realistic experiment soon.) Right now, I’m mainly focused on three questions:

• What would mocking or stubbing mean in a strict(ish) functional language?

• What’d be a good mocking notation for Clojure?

• How do you balance the outside-in style associated with mocks and the bottom-up style that the REPL (interpreter) encourages?

Here’s an example from Conway’s Game of Life. It begins with an implementation suggestion from Paul Blair and Michael Nicholaides at the Philly Code Retreat. Instead of thinking of the board as a 2×2 array of cells, with some of them dead and some alive, think instead only of living cells, each of which knows its coordinates. Here’s an example that shows how “blinkers” blink from generation to generation.

A couple of things have happened here:

• This is my notation for a straightforward non-stubbing test. The value on the left is executed and it’s compared (for equality) to the value on the right.

• I’ve started coding outside-in, and I’ve named the first function I need: next-world.

The Blair/Nicholaides approach advances the “world” to the next generation by (conceptually) adding dead cells around the edge of all the living cells, running the normal life rules that govern how cells change because of their neighbors, and then throwing away all the cells that end up dead. In other words:

• The pending bit is just there because (sadly) Clojure makes you declare functions before mentioning them. pending just creates functions that print that they’ve not yet been implemented.

• The rest of the code flows the world argument through a pipeline of three functions. If you’re not familiar with the -> macro, the result is the same as this:

  I don’t feel the need to test this code now because it’s really declarative—it says what it means to produce a next world under this approach. (It will be tested in the very end by the “integration test” that shows a blinker working.)

I can now implement any of the three new functions. I’ll pick tick because it seems to be the heart of the matter. Here’s a first implementation:

There are two odd things going on here.

• I think of the Clojure programs I’ve written this way: there’s a big stateful universe out there. At some moment, a snapshot of relevant bits of that universe is presented to my pure functional program. It churns away, presents the results back to the big stateful universe, and then disappears. Given that bias, I find it convenient to think of the universe-bits not as data to be passed around, but as the unchanging background behind my code’s calculations. Any of that code should be able to reach out and grab bits of the relevant background by calling dynamically bound functions of no arguments.

  Because of against-background, any code operating inside successor (or inside functions it calls) can call (world) and magically get the original bordered-world. As you’ll see, this lets me put off committing to a representation for cells. (The representation I used for the blinkers isn’t enough after the border’s been added, since there’s now a need to distinguish between living and dead cells.)

• This essay is supposed to be a sketch of TDD in Clojure, but here’s the second function I’ve written without tests. What’s up with that? I’ve tentatively concluded that testing functions that map one function over a sequence is the moral equivalent of testing getters and setters: not worth the trouble. But don’t fear, successor is worth testing, and we’ll do that next. Almost next.

In object-oriented languages, I think of mock-driven-design as a way of teasing out collaborators for the object I’m building. I push responsibilities for work onto objects that I’ll implement later. Mocking lets me defer the implementation of those objects until I’m ready, and creating some examples of the API teaches me the (implicit) specification for the new object.

I’ve found that with pure functional programs that don’t modify state, it makes more sense to think of a function like (f 2) => 4 as a fact. What I’m doing as I test-drive a function is describing how facts about its inputs and outputs depend on other facts, in an almost Prolog-like way. For example, consider this code:

That says that, for any cell you care to provide, f of that cell will be 10, provided g of that cell is true and h is 2. If either of those latter two facts don’t apply to the cell, I’m not saying what f’s value is.

I use the funny ...cell... notation in the way that mathematicians use n to talk about any integer. (They call that universal quantification.) I don’t want to create a particular cell because I might need to specify properties that have nothing to do with the function I’m working on. This notation says that nothing about the cell is relevant except for what comes after the provided.

Here’s one way to write a Life rule in this notation:

The falsey bit in the first line is because Clojure has two distinct values that can mean “false”. falsey is a function that takes the result of the left-hand side and fails the test if that result is anything other than one of the two false values. I’m using it because I don’t want to overspecify living?. There’s no reason to care which of the two “false” values it returns.

There’s a problem with this test, though. Remember what I said above: the left-hand side gets evaluated and handed to falsey. That means living? has to have a definition—which means I’d have to settle on how the code knows whether a cell is alive or dead. I like doing one thing at a time and putting off decisions as long as I can, and right now I’d rather be focused on successor instead of cell representations.

Here’s a way to defer that decision:

Here I’m saying something subtly different than before. I’m saying that the result of successor is specifically that cell produced by calling killed on the original cell. The =means=> notation tells the framework to create a mock instead of evaluating the right-hand side for its value. In a more familiar mocking syntax (for Ruby), the whole test is equivalent to:

OK. The next figure gives the whole set of Life rules, expressed as executable tests. (Well, executable as soon as I implement the testing framework.) Notice that I called the outer wrapper know (a fact) instead of example. know seems more appropriate for rules. The two forms mean the same thing.

Notice also that I implemented a notation for saying “run this test for each value in a sequence”. The use of commas, as in [4,,,8], indicates that—conceptually—the fact is true for all values four through eight. Only the ones listed are actually tried. (Commas count as >white space in Clojure.)

This isn’t the tersest possible format—a table would be better—but it’ll do. I think it’s reasonably readable. Do you?

Here, for reference, is code that passes the test:

We now have an expanded choice of functions to write:

I could go breadth-first—with border and unborder—or go depth-first with one of the functions on the second line. In this particular case, I’d rather go depth first. I’ve avoided deciding on a representation, so I don’t know yet what border should do.

If this installment meets your approval, I’ll add another one that begins work on—oh—probably living-neighbor-count is the most complicated, so it’s a good one to chip away at.