Tail call optimization in Javascript without trampoline

Discussion in 'Javascript' started by glathoud, Feb 2, 2010.

  1. glathoud

    glathoud Guest

    glathoud, Feb 2, 2010
    #1
    1. Advertising

  2. 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/publications/tailopt-js/tailopt-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
     
    Thomas 'PointedEars' Lahn, Feb 2, 2010
    #2
    1. Advertising

  3. glathoud

    glathoud Guest

    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
     
    glathoud, Feb 3, 2010
    #3
  4. glathoud

    glathoud Guest

    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
     
    glathoud, Feb 3, 2010
    #4
  5. 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
     
    Thomas 'PointedEars' Lahn, Feb 3, 2010
    #5
  6. 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
     
    Thomas 'PointedEars' Lahn, Feb 3, 2010
    #6
  7. glathoud

    glathoud Guest

    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/publications/files/ECMA-ST/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/publications/tailopt-js/tailopt-js.xhtml
     
    glathoud, Feb 3, 2010
    #7
  8. glathoud

    glathoud Guest

    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/publications/files/ECMA-ST/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/publications/tailopt-js/tailopt-js.xhtml
     
    glathoud, Feb 3, 2010
    #8
  9. 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/es-discuss/2009-September/009816.html
    --
    Garrett
    comp.lang.javascript FAQ: http://jibbering.com/faq/
     
    Garrett Smith, Feb 3, 2010
    #9
  10. 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.)
     
    Thomas 'PointedEars' Lahn, Feb 4, 2010
    #10
  11. glathoud wrote:

    [Quotation fixed]
    > | 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()
    > {}".


    I would not interpret the Specification in that way. Indeed, mentioning
    white space, line terminators and semicolons in the next sentence would not
    make sense if the return value was completely arbitrary with regard to the
    function body. In addition, a string representation of a function that
    does not, as source code, provide the functionality of the function does
    not qualify as representation of that function. Apparently implementors
    agree here where it matters, with user-defined functions (it stands to
    reason that they would not or could not expose the source code of built-in
    functions/methods and host object's methods).

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


    If you limit your target runtime environments like this, then it becomes
    easier to do, but less compatible, of course.

    > - Mobile: kangax may well have a good point.


    Mobile/7D11 Safari 4.0 (Build 528.16 on iPhone OS 3.1.2) provides an exact,
    (executable) representation of the function body: it keeps the original
    source code and preserves newlines and comments, and does not insert
    semicolons.

    It does not stand to reason that other implementors would do something
    different on mobiles there. As for BlackBerry, its implementation has been
    shown to be borken in several other places, so hardly worth considering at
    this point.

    > Which leads me to:
    >
    > Do the standards drive the implementations, or do the implementations
    > drive the standards?


    The record suggests that the latter applies. See also the ECMAScript
    Support Matrix.

    > Finally, thanks again to Thomas Mahn for his previous comments on
    > syntax. [...]


    To whom? ;-) And you are welcome.

    But please use the `>' prefix only to mark quotations in the thread; use
    another character (customary is `|') for third-party quotations like from
    the Specification, to distinguish them. See above.


    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
     
    Thomas 'PointedEars' Lahn, Feb 4, 2010
    #11
  12. glathoud

    glathoud Guest

    @Garrett Smith and kangax: Native functions are off-topic here. Why
    would you try to optimize a native function with Javascript???

    @Thomas Lahn:
    >> [...] the function is *there*. I am talking about Firefox 3.6, Safari 4.0.4,
    >> Google Chrome 3.0 and IE8. Today.

    >
    > If you limit your target runtime environments like this, then it becomes
    > easier to do, but less compatible, of course.


    Well that is covering quite well the current world of desktop
    browsers.

    Javascript servers like Rhino and Google's V8 Javascript Engine also
    implement a meaningful <Function instance>.toString() method. Anyone
    using e.g. node.js can use the technique I presented.

    Guillaume
     
    glathoud, Feb 4, 2010
    #12
  13. glathoud wrote:

    > @Thomas Lahn:


    This is not a chat. Reply to the posting you are referring to.

    >>> [...] the function is *there*. I am talking about Firefox 3.6, Safari
    >>> 4.0.4, Google Chrome 3.0 and IE8. Today.

    >>
    >> If you limit your target runtime environments like this, then it becomes
    >> easier to do, but less compatible, of course.

    >
    > Well that is covering quite well the current world of desktop
    > browsers.


    You have not even scratched the surface.

    > Javascript servers


    For the umpteenth time, there is no "Javascript"!

    > like Rhino


    Rhino is not a "Javascript server", it is a JavaScript script engine
    written in Java.

    > and Google's V8 Javascript Engine


    V8 implements Google's ECMAScript implementation, not "Javascript".

    > also implement a meaningful <Function instance>.toString() method.


    True.

    > Anyone using e.g. node.js can use the technique I presented.


    Your experience and tests are too limited to make that assessment.


    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
     
    Thomas 'PointedEars' Lahn, Feb 4, 2010
    #13
  14. Thomas 'PointedEars' Lahn wrote:
    > 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.


    Is it?

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


    I don't see the problem with the test case.

    >> [...]
    >> 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.
    >


    I did not invent that data; I ran the code and the result was produced.
    I did not copy the whitespace separators correctly for Chrome result,
    but that is so minor it seems hardly worth mentioning. At least to me.
    --
    Garrett
    comp.lang.javascript FAQ: http://jibbering.com/faq/
     
    Garrett Smith, Feb 4, 2010
    #14
  15. Garrett Smith wrote:

    > Thomas 'PointedEars' Lahn wrote:
    >> 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.

    >
    > Is it?


    Quite obviously. You are calling the method on the built-in protoype
    object, not on a user-defined function.

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

    >
    > I don't see the problem with the test case.


    Look closer.

    >>> [...]
    >>> 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.

    >
    > I did not invent that data; I ran the code and the result was produced.
    > I did not copy the whitespace separators correctly for Chrome result,
    > but that is so minor it seems hardly worth mentioning. At least to me.


    Poor wording on my part. You test case is flawed as to the proof it is
    supposed to provide by your own account; the results that you presented
    are likely genuine, although rather useless.


    PointedEars
    --
    Danny Goodman's books are out of date and teach practices that are
    positively harmful for cross-browser scripting.
    -- Richard Cornford, cljs, <cife6q$253$1$> (2004)
     
    Thomas 'PointedEars' Lahn, Feb 4, 2010
    #15
  16. kangax wrote:

    > Garrett Smith wrote:
    >> Thomas 'PointedEars' Lahn wrote:
    >>> 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.

    >> Is it?
    >> [...]

    >
    > The problem is that `Function.prototype` does not reference user-defined
    > function ;)


    Exactly.

    > However, observing results of user-defined anonymous function —
    > `(function(){})+''` across common implementations is all it takes to
    > disprove absurd claims of PointedEars, such as this one:
    >
    > | 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".
    >
    >

    <http://groups.google.com/group/comp.lang.javascript/msg/621ffb36a5a2cd2b>
    >
    > [...]


    Let's test that rather bold statement of yours.

    Test case
    ----------

    (function(){})+''

    (String(...) or ...toString() would be more obvious, but if you insist ...)

    Results
    --------

    Microsoft JScript 5.6.6626 / IE 6.0.2800.1106 for Windows:

    "(function(){})"

    Mozilla.org JavaScript (TraceMonkey) 1.9.1.6 / Iceweasel 3.5.6:

    "function () {
    }"

    Google V8 1.3 / Chrome 4.0.249.43:

    "function(){}"

    Apple JavaScriptCore of WebKit 531.21.8 / Safari 4.0.4 for Windows:

    "function () {}"

    Opera Futhark of Presto 2.4 / Opera 10.10 for Debian/Ubuntu:

    "function(){}"

    KJS / Konqueror 4.3.4:

    "function ()
    {
    }"

    Apple JavaScriptCore of WebKit 528.18 / Mobile Safari 4.0 / iPhoneOS 3.1.2:

    "function () {}"


    All those undoubtedly common implementations return a string value that is
    undoubtedly syntactically correct code.

    You were saying?


    PointedEars
    --
    realism: HTML 4.01 Strict
    evangelism: XHTML 1.0 Strict
    madness: XHTML 1.1 as application/xhtml+xml
    -- Bjoern Hoehrmann
     
    Thomas 'PointedEars' Lahn, Feb 4, 2010
    #16
  17. kangax wrote:

    > Thomas 'PointedEars' Lahn wrote:
    >> kangax wrote:

    > [...]
    >>> However, observing results of user-defined anonymous function —
    >>> `(function(){})+''` across common implementations is all it takes to
    >>> disprove absurd claims of PointedEars, such as this one:
    >>>
    >>> | 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".

    >>

    <http://groups.google.com/group/comp.lang.javascript/msg/621ffb36a5a2cd2b>
    >>>
    >>> [...]

    >>
    >> Let's test that rather bold statement of yours.
    >> [...]
    >> All those undoubtedly common implementations return a string value that
    >> is undoubtedly syntactically correct code.
    >>
    >> You were saying?

    >
    > You know exactly what I was saying.


    You said that the statement I made (as you quoted above) could be
    disproven by those tests. The tests did not disprove it.

    > None of these conform to syntax of /FunctionDeclaration/.


    Nobody claimed they do. Your turn.


    PointedEars
    --
    var bugRiddenCrashPronePieceOfJunk = (
    navigator.userAgent.indexOf('MSIE 5') != -1
    && navigator.userAgent.indexOf('Mac') != -1
    ) // Plone, register_function.js:16
     
    Thomas 'PointedEars' Lahn, Feb 4, 2010
    #17
  18. Thomas 'PointedEars' Lahn wrote:
    > kangax wrote:
    >
    >> Garrett Smith wrote:
    >>> Thomas 'PointedEars' Lahn wrote:
    >>>> 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.
    >>> Is it?
    >>> [...]

    >> The problem is that `Function.prototype` does not reference user-defined
    >> function ;)

    >
    > Exactly.
    >


    Function.prototype.toString returns an implementation-dependent
    representation of the function it is called on. "This representation has
    the syntax of a FunctionDeclaration." (Ecma-262 r3, r5).

    Calling Function.prototype.toString on a function should return an
    implementation-dependent string with the syntax of a FunctionDeclaration.

    Function.prototype is a function.

    Calling Function.prototype.toString on Function.prototype should return
    an implementation-dependent string with the syntax of a FunctionDeclaration.

    The expected result is a FunctionDeclaration. Of the browsers tested
    Chrome passed.

    The result shows that Function.prototype.toString does not perform as
    specified, and that it fails in the most blatantly obvious way; by
    calling it just as specified: `Function.prototype.toString()`.

    The fact that Function.prototype.toString fails in the most blatantly
    obvious way in all known implementations provides very strong indication
    that it is specified incorrectly.

    >> However, observing results of user-defined anonymous function —
    >> `(function(){})+''` across common implementations is all it takes to
    >> disprove absurd claims of PointedEars, such as this one:
    >>
    >> | 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".
    >>


    The specification guarantees that Function.prototype.toString returns
    the syntax of a FunctionDeclaration.

    What part of "implementation-dependent" sounds reliable?

    Javascript interpreters may make optimizations. Indeed, we have seen
    cases where implementations will optimize away the creation of the
    arguments object, or have better performance for an array that looks
    like it might be "dense", depending on how the array is populated for
    example.

    Therefore, an implementation might want to to drop useless statements
    during lexical interpretation.

    Testing that, we can create a function with a useless statement, call
    its toString, and examine the result:

    (function x() {
    if(false) alert(42);
    }).toString();

    could legally result:-

    "function x() {
    }"

    And in Spidermonkey (and Tracemonkey) that the result produced. That
    result dates back to Firefox 2, possibly earlier.

    Of course, the result could also be, legally:-

    "function y(){
    if(true) alert(42);
    "

    However:
    (function(){}).toString()

    - could not legally result "function() { }"

    As stated several times in this thread, that happens in 5 engines.

    Function.prototype.toString returns varied implementation-dependent
    results, as specified.

    Implementations also violate the specification by returning a string
    that is not a FunctionDeclaration representation (as stated numerous times).

    >>

    > <http://groups.google.com/group/comp.lang.javascript/msg/621ffb36a5a2cd2b>
    >> [...]

    >
    > Let's test that rather bold statement of yours.
    >
    > Test case

    [snip]

    Didn't I already test that?

    Following the test of Function.prototype.toString(), I wrote:-

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

    > All those undoubtedly common implementations return a string value that is
    > undoubtedly syntactically correct code.
    >

    None of those results are a string representation of a FunctionDeclaration.

    As such, none of them can be considered "syntactically correct" result.
    --
    Garrett
    comp.lang.javascript FAQ: http://jibbering.com/faq/
     
    Garrett Smith, Feb 4, 2010
    #18
  19. Garrett Smith wrote:

    > Thomas 'PointedEars' Lahn wrote:
    >> kangax wrote:

    >
    > [snip "Garrett doesn't get it"]
    >>
    >> Let's test that rather bold statement of yours.
    >>
    >> Test case

    > [snip]
    >
    > Didn't I already test that?


    No, you didn't. You tested the return value of
    Function.prototype.toString() when called on Function.prototype, a built-in
    object, which you still don't seem to get.

    > Following the test of Function.prototype.toString(), I wrote:-
    >
    > | Chrome 4 is the only browser that conforms there, but then it fails


    That is hardly a viable test result. You don't say the exact version or
    operating system, and you don't say what other implementations you have
    tested, so your "only" is sufficiently bogus to be disregarded.

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


    The result does not comply with what the Specification says. Nobody denied
    that. However, it is syntactically correct, so let it be stored in `f', it
    can be used in eval("(" + f + ")") and does not matter for this use case.
    Got it?

    >> All those undoubtedly common implementations return a string value that
    >> is undoubtedly syntactically correct code.

    >
    > None of those results are a string representation of a
    > FunctionDeclaration.


    And I did not say they would. Got it now?

    > As such, none of them can be considered "syntactically correct" result.


    Nonsense.


    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
     
    Thomas 'PointedEars' Lahn, Feb 5, 2010
    #19
  20. Thomas 'PointedEars' Lahn wrote:
    > Garrett Smith wrote:
    >
    >> Thomas 'PointedEars' Lahn wrote:
    >>> kangax wrote:

    >> [snip "Garrett doesn't get it"]


    You can say that, but it does not make Function decompilation any more
    reliable.

    >> Didn't I already test that?

    >
    > No, you didn't. You tested the return value of


    [snip]

    No, actually I did. Here it is again:

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

    >


    I tested user-defined function just above.

    > The result does not comply with what the Specification says. Nobody denied
    > that. However, it is syntactically correct, so let it be stored in `f', it
    > can be used in eval("(" + f + ")") and does not matter for this use case.
    > Got it?
    >

    Something that "can be used in eval" does not make that thing a
    FunctionDeclaration.

    Function serialization is defined as being "implementation-dependent".
    Sounds unreliable. No?

    The most obvious cases of serializing built-in and user-defined function
    fails to do what is specified in the most popular implementations.
    Sounds unreliable. Still not convinced?

    It fails to serialize user-defined functions as written, as shown in
    examples by kangax, Richard, and myself, is unreliable.

    I fail to see the benefit in defending such unreliable strategy.
    Furthermore, the reasons for wanting to do that are usually based on
    inexperienced floundering and misguidance.
    --
    Garrett
    comp.lang.javascript FAQ: http://jibbering.com/faq/
     
    Garrett Smith, Feb 5, 2010
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Crutcher
    Replies:
    4
    Views:
    310
    Michel Salim
    Mar 3, 2006
  2. Sam Stephenson

    Tail call ``optimization''

    Sam Stephenson, Sep 24, 2004, in forum: Ruby
    Replies:
    1
    Views:
    130
    Robert Klemme
    Sep 25, 2004
  3. Thomas Hurst

    1.9 tail-call optimization status?

    Thomas Hurst, Aug 23, 2008, in forum: Ruby
    Replies:
    0
    Views:
    114
    Thomas Hurst
    Aug 23, 2008
  4. Terry Michaels

    Tail Call Optimization (Tail Recursion)

    Terry Michaels, Apr 18, 2011, in forum: Ruby
    Replies:
    16
    Views:
    335
    Robert Klemme
    Apr 20, 2011
  5. Balazs Endresz

    tail call optimization problem

    Balazs Endresz, May 2, 2010, in forum: Javascript
    Replies:
    9
    Views:
    191
    Ry Nohryb
    May 2, 2010
Loading...

Share This Page