So I'm reading through "Notes on structured programming" in which Dijkstra lays out the concept of a coordinate system to identify a discrete point in a computation process. Basically, this is what you want your stack trace to be, something blows up, and you want to know as much as possible about when and where exactly things went awry.
In the context of understanding programs he notes how a mathematical theory and a computer program are both structured, timeless objects, but while the mathematical theory makes sense on it's own, the program doesn't make sense until its execution. With this in mind, he describes a way to decompose programs in such a way that it becomes easier for humans to make sense out of them. For this purpose, he distinguishes three types of decomposition: concatenation, selection and repetition.
We have now seen three types of decomposition; we could call them "concatenation", "selection" and "repetition" respectively. The first two are understood by enumerative reasoning, the lost one by mathematical induction.
- Dijkstra, notes on structured programming.
Concatenation is used to decompose computations directly following each other, selection is a way of decomposing computations that are executed based on a condition and repetition is the decomposition of computations that are in a loop.
Now, with these 3 types of decomposition, it becomes easier to read and understand a program because once you decompose a number of computations, you can then mentally abstract it, and view it as a single step.
Once we have a properly decomposed program, we want to be able to make assertions about its computations, we want to know what value a certain variable has at a certain point in the program, during its execution. To be able to do this Dijkstra explains:
In short, we are looking for a co-ordinate system in terms of which the discrete points of computation progress can be identified,... We can state our problem in another way. Given a program in action and suppose that before completion of the computation the latter is stopped at one of the discrete points of progress. How can we identify the point of interruption, for instance if we want to redo the computation up to the very same point ?
- Dijkstra, notes on structured programming.
As far as the concatenation and selection decompositions are concerned, it is trivial to do this by using what Dijkstra calls the textual index of the program text, in other words, the line number. However, as we all know, due to the nature of loops, the same does not hold true for the repetition decomposition. Simply because a loop iterates over the same computations (with the same textual index) several times, the textual index is of no use to us for the purpose of indicating where we are in the computation progress. The solution ? Introduce a dynamic index, a variable independent from the computation that keeps track of where exactly in the repetition we are. OK so now we almost have a coordinate system as described above, there's just one more concept that isn't covered yet,... functions. When a language allows for functions, we need a way to represent the exact point of progress where our function is called. A textual index won't suffice, since it is lacking context, however, we can pass along the textual index of where our function was called.
Mix all the above together, and you get a perfect stack trace which would give you:
- the line number of the call producing the error
- if the error-producing call is part of a function, the line number of the call invoking this function
- if the error-producing call is nested in any loops, the dynamic index indicating the specific iteration of those loops
Regardless, that's an interesting bit of history right there, and I'm only on page 29 :)
No comments:
Post a Comment