Iterators: the Next Iteration

Roman E. Maeder, Wolfram Research

(RowDefault[, (Spacer1), , (Spacer1), ])  #WolframTechConf

ABSTRACT

Iterators are a generalization of lists that are accessed one element at a time.
Iterators allow to work with data whose length is infinite or unknown, and they avoid the explicit generation of all elements at the same time, by using incremental generators.

First presented a year ago, this project has now matured, and I would like to share some of the improvements made, focusing on programming techniques for paclet design, and seamless integration of iterators into the Wolfram Language

20221019

Iterators

An iterator is a way to present the elements of a possibly very long list one at a time.

Many operations on lists work with the elements one at a time:

Map, Select

including most listable functions

MemberQ

which may consume the whole iterator in case of a negative answer

The main algorithmic challenge is to find incremental generators, for example, for binary trees.

There are at least two different ways to implement iterators:

Immutable

also called lazy lists, which I presented back in 1994 (The Mathematica Programmer)

Mutable

an iterator is an object with internal state that changes every time a new element is requested

There are related concepts such as

Out of core data, which is read only as needed

Sow and Reap, which build results as they are found

CloudExpression, where the computation is done on the server where the data resides

Coroutines, which allow a process to pause after each result it produced

Outline of Presentation

The minimum requirements for mutable iterators

A framework for implementing iterator factories

Operations on iterators

Seamless integration into Wolfram Language

All code is in a paclet, soon available in the Wolfram Language Paclet Repository.

I’d like to thank Leonid Shifrin for discussions of concepts and syntax details,
and Tom Wickham-Jones for help with the compiler.

A Minimal Interface, Take 2

An iterator is a thing that supports one function: give the next element.

In this tutorial example we use a unique symbol to represent the iterator, and another symbol to hold the mutable value.

We essentially hand-craft an iterator that runs through the positive integers.

Needs["Iterators`Interface`"]

iter=Module[{next=0,ints},
ints[]:=++next;
ints/:IteratorQ[ints]=True;
ints
]

The next element method is implemented as a function call operator:

iter[]

iter[]

Table[iter[],10]

The IteratorQ predicate serves as a type declaration.
We do not have a single OO hierarchy, so cannot use patterns.

IteratorQ[iter]

IteratorQ[junk]

I keep the interface as simple as possible:

The next element function call operator

EndOfIterator exception to indicate that we fell off the end

the IteratorQ predicate

But not:

No “peek” method

No EmptyQ predicate

No set/reset methods

All other methods are optional, but most implementations will provide some of them

Size, the number of elements remaining

Constructor, a (held) constructor for a copy of an iterator

Clone, an independent copy of an iterator

A Simple Iterator Factory

This examples shows some of the optional methods.
It uses the same representation, but packages the setup into a factory method, so we can easily make several iterators as needed.

makeRange[i0_Integer:1,i1:(_Integer|Infinity),Optional[di_Integer?Positive,1]]:=
With[{range=Unique["range"]},
Module[{i=i0-di}, (* value before first step *)
range[]:=(i+=di;If[i<=i1,i,RaiseEndOfIterator[]]); (* next value *)
range/:Size[range]:=Max[Floor[(i1-i)/di],0]; (* length *)
range/:IteratorQ[range]=True; (* predicate *)
range
]]

makeRange takes the same arguments as Range, but the upper bound can be infinity:

odds=makeRange[1,Infinity,2]

Size[odds]

odds[]

odds[]

Lisp-Like Lists, but mutable

Here is yet another way to implement a simple iterator.
This implementation represents iterators as normal expressions containing a held variable with the instance data.

mList[l_List]:=Module[{rest=l},mList[Hold[rest]]];

mList[Hold[rest_]][]:=If[rest==={},RaiseEndOfIterator[],With[{e=First[rest]},rest=Rest[rest];e]];
mList/:Size[mList[Hold[rest_]]]:=Length[rest];
mList/:Constructor[mList[Hold[rest_]]]:=With[{rest=rest},Hold[mList[rest]]];
mList/:IteratorQ[mList[Hold[rest_]]]:=ListQ[rest];
Format[HoldPattern[mList[Hold[rest_]]/;ListQ[rest]],StandardForm]:=HoldForm[mList[…]]

The Constructor method should return a suitable constructor call, wrapped in Hold.

list=mList[{a,b,c,d}]

list[]

Constructor[list]

ReleaseHold[%]

list2=Clone[list]

Table[list[],Size[list]]

Table[list2[],Size[list2]]

Support for Optional Methods

The code in Iterators`Interface` provides tools to make it easy to provide those optional methods.
This support includes error handling code and generic implementations of methods.

IteratorQ[_]:=False;

Size[iter_?IteratorQ]:=Indeterminate

Clone[self_?IteratorQ]:=ReleaseHold@Constructor[self]

Constructor[self_?IteratorQ]:=RaiseIteratorConstructor[self]

RaiseIteratorConstructor[___]:=ConfirmAssert[False,"Iterator has no constructor",tagConstructor]

This is all we needed for the examples above.

Generic Operations

Most functions on iterators that do not return another iterator can be programmed generically, using interface functions only.

We added implementations of those functions to the interface.

Here are some examples. First the error handling macros:

EncloseIterator[code_,handler_:($Failed&)]:=Enclose[code,handler,tagEndOfIterator]

RaiseEndOfIterator[]:=ConfirmAssert[False,"no more elements",tagEndOfIterator]

Now, the code:

itFirst[iter_?IteratorQ]:=EncloseIterator[
iter[],IteratorFailure["EmptyIterator","Iterator `1` has no elements.",iter]&
]

itRest[iter_?IteratorQ]:=EncloseIterator[
iter[];iter,IteratorFailure["EmptyIterator","Cannot take Rest of empty iterator `1`.",iter]&
]

itLast[iter_?IteratorQ]:=Module[{e=noValue},
EncloseIterator[While[True,e=iter[]]];(*run to the very end*)If[e===noValue,RaiseEndOfIterator[],e]
]

itNormal[iter_?IteratorQ]:=First[Reap[EncloseIterator[While[True,Sow[iter[]]]]][[2]],{}]

itMemberQ[iter_?IteratorQ,e_]:=EncloseIterator[While[!MatchQ[iter[],e],Nothing];True,False&]

Sample Use

odds=makeRange[1,Infinity,2]

itFirst[odds]

itRest[odds]

odds[]

itPart[odds,5]

itTake[odds,10]

itMemberQ[odds,99]

itMemberQ[makeRange[1,Infinity,2],100]

itNormal[mList[{a,b,c}]]

itScan[Print,mList[{a,b,c}]]

itFold[f,0,mList[{a,b,c}]]

Iterator Classes Revisited

Common Support Code

Even the ad-hoc iterator factories shown before consist of a lot of housekeeping code, that sets up the object and default methods.

We need to figure this out only once, and can implement a framework for providing this common code.

We represent an iterator as a normal expression, with the instance variables in held form inside, plus some housekeeping data.

The result is a function DeclareIterator[] that makes iterator declarations look like class declarations.

If you are brave enough, you can look at the code of DeclareIterator, which is in Iterators/Kernel/Class.wl

The Range Example Revisited

Needs["Iterators`Interface`"]
Needs["Iterators`Class`"]

DeclareIterator[myRange, {s,next,max,d},{
myRange[imin_:1,imax_,di_:1]:=
(s=Sign[di];next=imin;max=s*imax;d=di),
_myRange[]:=If[s*next<=max,With[{res=next},next+=d;res],RaiseEndOfIterator[]],
Size[_myRange]:=If[IntegerQ[max]&&d=!=0,Internal`GetIteratorLength[{i,next,max,s*d},range],Infinity]
}];

The declaration consists of these parts:

The name of the new iterator class, which is used as constructor and data type

The list of instance variables

The list of method definitions, including

the constructor

the next element function operator

optional methods, such as Size (more on these below)

negatives=myRange[-1,-Infinity,-1]

Size[negatives]

Table[negatives[],10]

IteratorQ[negatives]

The Constructor Definitions

Each constructor definition must have one of two forms

myRange[i0_]:=myRange[i0,Infinity]

which calls the same constructor again, useful for providing default arguments, or

myRange[imin_:1,imax_,di_:1]:=
	(s=Sign[di]; next=imin; max=s*imax; d=di)

which initializes the instance variables (which can be specified with their declared names).

Everything else, the creation of the object and definition of the methods for it, is handled behind the scenes.

InputForm[negatives]

The Method Definitions

A method looks like a function with the object as first argument (self).
The pattern for this first argument must have one of these two forms:

Size[_myRange]:=…

Size[self_myRange]:=…

This looks like it matches any expression with head myRange, but it is actually rewritten to match only valid objects, and sets up the instance variables as pattern variables, so you can use them on the RHS.
It also sets up the definitions as Upvalues.
There is a lot of trickery going on; it is not easy to write rules for rewriting rules.

Functions on Iterators

This section gives examples of programming with iterators.

Functions that consume the input iterator and return a single result

We already looked at those, which are part of the interface

Functions that work incrementally and return a result iterator

The Most Important Function: Map

Map applies a function to each element of an iterator, and returns the iterator of results.
So it is itself an iterator class.

Needs["Iterators`Interface`"]
Needs["Iterators`Class`"]

DeclareIterator[myMap,{ff,elems},{
myMap[f_,it_?IteratorQ]:=(ff=f;elems=it),
_myMap[]:=ff[elems[]],
Size[_myMap]:=Size[elems],
Constructor[_myMap]:=ConstructHeld[myMap,ff,CloneHeld[elems]]
}]

Note the particularly simple (non-)handling of the EndOfIterator exception. The end of the inner iterator is also the end of the mapped one, so we simply let the exception propagate.

Needs["Iterators`Library`"]

ints=iRange[Infinity]

squares=myMap[#^2&,ints]

Table[squares[],10]

Size[squares]

Beware:

ints[]

So, the argument iterator is consumed! Time to clone!

Serialization and Cloning

Consuming an argument iterator is fine, if it is a fresh one:

squares=myMap[#^2&,iRange[Infinity]]

… but otherwise we might want to clone the iterator

ints=iRange[Infinity]
squares=myMap[#^2&,Clone[ints]]

Table[squares[],10]

ints[]

To make an iterator cloneable, you need to define the Constructor method, which must return a held constructor for a copy of the iterator.

Constructor[ints]

And here is the clone:

ReleaseHold[%]

This is also useful for serializing iterators, or sending them to parallel subkernels.

The Constructor method of myMap needs to clone the input iterator of the mapped one, but delayed.
This is what the auxiliary functions CloneHeld and ConstructHeld are for.

Compiled Iterators

Compiling an iterator declaration, in particular, the next element method

Using compiled data structures as sources for iterators

Iterators are data types, and we can use the compiler support for such data types.
The internal state is then kept in an opaque blob.
The code in DeclareIterator needs to create the blob, and translate the API.

Here is a simple example, which uses one of the existing data types, “Counter”
(writing a new data structure is outside the scope of this presentation).

DeclareIterator[cCounter,{ds},{
cCounter[i_Integer:1]:=( ds=CreateDataStructure["Counter",i] ),
_cCounter[]:=ds["Increment"],
Size[_cCounter]:=Infinity,
Constructor[_cCounter]:=ConstructHeld[cCounter,ds["Get"]]
}]

ct=cCounter[42]

ct[]

ct[]

Size[ct]

Clone[ct]

Seamless Integration

We could now go through all WL functions and see which ones can be made to work with iterators.

Map, Select, FoldList

Prepend, Append

Element extraction, such as Part, First, Last, Take

usually cannot support negative indices

Table, Do

MemberQ, FreeQ

accumulators, such as Scan, Fold, Total, Max

And we can go through all functions that generate lists and see which ones are suitable as iterator constructors

Range, ConstantArray, NestList

Combinatorial Generators (Groupings, permutations, …)

ReadList, …

RandomReal, RandomInteger

List, Data Structures

However: do we really need to define an iName for every Name?

Let’s integrate iterators seamlessly:

Use existing function names for the constructors

Range, NestList, List, RandomReal, ...

Make existing functions accept iterators in place of ordinary lists

Map, Select, First, Last, Part, ...

This is surprisingly easy. The code is in Iterators/Kernel/Integration.wl

IteratorObject

We define a data type that wraps raw iterators.
We can then set up upvalues for all system functions that can accept iterators in place of lists.

ints=IteratorObject[iRange[Infinity]]

Length[ints]

The supported set includes most listable functions:

ints^2+1

Take[%,10]

primes=Select[ints,PrimeQ]

Take[primes,10]

Note that the wrapped iterator need not be one set up with DeclareIterator.
Anything that implements the minimal interface should work.

A Look at the Code

The wrapper accepts only valid iterators.

IteratorObject[junk_,___]/;!IteratorQ[junk]:=(Message[IteratorObject::inv,junk];
Failure["InvalidIteratorObject",<|"MessageTemplate"->IteratorObject::inv,"MessageParameters"->{junk}|>])

Now, we can delegate all generic functions to their implementations in the interface. We also convert the EndOfIterator exception into a symbol.

The general principle is the extract the raw iterators inside the object, apply the interface function to it, and wrap the result in IteratorObject.

IteratorObject/:HoldPattern[IteratorObject[iter_,___][]]:=EncloseIterator[iter[],EndOfIterator&]

IteratorObject/:Length[HoldPattern[IteratorObject[iter_,___]]]:=Size[iter]

IteratorObject/:Constructor[HoldPattern[IteratorObject[iter_,___]]]:=EncloseIteratorConstructor[Replace[Constructor[iter],Hold[cons_]:>Hold[IteratorObject[cons]]]]

IteratorObject/:Clone[HoldPattern[IteratorObject[iter_,___]]]:=EncloseIteratorConstructor[IteratorObject@Clone[iter]]

IteratorObject/:First[HoldPattern[IteratorObject[iter_,___]]]:=itFirst[iter]

...

IteratorObject/:Map[f_,HoldPattern[IteratorObject[iter_,___]]]:=IteratorObject@iMap[f,iter]

...

Constructors

We can also simplify our life by not having to remember all the iterator classes.
We can be inspired by the corresponding WL functions.

There is a magic wrapper: Iterator

Iterator[Range[10]]

Normal[%]

Or even turn a given list into an iterator version of itself:

list=Iterator[{a,b,c}]

list[[2]]

Last[list]

The implementation consists of a number of downvalues for the recognized cases, calling the iterator classes from the library.

Iterator[Range[imin_:1,imax_,di_:1]]:=IteratorObject@iRange[imin,imax,di]

Iterator[l_List]:=IteratorObject@iList[l]

...

The Iterators paclet

The paclet info file sets up the meta data and the custom loading function.

PacletObject[<|
"Name"->"Iterators",
"Description"->"Support for mutable iterators",
"Creator"->"Roman E. Maeder, Wolfram Research, Inc.","Version"->"3.0",
"WolframVersion"->"13.1+",
"AutoUpdating"->True,
"Loading"->"Startup",
"Extensions"->{{"Kernel","Root"->"Kernel","Context"->"IteratorsStartup`"}}
|>]

The IteratorsStartup` loader sets up autoloading for the code, and determines the visibility of the contexts in $ContextPath.

For hidden contexts, it looks like this:

`autoInterface={
"Iterators`Interface`IteratorQ",
"Iterators`Interface`Size",
...,
Nothing}

Package`DeclareLoad[
autoInterface,
absFile["Interface.wl"],
Package`ExportedContexts->{},Package`HiddenContexts->{"Iterators`Interface`"},Package`HiddenImport->True
]

For visible contexts, it looks like this:

`autoIntegration={
"Iterators`IteratorObject",
"Iterators`RawIterator",
"Iterators`Iterator",
"Iterators`EndOfIterator",
Nothing}

Package`DeclareLoad[
autoIntegration,
absFile["Integration.wl"],Package`ExportedContexts->{"Iterators`"},
Package`HiddenImport->True
]

Resources

The code for iterators is available in the paclet repository, https://resources.wolframcloud.com/PacletRepository/resources/RomanMaeder/Iterators/

The use it, load the paclet with

PacletInstall[ResourceObject["RomanMaeder/Iterators"]]

$ContextPath

As I said before, this is a work-in-progress, so don’t look for a lot of documentation, etc.

The currently published version is 2.0, which represents the code as of the European Wolfram Technology Conference in the Spring of 2022.
The updated code described here will follow soon (Version 2.0).

Bonus: ParallelSelect

The sequential nature of iterators make parallelization a challenge.
In functions such as Map and Select we can submit the next few items (up to $KernelCount) and when we need the next item, wait until it is returned from one of the kernels, and cache any others that have already finished.

myParallelSelect Code

This iterator defines one additional method: QueueLength.

Needs["Iterators`Interface`"]
Needs["Iterators`Class`"]

DeclareIterator[myParallelSelect,{func,iter,pending,run,res,nextin,nextout,len},{
myParallelSelect[iter0_, f0_]:=(
func=f0;iter=iter0;nextin=1;nextout=1;
pending={};run=True;res=<||>;len=Size[iter];
),
_myParallelSelect[]:=Block[{i,resi,job},
While[True,
While[run&&Length[pending]≤$KernelCount, (* submit one more *)
EncloseIterator[
AppendTo[pending,With[{ff=func,ni=nextin++,e=iter[]},ParallelSubmit[{ni,If[TrueQ[ff[e]],e,false]}]]],
(run=False)&
]
];
(* wait for the next desired result *)
If[KeyExistsQ[res,nextout] ,
With[{e=res[nextout]},
KeyDropFrom[res,nextout];nextout++;
If[e=!=false,
Return[e]
]]];
(* give up *)
If[!run && Length[pending]==0,RaiseEndOfIterator[]];
(* wait for a result *)
If[Length[pending]>0,
{{i,resi},job,pending}=WaitNext[pending];
res[i]=resi
]
]
],
DeleteObject[_myParallelSelect]:=(AbortKernels[];Clear[func,iter,pending,run,res,nextin,nextout,len];),
QueueLength[_myParallelSelect]:={Length[pending],Length[res]}
}];

Example

We want to find Fermat primes.

LaunchKernels[ ];$KernelCount

fermat=IteratorObject[myParallelSelect[
Iterators`Library`iRange[Infinity],
PrimeQ[2^Prime[#]-1]&]
]

Here is the first one:

fermat[]

The additional method QueueLength shows how many computations have been submitted, and how many results have already been collected.

QueueLength[RawIterator@fermat]

So, perhaps the next few are already done:

Take[fermat,16]

fermat[]

If we abandon the iterator before it is exhausted, it is necessary to clean up the pending computations on the subkernels.

DeleteObject[fermat];