1
$\begingroup$

Never have I heard of a partially executed function before. But it seems the idea of it has been out for some time. Does a generator really stop execution at the machine code level, and that next time when the iterator is invoked, then there is a jump back to that machine code location to continue the execution?

Or is it done by having some private variables and states to control what to return? Is stopping execution of machine code and resuming to that location possible?

It seems quite strange, as

  1. it differ from mathematics for what a function is. (in math, there is no partially executed function).
  2. the traditional function will add to the stack, and once finished, everything is popped from the stack. But the generator is like a function that stays... so nothing is popped from the stack. So does it use something other than the stack for memory? (the heap?)

Example: JavaScript ES6 Generator:

function* generator() {    // note the asterisk
    yield 1;
    yield 3;
    yield 5;
}

const iterator = generator();

console.log(iterator.next());
console.log(iterator.next());
console.log(iterator.next());
console.log(iterator.next());

result:

{value: 1, done: false}
{value: 3, done: false}
{value: 5, done: false}
{value: undefined, done: true}

Example 2: a generator that can give an infinite number of changing color names:

function* generator() {
    const colors = ["red", "green", "blue"];
    let   i = 0;
    while (true) {
        yield colors[i];
        i = (i + 1) % colors.length;
    }
}

const iterator = generator();

console.log(iterator.next());
console.log(iterator.next());
console.log(iterator.next());
console.log(iterator.next());

result:

{ value: 'red', done: false }
{ value: 'green', done: false }
{ value: 'blue', done: false }
{ value: 'red', done: false }
  ...
$\endgroup$
1
$\begingroup$

It depends on the language implementation, but most do it by packaging the local variables of the generator function, together with the instruction pointer from where the last yield occurred, into a heap-allocated closure object. This is what is inside the opaque "generator object" that represents the stream of values in the language. The heap variables representing the saved instruction pointer and generator function locals are updated in place whenever the generator function yields, and reloaded to resume execution of the generator function whenever the next value is demanded from the generator.

It is important to remember that, when you get down to the machine code level, the computer has no concept of a "stack" and a "heap". Those are abstractions added by programming langauge runtime environments on top of the fundamental concepts of contiguous RAM and goto.

Generators are another feature that language runtimes can implement on top of these basic primitives. So the literal answer to the question "Does a generator really stop execution at the machine code level, and that next time when the iterator is invoked, then there is a jump back to that machine code location to continue the execution?" is yes, absolutely.

Generators are an instance of a more general concept called continuations and the call/cc operator. A continuation is often implemented as literally the state of the stack and instruction pointer packaged into a heap-allocated object.

Note that most programming language specifications allow the implementation total latitude as to how memory management works as long as the semantics of the language are conformed to. This is important for the implementation of lazy functional languages, which generalize the generator concept so that all data structures and subexpressions are generated lazily by default. These languages often have implementations that barely resemble the C locals+malloc model. Check out Simon Peyton Jones's books on the implementation of functional programming languages and the Spineless Tagless G-machine for more info. 1 2 3

$\endgroup$
  • $\begingroup$ so some implementation of generators actually can be partially executed functions (as it appears to be, a function that finish only partly), while some actually faked it by having a function that completely finished running but just having "states" to manage what it would return? (I tried the first example in Babel or Traceur and they are like so). $\endgroup$ – nonopolarity Dec 21 '19 at 2:29
  • $\begingroup$ @nopole Babel is "faking" it in the sense that it has to transpile generators into a language that has no continuation mechanism or direct control over the instruction pointer. But if you look at what the CPU ends up doing, it is effectively the same, just with a bit more overhead because it has to look up where to jump to in a switch-case rather than jumping to the saved instruction pointer directly. $\endgroup$ – Aaron Rotenberg Dec 21 '19 at 3:31
  • $\begingroup$ @nopole Do you know any CPU assembly languages, or are you planning to learn any? It is much easier to understand what is going on with all these layers of abstraction once you have implemented language features in terms of machine instructions yourself before. (In particular, the entire concept of functions only exists at the language level, not at the machine level.) $\endgroup$ – Aaron Rotenberg Dec 21 '19 at 3:37
  • $\begingroup$ now, if the JavaScript interpreter actually has a separate execution mechanism that process the generator calls, won't that work? That is, if JavaScript or any language had no such "stop execution" mechanism, then it has to be faked. But if the interpreter has it built in to the interpreter, then it should be possible. I used to know 6502 and some Z80 and IBM 360 machine code. $\endgroup$ – nonopolarity Dec 21 '19 at 5:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.