In the discrete world of computing, there is no meaningful metric in which "small" changes and "small" effects go hand in hand, and there never will be.
This is a fascinating quote. What's the justification for it though? Is it not possible that one day we will invent a computer language that supports writing very "robust" (in the sense of source code sensitivity) programs?
Isn't that, in many ways, the opposite of what people want out of a programming languages? It seems to me that expressiveness, and robustness (in the sense that you define robustness) are inversely related.
Whenever a language comparison pops up, there's always a large contingent of people who argue for the superiority of a language because ideas can be expressed more concisely in 'their' language, but that necessarily means that some small change will have a relatively large effect.
There's also robustness in the sense that, e.g., BitC was trying to be robust, and that's something that I think is promising.
However, a concise, expressive, very high-level domain-specific language can make it impossible to express many idioms that would break the semantics of the domain.
As an analogy (I hesitate to use one because of the article), you could have a high-level representation of HTML that would make it totally impossible to generate <HTML></NOTHTML>, which is not the case if you use a general-purpose system. (not a foolproof analogy but anyway)
On formal principles, we'd expect that robustness and expressiveness are inversely related, on the principle that low-entropy data can be recovered with better fidelity than dense data, but I think I can name a counterexample to this principle in practice: I think Haskell does a phenomenally good job of being both expressive and robust if we consider a practical definition of robust, whereby pain is not measured by likelihood of error but the cost of an error. Compile-time errors are extremely cheap in comparison to run-time errors.
You want an "almost right" program to fail, but you want it to do so at compile time. Runtime silent failure is the worst.
How could it be possible? Let's assume that a "small effect" is something like a character change. Consider:
if (a == b) ...
And,
if (a != b) ...
One character difference, exactly opposite meaning. Is it possible for such behavior to not exist in programming languages? I can't prove it, but I doubt it. I suspect it's inherent.
Let me clarify. Consider if I instead chose equal and not equal as my operators. Now a "small change" probably won't even be a valid program (not wqual). Any small change that does result in a valid program is unlikely to result in an equally small behavior change for any interesting input. Changing a strictly-less-than to a less-than-or-equal-to is a small change that results in what seems like a small behavior change when viewed locally. But my own experience with programming is that a local change such as that will have huge consequences later on - often to the point that the program crashes.
Consider it this way: the space of valid programs is infinite. The space of valid programs that solve a particular problem is much smaller (in the physics << sense) than the space of valid programs. Any perturbation from a valid program that solves the problem is much more likely (>>) to land you on a valid program that does not solve your problem than one that does.
I agree with your intuition, but computer science is a mathematically founded discipline, so the kinds of claim Dijkstra was making about "robustness" require formalisation and mathematical proof if they are to be taken seriously.
Like you I find it very difficult to even envisage what a "robust" language would be in this sense. What I'd like is for someone to define the properties that one would have and then show that it can't exist :)
NB he is demonstrably incorrect on this point:
Like all digitally encoded information, it has unavoidably the uncomfortable property that the smallest possible perturbations —i.e. changes of a single bit— can have the most drastic consequences.
>>> Like all digitally encoded information, it has unavoidably the uncomfortable property that the smallest possible perturbations —i.e. changes of a single bit— can have the most drastic consequences.
>> Error correcting codes do exist!
He acknowledged this explicitly immediately after, on the next sentence:
> [For the sake of completness I add that the picture is not essentially changed by the introduction of redundancy or error correction.]
Think of what happens if a single bit is changed in the error-correcting part of the program.
You could once-and-for-all prove the error correcting program correct and then use it again and again for every program. But that wouldn't actually help getting programs correct. For example if your error correcting program was to write every program three times, then if one of the three programs gives a different answer you use the answer of the other two. Now a human writing a program would probably just write the same bug in each of the three versions, i.e. the three versions are not independent. You could have the three versions written by three different humans. But that doesn't solve the problem either because some errors are just likely to be made by all three of them (for example forgetting to check some edge condition somewhere). So again the three versions are correlated. Or worse the problem could be in the specification all three of them got. I don't think there is any way out of this.
Human DNA is a "robust language." Everything is encoded redundantly, and most features "express" through multiple small, additive gates (e.g. changing one bit of your DNA will never take your hair all the way from blonde to black, only make it slightly lighter or darker.) We could make a programming language that works similarly, though it would likely be very unintuitive.
Not everything is encoded redundantly. Try changing CGA to TGA in one of the exons of PAX6. In humans, this change will result in aniridia, the lack of an iris, an unstable corneal epithelium, and other problems. This is just one example, the one I'm familiar with. There are many other single nucleotide polymorphisms that can cause big changes.
We think in continuous terms all the time when we use big O notation. If you have an O(n) (or O(n^2)) algorithm and make the input a tiny bit bigger, the computation becomes a tiny bit more complex. Dijkstra is too rigorous to let us get away with that, though. In theory, big O notation says nothing about any particular finite value, only about limits, and in practice, this manifests in big O notation's failure to predict big jumps in resource costs when internal limits such as cache sizes are exceeded. To create an abstraction as nice and well-behaved as big O notation, we have to gloss over the real behavior of the machine.
Is it not possible that one day we will invent a computer language that supports writing very "robust" (in the sense of source code sensitivity) programs?
If you apply an edit distance metric to source code and a behavior metric to running programs, it would take a ridiculous amount of work to write programs in any system where small changes in source code resulted in small changes in running systems. Also, very often people want small changes in input data to result in small changes in behavior, but just as often, they want small changes in input data to result in large changes in behavior, so we have external requirements to make some parts of our program "robust" and other parts extremely sensitive. A language would need to support both requirements.
I do believe we could simulate that, for some users, but we could never do it in any meaningful way in the context of this discussion.
For instance, we could make a language that interpreted "plus", "+", "adds", and "pslu" as addition operators. But that would only be increasing the amount of operators.
Even if we had an adaptive algorithm that would figure out what people meant in context, it would only reduce the amount of syntax errors.
What is really referred to here is the elements of the program. In this example, it would be our decision to add. If that elemental decision was wrong, the program would flip.
Another case is to consider numbers. If a letter needs to be mailed to every fifth address, and the elemental data, 5, is altered in any way, the program will fail. So while our algorithm could pick up 'fiev' and 'fifth', 4 or fourth will blow it.
Comments
In the discrete world of computing, there is no meaningful metric in which "small" changes and "small" effects go hand in hand, and there never will be.
This is a fascinating quote. What's the justification for it though? Is it not possible that one day we will invent a computer language that supports writing very "robust" (in the sense of source code sensitivity) programs?
Isn't that, in many ways, the opposite of what people want out of a programming languages? It seems to me that expressiveness, and robustness (in the sense that you define robustness) are inversely related.
Whenever a language comparison pops up, there's always a large contingent of people who argue for the superiority of a language because ideas can be expressed more concisely in 'their' language, but that necessarily means that some small change will have a relatively large effect.
There's also robustness in the sense that, e.g., BitC was trying to be robust, and that's something that I think is promising.
However, a concise, expressive, very high-level domain-specific language can make it impossible to express many idioms that would break the semantics of the domain.
As an analogy (I hesitate to use one because of the article), you could have a high-level representation of HTML that would make it totally impossible to generate <HTML></NOTHTML>, which is not the case if you use a general-purpose system. (not a foolproof analogy but anyway)
On formal principles, we'd expect that robustness and expressiveness are inversely related, on the principle that low-entropy data can be recovered with better fidelity than dense data, but I think I can name a counterexample to this principle in practice: I think Haskell does a phenomenally good job of being both expressive and robust if we consider a practical definition of robust, whereby pain is not measured by likelihood of error but the cost of an error. Compile-time errors are extremely cheap in comparison to run-time errors.
You want an "almost right" program to fail, but you want it to do so at compile time. Runtime silent failure is the worst.
How could it be possible? Let's assume that a "small effect" is something like a character change. Consider:
And, One character difference, exactly opposite meaning. Is it possible for such behavior to not exist in programming languages? I can't prove it, but I doubt it. I suspect it's inherent.You needn't choose "==" and "!=" for your equality and inequality operators!
That's true, but does it change my point?
Let me clarify. Consider if I instead chose equal and not equal as my operators. Now a "small change" probably won't even be a valid program (not wqual). Any small change that does result in a valid program is unlikely to result in an equally small behavior change for any interesting input. Changing a strictly-less-than to a less-than-or-equal-to is a small change that results in what seems like a small behavior change when viewed locally. But my own experience with programming is that a local change such as that will have huge consequences later on - often to the point that the program crashes.
Consider it this way: the space of valid programs is infinite. The space of valid programs that solve a particular problem is much smaller (in the physics << sense) than the space of valid programs. Any perturbation from a valid program that solves the problem is much more likely (>>) to land you on a valid program that does not solve your problem than one that does.
I agree with your intuition, but computer science is a mathematically founded discipline, so the kinds of claim Dijkstra was making about "robustness" require formalisation and mathematical proof if they are to be taken seriously.
Like you I find it very difficult to even envisage what a "robust" language would be in this sense. What I'd like is for someone to define the properties that one would have and then show that it can't exist :)
NB he is demonstrably incorrect on this point:
Like all digitally encoded information, it has unavoidably the uncomfortable property that the smallest possible perturbations —i.e. changes of a single bit— can have the most drastic consequences.
Error correcting codes do exist!
>>> Like all digitally encoded information, it has unavoidably the uncomfortable property that the smallest possible perturbations —i.e. changes of a single bit— can have the most drastic consequences.
>> Error correcting codes do exist!
He acknowledged this explicitly immediately after, on the next sentence:
> [For the sake of completness I add that the picture is not essentially changed by the introduction of redundancy or error correction.]
Think of what happens if a single bit is changed in the error-correcting part of the program.
You could once-and-for-all prove the error correcting program correct and then use it again and again for every program. But that wouldn't actually help getting programs correct. For example if your error correcting program was to write every program three times, then if one of the three programs gives a different answer you use the answer of the other two. Now a human writing a program would probably just write the same bug in each of the three versions, i.e. the three versions are not independent. You could have the three versions written by three different humans. But that doesn't solve the problem either because some errors are just likely to be made by all three of them (for example forgetting to check some edge condition somewhere). So again the three versions are correlated. Or worse the problem could be in the specification all three of them got. I don't think there is any way out of this.
Human DNA is a "robust language." Everything is encoded redundantly, and most features "express" through multiple small, additive gates (e.g. changing one bit of your DNA will never take your hair all the way from blonde to black, only make it slightly lighter or darker.) We could make a programming language that works similarly, though it would likely be very unintuitive.
Not everything is encoded redundantly. Try changing CGA to TGA in one of the exons of PAX6. In humans, this change will result in aniridia, the lack of an iris, an unstable corneal epithelium, and other problems. This is just one example, the one I'm familiar with. There are many other single nucleotide polymorphisms that can cause big changes.
DNA also has lots of garbage: genes that aren't expressed and are just along for the ride.
We think in continuous terms all the time when we use big O notation. If you have an O(n) (or O(n^2)) algorithm and make the input a tiny bit bigger, the computation becomes a tiny bit more complex. Dijkstra is too rigorous to let us get away with that, though. In theory, big O notation says nothing about any particular finite value, only about limits, and in practice, this manifests in big O notation's failure to predict big jumps in resource costs when internal limits such as cache sizes are exceeded. To create an abstraction as nice and well-behaved as big O notation, we have to gloss over the real behavior of the machine.
Is it not possible that one day we will invent a computer language that supports writing very "robust" (in the sense of source code sensitivity) programs?
If you apply an edit distance metric to source code and a behavior metric to running programs, it would take a ridiculous amount of work to write programs in any system where small changes in source code resulted in small changes in running systems. Also, very often people want small changes in input data to result in small changes in behavior, but just as often, they want small changes in input data to result in large changes in behavior, so we have external requirements to make some parts of our program "robust" and other parts extremely sensitive. A language would need to support both requirements.
I do believe we could simulate that, for some users, but we could never do it in any meaningful way in the context of this discussion.
For instance, we could make a language that interpreted "plus", "+", "adds", and "pslu" as addition operators. But that would only be increasing the amount of operators.
Even if we had an adaptive algorithm that would figure out what people meant in context, it would only reduce the amount of syntax errors.
What is really referred to here is the elements of the program. In this example, it would be our decision to add. If that elemental decision was wrong, the program would flip.
Another case is to consider numbers. If a letter needs to be mailed to every fifth address, and the elemental data, 5, is altered in any way, the program will fail. So while our algorithm could pick up 'fiev' and 'fifth', 4 or fourth will blow it.