Name: Structured Programming
ISBN: 9781478375807

What Hacker News says

akiarieApr 2024

Yes, the code example you've given is exactly in the direction we're thinking. (Edit: thought it can't be verified yet.)

We haven't documented the algorithm because it's not the unique part of what we're doing. It works in a very simple-minded way, analysing possible states.

The interesting part is the insight that function interfaces are the boundary along which verification should take place. Applying this idea consistently we escape the combinatorial explosion which tends to plague efforts in this area, because every function can be verified by itself. Notably, Dafny recognised this point before us, and the earliest clear statement we can find regarding it is in Dijkstra's "Notes on Structured Programming", in his chapter "On a Program Model". You may find that illuminating read.

I'm no expert on Clang/GCC and the new annotation syntax for C and C++, but from what I've seen it's not general enough for what we're trying to achieve in Xr0. The safety semantics which are expressed in annotations in Xr0 (see [0] for an example) get very detailed.

[0]: https://xr0.dev/learn#initialisation-of-memory-and-the-clump

thread

danoloanSep 2020

read Dijkstra's "Structured Programming". it will improve your programming reasoning.

thread

MaysonLSep 2012

Try "A Discipline of Programming" and "Structured Programming" by Edsger Dijkstra (the second with co-authors C. A. R. Hoare & Ole-Johan Dahl).

Also, Project Oberon by Niklaus Wirth, for showing how it can be done well and clearly.

SICP and How to Solve it, as others have recommended, are also great, ditto Project Euler.

thread

needfishAug 2026

Hi, CS graduate here. during my post-graduation unemployed year I have been wrestling with this question a lot. The answer is that there is none - the research on the practice of translating requirements into code has stopped in the 1970s with Structured Programming (Dijkstra) and Problem Frames (Jackson). There is a certain inspiration people had with reusable patterns of problems a la Alexander, but after some time people got lost in the Java enterprise world and started making "design patterns" (which has very much dominated the online space and I cannot search properly for general software design anymore). The second problem is with Clean Code, which to me is a really bad set of "if you know you know" hand-wavy advice that is purposefully vague, because observable, actionable advice is actually very hard to come by.

I think when people say software engineering, they confuse the high level designs (server, caching, db, etc. generally interaction constraints) and the lower level designs (modules, abstractions, classes, data structure design). There is a lot of content on the former but really few on the latter - which is some people cannot write new code, but can work on existing systems fine. Two main problems is 1. How to break down the problem at hand and 2. Organizing data into abstractions, and often creating new ones.

For (1) the advice everyone resorts to is "just do more" and rely on pattern recognition, because you can't really break down a thing you haven't seen nor can relate to what you've seen before. But there is [A Framework for Decomposition in Computational Thinking](https://www.researchgate.net/publication/334579725_A_Framewo...) that's the best attempt at it so far in my opinion. Some other approaches involve observation from ideal user flow and software ideal behaviour, or UI wireframing to see what elements should be there.

For (2), this also has the problem of organizing (which code goes into which file, which function does this belong to) and naming. For organizing data, I will recommend [The Many Forms of a Single Fact](https://www.bkent.net/Doc/manyform.htm) and the first chapter of [Data and Reality](https://cmpct.info/~calvin/Papers/Data%20and%20Reality.pdf) to see how impossible it is to create exactly correct representations in code. In areas that's entirely inside the box (e.g graphics) people don't often deal with messy representations of real world domains, but in business software they will do much more.

On the naming side, the first chapter of [Elements of Clojure](https://elementsofclojure.com/) was a really good attempt, making me realize it is way deeper into philosophy than anyone would like to wander in.

That said, the way software engineering discussion has been so far is very much influenced by the programming languages of the time (see Java), and so my recommendation is to try to learn concepts of organization independently, and see what its workaround is in your active language (e.g algebraic data type is sometimes useful, and people try to do it with sealed classes in Kotlin or interfaces in TypeScript). Once you have a good grasp of one tool (with all their warts, they all have pains), you'll find the capability to experiment.

thread

mschoenertFeb 2025

This prime generating code has fascinated me for a while.

It was first described by E.W. Dijkstra "Notes on Structured Programming (EWD249), 2nd; 1970; TH Eindhoven". https://www.cs.utexas.edu/~EWD/ewd02xx/EWD249.PDF

And then reformulated by D.E. Knuth "Literate Programming; 1984" http://www.literateprogramming.com/knuthweb.pdf

Both use it to demonstrate their way of deriving and documenting an algorithm.

And then R. Martin used it again in his book "Clean Code; 2008". (Though I'm not 100% certain what he wants to demonstrate with his rather difficult formulation.)

For the sake of this email I am going to call it "Dijkstra's algorithm".

If we look at it from an engineering perspective, then Dijkstra's algorithm is never the best choice (at least not in 2025).

If performance is not the most important aspect, e.g. if we need less than 100000 primes, then the straightforward trial division is just as fast - and soooo much simpler (basically impossible to get wrong). Note that this is different in 2025 than it was in 1970, back then multiplications and divisions were much more expensive so it made sense to minimize them.

If performance is the most important aspect, then the sieve of Eratosthenes is much faster. And you can implement the sieve with a sliding window, which is just as fast (or even a bit faster because of caching) and uses a bounded amount of memory.

Concretely - my implementation of the sliding window sieve of Eratosthenes is about 50 times faster than Dijkstra's algorithm (on the same machine) when generating the first 200 million primes (7.5 sec vs 6 min).

The reformulation - both by Ousterhout and Martin - computes multiples for every new prime found. This will quickly lead to overflow, e.g. the 6543-th prime is 65537, so its square will overflow 32 bit unsigned integers. Dijkstra's formulation on the other hand only computes multiples that are actually used to filter, the multiples are never (much) larger than the candidate.

Note that computing the multiples so eagerly will also make the multiples vector unnecessarily large (wasting memory).

Knuth and Dijkstra both remark that there is a subtle problem with the correctness of the algorithm. When incrementing lastMultiple and then later accessing primes[lastMultiple] und multiples[lastMultiple] it is not obvious that those will already be assigned. In fact they will be, but it is very difficult to prove that. It is a consequence of the fact that for every integer n there is always a prime between n and n*n, which follows from Betrand's theorem, a difficult number-theoretical result.

So if you look at Ousterhout's and Martin's reformulation and think "a yes - now I get the algorithm", then beware: You've missed at least two aspects that are relevant for the algorithm's correctness. ;-)

thread

rramadassFeb 2023

Whenever somebody says something, one has to consider their Competency, Context and Time to read between the lines and try and get at the gist of what is being intended rather then the mere words themselves.

This is orders of magnitude more important when we try to understand "The Greats" (in any field) because they have a certain insight into things, a huge knowledge base to draw upon and are aware of myriads of nuances involved in their domain of expertise all of which we poor students have to struggle to grasp.

It is with the above points in mind that one should interpret Knuth's nuanced quote above. He had the highest of regards/respect for Dijkstra (see his detailed review (pdf) of Dijkstra's book "Structured Programming" at http://infolab.stanford.edu/pub/cstr/reports/cs/tr/73/371/CS...) Given that Donald Knuth is the "Patron Saint of Yak Shaves" (https://yakshav.es/the-patron-saint-of-yakshaves/) his perspective did not allow a fully mathematical abstraction without any reference to a machine (real or virtual). Note that he did not deny Dijkstra's approach but merely wasn't agreeing with Dijkstra's strident promotion of it. That is a viewpoint and not a value judgement.

Coming back to the points above;

[1-3] - One has to remember that when Dijkstra did these almost nothing that we take for granted today existed. Everything had to be built from ground-up. You can imagine the difficulty when you have nothing/nobody to learn from and are basically inventing stuff as you go along. You only had Mathematics as a stable bedrock.

[4] No, he pioneered it. Wikipedia actually credits him with coining the very term "Structured Programming" (https://en.wikipedia.org/wiki/Structured_programming#cite_no...) Regardless, he wrote EWD249 "Notes on Structured Programming" in 1969. Also see EWD1308 "What led to Notes on Structured Programming".

[5] Most people misunderstand what is meant by "Correctness" in a Computer Program. Perhaps Bertrand Meyer's synonym of a "Contract" is better suited to explain that what is meant is "Correctness w.r.t. Specification". Obviously this is fundamental to Programming itself. To get the benefit of this approach you don't have to go 100% rigour (rather difficult) but train yourself to think in these terms and using appropriate pre/post conditions. A good example can be seen in the use of Design-by-Contract syntax in Eiffel. Here is Dijkstra from EWD288 "Concern for Correctness as a Guiding Principle for Program Composition"

My thesis is, that a helpful programming methodology should be closely tied to correctness concerns. I am perfectly willing to admit that I myself may be the most complete victim of my own propaganda, but that will not prevent me from preaching my gospel, which is as follows. When correctness concerns come as an afterthought and correctness proofs have to be given once the program is already completed, the programmer can indeed expect severe troubles. If, however, he adheres to the discipline to produce the correctness proofs as he programs along, he will produce program and proof with less effort than programming alone would have taken.

Finally, a word or two about a wide-spread superstition, viz. that correctness proofs can only be given if you know exactly what your program has to do, that in real life it is often not completely known what the program has to do and that, therefore, in real life correctness proofs are impractical. The fallacy in this argument is to be found in the confusion between "exact" and "complete": although the program requirements may still be "incomplete", a certain number of broad characteristics will be "exactly" known. The abstract program can see to it that these broad specifications are exactly met, while more detailed aspects of the problem specification are catered for in the lower levels.

[6-7] Your comment "Notably, none of his accomplishments in 1-3 were attained according to the methodology he advocated later in life as the only possible one" is exactly the wrong inference to draw! It is precisely due to this formative experience that he was such a strident proponent of the use of Mathematics in Programming. As pointed out above, he had to invent a lot of this stuff as he went along and had nothing other than mathematical logic to aid him in his endeavour. Dijkstra actually said he was "slow" to understand the works of Floyd/Hoare/Others on Program Correctness techniques. But of course once he got involved, he took it to the next level.

In summary, read Dijkstra, try and get at what he intended to convey rather than the tone/words (which are irrelevant in the broader scheme of things) and put forth effort to understand what has been said/written down. The rewards are great.

thread