Edsger Dijkstra – The Man Who Carried Computer Science on His Shoulders
inference-review.com
Edsger Dijkstra – The Man Who Carried Computer Science on His Shoulders
1–10 of 206 posts
Re: Edsger Dijkstra – The Man Who Carried Computer Science on His Shoulders
#2> 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?
Re: Edsger Dijkstra – The Man Who Carried Computer Science on His Shoulders
#3> 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]
Re: Edsger Dijkstra – The Man Who Carried Computer Science on His Shoulders
#4> 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?
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-...
Re: Edsger Dijkstra – The Man Who Carried Computer Science on His Shoulders
#5> 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?
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 .
Re: Edsger Dijkstra – The Man Who Carried Computer Science on His Shoulders
#6What are the greatest advances in CS of the last decade?
Re: Edsger Dijkstra – The Man Who Carried Computer Science on His Shoulders
#7What are the greatest advances in CS of the last decade?
[deleted]
Re: Edsger Dijkstra – The Man Who Carried Computer Science on His Shoulders
#8What are the greatest advances in CS of the last decade?
Editor support for Dark Mode? (I jest)
Re: Edsger Dijkstra – The Man Who Carried Computer Science on His Shoulders
#9> 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?
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.
Re: Edsger Dijkstra – The Man Who Carried Computer Science on His Shoulders
#10What are the greatest advances in CS of the last decade?
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.