Hacker News Reader

Comment by rogerbraun | Hacker News Reader

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

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.

    > It will still need a stack of return addresses

Keep reading, further down he even gets rid of the stack of return addresses.

No; the stack of return addresses is required when the variable mutations don't have a consistent inverse.

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.

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.

Yeah. Most languages don't. Python and Javascript compilers still don't and Emacs LISP still doesn't.

Reply on news.ycombinator.com