Stackless Python and Python 2.x

[Tim Peters]

[Michael Abbott]
> How does the Python interpreter maintain the state of a generator during
> calls to yield?  Evidently the entire state has to be restored from
> wherever it's being kept and plonked back onto the current stack.
>
> Perhaps this is a slightly stupid question, but it's more
> interesting than  the other "What part of ... do you not understand?"
> stuff.

Oh, I don't know about *that* <wink>, but it's a not a stupid question at
all.  The implementation is simple but subtle.

Here's the C struct that holds a generator (strictly speaking, a
generator-iterator):

typedef struct {
	PyObject_HEAD
	/* The gi_ prefix is intended to remind of generator-iterator. */

	PyFrameObject *gi_frame;

	/* True if generator is being executed. */
	int gi_running;
} genobject;

"PyObject_HEAD" is a macro with which every Python object declaration
begins -- it expands to a pointer to the type object, and to a refcount.

Other than that, it simply stores a pointer to a frame object, and a 1-bit
flag saying whether the generator is currently active.  That's all there is
to it!  The frame object is ordinary in every respect, containing stuff like
the current set of locals, a virtual instruction pointer, and an evaluation
stack (each Python code object computes, at compile-time, exactly how much
stack space it needs, and space for its stack is allocated in the frame
object when the code object is executed).

The point of all that was to convince you that reading the Python source
code can be an enjoyable adventure:  much of it is frighteningly clear and
simple, and Neil Schemenauer's generator implemenation is particularly
clean.

As Aahz said, at a high level the only other trick in this game is that a
generator-iterator simply refrains from decrementing the refcount on its
gi_frame when a generator yields.  That's all it takes to keep the frame
alive.  The frame stays alive until the generator-iterator itself becomes
trash, at which point its gi_frame gets decref'ed as a matter of course in
the generator's destructor, the full source code for which is here:

static void
gen_dealloc(genobject *gen)
{
	PyObject_GC_Fini(gen);
	Py_DECREF(gen->gi_frame);
	PyObject_Del(gen);
}

Dince generators can be part of reference cycles (although it's not
particularly easy to provoke that), the PyObject_GC_Fini business is telling
the cycle collector that this object is no longer interesting.

[Aahz]
> ...
> The part I don't understand (though if I had access to 2.2a2, I could
> probably test it easily enough) is what happens when you re-enter a
> generator and trigger an exception (an exception that isn't
> StopIteration, for any smartasses out there).

Nothing special:  the exception is caught by the frame or not, and if not
propagates out of the frame.  Generators do nothing special at all here, and
since they always return to their immediate invoker, there are no debatable
issues about *which* frame *to* propagate an uncaught exception (general
coroutines are muddier in this respect, and general continuations even
worse).

There is one "slick trick" here in support of generators:  near the start of
eval_frame(), you'll find this:

	stack_pointer = f->f_stacktop;
	assert(stack_pointer != NULL);
	f->f_stacktop = NULL;

where f is the PyFrameObject being eval'ed, and f->f_stacktop is the current
top of the frame's eval stack.  Note that if nothing sets f->f_stacktop
non-NULL again, it would be an assert-error to enter eval_frame() with this
f again.

Now in all of eval_frame(), there is only one way to get f_stacktop non-NULL
again, and that's in the body of the YIELD opcode:

		case YIELD_VALUE:
			retval = POP();
			f->f_stacktop = stack_pointer;
			f->f_lasti = INSTR_OFFSET();
			why = WHY_YIELD;
			break;

Any other way of leaving the frame (exception or return) leaves f_stacktop
NULL, in turn making the frame unresumable.  That's how the .next() method
of a generator-iterator knows whether eval_frame yielded or returned:

static PyObject *
gen_iternext(genobject *gen)
{
...
	gen->gi_running = 1;
	result = eval_frame(f);
	gen->gi_running = 0;

...
	/* If the generator just returned (as opposed to yielding), signal
	 * that the generator is exhausted. */
	if (result == Py_None && f->f_stacktop == NULL) {
		Py_DECREF(result);
		result = NULL;
	}

	return result;
}

there's-so-little-to-it-it's-amazing-it-works-at-all<wink>-ly y'rs  - tim