5 ms·

> 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 w

> 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.
      - mtdewcmu 12y ago
        I thought languages were Turing-complete, not machines. Languages don't have the problem, because they don't have to have their own memory.
        Chinjut 12y ago
        If a language only allows you to specify programs with bounded memory usage, then it will fail to be Turing-complete.
    - Chinjut 12y ago
      A finite memory machine is a finite state machine. These are not Turing complete. The notion of Turing completeness becomes uninteresting if we can't even draw this distinction. "dynamic memory allocation" may not have been the right term to use to denote moving beyond finite state machines, for an audience which wants to consider a Turing machine as having statically allocated infinite memory. But it makes sense if you think of a Turing machine's memory as only storing enough data for the portion of the tape which has already been accessed, and allocating new memory as new tape regions are needed. It's true that the actual machine sitting on your desk only has a fixed finite memory. In that sense, without a peripheral unbounded store, it's not properly Turing complete. It's also true that we often find it convenient to analyze it as Turing complete anyway, but this abstraction basically goes hand-in-hand with abstracting away its memory limitations. I don't see any point in pretending you can be Turing complete using only programs with a statically given memory bound (which amounts to a logarithmic bound on the number of states in a corresponding finite state machine); if we're going to pretend, let's pretend the memory is effectively infinite as well.
  - bodyfour 12y ago
    > So, if you wanted to only allow recursion via tail-calls, you easily could To be fair, we're talking about a language designed in 1959, where a compiler had to run in 4KB of memory or so. At that point you're barely optimizing anything, just doing the simplest transformation you can. Doing tail-call elimination isn't quite as simple as just doing a "JMP" instead of a "CALL" since you also need to replace the currently in-use activation record. Consider the C fragment: int f(int a, int b) { if (a > b) return f(b, a); // ... } Now imagine you're trying to compile this for an ancient register-less machine. We have to replace "a,b" in the activation record with "b,a" but if we just naively copy the values one by one we'll step on "a" before we read it and end up with "b,b". These problems certainly aren't insurmountable, but if it takes a few hundred instructions you've already blown a lot of your budget on one little feature. You could see why a language designer in 1959 would want to leave it out.
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.)

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.
    - mtdewcmu 12y ago
      I thought languages were Turing-complete, not machines. Languages don't have the problem, because they don't have to have their own memory.
      - Chinjut 12y ago
        If a language only allows you to specify programs with bounded memory usage, then it will fail to be Turing-complete.
  - Chinjut 12y ago
    A finite memory machine is a finite state machine. These are not Turing complete. The notion of Turing completeness becomes uninteresting if we can't even draw this distinction. "dynamic memory allocation" may not have been the right term to use to denote moving beyond finite state machines, for an audience which wants to consider a Turing machine as having statically allocated infinite memory. But it makes sense if you think of a Turing machine's memory as only storing enough data for the portion of the tape which has already been accessed, and allocating new memory as new tape regions are needed. It's true that the actual machine sitting on your desk only has a fixed finite memory. In that sense, without a peripheral unbounded store, it's not properly Turing complete. It's also true that we often find it convenient to analyze it as Turing complete anyway, but this abstraction basically goes hand-in-hand with abstracting away its memory limitations. I don't see any point in pretending you can be Turing complete using only programs with a statically given memory bound (which amounts to a logarithmic bound on the number of states in a corresponding finite state machine); if we're going to pretend, let's pretend the memory is effectively infinite as well.
- bodyfour 12y ago
  > So, if you wanted to only allow recursion via tail-calls, you easily could To be fair, we're talking about a language designed in 1959, where a compiler had to run in 4KB of memory or so. At that point you're barely optimizing anything, just doing the simplest transformation you can. Doing tail-call elimination isn't quite as simple as just doing a "JMP" instead of a "CALL" since you also need to replace the currently in-use activation record. Consider the C fragment: int f(int a, int b) { if (a > b) return f(b, a); // ... } Now imagine you're trying to compile this for an ancient register-less machine. We have to replace "a,b" in the activation record with "b,a" but if we just naively copy the values one by one we'll step on "a" before we read it and end up with "b,b". These problems certainly aren't insurmountable, but if it takes a few hundred instructions you've already blown a lot of your budget on one little feature. You could see why a language designer in 1959 would want to leave it out.

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.)