8 ms·

Isn't this just rewriting tail calls (http://en.wikipedia.org/wiki/Tail_call http://en.wikipedia.org/wiki/Tail_call)? Am I missing something?

barrkel 12y ago
The "spaghetti code" approach isn't far off, no. But there is an idea which is distinct; it's reducing data usage at the cost of running more code. Not all recursive functions can be made tail recursive (at least, not without other tricks). But the approach first described in the article can be applied to any recursive function. It will still need a stack of return addresses, but no stack for parameters or locals.
- LukeShu 12y ago
  > It will still need a stack of return addresses Keep reading, further down he even gets rid of the stack of return addresses.
  - barrkel 12y ago
    No; the stack of return addresses is required when the variable mutations don't have a consistent inverse.
segmondy 12y ago
This was 1995, Outside of Prolog, LISP, Scheme, and other exotic languages, what popular languages of that era offered TC? (C, Pascal, C++, BASIC, FORTRAN, etc) didn't.
- icarot 12y ago
  Yeah. Most languages don't. Python and Javascript compilers still don't and Emacs LISP still doesn't.
- dragonwriter 12y ago
  Tail call optimization, strictly speaking, isn't a language feature (though a language standard can require it in conforming implementations, as Scheme standards have. Which brings me to: > (C, Pascal, C++, BASIC, FORTRAN, etc) didn't. I'm not sure that's true. gcc, in optimizing modes, could do at least tail recursion elimination at least as far back as 1999, and does more now. (The earliest reference I can find refers to gcc 2.95.3, but its not clear to me if that's the first version that did it, or just the earliest version on which the writer tested and confirmed the behavior.) Outside of a handful of languages, tail call elimination in either restrictive (e.g., tail recursion only) or general forms is an optional optimization rather than an essential behavior.

barrkel 12y ago

The "spaghetti code" approach isn't far off, no. But there is an idea which is distinct; it's reducing data usage at the cost of running more code. Not all recursive functions can be made tail recursive (at least, not without other tricks). But the approach first described in the article can be applied to any recursive function. It will still need a stack of return addresses, but no stack for parameters or locals.

LukeShu 12y ago
> It will still need a stack of return addresses Keep reading, further down he even gets rid of the stack of return addresses.
- barrkel 12y ago
  No; the stack of return addresses is required when the variable mutations don't have a consistent inverse.

segmondy 12y ago

This was 1995, Outside of Prolog, LISP, Scheme, and other exotic languages, what popular languages of that era offered TC? (C, Pascal, C++, BASIC, FORTRAN, etc) didn't.

icarot 12y ago
Yeah. Most languages don't. Python and Javascript compilers still don't and Emacs LISP still doesn't.
dragonwriter 12y ago
Tail call optimization, strictly speaking, isn't a language feature (though a language standard can require it in conforming implementations, as Scheme standards have. Which brings me to: > (C, Pascal, C++, BASIC, FORTRAN, etc) didn't. I'm not sure that's true. gcc, in optimizing modes, could do at least tail recursion elimination at least as far back as 1999, and does more now. (The earliest reference I can find refers to gcc 2.95.3, but its not clear to me if that's the first version that did it, or just the earliest version on which the writer tested and confirmed the behavior.) Outside of a handful of languages, tail call elimination in either restrictive (e.g., tail recursion only) or general forms is an optional optimization rather than an essential behavior.