Note: There are a few cases of duplicates in user autocompletion which are being worked on.
Bug 380237 (genexp)

Implement generator expressions for JS1.8

VERIFIED FIXED in mozilla1.9alpha5

Status

()

Core
JavaScript Engine
P1
normal
VERIFIED FIXED
10 years ago
8 years ago

People

(Reporter: brendan, Assigned: brendan)

Tracking

Trunk
mozilla1.9alpha5
Points:
---
Dependency tree / graph
Bug Flags:
in-testsuite +

Firefox Tracking Flags

(Not tracked)

Details

(URL)

Attachments

(5 attachments, 18 obsolete attachments)

98.46 KB, patch
mrbkap
: review+
Details | Diff | Splinter Review
6.45 KB, text/javascript
Details
5.09 KB, text/plain
Details
9.69 KB, text/plain
Details
7.96 KB, text/plain
Details
(Assignee)

Description

10 years ago
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
Attachment #264310 - Flags: review?(igor)
(Assignee)

Updated

10 years ago
Status: NEW → ASSIGNED
Priority: -- → P1
(Assignee)

Comment 1

10 years ago
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
(Assignee)

Comment 2

10 years ago
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
Attachment #264310 - Attachment is obsolete: true
Attachment #264331 - Flags: review?(igor)
Attachment #264310 - Flags: review?(igor)
(Assignee)

Comment 3

10 years ago
Created attachment 264332 [details]
sudoku.js, more array comprehension removal via genexps
Attachment #264311 - Attachment is obsolete: true
(Assignee)

Comment 4

10 years ago
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
Attachment #264331 - Attachment is obsolete: true
Attachment #264446 - Flags: review?(igor)
Attachment #264331 - Flags: review?(igor)

Comment 5

10 years ago
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.
(Assignee)

Comment 6

10 years ago
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
Attachment #264446 - Flags: review?(igor)
(Assignee)

Comment 7

10 years ago
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
Attachment #264446 - Attachment is obsolete: true
Attachment #264585 - Flags: review?(igor)

Comment 8

10 years ago
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.
Attachment #264585 - Flags: review?(igor) → review+

Comment 9

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

Comment 10

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

Needs parens.  Same with |yield|.

Comment 11

10 years ago
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

10 years ago
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

10 years ago
Empty destructuring (aka "binding nothing") strikes again?

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

Comment 14

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

Comment 15

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

New patch shortly.

/be
(Assignee)

Comment 16

10 years ago
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
Attachment #264585 - Attachment is obsolete: true
Attachment #264950 - Flags: review?(igor)
(Assignee)

Comment 17

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

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

/be
Attachment #264950 - Flags: review?(mrbkap)
(Assignee)

Comment 18

10 years ago
Created attachment 264951 [details] [diff] [review]
generator expressions, v3

This is the right patch.

/be
Attachment #264950 - Attachment is obsolete: true
Attachment #264951 - Flags: review?(igor)
Attachment #264950 - Flags: review?(mrbkap)
Attachment #264950 - Flags: review?(igor)
(Assignee)

Updated

10 years ago
Attachment #264951 - Flags: review?(mrbkap)

Comment 19

10 years ago
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

10 years ago
The problem in comment 10 still exists.

Comment 21

10 years ago
Simple loops crash!?

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

Comment 22

10 years ago
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
Attachment #264951 - Attachment is obsolete: true
Attachment #264975 - Flags: review?(igor)
Attachment #264951 - Flags: review?(mrbkap)
Attachment #264951 - Flags: review?(igor)
(Assignee)

Updated

10 years ago
Attachment #264975 - Flags: review?(mrbkap)

Comment 23

10 years ago
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

10 years ago
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

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

Comment 26

10 years ago
> 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

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

Comment 28

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

Comment 29

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

New patch in a bit.

/be
Attachment #264975 - Attachment is obsolete: true
Attachment #264975 - Flags: review?(mrbkap)
Attachment #264975 - Flags: review?(igor)

Comment 30

10 years ago
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: [...]
(Assignee)

Comment 31

10 years ago
(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

(Assignee)

Comment 32

10 years ago
(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

10 years ago
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

10 years ago
(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

10 years ago
> 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

10 years ago
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: [...]

(Assignee)

Comment 37

10 years ago
(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

10 years ago
I am taking few days off so do not count on any my r=something until Tuesday. 
(Assignee)

Comment 39

10 years ago
Created attachment 265097 [details]
Jesse's parenthesization test, more cases added
Attachment #264987 - Attachment is obsolete: true

Comment 40

10 years ago
Created attachment 265100 [details]
Parenthesization test, even more cases added
Attachment #265097 - Attachment is obsolete: true

Updated

10 years ago
Flags: in-testsuite?

Comment 41

10 years ago
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.
Attachment #265100 - Attachment is obsolete: true
(Assignee)

Comment 42

10 years ago
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
Attachment #265147 - Flags: review?(mrbkap)
(Assignee)

Comment 43

10 years ago
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
Attachment #265147 - Attachment is obsolete: true
Attachment #265167 - Flags: review?(mrbkap)
Attachment #265147 - Flags: review?(mrbkap)
(Assignee)

Comment 44

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

s/big/bit

/be

Updated

10 years ago
Attachment #265167 - Flags: review?(mrbkap) → review+

Comment 45

10 years ago
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

10 years ago
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
(Assignee)

Comment 47

10 years ago
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
Attachment #265167 - Attachment is obsolete: true
(Assignee)

Updated

10 years ago
Attachment #265178 - Flags: review?(mrbkap)
(Assignee)

Comment 48

10 years ago
Created attachment 265183 [details] [diff] [review]
generator expressions, v4c

Third time's the charm.

/be
Attachment #265178 - Attachment is obsolete: true
Attachment #265183 - Flags: review?(mrbkap)
Attachment #265178 - Flags: review?(mrbkap)
(Assignee)

Comment 49

10 years ago
Created attachment 265185 [details] [diff] [review]
generator expressions, v4d

I hate the newfangled get/set syntax...

/be
Attachment #265183 - Attachment is obsolete: true
Attachment #265185 - Flags: review?(mrbkap)
Attachment #265183 - Flags: review?(mrbkap)
(Assignee)

Comment 50

10 years ago
Created attachment 265187 [details] [diff] [review]
my final answer

Tracking checkin for bug 381101...

/be
Attachment #265185 - Attachment is obsolete: true
Attachment #265187 - Flags: review?(mrbkap)
Attachment #265185 - Flags: review?(mrbkap)
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.
Attachment #265187 - Flags: review?(mrbkap) → review+
(Assignee)

Comment 52

10 years ago
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
Status: ASSIGNED → RESOLVED
Last Resolved: 10 years ago
Resolution: --- → FIXED

Comment 53

10 years ago
Created attachment 265196 [details]
Parenthesization test

Added tests to ensure that generator expressions are not allowed in LHS contexts.
Attachment #265143 - Attachment is obsolete: true

Comment 54

10 years ago
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

10 years ago
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

10 years ago
"Comment 12" in the previous comment refers to comment 12 in *this* bug.
(Assignee)

Comment 57

10 years ago
(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

10 years ago
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 [ ] ) ) ; }

Flags: in-testsuite? → in-testsuite+

Comment 59

10 years ago
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
(Assignee)

Updated

10 years ago
Depends on: 382355
(Assignee)

Comment 60

10 years ago
Created attachment 266577 [details]
sudoku.js, updated after fix for bug 366941 landed
Attachment #264332 - Attachment is obsolete: true

Comment 61

10 years ago
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

10 years ago
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

10 years ago
> 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.
(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.
(Assignee)

Comment 65

10 years ago
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
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.
(Assignee)

Comment 67

10 years ago
(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

10 years ago
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

10 years ago
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

10 years ago
/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.
(Assignee)

Comment 71

10 years ago
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

Updated

10 years ago
Depends on: 382673

Comment 72

10 years ago
(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

10 years ago
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.
(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

10 years ago
verified fixed 1.9.0 linux/mac*/windows.
Status: RESOLVED → VERIFIED

Comment 76

9 years ago
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

Updated

8 years ago
Depends on: 486713
You need to log in before you can comment on or make changes to this bug.