380237 - (genexp) Implement generator expressions for JS1.8

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[Brendan Eich [:brendan]]

Attachment: generator expression, v1

Inspired by Peter Norvig's sudoku solver literately programmed at

http://norvig.com/sudoku.html

I translated his sudoku.py into JS. The generalized depth-first search with constraint propagation solution fails to complete due to lack of generator expressions in JS1.7 -- expanding these to array comprehensions ties up too much RAM and too many cycles computing results that are not needed by the some function in search. So I implemented generator expressions -- they were easy enough with a little refactoring.

I did not implement the "Early Binding versus Late Binding" part of PEP 289. This section abuses "binding" to mean "evaluation", but otherwise it makes a pragmatic usability decision in favor of evaluating the first |for| expression (the one on the right of the |for|'s |in| keyword) early, and any chained |for| expressions further to the right in the generator expression later. See the PEP for the rationale.

For JS1.8 and JS2/ES4, I think it's best to treat generator expressions as sugar for anonymous generation functions that are immediately applied, resulting in a generator-iterator. That's what I've implemented, and it requires no unusual "early evaluation".

SpiderMonkey patch attached here; sudoku.js that depends on it attached next.

/be

Comment 1

[Brendan Eich [:brendan]]

Attachment: sudoku.js, from Peter Norvig's sudoku.py

More grist for JS1.8/2 and ES4:

// XXX should be standard (and named clone, after Java?)
// XXX thought spurred by the next two functions: array extras should default to identity function
    // XXX should destructure [s, d] but JS1.7 is broken
    // XXX Math.min etc. should work with generator expressions and other iterators
    // XXX Math.min etc. should work on arrays (lists or tuples in Python) as well as numbers

/be

Comment 2

[Brendan Eich [:brendan]]

Attachment: generator expression, v1a

Nit-pick old spacing gaffe; report errors for comma expression as left-hand side of |for| in a generator expression.

/be

Comment 3

[Brendan Eich [:brendan]]

Attachment: sudoku.js, more array comprehension removal via genexps

Comment 4

[Brendan Eich [:brendan]]

Attachment: generator expressions, v1b

Fine-tune error reporting to point to the offending source location.

This is ready for review. It looks a bit bigger than it is, because code moved from PrimaryExpr (the array comprehension case) into ComprehensionTail.

/be

Comment 5

[Jesse Ruderman]

With this patch, generator expressions decompile as the "anonymous generation functions that are immediately applied" they're sugar for, instead of decompiling as generator expressions.  Is that intentional?

js> j = function() { g = (d for (d in [0])); g.next(); }

function () {
    g = (function () {for (d in [0]) {yield d;}})();
    g.next();
}

If you're going to keep it that way, you should toss in a "let" in the decompilation so that the variable "d" doesn't leak out of scope in the decompiled version.

Comment 6

[Brendan Eich [:brendan]]

Comment on attachment 264446 [details] [diff] [review]
generator expressions, v1b

Oops, good point -- the decompiler needs a hint. The loop variable is a let by virtue of it being bound by the parser in the prototype block object, so the emitter specializes to the right opcode (JSOP_FORLOCAL). But the decompiler does not know to add 'let'.

Really, though, we ought to decompile generator expressions properly.

/be

Comment 7

[Brendan Eich [:brendan]]

Attachment: generator expressions, v2

Now with decompilation!

Other than InitSprintStack moving, and the code for unannotated JSOP_YIELD indenting one level, the change here adds a SRC_GENEXP alias for a unit-byte note (SRC_IF is the original such note) applied to the JSOP_ANONFUNOBJ that pushes the generator expression's lambda. Using this note, the decompiler can pretty-print the generator expression, reusing much of the machinery for array comprehensions.

/be

Comment 8

[Igor Bukanov]

Comment on attachment 264585 [details] [diff] [review]
generator expressions, v2

>===================================================================
>RCS file: /cvsroot/mozilla/js/src/jsopcode.c,v
...
>@@ -3612,19 +3654,92 @@ Decompile(SprintStack *ss, jsbytecode *p
...
>+              case JSOP_ANONFUNOBJ:
>+                    /*
>+                     * Alas, we have to malloc a copy of the result left on
>+                     * the top of ss2 because both ss and ss2 arena-allocate
>+                     * from cx's tempPool.
>+                     */
>+                    rval = JS_strdup(cx, PopStr(&ss2, op));
>+                    JS_ARENA_RELEASE(&cx->tempPool, mark);
>+                    if (!rval)
>+                        return NULL;
>+                    todo = SprintCString(&ss->sprinter, rval);
>+                    JS_free(cx, (void *)rval);
>+                    break;
>+                }

Nit: using char* variable in place of const char* rval avoids the cast to void*.

Besides this, the patch looks fine.

Comment 9

[Jesse Ruderman]

js> (function() { g = (d for (d in [0]) for (e in [1])); })
Assertion failure: blockpos == 0 && pos == 0, at jsopcode.c:2703

Comment 10

[Jesse Ruderman]

js> function() { return (1 for (i in [])) } 
function () {
    return 1 for (i in []);
}

Needs parens.  Same with |yield|.

Comment 11

[Jesse Ruderman]

A generator expression can be used as a "with-statement object", but only if it has extra parens around it.  That seems strange and results in decompilations that don't compile:

js> f = function() { with((x for (x in []))) { } }
function () {
    with (x for (x in [])) {
    }
}
js> eval("" + f)
typein:5: SyntaxError: missing ) after with-statement object:
typein:5:     with (x for (x in [])) {
typein:5: ............^

Comment 12

[Jesse Ruderman]

An "if (1)" at the end of a generator expression is nicely optimized away, but an "if (0)" causes an assertion failure.

js> (function() { (1 for (w in []) if (0)) })
Assertion failure: ss2.top == 1, at jsopcode.c:3715

Comment 13

[Jesse Ruderman]

Empty destructuring (aka "binding nothing") strikes again?

js> (function() { (x for ([{}, {}] in [])); })
Assertion failure: pos != 0, at jsopcode.c:2693

Comment 14

[Jesse Ruderman]

js> (function() { (x for each (x in [])) = 3; })
Assertion failure: *pc == JSOP_CALL, at jsopcode.c:3708

Comment 15

[Brendan Eich [:brendan]]

Jesse had a co-starring role in "Hot Fuzz" :-P.

New patch shortly.

/be

Comment 16

[Brendan Eich [:brendan]]

Attachment: generator expressions, v3

The decompiler is costing too much, as usual. But here is a patch that addresses all of the hard cases Jesse found by fuzzing. This patch also includes the fix for bug 380506, which I will split out later tonight.

/be

Comment 17

[Brendan Eich [:brendan]]

Comment on attachment 264950 [details] [diff] [review]
generator expressions, v3

mrbkap is on the road, but I would appreciate his review too.

/be

Comment 18

[Brendan Eich [:brendan]]

Attachment: generator expressions, v3

This is the right patch.

/be

Comment 19

[Jesse Ruderman]

js> (function() { (x*x for (x in a)); })
function () {
    (x for (x in a) * x for (x in a) for (x in a));
}

(for (x in a) for (x in a)?  for (x in a)!)

Comment 20

[Jesse Ruderman]

The problem in comment 10 still exists.

Comment 21

[Jesse Ruderman]

Simple loops crash!?

js> for (i = 0; i < t; ++i) { }
Assertion failure: CURRENT_TOKEN(ts).type == TOK_LP, at jsparse.c:5973

Comment 22

[Brendan Eich [:brendan]]

Attachment: generator expressions, v3a

Sorry, I had comment 10's problem fixed, and then I unfixed it at the last minute. That for loop assertion is trying to tell me that it's not worth allowing an unparenthesized generator expression in any of the three for-loop head parts.

This patch unfixes bug 349650 since the fix attempt was bogus, resulting in the mess shown in comment 19 -- look for the FIXME comment.

This patch passes the testsuite and all the comments' testcases.

/be

Comment 23

[Jesse Ruderman]

js> function() { (yield x for (x in [1,2,3])) }
function () {
    (x for (x in [1, 2, 3]));
}

I have no idea how "(yield x for (x in [1,2,3]))" should be interpreted.  Syntax error?  yield the genexp?  "(yield x)" from the outer function somehow?  "(yield x)" from the generator?  The current behavior almost seems consistent with the last interpretation, but I think it isn't really consistent (at least for more complicated examples).

Comment 24

[Jesse Ruderman]

Attachment: parenthesization test

Given that parentheization seems so fragile *and* the rules for where genexps are allowed keep changing, I thought it would be good to have a way to test that:

1)
unparenthesized genexps are allowed in some places
  and the decompilation is sane and not over-parenthesized

2)
unparenthesized genexps are disallowed in many places
  and when there are parens, the decompilation is sane and not over-parenthesized

This test finds several cases where decompilation is over-parenthesized:

    new ((x * x for (x in [])));
    new a((x * x for (x in [])));
    eval((x * x for (x in [])));    // yay for eval being special
    ((x * x for (x in [])))();

It also finds one bug where the decompilation is under-parenthesized and does not compile as a result:

    for (; x * x for (x in []);) { }

Am I understanding correctly that genexps are *only* allowed "without parens" in contexts where there are already parens snugly around it, such as f(genexp) and with(genexp){}?  That's what the test seems to show, at least ;)

Perhaps a modified version of this test can become part of the JavaScript Engine test suite.

Comment 25

[Jesse Ruderman]

js> (function () { (1 for (y in (yield 3))); })
Assertion failure: expos < ss->top, at jsopcode.c:2708

Comment 26

[Jesse Ruderman]

> This patch unfixes bug 349650 since the fix attempt was bogus, resulting in the
> mess shown in comment 19 -- look for the FIXME comment.

In what way does it unfix that bug?  It seems ok to me with the testcase in that bug.

Comment 27

[Jesse Ruderman]

js> (function () { delete (x for (x in [])); })
Assertion failure: *pc == JSOP_CALL, at jsopcode.c:3725

Comment 28

[Jesse Ruderman]

$ ./js -v 170
js> (function() { ([yield] for (x in [])); })
Assertion failure: pos == 0, at jsopcode.c:2718

Comment 29

[Brendan Eich [:brendan]]

Comment on attachment 264975 [details] [diff] [review]
generator expressions, v3a

New patch in a bit.

/be

Comment 30

[Jesse Ruderman]

js> f = function() { if(1, (x for (x in []))) { } }
function () {
    if (1, x for (x in [])) {
    }
}
js> eval("" + f)
typein:3: SyntaxError: generator expression must be parenthesized: [...]

Comment 31

[Brendan Eich [:brendan]]

(In reply to comment #26)
> > This patch unfixes bug 349650 since the fix attempt was bogus, resulting in the
> > mess shown in comment 19 -- look for the FIXME comment.
> 
> In what way does it unfix that bug?  It seems ok to me with the testcase in
> that bug.

With the latest patch,

js> function(){return(i*j for each (i in [1,2,3,4]) for each (j in [5,6,7,8]))}
function () {
    return (i * j for each (i in [1, 2, 3, 4]));
}

I was trying to fix the loss of the inner for-head, which is what bug 349650 is all about. I may yet get a fix.

Thanks for the parenthesization test. Parenthesization of generator expressions is complicated in JS compared to Python, because Python doesn't have parenthesized head syntax for if, while, etc., so it can simply require parenthesization of genexps in all cases except a single actual argument

Now (latest and next patches) with JOF_PARENHEAD set in the formats of the opcodes that consume the result of evaluating such head expressions, SpiderMonkey is on more stable ground. The only hard case for the decompiler involves distinguishing |if (genexp)| from |(genexp) ? y : z| -- the latter must parenthesize genexp, the former should not (over-)parenthesize.

The parser is still inherently complicated compared to Python. My original patch was just like Python: only the argument list and parenthesized expression rules needed tweaking. But JS inherited the curse of C syntax, which may also be a blessing (who knows? It's claimed to be a _sine qua non_ of the NBL ;-).

/be

Comment 32

[Brendan Eich [:brendan]]

(In reply to comment #23)
> js> function() { (yield x for (x in [1,2,3])) }
> function () {
>     (x for (x in [1, 2, 3]));
> }
> 
> I have no idea how "(yield x for (x in [1,2,3]))" should be interpreted.

Sure you do ;-).

$ python2.5
>>> g = ((yield i*i) for i in range(1,5))
>>> g.next()
1
>>> g.next()
>>> g.next()
4
>>> g.next()
>>> g.next()
9
>>> g.next()
>>> g.next()
16
>>> g.next()
>>> g.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

/be

Comment 33

[Jesse Ruderman]

If that's the intent, the "yield not in function" error needs to go away for that case in JavaScript.

js> g = ((yield i) for (i in [1,2,3]))
typein:1: SyntaxError: yield not in function: [...]

Comment 34

[Bob Clary [:bc] (inactive)]

(In reply to comment #24)

> Perhaps a modified version of this test can become part of the JavaScript
> Engine test suite.

sure, as soon as the bug is fixed, I'll add it to the js1_8 suite.

Comment 35

[Jesse Ruderman]

> I was trying to fix the loss of the inner for-head, which is what bug 349650 is
> all about. I may yet get a fix.

That sounds more like bug 380506 than bug 349650.

Comment 36

[Jesse Ruderman]

Another place where decompilation needs parens:

js> f = function() { try { } catch(x if (1 for (x in []))) { } finally { } }; uneval(f);
(function () {try {} catch (x if 1 for (x in [])) {/*EXCEPTION*/;} finally {}})
js> eval(uneval(f));
typein:2: SyntaxError: missing ) after catch: [...]

Comment 37

[Brendan Eich [:brendan]]

(In reply to comment #35)
> > I was trying to fix the loss of the inner for-head, which is what bug 349650 is
> > all about. I may yet get a fix.
> 
> That sounds more like bug 380506 than bug 349650.

D'oh, that's the bug I meant. Thanks,

/be

Comment 38

[Igor Bukanov]

I am taking few days off so do not count on any my r=something until Tuesday. 

Comment 39

[Brendan Eich [:brendan]]

Attachment: Jesse's parenthesization test, more cases added

Comment 40

[Jesse Ruderman]

Attachment: Parenthesization test, even more cases added

Comment 41

[Jesse Ruderman]

Attachment: Parenthesization test

Includes a new failure found by jsfunfuzz:

js> f = function() { if (1, (x for (x in []))) { } }
function () {
    if (1, x for (x in [])) {
    }
}
js> eval("" + f)
typein:5: SyntaxError: generator expression must be parenthesized: [...]

Interesting that the decompilation of a comma expression containing a genexp is different when it is part of an "if" condition.

Comment 42

[Brendan Eich [:brendan]]

Attachment: generator expressions, v4

This passes the latest parenthesization test and the fuzzer-generated tests cited in comments 25-36 by Jesse.

/be

Comment 43

[Brendan Eich [:brendan]]

Attachment: generator expressions, v4a

A few "small" mistakes and a rogue line deletion fixed.

Parenthesization is changing a big, so the testsuite will give some false positives with this patch applied. It needs to adjust or relax.

/be

Comment 44

[Brendan Eich [:brendan]]

> Parenthesization is changing a big, so the testsuite will give some false

s/big/bit

/be

Comment 45

[Jesse Ruderman]

Comma expressions on the left side of genexps need to be parenthesized.

js> f = function() { ((a, b) for (x in [])) }
function () {
    (a, b for (x in []));
}
js> eval("" + f)
typein:4: SyntaxError: generator expression must be parenthesized: [...]

Comment 46

[Jesse Ruderman]

Removing the parens around lambda in lambda.foo broke the code that decides whether to use the "setter" or "set" syntax when decompiling object literals (see bug 355992, bug 358594, bug 380933, etc).

js> (function() { ({x setter: (function () {}).x }) })
Assertion failure: rval[strlen(rval)-1] == '}', at jsopcode.c:4182

Comment 47

[Brendan Eich [:brendan]]

Attachment: generator expressions, v4b

Fix the two problems Jesse found, and via the getter/setter decompilation fix, also fix bug 381101 (a spot-fix patch can be extracted, but I don't want this bug's patch to regress anything even temporarily).

/be

Comment 48

[Brendan Eich [:brendan]]

Attachment: generator expressions, v4c

Third time's the charm.

/be

Comment 49

[Brendan Eich [:brendan]]

Attachment: generator expressions, v4d

I hate the newfangled get/set syntax...

/be

Comment 50

[Brendan Eich [:brendan]]

Attachment: my final answer

Tracking checkin for bug 381101...

/be

Comment 51

[Blake Kaplan (:mrbkap) (inactive)]

Comment on attachment 265187 [details] [diff] [review]
my final answer

Bugzilla interdiff is failing me, but from what I've been able to glean, this is all good.

Comment 52

[Brendan Eich [:brendan]]

Fixed on trunk:

js/src/js.msg 3.78
js/src/jsconfig.h 3.44
js/src/jsemit.c 3.250
js/src/jsemit.h 3.74
js/src/jsopcode.c 3.241
js/src/jsopcode.h 3.46
js/src/jsopcode.tbl 3.93
js/src/jsparse.c 3.281
js/src/jsparse.h 3.41

Followup bugs as needed, this bug is fixed. Now to convince ECMA TG1.

/be

Comment 53

[Jesse Ruderman]

Attachment: Parenthesization test

Added tests to ensure that generator expressions are not allowed in LHS contexts.

Comment 54

[Jesse Ruderman]

Is it intentional that the for-LHS syntax is stricter for genexps than in standalone loops?

js> for ([x, z[y]] in []) { }

js> (function() { g = (1 for ([x, z[y]] in [])) })
typein:9: SyntaxError: missing variable name:
typein:9: (function() { g = (1 for ([x, z[y]] in [])) })
typein:9: ..............................^

Comment 55

[Jesse Ruderman]

In addition to my parenthesization test some functionality tests, testcases based on the following comments should be added to the test suite:

Comment 9  -- perhaps as a test for bug 380506
Comment 12 -- and the same thing with if(1)
Comment 13
Comment 25
Comment 28
Comment 33 -- be sure to test top-level
Comment 45
Comment 46

Comment 56

[Jesse Ruderman]

"Comment 12" in the previous comment refers to comment 12 in *this* bug.

Comment 57

[Brendan Eich [:brendan]]

(In reply to comment #54)
> Is it intentional that the for-LHS syntax is stricter for genexps than in
> standalone loops?
> 
> js> for ([x, z[y]] in []) { }
> 
> js> (function() { g = (1 for ([x, z[y]] in [])) })
> typein:9: SyntaxError: missing variable name:
> typein:9: (function() { g = (1 for ([x, z[y]] in [])) })
> typein:9: ..............................^

Yes, that's intentional. Without var or let (or even const) in a for loop, you can assign to arbitrary lvalues.

As with array comprehensions, generator expressions always bind lexical (let) variables scoped by the immediately enclosing comprehension or expression. IOW, there is an implicit let declaration for the first for-head's bindings. This is superior and Pythonic.

(The analogy is imperfect because if there is more than one for-head, then the variables in the second through Nth heads are all scoped by the same single block that corresponds to the immediately enclosing array comprehension or generator expression. Whereas with nested for-in loop statements, the scope of each head's bindings is that loop.)

/be

Comment 58

[Bob Clary [:bc] (inactive)]

I think I've included all requested tests.

/cvsroot/mozilla/js/tests/js1_8/genexps/regress-380237-01.js,v  <--  regress-380237-01.js
initial revision: 1.1
/cvsroot/mozilla/js/tests/js1_8/genexps/regress-380237-02.js,v  <--  regress-380237-02.js
initial revision: 1.1
/cvsroot/mozilla/js/tests/js1_8/genexps/regress-380237-03.js,v  <--  regress-380237-03.js
initial revision: 1.1
/cvsroot/mozilla/js/tests/js1_8/genexps/regress-380237-04.js,v  <--  regress-380237-04.js
initial revision: 1.1
/cvsroot/mozilla/js/tests/js1_8/genexps/browser.js,v  <--  browser.js
initial revision: 1.1
/cvsroot/mozilla/js/tests/js1_8/genexps/shell.js,v  <--  shell.js
initial revision: 1.1

jstest: js1_8/genexps/regress-380237-02.js bug:  result: FAILED 
expected:  function ( ) { ( 1 for ( w in [ ] ) if ( 1 ) ) ; }  
actual:    function ( ) { ( 1 for ( w in [ ] ) ) ; }

jstest: js1_8/genexps/regress-380237-02.js bug:  result: FAILED
expected:  function ( ) { ( x for ( [ { } , { } ] in [ ] ) ) ; }  
actual:    function ( ) { ( x for ( [ [ ] , [ ] ] in [ ] ) ) ; }

Comment 59

[Bob Clary [:bc] (inactive)]

oops, those failures should read js1_8/genexps/regress-380237-03.js

/cvsroot/mozilla/js/tests/js1_8/genexps/regress-380237-03.js,v  <--  regress-380237-03.js
new revision: 1.2; previous revision: 1.1

Comment 60

[Brendan Eich [:brendan]]

Attachment: sudoku.js, updated after fix for bug 366941 landed

Comment 61

[Bob Clary [:bc] (inactive)]

update to latest sudoku
/cvsroot/mozilla/js/tests/js1_8/genexps/regress-380237-01.js,v  <--  regress-380237-01.js
new revision: 1.2; previous revision: 1.1

Comment 62

[Bob Clary [:bc] (inactive)]

current set of failures. Are these real failures, or should the test be adjusted?

js1_8/genexps/regress-380237-03.js

expected:  function ( ) { ( 1 for ( w in [ ] ) if ( 1 ) ) ; }  
  actual:  function ( ) { ( 1 for ( w in [ ] ) ) ; }

expected:  function ( ) { ( x for ( [ { } , { } ] in [ ] ) ) ; }  
  actual:  function ( ) { ( x for ( [ [ ] , [ ] ] in [ ] ) ) ; }

expected:  function ( ) { ( [ ( yield ) ] for ( x in [ ] ) ) ; }
  actual:  function ( ) { ( [ yield ] for ( x in [ ] ) ) ; }

Comment 63

[Jesse Ruderman]

> expected:  function ( ) { ( 1 for ( w in [ ] ) if ( 1 ) ) ; }  
>   actual:  function ( ) { ( 1 for ( w in [ ] ) ) ; }

That's a reasonable optimization to make, and it's intentional.  If the condition were if(x) instead of if(1), it wouldn't be optimized away.  Please change the "expected" for this test, and add a test with if(x).

> expected:  function ( ) { ( x for ( [ { } , { } ] in [ ] ) ) ; }  
>  actual:  function ( ) { ( x for ( [ [ ] , [ ] ] in [ ] ) ) ; }

We do the same thing for empty hash-destructuring in other contexts:

js> (function() { ({}) = h; })
function () {
    [] = h;
}

I don't know whether it's intentional and I don't know whether it's incorrect.  It does lead to bug 356247, though ;)

> expected:  function ( ) { ( [ ( yield ) ] for ( x in [ ] ) ) ; }
>   actual:  function ( ) { ( [ yield ] for ( x in [ ] ) ) ; }

Not over-parenthesizing yield seems like a good thing to me :)  I think this is the "optimize away parens around any single expr in brackets or parens" change Brendan made in bug 381113 comment 40.

Comment 64

[Jeff Walden [:Waldo]]

(In reply to comment #63)
> I don't know whether it's intentional and I don't know whether it's incorrect. 

Per <http://developer.mozilla.org/es4/proposals/destructuring_assignment.html> this is safe to do; it's not kosher in type-checked ES4, but that's not a problem for now.

Comment 65

[Brendan Eich [:brendan]]

Jeff: ([] : {}) and ({length:0} : []) are both valid structural-type-annotated expressions. So [] should be usable as an empty pattern instead of {} when destructuring, no matter the type of the right hand side *or* the type annotated on the left-hand side (if any).

It would be nicer to decompile {} as {} and [] as [], for sure, but I don't see a type error under ES4. What am I missing?

/be

Comment 66

[Jeff Walden [:Waldo]]

I was operating under the assumption, based on a quick and inaccurate skim of the typing section, that the rvalue for a destructuring assignment must have the same type as the rhs pattern, e.g.:

> var [a, b] = rvalue; // rvalue is Array

My closer scan finds no such constraint explicitly mentioned, but I think it's reasonable to assume it'll be a part of LeftHandSideExpression's verification, which isn't yet described in chapter 14.

This doesn't preclude special-casing empty destructuring verification to do verifyType(rvalueType, *), but I think this is unintuitive at best.

Comment 67

[Brendan Eich [:brendan]]

(In reply to comment #66)
> I was operating under the assumption, based on a quick and inaccurate skim of
> the typing section, that the rvalue for a destructuring assignment must have
> the same type as the rhs pattern, e.g.:

(s/rhs/lhs/, right?)

> 
> > var [a, b] = rvalue; // rvalue is Array
> 
> My closer scan finds no such constraint explicitly mentioned, but I think it's
> reasonable to assume it'll be a part of LeftHandSideExpression's verification,
> which isn't yet described in chapter 14.

The type of [a, b] is [*]. The names a and b don't tell us anything about the types of values in the rvalue at property ids 0 and 1. To annotate a destructuring binding form, you write

  var [a, b] : [int, string] = rvalue;

for example. Even here, the type annotation does not make it a type error for rvalue to be {0: "42", 1: 3}, because annotation means conversion. The lack of a DontEnum length property in such an rvalue is not an issue, either, since length is not being destructured. Destructuring is really just sugar for property gets and variable or (in an assignment expression, not in a binding form) lvalue sets.

/be

Comment 68

[Igor Bukanov]

Attachment: sudoku written in EcmaScript 3 and functional programming style

Brendan wrote in bug 382335 comment #11:
> (In reply to bug 382335 comment #9)
> > After spending 4 hours trying to debug the example my conslusion is rather
> > anti-generator one:
> > 
> > 1. JS code that explicitly calls generator method is extremely fragile and hard
> > to follow.
> 
> Maybe, but generators help avoid explicit state save/restore, or even more
> difficult for average programmers continuation passing style (which risks stack
> overflow without proper tail call guarantees).

The attached example rewrites the sudoku example using functional programming style using just EcmaScript v3 syntax. The code does not manipulate the state explicitly, does not use continuation style and does not rely on tail call elimination.  

> Don't judge only by this example, esp. from your view of it in gdb!

gdb alone was useless there since it was not clear where to look for. The most of the time was spend to understand/simplify the code to clear its functionality. In any case, that generator abuse was just a final straw that triggered me to write that comment.

> 
> > 2. JS code that uses generators with for-in loops can be replaced by explicit
> > lambdas or functions without loss of functinality and readability as any loop
> > like
> > 
> > for (i in iterator) 
> >    body;
> > 
> > can be written in the following style:
> > 
> > iterator(f);
> > function f(i) body;
> 
> That's true only if you are willing to turn your generator function inside out
> and make it save state explicitly, or in its activation/continuation.

I do not understand this claim about explicit state manipulation. Consider the following fragment:

for (let i in sequence_as_generator())
  complex_body;
...
function sequence_as_generator()
{
 ...; yield element; ...
}

If written using functional style will look like:

sequence_as_function(function(i) {
  complex_body;
});

function sequence_as_function(action)
{
 ...; action(element); ...
}

Clearly, if complex_body has some control transfer outside the loop, the functional transformation would require to define some protocol so action(element) can break the iteration, but even in the case of sudoku.js a simple solution based on the return value of action(element) was enough.

So where exactly is state manipulation in the functional style which was not present with generators?

> > Thus all those extra efforts for the parser and runtime support for generators
> > is just a bloat to support writing unmaintainable code.
> 
> Judging from one example is risky.
> 
> Consider the Sudoku solver from Bug 380237.

This is what I did and it only confirmed my expectations. The rewritten code does not use for-in loops and instead relies on its functional equivalent. Yet with optimized js shell it only 15% percent slower (best time increases from 0.693s to 0.791). And if I replace the single functional loop inside eliminate/check_places with explicit for (var i = 0; i != u.length; ++i) it would drop the best time to 0.537s.

So again I end up with that conclusion: generators is just a bloat to support writing unmaintainable code.

Comment 69

[Brian Crowder]

I think perhaps the use of generators in a processing intensive application like the sudoku solver isn't a great example of their most intuitive usage, which for me is in managing code that might block, as in a network application, or while waiting for database activity.

Neil Mix's "thread" library makes writing code like that a lot more straightforward, and you can explicitly "block" your coroutine while waiting for external work to complete (network packets to arrive, DB results, etc.), without implementing a state machine:

function interview(user)
{
    user.ask_question("question 1");
    let answer = yield user.wait_input();

    let dbresult = yield wait_db_query("insert into....");
    .... handle dbresult ....

    user.ask_question("question 2");
    answer = yield user.wait_input();
    .... and so on ....
}

I still think this is a very useful programming paradigm, and allows for significantly cleaner code in some circumstances.  The fact that it also yields as much as a 15% performance improvement for something like the sudoku solver doesn't seem easily dismissed, either, though.

Comment 70

[Bob Clary [:bc] (inactive)]

/cvsroot/mozilla/js/tests/js1_8/genexps/regress-380237-03.js,v  <--  regress-380237-03.js
new revision: 1.3; previous revision: 1.2

updated per Jesse. Passes all cases now.

Comment 71

[Brendan Eich [:brendan]]

Igor's rewrite is quite a bit bigger too, by wc -l (counting comments too, but apples to apples).

The Sudoku solver does not show state-saving wins due to generators, but it does show conciseness and (if you are aware of Python or otherwise know about genexps) clarity through less functional boilerplate.

Brian is right to point to i/o muxing as a likelier place to find state saving wins via generator-function local variables.

/be

Comment 72

[Igor Bukanov]

(In reply to comment #69)
> Neil Mix's "thread" library makes writing code like that a lot more
> straightforward, and you can explicitly "block" your coroutine while waiting
> for external work to complete (network packets to arrive, DB results, etc.),
> without implementing a state machine:
> 
> function interview(user)
> {
>     user.ask_question("question 1");
>     let answer = yield user.wait_input();
> 
>     let dbresult = yield wait_db_query("insert into....");
>     .... handle dbresult ....
> 
>     user.ask_question("question 2");
>     answer = yield user.wait_input();
>     .... and so on ....
> }
> 
> I still think this is a very useful programming paradigm, and allows for
> significantly cleaner code in some circumstances.

Here is a functional equivalent of the above code:

function interview(user)
{
    actions(
        function() {
            user.ask_question("question 1");
            user.wait_input();
        }
        function(answer) {
            let dbresult = yield wait_db_query("insert into....");
            .... handle dbresult ....
            user.ask_question("question 2");
            user.wait_input();
        },
        function(answer2) {
        }
    );
}

which assumes that there is a suitably defined actions function that runs its actions as a sequence.

Such functional style is strictly more powerful then using yield since with a suitable library one can define that some actions can run in parallel, that an action depends on a condition or should be repeated several times etc.

So here is that pattern again. The generators adds sugar that allows to simplify programming of very specific paradigms. Yet that sugar comes with heavy runtime code bloat. On the other hand, already widespread practice of using closures and lambdas (just consider all those XMLHttpRequest and setTimeout calls or tricks of using closures to get private variables) only very recently finally got a sweetener in the form of function shortcuts that allows to write function() exp instead of function() { return exp; }. 

This is nice, but it make me wonder why spend all those efforts to emulate Python, a language that only fairly recently got proper lambda and closure support and whose designers does not like them in any case AFAIK, when what JS is really need is some sugar that will allow to make the current JS programs clear and perhaps more efficient.
          
>  The fact that it also yields
> as much as a 15% performance improvement for something like the sudoku solver
> doesn't seem easily dismissed, either, though.

In the rewritten sudoku I on purpose haven't used any for loops except in few basic utility functions and used that loop function instead to show a particular style that already possible with ES3. If one rewrites a single functional loop in the performance-critical function via standard for(;;) loop, then the example would run 15% faster then the generator case.

Comment 73

[Igor Bukanov]

Attachment: functional sudoku using expression closures

Here is the functional sudoku again but this time it uses expression closures. In few places I perhaps went too far in eliminating { return ; }, but in general this is very nice sugar that makes code cleaner if used properly.

I wish all those efforts to emulate Python during the 15 or so months would be spent to improve closure performance and develop more sweeteners to make already written JS easier to follow.

Comment 74

[Jeff Walden [:Waldo]]

(In reply to comment #67)
> (s/rhs/lhs/, right?)

Yeah.

> snip bits of stuff about sugar and all...

The point is that intuitively, if I see |var [a, b] = foo();| I expect |foo()| returned an array, and I don't expect it returned an object with 0 and 1 properties.  The presence or absence of length is relevant only insofar as I know arrays have a length property.  Intuition about destructuring will be in line with its sugared definition, but I'll be very surprised if intuition doesn't (illogically?) expect the value assigned to the pattern to be an array, regardless that the destructuring cherrypicks 0, 1, 2, etc. properties off it.

Comment 75

[Bob Clary [:bc] (inactive)]

verified fixed 1.9.0 linux/mac*/windows.

Comment 76

[Bob Clary [:bc] (inactive)]

http://hg.mozilla.org/tracemonkey/rev/ea3d58b45bf5
/cvsroot/mozilla/js/tests/js1_8/genexps/regress-380237-01.js,v  <--  regress-380237-01.js
new revision: 1.3; previous revision: 1.2