4 ms·

The article doesn't mention why people didn't want recursion to be a requirement. It was probably because the idea of using a call stack was still controversia

The article doesn't mention why people didn't want recursion to be a requirement. It was probably because the idea of using a call stack was still controversial. For instance, on a PDP-8 (released some years after ALGOL) the calling convention was that the return address was written to the word of memory before the called function. This was simple, but pretty much precludes recursive calls. These days we take for granted that the CPU will provide some sort of stack pointer that gets automatically managed by a CALL/RET instruction pair. Before that was provided in hardware, the compiler would have to do that itself. So if you decided to support recursion, you'd end up requiring a stack and adding a small cost to every function call. Once you decide to have a stack, allowing recursion is a freebee so of course you'd include it.

Hemospectrum 12y ago
> The article doesn't mention why people didn't want recursion to be a requirement. It does, actually: > And this is what they wanted to remove because they wanted static allocation of procedure activation records. A stack frame is a dynamically allocated procedure activation record, but we no longer call them that because it's seen as absurd that they would be statically allocated.
- kibwen 12y ago
  I wouldn't say it's absurd, as it's legitimately very useful (though onerous) to be able to statically determine the amount of memory that will be used by a program. To this end, it is indeed true that tail-call elimination can remove the need for dynamically-allocated stack frames in the face of recursion. However, AFAIK, it is undecidable (given a Turing-complete language) to determine if a program contains only TCE-compatible recursion. In the face of that, you would have to forbid recursion entirely via a mechanism like the "declaration must precede use" rule mentioned in the article.
  - Chinjut 12y ago
    Whether a call is a tail-call is trivially decidable; it's an entirely syntactic condition (a call to f is a tail-call just in case it's of the form "return f(...);"). It's true that it's not possible to make a Turing-complete language for which it's possible to statically determine the amount of memory arbitrary programs on arbitrary inputs will use. But typically a language has other means of supporting dynamic memory allocation than simply via frame allocation for functions; e.g., via built-in operations to manipulate lists of arbitrary length. So, if you wanted to only allow recursion via tail-calls, you easily could, and if you wanted to furthermore go ahead and prevent all dynamic memory allocation, you could as well, but you would necessarily be giving up Turing-completeness.
    - pornel 12y ago
      I don't see the relationship between Turing-completness and dynamic memory allocation. Even in a classic Turing machine I interpret the tape as a single pre-allocated array (of infinite size). When talking about Turing-complete programming languages, a relaxed definition with finite-size memory is assumed, and to me it seems that it's just hair splitting whether program hits that limit via malloc() call or by advancing a pointer in an internal fixed-size array. Dynamic memory allocation is just a name for a bunch of bookkeeping done on a fixed-size memory. In practice asm.js programs are not allowed to dynamically allocate any memory from the browser: a fixed-size array is created before the asm.js program starts. From the point of the VM programs are just shuffling bytes within a fixed-size array, and yet, we can run "Turing-complete" programs in asm.js.
      - andrewflnr 12y ago
        I'm not sure how to untangle it, but I think you've got your abstraction layers mixed up. Anyway, that infinite tape is critical to Turing completeness. So strictly speaking, a limited-memory computer isn't strictly Turing complete, just close enough as makes no difference, because in practice they can use as much memory as they want, via dynamic memory allocation. When you tell the program it can't use as much memory as it wants, by taking away dynamic allocation, then you're not only not Turing complete, you're not even close to the Turing machine model.
- bodyfour 12y ago
  Oh sorry, you're right. I scanned the article too quickly and missed that line.
- asveikau 12y ago
  I don't think it's that absurd. For example, IIRC the allocation size for stacks inside the Linux kernel is usually 8192 bytes (on x86). Consequently, people avoid stuff like recursion in kernel mode. Today.
  - makomk 12y ago
    Yet activation records are still dynamically-allocated from those 8192 byte stacks - they have to be, because Linux runs on SMP machines and the same kernel function could be executing on multiple cores at once. (Also, for big pieces of kide lke the Linux kernel, it'd probably be more expensive not to dynamically allocate them.)
duaneb 12y ago
> These days we take for granted that the CPU will provide some sort of stack pointer that gets automatically managed by a CALL/RET instruction pair. Not really; most risc architectures still manage the stack via the compiler rather than instruction. About the closest you get is a jump-and-store-link-register instruction.

Hemospectrum 12y ago

> The article doesn't mention why people didn't want recursion to be a requirement. It does, actually: > And this is what they wanted to remove because they wanted static allocation of procedure activation records. A stack frame is a dynamically allocated procedure activation record, but we no longer call them that because it's seen as absurd that they would be statically allocated.

kibwen 12y ago
I wouldn't say it's absurd, as it's legitimately very useful (though onerous) to be able to statically determine the amount of memory that will be used by a program. To this end, it is indeed true that tail-call elimination can remove the need for dynamically-allocated stack frames in the face of recursion. However, AFAIK, it is undecidable (given a Turing-complete language) to determine if a program contains only TCE-compatible recursion. In the face of that, you would have to forbid recursion entirely via a mechanism like the "declaration must precede use" rule mentioned in the article.
- Chinjut 12y ago
  Whether a call is a tail-call is trivially decidable; it's an entirely syntactic condition (a call to f is a tail-call just in case it's of the form "return f(...);"). It's true that it's not possible to make a Turing-complete language for which it's possible to statically determine the amount of memory arbitrary programs on arbitrary inputs will use. But typically a language has other means of supporting dynamic memory allocation than simply via frame allocation for functions; e.g., via built-in operations to manipulate lists of arbitrary length. So, if you wanted to only allow recursion via tail-calls, you easily could, and if you wanted to furthermore go ahead and prevent all dynamic memory allocation, you could as well, but you would necessarily be giving up Turing-completeness.
  - pornel 12y ago
    I don't see the relationship between Turing-completness and dynamic memory allocation. Even in a classic Turing machine I interpret the tape as a single pre-allocated array (of infinite size). When talking about Turing-complete programming languages, a relaxed definition with finite-size memory is assumed, and to me it seems that it's just hair splitting whether program hits that limit via malloc() call or by advancing a pointer in an internal fixed-size array. Dynamic memory allocation is just a name for a bunch of bookkeeping done on a fixed-size memory. In practice asm.js programs are not allowed to dynamically allocate any memory from the browser: a fixed-size array is created before the asm.js program starts. From the point of the VM programs are just shuffling bytes within a fixed-size array, and yet, we can run "Turing-complete" programs in asm.js.
    - andrewflnr 12y ago
      I'm not sure how to untangle it, but I think you've got your abstraction layers mixed up. Anyway, that infinite tape is critical to Turing completeness. So strictly speaking, a limited-memory computer isn't strictly Turing complete, just close enough as makes no difference, because in practice they can use as much memory as they want, via dynamic memory allocation. When you tell the program it can't use as much memory as it wants, by taking away dynamic allocation, then you're not only not Turing complete, you're not even close to the Turing machine model.
bodyfour 12y ago
Oh sorry, you're right. I scanned the article too quickly and missed that line.
asveikau 12y ago
I don't think it's that absurd. For example, IIRC the allocation size for stacks inside the Linux kernel is usually 8192 bytes (on x86). Consequently, people avoid stuff like recursion in kernel mode. Today.
- makomk 12y ago
  Yet activation records are still dynamically-allocated from those 8192 byte stacks - they have to be, because Linux runs on SMP machines and the same kernel function could be executing on multiple cores at once. (Also, for big pieces of kide lke the Linux kernel, it'd probably be more expensive not to dynamically allocate them.)

duaneb 12y ago

> These days we take for granted that the CPU will provide some sort of stack pointer that gets automatically managed by a CALL/RET instruction pair. Not really; most risc architectures still manage the stack via the compiler rather than instruction. About the closest you get is a jump-and-store-link-register instruction.