Generators originated as an API for traversing linked data structures. By mid-1970s, they were connected to backtracking (generally, non-determinism) and modular on-demand processing; and by the end of 1970s, recognized as the most general control construct in programming languages. Also recognized by the end of 1970s was the simple version of generators: less expressive but strikingly elementary to implement, with no special run-time.
Perhaps the very variety of generators, and the breadth of their connections to streams, coroutines, traversals, enumeration, iteration, and non-determinism needed some time to sink in. To help grasp this, here we look onto the whole terrain of generators -- from traversal to non-determinism -- from the lookout of pull streams (for general generators) and push streams (for simple ones).
Generators were fully worked out, along with their theory, in the language Alphard developed in the the group of Mary Shaw at CMU in mid-1970s. In 1975 generators, under the name of iterators, migrated to the language CLU. Both Alphard and CLU stressed data abstraction. Generators were viewed as an API to provide efficient access to a collection without exposing the implementation. Alphard in particular was aimed at the development of verifiably reliable software. Abstraction was indispensable in making (Hoare-style) proofs simpler and modular. Since iterative computations invariably loop over the elements of some collection (be it as simple as the range of integers), it made sense to separate operations on the current element (the loop body) from obtaining the current element (the loop control). The goal was to hide the details of the collection, encapsulate the state of the enumeration, and make iterative computations modular and easier to prove terminating and correct. As Shaw et al. wrote, generators abstract over control as functions abstract over operations.
About two years later, generators as the one and only control structure appeared in the programming language Icon. As its predecessor SL5, Icon is a non-deterministic programming language with goal-directed evaluation. A generator in Icon is an expression that may (fail to) produce several values on demand. The expression's context determines the demand. Again we see the separation between obtaining (candidate) values and consuming the values, possibly demanding more. Generator hides the details of generating the candidates and encapsulates the generation state. It represents the traversal of a virtual collection whose elements are computed during the enumeration as needed.
However different Alphard and Icon are, they both have a for-loop,
implemented in terms of the generator producing integers from i
through j on demand -- called upto(i,j) in Alphard and i to j in
Icon.
Generators also appeared in many AI languages of early 1970s such as SAIL, CONNIVER, QLISP/INTRELISP, POPLER -- alongside backtracking, co-routines and other control facilities. Icon stands out in the systematic use of generators as the fundamental control structure, on which backtracking and other control facilities are built.
I thank Richard O'Keefe for pointing out early AI languages.
A warning about terminology: `generator' is sometimes called `iterator' (e.g., in CLU); its semantics and expressivity, whether it is push or pull (see below) vary with the programming language (or, in case of Python, for example, with the version of Python).
Allen Newell and Fred M. Tonge.
An Introduction to Information Processing Language V.
Communications of the ACM, v3, N4, 1960, pp. 205-211
Allen Newell, Ed.
IPL-V Programmers Reference Manual. RAND Corporation, 1963
Mary Shaw, William A. Wulf and Ralph L. London.
Abstraction and verification in Alphard:
defining and specifying iteration and generators.
Communications of the ACM, v20, N8, pp. 553-564. August 1977
Barbara Liskov. A History of CLU.
MIT LCS Technical Report 561. April l992. Section 3.10. Iterators.
Ralph E. Griswold. An Overview of the Icon Programming Language; Version 9. March 2, 1996. Section 2.2. Generators. <http://www.cs.arizona.edu/icon/docs/ipd266.htm>
Daniel G. Bobrow and Bertram Raphael.
New Programming languages for AI research.
Xerox Palo Alto Research Center Report CSL-73-2. August 20, 1973
<http://www.bitsavers.org/pdf/xerox/parc/techReports/CSL-73-2_New_Programming_Languages_For_AI_Research.pdf>
yield and for syntaxes are discussed in
for-yield interface.
Push generator is `active', traversing the collection itself and
invoking a user-supplied function, the `visitor', on each encountered
element. In contrast, pull generator supplies the next element (or
reports its absence) only when asked. Whereas push generator
encapsulates the traversal loop, with pull generator, it is the
programmer that has to write the loop, pulling the generator
repeatedly. As we shall see, yield/for-loop interface so often
associated with generators is implementable with either push or pull
generators.
for-each function in Scheme, or
iter functions in OCaml:
val List.iter : ('a -> unit) -> 'a list -> unit
val Array.iter : ('a -> unit) -> 'a array -> unit
(the iter functions also exist for sequences Seq, strings, sets,
and all other OCaml collections.)
The push generator therefore has the type (where 'a is the type of
the elements)
type 'a push_gen = ('a -> unit) -> unit
All collections (in OCaml, and similarly for many other languages)
already provide an operation of that type. One may also write
one's own generators for newly introduced collections, or for what may be
thought of as collections. For example, the generator upto lo hi to
enumerate the range of integers from lo to hi inclusively.
let upto (lo:int) (hi:int) : int push_gen = fun visitor ->
for i = lo to hi do visitor i done
The generator enumerates the range without materializing it, that is,
in constant memory. It indeed contains a loop. Here is an usage example,
borrowed from an old manual: enumerating the range and
printing the squares of each element.
upto 1 5 (fun i -> Printf.printf "%d squared is %d\n" i (i*i))Does it remind you of something?
A more interesting example (also borrowed from the same old manual, and used in many tutorials since) is traversing a binary tree, with values in nodes.
type label = int
type tree = Leaf | Node of label * tree * tree
The code is most straightforward: in fact, it is the very specification for
inorder traversal:
let rec inorder (t:tree) : label push_gen = fun visitor ->
match t with
| Leaf -> ()
| Node (label, left, right) ->
inorder left visitor;
visitor label;
inorder right visitor
To visit a tree, we visit the left branch, the node value, and the
right branch, in the desired order.
As should be clear from its type 'a -> unit, the visitor function is
invoked solely for its side-effect. A clear illustration is an accumulator,
which accumulates or aggregates the traversed elements. For example,
the following
function collects all elements in a list (useful for
writing tests, among others).
let to_list (g:'a push_gen) : 'a list =
let l = ref [] in
g (fun i -> l := i :: !l); List.rev !l
A notable advantage of generators is the ease of combining/adjusting existing generators to obtain new ones: generators easily compose. One may write a whole library of operations on generators. For example,
let map : ('a -> 'b) -> 'a push_gen -> 'b push_gen = fun f g -> fun visitor ->
g (f >> visitor)
let filter (pred:('a -> bool)) (g:'a push_gen) : 'a push_gen = fun visitor ->
g (fun i -> if pred i then visitor i)
let append (g1:'a push_gen) (g2:'a push_gen) : 'a push_gen = fun visitor ->
g1 visitor; g2 visitor
let cartesian (g1:'a push_gen) (g2:'b push_gen) : ('a*'b) push_gen =
fun visitor ->
g1 (fun i -> g2 (fun j -> visitor (i,j)))
Here, >> is the left-to-right function composition. The code for
append could not be any clearer. The operation cartesian
illustrates nesting: nested loops. All this code shows the
constant-space processing. There are no intermediate variable-size
data structures such as lists: the current element is handled
immediately, rather then stashed away for later processing. This is
the so-called `fusion', which is automatic with generators.
Since a push generator itself drives the enumeration, early termination requires some sort of a feedback from a visitor to the traversing loop -- or, in the simplest case, a non-local exit, such as exceptions or goto, etc. For example, the following function obtains the first element from the collection, if any. (Alphard, in 1977, already had such a language construct.)
let first_opt : type a. a push_gen -> a option = fun g ->
let exception Found of a in
match g (fun i -> raise (Found i)) with
| exception Found x -> Some x
| _ -> None
The operation take n (restricting the traversal to the first n
elements) is similar; it is a bit tricky to implement (left as an exercise).
Here is a sample test:
let [1;2;4] =
upto 1 10 |> filter (fun x -> x mod 3 <> 0) |> take 3 |> to_list
where |> is the pipeline operator in OCaml: the function
application when the argument is on the left. To confirm that the
range enumeration indeed terminates early, let's insert into the
pipeline the printing of each element as it is originally emitted.
let [1;2;4] =
upto 1 10 |> map (fun i -> Printf.printf "emitted %d\n" i; i) |>
filter (fun x -> x mod 3 <> 0) |> take 3 |> to_list
The final, interesting example (inspired by the Icon tutorial) is checking
if two collections have an element in common (and returning it, if any).
let common (g1:'a push_gen) (g2:'a push_gen) : 'a option =
cartesian g1 g2 |> filter (fun (x,y) -> x = y) |> map fst |> first_opt
let (Some 4) = common (upto 4 10) (inorder tree1)
This is the so-called nested loop join (not the most optimal way to
join collections, for sure, but good for an example). As before,
we may easily confirm that the traversal of both collections terminates as
soon as the common element is found.
The operation on push generators that we cannot (easily) implement
is zip: see the discussion below.
As seen already from the push generator type (and from all the code), push generator is a higher-order function: it takes a visitor function as argument. Therefore, the programming language has to have some support for passing functions as arguments. However, the full first-class function support (including returning functions or assigning to mutable variables) is not required. Non-escaping closures or downward-passing of functions, like procedure passing in old Algol68 or lambda-abstractions in modern C++, suffice. Therefore, push generators do not require any special run-time, heap allocation or any GC. They can be compiled for the single standard stack, and implemented even in C (as we discuss later).
Push generators execute their visitor function solely for its side-effect rather than for its value; the visitor is not even expected to return any value. The generator likewise returns nothing. One may easily imagine generalizations: letting the visitor return a value, and aggregate it, e.g., in some monoid; or threading an explicit state through the visitor, returning the final state. The latter variation is typically called `left fold'. For example, for Arrays:
val Array.fold_left : ('acc -> 'a -> 'acc) -> 'acc -> 'a array -> 'acc
next,
to advance the traversal, returning true if the enumeration
has not yet finished and hence the current property is valid.
What we just described is the generator of the programming language
from 1970s (Alphard) -- which also happens to be
the IEnumerator interface from the contemporary .NET.
(Alphard's generators are valid as soon as successfully
constructed, whereas for
.NET enumerators one first has to call next, spelled MoveNext.)
Alphard's generators also included pre- and
post-conditions and invariants, for the sake of loop verification.
Pull generators should also remind one of
the FILE i/o in C: a FILE handler with the basic operations
feof and fgetc. Or of the output state machine:
next being the transition function.
In a language with option types, the pull generator interface may be
reduced to a single method, call it read, which returns the current
element, if any, and advances the traversal, if possible. Formally,
the generator interface is described by the signature
module type pull_gen_imperative = sig
type e (* element type *)
type h (* type of the generator: `handle' *)
val h : h (* The handle itself *)
val read : h -> e option
end
More convenient, for OCaml, is the equivalent but non-destructive interface:
rather than modifying the handle, the read method returns, along
with the element, the new handle value, representing the next state of
the traversal
module type pull_gen = sig
type e
type h
val h : h
val read : h -> (e * h) option
end
type 'a pull_gen = (module pull_gen with type e = 'a)
We also define the type 'a pull_gen to refer to the
interface's implementation.
The pull generator upto lo hi, enumerating the range of integers
from lo to hi inclusively, takes the following form:
let upto (lo:int) (hi:int) : int pull_gen =
(module struct
type e = int
type h = int
let h = lo
let read i = if i <= hi then Some (i, i+1) else None
end)
which is almost the same as the code in the Alphard paper introducing
the generators (modulo very large differences in syntax).
The example of printing the squares for a range of integers now has to include a loop: unlike push generator, which runs itself, pull generator has to be repeatedly polled, or pulled.
let module M = (val upto 1 5) in
let rec loop h = match M.read h with
| None -> ()
| Some (i,h) ->
Printf.printf "%d squared is %d\n" i (i*i);
loop h
in loop M.h
Writing such a loop all the time is a chore; it is worth,
therefore, defining an operation for the full traversal with a
pull generator:
let every : type a. a pull_gen -> (a -> unit) -> unit = fun (module M) ->
fun visitor ->
let rec loop h = match M.read h with
| None -> ()
| Some (i,h) -> visitor i; loop h
in loop M.h
The type should look familiar; in fact, it can be written as
val every : 'a pull_gen -> 'a push_genThe operation
every is hence a constructive proof that every pull
generator can be converted to a push one.
The second running example, the inorder traversal of a binary tree, looks as follows with the pull generator:
let rec inorder (tree:tree) : label pull_gen =
(module struct
type e = label
type frame = V of label | T of tree
type h = frame list
let h = [T tree]
let rec read : frame list -> (label * frame list) option = function
| [] -> None
| T Leaf :: t -> read t
| V i :: t -> Some (i,t)
| T (Node (i, left, right)) :: t ->
T left :: V i :: T right :: t |> read
end)
One might argue that the code is also clear (after reading
through it several times); that there is more code is inarguable.
Pull generators, like push ones, also compose; one may likewise build libraries of pull generator combinators, for example:
let map : type a b. (a -> b) -> a pull_gen -> b pull_gen =
fun f (module M) ->
(module struct
include M
type e = b
let read h = match M.read h with Some (i,h) -> Some (f i,h) | _ -> None
end)
let append : type a. a pull_gen -> a pull_gen -> a pull_gen =
fun (module M1) (module M2) ->
(module struct
type e = a
type h = (M1.h, M2.h) Either.t
open Either
let h = Left M1.h
let rec read = function
| Left h1 -> begin match M1.read h1 with
| Some (i,h1) -> Some (i, Left h1)
| None -> read (Right M2.h)
end
| Right h2 -> begin match M2.read h2 with
| Some (i,h2) -> Some (i, Right h2)
| None -> None
end
end)
The fusion is also automatic.
The comparison with the push generator combinators is telling,
especially for append. (Although cartesian is also implementable
in principle, managing the state of two generators is so ungainly to
even contemplate. It is left as a challenge to a courageous reader.)
Early termination with pull generators is simple: when we are done, we just stop pulling. (Freeing resources is a separate question, however.)
let first_opt : type a. a pull_gen -> a option = fun (module M) ->
M.read M.h |> Option.map fst
The operation take is also straightforward and no longer tricky,
although unwieldy.
What pull generators can do, in contrast to push generators, is parallel loops, or zip: traversing two collections side-by-side.
let zip : type a b. a pull_gen -> b pull_gen -> (a*b) pull_gen =
fun (module M1) (module M2) ->
(module struct
type e = a*b
type h = M1.h * M2.h
let h = (M1.h,M2.h)
let read (h1,h2) = match (M1.read h1, M2.read h2) with
| (Some (i1,h1), Some (i2,h2)) -> Some ((i1,i2),(h1,h2))
| _ -> None
end)
We can now determine when two collections first differ, in their
traversal order: the variant of the famous same-margin problem.
Early termination is quite simpler with pull generators. Both generators support nesting, but only pull generators support zipping, or side-by-side enumerating of several collections, with the constant per-element processing cost.
A pull generator requires some notion of a `handle', or object -- the value representing the state of the traversal. It is passed around in the user code, and is meant to be used linearly -- but most programming languages have no mechanism to enforce this. A handle may remain reachable (alive) for a long time, and so its resources. Resource leaks is a persistent problem with pull generators. Push generator does all the traversal itself, from the beginning, allocating resources, to the end, freeing them. The life time of resources is predictable.
Although we have not talked about it, push generators are related to fold and F-algebras, and pull -- to unfold and F-coalgebra.
Every pull generator can be converted to push generator, as we have
already seen: every. The other way around is tricky:
one generally needs some sort of suspension (coroutine, delimited
control, which requires a run-time support). A
sufficiently general and polymorphic push generator can be converted
to pull without delimited control and run-time support; however,
space and time performance per element is no longer be constant.
strymonas.pdf [614K]
POPL2017 paper, Sec. 3.
Explanation of push vs. pull stream processing
Mary Shaw, William A. Wulf and Ralph L. London.
Abstraction and verification in Alphard:
defining and specifying iteration and generators.
Communications of the ACM, v20, N8, pp. 553-564. August 1977
How to zip folds: A library of fold transformers
Iteratee: Incremental multi-level input processing and collection enumeration
generators.ml [17K]
The complete OCaml code
Recall the push generator: it takes a visitor function and applies it to
each traversed element in turn. The example, repeated below,
uses the upto lo hi generator to enumerate a range of integers; the visitor
prints out the integer and its square.
upto 1 5 @@ fun i ->
Printf.printf "%d squared is %d\n" i (i*i)
Let's contrast it with the ordinary for-loop:
for i = 1 to 5 do
Printf.printf "%d squared is %d\n" i (i*i)
done
The two pieces of `syntax sugar'
let for_ = Fun.id
let (let-) = Fun.id
(the latter is a so-called binding operator) lets us write the
example as
for_ begin let- i = upto 1 5 in
Printf.printf "%d squared is %d\n" i (i*i)
end
This is not a mere resemblance of the for-loop. A for-loop is an application (pun intended) of a generator. Being able to write a for loop as an application of a generator was exactly the reason modern generators were introduced, in Alphard. With enumeration encapsulated as generators, loops become modular: easier to write, and, for Alphard, easier to formally reason about. That the old familiar for-loop notation so elegantly extends to arbitrary traversals must have been very appealing to CLU developers. That's why they made generators (renamed iterators) and the accompanying for-loop notation the only iteration construct in their language. (According to Liskov, the main appealing feature of generators was the encapsulation of the traversal without exposing the implementation of the collection. Abstraction was the selling point of CLU.)
Generators in Alphard are pull; in CLU push. The for-loop notation
works with either. When we write our example with pull generators,
for_ is not the identity function but every (which is the
pull-push converter).
As a bit more interesting example of the for-notation, let's re-implement finding the common element of two collections. In Push generator, the example was written in the combinator style, repeated below:
let cartesian (g1:'a push_gen) (g2:'b push_gen) : ('a*'b) push_gen =
fun visitor ->
g1 (fun i -> g2 (fun j -> visitor (i,j)))
let common (g1:'a push_gen) (g2:'a push_gen) : 'a option =
cartesian g1 g2 |> filter (fun (x,y) -> x = y) |> map fst |> first_opt
In the for-notation, the code looks as
let common (g1:'a push_gen) (g2:'a push_gen) : 'a option =
with_break @@ fun break ->
for_ begin let- i = g1 in
for_ begin let- j = g2 in
if i = j then break i
end
end
where with_break encapsulates a non-local exit (via a local exception).
Terminating generators with a non-local exit also first appeared in CLU.
Incidentally, Alphard introduced not only the general for-loop in
terms of generators, but also a so-called first loop, to find the
first element in the traversal satisfying a given condition. This
construct is prominent in theory of recursive functions. Hardly
any language offers it, however, as syntax.
Yield has become the most recognizable sign of generators. It has
been with generators almost from the very beginning. Alphard did not
have yield. One had to write generators as an explicit state machine,
as we did in Pull generator. When CLU borrowed generators, it
simplified them from pull to push and, for the first time, introduced yield
to help write them. The inspiration came from
Simula 67 coroutines. (Icon has a similar form, called suspend,
borrowed from SL5, also inspired by Simula's coroutines.) CLU has
showed that yield can be efficiently compiled, as an ordinary function
call. (In Liskov's recollection, a CLU developer, Russ Atkinson, did all this
on a plane ride from Pittsburgh to Boston after visiting Mary Shaw's
group at CMU and learning about generators.)
With time, generators, symbolized by yield, spread to other
languages. Python has generators and the keyword yield since version
2.2. The following example is quoted from David Mertz's Charming
Python article, as an elegant, exemplary generator.
>>>> # A recursive generator that generates Tree leaves in in-order.
>>> def inorder(t):
... if t:
... for x in inorder(t.left):
... yield x
... yield t.label
... for x in inorder(t.right):
... yield x
The talk about coroutines and suspensions may make yield sound like
magic: something that requires special compiler support and special
run-time. Let's recall, however, our inorder generator in plain
OCaml from Push generator, and rename the variable visitor
(inserting some identity sugar):
let rec inorder (t:tree) : label push_gen = fun yield ->
match t with
| Leaf -> ()
| Node (label, left, right) ->
for_ begin let- x = inorder left in
yield x end;
yield label;
for_ begin let- x = inorder right in
yield x end
I believe no comments are needed.
As another illustration of the convenience of yield in building and
composing generators, let's define commons to return all elements in
common in two collections, represented by generators, g1 and g2.
let commons (g1:'a push_gen) (g2:'a push_gen) : 'a push_gen = fun yield ->
for_ begin let- i = g1 in
for_ begin let- j = g2 in
if i = j then yield i
end
end
David Mertz.
Charming Python: Iterators and simple generators.
Autodidact, Gnosis Software, Inc. September 2001
Barbara Liskov. A History of CLU.
MIT LCS Technical Report 561. April l992. Section 3.10. Iterators.
generators.ml [17K]
The complete OCaml code