4 ms·

I remember reading about arguments over whether Algol should permit recursive procedures, where one side of the argument was apparently claiming that they would

I remember reading about arguments over whether Algol should permit recursive procedures, where one side of the argument was apparently claiming that they wouldn't be possible to implement. That seems pretty strange to modern ears, but maybe the underlying point was that it isn't possible to statically know how much stack size would be required. I suppose it wouldn't have been obvious then that if you fudge the issue for the first thirty years or so, everyone will just accept that this is the way the world is. Still, it's a bit of a shame that there are still widely-used systems where if you exceed the available stack space you're likely to face a "weird crash" rather than a clean error message at runtime.

mananaysiempre 5y ago
Contemporary books (incl. TAoCP Vol. 1 IIRC) don’t place return addresses on a stack or in a register at all: you’re generally told to modify the operand of the jump instruction at the end of the procedure you want to call then jump to its entry point. It took a while before reentrancy was even recognized as a possibility, let alone used (by humans or compilers) by default. I remember reading that the call stack was invented as an implementation device for recursion as introduced in Algol, but I can’t recall how that claim was sourced.
jerf 5y ago
"but maybe the underlying point was that it isn't possible to statically know how much stack size would be required." Given the time frame you're talking about, remember to be thinking in terms of kilobytes, not gigabytes. And potentially low-single-digit numbers of kilobytes. It could be in the range of hundreds of bytes dedicated to stacks at the time. Even if you could compute your maximum size it's easy to imagine people balking a the results of such a computation and think it's not worth it to even consider the possibility because you'd blow your stack so quickly it's not like there'd be any benefit to it.
a1369209993 5y ago
> it isn't possible to statically know how much stack size would be required. It's not just that - if it were merely that you couldn't know the size statically, you could use dynamic memory allocation. The problem with that though, is that now every (not provably nonrecursive) function call can now fail with a memory allocation error, and if your language doesn't surface that to the caller, and (correctly) doesn't allow spurious errors to appear out of nowhere (cough every modern programming language cough cough), there's no way to handle that error.

mananaysiempre 5y ago

Contemporary books (incl. TAoCP Vol. 1 IIRC) don’t place return addresses on a stack or in a register at all: you’re generally told to modify the operand of the jump instruction at the end of the procedure you want to call then jump to its entry point. It took a while before reentrancy was even recognized as a possibility, let alone used (by humans or compilers) by default. I remember reading that the call stack was invented as an implementation device for recursion as introduced in Algol, but I can’t recall how that claim was sourced.

jerf 5y ago

"but maybe the underlying point was that it isn't possible to statically know how much stack size would be required." Given the time frame you're talking about, remember to be thinking in terms of kilobytes, not gigabytes. And potentially low-single-digit numbers of kilobytes. It could be in the range of hundreds of bytes dedicated to stacks at the time. Even if you could compute your maximum size it's easy to imagine people balking a the results of such a computation and think it's not worth it to even consider the possibility because you'd blow your stack so quickly it's not like there'd be any benefit to it.

a1369209993 5y ago

> it isn't possible to statically know how much stack size would be required. It's not just that - if it were merely that you couldn't know the size statically, you could use dynamic memory allocation. The problem with that though, is that now every (not provably nonrecursive) function call can now fail with a memory allocation error, and if your language doesn't surface that to the caller, and (correctly) doesn't allow spurious errors to appear out of nowhere (cough every modern programming language cough cough), there's no way to handle that error.