Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Javascript > Tail call optimization in Javascript without trampoline

Reply
Thread Tools

Tail call optimization in Javascript without trampoline

 
 
glathoud
Guest
Posts: n/a
 
      02-02-2010
Hello, here is a code that transforms a tail call-recursive function
(growing stack depth) into a "flat" one (constant stack depth). This
brings also speed improvements on all JS engines I tested with
(Firefox, Safari, Chrome, IE). In case of interest:

http://glathoud.easypagez.com/public...ilopt-js.xhtml

Regards,

Guillaume
 
Reply With Quote
 
 
 
 
Thomas 'PointedEars' Lahn
Guest
Posts: n/a
 
      02-02-2010
glathoud wrote:

> Hello, here is a code that transforms a tail call-recursive function
> (growing stack depth) into a "flat" one (constant stack depth). This
> brings also speed improvements on all JS engines I tested with
> (Firefox, Safari, Chrome, IE). In case of interest:
>
> http://glathoud.easypagez.com/public...ilopt-js.xhtml


1. Interesting idea.

2. There is no "Javascript". You are dealing with several ECMAScript
implementations here (among them JavaScript, JScript, Opera ECMAScript,
JavaScriptCore, and KJS), and you have yet to prove (you cannot) that
none of them (including, but not limited to, those mentioned) does not
make tail call optimization, before making such a statement.

As a result of that common misconception, you have falsely attributed
implementation-specific behavior to bugs in the runtime environments
(browsers) of the implementations that do not exhibit it, to bugs that
would need to be worked around, such as in (properly wrapped; your
source code SHOULD NOT exceed 80 characters per line)

eval( 'ret = (' + new_head + '{' + new_body + '})' );
// Ugly 'ret = (' because of IE

However, it is not "IE" that is the "culprit" here; instead, Microsoft
JScript implements the ECMAScript Language Specification rather
strictly, and

function (n) {...}

(as created by debugging the "Concise" example) is _not_ a syntactically
valid ECMAScript /Program/ as required by eval() so

eval("function (n) {...}");

MUST throw a SyntaxError exception (ES5, 15.1.2.1) *unless* an
implementation (those which you observed to be "working" without
the change) extends program syntax so that this is allowed, in
which case implementation-specific behavior is permitted instead
(section 16).

By placing the parentheses around the program code, and using
it in an assignment --

x = (function (n) {...})

--, it becomes producible by the /AssignmentExpression/ production;
therefore, a syntactically valid ECMAScript /Program/:

Program ::
SourceElement

SourceElement ::
Statement

Statement ::
ExpressionStatement

ExpressionStatement ::
[lookahead ∉ {{, function}] Expression

Expression ::
AssignmentExpression

AssignmentExpression ::
LeftHandSideExpression AssignmentOperator AssignmentExpression

LeftHandSideExpression ::
NewExpression

NewExpression ::
MemberExpression

MemberExpression ::
PrimaryExpression

PrimaryExpression ::
Identifier

AssignmentOperator ::
=

AssignmentExpression ::
ConditionalExpression

...

PrimaryExpression ::
( Expression )

Expression ::
MemberExpression

MemberExpression ::
FunctionExpression

3. `window' refers to a host object; do not try to augment it with
properties. Use a reference to the ECMAScript Global Object instead
or simply let the scope chain do its work. So instead of

(function () {
// ...
window.tailopt = function (...) {
// ...
};
// ...
)();

use either

var _global = this;

(function () {
// ...
_global.tailopt = function (...) {
// ...
};
// ...
)();

or simply

var tailopt;

(function () {
// ...
tailopt = function (...) {
// ...
};
// ...
)();

4. In the same vein, do not assume `window.console' and `console'
would be identical. And do not assume that because a property has
a true-value it must be callable; test for the type, catch
exceptions on call where necessary. For example, instead of
(wrapped)

var log = function () {
window.console && console.log && console.log.apply
&& console.log.apply( console, arguments );
},

use

/*
* See also the newsgroup's archives at e.g. Google Groups
* and use your favorite search engine to find more
* sophisticated implementations by contributors.
*/
function _isNativeMethod(o, p)
{
if (!o) return false;
return /\bfunction\b/i.test(typeof o[p]);
}

function _isHostMethod(o, p)
{
if (!o) return false;
var t = typeof o[p];
return (/\bunknown\b/i.test(t)
|| (/\b(function|object)\b/i.test(t) && o[p]));
}

function log()
{
/* but see also jsx.tryThis() for a compatibility wrapper */
try
{
typeof _global.console != "undefined"
&& _isHostMethod(console, "log")
&& _isNativeMethod(console.log, "apply")
&& console.log.apply(console, arguments);
}
catch (e)
{
throw new Error("Error console unavailable");
}
}

5. As you can also see here, you should not use function expressions where
function declarations suffice. And it might be better to prefix
identifiers that are only available in the local execution context,
or are user-defined, to distinguish them from others.

6. I don't see why a `while (true)' loop should be necessary anymore
to remove all comments with remove_comments() if you simply added
the global modifier to the RegExp initializer of the replace() call.

7. Code becomes easier to read and more obvious if you declare variables
where you initialize them, unless the execution contexts differ. If
you write

var rx = /^\s*(function\s*\(.*?\))\s*\{([\w\W]*?)\}\s*$/;

instead of

var ..., rx, ...;

/* [17 lines in-between] */

rx = /^\s*(function\s*\(.*?\))\s*\{([\w\W]*?)\}\s*$/;

it becomes obvious that you are initializing a local variable here.

8. In fact, I do not find that your overall code style improves
readability, rather the reverse:

if ( ! ( new RegExp( '^\\s*\\(\\s*' + fname + '\\s*=\\s*' ) ).test(
cond[ 1 ] ) ) {
// ...
}

as compared to (what I would prefer)

if (!(new RegExp('^\\s*\\(\\s*' + fname + '\\s*=\\s*')).test(cond[1]))
{
// ...
}

or

var rx = new RegExp('^\\s*\\(\\s*' + fname + '\\s*=\\s*');
if (!rx.test(cond[1]))
{
// ...
}


HTH

PointedEars
--
realism: HTML 4.01 Strict
evangelism: XHTML 1.0 Strict
madness: XHTML 1.1 as application/xhtml+xml
-- Bjoern Hoehrann
 
Reply With Quote
 
 
 
 
glathoud
Guest
Posts: n/a
 
      02-03-2010
Hello, first of all thanks for the detail feedback - you read the code
in detail, and I appreciate that. I'll definitely try to improve the
coding style.

While reading your answers, two points came to my mind:
- as far as I know, the various ECMAScript *standards* do not force
to implement tail call optimization (TCO), whereas standards from
other languages do (e.g. Scheme).
- my results show clearly that the most common browser *engines* do
not implement TCO.

Best regards,

Guillaume
 
Reply With Quote
 
glathoud
Guest
Posts: n/a
 
      02-03-2010
By the way, at this point, a Javascript parser in Javascript would
really help improve the code. I have found the Pratt parser used by
Douglas Crockford in JSLint. Should I use this for code parsing/
transformation/generation ? Is there any other parser I can compare
with ?

Cheers,

Guillaume
 
Reply With Quote
 
Thomas 'PointedEars' Lahn
Guest
Posts: n/a
 
      02-03-2010
kangax wrote:

> However, the biggest problem I see here is the fact that implementation
> relies on so-called "function decompilation" — a process of getting
> string representation of a Function object.
>
> Function decompilation is generally recommended against, as it is a
> non-standard part of the language, and as a result, leads to code being
> non-interoperable and potentially error-prone.


Nonsense.

> Both, 3rd and 5th editions of ECMAScript specify
> `Function.prototype.toString` (which is what `toString` of all native
> function objects usually resolves too) to return
> *implementation-dependent* representation of a function (e.g. see
> 15.3.4.2 in ES3 specs).


Per Specification, implementation-dependent is only the content of the
representation of the function body (e.g., include or omit whitespace,
include or omit comments), not the syntactical correctness of the
representation.

> And in fact, in practice, you can easily observe the diversity of
> function representations among some of the implementations:
>
> <http://perfectionkills.com/those-tricky-functions/>
> <http://magnetiq.com/2009/02/06/tostring-on-function-with-comments/>


Apples and oranges. You clearly fail to see the difference between built-
in functions, host methods, and user-defined functions there and here.

The representation of user-defined functions -- which are the only ones
that are exposed to this algorithm -- is syntactically correct in all known
implementations, so there is nothing that supports your idea of a general
recommendation against "function decompilation".


PointedEars
--
Anyone who slaps a 'this page is best viewed with Browser X' label on
a Web page appears to be yearning for the bad old days, before the Web,
when you had very little chance of reading a document written on another
computer, another word processor, or another network. -- Tim Berners-Lee
 
Reply With Quote
 
Thomas 'PointedEars' Lahn
Guest
Posts: n/a
 
      02-03-2010
kangax wrote:

> Thomas 'PointedEars' Lahn wrote:
>> kangax wrote:
>>> However, the biggest problem I see here is the fact that implementation
>>> relies on so-called "function decompilation" — a process of getting
>>> string representation of a Function object.
>>>
>>> Function decompilation is generally recommended against, as it is a
>>> non-standard part of the language, and as a result, leads to code being
>>> non-interoperable and potentially error-prone.

>>
>> Nonsense.
>>
>>> Both, 3rd and 5th editions of ECMAScript specify
>>> `Function.prototype.toString` (which is what `toString` of all native
>>> function objects usually resolves too) to return
>>> *implementation-dependent* representation of a function (e.g. see
>>> 15.3.4.2 in ES3 specs).

>>
>> Per Specification, implementation-dependent is only the content of the
>> representation of the function body (e.g., include or omit whitespace,
>> include or omit comments), not the syntactical correctness of the
>> representation.

>
> Where are you getting this from?


The Specification prose.

> Read 15.3.4.2 again.


Read it yourself.

| 15.3.4.2 Function.prototype.toString ( )
|
| An implementation-dependent representation of the function is returned.
| This representation has the syntax of a FunctionDeclaration. [...]

(The wording is the same in ES3F and ES5.)

>>> And in fact, in practice, you can easily observe the diversity of
>>> function representations among some of the implementations:
>>>
>>> <http://perfectionkills.com/those-tricky-functions/>
>>> <http://magnetiq.com/2009/02/06/tostring-on-function-with-comments/>

>>
>> Apples and oranges. You clearly fail to see the difference between
>> built- in functions, host methods, and user-defined functions there and
>> here.

>
> What are you talking about? No one tried to generalize anything.


You tried to make a point about a recommendation against "function
decompilation" in general and especially here on the grounds that this
would "not be interoperable" and "potentially error-prone" while referring
to considerable differences in string representations of methods that are
_not_ user-defined, so completely irrelevant here.

>> The representation of user-defined functions -- which are the only ones
>> that are exposed to this algorithm -- is syntactically correct in all
>> known implementations, so there is nothing that supports your idea of a
>> general recommendation against "function decompilation".

>
> In all known implementations, huh? Well, that's funny


How so? It merely emphasizes that any other unknown implementation would
have a bug waiting to be fixed there.


PointedEars
--
Anyone who slaps a 'this page is best viewed with Browser X' label on
a Web page appears to be yearning for the bad old days, before the Web,
when you had very little chance of reading a document written on another
computer, another word processor, or another network. -- Tim Berners-Lee
 
Reply With Quote
 
glathoud
Guest
Posts: n/a
 
      02-03-2010
Hello, thanks for the interesting discussion. I have two reactions on
this:

--- (1) The standards

I just looked at both:

3rd: "ECMAScript Language Specification, Edition 3 Final, 24-Mar-00"
http://www.mozilla.org/js/language/E262-3.pdf

5th:
http://www.ecma-international.org/pu...T/ECMA-262.pdf

Both have the same words:

> 15.3.4.2 Function.prototype.toString ( )
>
> An implementation-dependent representation of the function is returned. This representation has the syntax of a
> FunctionDeclaration. Note in particular that the use and placement of white space, line terminators, and semicolons
> within the representation string is implementation-dependent.


I read again:

> This representation has the syntax of a FunctionDeclaration.


Yes, this guarantees syntaxic correctness only, but not content.
ECMAScript engines are totally free to implement this in a useless
manner, e.g. always returning a constant string like "function f()
{}".

However in practice:

--- (2) The various ECMAScript engines

- Desktop: kangax's information is *outdated*. There are obviously
small syntaxic differences across browsers, but the full definition of
the function is *there*. I am talking about Firefox 3.6, Safari 4.0.4,
Google Chrome 3.0 and IE8. Today.

- Mobile: kangax may well have a good point. Which leads me to:

--- A practical question:

Do the standards drive the implementations, or do the implementations
drive the standards?

---
Finally, thanks again to Thomas Mahn for his previous comments on
syntax. I just updated the tailopt site - not only the implementation,
but also the *usage* has been quite simplified.

http://glathoud.easypagez.com/public...ilopt-js.xhtml
 
Reply With Quote
 
glathoud
Guest
Posts: n/a
 
      02-03-2010
Hello, thanks for the interesting discussion. I have two reactions on
this:

--- (1) The standards

I just looked at both:

3rd: "ECMAScript Language Specification, Edition 3 Final, 24-Mar-00"
http://www.mozilla.org/js/language/E262-3.pdf

5th:
http://www.ecma-international.org/pu...T/ECMA-262.pdf

Both have the same words:

> 15.3.4.2 Function.prototype.toString ( )
>
> An implementation-dependent representation of the function is returned. This representation has the syntax of a
> FunctionDeclaration. Note in particular that the use and placement of white space, line terminators, and semicolons
> within the representation string is implementation-dependent.


I read again:

> This representation has the syntax of a FunctionDeclaration.


Yes, this guarantees syntaxic correctness only, but not content.
ECMAScript engines are totally free to implement this in a useless
manner, e.g. always returning a constant string like "function f()
{}".

However in practice:

--- (2) The various ECMAScript engines

- Desktop: kangax's information is *outdated*. There are obviously
small syntaxic differences across browsers, but the full definition of
the function is *there*. I am talking about Firefox 3.6, Safari 4.0.4,
Google Chrome 3.0 and IE8. Today.

- Mobile: kangax may well have a good point. Which leads me to:

--- A practical question:

Do the standards drive the implementations, or do the implementations
drive the standards?

---
Finally, thanks again to Thomas Mahn for his previous comments on
syntax. I just updated the tailopt site - not only the implementation,
but also the *usage* has been quite simplified.

http://glathoud.easypagez.com/public...ilopt-js.xhtml
 
Reply With Quote
 
Garrett Smith
Guest
Posts: n/a
 
      02-03-2010
kangax wrote:
> On 2/3/10 2:46 PM, Thomas 'PointedEars' Lahn wrote:
>> kangax wrote:
>>
>>> Thomas 'PointedEars' Lahn wrote:
>>>> kangax wrote:

> [...]
>>>>> And in fact, in practice, you can easily observe the diversity of
>>>>> function representations among some of the implementations:
>>>>>
>>>>> <http://perfectionkills.com/those-tricky-functions/>
>>>>> <http://magnetiq.com/2009/02/06/tostring-on-function-with-comments/>
>>>>
>>>> Apples and oranges. You clearly fail to see the difference between
>>>> built- in functions, host methods, and user-defined functions there and
>>>> here.
>>>
>>> What are you talking about? No one tried to generalize anything.

>>
>> You tried to make a point about a recommendation against "function
>> decompilation" in general and especially here on the grounds that this
>> would "not be interoperable" and "potentially error-prone" while
>> referring
>> to considerable differences in string representations of methods that are
>> _not_ user-defined, so completely irrelevant here.

>
> Please, read carefully my blog post again
> (<http://perfectionkills.com/those-tricky-functions/>), and realize that
> examples include user-defined functions as well. Specifically, look at
> Blackberry (mobile browser) and Safari <2 (desktop browser) examples.
>
> Also, please understand that two conforming implementations are allowed
> (by specification) to return two different function representations
> (which could even conform to FunctionDeclaration syntax), yet result in
> different outcome.
>
> This is the interoperability issue I'm talking about. It's not just a
> theoretical concern, but something that can be observed in practice.
>
> And speaking of `Function.prototype.toString` in general, current
> implementations are far from being conforming (specifically, built-in
> functions "produce" strings that don't satisfy /FunctionDeclaration/
> syntax (e.g. ubiquitous "function(){ [native code] }" and its variations
> )).
>


Actually, the specification requires `Function.prototype.toString` to
return a representation of a FunctionDeclaration. See how many get that
right:

javascript: alert(Function.prototype.toString() )

Opera 10:
function () { [native code] }

FF 3.5
function () {
}

IE7
function prototype() {
[native code]
}

Safari 4
function () {
[native code]
}
Chrome 4:
function Empty(){}

Chrome 4 is the only browser that conforms there, but then it fails with
the case of a user defined function (as you mentioned):-

(function(){}).toString();

- returning "function(){}"

That result is invalid because it is not a FunctionDeclaration.

Actually, I think what Chrome does there makes sense; a function object
with no Identifier would need to have something looking like an
Identifier in the string representation to be valid. I believe this
should be changed and have proposed that change here:

https://mail.mozilla.org/pipermail/e...er/009816.html
--
Garrett
comp.lang.javascript FAQ: http://jibbering.com/faq/
 
Reply With Quote
 
Thomas 'PointedEars' Lahn
Guest
Posts: n/a
 
      02-04-2010
Garrett Smith wrote:

> Actually, the specification requires `Function.prototype.toString` to
> return a representation of a FunctionDeclaration.


Yes, when called on a Function instance.

> See how many get that right:
>
> javascript: alert(Function.prototype.toString() )


Your test case is flawed. And despite considerable hints you still manage
to miss the point. This is about the representation of *user-defined*
functions, not built-in ones.

> [snip bogus results]


Present a correct test case first, then we might talk.

> [...]
> That result is invalid because it is not a FunctionDeclaration.


Your test case is flawed, so whatever invented data you present as its
results here are irrelevant.


PointedEars
--
Use any version of Microsoft Frontpage to create your site.
(This won't prevent people from viewing your source, but no one
will want to steal it.)
-- from <http://www.vortex-webdesign.com/help/hidesource.htm> (404-comp.)
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Tail Call Optimization (Tail Recursion) Terry Michaels Ruby 16 04-20-2011 11:37 AM
tail call optimization problem Balazs Endresz Javascript 9 05-02-2010 12:36 PM
1.9 tail-call optimization status? Thomas Hurst Ruby 0 08-23-2008 04:35 AM
Tail Call Optimization as a Decorator Crutcher Python 4 03-03-2006 07:02 PM
Tail call ``optimization'' Sam Stephenson Ruby 1 09-25-2004 09:46 AM



Advertisments