News for hackers. Stuff that matters.
Re:How recursion got into Algol 60: a comedy of errors by munificent on Thursday August 27, 2015 @07:55PM (#10132901)
> I don't understand what's weird and special about recursion

Here's one way to see why recursion is special. Look at it from the perspective of implementing the language.

If your language doesn't have recursion, you can treat every local variable in your program as if it were a static global variable. It's local in terms of name scope, but you can give it a fixed blob of memory that you pick at compile time.

This is exactly what early Fortran compilers did. foo()'s local variables go here, bar()s go here, etc. You can do away with the stack entirely, I believe.

So, without recursion, you can make your entire program only use statically allocated memory. You can be sure it will never, ever ever run out of memory.

Re:How recursion got into Algol 60: a comedy of errors by bodyfour on Friday August 28, 2015 @07:14AM (#10134765)
Yep, exactly. For instance the natural calling convention on the PDP-8 was that the return address was stored before the contents of the called function (i.e. in C terms it looked like "funcaddr[-1] = pc; pc = funcaddr;") I think other machines of that vintage and older were similar.

This meant you could support function calling without the need for a stack. However you can't directly support recursive (or co-recursive) functions. Nor could you ever do things like multithreading or shared libraries, although hose obviously weren't concerns at that time.

Today we think of the callstack as a fundamental part of the machine architecture, but at the time of algol-60 it was still a very contentious subject.

Re:How recursion got into Algol 60: a comedy of errors by sn41 on Thursday August 27, 2015 @08:59PM (#10133104)
Thank You for that interesting view. Do you have a reference for the early Fortran compiler design? I've always wondered why people say Fortran is blazing fast, even compared to C.
Re:How recursion got into Algol 60: a comedy of errors by blt on Thursday August 27, 2015 @09:41PM (#10133289)
From what I've read, Fortran's performance advantage over C is mainly due to a lack of pointer aliasing[1] which permits the compiler to optimize more aggressively.

I am curious to know if modern Fortran compilers still use static allocation for local variables when compiling in Fortran 77 mode. I'd guess the cache advantages of keeping parameters close together in memory compensates for the extra work of manipulating the stack, but who knows...

[1] https://en.wikipedia.org/wiki/Pointer_aliasing

Re:How recursion got into Algol 60: a comedy of errors by munificent on Friday August 28, 2015 @01:55AM (#10133932)
I don't offhand, but that's what the article is referring to when it says:

> And this is what they wanted to remove because they wanted static allocation of procedure activation records.

From what I can tell with a bit of digging, machines/compilers back then didn't even use return stacks for subroutines. Instead, they used self-modifying code (!).

To return from a subroutine call, you'd do something like this:

1. When compiling a subroutine, add a JUMP followed by an address to the end.

2. When you call a subroutine, modify the code to change that address to point back to the callee.

3. Jump to the subroutine.

4. When it's done running, it hits the last JUMP and jumps back to the caller.

With this, you don't need any concept of a call stack at all. But it obviously prohibits recursion since the later call would trash the earlier one's return address.

Re:How recursion got into Algol 60: a comedy of errors by mhink on Friday August 28, 2015 @02:43AM (#10134018)
So instead of a call stack, you have a call linked list? That's a pretty wild world to imagine.
Re:How recursion got into Algol 60: a comedy of errors by FullyFunctional on Friday August 28, 2015 @12:10PM (#10136237)
Nothing wild about that. Implementations using frame pointers effectively have exactly that and in some architectures, like SPARC, this is mandatory. Furthermore, some functional languages (SML and some Scheme implementations) do this explicitly. For one this, it make call-with-current-continuation much simpler to implement.