Last Comment Bug 380237 - (genexp) Implement generator expressions for JS1.8
(genexp)
: Implement generator expressions for JS1.8
Status: VERIFIED FIXED
:
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Trunk
: All All
: P1 normal (vote)
: mozilla1.9alpha5
Assigned To: Brendan Eich [:brendan]
:
: Jason Orendorff [:jorendorff]
Mentors:
http://www.python.org/dev/peps/pep-0289/
Depends on: 382355 382673 486713
Blocks: js1.8
  Show dependency treegraph
 
Reported: 2007-05-09 18:59 PDT by Brendan Eich [:brendan]
Modified: 2009-04-04 11:38 PDT (History)
13 users (show)
bob: in‑testsuite+
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
generator expression, v1 (28.14 KB, patch)
2007-05-09 18:59 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
sudoku.js, from Peter Norvig's sudoku.py (5.12 KB, text/plain)
2007-05-09 19:01 PDT, Brendan Eich [:brendan]
no flags Details
generator expression, v1a (29.76 KB, patch)
2007-05-09 22:40 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
sudoku.js, more array comprehension removal via genexps (5.12 KB, text/plain)
2007-05-09 22:43 PDT, Brendan Eich [:brendan]
no flags Details
generator expressions, v1b (30.84 KB, patch)
2007-05-10 23:03 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
generator expressions, v2 (48.90 KB, patch)
2007-05-12 00:01 PDT, Brendan Eich [:brendan]
igor: review+
Details | Diff | Splinter Review
generator expressions, v3 (62.94 KB, patch)
2007-05-15 19:15 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
generator expressions, v3 (62.94 KB, patch)
2007-05-15 19:18 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
generator expressions, v3a (68.10 KB, patch)
2007-05-16 01:18 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
parenthesization test (3.82 KB, text/javascript)
2007-05-16 04:18 PDT, Jesse Ruderman
no flags Details
Jesse's parenthesization test, more cases added (3.91 KB, text/plain)
2007-05-16 23:48 PDT, Brendan Eich [:brendan]
no flags Details
Parenthesization test, even more cases added (4.58 KB, text/javascript)
2007-05-17 00:42 PDT, Jesse Ruderman
no flags Details
Parenthesization test (4.90 KB, text/javascript)
2007-05-17 13:54 PDT, Jesse Ruderman
no flags Details
generator expressions, v4 (137.25 KB, patch)
2007-05-17 14:12 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
generator expressions, v4a (137.29 KB, patch)
2007-05-17 16:01 PDT, Brendan Eich [:brendan]
mrbkap: review+
Details | Diff | Splinter Review
generator expressions, v4b (99.74 KB, patch)
2007-05-17 16:55 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
generator expressions, v4c (99.74 KB, patch)
2007-05-17 17:34 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
generator expressions, v4d (99.81 KB, patch)
2007-05-17 17:42 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
my final answer (98.46 KB, patch)
2007-05-17 17:52 PDT, Brendan Eich [:brendan]
mrbkap: review+
Details | Diff | Splinter Review
Parenthesization test (6.45 KB, text/javascript)
2007-05-17 19:27 PDT, Jesse Ruderman
no flags Details
sudoku.js, updated after fix for bug 366941 landed (5.09 KB, text/plain)
2007-05-29 21:29 PDT, Brendan Eich [:brendan]
no flags Details
sudoku written in EcmaScript 3 and functional programming style (9.69 KB, text/plain)
2007-05-31 10:07 PDT, Igor Bukanov
no flags Details
functional sudoku using expression closures (7.96 KB, text/plain)
2007-06-01 13:08 PDT, Igor Bukanov
no flags Details

Description Brendan Eich [:brendan] 2007-05-09 18:59:22 PDT
Created attachment 264310 [details] [diff] [review]
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] 2007-05-09 19:01:43 PDT
Created attachment 264311 [details]
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] 2007-05-09 22:40:22 PDT
Created attachment 264331 [details] [diff] [review]
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] 2007-05-09 22:43:40 PDT
Created attachment 264332 [details]
sudoku.js, more array comprehension removal via genexps
Comment 4 Brendan Eich [:brendan] 2007-05-10 23:03:51 PDT
Created attachment 264446 [details] [diff] [review]
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 2007-05-11 01:35:54 PDT
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] 2007-05-11 08:49:02 PDT
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] 2007-05-12 00:01:00 PDT
Created attachment 264585 [details] [diff] [review]
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 2007-05-12 07:55:49 PDT
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 2007-05-12 08:27:18 PDT
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 2007-05-12 23:52:05 PDT
js> function() { return (1 for (i in [])) } 
function () {
    return 1 for (i in []);
}

Needs parens.  Same with |yield|.
Comment 11 Jesse Ruderman 2007-05-12 23:56:33 PDT
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 2007-05-13 00:02:52 PDT
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 2007-05-13 00:11:10 PDT
Empty destructuring (aka "binding nothing") strikes again?

js> (function() { (x for ([{}, {}] in [])); })
Assertion failure: pos != 0, at jsopcode.c:2693
Comment 14 Jesse Ruderman 2007-05-13 00:13:23 PDT
js> (function() { (x for each (x in [])) = 3; })
Assertion failure: *pc == JSOP_CALL, at jsopcode.c:3708
Comment 15 Brendan Eich [:brendan] 2007-05-15 15:38:22 PDT
Jesse had a co-starring role in "Hot Fuzz" :-P.

New patch shortly.

/be
Comment 16 Brendan Eich [:brendan] 2007-05-15 19:15:26 PDT
Created attachment 264950 [details] [diff] [review]
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] 2007-05-15 19:16:44 PDT
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] 2007-05-15 19:18:23 PDT
Created attachment 264951 [details] [diff] [review]
generator expressions, v3

This is the right patch.

/be
Comment 19 Jesse Ruderman 2007-05-15 20:31:48 PDT
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 2007-05-15 20:34:21 PDT
The problem in comment 10 still exists.
Comment 21 Jesse Ruderman 2007-05-15 20:45:01 PDT
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] 2007-05-16 01:18:58 PDT
Created attachment 264975 [details] [diff] [review]
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 2007-05-16 04:02:11 PDT
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 2007-05-16 04:18:02 PDT
Created attachment 264987 [details]
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 2007-05-16 04:26:35 PDT
js> (function () { (1 for (y in (yield 3))); })
Assertion failure: expos < ss->top, at jsopcode.c:2708
Comment 26 Jesse Ruderman 2007-05-16 04:31:24 PDT
> 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 2007-05-16 10:11:00 PDT
js> (function () { delete (x for (x in [])); })
Assertion failure: *pc == JSOP_CALL, at jsopcode.c:3725
Comment 28 Jesse Ruderman 2007-05-16 10:13:11 PDT
$ ./js -v 170
js> (function() { ([yield] for (x in [])); })
Assertion failure: pos == 0, at jsopcode.c:2718
Comment 29 Brendan Eich [:brendan] 2007-05-16 10:14:08 PDT
Comment on attachment 264975 [details] [diff] [review]
generator expressions, v3a

New patch in a bit.

/be
Comment 30 Jesse Ruderman 2007-05-16 10:19:08 PDT
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] 2007-05-16 10:22:26 PDT
(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] 2007-05-16 10:39:57 PDT
(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 2007-05-16 11:04:31 PDT
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:] 2007-05-16 11:06:24 PDT
(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 2007-05-16 11:07:54 PDT
> 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 2007-05-16 12:51:23 PDT
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] 2007-05-16 15:44:15 PDT
(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 2007-05-16 15:49:33 PDT
I am taking few days off so do not count on any my r=something until Tuesday. 
Comment 39 Brendan Eich [:brendan] 2007-05-16 23:48:30 PDT
Created attachment 265097 [details]
Jesse's parenthesization test, more cases added
Comment 40 Jesse Ruderman 2007-05-17 00:42:05 PDT
Created attachment 265100 [details]
Parenthesization test, even more cases added
Comment 41 Jesse Ruderman 2007-05-17 13:54:36 PDT
Created attachment 265143 [details]
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] 2007-05-17 14:12:13 PDT
Created attachment 265147 [details] [diff] [review]
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] 2007-05-17 16:01:30 PDT
Created attachment 265167 [details] [diff] [review]
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] 2007-05-17 16:02:31 PDT
> Parenthesization is changing a big, so the testsuite will give some false

s/big/bit

/be
Comment 45 Jesse Ruderman 2007-05-17 16:28:27 PDT
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 2007-05-17 16:35:47 PDT
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] 2007-05-17 16:55:43 PDT
Created attachment 265178 [details] [diff] [review]
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] 2007-05-17 17:34:28 PDT
Created attachment 265183 [details] [diff] [review]
generator expressions, v4c

Third time's the charm.

/be
Comment 49 Brendan Eich [:brendan] 2007-05-17 17:42:27 PDT
Created attachment 265185 [details] [diff] [review]
generator expressions, v4d

I hate the newfangled get/set syntax...

/be
Comment 50 Brendan Eich [:brendan] 2007-05-17 17:52:06 PDT
Created attachment 265187 [details] [diff] [review]
my final answer

Tracking checkin for bug 381101...

/be
Comment 51 Blake Kaplan (:mrbkap) 2007-05-17 18:01:15 PDT
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] 2007-05-17 18:42:17 PDT
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 2007-05-17 19:27:32 PDT
Created attachment 265196 [details]
Parenthesization test

Added tests to ensure that generator expressions are not allowed in LHS contexts.
Comment 54 Jesse Ruderman 2007-05-17 19:39:40 PDT
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 2007-05-17 19:45:54 PDT
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 2007-05-17 19:47:13 PDT
"Comment 12" in the previous comment refers to comment 12 in *this* bug.
Comment 57 Brendan Eich [:brendan] 2007-05-17 22:29:35 PDT
(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:] 2007-05-26 09:14:22 PDT
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:] 2007-05-26 09:17:10 PDT
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] 2007-05-29 21:29:15 PDT
Created attachment 266577 [details]
sudoku.js, updated after fix for bug 366941 landed
Comment 61 Bob Clary [:bc:] 2007-05-29 22:59:08 PDT
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:] 2007-05-30 11:52:40 PDT
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 2007-05-30 12:56:35 PDT
> 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] (remove +bmo to email) 2007-05-30 14:04:33 PDT
(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] 2007-05-30 14:15:40 PDT
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] (remove +bmo to email) 2007-05-30 15:02:51 PDT
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] 2007-05-30 15:34:05 PDT
(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 2007-05-31 10:07:04 PDT
Created attachment 266768 [details]
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 2007-05-31 12:27:57 PDT
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:] 2007-05-31 12:47:17 PDT
/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] 2007-05-31 13:21:23 PDT
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 2007-06-01 12:59:08 PDT
(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 2007-06-01 13:08:22 PDT
Created attachment 266938 [details]
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] (remove +bmo to email) 2007-06-02 22:32:07 PDT
(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:] 2007-09-18 14:40:16 PDT
verified fixed 1.9.0 linux/mac*/windows.
Comment 76 Bob Clary [:bc:] 2009-03-05 18:21:02 PST
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

Note You need to log in before you can comment on or make changes to this bug.