tail recursion optimization

[Jens Müller]

Hi,

I am currently reading Douglas Crockford's "JavaScript: The Good Parts".

On page 35, it says:

"Some languages offer the /tail recursion optimization/. This means that
if a function returns the result of invoking itself recursively, then
the invocation is replaced with a loop, which can significantly speed
things up. Unfortunately, JavaScript does not currently provide tail
recursion optimization. Functions that recurse very deeply can fail by
exhausting the return stack."

I'm not quite sure what the author's point is here. IMO, an optimization
is not a property of the language, but of a particular implementation.
IMO, the same holds for implementation of nested function calls using a
return stack.

Does the author mean that existing implementations do not offer this
optimization, or is there more about the argument, i.e., does JavaScript
has some properties that make tail recursion optimization difficult or
impossible?

- Jens

 

[Thomas 'PointedEars' Lahn]

I am currently reading Douglas Crockford's "JavaScript: The Good Parts".

On page 35, it says:

"Some languages offer the /tail recursion optimization/. This means that
if a function returns the result of invoking itself recursively, then
the invocation is replaced with a loop, which can significantly speed
things up. Unfortunately, JavaScript does not currently provide tail
recursion optimization. Functions that recurse very deeply can fail by
exhausting the return stack."

I'm not quite sure what the author's point is here. IMO, an optimization
is not a property of the language, but of a particular implementation.
IMO, the same holds for implementation of nested function calls using a
return stack.

You are correct.

Does the author mean that existing implementations do not offer this
optimization,

Probably. It is imposslbe to be sure without seeing the statement in
context.

or is there more about the argument, i.e., does JavaScript has some
properties that make tail recursion optimization difficult or impossible?

If that would be the argument, it would be wrong.

Indeed, it is a property of the programming language as formally specified
in the language standard that functions are represented as objects (Function
instances), and function names or, more generally, property names, are
references to those objects (a function can refer to itself without using
its name by `arguments.callee'). As such, they have identity, no matter how
the concept "reference to a function" is implemented. So tail recursion
optimization is entirely possible. IIRC, a method to do this has been
proposed here before.

Without having seen this statement in context, I have to assume that,
oversimplifying the issue, the author is regarding JavaScript to be a
programming language that is universally implemented (a standard), when it
is in fact one implementation of a programming language standard, one of
many different and differing ones, especially one of several such
implementations to be found in browsers. As a result, he is falsely
attributing properties of a subset of known implementations – or one
implementation – to the formal language standard they are based upon.
This is a common misconception.

<http://PointedEars.de/es-matrix>


Pointedars

 

[Jukka K. Korpela]

I am currently reading Douglas Crockford's "JavaScript: The Good Parts".

On page 35, it says:

"Some languages offer the /tail recursion optimization/.

This is one of the bad parts of "The Good Parts". This part is not
really incorrect, just a little sloppily formulated - but more
importantly, it deals with a topic that shouldn't be discussed at all
when describing the good parts of JavaScript.

The possibility of recursion as such belongs to good parts, of course,
but mainly due to its usefulness in tree traversal. The author is
probably trying to say that in JavaScript, recursion should not be used
when simple iteration can easily be used. But it's not a good idea to
make an excursion to tail recursion optimization to "prove" that.

[...] JavaScript does not currently provide tail
recursion optimization. Functions that recurse very deeply can fail by
exhausting the return stack."

I'm not quite sure what the author's point is here. IMO, an optimization
is not a property of the language, but of a particular implementation.

People often speak freely about a programming language, without making a
sharp distinction between a language and its implementations, the
standard (if any) of the language and its varying "dialects", and so on.
And this usually causes no problems, except if you are disturbed too
much by trolls who make big noises whenever someone writes "JavaScript".

Optimization is of course an implementation issue. But when no existing
implementation has a certain kind of optimization, then one can say in
practice that the language lacks it - from the programmer's perspective.

IMO, the same holds for implementation of nested function calls using a
return stack.

That's slightly different. A stack, as a suitably abstract concept, is
_necessary_ for the implementation of a programming language that has
functions with local variables.

Does the author mean that existing implementations do not offer this
optimization, or is there more about the argument, i.e., does JavaScript
has some properties that make tail recursion optimization difficult or
impossible?

My bet is that the author was thinking of functional programming
languages, in which tail recursion optimization is _essential_ to
language implementation. Regarding JavaScript, the lack of it in
implementations is more an issue of needs. The intended and actual use
of the language has fairly little to do with the potential benefits of
tail recursion optimization.

The factorial function, presented as an example in this context in the
book, is a bad example. It is easy to see how it can be implemented
using iteration, not just more efficiently but also simpler, in a manner
that lets one see immediately what's going on. The author's example
contains a pointless extra argument (a multiplier). The given example of
factorial(4) is hardly one that "can fail by exhausting the return
stack". And actually, factorial(170) (which causes no problems in any
remotely modern computer) is the largest useful value - after that, all
factorials are equal in the Infinity of JavaScript.

"JavaScript: The Good Parts" is still a very good book. Just take the
good parts. The main problem with the other parts is that it takes time
to see which parts are just difficult to understand (and need to be read
a few times) and which parts are just not good.

 

[Lasse Reichstein Nielsen]

I am currently reading Douglas Crockford's "JavaScript: The Good Parts".

On page 35, it says:
[Tail call optimization]

I'm not quite sure what the author's point is here. IMO, an
optimization is not a property of the language, but of a particular
implementation. IMO, the same holds for implementation of nested
function calls using a return stack.

Actually, for the tail call optimiztion to be really useful, the
programmer must be able to rely on it being there. Writing deeply
recursive programs will fail if you don't have tail tall optimization,
and fly if you do.
That's why it's a feature that pretty much needs to be defined as part
of the language (like in, e.g., Scheme).

Does the author mean that existing implementations do not offer this
optimization, or is there more about the argument, i.e., does
JavaScript has some properties that make tail recursion optimization
difficult or impossible?

It does have some iherited crud that makes it impossible (e.g.,
myfunction.arguments), but if you cut that away, as they have in
strict mode, it should be possible.
On the other hand, nobody will ever write a loop as a tail recursive
function if they don't know that every implementation will have it.

/L

 

[Alexander Veit]

Am 27.06.2011, 03:45 Uhr, schrieb Thomas 'PointedEars' Lahn

I am currently reading Douglas Crockford's "JavaScript: The Good Parts".
[...]
I'm not quite sure what the author's point is here. IMO, an optimization
is not a property of the language, but of a particular implementation..
IMO, the same holds for implementation of nested function calls usinga
return stack.

You are correct.

As Lasse already pointed out, tail call recursion is not only a technique
for compiler optimization but is also present as a feature of programming
languages, especially in Scheme, one of the ancestors of JavaScript.

[...]

or is there more about the argument, i.e., does JavaScript has some
properties that make tail recursion optimization difficult or
impossible?

If that would be the argument, it would be wrong.

Indeed, it is a property of the programming language as formally
specified in the language standard that functions are represented
as objects (Function instances), and function names or, more
generally, property names, are references to those objects (a
function can refer to itself without using its name by
`arguments.callee'). As such, they have identity, no matter how the
concept "reference to a function" is implemented. So tail
recursion optimization is entirely possible.

Unfortunately not. Language features like <function>.arguments, or
arguments.callee induce problems that prohibit tail call optimization.
Therefore the notion of "proper tail calls" has been introduced for
discussing possible future versions of the ECMAScript standard.

See
http://wiki.ecmascript.org/doku.php?id=harmony:proper_tail_calls
and
http://code.google.com/p/v8/issues/detail?id=457

Without having seen this statement in context, I have to assume that,
oversimplifying the issue, the author is regarding JavaScript to be a
programming language that is universally implemented (a standard), when
it is in fact one implementation of a programming language standard,
one of many different and differing ones, especially one of several such
implementations to be found in browsers. As a result, he is falsely
attributing properties of a subset of known implementations – or one
implementation – to the formal language standard they are based upon.
This is a common misconception.

No. As it is common usage, he uses JavaScript as a synomym for ECMAScript
or its implementations.

 

[Thomas 'PointedEars' Lahn]

I am currently reading Douglas Crockford's "JavaScript: The Good Parts".
[...]
I'm not quite sure what the author's point is here. IMO, an optimization
is not a property of the language, but of a particular implementation.
IMO, the same holds for implementation of nested function calls using a
return stack.

You are correct.

As Lasse already pointed out, tail call recursion is not only a technique
for compiler optimization but is also present as a feature of programming
languages, especially in Scheme, one of the ancestors of JavaScript.
ACK

Without having seen this statement in context, I have to assume that,
oversimplifying the issue, the author is regarding JavaScript to be a
programming language that is universally implemented (a standard), when
it is in fact one implementation of a programming language standard,
one of many different and differing ones, especially one of several such
implementations to be found in browsers. As a result, he is falsely
attributing properties of a subset of known implementations – or one
implementation – to the formal language standard they are based upon.
This is a common misconception.

No. As it is common usage,

As in this case, common usage is often, if not most of the time, wrong.
Just consider the usage of "Internet" or "hacker" in mass media.

he uses JavaScript as a synomym for ECMAScript or its implementations.

He can make such a statement about ECMAScript, but not about its
implementations (all of them).


PointedEars

 

[John G Harris]

No. As it is common usage, he uses JavaScript as a synomym for
ECMAScript or its implementations.

Towards the end of chapter 1 of "JavaScript : the good parts" he writes

... "JavaScript (aka JScript)" ...

and

"The language described in this book is a proper subset of
ECMAScript."


Confused? Who? Crockford? Perish the thought!

John

 

[Thomas 'PointedEars' Lahn]

Alexander Veit wrote:


Towards the end of chapter 1 of "JavaScript : the good parts" he writes

... "JavaScript (aka JScript)" ...

and

"The language described in this book is a proper subset of
ECMAScript."


Confused? Who? Crockford? Perish the thought!

Is this sarcasm?


PointedEars

 

[glathoud]

Yes, at least within ECMAScript 5 strict mode, an interpreter *could*
implement tail call optimization (TCO) [1]. However, the ECMAScript 5
standard does not force any interpreter to implement TCO.

Right now, one solution to obtain TCO in a safe and performant manner
is to manually mark the parts of your code you need to be optimized,
and let the code be automatically transformed by another program [2].
Also server-side code "compilation".

IMHO this remains a bit constraining. Hopefully someday there will be
implementations doing TCO.

Best regards,
Guillaume

[1] http://wiki.ecmascript.org/doku.php?id=harmony:proper_tail_calls
[2] http://www.glat.info/jscheck/tomrec_prod.html

 

[glathoud]

Yes, at least within the ECMAScript 5 strict mode, an interpreter
*could* implement Tail Call Optimization (TCO) [1]. But the ECMAScript
5 standard does not force any interpreter to implement TCO.

Right now, one solution to have TCO in a safe and performant manner is
to mark the tail-recursive parts of the code you want to optimized,
and have another program automatically optimize your code [2]. Also
server-side code "compilation".

IMHO this remains a bit constraining and hopefully interpreters will
implement TCO someday.

Best regards,
Guillaume

[1] http://wiki.ecmascript.org/doku.php?id=harmony:proper_tail_calls
[2] http://www.glat.info/jscheck/tomrec_prod.html