Hacker News Reader

Comment by shadowofneptune | Hacker News Reader

One feature, as far as I can tell, that no languages had until Algol-60 was recursion (https://craftofcoding.wordpress.com/2020/12/01/recursion-the...).

It's hard to imagine nowadays how controversial this was. Previous versions of Algol did not necessarily require any form of dynamic memory allocation. Recursion requires it in some form to avoid overwriting a procedure's variables upon the recursive call.

Languages that forbid recursion (like Fortran before F90) can allocate for peak memory usage before runtime, which is especially useful on RAM-poor computers.

EDIT: The site also has a great quote on the subject (https://craftofcoding.wordpress.com/2022/10/20/d%c8%b3kstra-...).

View on HN

I never cease to be amazed by the fact that Algol-60 was standardized in the form that it was. It's not just that there were many innovations there - it's the complexity of implementation. Recursion (at the time) was one of the sticking points, but there were far bigger ones!

Consider, rather, the fact that Algol-60 had nested functions which captured the enclosing environment and could also be passed as arguments to other functions. Or call-by-name, whereby expression used as an argument in a function call would be re-evaluated every time it's referenced inside the function - again, kinda like closure, except this one could also be used on the left side of assignment. Or the ability to pass labels as function arguments, which could then be used for nonlocal goto across multiple function boundaries.

And now try to implement all this in a compiler targeting a machine with memory measured in kilobytes. Oh, and the compiler itself also runs on another such machine.

For the curious, here's the language specification: https://www.masswerk.at/algol60/report.htm

"The more I ponder the principles of language design, and the techniques that put them into practice, the more is my amazement at and admiration of ALGOL 60. Here is a language so far ahead of its time that it was not only an improvement on its predecessors but also on nearly all its successors."

- C.A.R. Hoare in 1974 in "Hints on programming language design"

https://www.cs.yale.edu/flint/cs428/doc/HintsPL.pdf

I would actually disagree with that - call-by-name is very much an anti-feature, for example, as are goto-labels-as-function-arguments. And, at the same time, crucial features such as pointers were missing.

OTOH Algol 68 is a whole different story, and for all its weirdness (much of which is terminological - "transput" for I/O, "mode" for type etc), its extreme orthogonality and consistency is very elegant.

And then comes a group of folks and throws most of Algol achievements in safety, by creating an OS with a systems language where everything goes.

When you have a single fixed activation record per routine you also lose reentrance, not just recursion. Which means any tasking system has to be designed around that as well. A low priority task in the middle of a call cannot be suspended if a higher priority task needs to make use of the same subroutine, as an example. So all tasks have to run to completion or to some known safe points.

> Recursion requires [dynamic memory allocation] in some form to avoid overwriting a procedure's variables upon the recursive call.

Technically untrue, actually; you can require any potentially-recursive procedure to take a (pointer to a) array of stack frames to use when making a recursive call. However I don't know of any programming languages that actually do that, rather than supporting stack frames implicitly or (historically) prohibiting recursion altogether.

Having an explicit stack as part of the algorithm is not usually counted as recursion, as far as I know.

Do I remember correctly, that the stack variables were controversial even when developing C, and the compromise was that it supported both with `static` and `auto` keywords, and the controversy moved to what is the default, which was sneakily set to `auto`.

Of course Lisp had recursion before Algol60.

Indeed, Lisp contributed to why Algol 60 has recursion. Quoting https://vanemden.wordpress.com/2014/06/18/how-recursion-got-...

> McCarthy, fresh from the success of his Lisp project, was enthusiastic about recursion as an elegant way to get computers to do what they are best at: repeat execution of the same code with suitable modification each time around. In fact, the first Lisp had no iteration, so that the only way to add all elements of a linear list was to write a recursively defined function. As a member of the Algol committee he proposed making the possibility of recursion a feature of the new language. The proposal was crowded out by more pressing concerns. The result was that in the early months of 1960, when the report was to be finalized, there was no consensus on recursion.

Lisp was in fact returning up from 19 levels of recursion, when it encountered Algol that was just starting on its way down. Lisp thumbed its nose:

"I got there first, Algol; don't bother looking for the return value!"

Ah, of course I forgot lisp. Came so early, considering what it could do.

Reply on news.ycombinator.com