The Math Professor
I had a Mathematics professor who once said, “You’ve been using numbers for quite a while, so it’s about time you learned what they really are.” This was in an analysis class where we were learning about real numbers. There are a couple of ways to define real numbers: an axiomatic approach and a construction-based approach. In the former, you write down the fourteen or fifteen properties of real numbers and presume that a set containing such elements exists. In the latter, you build real numbers out of rational numbers.
It’s almost true that real numbers are merely sequences of rational numbers. It’s well known that pi or the square root of two are not rational, but there are sequences of rational numbers that converge to these real numbers. However, the sequences are not unique. There are lots and lots of sequences whose limit is pi.
For example, just take any sequence that converges to pi and prepend any integer to the beginning of it. Since you have an infinite number of integers to choose from, you have at least an infinite number of sequences that all converge to the same real number. If that strikes you as too much of a cheat, consider that different algorithms exist for approximating pi. Some converge faster than others, but if you could run them forever, they’d all produce pi.
So, an individual sequence doesn’t correspond to a real number, but the set of all sequences with the same limit does. In other words, real numbers are equivalence classes of sequences of rationals. On the one hand, we could have a totally abstract definition of real numbers, based on axioms. (Multiplicative commutativity, the distributive law, and so on.) But on the other hand we could have a more pragmatic definition rooted in equivalence classes of simpler, more mundane objects.
There’s something magical about equivalence classes. Consider again that two different algorithms can generate sequences of digits that both converge to pi. If you’ll pardon the pun, pi must be, well, real, if you can arrive at it in different ways. Equivalence classes of concrete things agree with the abstract real number concept, which is otherwise described by axioms alone.
The Physics Professor
I had a Physics professor who advanced a compelling definition of mass. “Mass,” he said, “is that property of a substance that makes the law of conservation of momentum true.” We all found this delightful. It was a rigorous step up from the circular pseudo-definitions we had seen before. (Mass is quantity of matter. What is matter? Matter is anything that occupies space and has mass. What then is mass, again? Ugh.)
As curious Physics majors, the professor’s axiomatic approach to mass appealed to our inner Euclid. First, demand that the something like the law of conservation of momentum works, and then see what follows from that. But, in time, I came to feel that it was dangerously abstract. Sure there’s this elegant concept, but why should the real universe obey it? Yes, it was the apparent utility of mass and momentum that made them worth studying, but were we doing Physics (where we’re never sure that we’re right) or doing Mathematics (where we’re right but we don’t know what we’re talking about).
Anyway, there are a number of operational definitions of mass. By “operational,” we mean measurements that rely directly on experiments, even if those experiments are only gedankens. For example, if you pull on an isolated body with a rubber band stretched to a fixed length, then the object’s mass can be operationally defined as the reciprocal of the resulting acceleration.
Other operational definitions are possible. Imagine tying a body to a test mass and spinning them about each other in zero-g. The location of the axis on the rope can be used to measure the ratio of the two masses. You could also imagine a mass-measurer made out of an asymmetrical tilt-a-whirl, where the units surprisingly turn out to be seconds-squared.
You could repeat many experiments, and the results would -- if you’ll pardon the term -- converge on the true mass as operationally defined. Moreover, different methods of measurement will agree. The different operational definitions produce consistent measures. You know where I'm going with this. I'm about to suggest that they form an informal equivalence class.
The abstract definition of mass is real, and it’s complemented by the equivalence class of all operational definitions of mass. This same line of reasoning sheds insight into other physical observables, such as charge, temperature, and so on. I’m struck by the analogy to the two complementary ways to define real numbers. Equivalence classes of operational definitions marry real world phenomena to abstract models, where we can flex our mathematical muscles and do interesting work.
Software Velocity
When tracking progress on a burn-up chart, agilists concede that the units of velocity are not important. They could be person-days, story-points, or whatever. Nevertheless, the velocity concept has meaning. I imagine that each team is like its own custom experimental apparatus, providing its own operational definition of velocity.
But is software velocity real? Yes. It’s an abstract concept whose complement is the equivalence class of all operational definitions of software velocity. The difference between physical mass and software velocity is that the experimental equipment needed to operationally define physical mass is very simple, at least in principle. But the analogous equipment for a software development project lives in the deep structures of the developers’ brains, drawing upon whatever arcane magic causes them to choose which Fibonacci number corresponds to the heft of any given feature.
Friday, December 26, 2008
Saturday, September 20, 2008
Normative Theorems, Narrative Principles
We need a better word than "spec" to name the documents we write. A specification well-describes things that are specifiable, such as a language grammar or a communication protocol or a reusable library. So, if you need to write an Ada compiler, or implement an HTTP client, or use the STL, then the specs for these sorts of things are probably sufficient for you to get your work done.
But, that's because you already knew a thing or two about compilers, or IPC, or generic programming. If that's the kind of thing that you do in your day job, then I'm happy for you, and a little jealous. A lot of software has to do with modeling poorly understood domains, where there is little agreed-upon common vocabulary or precedent. Some days I get confused about exactly what my job is, because I've strayed into something quite new.
If that describes you too, then a normative-only spec doesn't reveal the gist of the problem to be solved. Many of the so-called specs that we write concern "wicked" problems, that is, problems that are so intractable that they can only be stated by solving them. I've often seen requirements documents go on for pages and pages with the guise of rigor, but which fail to convey enough context for why their enumerated and cross-referenced shalls are good ideas.
During the actual process of composing such a document, a good writer will actually discover and answer these "why" questions. Options are weighed and decisions are made. But if the reasoning isn't recorded, then the spec degenerates into solipsist snippets of conversations between the author and himself. That's hardly communication.
At work, I try to champion putting more non-normative context into our documents. Unfortunately, I'm really good at losing arguments. So, I've started to wonder if any lessons from Mathematics or Physics can shore up my reasoning. I can think of three reasons why normative-only specifications are like Mathematical proofs.
A while back, a pretentious document crossed my desk. It dotted every "i" and crossed every "t." Yet, after several readings, I still had no idea what the point was. There was a whole bunch of language that felt like it was adding fault tolerance features to an existing distributed product, but at the same time there was no redundant hardware to make changes worthwhile. So, naturally, I started to inject myself into hallway conversations to get the gist of the project.
It turns out that the existing product relied on some third-party software that came with some pretty onerous licensing fees. The whole point of the project was to rework how the system was deployed to save money. If you could revisit a few architectural decisions, then the expensive software could be localized in fewer places, thus saving a few bucks. Knowing that one little gem would have made the spec comprehensible, but it was nowhere to be found in the text because it was "non-normative."
Of course, you already know the punchline of the story. After spending a bunch of cash on the new project, somebody finally had the idea to call up the third-party software vendor and try to negotiate a more reasonable price. They agreed, and the re-architecture effort turned out to be a very expensive way to save money. By every criterion, whether dollars spent or risk incurred or opportunities lost, the phone call was the better option. But since not enough people were trusted with the real objective of the project, the optimal solution was discovered too late.
In hindsight, calling up the vendor seems obvious, but it wasn't. For those developers, who seldom interacted non-technically, it actually tipified out-of-the-box thinking. Creativity can't be scheduled into the spec-writer's block of time, because nobody can think of everything. The deliberate decision to exclude non-normative information from the original spec enabled this mistake
The best solution to a wicked problem is not commanded; it often emerges as it is solved. Had enough people understood what they were being asked to do, somebody would have made that phone call sooner. Consider Eric Raymond's assertion that "given enough eyeballs, all bugs are shallow." It's interesting to speculate whether there exists some parallel to Linus's Law. Perhaps enough eyeballs tame all wicked problems.
I suppose rationale doesn't matter when the spec itself is the work product. A compiler writer doesn't really have to know why Ada has two different functions for mod and remainder. One would just have to know the rules for each, and implement them correctly. But many of our software documents are not work products themselves; they are just the means why which communities build work products.
Much of what we do is wicked.
The analogy to nature came to mind as I thought about this software development question. I can hone my mathematical skills by reading and doing mathematics. Terse proofs are suitable in Mathematics, because anything you need to know is already out there for the taking. (Can you tell whether I'm a Platonist?) But Physics doesn't work that way. Or, at least, it doesn't work that way in my brain. One can't do new physics without doing experiments, and the most exciting experiments are done in unfamiliar domains.
So, mathematical proofs are like normative specifications, but physical principles are like domain expertise. That surely can't be guessed a priori. Now, suspend your objections for a minute. Yes, Physics has proofs. Yes, Mathematics is at least a quasi-empirical science. Yes, the analogy is bad. But all analogies are bad. I'm not really trying to make a point about Mathematics and Physics here; I'm trying to explore how to write better software documents.
For example, I think one can reason their way towards the notion that there are more real numbers than there are rationals. (I'm not saying everyone is Cantor, but I am saying that bright people can follow his conclusions, and that he didn't need to build a machine to discover them.) This contrast with Physics. I don't think anybody thought up the quantum Hall effect before it was discovered experimentally, even though both quantum mechanics and the Hall effect were already laying around. Physics is wicked.
The second most famous equation in Physics is due to Newton, F = ma. With calculus, we economically write the more general form F = dp/dt, where p represents the momentum of the object. In all our ordinary experience, momentum is the product of the object's mass and velocity, p = mv. Newton's second law tells us that forces impart changes to an object's momentum.
Embracing the analogy, we can say that F = dp/dt is a normative specification for how the universe works. Strictly speaking, you don't need to convey much else. You don't need an appendix containing the history of Leibniz and Newton. As long as you already know calculus and the definition of p, you're off to the races.
Knowing calculus is a technical skill. If you grok fluxions, then you understand what F = dp/dt really means. Given some measurements, you can make some meaningful, quantitative remarks about an object's behavior.
Maybe it's technical skill like being able to read UML. If you look at the arrows on a class diagram (whether inheritance or composition), then you can tell what depends on what in the picture. If there are cycles, then you might be able to say something intelligent about the quality of the design.
Einstein realized that some pretty weird things happen when objects move at speeds that are non-trivial fractions of the speed of light. Our humdrum definition of momentum grows some wrinkles. Our familiar p = mv turns out to be the low velocity approximation of the more general p = mv/sqrt(1-v^2/c^2).
The normative formula, F = dp/dt is still quite correct! Even with Einstein's discovery, I wouldn't need to rewrite my normative spec. But it's going to be misunderstood by anybody who only knows the low velocity definition of p. When you start to pull people out of the domain in which they are most comfortable, normative isn't enough.
So, if "spec" is too pretentious for what we do, what's the alternative? Our documents need to be more humble. It's a happy coincidence of English that humble and human are such similar words, because when trying to evolve solutions to wicked problems, it's all about people communicating.
Specs are perfectly good work products that describe what something has to do, and they have a crucial role in software development. But not every document is an end unto itself. Many are living documents. What could we call those documents, which people use as tools to build a work product?
Narratives.
Specs are ends of well-defined efforts. Narratives are means of attacking wicked problems. In literature, the best narratives uncover profound truths about the human condition. In software development, the best narratives collect the relevant principles needed to attack the problem at hand.
Einstein elucidated the principle that the speed of light is constant, regardless of the speed of the observer. This principle drove a rethinking of the definition of momentum, but it only matters for objects outside of our familiar experiences. However, when attacking problems where the principle is relevant, we'd better make it clear. I'm going to start calling what I do in my day job narrative-writing instead of spec-writing, and see where that leads.
But, that's because you already knew a thing or two about compilers, or IPC, or generic programming. If that's the kind of thing that you do in your day job, then I'm happy for you, and a little jealous. A lot of software has to do with modeling poorly understood domains, where there is little agreed-upon common vocabulary or precedent. Some days I get confused about exactly what my job is, because I've strayed into something quite new.
If that describes you too, then a normative-only spec doesn't reveal the gist of the problem to be solved. Many of the so-called specs that we write concern "wicked" problems, that is, problems that are so intractable that they can only be stated by solving them. I've often seen requirements documents go on for pages and pages with the guise of rigor, but which fail to convey enough context for why their enumerated and cross-referenced shalls are good ideas.
During the actual process of composing such a document, a good writer will actually discover and answer these "why" questions. Options are weighed and decisions are made. But if the reasoning isn't recorded, then the spec degenerates into solipsist snippets of conversations between the author and himself. That's hardly communication.
At work, I try to champion putting more non-normative context into our documents. Unfortunately, I'm really good at losing arguments. So, I've started to wonder if any lessons from Mathematics or Physics can shore up my reasoning. I can think of three reasons why normative-only specifications are like Mathematical proofs.
- They hide the many wrong turns and false starts that their authors suffered while working.
- They are themselves the end product of the effort, not necessarily a means to an end. (Implementing the spec, or applying the theorem, is often left to others.)
- Specs and proofs are both terse, but they convey enough information for their consumers, as long as their consumers have the expertise and context to read them.
I am going to give what I will call an elementary demonstration. [But] elementary does not mean easy to understand. Elementary means that nothing, very little, is required to know ahead of time in order to understand it, except to have an infinite amount of intelligence. It is not necessary to have knowledge, but to have intelligence in order to understand an elementary demonstration.In this sense, our normative software specs need to be elementary. Unfortunately, I have never met a software spec writer as gifted as Feynman. Neither have you.
A while back, a pretentious document crossed my desk. It dotted every "i" and crossed every "t." Yet, after several readings, I still had no idea what the point was. There was a whole bunch of language that felt like it was adding fault tolerance features to an existing distributed product, but at the same time there was no redundant hardware to make changes worthwhile. So, naturally, I started to inject myself into hallway conversations to get the gist of the project.
It turns out that the existing product relied on some third-party software that came with some pretty onerous licensing fees. The whole point of the project was to rework how the system was deployed to save money. If you could revisit a few architectural decisions, then the expensive software could be localized in fewer places, thus saving a few bucks. Knowing that one little gem would have made the spec comprehensible, but it was nowhere to be found in the text because it was "non-normative."
Of course, you already know the punchline of the story. After spending a bunch of cash on the new project, somebody finally had the idea to call up the third-party software vendor and try to negotiate a more reasonable price. They agreed, and the re-architecture effort turned out to be a very expensive way to save money. By every criterion, whether dollars spent or risk incurred or opportunities lost, the phone call was the better option. But since not enough people were trusted with the real objective of the project, the optimal solution was discovered too late.
In hindsight, calling up the vendor seems obvious, but it wasn't. For those developers, who seldom interacted non-technically, it actually tipified out-of-the-box thinking. Creativity can't be scheduled into the spec-writer's block of time, because nobody can think of everything. The deliberate decision to exclude non-normative information from the original spec enabled this mistake
The best solution to a wicked problem is not commanded; it often emerges as it is solved. Had enough people understood what they were being asked to do, somebody would have made that phone call sooner. Consider Eric Raymond's assertion that "given enough eyeballs, all bugs are shallow." It's interesting to speculate whether there exists some parallel to Linus's Law. Perhaps enough eyeballs tame all wicked problems.
I suppose rationale doesn't matter when the spec itself is the work product. A compiler writer doesn't really have to know why Ada has two different functions for mod and remainder. One would just have to know the rules for each, and implement them correctly. But many of our software documents are not work products themselves; they are just the means why which communities build work products.
Much of what we do is wicked.
The analogy to nature came to mind as I thought about this software development question. I can hone my mathematical skills by reading and doing mathematics. Terse proofs are suitable in Mathematics, because anything you need to know is already out there for the taking. (Can you tell whether I'm a Platonist?) But Physics doesn't work that way. Or, at least, it doesn't work that way in my brain. One can't do new physics without doing experiments, and the most exciting experiments are done in unfamiliar domains.
So, mathematical proofs are like normative specifications, but physical principles are like domain expertise. That surely can't be guessed a priori. Now, suspend your objections for a minute. Yes, Physics has proofs. Yes, Mathematics is at least a quasi-empirical science. Yes, the analogy is bad. But all analogies are bad. I'm not really trying to make a point about Mathematics and Physics here; I'm trying to explore how to write better software documents.
For example, I think one can reason their way towards the notion that there are more real numbers than there are rationals. (I'm not saying everyone is Cantor, but I am saying that bright people can follow his conclusions, and that he didn't need to build a machine to discover them.) This contrast with Physics. I don't think anybody thought up the quantum Hall effect before it was discovered experimentally, even though both quantum mechanics and the Hall effect were already laying around. Physics is wicked.
The second most famous equation in Physics is due to Newton, F = ma. With calculus, we economically write the more general form F = dp/dt, where p represents the momentum of the object. In all our ordinary experience, momentum is the product of the object's mass and velocity, p = mv. Newton's second law tells us that forces impart changes to an object's momentum.
Embracing the analogy, we can say that F = dp/dt is a normative specification for how the universe works. Strictly speaking, you don't need to convey much else. You don't need an appendix containing the history of Leibniz and Newton. As long as you already know calculus and the definition of p, you're off to the races.
Knowing calculus is a technical skill. If you grok fluxions, then you understand what F = dp/dt really means. Given some measurements, you can make some meaningful, quantitative remarks about an object's behavior.
Maybe it's technical skill like being able to read UML. If you look at the arrows on a class diagram (whether inheritance or composition), then you can tell what depends on what in the picture. If there are cycles, then you might be able to say something intelligent about the quality of the design.
Einstein realized that some pretty weird things happen when objects move at speeds that are non-trivial fractions of the speed of light. Our humdrum definition of momentum grows some wrinkles. Our familiar p = mv turns out to be the low velocity approximation of the more general p = mv/sqrt(1-v^2/c^2).
The normative formula, F = dp/dt is still quite correct! Even with Einstein's discovery, I wouldn't need to rewrite my normative spec. But it's going to be misunderstood by anybody who only knows the low velocity definition of p. When you start to pull people out of the domain in which they are most comfortable, normative isn't enough.
So, if "spec" is too pretentious for what we do, what's the alternative? Our documents need to be more humble. It's a happy coincidence of English that humble and human are such similar words, because when trying to evolve solutions to wicked problems, it's all about people communicating.
Specs are perfectly good work products that describe what something has to do, and they have a crucial role in software development. But not every document is an end unto itself. Many are living documents. What could we call those documents, which people use as tools to build a work product?
Narratives.
Specs are ends of well-defined efforts. Narratives are means of attacking wicked problems. In literature, the best narratives uncover profound truths about the human condition. In software development, the best narratives collect the relevant principles needed to attack the problem at hand.
Einstein elucidated the principle that the speed of light is constant, regardless of the speed of the observer. This principle drove a rethinking of the definition of momentum, but it only matters for objects outside of our familiar experiences. However, when attacking problems where the principle is relevant, we'd better make it clear. I'm going to start calling what I do in my day job narrative-writing instead of spec-writing, and see where that leads.
Sunday, January 6, 2008
Methods Of Proof
Over the past couple of weeks or so, I've been playing with some recreational math. It was pointed out to me that the sum of the first n cubes always seemed to be a square. For example, 1^3 + 2^3 + 3^3 = 36 = 6^2. This is probably obvious to the highly numerate, but it blew my mind to learn it. After struggling a bit, I could show that the sum of the first n cubes is always the square of the sum of the first n integers. Wow!
I came up with a couple of different proofs that were full of tedious algebra, and didn't seem to offer any insights into why such a relation should hold. I became convinced that something so easy to state should have a brief demonstration, possibly geometric, and definitely more intuitive. For quite a while, I couldn't find such a thing.
Then it hit me. Induction! There are so many methods of proof: reductio ad absurdam, proof by construction, even proof by computer. Once I remembered the technique, I quickly banged out a proof by induction that the sum of the first n cubes is the square of the sum of the first n integers in just a handful of lines.
Mathematical proofs to me are a lot like tests in software development. Just as there are varied methods of proof, there are varied mechanisms for testing the deliverables in the software development process. For example, I might test that the requirements are met with formal acceptance testing. In other words, the acceptance test proves the functional spec (or some other document).
As another example, someone might say that the unit tests prove the code. As a fan of test driven development, I would say exactly the reverse. But the point is that different testing mechanisms are suitable for different parts of the development process. Just as a mathematician must be well versed in different methods of proof, we software folks must be well versed in different testing mechanisms.
But what tests the design?
Sure, a formal inspection can uncover lots of problems in a document, but is that really sufficient to demonstrate that a design is any good? Multithreading issues, resource leaks, inadequate error handling, and bottlenecks are difficult to uncover in a review, except in the most obvious cases. Formal review chauvinists are sure to challenge me on that opinion. But I believe that if humans really could anticipate how complex systems behaved, then there wouldn't be any such phrase as emergent behavior.
So, I feel that we need another "method of proof" suitable for evaluating design fitness. Ideally, it would be inexpensive and repeatable, giving it another leg up on formal inspections. It should also be available as early in the development process as possible. I suggest that designs are testable by simulation.
The project I've been working on most recently has lots of algorithms with tunable parameters, and one of the open questions is how much hardware firepower do we really need to handle realistic customer loads. Although I can imagine that somebody much smarter than I could figure this out from first principles, I wouldn't have much confidence in any design that wasn't vetted by simulations.
Happily, with simulation, we don't have to be done before we find out that our design is broken. With languages like Ruby, we can develop margin eaters and simulators rapidly. Design trouble spots can be identified early, maybe even before any production code is written. Of course, this is only possible if the architecture is amenable to simulation.
One figure of merit for a good architecture is how early it can support simulations. For example, a recent effort I've shepherded used text over sockets for interprocess communication. There were a lot of fans of Java Object Serialization, but that would have required Java on both sides of the connection. Sticking with text over sockets allowed rapid development of Ruby simulators and placeholders.
Testing designs by simulation is not an earth-shattering suggestion. Mature software companies have been using simulation forever, replacing margin eaters with production code as development proceeds. But as an architect, I have profited from the notion that simulation is a kind of test, a method of proof, for designs themselves.
I came up with a couple of different proofs that were full of tedious algebra, and didn't seem to offer any insights into why such a relation should hold. I became convinced that something so easy to state should have a brief demonstration, possibly geometric, and definitely more intuitive. For quite a while, I couldn't find such a thing.
Then it hit me. Induction! There are so many methods of proof: reductio ad absurdam, proof by construction, even proof by computer. Once I remembered the technique, I quickly banged out a proof by induction that the sum of the first n cubes is the square of the sum of the first n integers in just a handful of lines.
Mathematical proofs to me are a lot like tests in software development. Just as there are varied methods of proof, there are varied mechanisms for testing the deliverables in the software development process. For example, I might test that the requirements are met with formal acceptance testing. In other words, the acceptance test proves the functional spec (or some other document).
As another example, someone might say that the unit tests prove the code. As a fan of test driven development, I would say exactly the reverse. But the point is that different testing mechanisms are suitable for different parts of the development process. Just as a mathematician must be well versed in different methods of proof, we software folks must be well versed in different testing mechanisms.
But what tests the design?
Sure, a formal inspection can uncover lots of problems in a document, but is that really sufficient to demonstrate that a design is any good? Multithreading issues, resource leaks, inadequate error handling, and bottlenecks are difficult to uncover in a review, except in the most obvious cases. Formal review chauvinists are sure to challenge me on that opinion. But I believe that if humans really could anticipate how complex systems behaved, then there wouldn't be any such phrase as emergent behavior.
So, I feel that we need another "method of proof" suitable for evaluating design fitness. Ideally, it would be inexpensive and repeatable, giving it another leg up on formal inspections. It should also be available as early in the development process as possible. I suggest that designs are testable by simulation.
The project I've been working on most recently has lots of algorithms with tunable parameters, and one of the open questions is how much hardware firepower do we really need to handle realistic customer loads. Although I can imagine that somebody much smarter than I could figure this out from first principles, I wouldn't have much confidence in any design that wasn't vetted by simulations.
Happily, with simulation, we don't have to be done before we find out that our design is broken. With languages like Ruby, we can develop margin eaters and simulators rapidly. Design trouble spots can be identified early, maybe even before any production code is written. Of course, this is only possible if the architecture is amenable to simulation.
One figure of merit for a good architecture is how early it can support simulations. For example, a recent effort I've shepherded used text over sockets for interprocess communication. There were a lot of fans of Java Object Serialization, but that would have required Java on both sides of the connection. Sticking with text over sockets allowed rapid development of Ruby simulators and placeholders.
Testing designs by simulation is not an earth-shattering suggestion. Mature software companies have been using simulation forever, replacing margin eaters with production code as development proceeds. But as an architect, I have profited from the notion that simulation is a kind of test, a method of proof, for designs themselves.
Subscribe to:
Posts (Atom)