A Parable by Dijkstra (1973)

https://www.cs.utexas.edu/users/EWD/transcriptions/EWD05xx/EWD594.html

by fpvsoop • 8 years ago

296 102 8 years ago

cs.utexas.edu

Cieplak• 8 years ago

Since we're talking about Dijkstra, thought I'd bring up the letter he wrote to the University of Texas when they replaced Haskell with Java in their introductory programming course:

https://chrisdone.com/posts/dijkstra-haskell-java

https://www.cs.utexas.edu/users/EWD/OtherDocs/To%20the%20Bud...

rcdmd• 8 years ago

Great letter (2001). It predictably focuses on language quality and side-steps practicality-- the assumption being practicality isn't as important as learning a high-quality language in an introductory course.

AnimalMuppet2• 8 years ago

Depends on what you think you're teaching. Are you teaching computer science, or are you teaching software engineering?

Hint: Of your graduates, probably 95% will work as software engineers, and only 5% will be computer scientists. But CS departments think they're computer science departments, even though they mostly are located in the college of engineering. (I accidentally typed "enginerring", which I thought was amusing...)

TeMPOraL4• 8 years ago

In a sense, those two are not conflicting, but reinforcing - practicality in software "engineering" usually means lowest-common-denominator, cheapest-workforce technology. It's good to have exposure to more powerful tools and ways of thinking, and the industry isn't likely to give you one unless you actively come looking.

ereyes01• 8 years ago

A very practical reason for preferring functional programming in a freshman course is that most students already have a certain familiarity with imperative programming. Facing them with the novelty of functional programming immediately drives home the message that there is more to programming than they thought.

While later on, he does gripe about language quality, I think this is the most salient point of that letter. It touches upon IMO one of the most misunderstood things about Computer Science- it's a science curriculum, not a vocational school. The best (only?) way to build practical skills is doing practical things and learning through experience. Computer Science is more about rigorous reasoning about programs and their mathematical properties.

While learning about practical things like building web apps is fine and well, universities are not well equipped for this sort of vocational curriculum. They are primarily institutions optimized for performing scientific research.

lr4444lr2• 8 years ago

I absolutely adore Djikstra's stubborn and always eloquent insistence on rigor and purity in CS education, his unabashed refusal to see even one tendril of its mathematical connections be sacrificed for mere code production efficiency. If this case isn't going to be made at the university level, then where?

Bromskloss• 8 years ago

I agree with you! Something I've wondered, though, is how he would propose writing a formal specification for, say, a graphical application. Does anyone know?

commandlinefan2• 8 years ago

One thing I noticed even decades ago when I was in school is that the education system - from kindergarten up until grad school - encourages "bare minimum" thinking. The goal is an A - if you happen to learn something en route to getting that A, great, but the goal is an A. Everything about the way things are structured encourages you to find the path of least resistance to that A. Now that I'm (much) older, I'm going back and trying to re-learn the things that I learned just enough to get by when I was in college, I wonder - if the curriculum had been more "rigorous", would I have learned more, or would I have been washed out?

dfxm12• 8 years ago

It seems like college taught you "how to learn", which I think is way more important that learning Haskell vs Java, etc., especially in a field as ever changing as Comp Sci.

I don't know how many decades ago you were in school, but imagine all those people who were "rigorous" with learning punch cards in 80s in depth, at the expense of getting a wider education...

ben5092• 8 years ago

GPA and class rankings do seem to be counterproductive measures if you're trying to get people to challenge themselves. The classes I got the most out of are the ones I got B's and C's in, or even had to redo in one case.

It definitely makes more sense if you look at the idea of the "sheepskin effect" where the degree is not a signifier of material mastered, but a signifier that you are a good worker. In that case, what you learn is generally far less important than whether you work well on a team. And a high GPA means you are orderly, methodical and conscientious.

bmer• 8 years ago

For those who want to see Dijkstra's mathematics of programs in action:

1) basic (great for kids, math novices, whatever): https://www.amazon.com/gp/product/0470684534/ref=dbs_a_def_r... (ignore the two star review, this book would get 5 stars from me)

2) advanced (free, complete with videos): http://www.cs.toronto.edu/~hehner/aPToP/

3) advanced: https://www.amazon.com/gp/product/0470848820/ref=dbs_a_def_r...

4) advanced, theoretical, from the man himself: https://www.springer.com/gp/book/9781461279242

jonsen2• 8 years ago

Ad 1) Two five-star reviews on amazon UK:

https://www.amazon.co.uk/Algorithmic-Problem-Solving-Roland-...

jonsen2• 8 years ago

5) advanced: https://www.amazon.com/Science-Programming-Monographs-Comput...

User23• 8 years ago

Also advanced, but quite readable: https://www.amazon.com/Discipline-Programming-Edsger-W-Dijks...

mcguire8• 8 years ago

Also, slightly less advanced:

A Discipline of Programming

https://www.amazon.com/Discipline-Programming-Edsger-W-Dijks...

For more practical fun, consider Frama-C, SPARK, and Dafny.

madhadron• 8 years ago

I learned this stuff from Roland's 'Program Construction'. Great book. Once you've been through that, then suddenly Dijkstra's writing becomes really practical.

forapurpose• 8 years ago

I thought the moral was going to be that accommodating toiletless cars cost more than simply building all cars with toilets.

squirrelicus• 8 years ago

I feel like that's still the point irrespective of Dijkstra's apparent view on the parable. Creating exceptional cases is the best way to increase costs.

djsumdog3• 8 years ago

Yea, that's where I thought it was going too. I've been on a lot of project lately that try to pre-optimize instead of building a solution and then determining where the bottlenecks are.

A lot of times when we try to build for speed, the real bottlenecks are no where we think they'd logically be.

neilwilson• 8 years ago

There's politics involved as well. The solution creates units that all have toilets without countermanding the commercial directors initial edict. Programmers sometimes have to triangulate too.

mcguire8• 8 years ago

With the end solution, a passenger is only one car length from a toilet (which would be the case if toilets are at the end of cars for structural reasons anyway) and they only pay for toilets in half of the cars.

ben5092• 8 years ago

I think he understates the cost of putting a toilet in a car, as it takes up space that could accommodate fare-paying passengers.

simplecomplex2• 8 years ago

Moral: The engineer who conceived of the innovation was forgotten and not compensated for it, and the train owners made the bulk of the money.

Sounds like software engineering to me!

djsumdog3• 8 years ago

The more things change, the more things stay the same.

TeMPOraL4• 8 years ago

Also, note how the shunting department was severely underequipped, "and it was only by virtue of the most cunning ingenuity, that they could just manage". Also sounds very realistic to me.

That, plus a manager inventing and enforcing specific requirements for dubious reasons, causing trouble in the company, and - as 'jancsika points out in their comment - quite likely introducing many new problems into the product.

SilasX• 8 years ago

Nah, it'd be more realistic if they were stuck with this expensive mess, and had to reverse all their work, and still had to do one toilet per car, because no one figured out this solution.

And the one guy who would have thought of this, they passed on three months before because he wanted 10% more in salary.

/cynicism

DaveInTucson• 8 years ago

I feel like the actual moral of the story should be "don't underestimate how trying to scrimp on a vital resource can result in horrible logistical complexities and a nightmare UX".

vanderZwan• 8 years ago

It's one of those parables with enough depth to support a ton of interpretations and morals

mcguire8• 8 years ago

...which can be solved by a simple innovation, given the right approach.

rossdavidh• 8 years ago

All true, but I would add that "in order to get back to the previous system that actually worked, you may have to provide a fig leaf for management, so that they can pretend no such thing is happening." We are back to one toilet per car, but we have to use cars of twice the size (with superfluous coupling in the middle that is never uncoupled) in order to pretend that we did not go back to the original system.

pr_millipede• 8 years ago

I don't quite understand why 'true mathematicians' fail to get the point. Any ideas?

f2f• 8 years ago

true mathematicians don't do practicality. https://xkcd.com/435/

Sniffnoy• 8 years ago

Because you get to the solution and you say, "But that's just the same thing..."

djsumdog3• 8 years ago

It's like the joke with boiling the pot of water and just dumping out the water; reducing it to the previous problem with a known solution ... or something like that...

epx2• 8 years ago

So in the end the permanently coupled tuple of cars is handled as a single car, it kind of proves that every car must have a toilet? Or perhaps the next manager reiterates the rationale and decides to put just one toilet every two car tuples...

mcguire8• 8 years ago

But twice as long and articulated.

epx2• 8 years ago

Yes, the articulation is the only difference from a span-bolstered car with 8/12 axles.

sus_0072• 8 years ago

Is Haskell still a preferred introductory language to enter the Functional Paradigm with? Or do you think other alternatives do a better job at that than Haskell ? I'm learning Scheme with the SICP Book ATM, and am confused where to go next to get better at Functional thinking(and programming).

simplecomplex2• 8 years ago

Haskell. If programming languages were mountains, Haskell is Everest. Conquer it and other languages can be mastered in your sleep.

Go further.

frabert• 8 years ago

I never did alpinism, I guess Everest would be a good place to start with...

pyrale• 8 years ago

I'm not sure the mountain allegory is fitting here.

Haskell is not that hard to get into: there are hard parts but they are totally optional and avoidable.

Also for newcomer who want to get in fp but find Haskell intimidating, you can try Elm, it's tailored to cater to beginners.

merijnv• 8 years ago

Is Haskell still a preferred introductory language to enter the Functional Paradigm with?

I say yes, for a two reasons. 1) Enforced purity means you can't just fall back to your old imperative style as coding and use it as a crutch, and 2) it's the "most different" functional language, it will expose you to more than just functional programming and thus teach you more.

Learning Haskell will teach you: pure functional programming, algebraic datatypes, laziness, and ML-style types. All of which are worthwhile imo.

ML-style typing and algebraic datatypes you could also learn in F#/Ocaml/SML, but pure FP and laziness are two things that are very much worth learning and only apply to a handful of languages. And of that handful Haskell is really the only one with an ecosystem and community that makes it practical to write actual projects in.

sus_0072• 8 years ago

Thanks for the detailed explanation. I'll surely learn Haskell now, after I'm done with this book.

jancsika3• 8 years ago

When the shunting person persuaded everyone to imagine the two-car units as if they were symmetrical, the passengers still complained. Toilets can break, and when they did the doubly unlucky passenger would be forced to walk four car lengths to get to the nearest toilet.

Also, those helpful arrows would be guiding the passenger the wrong direction for two of those car lengths.

So we have comments that go out of sync with the running program, a spec that lies about reality, and an implementation that doesn't match the spec. Yep, that sounds like programmers to me.

Legit parable.

Edit: just realized the least lucky passenger would have to walk six car lengths. If the passenger is already at the wrong end of the "symmetrical" two-car unit with a broken toilet, the arrow will point them in the direction of the broken toilet. If the broken toilet is the last car, then they must walk back two car lengths to get where they started. Now if the next two-car unit is turned the wrong direction they must walk two more car lengths.

So add to this a spec that's difficult to reason about.

Again, legit programmer parable.

mikorym4• 8 years ago

the least lucky passenger would have to walk six car lengths

I just want to elaborate on this to show which assumptions you are making. There are two ways to make a paired unit: --+ and -+-.

In your scenario I think you assume the first. The end of the train is thus ...+----+, since you mention the second last car's orientation being reversed. The +'s represent toilets. Then, what you are saying is to consider a passenger located at the ^ symbol: ...+--^--+. In this configuration, your observation makes sense.

I do think that a more practical solution is to work only with (-+,-) pairs. The symmetry that Dijkstra talks of is then that (-+,-) and (-,+-) are equivalent for the purposes of the problem. Then an end of a train would be: ...-+-+-. This is then the "extra few feet" that he talks of.

mikorym4• 8 years ago

Correction on the second last sentence: "...-+--+-".

mannykannot3• 8 years ago

Yes, though I think the last three feet refers to the vestibule connecting the two carriages, which a passenger in the non-toilet carriage must traverse.

mcguire8• 8 years ago

Indeed. Dijkstra specifies two cars joined with the toilet in the middle:

"When each car with a toilet was coupled, from now until eternity, at its toileted end with a car without a toilet, from then onwards the shunting yard, instead of dealing with N directed cars of two types, could deal with N/2 identical units that, to all intents and purposes, could be regarded as symmetrical."

jancsika3• 8 years ago

I just want to elaborate on this to show which assumptions you are making. There are two ways to make a paired unit: --+ and -+-.

Why are there three characters to represent a pair?

Do you mean something like this:

car with toilet: [+-]

car without toilet: [--]

my pair: [+-][--]

your pair: [-+][--]

This is then the "extra few feet" that he talks of.

Using my notation (sorry to flip it):

[-+][--][-+][--]

That's four cars. If someone is sitting at the right end of car #2, they have an arrow pointing them to car #1 for the toilet. If that toilet is broken, then they must walk back through car #2 all the way to the end of car #3.

But I may be misunderstanding your initial notation.

oblib• 8 years ago

The greater point I took away was that sometimes someone who's not involved in solving a problem can see a solution while those who are do not.

In that respect programming is often as much an art as it is a practice.

praptak• 8 years ago

The director got fired for causing actual losses and the shunting yard workers got huge bonuses and promotions for saving the company, right? Right?!

sanbor2• 8 years ago

Almost. The director got the bonus and the yard workers got more work.

konschubert• 8 years ago

I'll bite. What's the morale that he's implying?

That algorithms can be simplified by slightly lifting the constraints?

B1FF_PSUVM• 8 years ago

That some problems can be solved more easily with a different data structure.

I think it was Robert Tarjan that wrote a book on that topic, but I can't find it.

TheOtherHobbes• 8 years ago

This solution is wrong.

Rolling stock needs maintenance, and if you keep units permanently paired you can easily run out of units.

In fact there is no easy solution given realistic business constraints. You can either put toilets in every car, which has a cost because it reduces available seating. In the best case you’ll lose money because of the lost seats. In the worst case overcrowding will make the toilets ineffective.

Or you can buy enough spare units to allow for maintenance, which has a larger up front cost, and continuing costs in terms of stabling, and possible issues with shunting yard size.

Working out the most efficient answer given real trains, real passenger loads, likely future passenger loads, and shunting yard constraints, is not a trivial problem.

Unlike Dijkstra, some of the managers in his audiences will have understood this. It’s no wonder they found his glib hand-waving annoying.

The actual lesson of the parable is the opposite of the one Dijkstra is making: the real world is hard, and if you think a solution fits neatly into a trivial software construct, you’re almost certainly wrong.

zaphar• 8 years ago

It's a parable which means it is fiction that that ignores details to make a point. As such it does it's job quite well unless you yet to read more into it than the author intended.

sethrin• 8 years ago

To me this says that parables are fairly useless: with enough padding any trivial insight may seem wise. I can't at the moment imagine something that I would think important to communicate which would be made more clear by a parable. I would also be concerned about being patronizing. I'm sure this makes good fodder for academic quibbling, but I am beginning to doubt whether Dijkstra was more insightful than arrogant.

dredmorbius• 8 years ago

All metaphors melt if you push them loudly enough.

contingencies• 8 years ago

For me, one moral of the story is when approaching any issue in a live system, it often pays to go back to modeling the actual problem instead of iterating on broken assumptions. Good solutions should have documentation which explains their take on the problem and the reason the solution in particular was chosen versus other potential designs.

Of course, outsourcing, interdepartmental or interpersonal politics can create commercial misincentives to remove such time and money saving features...

tw1010• 8 years ago

I don't get it. (And I don't think it's because I'm a "true mathematician".)

coldtea2• 8 years ago

With growing size or sophistication of the program, the operational argument quickly becomes impossible to carry through, and the general adherence to operational reasoning has to be considered one of the main causes of the persistence of the software crisis.

What "software crisis"? Since its inception in the 50s or so, software has only gone from strength to strength.

brazzy2• 8 years ago

https://en.wikipedia.org/wiki/Software_crisis

mcguire8• 8 years ago

Projects running over-budget

Projects running over-time

Software was very inefficient

Software was of low quality

Software often did not meet requirements

Projects were unmanageable and code difficult to maintain

Software was never delivered

Yeah, that one.

JacKTrocinskI• 8 years ago

KISS - Keep It Simple Stupid and put a toilet in each car of the train.

mcguire8• 8 years ago

Because it is cheaper than the cost of figuring out how to do it the other way?

tzs• 8 years ago

Note that the arrow solution failed because to the shunting yard the cars were immutable objects. They could only control the direction of the arrows in the non-toilet cars by how they oriented the whole car when they composed it into the train they were building.

If the non-toilet cars were made mutable, specifically if they were made so the arrows could be reversed, then the shunting yard could compose the cars without regard for the orientation of the non-toilet cars, and someone later could go through and set the arrow directions. I'd guess there is some sort of preload inspection done by the crew, which might be a good place to handle setting the arrows.

dacracot2• 8 years ago

The math is simple. This did not require a mathematician, just an cost benefit analysis.

($ * toilet each car) < shunting{($ * action * yard) + ($ * training * employee)} + ($ * accident cleanup) + ($ * customer bad will)

ufo• 8 years ago

Read until the end again. The solution they came up with still only put toilets in 50% of the cars.

dacracot2• 8 years ago

And from a system perspective, I would wager that the cost is still higher given the complexity of their final solution.

xamuel• 8 years ago

The final paragraph is my favorite. I have a PhD in mathematics but I've since realized I'm not a mathematician, I'm more of a logician/philosopher. I find the parable very interesting, but I can totally believe a lot of real mathematicians don't. Too many mathematicians, if you crack open a random page of their work, you'll see lots of opaque integrals and calculations. None of that ever appealed to me. Even when I was the top of the class among undergraduate mathematics majors, I was basically doing the bare minimum I could get away with of that kind of "grind", and focusing all my time and passion on things more closely resembling this kind of "parable".

contravariant• 8 years ago

I don't think he was saying mathematicians don't find it interesting because it lacks sufficiently convoluted mathematics.

Rather a 'true mathematician' (who by definition ignores all practical considerations) would find it unsatisfactory because the problem of finding a way of allowing toilet-less carriages is solved by not allowing toilet-less carriages.

Frankly I think they should have just put the toilet in the middle of the toilet-carrying carriages, but maybe I'm weird.

CamTin• 8 years ago

I guess the ultimate solution assumes that all the turntables are long enough to deal with at least two-car consists? Seems strange that the company would cheap out on a little bit of porcelain in each car and then overprovision its turntables in such an extravagant way.

hnal9432• 8 years ago

I thought that originally as well. However I'm not sure that the cars both need to be on the turn table to remain paired. If cars #45 and #44 are paired, can we repeat the turntable operation to keep them oriented in the same way without needing to generically solve the problem of car orientation?

mannykannot3• 8 years ago

With the toilet at the end of the carriage that is connected to its corresponding non-toilet carriage, and consequently approximately in the middle (the offset is the "last three feet" that Dijkstra mentions), there is no longer a need to reverse any two-carriage set.

mayoff• 8 years ago

Turntables are not just for reversing. A turntable also moves cars (and engines) between multiple tracks and storage facilities. Two-car sets need to be moved even if not reversed.

dokem• 8 years ago

There is no longer a need to perform rotations on the car tuple because it can be treated as symmetrical.

Finster• 8 years ago

This seems like it has potential for being the core of an interesting interview question. Maybe something along the lines of "You are hired as the Chief Shunter (lol) of a new rail company and the CEO, to cut costs, has stated that only half of all cars will have toilets. What instructions will you give the shunters? What complications could arise? What is the optimal solution and how would it impact UX?" etc. etc.

sanbor2• 8 years ago

Often people is nervious at job interviews. It might not be the best place for this sort of creative problems.

ggchappell• 8 years ago

I have told the above story to different audiences. Programmers, as a rule, are delighted by it, and managers, invariably, get more and more annoyed as the story progresses; true mathematicians, however, fail to see the point.

I see the point. In fact I'd go so far as to call myself "delighted". But I thought I was a true mathematician.

'Scuse me while I go have a little existential crisis.

victorNicollet• 8 years ago

TGV trains in France have a very strict structure. For the TGV atlantique lines, for example, "short" trains contain exactly 10 cars (and "long" trains are composed of two "short" trains), with the following distribution:

- Car 1 and 10 are engines, and include some second class seats. - Cars 2 and 3 are first class. - Car 4 is the bar-restaurant. - Car 5 is first class. - Cars 6, 7, 8 and 9 are second class.

All the infrastructure is designed to treat the train as a single unit, during all operations at the shunting yard, in repair workshops, and son on.

And the position of toilets (including special toilets for nappy changes) is fixed.

A Parable by Dijkstra (1973)

Related Stories