Iterators

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.
We show an implementation of iterators that allows to use them like lists, with natural Wolfram Language syntax.
Along the way we explore mutable objects and constructors, syntax transformation, working with unevaluated expressions, parallelization, and compilation.

20211014

Chapter 0: 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

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, currently available via the Files link of this presentation,
and hopefully showing up in the new Wolfram Paclet Repository soon.

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

Chapter 1: A Minimal Interface

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

(I do not want to call it an object at this point.)

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

iter=Module[{next=1,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[{}]

I keep the interface as simple as possible:

The next element function call operator

EndOfIterator to indicate that we fell off the end

the iteratorQ predicate

But not:

No “peek” method

No set/reset methods

All other methods are optional (such as Size, and cloning)

However, if you need additional methods, you can easily define them.

An Iterator Factory

If we need many similar iterators,
it is worthwhile to write a constructor that does all the tedious work of setting up the objects.

makeRange[i0_Integer,i1:(_Integer|Infinity),Optional[di_Integer?Positive,1]]:=
With[{range=Unique["range"]},
Module[{i=i0-di},
range[]:=(i+=di;If[i<=i1,i,EndOfIterator]);
Size[range]:=Max[Ceiling[(i1-i)/di],0];
range
]]

This example also shows two common features of iterators:

a way to handle exhaustion

a method that returns the number of remaining elements

Both are (optional) parts of our interface.

i10=makeRange[1,10]

Size[i10]

Table[i10[],Size[i10]]

i10[]

Size[i10]

Infinity

As iterators produce elements one at a time,
there is no need for an a-priori bound on the number of elements.
It may be infinite, or unknown (Indeterminate).

inf=makeRange[1,Infinity,2]

Table[inf[],20]

Size[inf]

Chapter 2: Iterator Factories

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 also change the representation of an iterator to a normal expression, with the instance variables in held form inside.

What we implement is essentially a custom subset of OO technologies without the usual OO syntax quirks.

The Range Example Revisited

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],EndOfIterator],
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.

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.

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

Or look at the definitions created when an iterator class is declared.

?myRange

Chapter 3: Functions on Iterators

This section gives examples of programming with iterators.

Functions that consume the input iterator and return a single result

Functions that work incrementally and return a result iterator

Membership Test, or the Importance of the Abort Key

Here is itMemberQ, which is an iterator version of MemberQ.

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

Iterators that are exhausted return EndOfIterator; but for programming it is often more convenient to generate an exception when this happens, to avoid ugly If[] statements all over the place.

You can wrap inner iterator calls in ConfirmIterator, which generates an exception when it sees EndOfIterator, and you can handle this exception with EncloseIterator.
By default, EncloseIterator returns EndOfIterator itself, but above we use a different value, False.

itMemberQ[iRange[2,10,2],5]

itMemberQ[iRange[2,Infinity,2],5]

MemberQ is a partial function.
Other examples include: FreeQ, Last, Select, Fold, …

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.

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

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.

Constructor[_myMap]:=ConstructHeld[myMap,ff,CloneHeld[elems]]

Clone[squares]

%[]

Note: it is ConstructHeld, not ConstructorHeld, as it is a version of the System function Construct, that returns its result wrapped in Hold (like LinkReadHeld).

Construct[Plus,Sqrt[2.0],10!]

ConstructHeld[Plus,Sqrt[2.0],10!]

A Nontrivial Example: Binary Trees

You know where to find code like this…

Clear[ltt,toTree];
ltt[]:=With[{kk=++k},
f[If[ll[[kk]]===0,list[[++i]],ltt[]],
 If[rr[[kk]]===0,list[[++i]],ltt[]] ]
];
toTree[ll0_,rr0_,f0_,{e_}]:=e; (* one element case is special, so treat it here *)
toTree[ll0_,rr0_,f0_,list0_]:=Block[{i=0,k=0,ll=ll0,rr=rr0,list=list0,f=f0}, ltt[]]

DeclareIterator[iGroupings,{n,f,list,ll,rr,count,first},{
iGroupings[list0:{__},f0_:List]:=(
list=list0;f=f0;
n=Length[list]-1;count=CatalanNumber[n];
ll=Append[Range[2,n],0];
rr=ConstantArray[0,n];
first=True
),
_iGroupings[]:=Which[
count≤0,
	EndOfIterator,
first,
	first=False;--count;
	toTree[ll,rr,f,list],
True,
  Block[{j=1,y,k},
	--count;
	While[j≤n&&ll[[j]]==0,rr[[j]]=0;ll[[j]]=j+1;j++];
	(* this code is called only if there are elements left, so j>n is not possible *)
	y=ll[[j]];k=0;
	While[rr[[y]]>0,k=y;y=rr[[y]]];
	If[k>0,rr[[k]]=0,ll[[j]]=0];
	rr[[y]]=rr[[j]];rr[[j]]=y;
	toTree[ll,rr,f,list]
  ]
],
Size[_iGroupings]:=count
}]

gr=iGroupings[{(CombinatorS),(CombinatorK),(CombinatorS),(CombinatorK),(CombinatorS)},Application]

Size[gr]

Table[gr[],Size[gr]]

Compiled 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 thing.
The code in DeclareIterator needs to create the data thing, 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]

Chapter 4: 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

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.

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]

(I just started with this; the support is far from complete right now)

Resources

The code is in a paclet, currently available as part of the presentation resources, as a .paclet archive.

Download it, then install it (use Insert▶File Path to get the path)

PacletInstall["/home/home1/maeder/Downloads/Iterators-0.9.paclet"]

Everything is now set up and will load on first use in the current and every new session.

$ContextPath

To remove the paclet, use

PacletUninstall["Iterators"]

PacletFind["Iterators"]

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

Bonus: ParallelMap

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.

iParallelMap Code

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

Example

We want to find the number of prime factors of the numbers 10^60+i, for i=1000,1001,…

Total[FactorInteger[10^60+1000][[All,2]]]

$KernelCount

factors=iParallelMap[{#,Total[FactorInteger[10^60+#][[All,2]]]}&,iRange[1000,Infinity]]

Here is the first one:

factors[]

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

QueueLength[factors]

So, perhaps the next one is already done:

factors[]

Select can benefit from parallelization, as often many items need to be computed until one is found that meets the condition.

primes=iSelect[factors,#[[2]]==1&]

primes[]

primes[]

QueueLength[factors]

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

DeleteObject[primes];DeleteObject[factors]

slides[]

One more thing:

…[…_]:=……

…@…