Mar 18, 2016
An alternative worldview to 'modularity'

It's a common trope among programmers that a single computer contains enough bits that the number of states it can be in far exceeds the number of atoms in the universe. See, for example, this 3-minute segment from a very entertaining talk by Joe Armstrong, the creator of the Erlang programming language. Even if you focus on a single tiny program, say one that compiles down to a 1KB binary, it's one of 21024 possible programs of the same length. And 1KB is nothing these days; larger programs get exponentially larger spaces of possibility.

The conventional response to this explosion of possibilities is to observe that the possibilities stem from a lack of structure. 10 bits encode 210 possibilities, but if you divide them up into two sub-systems with 5 bits each and test each independently, you then only have to deal with twice 25 possibilities — a far smaller number. From here stem our conventional dictums to manage complexity by dividing systems up into modules, encapsulating internal details so modules can't poke inside each other, designing their interfaces to minimize the number of interactions between modules, avoiding state within modules, etc. Unfortunately, it's devilishly difficult to entirely hide state within an encapsulated module so that other modules can be truly oblivious to it. There seems the very definite possibility that the sorts of programs we humans need to help with our lives on this planet intrinsically require state.

So much for the conventional worldview. I'd like to jump off in a different direction from the phenomenon of state-space explosion in my first paragraph. I'll first observe that if we had to target a single point in such impossibly large spaces, we'd never be able to do so. What saves us is that for every desire we have in mind, every bit of automated behavior we conceive of that will help us in our lives, there are many many possible programs that would satisfy it. We're targeting not a single point, but a whole territory, a set of potential programs that we could have written (and might yet write in the future) that meet our need of the moment.

This is a really nice property, and it saves us in the short-term. However, this boon comes curled up around a stinger. Even though you care only about whether your program is in this territory (correct) or not (buggy) and don't care precisely where in the territory your program is, your program only encodes the current point you're at. But human programs have a way of lasting a long time, and other people will make changes to your program. Every little change is moving its location in the space of possible programs to some adjacent point. Make enough changes and you can end up pretty far from where you started. Are you still in the territory of correct programs? You have no possible way of knowing as long as you focus on just the contents of your program. It doesn't matter how much you tinker with the anatomy of your program, dividing and sub-dividing it into sub-systems and components. We need to start encoding the boundaries of the territory we care about.

Tests are the only way we yet have to try to encode territories. A test says, "I don't care what's inside your program, but does it work in this one situation?" A comprehensive set of tests is like a Fourier Transform, taking us away from the space of possible programs and into the space of possible situations our program may find itself in. Ideally, if we pass all tests we're confident that our program hasn't left the territory of correct programs. However, contemporary tests aren't quite the complete solution yet. It's easy today to write tests that fail in spurious ways even if your program remains correct. The map (tests) doesn't yet correspond well to the territory.

Modules work well for simple sub-systems without internal state. But remember the dictum to make our designs as simple as possible but no simpler. To the extent that our programs require state, stop tweaking modularity constraints endlessly and ineffectually. Instead, practice writing tests, watch out for ways that the tests you write only work for this program but not other correct programs. Work on ways to write more general tests rather than more general code.

With apologies to Fred Brooks:

Show me a program's code but not its tests, and I shall continue to be mystified. Show me its tests, and I won't usually need its code; it'll be obvious.

(Thanks Kinnard Hockenhull for the conversations that resulted in this post.)


  • rocketnia, 2016-03-20: "Avoiding state within modules" took me by surprise, probably just because I've been working with a particular concept of module state.

    I think of modules as units of program serialization. We need a complete set of matching modules in order to know what program implementation we're running in the first place. As far as the running program is concerned, its modules don't change. They can change as you install or uninstall them from the machine, or as you actively develop them, but then the program itself changes (or becomes effectively uninstalled) as well.

    You're talking about a different kind of module, one that can delimit areas of a region of stateful behavior. This kind of module is no longer very easy to serialize or transport between hosts, so it's a much different kind of entity.

    In that case, I believe that kind of modularity boundary is essentially a social issue. It's a privacy boundary.

    If a region of stateful behavior has its own independence and rights (e.g. if it's literally a human being), then any given module boundaries are going to be harmful or conducive to that, and we should try to keep the boundaries continuously up to date if we're going to draw them at all. They may ultimately have only a passing resemblance to the original source code boundaries, because the run time state of the system can become much more socially relevant than the original programming (especially if the original programming was a language interpreter).

    Overseeing these privacy boundaries to avoid letting oppressive situations hide out is good, but we'll also want to *avoid* policing them in ways that reinforce oppression. So I think when we use state in a program, we need the ability to designate someone who we trust to make the proper judgments regarding whether we're using that state ethically. (Other witnesses can judge whether we're choosing a witness ethically, and so on up the reflective tower.)

    Internally to the program, we can still subdivide the state in a fractal way where every branch is modularly independent from every other, but we may be required to reallocate the boundaries sometimes.

    "Tests are the only way we have yet to try to encode territories" indeed, but I'd say that's a tautological consequence of the way you've formulated the problem. If we need some way to check that a program is in the desired territory, then that "way to check" is a test, and we need a test. That said, some "ways to check" might care about implementation details, if the person doing this checking has access to the implementation details already. Typechecking cares about implementation details, for instance.

    "It's easy today to write tests that fail in spurious ways even if your program remains correct." - Interesting! Having written more tests than I'm used to, I've experienced this too. I tend to blame it on the use of a concurrent or stateful framework that doesn't provide adequate support for synchronization on the states I'm trying to check for. I think careful design could mitigate this, but that depends on everything following that careful design, and race conditions have a history of defying careful designs I guess.

    I'm finishing with a compliment half-sandwich, but I mean it: The idea that module boundaries reduce the search space by dividing its dimensions into two orthogonal sets of dimensions... That's pretty evocative. It gives a real meaning to orthogonality. I don't quite understand the Fourier Transform comparison, but it is thought-provoking too.   

    • Kartik Agaram, 2016-03-20: I've tried for many years to avoid the word 'modularity' since it's so imprecise and means so many different things to different people. That's part of the problem with this post of mine. But I'm glad you got something out of it:

      _"I think of modules as units of program serialization. We need a complete set of matching modules in order to know what program implementation we're running in the first place.. You're talking about a different kind of module, one that can delimit areas of a region of stateful behavior."_

      That's a really useful distinction! I think there's a sleight of hand practiced by our profession: we motivate modules by pointing at complexity and promising the ideal of regions of isolated stateful behavior. But this ideal has never been realized to date. Instead we get suckered into more superficial forms of isolation that don't always break even on the complexity they introduce.

      _"It's easy today to write tests that fail in spurious ways even if your program remains correct." - Interesting! Having written more tests than I'm used to, I've experienced this too. I tend to blame it on the use of a concurrent or stateful framework that doesn't provide adequate support for synchronization on the states I'm trying to check for._

      Hmm, I've seen other causes. Such as making radical changes that alter many function headers at once. Then the tests fail because the invocations they're making are stale. You've seen my previous idea of white-box testing to address issues like this. But it's (obviously) not perfect yet. I should do a follow-up about the issues I've run into. They're just really hard to describe without going into great gory detail..

  • Anonymous, 2016-05-24: I find this interesting and I think there is a lot of value in your other posts too, which I am just finding for the first time.

    Let me first posit that the human brain performs 'compression' in how concepts are stored, and the complexity, loosely Kolmogorov complexity, or the minimum compressed size, corresponds to the difficulty of retaining the concepts in the mind. Let me use this as the definition of simplicity. Unlike Kolmogorov complexity which occurs in isolation, the human conceptual compression occurs in the context of human experience, so for example metaphors with real life or invocation of commonly understood Patterns can produce very high compression ratios and hence quick understanding.

    A program with many interdependencies will tend not to have an efficient compressed representation, while a program factored into modules will tend to be more easily conceptualized, as long as the modules generally follow conceptual boundaries (critical, but generally not stated because it's "obvious"). Easier conceptualization is also true of structured vs. goto-oriented programs also and I see it as part of the same push toward simplicity.

    Now, this only pushes toward having a program for which a compressed representation *exists*, and doesn't directly address the problem of *finding* that representation, i.e. the difficulty of gaining a conceptual understanding of the program (cue Peter Naur). How often is it that an expert sees a program as "simple" while an outsider sees a program as impenetrable?

    Your concept of territories of programs is an interesting one, and I would say each conceptual definition of a program would correspond to a territory, as each represents a concept of correctness. I would agree that the program text, as a point in the territory, does not by itself distinguish what aspects are necessary and which are accidental. There are many territories that contain the point, and the point is mostly silent about which territory it is a solution for.

    I say "mostly silent" because in practice reverse-engineering produces a somewhat predictable conceptual understanding (territory) from a program, again through compression or Occam's Razor or induction, which are to me facets of the same underlying phenomenon. Loosely this is a process by which a person searches for the simplest territory for which the given program is a solution. With a weak understanding (minimal compression), very little may be assumed to be accidental, and safety demands treating nearly everything as necessary. The territory must be assumed a very small neighborhood of the program. As understanding grows, so does simplicity, and more can be understood to be accidental vs. necessary and the territory grows accordingly.

    Needless to say, this inference process is awful. It's time-consuming and very error-prone, and can lead to different territories even among members of the same team.

    I cannot speak from experience when it comes to test driven development, but I think this non-test-oriented subjective inference of territories from points is an extremely common experience of how things can go wrong.

    I can't say from experience but I am thoroughly convinced that tests would be critical in objectively defining the territory. I'll assume code is always meant to be read by humans and not just executed by machines, but for the tests themselves the importance of human readability is even greater. You have already said this but it merits repeating, paraphrased, that since the tests define the territory, they would serve as a natural channel for communicating the concepts of the program.   

    • Kartik Agaram, 2016-05-24: That's a nice alternative way of thinking about it. Yes, the difference between the expert's and outsider's view is often training their neural networks on which bits are crucial to correctness and which bits are irrelevant. You start out with Occam's Razor, and then you train on additional wrinkles as you spend time in the school of hard knocks.

Comments gratefully appreciated. Please send them to me by any method of your choice and I'll include them here.

RSS (?)
twtxt (?)
Station (?)