12 ms·

Letters between Backus and Dijkstra (1979)

237 points by acidflask 10y ago

weinzierl 10y ago
This is a series of cell phone shots of an exchange of letters between Backus and Dijkstra. There is no transcript and some of the letters are hard to read, especially the handwritten ones. I only skimmed it but it is definitely an interesting read. I didn't interpret their stance as arrogant though. In my book both are enthusiastic about their subject and think the other party is misguided. Both take some effort not to hurt the others feelings while still bringing their point across.
- acidflask 10y ago
  The title "This guy’s arrogance takes your breath away" is taken directly from Backus's own description of this collection of letters. I've changed the title to make clearer that it is a direct quotation. Unfortunately, the Library of Congress does not allow scanners without prior approval, so this was the only way I could make my own copies. It did not help that all these letters were written or typed on very thin mimeograph paper.
  - weinzierl 10y ago
    Thanks for making these letter public! I missed that the quote was Backus's, it makes a lot more sense now. The quality of your photos is excellent and I doubt a scanner would make them much better. I wish there was a transcript though. As a start, here is the first letter transcribed: to John Backus International Business Machines Corporation 5600 Cattle Road SAN JOSE CA 95193 U.S.A Monday 29th of May, 1978 “To interrupt one’s own researches in order to follow those of another is a scientific pleasure which most experts delegate to their assistants.” (Eric Temple Bell in “Development of Mathematics”) Dear John, I do not claim to be more noble or sensible than “most experts”; perhaps it is only becauseI have only one assistant to whom I can delegate no more than one man can do. But when you open your letter with: “I am quite sure that you have never read any paper I’ve sent you before” it is my pleasure to inform you that - although “quite sure” - you were very wrong. I very well remember that you mailed me a sizeable paper on reduction languages to which I owe my introduction to that subject. I didn’t only read it, parts of it were even studied. I also remember that it left me with mixed feelings. I can very well understand your excitement, although, for lack of experience, I still cannot share it. I am far from delighted with the state of the art of programming today, and anyone suggesting an alternative has in in [sic] principle my sympathy - until, of course, he loses it again, like Terry Winograd did when he suggested natural language programming - “natural descriptions”! - as an alternative-. In the long run I have more faith in any rephrasing of the programming task that makes it more amendable to mathematical treatment. But you must have lots of patience, for the run will be very long. It isn’t just mental inertia - that problem can be solved generally by education a new generation of youngsters and waiting until the old ones have died - . It is the development of a new set of techniques needed to achieve a comparable degree of proficiency. Could you get me a copy of G.A. Mago’s (not yet published) “A network of microprocessors to execute reduction languages”? That might whet my appetite! From various angles I have looked into such networks and I am not entirely pleased with what I have seen. Firstly I suspect our techniques for proving the correctness of such designs: each next proof seems to differ so much from all the previous ones. I suspect I discovered that all I could design were special purpose networks, which, of course, made me suspect the programming language in the Von Neumann style which, already before you have chosen your problem, seems to have set you on the wrong track. Semantically speaking the semicolon is, of course, only a way of expressing functional composition: it imposes the same order that can also be expressed with brackets - innermost brackets first -. In combination with the distribution you can generate many innermost bracket pairs, thus expressing very honestly that it is really only a partial order that matters. I like that, it is honest. When you write “one can transform programs [....] by the use of laws [...] which are _part of the program- ming language_” etc. I am somewhat hesitant. I am not convinced (yet?) that the traditional separation in fixed program, variable data and assertions is a mistake. The first and the last - program and assertions - are somewhat merged in LUCID, in which correctness proofs are carried out in (nearly) the same formalism as the program is expressed in. On the one hand that presents a tempting unification, on the other hand I thought that mathematicians speerated carefully and for good reasons the language they talk about and the metalanguage in which they do so. To put it in another way: given a functional program, I feel only confident if I can do enough other significant things to it besides easy[striked out three times] carrying it out. And those I don’t see yet. The almost total absence of redundancy is another aspect of the same worry. In the case of a traditional program we know how to make it redundant: by inserting assertions, combination of text and assertions makes it into a logically tightly knit whole, that gives me confidence. How do we this with functional programs? By supplying two of them and an argument that demonstrates their equivalence? What about the following example? (My notation because I lack the fluency in yours.) (1) Consider the function f defined by: f(0) = 0, f(1) = 1, f(2n) = f(n), f(2n+1) = f(n) + f(n+1) (2) Consider the following program (“peven” = “positive and even”, so for “podd”) {N>=0} n, a, b := N, 1, 0; _do_ peven(n) -> a, n := a + b, n/2 [] podd(n) -> b, n := b + a, (n-1)/2 _od_ {b=f(N)} Here (1) gives a recursive definition of f, (2) gives a repetitive program. Both definitions can be translated in a straightforward manner into functional programs. What would be involved in the demonstration of their equivalence? The above seems to me little example of the appropriate degree of sophistication to try your hands on. (I am not going to try it myself, as I fear that my past experience would misguide me: I am afraid that I wouldn’t rise above the level of translating (2)’s traditional correctness proof - with which I am very familiar - in an unfamiliar notation. Good luck!) With my greetings and warmest regards, yours ever _Edsger_ P.S. Please note my new postal code: 5671 AL (capitals obligatory) _in front of_ the village name EWD. Maybe someone with OCR software at hand can give the typed ones a try?
    - jorams 10y ago
      As an addition to your transcription, here is the last letter transcribed: to John Backus 91 Saint Germain Avenue SAN FRANCISCO, California 94114 U.S.A. 12th July 1979 Dear John, My schedule is very tight, and I am afraid that I must disappoint John Williams; Monday 20 or Tuesday 21 August seem the only two slots that are really available. I shall arrive in the USA on Sunday 29th July, and had already committed myself for the week of Monday 30 July to Burroughs in Mission Viejo. My wife and the two youngest children will join me for the first three weeks of the trip, and the week of 6th August was planned as "the real holiday." Since then Bill McKeenan has twisted my arm: the programming course to be given that week was so heavily over- booked that he asked me to give a second course, in parallel to David's. Under those circumstances I would like to avoid further commitments in the week starting on Monday 13: it is their last week in the USA, and I have then been working almost all the time! Immediately after WG2.3 I shall go to Austin, Texas (Burroughs and University), and then home! If I have a completely free choice, I think I would prefer Monday 20 slightly over Tuesday 21. New title and abstract: Title: Termination Detection for Diffusing Computations Abstract: The activity of a finite computation may propagate over a network of machines, when machines may delegate (repeatedly) subtasks to their neighbours; when such a computation is fired from a single machine, we call it "a diffusing computation." We present a signalling scheme --to be superimposed on the diffusing computation-- enabling the machine that fired it to detect its termination. Our signalling scheme is perfectly general in the sense that, independently of the topology of the network, it is applicable to any diffusing computation. (End of abstract.) Please give my regards to John Williams and tell him how sorry I am that I shall miss him. I am not familiar with distance and transport facilities between Santa Cruz and San Jose. If it is better when I come to San Jose the day before that is fine with me; may I leave the logistics to you? (Wife and children leave on Friday 17th of August.) With my greetings and best wishes, yours ever _Edsger_
    - acidflask 10y ago
      Thanks for contributing the transcript! I've started a GitHub repo with a first draft of transcripts for all the letters. https://github.com/jiahao/backus-dijkstra-letters-1979 https://github.com/jiahao/backus-dijkstra-letters-1979 Anyone else who is interested is welcome to help proofread and submit PRs.
  - Nullabillity 10y ago
    Why doesn't the LoC scan it themselves? That seems much more useful than just having on display in one location.
    - esbranson 10y ago
      The government only recently scanned the US Statutes at Large, so I would say they have more important works to scan.
  - dang 10y ago
    Thank you for going to the trouble of sharing this amazing material! I'd also like to hear about the historical paper you're working on. We've taken the "arrogance" quote out of the HN title and replaced it with a neutral description of the letters—perhaps a bit too neutral, given how fabulous the post is. But HN readers can figure that out for themselves, especially once a post gets so high on the front page.
    - acidflask 10y ago
      The paper is about, among other things, the history of the array data structure. It's far too early to advertise, but you can see a very early version on my GitHub account. :) I was surprised to discover recently that the word 'array' prior to 1950 was used exclusively to describe two dimensional tables of numbers that one might find in a matrix or determinant. But by the advent of FORTRAN I in 1957 and ALGOL 58, 'array' now referred exclusively to a one-dimensional entity, as compared with 'n-dimensional arrays'. I was interested in digging through John Backus's papers from this era to see if I could find any clues. I was able to narrow down the near window to 1952-1954, since the FORTRAN preliminary report of 1954 uses the word 'array' casually in the modern one-dimensional sense as interchangeable with 'subscripted variables', the latter being the more common terminology at the time. By comparison, a virtually unknown paper by Rutishauser in 1952 describing the "for" loop did not use the word 'array' at all, only 'subscripted variables'. (Rutishauser was an accomplished mathematician and quite possibly the world's first computational scientist.) A paper by Laning and Zierler at MIT in 1954 describing a formula compiler also used only the term 'subscripted variables'. Backus's papers also have evidence showing that FORTRAN I was clearly written specifically to take advantage of the IBM 704's machine capabilities. Not only was the IBM 704 the world's first commercially successful computer, it was also an improvement over the preceding IBM 701 in providing index registers (3 of them) and floating point instructions which were fast for its era. Backus's papers describe how providing hardware support for indexing and floating point was revolutionary, as all programs up to that time had to write in all these instructions by hand (and for many programs was pretty much all they did). So it is clear to me now that the changeover in the implied dimensionality of the word 'array' must be related to how the array developed as a data structure abstracting away indexing operations. By the time IAL (pre-ALGOL) came on the scene in 1958, the idea of indexable homogeneous containers was already well established. But I still haven't found any strong smoking gun evidence introducing the one-dimensional sense of the word. I suspect further digging into the description of the IBM 704 may be necessary. The 704 was not the first to provide index registers, but it may have been the first to call them as such. (The Manchester Mark I computer of 1948 appears to be the first computer with an index register, but it was called a B line. The [patent](https://www.google.com/patents/US3012724 https://www.google.com/patents/US3012724) claiming to cover index registers uses the term "control instruction" - no arrays mentioned - but it very cutely describes numbers as residing in known locations or "addresses" in quotes.)
- samfisher83 10y ago
  I found the handwriting pretty good. However they tend to be quite verbose in their language.
  - bluejekyll 10y ago
    It's amazing isn't it, the language that surrounds the detailed arguments. The constant attention to recognize the effort put into the designs and ideas, trying not to offend, but clearly still managing to do so. My technical correspondence is nowhere near this kind, and I know that it offends in some cases, but I also find that anything over 2-3 paragraphs these days is generally ignored. Email, texts, slack, etc. have greatly abbreviated our conversations, allowing for many more, but reducing their quality.
  - sverige 10y ago
    I found their prose to be quite good. It's sad that it seems long-winded to modern readers. These letters are not long. Maybe attention spans are too short. Some of the "verbosity" seems to arise from their apparently mutual concern to preserve their relationship by delivering criticism of ideas or behaviors without attacking the person. We could certainly use more of this style of communication today, but all it earns now is a "TL;DR" at the beginning or the end.
- Bromskloss 10y ago
  What do you say? Shall we divide the task among a few of us and type this up? (Or do people perhaps do this with OCR nowadays?) Would there be enough interest in having these letters in searchable form to motivate the effort?
  - weinzierl 10y ago
    > Would there be enough interest in having these letters in searchable form to motivate the effort? Yes, yes, yes. > Shall we divide the task among a few of us and type this up? I did the first one, see my other comment. It took me about 20 minutes to type and another 20 minutes to proof read. It is one of the longer ones and handwritten. If a few other join in, absolutely doable.
  - akkartik 10y ago
    Unfortunately they don't seem to be in the EWD archives at http://www.cs.utexas.edu/users/EWD/indexChron.html http://www.cs.utexas.edu/users/EWD/indexChron.html. So they indeed don't seem to be OCR'd.
    - Bromskloss 10y ago
      Now that you mention it, maybe we should just turn it over to those guys to make transcriptions and host it all. :-) Edit: I sent a mail to the project maintainer.
  - alex_muscar 10y ago
    > Would there be enough interest in having these letters in searchable form to motivate the effort? Yes, please :). Esp. Dijkstra's letter from the 5th of Apr '79. It's a bit hard to read. Thanks for making them available.
    - EdwardCoffin 10y ago
      update - not working on this one now. The pages are pretty readable, if you save them. The image display stuff that medium is using is what screws them up to the point of unreadability.
deleted 10y ago
[deleted]
justin66 10y ago
"I don't know how many of you have ever met Dijkstra, but you probably know that arrogance in computer science is measured in nano-Dijkstras." - Alan Kay
- vanderZwan 10y ago
  Funny thing is that Alan Kay himself often comes across just as arrogant these days. "Comes across", because more often than not I think it's more likely that people who are too pleased with themselves don't like to be told that, really, what they've achieved isn't good enough, or even misguided. Even if, or perhaps especially if, the person who tells them that (Dijkstra when it comes to programming, Kay when it comes to HCI) is right or at least has a very good point.
  - justin66 10y ago
    What recent talks has Kay given? To be honest, my only criticism of him based on what I've seen the last decade is that he's reusing too much of the same material, even though he certainly has a lot more to say.
    - vanderZwan 10y ago
      The thing is that I think he is hung up on the masses still not really getting that material, so he keeps repeating himself. Kinda like how a teacher will repeat the same material because he keeps getting new kids every year. Also, there's this single question by him on Stack Overflow, where he keeps replying to people with "nope, already had that in the 60s/70s": http://stackoverflow.com/questions/432922/significant-new-inventions-in-computing-since-1980 http://stackoverflow.com/questions/432922/significant-new-in...
      - sukilot 10y ago
        Kay is the reductio but forgot the absurdum. The natural numbers are the most recent invention in computer science. The rest is just implementation details.
vanderZwan 10y ago
You know, I'm wondering: could part of Dijkstra's reputed arrogance be due to a cultural difference? I'm Dutch, and bluntly calling out flaws in each other's work is not considered all that rude over here; it's almost the opposite: not calling someone out on their flaws implies we either consider them a lost cause or not worth the hassle of educating. I almost got fired from a teaching position in Sweden because I told my 3rd year bachelor students that many did not bother to add their names or the assignment number, or using paragraphs and in some cases even basic interpunction on their assignments. And that this was well below the level required to to pass secondary school, and that I expect better from them. This was apparently too confrontational, and a few upset students later I got chewed out and almost fired. Meanwhile, from my point of view, I was just doing my job and already sugarcoating it by Dutch standards. Having said that, yes, even by Dutch standards I would say that Dijkstra liked to troll people a bit. PS: I really like the following insight from Dijkstra's review: But whereas machines must be able to execute programs (without understanding them), people must be able to understand them (without executing them).
- Qantourisc 10y ago
  Belgium here: it's a bit the same. However HOW you say it matters to. First times you are expected to say it "without" emotion, like not being angry. Consequential times incrementally go nuts :D
- bmer 10y ago
  Full disclosure: a) Dijkstra is a bit of a personal "hero" of mine (hero in quotation marks, because I don't like to think of myself as a hero worshipper), because it was due to him I learned of textbooks written by guys like Eric Hehner and Roland Backhouse, which ended up changing my life significantly. b) I do not really grasp the technical issues being discussed in the correspondences between Dijkstra and Backus Given this disclosure: Regardless of the cultural issues (which I suspect you are right about), I found Backus' first response to Dijkstra full of ad hominems, and very light on technical rebuttals. If we subtract out the ad hominems, I suspect the technical rebuttals would take less than a page (which is a significant reduction, considering that the full letter is 4 (typewritten!) pages). Calling Dijkstra arrogant seems to have been a popular insult (as Backus himself admits), so I wonder if Backus was simply jumping onto the bandwagon as a defensive reaction to the arguments presented in EWD 692. I think Dijkstra's responses were indeed trollish. I wish he wouldn't have said anything further after he noticed the gratuitous personal attacks against his character in Backus' response, but he couldn't help but say something back. Oh well. Can you comment on this observation?
vog 10y ago
Could anybody explain why this comment by "internaut" was downvoted so heavily? I found internaut's comment to be insightful, well-conceived and on-topic. What's wrong with this comment? EDIT: Moreover, who downvoted me so quickly for asking this question? This happened almost immediately after I posted this. Are there some nasty bots at place here?
- pvg 10y ago
  https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html search for 'downvoted'.
  - vog 10y ago
    I don't know what to make of this. This hint is not useful at all. The guideline in question ... > Please resist commenting about being downvoted. ... does not explain anything here. 1. This guideline does not explain the downvote of internaut's comment. 2. This guideline does not explain the downvote of my initial comment, where I complained about another person being downvoted, not about myself being downvoted (which I wasn't at that point in time). 3. This guideline does not explain the situation after my EDIT. Although it violated that guideline, it did not receive heavy downvotes, but received multiple upvotes instead.
    - deleted 10y ago
      [deleted]
    - pvg 10y ago
      It simply asks you not to go on (and continue to go on) about downvoting. The forum is better if everyone does as it asks. If you're really worried about being targeted by some evil bot, you can just email the site admins.
      - vog 10y ago
        Thanks for the clarification. Now your first comment makes a lot more sense to me. It was not clear to me that you were asking for something. I thought you were trying to explain something.
bby 10y ago
I think of Dijkstra the same way I think of Drake.
OJFord 10y ago
Dear John, ... But when you open your letter with: “I am quite sure that you have never read any paper I’ve sent you before” it is my pleasure to inform you that - although “quite sure” - you were very wrong. Zing!
Ericson2314 10y ago
I'm sad that in this thread and https://news.ycombinator.com/item?id=11786193 https://news.ycombinator.com/item?id=11786193, nobody is actually talking about the technical arguments at play. I've only read the EWD692 "opening salvo" but already there are interesting things to point out. EWD1303: > The profound significance of Dekker's solution of 1959, however, was that it showed the role that mathematical proof could play in the process of program design. Now, more than 40 years later, this role is still hardly recognized in the world of discrete designs. If mathematics is allowed to play a role at all, it is in the form of a posteriori verification, i.e. by showing by usually mechanized mathematics that the design meets its specifications; the strong guidance that correctness concerns can provide to the design process is rarely exploited. On the whole it is still "Code first, debug later" instead of "Think first, code later", which is a pity, but Computing Science cannot complain: we are free to speak, we don't have a right to be heard. And in later years Computing Science has spoken: in connection with the calculational derivation of programs —and then of mathematical proofs in general— the names of R.W. Floyd, C.A.R. Hoare, D. Gries, C.C. Morgan, A.J.M. van Gasteren and W.H.J. Feijen are the first to come to my mind. Backus as quoted in EWD692 (Djikstra attacks this): > One advantage of this algebra over other proof techniques is that the programmer can use his programming language as the language for deriving proofs, rather than having to state proofs in a separate logical system that merely [sic!] talks about his programs. From a perspective of a PL person like myself, these ideals are very compatible. Without correctness by construction, there is not enough proof reuse so formality will forever be doomed for niche applications (aka computers embedded in dangerous things). Likewise after trying out intuitionistic type theory--based things (e.g. Agda) separating the program and proof langauges just seems clumsy. Overall separating programming and proof whether spatially (seperate languages) or temporally (correctness proved after the fact) is bad, and the reasons hardly depend on the dimension of separation
- Ericson2314 10y ago
  IIUC, Backus also talks about correctness proofs with "Von Neumann model" languages just being a lot harder to prove, a separate point from the language for the proof itself. Well, that's a huge selling point for PL research to this day, Dijkstra evidently came fully on board years later as evidenced in https://www.cs.utexas.edu/users/EWD/transcriptions/OtherDocs/Haskell.html https://www.cs.utexas.edu/users/EWD/transcriptions/OtherDocs...: > A fundamental reason for the preference is that functional programs are much more readily appreciated as mathematical objects than imperative ones, so that you can teach what rigorous reasoning about programs amounts to.
kazinator 10y ago
Dikjstra had very good command of English for a Dutchman; far better than the average American. It seems he could easily have taught first year English. Look at the way he nicely incorporates quotes and the diction and sentence variety. From this we can tell where he placed his efforts; if you want to troll computer science on an international level, you better beef up your English! He would have made a great asset to any software team, as a documenter; I wouldn't have had him write much code, though.
- morty16 10y ago
  My understanding is that English is a natural second language for the Dutch and is taught extensively in schools (i.e. learned by everyone). Also, they are close enough to the U.K. to receive broadcast television, etc. so they also have that level of immersion. Every Dutch person I've met has had a terrific command of the language, much better than average native speakers. I suspect that at least some of this is due to the fact that as second-language students they actually take time to learn the rules of grammar, etc. Most native speakers pick it up "on the street", so the Dutch (that I've met) tend to sound more formal and educated, especially when there's no discernible accent.
- mcguire 10y ago
  "Dikjstra had very good command of English for a Dutchman; far better than the average American." Once upon a time, I read a thriller of the Cussler style where a Russian translator for the CIA or something goes to a conference and gets to exchange knowing glances with two colleagues over some mistake that only they recognized. Then I realized that there would have likely been more than a few native Russian speakers in the room. You realize your statement is ridiculous, right?

237 points by acidflask 10y ago

This is a series of cell phone shots of an exchange of letters between Backus and Dijkstra. There is no transcript and some of the letters are hard to read, especially the handwritten ones. I only skimmed it but it is definitely an interesting read. I didn't interpret their stance as arrogant though. In my book both are enthusiastic about their subject and think the other party is misguided. Both take some effort not to hurt the others feelings while still bringing their point across.

acidflask 10y ago
The title "This guy’s arrogance takes your breath away" is taken directly from Backus's own description of this collection of letters. I've changed the title to make clearer that it is a direct quotation. Unfortunately, the Library of Congress does not allow scanners without prior approval, so this was the only way I could make my own copies. It did not help that all these letters were written or typed on very thin mimeograph paper.
- weinzierl 10y ago
  Thanks for making these letter public! I missed that the quote was Backus's, it makes a lot more sense now. The quality of your photos is excellent and I doubt a scanner would make them much better. I wish there was a transcript though. As a start, here is the first letter transcribed: to John Backus International Business Machines Corporation 5600 Cattle Road SAN JOSE CA 95193 U.S.A Monday 29th of May, 1978 “To interrupt one’s own researches in order to follow those of another is a scientific pleasure which most experts delegate to their assistants.” (Eric Temple Bell in “Development of Mathematics”) Dear John, I do not claim to be more noble or sensible than “most experts”; perhaps it is only becauseI have only one assistant to whom I can delegate no more than one man can do. But when you open your letter with: “I am quite sure that you have never read any paper I’ve sent you before” it is my pleasure to inform you that - although “quite sure” - you were very wrong. I very well remember that you mailed me a sizeable paper on reduction languages to which I owe my introduction to that subject. I didn’t only read it, parts of it were even studied. I also remember that it left me with mixed feelings. I can very well understand your excitement, although, for lack of experience, I still cannot share it. I am far from delighted with the state of the art of programming today, and anyone suggesting an alternative has in in [sic] principle my sympathy - until, of course, he loses it again, like Terry Winograd did when he suggested natural language programming - “natural descriptions”! - as an alternative-. In the long run I have more faith in any rephrasing of the programming task that makes it more amendable to mathematical treatment. But you must have lots of patience, for the run will be very long. It isn’t just mental inertia - that problem can be solved generally by education a new generation of youngsters and waiting until the old ones have died - . It is the development of a new set of techniques needed to achieve a comparable degree of proficiency. Could you get me a copy of G.A. Mago’s (not yet published) “A network of microprocessors to execute reduction languages”? That might whet my appetite! From various angles I have looked into such networks and I am not entirely pleased with what I have seen. Firstly I suspect our techniques for proving the correctness of such designs: each next proof seems to differ so much from all the previous ones. I suspect I discovered that all I could design were special purpose networks, which, of course, made me suspect the programming language in the Von Neumann style which, already before you have chosen your problem, seems to have set you on the wrong track. Semantically speaking the semicolon is, of course, only a way of expressing functional composition: it imposes the same order that can also be expressed with brackets - innermost brackets first -. In combination with the distribution you can generate many innermost bracket pairs, thus expressing very honestly that it is really only a partial order that matters. I like that, it is honest. When you write “one can transform programs [....] by the use of laws [...] which are _part of the program- ming language_” etc. I am somewhat hesitant. I am not convinced (yet?) that the traditional separation in fixed program, variable data and assertions is a mistake. The first and the last - program and assertions - are somewhat merged in LUCID, in which correctness proofs are carried out in (nearly) the same formalism as the program is expressed in. On the one hand that presents a tempting unification, on the other hand I thought that mathematicians speerated carefully and for good reasons the language they talk about and the metalanguage in which they do so. To put it in another way: given a functional program, I feel only confident if I can do enough other significant things to it besides easy[striked out three times] carrying it out. And those I don’t see yet. The almost total absence of redundancy is another aspect of the same worry. In the case of a traditional program we know how to make it redundant: by inserting assertions, combination of text and assertions makes it into a logically tightly knit whole, that gives me confidence. How do we this with functional programs? By supplying two of them and an argument that demonstrates their equivalence? What about the following example? (My notation because I lack the fluency in yours.) (1) Consider the function f defined by: f(0) = 0, f(1) = 1, f(2n) = f(n), f(2n+1) = f(n) + f(n+1) (2) Consider the following program (“peven” = “positive and even”, so for “podd”) {N>=0} n, a, b := N, 1, 0; _do_ peven(n) -> a, n := a + b, n/2 [] podd(n) -> b, n := b + a, (n-1)/2 _od_ {b=f(N)} Here (1) gives a recursive definition of f, (2) gives a repetitive program. Both definitions can be translated in a straightforward manner into functional programs. What would be involved in the demonstration of their equivalence? The above seems to me little example of the appropriate degree of sophistication to try your hands on. (I am not going to try it myself, as I fear that my past experience would misguide me: I am afraid that I wouldn’t rise above the level of translating (2)’s traditional correctness proof - with which I am very familiar - in an unfamiliar notation. Good luck!) With my greetings and warmest regards, yours ever _Edsger_ P.S. Please note my new postal code: 5671 AL (capitals obligatory) _in front of_ the village name EWD. Maybe someone with OCR software at hand can give the typed ones a try?
  - jorams 10y ago
    As an addition to your transcription, here is the last letter transcribed: to John Backus 91 Saint Germain Avenue SAN FRANCISCO, California 94114 U.S.A. 12th July 1979 Dear John, My schedule is very tight, and I am afraid that I must disappoint John Williams; Monday 20 or Tuesday 21 August seem the only two slots that are really available. I shall arrive in the USA on Sunday 29th July, and had already committed myself for the week of Monday 30 July to Burroughs in Mission Viejo. My wife and the two youngest children will join me for the first three weeks of the trip, and the week of 6th August was planned as "the real holiday." Since then Bill McKeenan has twisted my arm: the programming course to be given that week was so heavily over- booked that he asked me to give a second course, in parallel to David's. Under those circumstances I would like to avoid further commitments in the week starting on Monday 13: it is their last week in the USA, and I have then been working almost all the time! Immediately after WG2.3 I shall go to Austin, Texas (Burroughs and University), and then home! If I have a completely free choice, I think I would prefer Monday 20 slightly over Tuesday 21. New title and abstract: Title: Termination Detection for Diffusing Computations Abstract: The activity of a finite computation may propagate over a network of machines, when machines may delegate (repeatedly) subtasks to their neighbours; when such a computation is fired from a single machine, we call it "a diffusing computation." We present a signalling scheme --to be superimposed on the diffusing computation-- enabling the machine that fired it to detect its termination. Our signalling scheme is perfectly general in the sense that, independently of the topology of the network, it is applicable to any diffusing computation. (End of abstract.) Please give my regards to John Williams and tell him how sorry I am that I shall miss him. I am not familiar with distance and transport facilities between Santa Cruz and San Jose. If it is better when I come to San Jose the day before that is fine with me; may I leave the logistics to you? (Wife and children leave on Friday 17th of August.) With my greetings and best wishes, yours ever _Edsger_
  - acidflask 10y ago
    Thanks for contributing the transcript! I've started a GitHub repo with a first draft of transcripts for all the letters. https://github.com/jiahao/backus-dijkstra-letters-1979 https://github.com/jiahao/backus-dijkstra-letters-1979 Anyone else who is interested is welcome to help proofread and submit PRs.
- Nullabillity 10y ago
  Why doesn't the LoC scan it themselves? That seems much more useful than just having on display in one location.
  - esbranson 10y ago
    The government only recently scanned the US Statutes at Large, so I would say they have more important works to scan.
- dang 10y ago
  Thank you for going to the trouble of sharing this amazing material! I'd also like to hear about the historical paper you're working on. We've taken the "arrogance" quote out of the HN title and replaced it with a neutral description of the letters—perhaps a bit too neutral, given how fabulous the post is. But HN readers can figure that out for themselves, especially once a post gets so high on the front page.
  - acidflask 10y ago
    The paper is about, among other things, the history of the array data structure. It's far too early to advertise, but you can see a very early version on my GitHub account. :) I was surprised to discover recently that the word 'array' prior to 1950 was used exclusively to describe two dimensional tables of numbers that one might find in a matrix or determinant. But by the advent of FORTRAN I in 1957 and ALGOL 58, 'array' now referred exclusively to a one-dimensional entity, as compared with 'n-dimensional arrays'. I was interested in digging through John Backus's papers from this era to see if I could find any clues. I was able to narrow down the near window to 1952-1954, since the FORTRAN preliminary report of 1954 uses the word 'array' casually in the modern one-dimensional sense as interchangeable with 'subscripted variables', the latter being the more common terminology at the time. By comparison, a virtually unknown paper by Rutishauser in 1952 describing the "for" loop did not use the word 'array' at all, only 'subscripted variables'. (Rutishauser was an accomplished mathematician and quite possibly the world's first computational scientist.) A paper by Laning and Zierler at MIT in 1954 describing a formula compiler also used only the term 'subscripted variables'. Backus's papers also have evidence showing that FORTRAN I was clearly written specifically to take advantage of the IBM 704's machine capabilities. Not only was the IBM 704 the world's first commercially successful computer, it was also an improvement over the preceding IBM 701 in providing index registers (3 of them) and floating point instructions which were fast for its era. Backus's papers describe how providing hardware support for indexing and floating point was revolutionary, as all programs up to that time had to write in all these instructions by hand (and for many programs was pretty much all they did). So it is clear to me now that the changeover in the implied dimensionality of the word 'array' must be related to how the array developed as a data structure abstracting away indexing operations. By the time IAL (pre-ALGOL) came on the scene in 1958, the idea of indexable homogeneous containers was already well established. But I still haven't found any strong smoking gun evidence introducing the one-dimensional sense of the word. I suspect further digging into the description of the IBM 704 may be necessary. The 704 was not the first to provide index registers, but it may have been the first to call them as such. (The Manchester Mark I computer of 1948 appears to be the first computer with an index register, but it was called a B line. The [patent](https://www.google.com/patents/US3012724 https://www.google.com/patents/US3012724) claiming to cover index registers uses the term "control instruction" - no arrays mentioned - but it very cutely describes numbers as residing in known locations or "addresses" in quotes.)
samfisher83 10y ago
I found the handwriting pretty good. However they tend to be quite verbose in their language.
- bluejekyll 10y ago
  It's amazing isn't it, the language that surrounds the detailed arguments. The constant attention to recognize the effort put into the designs and ideas, trying not to offend, but clearly still managing to do so. My technical correspondence is nowhere near this kind, and I know that it offends in some cases, but I also find that anything over 2-3 paragraphs these days is generally ignored. Email, texts, slack, etc. have greatly abbreviated our conversations, allowing for many more, but reducing their quality.
- sverige 10y ago
  I found their prose to be quite good. It's sad that it seems long-winded to modern readers. These letters are not long. Maybe attention spans are too short. Some of the "verbosity" seems to arise from their apparently mutual concern to preserve their relationship by delivering criticism of ideas or behaviors without attacking the person. We could certainly use more of this style of communication today, but all it earns now is a "TL;DR" at the beginning or the end.
Bromskloss 10y ago
What do you say? Shall we divide the task among a few of us and type this up? (Or do people perhaps do this with OCR nowadays?) Would there be enough interest in having these letters in searchable form to motivate the effort?
- weinzierl 10y ago
  > Would there be enough interest in having these letters in searchable form to motivate the effort? Yes, yes, yes. > Shall we divide the task among a few of us and type this up? I did the first one, see my other comment. It took me about 20 minutes to type and another 20 minutes to proof read. It is one of the longer ones and handwritten. If a few other join in, absolutely doable.
- akkartik 10y ago
  Unfortunately they don't seem to be in the EWD archives at http://www.cs.utexas.edu/users/EWD/indexChron.html http://www.cs.utexas.edu/users/EWD/indexChron.html. So they indeed don't seem to be OCR'd.
  - Bromskloss 10y ago
    Now that you mention it, maybe we should just turn it over to those guys to make transcriptions and host it all. :-) Edit: I sent a mail to the project maintainer.
- alex_muscar 10y ago
  > Would there be enough interest in having these letters in searchable form to motivate the effort? Yes, please :). Esp. Dijkstra's letter from the 5th of Apr '79. It's a bit hard to read. Thanks for making them available.
  - EdwardCoffin 10y ago
    update - not working on this one now. The pages are pretty readable, if you save them. The image display stuff that medium is using is what screws them up to the point of unreadability.

deleted 10y ago

[deleted]

justin66 10y ago

"I don't know how many of you have ever met Dijkstra, but you probably know that arrogance in computer science is measured in nano-Dijkstras." - Alan Kay

vanderZwan 10y ago
Funny thing is that Alan Kay himself often comes across just as arrogant these days. "Comes across", because more often than not I think it's more likely that people who are too pleased with themselves don't like to be told that, really, what they've achieved isn't good enough, or even misguided. Even if, or perhaps especially if, the person who tells them that (Dijkstra when it comes to programming, Kay when it comes to HCI) is right or at least has a very good point.
- justin66 10y ago
  What recent talks has Kay given? To be honest, my only criticism of him based on what I've seen the last decade is that he's reusing too much of the same material, even though he certainly has a lot more to say.
  - vanderZwan 10y ago
    The thing is that I think he is hung up on the masses still not really getting that material, so he keeps repeating himself. Kinda like how a teacher will repeat the same material because he keeps getting new kids every year. Also, there's this single question by him on Stack Overflow, where he keeps replying to people with "nope, already had that in the 60s/70s": http://stackoverflow.com/questions/432922/significant-new-inventions-in-computing-since-1980 http://stackoverflow.com/questions/432922/significant-new-in...
    - sukilot 10y ago
      Kay is the reductio but forgot the absurdum. The natural numbers are the most recent invention in computer science. The rest is just implementation details.

vanderZwan 10y ago

You know, I'm wondering: could part of Dijkstra's reputed arrogance be due to a cultural difference? I'm Dutch, and bluntly calling out flaws in each other's work is not considered all that rude over here; it's almost the opposite: not calling someone out on their flaws implies we either consider them a lost cause or not worth the hassle of educating. I almost got fired from a teaching position in Sweden because I told my 3rd year bachelor students that many did not bother to add their names or the assignment number, or using paragraphs and in some cases even basic interpunction on their assignments. And that this was well below the level required to to pass secondary school, and that I expect better from them. This was apparently too confrontational, and a few upset students later I got chewed out and almost fired. Meanwhile, from my point of view, I was just doing my job and already sugarcoating it by Dutch standards. Having said that, yes, even by Dutch standards I would say that Dijkstra liked to troll people a bit. PS: I really like the following insight from Dijkstra's review: But whereas machines must be able to execute programs (without understanding them), people must be able to understand them (without executing them).

Qantourisc 10y ago
Belgium here: it's a bit the same. However HOW you say it matters to. First times you are expected to say it "without" emotion, like not being angry. Consequential times incrementally go nuts :D
bmer 10y ago
Full disclosure: a) Dijkstra is a bit of a personal "hero" of mine (hero in quotation marks, because I don't like to think of myself as a hero worshipper), because it was due to him I learned of textbooks written by guys like Eric Hehner and Roland Backhouse, which ended up changing my life significantly. b) I do not really grasp the technical issues being discussed in the correspondences between Dijkstra and Backus Given this disclosure: Regardless of the cultural issues (which I suspect you are right about), I found Backus' first response to Dijkstra full of ad hominems, and very light on technical rebuttals. If we subtract out the ad hominems, I suspect the technical rebuttals would take less than a page (which is a significant reduction, considering that the full letter is 4 (typewritten!) pages). Calling Dijkstra arrogant seems to have been a popular insult (as Backus himself admits), so I wonder if Backus was simply jumping onto the bandwagon as a defensive reaction to the arguments presented in EWD 692. I think Dijkstra's responses were indeed trollish. I wish he wouldn't have said anything further after he noticed the gratuitous personal attacks against his character in Backus' response, but he couldn't help but say something back. Oh well. Can you comment on this observation?

vog 10y ago

Could anybody explain why this comment by "internaut" was downvoted so heavily? I found internaut's comment to be insightful, well-conceived and on-topic. What's wrong with this comment? EDIT: Moreover, who downvoted me so quickly for asking this question? This happened almost immediately after I posted this. Are there some nasty bots at place here?

pvg 10y ago
https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html search for 'downvoted'.
- vog 10y ago
  I don't know what to make of this. This hint is not useful at all. The guideline in question ... > Please resist commenting about being downvoted. ... does not explain anything here. 1. This guideline does not explain the downvote of internaut's comment. 2. This guideline does not explain the downvote of my initial comment, where I complained about another person being downvoted, not about myself being downvoted (which I wasn't at that point in time). 3. This guideline does not explain the situation after my EDIT. Although it violated that guideline, it did not receive heavy downvotes, but received multiple upvotes instead.
  - deleted 10y ago
    [deleted]
  - pvg 10y ago
    It simply asks you not to go on (and continue to go on) about downvoting. The forum is better if everyone does as it asks. If you're really worried about being targeted by some evil bot, you can just email the site admins.
    - vog 10y ago
      Thanks for the clarification. Now your first comment makes a lot more sense to me. It was not clear to me that you were asking for something. I thought you were trying to explain something.

bby 10y ago

I think of Dijkstra the same way I think of Drake.

OJFord 10y ago

Dear John, ... But when you open your letter with: “I am quite sure that you have never read any paper I’ve sent you before” it is my pleasure to inform you that - although “quite sure” - you were very wrong. Zing!

Ericson2314 10y ago

I'm sad that in this thread and https://news.ycombinator.com/item?id=11786193 https://news.ycombinator.com/item?id=11786193, nobody is actually talking about the technical arguments at play. I've only read the EWD692 "opening salvo" but already there are interesting things to point out. EWD1303: > The profound significance of Dekker's solution of 1959, however, was that it showed the role that mathematical proof could play in the process of program design. Now, more than 40 years later, this role is still hardly recognized in the world of discrete designs. If mathematics is allowed to play a role at all, it is in the form of a posteriori verification, i.e. by showing by usually mechanized mathematics that the design meets its specifications; the strong guidance that correctness concerns can provide to the design process is rarely exploited. On the whole it is still "Code first, debug later" instead of "Think first, code later", which is a pity, but Computing Science cannot complain: we are free to speak, we don't have a right to be heard. And in later years Computing Science has spoken: in connection with the calculational derivation of programs —and then of mathematical proofs in general— the names of R.W. Floyd, C.A.R. Hoare, D. Gries, C.C. Morgan, A.J.M. van Gasteren and W.H.J. Feijen are the first to come to my mind. Backus as quoted in EWD692 (Djikstra attacks this): > One advantage of this algebra over other proof techniques is that the programmer can use his programming language as the language for deriving proofs, rather than having to state proofs in a separate logical system that merely [sic!] talks about his programs. From a perspective of a PL person like myself, these ideals are very compatible. Without correctness by construction, there is not enough proof reuse so formality will forever be doomed for niche applications (aka computers embedded in dangerous things). Likewise after trying out intuitionistic type theory--based things (e.g. Agda) separating the program and proof langauges just seems clumsy. Overall separating programming and proof whether spatially (seperate languages) or temporally (correctness proved after the fact) is bad, and the reasons hardly depend on the dimension of separation

Ericson2314 10y ago
IIUC, Backus also talks about correctness proofs with "Von Neumann model" languages just being a lot harder to prove, a separate point from the language for the proof itself. Well, that's a huge selling point for PL research to this day, Dijkstra evidently came fully on board years later as evidenced in https://www.cs.utexas.edu/users/EWD/transcriptions/OtherDocs/Haskell.html https://www.cs.utexas.edu/users/EWD/transcriptions/OtherDocs...: > A fundamental reason for the preference is that functional programs are much more readily appreciated as mathematical objects than imperative ones, so that you can teach what rigorous reasoning about programs amounts to.

kazinator 10y ago

Dikjstra had very good command of English for a Dutchman; far better than the average American. It seems he could easily have taught first year English. Look at the way he nicely incorporates quotes and the diction and sentence variety. From this we can tell where he placed his efforts; if you want to troll computer science on an international level, you better beef up your English! He would have made a great asset to any software team, as a documenter; I wouldn't have had him write much code, though.

morty16 10y ago
My understanding is that English is a natural second language for the Dutch and is taught extensively in schools (i.e. learned by everyone). Also, they are close enough to the U.K. to receive broadcast television, etc. so they also have that level of immersion. Every Dutch person I've met has had a terrific command of the language, much better than average native speakers. I suspect that at least some of this is due to the fact that as second-language students they actually take time to learn the rules of grammar, etc. Most native speakers pick it up "on the street", so the Dutch (that I've met) tend to sound more formal and educated, especially when there's no discernible accent.
mcguire 10y ago
"Dikjstra had very good command of English for a Dutchman; far better than the average American." Once upon a time, I read a thriller of the Cussler style where a Russian translator for the CIA or something goes to a conference and gets to exchange knowing glances with two colleagues over some mistake that only they recognized. Then I realized that there would have likely been more than a few native Russian speakers in the room. You realize your statement is ridiculous, right?