IteratorsIterators in JavaCLU-Style IteratorsCLU-style Iteratorsldots CLU-style Iteratorsldots CLU-style Iteratorsldots CLU-style Iteratorsldots CLU-style Iteratorsldots CLU-style Iteratorsldots CLU-style Iteratorsldots CLU Iterators --- Example ACLU Iterators --- Example Aldots CLU Iterators --- Example BCLU Iterators --- Example Bldots Iterator ImplementationIterator ImplementationIterator Implementationldots Iterator Implementationldots Nested IteratorsNested Iteratorsldots Nested Iteratorsldots Simpler Iterator ImplementationSimpler Iterator Implementationldots Simpler Iterator Implementationldots Icon GeneratorsReadings and ReferencesSummary520—Spring 2005—29CSc 520Principles of ProgrammingLanguages29: Control Flow — IteratorsChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2005 Christian Collberg[1]520—Spring 2005—29IteratorsFOR-loops are typically used to iterate over some rangeof enumerable values.Iterators are used to iterate over an abstraction,such as the elements of a list, the nodes of a tree, theedges of a graph, etc.For example,for n := tree_nodes_in_inorder(T) doprint nend[2]520—Spring 2005—29Iterators in JavaIn object-oriented languages it is typical to create anenumeration object which contains the current state ofthe iteration:Enumeration iter = new Tree.inorder(T);while (iter.hasNextElement()) {Node n = (Node) iter.nextElement();n.print();}This is not as clean as in languages with built-in supportfor iterators.[3]520—Spring 2005—29CLU-Style IteratorsIterators were pioneered by CLU, a (dead) class-basedlanguage from MIT.setsum = proc(s:intset) returns(int)sum : int := 0for e:int in intset$elmts(s) dosum := sum + eendreturnsumend setsum[4]520—Spring 2005—29CLU-style Iterators...Procedure setsum computes the sum of the elementsin a set of integers.setsum iterates over an instance of the abstract typeintset using the intset$elmts iterator.Each time around the loop, intset$elmts yields anew element, suspends itself, and returns control to theloop body.[5]520—Spring 2005—29CLU-style Iterators...intset = cluster is create,elmts,...rep = array[int]elmts = iter(s:cvt) yields(int)i : int := rep$low(s)while i <= rep$high(s) doyield (s[i])i = i + 1endendelmtsend intset[6]520—Spring 2005—29CLU-style Iterators...A CLU cluster is a typed module; a C++ class, butwithout inheritance.CLU makes a clear distinction between the abstracttype (the cluster as seen from the outside), and itsrepresentation (the cluster from the inside). Therepclause defines the relationship between the two.[7]520—Spring 2005—29CLU-style Iterators...elmts = iter(s:cvt) yields(int)i : int := rep$low(s)while i <= rep$high(s) doyield (s[i])i = i + 1endendelmts[8]520—Spring 2005—29CLU-style Iterators...s:cvt says that the operation converts its argument fromthe abstract to the representation type.rep$low and rep$high are the bounds of the arrayrepresentation.yield returns the next element of the set, and thensuspends the iterator until the next iteration.Iterators may be nested and recursive.[9]520—Spring 2005—29CLU-style Iterators...array = cluster [t: type] is ...elmts = iter(s:array[t]) yields(t)for i:int in int$from to(array[t]$low(a),array[t]$high(a)) doyield(a[i])endendelmtsend arrayelmts = iter(s:cvt) yields(int)for i:int in array$elmts(s) doyield(i)endendelmts[10]520—Spring 2005—29CLU-style Iterators...Iterators may invoke other iterators.CLU supports constrained generic clusters (like Ada’sgeneric packages, only better).[11]520—Spring 2005—29CLU Iterators — Example AHere’s an example of a CLU iterator that generates allthe integers in a range:for i in from_to_by(first,last,step) do...end[12]520—Spring 2005—29CLU Iterators — Example A...from_to_by = iter(from,to,by:int) yields(int)i : int := fromif by> 0 thenwhile i <= to doyield ii +:= byendelsewhile i >= to doyield ii +:= byendend[13]520—Spring 2005—29CLU Iterators — Example BHere’s an example of a CLU iterator that generates allthe binary trees ofn nodes.for t: bin_tree in bin_tree$tree_gen(n) dobin_tree$print(t)end[14]520—Spring 2005—29CLU Iterators — Example B...bin_tree = cluster ...node = record [left,right : bin_tree]rep = variant [some : node, empty : null]...tree_gen = iter (k : int) yields (cvt)if k=0 thenyield red$make_empty(nil)elsefor i:int in from_to(1,k) dofor l : bin_tree in tree_gen(i-1) dofor r : bin_tree in tree_gen(k-i) doyield rep$make_some(node${l,r})endendendend tree_gen...end[15]520—Spring 2005—29Iterator ImplementationIter1 = iter ( ... )... yield x(1) ...endendIter1P =proc ( ... )for i in Iter1(...) doSendendP[16]520—Spring 2005—29Iterator ImplementationCalling an iterator is the same as calling a procedure.Arguments are transferred, an activation record isconstructed, etc.Returning from an iterator is also the same as returningfrom a procedure call.[17]520—Spring 2005—29Iterator Implementation...Resume framefor Iter1ActivationRecord forIter 1Activationrecord for Presume link:return address: (1)[18]520—Spring 2005—29Iterator Implementation...When an iterator yields an item, its activation recordremains on the stack. A new activation record (called aresume frame) is added to the stack.The resume frame contains information on how toresume the iterator. The return address-entry in theresume frame contains the address in the iterator bodywhere execution should continue when the iterator isresumed.[19]520—Spring 2005—29Nested Iteratorsfor i in Iter1(...) doforj in Iter2(...) doSendend[20]520—Spring 2005—29Nested Iterators...Since iterators may be nested, a procedure may haveseveral resume-frames on the stack.A new resume frame is inserted first in the procedure’siterator chain.At the end of the for-loop body we resume the firstiterator on the iterator chain:1. The first resume frame is unlinked.2. We jump to the address contained in the removedframe’s return address entry.[21]520—Spring 2005—29Nested Iterators...return address: (1)resume link:/resume link:AR for Preturn address: (2)resume link:Resume AR for Iter2Resume AR for Iter1AR for Iter2AR for Iter1return address: (1)resume link:/resume link:AR for PWhen we get to the endof Iter2’s body wereturn as from a normalcall.Iter1 may generate anew item and P may again start up Iter2.Resume AR for Iter1AR for Iter1[22]520—Spring 2005—29Simpler Iterator ImplementationIter = iter ( ... )while ... doyield
View Full Document