execution context suspension and resumption

I have questions Spec Reading
1

Hello and thanks in advance for your help.
So, I am writing an executable semantics of ES2021. For a bit of context, this formalization aims to be a formal copy of the specification. We have decided to take almost no implementation choices. Exceptions are the data structures for the state, and all its components(Objects, ExecutionContexts, EnvironmentRecords, etc..). By the way, now I am working on function expressions and function calls.
A practical example is:

 let id = function (v) {return v;};
 id("ciao")

The example is trivial, but its interpretation is not.
My problems start in FunctionDeclarationInstantiation and precisely in steps 24,25 and 26.

Let's start with step 24 and the createListIteratorRecord method call with the list ["ciao"], corresponding
to the arguments list. At this point, we are still in the callee execution context created by the ordinary function [[Call]]. Here basically we create a GeneratorObject and the return is an iterator record, with the generator object as iterator and %Generator.prototype.next% as next method.

Question 1:
After creating this object, we perform GeneratorStart. Step 4 of GeneratorStart defines a closure to assign to the callee execution context. Does this imply that the execution context is suspended in that step?

However, once we return the iterator record and so the control flow to FunctionDeclarationInstantiation,
it is time to bind the names in the context to a value. Indeed, steps 25 and 26 deal with this, depending on the presence of duplicated names.
IteratorBindingInitialization deals with it. And here I have problems(We consider the syntactic production that matches with SingleNameBinding). This method takes a parse node, an iterator record, and - in the example case - an environment, and returns an updated state, in which the environment is updated with the bindings for each of the names that live within the context of the called function.

Morally, what makes things awkward is the IteratorStep call! At a certain point, through IteratorNext, we call %Generator.prototype.next% using the Built-In Function [[Call]. At this point, a new context is created and pushed into the stack. The callee context was already suspended by GeneratorStart. Then, the algorithmic steps of %Generator.prototype.next% are executed. This method calls GeneratorResume with this value(the generator object created in CreateListIteratorRecord, and a value, that happens to be the aforementioned object.
This method, after some steps, suspends the running execution context(The new one created by the built-in function [[Call]]), pushes into the stack the callee context(We have a context duplication in the stack), and then it is resumed. Its resumption executes the closure defined in step 4 of GeneratorStart.
In the first steps of the resumption closure, another closure is executed, The one defined in CreateListIteratorRecord. Yield is executed for each of the arguments list.

Question 2:
The definition of Suspension and resumption is not defined precisely. Indeed, here things break, and I am quite sure that it is not an implementation dependant error. As a reminder, we are visually close to the specification, so it is difficult to make mistakes. We have a doubt, that can maybe solve our dilemmas. Basically, the Yield loop is executed all at once, regardless of the context suspensions/resumptions.
We then return the result and the control to the abstract closure in GeneratorStart.

- Does a suspension imply implicitly a sort of continuation(CPS)?
- In case a closure is not given, does a resumption make the context resume in the same algorithmic step in which it was suspended? Or it simply changes its CodeEvaluationState?

Here things really break, because, at the top of the execution context stack, we get the wrong contexts at the top of the stack, and this makes the binding initialization break.

I think that a nice proposal is to detail more what happens in context switches.

Thanks in advance!

P.S. I tried to detail as much as possible, but a lot of things are left out. If not, the thread would have been really confusing.

2

did you mean function* (v) {return v;}, so it's a generator?

3

@ljharb: I believe the GeneratorStart referred to is not the one in EvaluateGeneratorBody, but the one in CreateIteratorFromClosure, which is called from CreateListIteratorRecord, which is called from FunctionDeclarationInstantiation.

1 Like
4

Let me do my best to answer here. I'm not totally confident in this.

After creating this object, we perform GeneratorStart. Step 4 of GeneratorStart defines a closure to assign to the callee execution context. Does this imply that the execution context is suspended in that step?

I believe the idea is that execution contexts are suspended whenever they are removed from execution context stack. It would probably be best to be explicit about this.

I don't think GeneratorStart should be understood to suspend the execution of the running execution context. Rather, it is implicitly suspended when it is removed from the execution context stack. With a syntactic generator (as opposed to one created by CreateIteratorFromClosure), the execution context in question would be the one created in step 3 of [[Call]] on ordinary function objects, which is removed immediately after the call to GeneratorStart: step 7 of [[Call]]: OrdinaryCallEvaluateBody calls EvaluateBody calls EvaluateGeneratorBody, the last nontrivial step of which is GeneratorStart; step 8 of [[Call]] pops the execution context stack. So it should be understood to be suspended at that point.

That said, there are places where we explicitly suspend execution contexts before removing them from the stack. If my interpretation is correct, we should change the spec to be consistent here, and consistently suspend execution contexts before removing them.

Morally, what makes things awkward is the IteratorStep call! At a certain point, through IteratorNext, we call %Generator.prototype.next% using the Built-In Function [[Call]. At this point, a new context is created and pushed into the stack. The callee context was already suspended by GeneratorStart.

I believe this is a bug in CreateIteratorFromClosure, which was introduced in PR 2045. Specifically, I believe it needs to push a new execution context to the execution context stack before calling GeneratorStart, and pop it after.

I've submitted a pull request implementing this fix.

Basically, the Yield loop is executed all at once, regardless of the context suspensions/resumptions.

I'm not sure what this means.

Does a suspension imply implicitly a sort of continuation(CPS)?

Yes.

In case a closure is not given, does a resumption make the context resume in the same algorithmic step in which it was suspended? Or it simply changes its CodeEvaluationState?

Do you have an example in mind where this comes up? My understanding is that it resumes at the point it says to resume: so when an algorithm step says "Resume context", and context has not explicitly had its code evaluation state set, it means that execution proceeds at the "Resume context" step.

1 Like
5

I think one part of the confusion comes from the lack of distinction between code and meta-code. Code is typically the JavaScript that is being executed, while meta-code is an algorithmic description of how to execute it (i.e., the spec). Code can be manipulated, interrupted, and resumed, whereas meta-code cannot (at least I hope so, otherwise we’ll need meta-meda-code to handle it).

The part that is troubling in when code is written in spec style. For instance, the abstract closure created as part of step 1 of CreateListIteratorRecord should be code, as it uses yield, hence one should be able to interrupt its execution.

Things are less clear for the steps created in step 4 of GeneratorStart. As steps 4.a or 4.b can evaluate things that call yield, the whole series of steps may be suspended. Is this code or meta-code?

Finally, what is the status of built-in methods? For instance %GeneratorFunction.prototype.prototype.next% is defined to be [[NextMethod]] of the object returned by CreateListIteratorRecord, which is called (as a code function) from IteratorNext. Can it be interrupted?

To sum up, as our formalization is purely functional, we need to distinguish between code (which is plain data for us) from meta-code (which we implement as an interpreter). Does this distinction makes sense at the spec level?

6

Thanks for the answer!

So, what happens when a context is only explicitly suspended? It does stay at the top of the stack, right?
i.e. Step 6 of GeneratorResume.

It's true that after step 6 we add GenContext to the stack and resume it. Indeed, after step 9, the execution context has changed again, because of what the abstract closure did, right. So basically, when MethodContext is resumed, the computation continues sequentially from the point in which it was resumed? Having no resumption abstract closure assigned to this context, the code just continues to execute in a new state in which MethodContext is resumed and it's at the top of the stack.

Oh yes, here I was not that clear. Indeed, when we call generatorBody() in step 4b of the closure defined in GeneratorStart, we execute the piece of code defined in step 1 of CreateListIteratorRecord.
Imagine we have a non-trivial list, so one that has more than one element. What I meant for executed all at once is that, when we call Yield, there is a call to GeneratorYield. GeneratorYield manipulates the stack, and at the end, the MethodContext is again at the top of the stack. is there any manipulation of the control flow or we just get back to the loop that has called Yield, and do another iteration, if it is not finished?

This is the part in where Alan and I thought that a possible explanation for having a weird resulting context stack is that implicitly the code resumes somewhere else, and the loop is not executed sequentially.

But I guess that your last answer satisfies my doubt, and in that case the is no continuation. The control flow just continues sequentially, right?

Another peculiar thing is that, before the step 4.d. of the GeneratorStart closure, the execution stack is:
[MethodContext;GenContext; whatever..].
After performing 4.d. the stack is [GenContext; ...]. and actually, that's is due to a repetition of GenContext in the stack, and a missing push/pop somewhere. Actually, after 4.d. I would have expected to have a stack with MethodContext at the top, ready to be removed once we return the control to the built-in function [[Call]].

@AlanSchmitt post integrates my original post

7

To make things more precise, I would like to propose a concrete example.

Assume we are running step 1.a.i of CreateListIteratorRecord. It calls Yield, which calls GeneratorYield that removes in step 7 the current execution context. What I’m trying to understand is the point where we switch from interpreted code (which I assume to be the list of calls to Yield) to interpreter execution (which is not associated to any execution context and cannot be suspended).

One way to clarify this is to say that step 1 of CreateListIteratorRecord creates a concrete representation of steps to be interpreted (and not an abstract closure). Then CreateIteratorFromClosure takes as argument such a concrete list of steps, and GeneratorStart says to interpret this list of steps in 4.b.ii. Interpreting means considering the first step, changing the state of the execution context to store the remaining steps, and calling the corresponding specification abstract algorithm.

8

[AlanSchmitt] AlanSchmitt https://es.discourse.group/u/alanschmitt
April 29

I think one part of the confusion comes from the lack of distinction between
code and meta-code. Code is typically the JavaScript that is being executed,
while meta-code is an algorithmic description of how to execute it (i.e.,
the spec).

I think there's a good distinction. Anything algorithmic in the spec that
isn't clearly an example of ECMAScript code (in monospace font) is
'meta-code' (which we generally call 'pseudo-code'). The JavaScript that is
being executed is represented as parse trees (resulting from invocations of
ParseText).

You may wish to distinguish between abstract operations (or bits of
pseudo-code) that can be suspended/resumed, and those that can't. Currently,
the spec doesn't help you much with making that distinction, but it's
conceivably a piece of metadata that could be attached to each abstract
operation in the future. But note that that distinction is not the
distinction between JavaScript code and an algorithmic description of how to
execute it. (At least, not in the spec's world.)

Code can be manipulated, interrupted, and resumed, whereas
meta-code cannot (at least I hope so, otherwise we’ll need meta-meda-code to
handle it).

Meta-code can indeed be suspended and resumed.

The part that is troubling in when code is written in spec style. For
instance, the abstract closure created as part of step 1 of
CreateListIteratorRecord
https://tc39.es/ecma262/#sec-createlistiteratorRecord should be code, as
it uses |yield|, hence one should be able to interrupt its execution.

It uses Yield (note the capital Y), which is an abstract operation, and
not the ECMAScript yield keyword. And Abstract Closures are definitely
'meta' structures.

Things are less clear for the steps created in step 4 of GeneratorStart
https://tc39.es/ecma262/#sec-generatorstart. As steps 4.a or 4.b can
evaluate things that call |yield|, the whole series of steps may be
suspended. Is this code or meta-code?

It's meta-code. The fact that 4.a.i can (at some point) evaluate a
YieldExpression doesn't change that.

Finally, what is the status of built-in methods? For instance

%GeneratorFunction.prototype.prototype.next%| is defined to be
[[NextMethod]]| of the object

(Record, not object)

returned by CreateListIteratorRecord, which is called (as
a code function) from IteratorNext.

IteratorNext invokes the Call abstract operation, passing it the value
of some iterator record's [[NextMethod]] field. When that value is
%GeneratorFunction.prototype.prototype.next%, that results in the
invocation of that built-in function's [[Call]] internal method.

Implementations are allowed to implement the next function via ECMAScript
code, but they're not obliged to. So there isn't necessarily something being
called "as a code function" here.

Can it be interrupted?

When you invoke the next function's [[Call]] internal method, it will
invoke the GeneratorResume abstract op, which will typically cause a
suspension of the current execution context and the resumption of another.
(I would hesitate to call this "interrupted".)

To sum up, as our formalization is purely functional, we need to distinguish
between code (which is plain data for us) from meta-code (which we implement
as an interpreter). Does this distinction makes sense at the spec level?

I'd say that distinction as stated makes sense to the spec. However, it
sounds like you have additional ideas about that distinction that may not
fit well with how the spec sees it.

-Michael

9

Yes, although I think this is a distinction without a difference: as far as I am aware, every time the spec suspends an execution context, it immediately thereafter causes said context to not be at the top of the stack, either by popping the newly suspended context or by pushing a new context on top of it.

Right.

Oh, yeah, like I said I think the weird execution context stack resulting from CreateIteratorFromClosure is just a bug. If you use the definition for CreateIteratorFromClosure given in this PR, does it make sense?

Right, I think that's the same bug as above.

10

Thank you Michael for these clarification. From an implementation point of view, it seems that abstract algorithms that can be suspended and abstract algorithms that cannot be suspended are quite different and need to be implemented differently.

For instance, I’m curious to see how CreateListIteratorRecord is implemented, as step 1.a.i can be suspended, but I suspect step 3 cannot.

11

[AlanSchmitt] AlanSchmitt

From an implementation point of view, it seems that abstract algorithms
that can be suspended and abstract algorithms that cannot be suspended
are quite different and need to be implemented differently.

I imagine that would depend on the language of your implementation.

For instance, I’m curious to see how CreateListIteratorRecord is
implemented,

Well, there's certainly no shortage of implementations whose source you can
examine. But note that the specification of CreateListIteratorRecord (and a
bunch of other operations) changed ~4 months ago when PR #2045 was merged,
so most implementations (if they have an identifiable
CreateListIteratorRecord chunk) will be based on the older form. For
instance, that's the case with engine262, which follows the spec pretty closely:

as step 1.a.i can be suspended, but I suspect step 3 cannot.

Executing step 1.a.1 will lead to a suspension, yes, but note that step 1
merely creates an Abstract Closure, doesn't execute it.

Step 3 doesn't invoke any other operations, so executing it can't involve a
suspension.

So the execution of CreateListIteratorRecord itself will not be suspended,
but it returns a Record that will likely be the cause of future suspensions.

-Michael

12

Thank you for the link to engine262, this will be most helpful. Unfortunately they implement code that can be suspended with asynchronous functions. Their implementation of GeneratorStart is quite interesting, as it makes explicit the part of the code that is part of an execution context and the part that is not.

13

Thinking about this some more, I believe that every place the spec has a sequence of steps along the lines of

  1. Let oldCtx be the running execution context.
  2. Let ctx be a new execution context.
  3. Push ctx onto the execution context stack; ctx is now the running execution context.
  4. Do some stuff.
  5. Remove ctx from the execution context stack and restore oldCtx as the running execution context.

you can think of it as being instead

  1. Let oldCtx be the running execution context.
  2. Let ctx be a new execution context.
  3. Set the code evaluation state of ctx such that when it becomes the running execution context the following steps will be performed:
    1. Do some stuff.
    2. Remove ctx from the execution context stack and restore oldCtx as the running execution context.
  4. Push ctx onto the execution context stack; ctx is now the running execution context.
  5. Assert: When we reach this step, ctx has already been removed from the execution context stack and oldCtx is the currently running execution context.

Generators differ from this only in that

  • the push and corresponding pop of the execution context are not so closely linked as in the above (there is a push which happens in GeneratorResume and its corresponding pop is in GeneratorStart step 4.d or GeneratorYield step 7), and
  • the code evaluation state is set some time previously to its becoming the running execution context (in particular, the code evaluation state of the relevant context is set in GeneratorStart or GeneratorYield, and it only becomes the running execution context when GeneratorResume is next called).

Edit: I guess there is another difference, which is that the execution contexts for generators can return values to the thing which pushed them to the stack. Specifically, step 9 of GeneratorResume has "Let result be the value returned by the resumed computation", which corresponds to the Returns in steps 4.i.ii and 4.j of GeneratorStart and step 9 of GeneratorYield. It would probably be best to rephrase these so they don't use "Return"; perhaps something like

"Remove genContext from the execution context stack and restore the execution context that is at the top of the execution context stack as the running execution context using NormalCompletion(iterNextObj) as the returned value."

14

[bakkot]

  1. Set the code evaluation state of /ctx/ such that when it becomes the
    running execution context the following steps will be performed:

The spec doesn't use that formulation though. It's always:
... such that when evaluation is resumed [for that execution context] ...

I.e., simply pushing a context onto the stack doesn't trigger anything else; you have to explicitly "resume" such a context for it to start doing its stuff.

So I think this equivalence would be more in line with how the spec is currently written:

  1. ...
  2. ...
  3. Set the code evaluation state of /ctx/ such that when evaluation is resumed for that execution context, the following steps will be performed:
    1. Do some stuff.
    2. Remove /ctx/ from the execution context stack and restore /oldCtx/ as the running execution context.
  4. Push /ctx/ onto the execution context stack; /ctx/ is now the running execution context.
  5. Resume the evaluation of /ctx/.
  6. Assert: When we reach this step, /ctx/ has already been removed from the execution context stack and /oldCtx/ is the currently running execution context.

Specifically, step 9 of GeneratorResume has "Let /result/ be the value returned by the resumed computation", which corresponds to the Returns in steps 4.i.ii and 4.j of GeneratorStart and step 9 of GeneratorYield. It would probably be best to rephrase these so they don't use "Return"; perhaps something like

"Remove genContext from the execution context stack and restore the execution context that is at the top of the execution context stack as the running execution context using NormalCompletion(iterNextObj) as the returned value."

That would conflate a stack-pop with a transfer of control, which I don't think the spec currently does.

I can sort of see your point about not using the term "Return" in these steps, but I think just a different word would help.

15

That would conflate a stack-pop with a transfer of control, which I don't think the spec currently does.

It doesn't, but I think it would be clearer if it did; as far as I can tell there's no reason to separate the two.

Given that generators are implemented in a way which suggests that the execution context stack represents control, it is very strange that we manipulate what's on the execution context stack without transferring control. For example, I think without the NOTE which is step 10 of GeneratorYield it would not be at all clear what step 9 was supposed to do.

16

I’m troubled by this because we would have an algorithmic step that is part of the code evaluation state of an execution context remove its own execution context.

17

As long as it's the last step, that seems fine to me. Necessary, even: there needs to be some way of indicating that control should be transferred back to the previous execution context. It's just like return in any programming language: return is part of a function, and its effect is to complete execution of the function and remove it from the stack.

In any case, don't we already do this, for example in GeneratorYield step 7?

18

So all the places in the spec where they are separated, those can be converted to the "conflated" model?

One possibility might be: in some cases, they have to be separated, but for others, we introduce an abstract operation that bundles them together. So for the most part, you can think of them as conflated.

If these two views are at odds, perhaps the strangeness goes the other way.

(Lately I've been wondering if having 'code evaluation state' as a component of execution contexts might be the problem.)

I agree that there's a problem with GeneratorYield; I've been working on an issue/PR about it.

19

Almost. I can't quite make it work for PrepareForTailCall, with the way things are wired up: you really want a tail call to replace top of the execution context stack with the context of the new function, but the current logic is that a tail call does PrepareForTailCall which pops the stack, and then does F.[[Call]], and for ECMAScript functions and non-exotic built-in functions the implementation of [[Call]] pushes a new context as its first step.

(And it's not clear what to do with InitializeHostDefinedRealm, which is inherently weird.)

Sidebar:

There's an odd interaction with tail calls and Proxies: the [[Call]] slot for a Proxy will throw a TypeError if the Proxy has been revoked, and the above implies that if you tail-call a revoked Proxy the Realm for that TypeError should be that of the function which called the function which called the Proxy (since its execution context will be the top of the stack), which seems wrong.

Neither JSC nor engine262, the engines which implement tail calls I can most easily test, implements this behavior. [actually, turns out engine262 does not implement tail calls]

Edit: turns out there's tests for a similar case, though those tests recently became incorrect.

20

I don’t think so, because this is interpreter code: I do not think these abstract steps would be associated to the code evaluation state of genContext.

(I’m sorry I’m struggling so much with terminology… I’m trying to find words that distinguish between steps associated to executions contexts and steps that are not.)