4 ms·

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

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.)

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.)