loop unrolling and completion values in ES6

# Alan Schmitt (4 years ago)

Hello,

I've been looking into completions records in ES6, and I have a question regarding loop unrolling, as it seems completion records are dealt with differently for breaks inside loops and breaks inside blocks.

For while loops, the spec says (this is the part that applies to a "break" in the statement, as in that case LoopContinues is false):

e. Let stmt be the result of evaluating Statement. f. If LoopContinues (stmt, labelSet) is false, return Completion(stmt).

For blocks, the spec says:

StatementList : StatementList StatementListItem

  1. Let sl be the result of evaluating StatementList.
  2. ReturnIfAbrupt(sl).
  3. Let s be the result of evaluating StatementListItem.
  4. If s.[[type]] is throw, return Completion(s).
  5. If s.[[value]] is empty, let V = sl.[[value]], otherwise let V = s.[[value]].
  6. Return Completion{[[type]]: s.[[type]], [[value]]: V, [[target]]: s.[[target]]}.

The difference between the two is the following: if there is a "break" carrying the empty completion value in a while statement, then it is returned as such. For blocks, the completion value is patched with the current value (V in the algorithm above).

According to the spec, the following code has a completion value of 1 (the completion record of the while is (break,empty,a), it gets patched to (break,1,a) in the inner block, and the labeled statement return (normal, 1,empty) which is also the final completion record).

#+begin_src javascript var c; a: { c=1; while(true){ if (c) c=0; else break a; } } #+end_src

If we unroll one iteration of the loop, we get this code:

#+begin_src javascript var c; a: { c=1; if (true) { if (c) c=0; else break a; while(true){ if (c) c=0; else break a; } } } #+end_src

Now the completion record is (normal,0,empty): since the assignment "c=0" is run outside the while loop, the value 0 gets patched in the completion record, so the 1 is not patched in.

Is there a motivation for this difference of completion values between while loops and blocks?

Thanks,

Alan

# Allen Wirfs-Brock (4 years ago)

Alan,

I freed up goa couple minutes for a quick look at this. I want to spend some more time look at it deeper as this is an area where I made some fixes just a couple weeks ago and I want to review them again to make sure everything is as intended.

But, for now a quick answer to your question is: yes there is an intentional difference.

For blocks that are not part of loops (and top level StatementLists) we wanted to preserve the legacy completion values described in the NOTE at the end of 13.1.13. this requires preserving empty completion values originating from stand-alone blocks. However, we also wanted all control flow statements to always produce a non-emptry completion value.

# Alan Schmitt (4 years ago)

On 2015-04-06 02:08, Allen Wirfs-Brock <allen at wirfs-brock.com> writes:

Alan,

I freed up a couple minutes for a quick look at this. I want to spend some more time look at it deeper as this is an area where I made some fixes just a couple weeks ago and I want to review them again to make sure everything is as intended.

But, for now a quick answer to your question is: yes there is an intentional difference.

For blocks that are not part of loops (and top level StatementLists) we wanted to preserve the legacy completion values described in the NOTE at the end of 13.1.13. this requires preserving empty completion values originating from stand-alone blocks. However, we also wanted all control flow statements to always produce a non-emptry completion value.

I understand. In fact, it seems that this particular behavior did not change between ES 5 and ES 6: block evaluation guarantees the last value computed is returned, whereas loops don't. According to my tests, neither V8 nor SpiderMonkey have this behavior:

var c; a: { c = 1; while(true) { if (c) { c=0; } else { break a; } } }

returns 0 in both, whereas the spec says it should be 1 (caveat: I tested in a current Chrome and Firefox browsers, I don't know if it's the correct environment to do such tests).

Does this inconsistency matter?

Thanks,

Alan

# Allen Wirfs-Brock (4 years ago)

On Apr 7, 2015, at 10:09 AM, Alan Schmitt <alan.schmitt at polytechnique.org> wrote:

Hi Allen,

On 2015-04-06 02:08, Allen Wirfs-Brock <allen at wirfs-brock.com> writes:

Alan,

I freed up a couple minutes for a quick look at this. I want to spend some more time look at it deeper as this is an area where I made some fixes just a couple weeks ago and I want to review them again to make sure everything is as intended.

But, for now a quick answer to your question is: yes there is an intentional difference.

For blocks that are not part of loops (and top level StatementLists) we wanted to preserve the legacy completion values described in the NOTE at the end of 13.1.13. this requires preserving empty completion values originating from stand-alone blocks. However, we also wanted all control flow statements to always produce a non-emptry completion value.

I understand. In fact, it seems that this particular behavior did not change between ES 5 and ES 6: block evaluation guarantees the last value computed is returned, whereas loops don’t.

Well, they do for normal loop completions (according to the spec.) but not for breaks. I this the latter is a bug. In particular, I think it is pretty obvious that: eval(“ {0; while (true) {1; break}; 2}”) should evaluate to 1

It is a little less obvious for: eval(“{0; L: while (true) {1; while (true) {2; break L; 3}; 4}; 5}”)

but, I think that consistency with the first case requires this to evaluate to 2.

So, it’s arguably a bug that the ES6 spec. hasn’t changed in that regard relative to ES3/5. This is something that I can fix before submitting the final draft to Ecma net week.

According to my tests, neither V8 nor SpiderMonkey have this behavior:

var c; a: { c = 1; while(true) { if (c) { c=0; } else { break a; } } }

returns 0 in both, whereas the spec says it should be 1 (caveat: I tested in a current Chrome and Firefox browsers, I don't know if it's the correct environment to do such tests).

Doesn’t seem to match either ES3/5 specs or current ES6 drafts. I don’t know if this is old, non-conferment behavior or new attempts to implement “completion reform” that didn’t take the actual (evolving) ES6 spec. into account.

Does this inconsistency matter?

Probably. In ES6 we are trying to “reform” completion values so, among other things, program transformaions do have to worry too much about breaking the specified specified completions values.

# Brendan Eich (4 years ago)

Allen Wirfs-Brock wrote:

Well, they do for normal loop completions (according to the spec.) but not for breaks. I this the latter is a bug. In particular, I think it is pretty obvious that: eval(“ {0; while (true) {1; break}; 2}”)

(single quotes might avoid the smart-dumb transformation that happened here, which frustrated copy-paste into JS console :-|.)

should evaluate to 1

Why? Completion is on the 2; expression statement at the end. The break doesn't break from the block.

It is a little less obvious for: eval(“{0; L: while (true) {1; while (true) {2; break L; 3}; 4}; 5}”)

but, I think that consistency with the first case requires this to evaluate to 2.

The 3; and 4; statements are not reached, but 5; is -- again something seems wrong with these examples.

# Alan Schmitt (4 years ago)

On 2015-04-08 16:59, Allen Wirfs-Brock <allen at wirfs-brock.com> writes:

Well, they do for normal loop completions (according to the spec.) but not for breaks. I this the latter is a bug. In particular, I think it is pretty obvious that: eval(“ {0; while (true) {1; break}; 2}”) should evaluate to 1

It is a little less obvious for: eval(“{0; L: while (true) {1; while (true) {2; break L; 3}; 4}; 5}”)

but, I think that consistency with the first case requires this to evaluate to 2.

I think these cases are already fine (modulo the final expression statement, "; 2" and "; 5", which should not be there as Brendan said): since the body of the while is a block, the return value is patched as expected in the block evaluation semantics (step 5):

  1. Let sl be the result of evaluating StatementList.
  2. ReturnIfAbrupt(sl).
  3. Let s be the result of evaluating StatementListItem.
  4. If s.[[type]] is throw, return Completion(s).
  5. If s.[[value]] is empty, let V = sl.[[value]], otherwise let V = s.[[value]].
  6. Return Completion{[[type]]: s.[[type]], [[value]]: V, [[target]]: s.[[target]]}.

The problem happens when the first statement of the body of the while loop is a break: in that case the value from the previous iteration is not carried over.

So, it’s arguably a bug that the ES6 spec. hasn’t changed in that regard relative to ES3/5.

I looked deeper into the differences between ES5 and ES6, and something has partially changed, as illustrated by this example:

eval("var x=1; 12; while(true){ if (x) { x--; 42 } else { break } }")

In ES5 and in implementations this returns 42, in ES6 this returns undefined. The difference is here:

ES5 (12.6.2):

  1. Repeat a. Let exprRef be the result of evaluating Expression. b. If ToBoolean(GetValue(exprRef)) is false, return (normal, V, empty). c. Let stmt be the result of evaluating Statement. d. If stmt.value is not empty, let V = stmt.value. e. If stmt.type is not continue || stmt.target is not in the current label set, then i. If stmt.type is break and stmt.target is in the current label set, then 1. Return (normal, V, empty). ii. If stmt is an abrupt completion, return stmt.

In the example, 2.d does not apply for the second iteration of the loop (the returned value is empty), and we are in the 2.e.i.1 case (local break) so the returned value is patched in the completion statement.

ES6 (13.0.7 and 13.6.2.6)

the evaluation of the second iteration of the loop ends like this: e. Let stmt be the result of evaluating Statement. f. If LoopContinues (stmt, labelSet) is false, return Completion(stmt).

at this point we return (break, empty, empty) to the evaluation of the iteration statement, which transforms it into a (normal, undefined, empty).

The example I gave is different. Adapting it so that is resembles the previous one:

eval("var x=1; a: { 12; while(true) { if (x) { x--; 42} else { break a; } } }")

This returns 12 in both ES5 and ES6 (the 12 gets patched in because of the outer block evaluation), so the labeled statement conversion of empty to undefined does not kick in.

Does this inconsistency matter?

Probably. In ES6 we are trying to “reform” completion values so, among other things, program transformaions do have to worry too much about breaking the specified specified completions values.

We found this by looking into loop unrolling, so it would be great if completion values could propagate across loop iterations.

Best,

Alan

# Allen Wirfs-Brock (4 years ago)

On Apr 9, 2015, at 10:44 AM, Alan Schmitt <alan.schmitt at polytechnique.org> wrote:

  1. Let sl be the result of evaluating StatementList.
  2. ReturnIfAbrupt(sl).
  3. Let s be the result of evaluating StatementListItem.
  4. If s.[[type]] is throw, return Completion(s).
  5. If s.[[value]] is empty, let V = sl.[[value]], otherwise let V = s.[[value]].
  6. Return Completion{[[type]]: s.[[type]], [[value]]: V, [[target]]: s.[[target]]}.

The problem happens when the first statement of the body of the while loop is a break: in that case the value from the previous iteration is not carried over.

I agree, each kind of loop needs to do its equivalent of step 5 above before checking for exit conditions, that is the opposite of what is currently specified.

# Brendan Eich (4 years ago)

Alan Schmitt wrote:

We found this by looking into loop unrolling, so it would be great if completion values could propagate across loop iterations.

Definitely. Thanks for finding this!

# Alan Schmitt (4 years ago)

Hello,

On 2015-04-09 17:01, Allen Wirfs-Brock <allen at wirfs-brock.com> writes:

On Apr 9, 2015, at 10:44 AM, Alan Schmitt <alan.schmitt at polytechnique.org> wrote:

  1. Let sl be the result of evaluating StatementList.
  2. ReturnIfAbrupt(sl).
  3. Let s be the result of evaluating StatementListItem.
  4. If s.[[type]] is throw, return Completion(s).
  5. If s.[[value]] is empty, let V = sl.[[value]], otherwise let V = s.[[value]].
  6. Return Completion{[[type]]: s.[[type]], [[value]]: V, [[target]]: s.[[target]]}.

The problem happens when the first statement of the body of the while loop is a break: in that case the value from the previous iteration is not carried over.

I agree, each kind of loop needs to do its equivalent of step 5 above before checking for exit conditions, that is the opposite of what is currently specified.

Here is a proposal to solve this.

We define an abstract operation UpdateCompletion with two arguments, a completion and a (possibly empty) value, such as:

  1. Return UpdateCompletion(s, v).

Is a shorthand that is defined as follows:

  1. If s.[[type]] is throw or if s.[[value]] is not empty, return Completion(s).
  2. Return Completion{[[type]]:s.[[type]],[[value]]:v,[[target]]:s.[[target]]}.

We next update the spec:

  • 13.1.13: replace steps 4 to 6 with 4. Return UpdateCompletion(s,sl.[[value]]).

    This does not change the behavior.

  • 13.6.1.6: replace step 2.b with b. If LoopContinues(stmt, labelSet) is false, return UpdateCompletion(stmt,V).

    This changes the behavior: completion values from previous iterations are patched in the abrupt completion.

  • 13.6.2.6: replace step 2.f with f. If LoopContinues(stmt, labelSet) is false, return UpdateCompletion(stmt,V).

    Same change.

  • 13.6.3.8: replace step 4.c with c. If LoopContinues(result, labelSet) is false, return UpdateCompletion(result,V).

    Same change.

I'm much less confident about 13.6.4.13 (evaluation of ForIn/Of). I would replace step 5.n with: n. If LoopContinues(status,labelSet) is false then i. let status = UpdateCompletion(status,V). ii. Return IteratorClose(iterator,status).

This would ensure that if the "return" method of the iterator is undefined or if it does not throw, and if we get out of the loop through a break at the beginning of the loop body, then the last value computed is in the completion record.

Regarding Switch, I think we can make the following changes:

  • 13.11.9, both evaluations. Replace 4.b.iii with iii. If R is an abrupt completion, return UpdateCompletion(R,V).

    In the second evaluation (CaseBlock : { CaseClausesopt DefaultClause CaseClausesopt }), also replace 7.a.ii.3 with 3. If R is an abrupt completion, return UpdateCompletion(R,V). and 11 with 11. If R is an abrupt completion, return UpdateCompletion(R,V). and 12.c with c. If R is an abrupt completion, return UpdateCompletion(R,V).

This does not change the semantics, assuming that throw completion records never contain the empty value. I think it is the case:

  • 6.2.2.3 defines the generic completion for throwing exceptions, it creates an object for the value,
  • 13.13.1 is the throw statement, where the value is the result of the evaluation of the expression … this should never be empty, shouldn't it?
  • 23.1.1.1 (Map) creates an object for the value,
  • 23.3.1.1 (WeakMap) creates an object for the value,
  • 25.3.1.4 (Generator.prototype.throw) uses the exception passed as argument as value,
  • 25.4.2.1 (PromiseReactionJob) uses its argument as value.

Best,

Alan

# Allen Wirfs-Brock (4 years ago)

On Apr 10, 2015, at 3:18 AM, Alan Schmitt <alan.schmitt at polytechnique.org> wrote:

Hello,

...

Here is a proposal to solve this.

We define an abstract operation UpdateCompletion with two arguments, a completion and a (possibly empty) value, such as:

  1. Return UpdateCompletion(s, v).

Is a shorthand that is defined as follows:

  1. If s.[[type]] is throw or if s.[[value]] is not empty, return Completion(s).
  2. Return Completion{[[type]]:s.[[type]],[[value]]:v,[[target]]:s.[[target]]}.

We next update the spec:

  • 13.1.13: replace steps 4 to 6 with
  1. Return UpdateCompletion(s,sl.[[value]]).

This does not change the behavior.

  • 13.6.1.6: replace step 2.b with b. If LoopContinues(stmt, labelSet) is false, return UpdateCompletion(stmt,V).

This changes the behavior: completion values from previous iterations are patched in the abrupt completion.

  • 13.6.2.6: replace step 2.f with f. If LoopContinues(stmt, labelSet) is false, return UpdateCompletion(stmt,V).

Same change.

  • 13.6.3.8: replace step 4.c with c. If LoopContinues(result, labelSet) is false, return UpdateCompletion(result,V).

Same change.

yes, that all looks good

I'm much less confident about 13.6.4.13 (evaluation of ForIn/Of). I would replace step 5.n with: n. If LoopContinues(status,labelSet) is false then i. let status = UpdateCompletion(status,V). ii. Return IteratorClose(iterator,status).

yes, although I’ll probably make it

k. Let result be the result of evaluating stmt. l. Set the running execution context … m. If LoopContinues(result,labelSet) is false, return IteratorClose(iterator,UpdateCompletion(result, V) n. If result.[[value]] is not empty, let V = result.[[value]].

so that if follow the same pattern as the other loops.

This would ensure that if the "return" method of the iterator is undefined or if it does not throw, and if we get out of the loop through a break at the beginning of the loop body, then the last value computed is in the completion record.

Regarding Switch, I think we can make the following changes:

  • 13.11.9, both evaluations. Replace 4.b.iii with iii. If R is an abrupt completion, return UpdateCompletion(R,V).

yes

In the second evaluation (CaseBlock : { CaseClausesopt DefaultClause CaseClausesopt }), also replace 7.a.ii.3 with 3. If R is an abrupt completion, return UpdateCompletion(R,V). and 11 with 11. If R is an abrupt completion, return UpdateCompletion(R,V). and 12.c with c. If R is an abrupt completion, return UpdateCompletion(R,V).

yes, again

This does not change the semantics, assuming that throw completion records never contain the empty value. I think it is the case:

yes, I probably should assert that somewhere. But I probably won’t worry about that addition for the ES6 test.

And thanks for bringing up the loop unrolling perspective. It really helps clarify the desired semantics for these cases.

# Alan Schmitt (4 years ago)

On 2015-04-10 17:13, Allen Wirfs-Brock <allen at wirfs-brock.com> writes:

I'm much less confident about 13.6.4.13 (evaluation of ForIn/Of).
I would replace step 5.n with:
n. If LoopContinues(status,labelSet) is false then
i. let status = UpdateCompletion(status,V).
ii. Return IteratorClose(iterator,status).

yes, although I’ll probably make it

k. Let result be the result of evaluating stmt. l. Set the running execution context … m. If LoopContinues(result,labelSet) is false, return IteratorClose (iterator,UpdateCompletion(result, V) n. If result.[[value]] is not empty, let V = result.[[value]].

so that if follow the same pattern as the other loops.

Sure.

And thanks for bringing up the loop unrolling perspective. It really helps clarify the desired semantics for these cases.

The credit should go to Marek Materzok, a postdoc here who found the issue while working on proving the desugaring of while loops to λJS (if you're curious about what he is doing, his development is here: tilk/LambdaCert).

Best,

Alan