18 ms·

Edsger Dijkstra – The Man Who Carried Computer Science on His Shoulders

444 points by furcyd 6y ago

nickdrozd 6y ago
> ALGOL 60 included a series of novel features, such as recursion, which was supported in a much more complex manner than logicians had ever envisaged...Recursive procedures in ALGOL 60 are much more complex than in Lisp. Can anyone explain how this "much more complex" recursion works?
- deleted 6y ago
  [deleted]
- azhenley 6y ago
  There is an interesting write-up about Algol 60's recursion [0] that was discussed here before [1]. [0] https://vanemden.wordpress.com/2014/06/18/how-recursion-got-into-programming-a-comedy-of-errors-3/ https://vanemden.wordpress.com/2014/06/18/how-recursion-got-... [1] https://news.ycombinator.com/item?id=10131664 https://news.ycombinator.com/item?id=10131664
- niea_11 6y ago
  I did a quick search and according to this article [1], dijkstra's implementation was not restricted compared to other implementations at the time : It is Dijkstra's generalizing style which stands out when a comparison is made with the work of his contemporaries. Rutishauser, for example, had limited the order of his procedure activations in his run-time system [59], while Dijkstra had no such restriction. Floyd's work [60, p.42-43] relied on three specialized “yo-yo” lists (i.e., stacks) instead of one general stack. Likewise, the MAD translator [61, p.28] used several specialized tables. Also, and most importantly, the ALCOR compilers were severely restricted in that they could not handle several ALGOL60 language constructs, including the recursive procedure (cf. Section ). Finally, though the Irons-Feurzeig system [54] did implement recursive-procedure activations and by means of one general run-time stack, it was, in the interest of efficiency, sophisticated in its run-time capabilities and, hence, unlike the run-time system of Dijkstra and Zonneveld . [1] : https://www.dijkstrascry.com/node/4 https://www.dijkstrascry.com/node/4
- Someone 6y ago
  I think this refers to making the implementation efficient. They wanted performance on par with existing languages that didn’t allow recursion, and could simply assign fixed addresses to all function arguments and local variables. Lisp didn’t have that. It allocated environments left and right. That meant that a function call allocated memory and potentially could trigger garbage collection. The major improvement was to use a runtime stack. That was fairly novel. Earlier compilers used a stack at compile time to make it possible that those fixed addresses for arguments and locals could be shared between functions that didn’t call each other, directly or indirectly, but that stack didn’t exist at runtime. And yes, the idea of a stack seems trivial nowadays, but it wasn’t at the time. Quite a few CPUs didn’t even have “jump to subroutine” or “return from subroutine” instructions. Algol’s “call by name” feature also may have complicated this, but I don’t see how that’s more difficult than passing lambdas as arguments.
  - wilsonthewhale 6y ago
    Do you have any references or papers that developed the idea of having a stack at runtime? I love reading into the fundamentals of modern computing.
    - mjn 6y ago
      Dijkstra's paper "Recursive Programming" (1960) is where he lays out his proposal for implementing recursive Algol-60 subroutines with a stack: https://www.ics.uci.edu/~jajones/INF102-S18/readings/07_dijkstra.pdf https://www.ics.uci.edu/~jajones/INF102-S18/readings/07_dijk...
  - throwaway_pdp09 6y ago
    I'm not sure that's fair. If you have objects that escape downwards (so X calls Y, y creates some item i, i gets returned to X) then you can't have a stack. i may be overwritten at the next call of anything else, as the stack grows over it. I guess they do escape analysis and where items are provably local, stack allocate them. If not, plonk them on the heap. A call frame is an object like any other, so they go on the heap. This allows you to create closures.
- throwaway_pdp09 6y ago
  The answers to this question are extremely interesting and show how much work has been done to get where we are today, a position I took for granted and never really understood until now (even in name: 'yo-yo list', for heaven's sake!) It's a bit like parsing, these days we either reach for a technique (eg. recursive descent) or an implementation of a tool (such as flex/bison) and never think there was a time before these where people had to struggle conceptually with these things.
- todd8 6y ago
  Early LISP implementations used dynamic scope. This means that non-local references in a function search for the variable's binding in the call chain: if A calls B then when B uses nonlocal variable x it refers to the x in A, not necessarily the x that belongs in the lexical parent of B as seen in the source code. (Unlike C, Algol/Pascal/LISP can all define functions inside of other functions. These nested function definitions introduce lexical non-local scopes.) Dynamic scoping is easier to implement than lexical scoping. With lexical scoping, the run-time must incorporate some mechanism to find the stack frame of a lexical parent (as seen in the program's source code) to access a nonlocal variable's value. In dynamic scoping the run-time can just follow the stack frame order (starting at the top) to find a nonlocal variable's binding. Early LISP used dynamic scope. Scheme had lexical scope from the beginning. Common Lisp had both mechanisms and programs can use both. The implementation of recursion also has to address proper access to nonlocal variables in functions that are values themselves and are passed as arguments to other functions. Do these functions access the nonlocal variables based on their call location or their lexical location in the source code? These problems with functions as arguments are known as the upward and downward funarg problems. Knuth wrote the man-boy program to test Algol 60 implementations in these areas. Another complication for implementors of Algol 60 was parameter passing by-name, which is neither by-value nor by-reference. I don't recall any other well known language that has subsequently made that non-intuitive (to me) choice. I believe that Algol 68 abandoned call by-name, but it's been 25 years since I looked at the Algol 68 standard.
  - geophile 6y ago
    I may be fuzzy on this, it's been a long time. But isn't by-name a special case of passing a function? (And then referencing the parameter in the called procedure invokes the function.)
    - todd8 6y ago
      Yes, that's how "Jensen's Device" is used to implement call-by-name. However, note that the expression passed to an Algol 60 function by name causes the expression to be evaluated in the context of the function being called. Each time the formal parameter appears in the called function the expression passed to that parameter is re-evaluated.
amelius 6y ago
What are the greatest advances in CS of the last decade?
- deleted 6y ago
  [deleted]
- jnsie 6y ago
  Editor support for Dark Mode? (I jest)
- wyldfire 6y ago
  To me -- a casual novice -- it sounds like a lot of recent CS work results in things like CAP Theorem/consensus, NLP/AI models, AGI, practical tools for verification/formal methods.
  - sideshowb 6y ago
    I don't think we've made much progress towards AGI, but having reliable approaches to object recognition in images is fairly new, as is putting enough of that sort of thing together to make a self driving car.
- glouwbug 6y ago
  Leet code styled interviews
- caleb-allen 6y ago
  Session types may be up there? Or maybe progress on homomorphic encryption. Also, progress in quantum computing.
- hinkley 6y ago
  The older I get the harder it is to time-slot things, but I can think of a few things where much of the interesting work happened in the last ten years (similar to how a lot of pivotal work on GC algorithms happened in the late 90's). Most of the good work on escape analysis started around ~2010 Rust got us rolling on borrow semantics (I have a feeling the '20s will be remembered as the the golden age) I'm sure there's a thing or two in or around LLVM that would rank, but I'm not paying close enough attention. From a 'renaissance' standpoint: - LZ-family compression algorithms - Multi-tenant process isolation (containers) - transport protocols - Consensus algorithms
xenocyon 6y ago
It is remarkable how much he contravened modern academic norms: no work to bring in external funding, relatively few papers, very little collaboration, almost no PhD students. It's not an exaggeration to say that a young researcher with these characteristics today would likely get fired from any high-ranked American research university before even coming up for tenure review. Perhaps our modern academic metrics of merit are missing something?
- nurettin 6y ago
  It would be very funny to watch foremost experts in relatively new fields being denied because they don't have phd students. I somehow doubt this is the case, though.
- marcosdumay 6y ago
  > It's not an exaggeration to say that a young researcher with these characteristics today would likely get fired from any high-ranked American research university before even coming up for tenure review. He wouldn't even get in an university to get the chance to be fired. And that's not specific to the US, it applies to nearly all developed or developing countries. That person wouldn't be able to get much past a PhD, even as a student.
  - gautamdivgi 6y ago
    You’re right. The right of passage for most US computer science PhD programs is publications in the “right” journals and conferences. If you don’t publish you will rarely get past your thesis proposal. I think there are very few, very select professors in the US that prohibit publishing prior to graduating. But their count is likely in the single digits. Also, by some miracle you manage to graduate by minimal publishing or no publications you will find all doors to getting research funding shut. This means that you are basically unemployable as a tenure track professor (universities prefer their newly minted assistant professors to come with funding).
    - mcguire 6y ago
      Yes, it's true. EWD published almost nothing. http://www.netlib.org/bibnet/authors/d/dijkstra-edsger-w.html http://www.netlib.org/bibnet/authors/d/dijkstra-edsger-w.htm... (The ones marked "circulated privately" are the EWD series.)
AnimalMuppet 6y ago
Or at least who thought he carried computer science on his shoulders. He made significant, important contributions. He wasn't the only one. Hoare, Backus, McCarthy... there were a lot of people who made important, fundamental contributions. Structured programming caught on. Proofs did not, for reasons that would have offended Dijkstra - they took time, and it was actually more valuable (both socially and financially) to produce mostly-working software quickly than to produce proven-correct software slowly. But he never would have accepted that the real world was that way. He insisted that his approach was correct. As Backus said of him, "This guy’s arrogance takes your breath away." So: Important contributions? Absolutely. More than anyone else's? Perhaps. Carried computer science on his shoulders? No, but he probably thought he did.
- marcosdumay 6y ago
  Well, static types and analysis are in fashion now, and always moving on the direction of more powerful proof systems. He was very likely too much ahead of his time on that. Decades after him we still don't have good enough tech to do the kinds of proof he expected... And yes, maybe too arrogant to realize that it's not the entire world that is dumb, but it's a core piece of the system that is missing. On the other hand, he did work to improve proof systems, so who knows what he really thought?
olodus 6y ago
I have wondered what Dijkstra would have said about that most (from my limited view) verification advances nowadays focus on functional programming (dependant types and so forth). I get the feeling he wasn't too fond of functional programming. Or maybe he even was able to comment on it, I am not sure how far the field had moved while he was still with us. I have searched for it but could find any comment from him on the subject.
- Ericson2314 6y ago
  https://www.cs.utexas.edu/users/EWD/transcriptions/OtherDocs/Haskell.html https://www.cs.utexas.edu/users/EWD/transcriptions/OtherDocs... Actually, based on the above I think he would have been all for it. Well, I mean knowing Dijkstra he would have found something to complain about :D, but it wouldn't have been that it wasn't imperative enough!
deleted 6y ago
[deleted]
qazpot 6y ago
Arrogance in computer science is measured in nano-dijkstra. - Alan Kay
- baxrob 6y ago
  "This quote keeps on showing up out of context. Edsger and I got along quite well." - Alan Kay https://news.ycombinator.com/item?id=11796926 https://news.ycombinator.com/item?id=11796926
  - pinewurst 6y ago
    From everything I've read, Dijkstra was usually pleasant face-to-face. It was the later written backstab that one had to be prepared for.
  - joe_the_user 6y ago
    Well, the whole comment you link doesn't really deny that Dijkstra could be arrogant and dismissive, it just goes on to say essentially that he was a lovable old coot and that they listened to him only as much as they wanted; "Dijkstra was much more funny than annoying for anyone who had any sense of self. The two biggest problems in our not-quite-a-field were those who listened to him too carefully and those who didn't listen to him carefully enough."
    - ben7799 6y ago
      I read it more like people back then weren't so sensitive and didn't even take that kind of straight talk as arrogance and dismissiveness. But then maybe Alan Kay will show up and clarify. I'm just old enough to remember when corporate culture was like this too. It used to be OK to say when people were wrong or get mad when programming errors lit the building on fire. That started to become NOT OK in the past 15 years. A lot of older engineers really had to to work hard to adapt because it's so frustrating today when people make careless mistakes over and over again and no one can say a word without being accused of not being a team player or something. People were more likely to admit their own mistakes then too. In that environment it was better to come clean then try to hide a mistake even when coming forward can solve the problem faster. We've overcorrected this stuff.. correcting it helps make the field more inclusive but at some point after we're diverse and inclusive we need to walk some of this behavior back a bit.
Jtsummers 6y ago
If your opinion of Dijkstra is mostly negative and the result of reading others' opinions or selective readings of his EWDs (some of which are incredibly negative in tone), it would behoove you to read his EWDs. Just go through the archive and grab random ones based on title, then later do a more systematic reading of them.
- dryrunes 6y ago
  What is an EWD?
  - FireBy2024 6y ago
    > IN 1959, DIJKSTRA began writing a series of private reports. Consecutively numbered and with his initials as a prefix, they became known as EWDs.
  - ninly 6y ago
    He typed (edit: and handwrote) hundreds of these open letters, technical notes, reports, etc. Here's the archive at UT: https://www.cs.utexas.edu/users/EWD/ https://www.cs.utexas.edu/users/EWD/
  - Jtsummers 6y ago
    https://www.cs.utexas.edu/users/EWD/welcome.html https://www.cs.utexas.edu/users/EWD/welcome.html That's the archive, talked about in the linked article. Letters (mostly) that he wrote and sent out to people. Today we'd consider their content and length equivalent to a technical blog. Some were much longer, though.
- User23 6y ago
  I spent a year reading all of the English language ones and it has made me a MUCH better programmer. I can't recommend them highly enough. Also his book A Discipline of Programming was seminal for me.
rramadass 6y ago
A well written portrait of a truly great and original "Scientist" in the true sense of the term. I have always wondered why his approach of constructing correctness proof along with the implementation never really caught on. I think it was what allowed him to come up with his novel algorithms. Have we lost something of the real essence of logical thinking here? Perhaps the paper mentioned in the article; Social Processes and Proofs of Theorems and Programs which he was vehemently against, will give me the other side of the argument.
- ativzzz 6y ago
  Probably because the cost associated with constructing such proofs for the vast majority of modern software use cases (like showing ads on 8 different browsers) is too high (cheaper to just hire QA teams), and most programmers are not simultaneously software engineers, computer scientists, and mathematicians.
  - rramadass 6y ago
    > cost associated with constructing such proofs ... is too high People assume this is true because it has been repeated endlessly. I think it is an issue of granularity. For example; both Dijkstra's GCL and Hoare's Triples (fine granularity) vs. Meyer's DbC (coarse granularity) can be expressed using Assertions to build Preconditions/Postconditions/Invariants as "correctness proof" throughout a real-world software system. But their systematic usage is never taught nor enforced; we have to learn it by trial and error.
    - ativzzz 6y ago
      You really just made my point with your response > For example; both Dijkstra's GCL and Hoare's Triples (fine granularity) vs. Meyer's DbC (coarse granularity) can be expressed using Assertions to build Preconditions/Postconditions/Invariants as "correctness proof" throughout a real-world software system The average dev at an average company will read this and not understand 90% of your sentence. Again, the vast majority of devs are not computer scientists nor mathematicians. They are good at what they do, which is building what their bosses ask for using whatever web framework they specialize in.
znpy 6y ago
«Edsger W. Dijkstra, “Recursive Programming,” Numerische Mathematik 2 (1960): 312–18, doi:10.1007/bf01386232. » The link brings to a paywall. FFS do they really have the courage to ask 42,64€ for a paper from 1960 ?
- Joker_vD 6y ago
  Why not? The LotR was published in 1954, and won't enter the public domain for another 25 years or so... Copyright is a wonderful thing like that, surviving the death of the creator by another human lifetime.
- v64 6y ago
  Actual paper is here: https://sci-hub.st/10.1007/bf01386232 https://sci-hub.st/10.1007/bf01386232
- pmcjones 6y ago
  An open-access copy is here: MR33, Mathematisch Centrum, Amsterdam, 1960. https://ir.cwi.nl/pub/9253 https://ir.cwi.nl/pub/9253
andi999 6y ago
Somehow this gives me the impression he is a bit overrated, and he somehow developed a bit of cult-like following.
- lou1306 6y ago
  I genuinely wonder what gave you this impression. Dijkstra made seminal contributions to at least three subfields of computer science: algorithms (his optimal shortest path algorithm), programming languages (ALGOL -with others, but still- and his "goto considered harmful" paper), and concurrency theory (semaphores), just to state the most well-known ones...
  - luizfzs 6y ago
    I agree. I get the impression that he formalized several problems and provided a solution to them, e.g. the Dining Philosophers Problem: https://en.wikipedia.org/wiki/Dining_philosophers_problem https://en.wikipedia.org/wiki/Dining_philosophers_problem I think he is actually underrated. I'd have liked to be introduced to his proof notations during some formal courses on my CS formation, which was never mentioned.
    - User23 6y ago
      His proof format is amazing. I've used it ever since I discovered it in one of the last EWDs.
  - deleted 6y ago
    [deleted]
- rramadass 6y ago
  Not at all true. The Dutch are famously known to be blunt and direct which seems to be a national trait(eg: https://www.thrillist.com/travel/nation/dutch-culture-brutally-honest-people https://www.thrillist.com/travel/nation/dutch-culture-brutal...). Think of Dijkstra as Sherlock Holmes thought of himself; viz. My dear Watson,” said he, “I cannot agree with those who rank modesty among the virtues. To the logician all things should be seen exactly as they are, and to underestimate one’s self is as much a departure from truth as to exaggerate one’s own powers.
thelazydogsback 6y ago
One fun item I'm lucky enough to own is a core memory stack from Dijkstra's Electrologica computer, ca.1958 or so -- very low density obviously. This machine is where the first working Algol compiler was written.
- enchiridion 6y ago
  How do you come across something like that?
  - thelazydogsback 6y ago
    ebay baby! Went on a core memory kick a few years ago and just happened to catch an auction at the right time.
yters 6y ago
I have multiple CS and CE degrees, and learned his proofs, but industry is pretty antithetical to his approach and most CS pretty irrelevant. I am not sure he has that much real influence. Not that I don't wish it were otherwise. I love the beauty of mathematics and do wish software were more elegant.
w0mbat 6y ago
My only beef against Dijkstra is that I applied for a fairly crappy job I was eminently qualified for in terms of experience and someone told me to code Dijkstra's shunting yard algorithm on a whiteboard (well not in so many words, but that was the solution). It's a good algorithm but way beyond the scope of what you should ask in a whiteboard interview. I didn't get the job.
- _Nat_ 6y ago
  I get the sense that Dijkstra would've agreed with you and perhaps had harsh words for that interview process. Sometimes these interview stories sound like selecting a professor of mathematics by picking the one who can calculate the square-root-of-2 to 12 digits in their head the fastest.
mysterydip 6y ago
I wish seeing the name Dijkstra didn't immediately remind me of his oft-quoted BASIC comment: "It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration." The problem is it's quoted regardless of how much the BASIC dialect being discussed resembles the one he was talking about [1]. There are lots of good BASIC languages out there running all kinds of useful software that are dismissed out of hand by a subset of developers simply from that comment. [1] https://programmingisterrible.com/post/40132515169/dijkstra-basic https://programmingisterrible.com/post/40132515169/dijkstra-...
- Jtsummers 6y ago
  And there are a lot of people that dismiss his comment and the rest of his writings by ignoring what BASIC meant at the time of writing. Visual BASIC certainly wouldn't have been his favorite language, but had the features that BASIC at the time lacked and that he disliked it for (when you start digging into it: lack of recursion, non-reentrant functions, massive use of global variables, preference for goto versus structured control flow).
- nitrogen 6y ago
  My first language was actually GWBASIC on an ancient hand-me-down computer, followed by QBASIC. When I saw that quote as a teenager I was terrified that I had killed my career before it had even started. I've since become quite proficient in C, Ruby, Java, Kotlin, HTML, JS, shell scripting, and many many other languages and environments. So IMO there is very little modern merit to the idea that exposure to BASIC (or any other mocked language) is "mentally mutilat[ing]".
- root 6y ago
  BASIC only ruins you if you have no intellectual curiosity. BASIC was my first language and with each new language I’ve learned since I’ve always been excited at the new possibilities and paradigms it opened up.
  - microtherion 6y ago
todd8 6y ago
I read Dijkstra's goto considered harmful in college, circa 1970. I was a young programmer at the time, and it made me think and reconsider how and why big programs were often hard to understand. Years later, in grad school, my research was on program verification. Dijkstra was a big influence on the field. I attended a lecture at UT Austin that he gave before moving to the US. Dijkstra's approach to proving the correctness of programs is hard to apply in practice. Like a geometry proof, there are ways in which a proof of correctness can have mistakes that aren't obvious. Here's an example, prove that a sorting algorithm works. If the specification is that the output must be in sorted order, a proven program can still fail to sort correctly. The specification has an error, the output must not only be in sorted order, it must ensure that all of the input elements make it somewhere to the output. But this isn't good enough. A sort proven to meet this specification might leave out some duplicate values. Requiring that the output be the same length as the input still isn't good enough, multiple copies of one element might hide missing duplicate input values for another element. The specification requires that the output be a sorted permutation of the input. Sorting is a well understood problem, but real verification must deal with the strange mathematics implemented by computers. The mathematical theories that we are accustomed to from school assume infinite precision and no overflow, real life hardware doesn't act this way. All of this makes program verification hard, and my hope is that AI programming assistants will someday aid in the construction of meaningful specifications and work with the programmer to verify the correctness of programs or determine their safe operating boundaries. Progress has been slow, and the tools are still impractical for use by most programmers on most programs.
- mcguire 6y ago
  Take a look at Frama-C or Ada Spark sometime; they apply the predicate transformer semantics style to code and do pretty well. But yeah, incomplete specifications are always fun.
- amw-zero 6y ago
  This is such a great and actually important comment. I’ve been obsessed with program correctness / verification for a while now. It just seems like the holy grail that we can’t fully attain yet. But you keep bumping into certain walls, and the fact that correctness can only be relative to a given specification is a profoundly huge wall. There’s no checking to see if your specification is under-specified.
jamez 6y ago
Good read. For anyone interested in seeing the human side of Dijkstra, I recommend this documentary: https://www.youtube.com/watch?v=RCCigccBzIU https://www.youtube.com/watch?v=RCCigccBzIU When I watched it I was both studying Computer Science and learning Dutch, so it was twice as interesting. The version I linked provides English subtitles.
- deleted 6y ago
  [deleted]
- rramadass 6y ago
  Neat video! Thanks for posting it.
mcguire 6y ago
As an aside, I took a History of Logic course from Krzysztof Apt (https://inference-review.com/author/krzysztof-apt/ https://inference-review.com/author/krzysztof-apt/) while I was an undergrad and he was briefly at UT Austin. He is an excellent teacher and a very nice man. (He loaned me a copy of a book on Frege's logic during the course---it had been signed and given to him by the person who let him stay on their floor when he first came to the US.)
microtherion 6y ago
This is a really nice article on Dijkstra, both more detailed about his contributions and more balanced about his limitations — many articles about him are too hagiographic to my taste.
jakespoon 6y ago
Backus literally inspired functional programming with his Turing acceptance and Dijkstra attacked him for it. Dijkstra attacked the paper that inspired Haskell and everything else that currently exists in FP. He tried to destroy it. He should be a footnote in history.
- thotsBgone 6y ago
  The Whine Law: There will always be someone in every Hacker News comment section to whine like a baby. Every topic, every thread. Someone will whine.
  - assap_cocky 6y ago
    We both can't be right!
- Jtsummers 6y ago
  Functional programming already existed in a few forms by the 1977 Turing Award lecture. ML was around since 1973, which defined the ML family (Ocaml, SML, F#) and influenced Haskell and others. The Lisp family of languages had been around since 1958. Some parts of the lecture can be seen as related to languages in the APL family (originated in 1965). These developments influenced the lecture itself. To gain context into Dijkstra's response, it may be worth reading it [0]. Here's the conclusion of his response: > In short, the article is a progress report on a valid research effort but suffers badly from aggressive overselling of its significance, long before convincing results have been reached. This is the more regrettable as it has been published by way of Turing Award Lecture. Regarding "He tried to destroy it." Dijkstra is known, and often criticized by others, for his hyperbole. Perhaps instead of imitating this heavily criticized aspect of his, you could tone down your rhetoric and actually create an argument rather than try to dismiss someone (and all their work) for one thing you disagree with. [0] https://www.cs.utexas.edu/users/EWD/transcriptions/EWD06xx/EWD692.html https://www.cs.utexas.edu/users/EWD/transcriptions/EWD06xx/E...
  - jakespoon 6y ago
    So, looking back from 2020, did Backus oversell it? We aren't there yet but it still looks like the right direction to me.
a_136_chiffa 6y ago
Alan Kay on Dijkstra, (1997 OOPSLA keynote): '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.' Was this article written by Dijkstra himself?

444 points by furcyd 6y ago

> ALGOL 60 included a series of novel features, such as recursion, which was supported in a much more complex manner than logicians had ever envisaged...Recursive procedures in ALGOL 60 are much more complex than in Lisp. Can anyone explain how this "much more complex" recursion works?

deleted 6y ago
[deleted]
azhenley 6y ago
There is an interesting write-up about Algol 60's recursion [0] that was discussed here before [1]. [0] https://vanemden.wordpress.com/2014/06/18/how-recursion-got-into-programming-a-comedy-of-errors-3/ https://vanemden.wordpress.com/2014/06/18/how-recursion-got-... [1] https://news.ycombinator.com/item?id=10131664 https://news.ycombinator.com/item?id=10131664
niea_11 6y ago
I did a quick search and according to this article [1], dijkstra's implementation was not restricted compared to other implementations at the time : It is Dijkstra's generalizing style which stands out when a comparison is made with the work of his contemporaries. Rutishauser, for example, had limited the order of his procedure activations in his run-time system [59], while Dijkstra had no such restriction. Floyd's work [60, p.42-43] relied on three specialized “yo-yo” lists (i.e., stacks) instead of one general stack. Likewise, the MAD translator [61, p.28] used several specialized tables. Also, and most importantly, the ALCOR compilers were severely restricted in that they could not handle several ALGOL60 language constructs, including the recursive procedure (cf. Section ). Finally, though the Irons-Feurzeig system [54] did implement recursive-procedure activations and by means of one general run-time stack, it was, in the interest of efficiency, sophisticated in its run-time capabilities and, hence, unlike the run-time system of Dijkstra and Zonneveld . [1] : https://www.dijkstrascry.com/node/4 https://www.dijkstrascry.com/node/4
Someone 6y ago
I think this refers to making the implementation efficient. They wanted performance on par with existing languages that didn’t allow recursion, and could simply assign fixed addresses to all function arguments and local variables. Lisp didn’t have that. It allocated environments left and right. That meant that a function call allocated memory and potentially could trigger garbage collection. The major improvement was to use a runtime stack. That was fairly novel. Earlier compilers used a stack at compile time to make it possible that those fixed addresses for arguments and locals could be shared between functions that didn’t call each other, directly or indirectly, but that stack didn’t exist at runtime. And yes, the idea of a stack seems trivial nowadays, but it wasn’t at the time. Quite a few CPUs didn’t even have “jump to subroutine” or “return from subroutine” instructions. Algol’s “call by name” feature also may have complicated this, but I don’t see how that’s more difficult than passing lambdas as arguments.
- wilsonthewhale 6y ago
  Do you have any references or papers that developed the idea of having a stack at runtime? I love reading into the fundamentals of modern computing.
  - mjn 6y ago
    Dijkstra's paper "Recursive Programming" (1960) is where he lays out his proposal for implementing recursive Algol-60 subroutines with a stack: https://www.ics.uci.edu/~jajones/INF102-S18/readings/07_dijkstra.pdf https://www.ics.uci.edu/~jajones/INF102-S18/readings/07_dijk...
- throwaway_pdp09 6y ago
  I'm not sure that's fair. If you have objects that escape downwards (so X calls Y, y creates some item i, i gets returned to X) then you can't have a stack. i may be overwritten at the next call of anything else, as the stack grows over it. I guess they do escape analysis and where items are provably local, stack allocate them. If not, plonk them on the heap. A call frame is an object like any other, so they go on the heap. This allows you to create closures.
throwaway_pdp09 6y ago
The answers to this question are extremely interesting and show how much work has been done to get where we are today, a position I took for granted and never really understood until now (even in name: 'yo-yo list', for heaven's sake!) It's a bit like parsing, these days we either reach for a technique (eg. recursive descent) or an implementation of a tool (such as flex/bison) and never think there was a time before these where people had to struggle conceptually with these things.
todd8 6y ago
Early LISP implementations used dynamic scope. This means that non-local references in a function search for the variable's binding in the call chain: if A calls B then when B uses nonlocal variable x it refers to the x in A, not necessarily the x that belongs in the lexical parent of B as seen in the source code. (Unlike C, Algol/Pascal/LISP can all define functions inside of other functions. These nested function definitions introduce lexical non-local scopes.) Dynamic scoping is easier to implement than lexical scoping. With lexical scoping, the run-time must incorporate some mechanism to find the stack frame of a lexical parent (as seen in the program's source code) to access a nonlocal variable's value. In dynamic scoping the run-time can just follow the stack frame order (starting at the top) to find a nonlocal variable's binding. Early LISP used dynamic scope. Scheme had lexical scope from the beginning. Common Lisp had both mechanisms and programs can use both. The implementation of recursion also has to address proper access to nonlocal variables in functions that are values themselves and are passed as arguments to other functions. Do these functions access the nonlocal variables based on their call location or their lexical location in the source code? These problems with functions as arguments are known as the upward and downward funarg problems. Knuth wrote the man-boy program to test Algol 60 implementations in these areas. Another complication for implementors of Algol 60 was parameter passing by-name, which is neither by-value nor by-reference. I don't recall any other well known language that has subsequently made that non-intuitive (to me) choice. I believe that Algol 68 abandoned call by-name, but it's been 25 years since I looked at the Algol 68 standard.
- geophile 6y ago
  I may be fuzzy on this, it's been a long time. But isn't by-name a special case of passing a function? (And then referencing the parameter in the called procedure invokes the function.)
  - todd8 6y ago
    Yes, that's how "Jensen's Device" is used to implement call-by-name. However, note that the expression passed to an Algol 60 function by name causes the expression to be evaluated in the context of the function being called. Each time the formal parameter appears in the called function the expression passed to that parameter is re-evaluated.

amelius 6y ago

What are the greatest advances in CS of the last decade?

deleted 6y ago
[deleted]
jnsie 6y ago
Editor support for Dark Mode? (I jest)
wyldfire 6y ago
To me -- a casual novice -- it sounds like a lot of recent CS work results in things like CAP Theorem/consensus, NLP/AI models, AGI, practical tools for verification/formal methods.
- sideshowb 6y ago
  I don't think we've made much progress towards AGI, but having reliable approaches to object recognition in images is fairly new, as is putting enough of that sort of thing together to make a self driving car.
glouwbug 6y ago
Leet code styled interviews
caleb-allen 6y ago
Session types may be up there? Or maybe progress on homomorphic encryption. Also, progress in quantum computing.
hinkley 6y ago
The older I get the harder it is to time-slot things, but I can think of a few things where much of the interesting work happened in the last ten years (similar to how a lot of pivotal work on GC algorithms happened in the late 90's). Most of the good work on escape analysis started around ~2010 Rust got us rolling on borrow semantics (I have a feeling the '20s will be remembered as the the golden age) I'm sure there's a thing or two in or around LLVM that would rank, but I'm not paying close enough attention. From a 'renaissance' standpoint: - LZ-family compression algorithms - Multi-tenant process isolation (containers) - transport protocols - Consensus algorithms

xenocyon 6y ago

It is remarkable how much he contravened modern academic norms: no work to bring in external funding, relatively few papers, very little collaboration, almost no PhD students. It's not an exaggeration to say that a young researcher with these characteristics today would likely get fired from any high-ranked American research university before even coming up for tenure review. Perhaps our modern academic metrics of merit are missing something?

nurettin 6y ago
It would be very funny to watch foremost experts in relatively new fields being denied because they don't have phd students. I somehow doubt this is the case, though.
marcosdumay 6y ago
> It's not an exaggeration to say that a young researcher with these characteristics today would likely get fired from any high-ranked American research university before even coming up for tenure review. He wouldn't even get in an university to get the chance to be fired. And that's not specific to the US, it applies to nearly all developed or developing countries. That person wouldn't be able to get much past a PhD, even as a student.
- gautamdivgi 6y ago
  You’re right. The right of passage for most US computer science PhD programs is publications in the “right” journals and conferences. If you don’t publish you will rarely get past your thesis proposal. I think there are very few, very select professors in the US that prohibit publishing prior to graduating. But their count is likely in the single digits. Also, by some miracle you manage to graduate by minimal publishing or no publications you will find all doors to getting research funding shut. This means that you are basically unemployable as a tenure track professor (universities prefer their newly minted assistant professors to come with funding).
  - mcguire 6y ago
    Yes, it's true. EWD published almost nothing. http://www.netlib.org/bibnet/authors/d/dijkstra-edsger-w.html http://www.netlib.org/bibnet/authors/d/dijkstra-edsger-w.htm... (The ones marked "circulated privately" are the EWD series.)

AnimalMuppet 6y ago

Or at least who thought he carried computer science on his shoulders. He made significant, important contributions. He wasn't the only one. Hoare, Backus, McCarthy... there were a lot of people who made important, fundamental contributions. Structured programming caught on. Proofs did not, for reasons that would have offended Dijkstra - they took time, and it was actually more valuable (both socially and financially) to produce mostly-working software quickly than to produce proven-correct software slowly. But he never would have accepted that the real world was that way. He insisted that his approach was correct. As Backus said of him, "This guy’s arrogance takes your breath away." So: Important contributions? Absolutely. More than anyone else's? Perhaps. Carried computer science on his shoulders? No, but he probably thought he did.

marcosdumay 6y ago
Well, static types and analysis are in fashion now, and always moving on the direction of more powerful proof systems. He was very likely too much ahead of his time on that. Decades after him we still don't have good enough tech to do the kinds of proof he expected... And yes, maybe too arrogant to realize that it's not the entire world that is dumb, but it's a core piece of the system that is missing. On the other hand, he did work to improve proof systems, so who knows what he really thought?

olodus 6y ago

I have wondered what Dijkstra would have said about that most (from my limited view) verification advances nowadays focus on functional programming (dependant types and so forth). I get the feeling he wasn't too fond of functional programming. Or maybe he even was able to comment on it, I am not sure how far the field had moved while he was still with us. I have searched for it but could find any comment from him on the subject.

Ericson2314 6y ago
https://www.cs.utexas.edu/users/EWD/transcriptions/OtherDocs/Haskell.html https://www.cs.utexas.edu/users/EWD/transcriptions/OtherDocs... Actually, based on the above I think he would have been all for it. Well, I mean knowing Dijkstra he would have found something to complain about :D, but it wouldn't have been that it wasn't imperative enough!

deleted 6y ago

[deleted]

qazpot 6y ago

Arrogance in computer science is measured in nano-dijkstra. - Alan Kay

baxrob 6y ago
"This quote keeps on showing up out of context. Edsger and I got along quite well." - Alan Kay https://news.ycombinator.com/item?id=11796926 https://news.ycombinator.com/item?id=11796926
- pinewurst 6y ago
  From everything I've read, Dijkstra was usually pleasant face-to-face. It was the later written backstab that one had to be prepared for.
- joe_the_user 6y ago
  Well, the whole comment you link doesn't really deny that Dijkstra could be arrogant and dismissive, it just goes on to say essentially that he was a lovable old coot and that they listened to him only as much as they wanted; "Dijkstra was much more funny than annoying for anyone who had any sense of self. The two biggest problems in our not-quite-a-field were those who listened to him too carefully and those who didn't listen to him carefully enough."
  - ben7799 6y ago
    I read it more like people back then weren't so sensitive and didn't even take that kind of straight talk as arrogance and dismissiveness. But then maybe Alan Kay will show up and clarify. I'm just old enough to remember when corporate culture was like this too. It used to be OK to say when people were wrong or get mad when programming errors lit the building on fire. That started to become NOT OK in the past 15 years. A lot of older engineers really had to to work hard to adapt because it's so frustrating today when people make careless mistakes over and over again and no one can say a word without being accused of not being a team player or something. People were more likely to admit their own mistakes then too. In that environment it was better to come clean then try to hide a mistake even when coming forward can solve the problem faster. We've overcorrected this stuff.. correcting it helps make the field more inclusive but at some point after we're diverse and inclusive we need to walk some of this behavior back a bit.

Jtsummers 6y ago

If your opinion of Dijkstra is mostly negative and the result of reading others' opinions or selective readings of his EWDs (some of which are incredibly negative in tone), it would behoove you to read his EWDs. Just go through the archive and grab random ones based on title, then later do a more systematic reading of them.

dryrunes 6y ago
What is an EWD?
- FireBy2024 6y ago
  > IN 1959, DIJKSTRA began writing a series of private reports. Consecutively numbered and with his initials as a prefix, they became known as EWDs.
- ninly 6y ago
  He typed (edit: and handwrote) hundreds of these open letters, technical notes, reports, etc. Here's the archive at UT: https://www.cs.utexas.edu/users/EWD/ https://www.cs.utexas.edu/users/EWD/
- Jtsummers 6y ago
  https://www.cs.utexas.edu/users/EWD/welcome.html https://www.cs.utexas.edu/users/EWD/welcome.html That's the archive, talked about in the linked article. Letters (mostly) that he wrote and sent out to people. Today we'd consider their content and length equivalent to a technical blog. Some were much longer, though.
User23 6y ago
I spent a year reading all of the English language ones and it has made me a MUCH better programmer. I can't recommend them highly enough. Also his book A Discipline of Programming was seminal for me.

rramadass 6y ago

A well written portrait of a truly great and original "Scientist" in the true sense of the term. I have always wondered why his approach of constructing correctness proof along with the implementation never really caught on. I think it was what allowed him to come up with his novel algorithms. Have we lost something of the real essence of logical thinking here? Perhaps the paper mentioned in the article; Social Processes and Proofs of Theorems and Programs which he was vehemently against, will give me the other side of the argument.

ativzzz 6y ago
Probably because the cost associated with constructing such proofs for the vast majority of modern software use cases (like showing ads on 8 different browsers) is too high (cheaper to just hire QA teams), and most programmers are not simultaneously software engineers, computer scientists, and mathematicians.
- rramadass 6y ago
  > cost associated with constructing such proofs ... is too high People assume this is true because it has been repeated endlessly. I think it is an issue of granularity. For example; both Dijkstra's GCL and Hoare's Triples (fine granularity) vs. Meyer's DbC (coarse granularity) can be expressed using Assertions to build Preconditions/Postconditions/Invariants as "correctness proof" throughout a real-world software system. But their systematic usage is never taught nor enforced; we have to learn it by trial and error.
  - ativzzz 6y ago
    You really just made my point with your response > For example; both Dijkstra's GCL and Hoare's Triples (fine granularity) vs. Meyer's DbC (coarse granularity) can be expressed using Assertions to build Preconditions/Postconditions/Invariants as "correctness proof" throughout a real-world software system The average dev at an average company will read this and not understand 90% of your sentence. Again, the vast majority of devs are not computer scientists nor mathematicians. They are good at what they do, which is building what their bosses ask for using whatever web framework they specialize in.

znpy 6y ago

«Edsger W. Dijkstra, “Recursive Programming,” Numerische Mathematik 2 (1960): 312–18, doi:10.1007/bf01386232. » The link brings to a paywall. FFS do they really have the courage to ask 42,64€ for a paper from 1960 ?

Joker_vD 6y ago
Why not? The LotR was published in 1954, and won't enter the public domain for another 25 years or so... Copyright is a wonderful thing like that, surviving the death of the creator by another human lifetime.
v64 6y ago
Actual paper is here: https://sci-hub.st/10.1007/bf01386232 https://sci-hub.st/10.1007/bf01386232
pmcjones 6y ago
An open-access copy is here: MR33, Mathematisch Centrum, Amsterdam, 1960. https://ir.cwi.nl/pub/9253 https://ir.cwi.nl/pub/9253

andi999 6y ago

Somehow this gives me the impression he is a bit overrated, and he somehow developed a bit of cult-like following.

lou1306 6y ago
I genuinely wonder what gave you this impression. Dijkstra made seminal contributions to at least three subfields of computer science: algorithms (his optimal shortest path algorithm), programming languages (ALGOL -with others, but still- and his "goto considered harmful" paper), and concurrency theory (semaphores), just to state the most well-known ones...
- luizfzs 6y ago
  I agree. I get the impression that he formalized several problems and provided a solution to them, e.g. the Dining Philosophers Problem: https://en.wikipedia.org/wiki/Dining_philosophers_problem https://en.wikipedia.org/wiki/Dining_philosophers_problem I think he is actually underrated. I'd have liked to be introduced to his proof notations during some formal courses on my CS formation, which was never mentioned.
  - User23 6y ago
    His proof format is amazing. I've used it ever since I discovered it in one of the last EWDs.
- deleted 6y ago
  [deleted]
rramadass 6y ago
Not at all true. The Dutch are famously known to be blunt and direct which seems to be a national trait(eg: https://www.thrillist.com/travel/nation/dutch-culture-brutally-honest-people https://www.thrillist.com/travel/nation/dutch-culture-brutal...). Think of Dijkstra as Sherlock Holmes thought of himself; viz. My dear Watson,” said he, “I cannot agree with those who rank modesty among the virtues. To the logician all things should be seen exactly as they are, and to underestimate one’s self is as much a departure from truth as to exaggerate one’s own powers.

thelazydogsback 6y ago

One fun item I'm lucky enough to own is a core memory stack from Dijkstra's Electrologica computer, ca.1958 or so -- very low density obviously. This machine is where the first working Algol compiler was written.

enchiridion 6y ago
How do you come across something like that?
- thelazydogsback 6y ago
  ebay baby! Went on a core memory kick a few years ago and just happened to catch an auction at the right time.

yters 6y ago

I have multiple CS and CE degrees, and learned his proofs, but industry is pretty antithetical to his approach and most CS pretty irrelevant. I am not sure he has that much real influence. Not that I don't wish it were otherwise. I love the beauty of mathematics and do wish software were more elegant.

w0mbat 6y ago

My only beef against Dijkstra is that I applied for a fairly crappy job I was eminently qualified for in terms of experience and someone told me to code Dijkstra's shunting yard algorithm on a whiteboard (well not in so many words, but that was the solution). It's a good algorithm but way beyond the scope of what you should ask in a whiteboard interview. I didn't get the job.

_Nat_ 6y ago
I get the sense that Dijkstra would've agreed with you and perhaps had harsh words for that interview process. Sometimes these interview stories sound like selecting a professor of mathematics by picking the one who can calculate the square-root-of-2 to 12 digits in their head the fastest.

mysterydip 6y ago

I wish seeing the name Dijkstra didn't immediately remind me of his oft-quoted BASIC comment: "It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration." The problem is it's quoted regardless of how much the BASIC dialect being discussed resembles the one he was talking about [1]. There are lots of good BASIC languages out there running all kinds of useful software that are dismissed out of hand by a subset of developers simply from that comment. [1] https://programmingisterrible.com/post/40132515169/dijkstra-basic https://programmingisterrible.com/post/40132515169/dijkstra-...

Jtsummers 6y ago
And there are a lot of people that dismiss his comment and the rest of his writings by ignoring what BASIC meant at the time of writing. Visual BASIC certainly wouldn't have been his favorite language, but had the features that BASIC at the time lacked and that he disliked it for (when you start digging into it: lack of recursion, non-reentrant functions, massive use of global variables, preference for goto versus structured control flow).
nitrogen 6y ago
My first language was actually GWBASIC on an ancient hand-me-down computer, followed by QBASIC. When I saw that quote as a teenager I was terrified that I had killed my career before it had even started. I've since become quite proficient in C, Ruby, Java, Kotlin, HTML, JS, shell scripting, and many many other languages and environments. So IMO there is very little modern merit to the idea that exposure to BASIC (or any other mocked language) is "mentally mutilat[ing]".
root 6y ago
BASIC only ruins you if you have no intellectual curiosity. BASIC was my first language and with each new language I’ve learned since I’ve always been excited at the new possibilities and paradigms it opened up.
- microtherion 6y ago

todd8 6y ago

I read Dijkstra's goto considered harmful in college, circa 1970. I was a young programmer at the time, and it made me think and reconsider how and why big programs were often hard to understand. Years later, in grad school, my research was on program verification. Dijkstra was a big influence on the field. I attended a lecture at UT Austin that he gave before moving to the US. Dijkstra's approach to proving the correctness of programs is hard to apply in practice. Like a geometry proof, there are ways in which a proof of correctness can have mistakes that aren't obvious. Here's an example, prove that a sorting algorithm works. If the specification is that the output must be in sorted order, a proven program can still fail to sort correctly. The specification has an error, the output must not only be in sorted order, it must ensure that all of the input elements make it somewhere to the output. But this isn't good enough. A sort proven to meet this specification might leave out some duplicate values. Requiring that the output be the same length as the input still isn't good enough, multiple copies of one element might hide missing duplicate input values for another element. The specification requires that the output be a sorted permutation of the input. Sorting is a well understood problem, but real verification must deal with the strange mathematics implemented by computers. The mathematical theories that we are accustomed to from school assume infinite precision and no overflow, real life hardware doesn't act this way. All of this makes program verification hard, and my hope is that AI programming assistants will someday aid in the construction of meaningful specifications and work with the programmer to verify the correctness of programs or determine their safe operating boundaries. Progress has been slow, and the tools are still impractical for use by most programmers on most programs.

mcguire 6y ago
Take a look at Frama-C or Ada Spark sometime; they apply the predicate transformer semantics style to code and do pretty well. But yeah, incomplete specifications are always fun.
amw-zero 6y ago
This is such a great and actually important comment. I’ve been obsessed with program correctness / verification for a while now. It just seems like the holy grail that we can’t fully attain yet. But you keep bumping into certain walls, and the fact that correctness can only be relative to a given specification is a profoundly huge wall. There’s no checking to see if your specification is under-specified.

jamez 6y ago

Good read. For anyone interested in seeing the human side of Dijkstra, I recommend this documentary: https://www.youtube.com/watch?v=RCCigccBzIU https://www.youtube.com/watch?v=RCCigccBzIU When I watched it I was both studying Computer Science and learning Dutch, so it was twice as interesting. The version I linked provides English subtitles.

deleted 6y ago
[deleted]
rramadass 6y ago
Neat video! Thanks for posting it.

mcguire 6y ago

As an aside, I took a History of Logic course from Krzysztof Apt (https://inference-review.com/author/krzysztof-apt/ https://inference-review.com/author/krzysztof-apt/) while I was an undergrad and he was briefly at UT Austin. He is an excellent teacher and a very nice man. (He loaned me a copy of a book on Frege's logic during the course---it had been signed and given to him by the person who let him stay on their floor when he first came to the US.)

microtherion 6y ago

This is a really nice article on Dijkstra, both more detailed about his contributions and more balanced about his limitations — many articles about him are too hagiographic to my taste.

jakespoon 6y ago

Backus literally inspired functional programming with his Turing acceptance and Dijkstra attacked him for it. Dijkstra attacked the paper that inspired Haskell and everything else that currently exists in FP. He tried to destroy it. He should be a footnote in history.

thotsBgone 6y ago
The Whine Law: There will always be someone in every Hacker News comment section to whine like a baby. Every topic, every thread. Someone will whine.
- assap_cocky 6y ago
  We both can't be right!
Jtsummers 6y ago
Functional programming already existed in a few forms by the 1977 Turing Award lecture. ML was around since 1973, which defined the ML family (Ocaml, SML, F#) and influenced Haskell and others. The Lisp family of languages had been around since 1958. Some parts of the lecture can be seen as related to languages in the APL family (originated in 1965). These developments influenced the lecture itself. To gain context into Dijkstra's response, it may be worth reading it [0]. Here's the conclusion of his response: > In short, the article is a progress report on a valid research effort but suffers badly from aggressive overselling of its significance, long before convincing results have been reached. This is the more regrettable as it has been published by way of Turing Award Lecture. Regarding "He tried to destroy it." Dijkstra is known, and often criticized by others, for his hyperbole. Perhaps instead of imitating this heavily criticized aspect of his, you could tone down your rhetoric and actually create an argument rather than try to dismiss someone (and all their work) for one thing you disagree with. [0] https://www.cs.utexas.edu/users/EWD/transcriptions/EWD06xx/EWD692.html https://www.cs.utexas.edu/users/EWD/transcriptions/EWD06xx/E...
- jakespoon 6y ago
  So, looking back from 2020, did Backus oversell it? We aren't there yet but it still looks like the right direction to me.

a_136_chiffa 6y ago

Alan Kay on Dijkstra, (1997 OOPSLA keynote): '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.' Was this article written by Dijkstra himself?