Design top down, Code bottom up

Top-down design means designing from the client application programmer interface (API) down to the code. The API lays out a precise functional specification, which says what the code will do, not how it will do it.

Coding bottom up means coding the lowest-level foundations first, testing them, then continuing to build. Sometimes this requires dropping a thin mock framework top down or at least thinking about it a bit.

This top-down, then bottom-up approach solves two very important problems at once. First, it lets you answer the what-you-want-to-build problem cleanly from a client (the user of the code’s) perspective. Coding bottom up lays down a sold foundation on which to build. But more importantly, it helps you break big scary problems down into approachable pieces.

Documentation and testing go hand in hand

At every stage, it is important to decompose the problem into bits that can be easily described with doc and easily tested. Otherwise, there’s going to be now ay for anyone (including you in the future) to understand why the code is organized the way it is. It’s usually worth paying a small price in efficiency to achieve modularity, but usually it’s a win-win situation where writing the code in meaningful units makes everything much easier to design and test and makes the final design more efficient.

Programmers often complain that testing and doc add time to a project. I’ve found careful application of both can be huge time savers. It’s so much easier to debug a low level function on its own terms if you trust its foundations than it is to tackle a huge end-to-end system that is misbehaving. Especially if that big system is a plate of spaghetti, hairball, or describable by some other analogy of tangling.

Why this came up—testing Stan’s autodiff in C++11

I’m kicking off my next big Stan project, which is to write a test framework for our math library differentiable functions. They’re tested very thoroughly for reverse mode, but not so much beyond first-order derivatives. This is huge and scary and now there’s all of C++11 lying at my feet for the taking.

I spent a few weeks working on other things while panicking and thinking the problem was just too hard because I couldn’t grasp it all at once.

Then I bit the bullet and asked what I’d like to see from the user’s perspective. That was enough to let me write the client-facing technical spec in a simple GitHub issue on stan-dev/math: Issue 557: fvar testing framework. I came up with the rough outline of a feasible high-level API that would let the user express the problem in their own terms; here’s what it looks like for double values:

std::function<double(double,double)> f = ... some binding ...;
auto t = tester(f);

t.good(1, 1, 2);
t.good(2, 3, 5);

t.throw(NaN, 1.0, std::domain_error);

t.run();

I’ve already got a simple implementation hard coded for scalars on a branch.

I don’t know exactly what all that is going to look like. I’ve barely dipped my toe into C++11, though I can say I agree with Stroustroup that it looks like an entirely new (and better!) language.

Of course, as soon as I tried to code a simple (non-polymorphic) instance, I realized I actually need a much more general binding for the function and really need to pass a static templated function, which means passing a class type for a type that implements the function application concept. Otherwise, though, everything will look pretty much like this, right down to the factory method. And I should be able to make it fly for arbitrary argument and return types with enough typelist magic.

The takeaway message on design, as the entire industry has learned for most scales of projects, it’s really not worth going overboard on design—just something committed enough to see where you’re going without having to question that at every turn (which is a huge time sink).

So now I have to start building bottom up, where I’ll write a general functional test framework that takes in a differentiable functor and runs it through all five variations of autodiff (none, reverse, directional derivatives, second-order directional derivatives, Hessians, and tensors of third derivatives). Then, in a month or three, we’ll be ready to release Riemannian HMC in an interface (which will also require some distribution/config issues in all the interfaces).

That’s the rest of my weekend accounted for, but the magic is that it’ll just be clean coding. Not much thinking required. I can lay this code down like a bricklayer (programmers love building metaphors).

Even fictional physicists have this problem

The other reason I wrote this post today is that I just read a striking passage on page 79 of the sci-fi thriller Dark Matter by Blake Crouch. Our protagonist is trying to get his bearings and get out of his current bind and decides to fall back on his physics skills (no spoilers):

Experimental physics—hell, all of science—is about solving problems. However, you can’t solve them all at once. There’s always a larger, overarching question—the big target. But if you obsess on the sheer enormity of it, you lose focus.

The key is to start small. Focus on solving problems you can answer. Build some dry ground to stand on. And after you’ve put in the work, and if you’re lucky, the mystery of the overarching question becomes knowable. Like stepping slowly back from a photomontage to witness the ultimate image revealing itself.

I have to separate myself from the fear, the paranoia, the terror, and simply attack this problem as if I were in a lab—one small question at a time.

Exactly! Build some dry ground to stand on. If you try to build the entire program while in a rowboat, you’ll not only be coding alone, you’ll be miserable doing it.

Also in nonfiction

When I first read Hunt and Thomas’s Pragmatic Programmer, a book that changed my whole attitude about programming, it dawned on me that the whole thing was about controlling fear. Writing software other people are going to use is a scary business. We all know how hard it is to get even a few lines of code right, much less hundreds of thousands of lines.

And don’t forget real life

It helped to have a great practical introduction to all this at SpeechWorks. We had great marketing people helping with the functional specs, an awesome engineering team who could handle the technical specs and costing, and managers with enough judgement to get an amazing amount of coordinated work out of 20 programmers without exhausting us. Despite having watched John Nguyen do it, I’m still not sure how he pulled it off. Everyone who worked there misses the company.

8 thoughts on “Design top down, Code bottom up

  1. > it dawned on me that the whole thing was about controlling fear. Writing software other people are going to use is a scary business. We all know how hard it is to get even a few lines of code right, much less hundreds of thousands of lines.

    Great comment. I know too many researchers who have have been brave enough to write articles other people are going to read, but they admit that they don’t want to publish the code used because they are afraid that someone will read it!

    • Knowing that someone is going to review your code is a good way to keep yourself honest.

      If you’re afraid to have other people to look at your code, shouldn’t you be even more afraid to publish based on its results?

      I think what’s going on is that people think their code is like a messy apartment or bedroom; it’s not broken, just messy. Given time, they can find what they need. And probably nothing’s lost. They’re embarassed by the mess, but fail to perceive the larger problem of which the mess is merely a symptom.

  2. Totally agree on all your comments about well structured, documented and commented code. There are arguments to be made that if function names and variable names were better that many comments would be rendered moot.

    Have you considered non-test-based methods for addressing correctness? There’s a decent body of research that indicates that formal code review – going over the code line by line with an experienced individual, explaining what you did and why you did it, etc. all while carefully scribing comments on what’s wrong and what could simply be made better is a really effective way to eliminate defects in code.

    I’d also recommend you take a look at tools like Jester (that one’s specifically for Java if I recall correctly) if you haven’t already. It takes your code and makes small changes (like changing && to ||, for example) and then runs the tests again. Apparently people are horrified to find that the tests still happily pass because the test cases don’t actually exercise what you think they exercise. :)

    • Absolutely. Every pull request for Stan is code reviewed by at least one other developer.

      Pair programming is amazingly effective in my experience. But it’s exhausting.

      We want tests in place partly to avoid regression problems. We do a lot of refactoring and that’s really nasty to do without extensive tests in place, though it can also be a pain when there are if the tests are too low level and brittle, as many of ours are.

      We’re going to be working on test coverage in the coming year or two. I’m working on that now, in fact. I often do things myself like what you say Jester days when I’m surprised a test passes on the first go.

    • For those with the inclination, I find that pseudo-formal or semi-formal proofs of correctness are a very effective way to reduce bugs. The basic idea is to think up a variety of properties that you think your code should have “Function X only ever returns a valid positive floating point number or throws an exception of type Y” and “Whenever the input to X is positive, so is the output” or whatever. Then go through and examine the code to determine whether the property holds. You can gain two kinds of things from this:

      1) You find out some useful properties that you can rely on when programming other stuff

      2) You find out that a useful property you’re currently relying on when programming other stuff *isn’t* true, and you can then decide whether it should be and fix it, or whether it shouldn’t be and change your assumptions in other places.

      3) You think of things that you are implicitly relying on which need testing or examination.

      When working on code that runs for hours and hours even when it isn’t in a debugger, the idea of running the code until a bug shows up and then stepping through it… just doesn’t work. In a debugger your code might be 10 to 100 times slower. so something that was taking 5 hours to a day to show up will take 2 days to a month to hit in your debugger before you can even start stepping. The only effective way to debug that kind of code is to develop skills in reasoning about code.

      • Those are called “invariants” in computer science. And I completely agree it’s the way to think about things—it’s why you want to document the input conditions and error conditions of your functions and test them. And if there are data structures getting modified, test those for invariants. Maintaining invariants is the primary reason why computer scientists love immutable data structures; maintaining invariants in the face of mutating data is very challenging (as in a reactive GUI).

        I’ve seen good programmers (like Ezra Story, the best debugger I’ve ever met) write code to isolate bugs in that took two days to surface in intensive multi-core processes to kick off instrumentation. To make a long story short, unless you’re Ezra, don’t volunteer to debug multi-threaded telephony platform memory management.

Leave a Reply

Your email address will not be published. Required fields are marked *