Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Dijkstra is not talking about stack traces. Structured programming is not just about functions, it is also control structure blocks like if or while-blocks instead of goto's, which does not affect stack traces.

Dijkstra is talking about describing and analyzing the execution of a program. With structured programming, the execution of a program can be described as a tree of executed blocks. A program using goto's is a tangled graph, since every point can jump to any other point. This makes it much harder to describe and analyze.

I doubt Dijkstra cared much about stack traces, since he didn't care for debugging at all. For him, programs was something you analyzed on paper and proved correct.

As for gotos being constrained to a single function, this does not make any difference for Dijkstras point, since a single function can still contain the same complexity as a whole unstructured program.



(Imperative) Programs cannot be pure trees, looping constructs necessarily introduce cycles. What structured programming is all about is to make those cycles as well-behaved as possible.

You are largely right nonetheless, Dijkstra's argument could be summarized as:

1- Understanding code depends on imagining it's dynamic effects from its static description

2- As we progressively make code more powerful (executing single statements in sequence -->+ executing either of two statements depending on the current state -->+ aggregation of statement blocks into subroutines -->+ looping constructs); the job of the entity reading your code becomes progressively harder as it tries to reason about: a List -->+ a Tree -->+ a generalized extra-recursive tree where nodes are themselves trees -->+ that last kind of tree but with cycles.

3-GoTos create especially-nasty uber-unpredictable networks of cycles while adding no more power than other well-behaved options.

The essence of the argument is a tale as old as time: increasing the Freedom of Expression for the writer increases the Burden of Understanding on the reader.

Stack traces, in a generalized kind of way, is another equivalent form of describing Dijkstra's argument. The previous way of explaining Dijkstra's argument imagines an idealized reader (could be an actual person, a static-analysis tool trying to predict some property of your code, or any other "reader") and asks you to consider the complexity of the data structure it tries to construct to mentally represent your program in static form.

Now imagine it the other way: the reader is seeing your program's dynamical behavior in a "debugger" (could be an actual debugger, could be a sheet of a paper with a bunch of trace tables,...), how does the amount and complexity of the data structures that this idealized reader needs to follow the behaviour of your code scales as the complexity of your code scales? For purely sequential programs , that 's just a single counter keeping track of where we're in the program . Add conditionals, and you now have to keep track of a flag indicating for each line which branch was taken. Add blocks or subroutines , and you are now maintaining a whole stack of such counters/flags.

So far, so linear, you are still limited to incrementing counters, raising flags, and adding or removing counters/flags from the top of the stack. But you're never decrementing counters (going back to a previous point in execution) or touching the stack in the middle. Gotos and loops destroy this: Gotos are the worst of the pair as it arbitrarily jumps you to any counter on the whole stack without even recording the point of return. The whole concept of an "execution stack" becomes meaningless, program execution is a graph that you maintain in your head (or in the debugger) as it threads through the code. Other looping constructs are more well-behaved in that they state beforehand that a jump will happen and also the fixed whereabouts of its destination. The argument is that since different constructs give you the equivalent power but complicate your code's dynamic behavior asymmetrically, you should choose some of them and ban others.

The first version of the argument imagines code understanding as a writer-reader dynamic and talks about the reader reasoning about the static form of the programs written by the writer, the second imagines it as a dancer-viewer dynamic and talks about the viewer following the flow of the program orchestrated by the dance choreographer (the programmer). Two ways of saying the same thing.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: