Is there a formal basis for generators?

I have been programming in Python for a while and have been using generators as part of the language. However, I have recently found myself wanting to formally reason about a recursive generator function. Is there any formal basis for generators and is there any infomation on the subject on the web?

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.


There are slight differences between generators, semi-coroutines, and coroutines but you might find more Googling for coroutines.

I've not actually read this:
A Calculus of Coroutines

A Unifying Approach to Goal-Directed Evaluation

You can give a semantics of generators in terms of a backtracking monad. The following paper gives four different semantics for a tiny subset of Icon, and then compiles using type-directed partial evaluation.

A Unifying Approach to Goal-Directed Evaluation

Olivier Danvy, Bernd Grobauer, and Morten Rhiger.

Abstract: Goal-directed evaluation, as embodied in Icon and Snobol, is built on the notions of backtracking and of generating successive results, and therefore it has always been something of a challenge to specify and implement. In this article, we address this challenge using computational monads and partial evaluation....

Interruptible Iterators

I think Interruptible Iterators by Jed Liu, Aaron Kimball and Andrew C. Myers (POPL '06) makes for an interesting read in this context. From the abstract:

Interruptible iterators are more powerful coroutines in which the loop body is able to interrupt the iterator with requests to perform updates. Interrupts are similar to exceptions, but propagate differently and have resumption semantics. Interruptible iterators have been implemented as part of the JMatch programming language, an extended version of Java.

(Their paper includes an appendix with a formalisation of interruptible iterators.)