DOC PREVIEW
UA CSC 520 - Control Flow — Iterators

This preview shows page 1-2-3-26-27-28 out of 28 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

UA CSC 520 - Control Flow — Iterators

Documents in this Course
Handout

Handout

13 pages

Semantics

Semantics

15 pages

Haskell

Haskell

15 pages

Recursion

Recursion

18 pages

Semantics

Semantics

12 pages

Scheme

Scheme

32 pages

Syllabus

Syllabus

40 pages

Haskell

Haskell

17 pages

Scheme

Scheme

27 pages

Scheme

Scheme

9 pages

TypeS

TypeS

13 pages

Scheme

Scheme

27 pages

Syllabus

Syllabus

10 pages

Types

Types

16 pages

FORTRAN

FORTRAN

10 pages

Load more
Download Control Flow — Iterators
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Control Flow — Iterators and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Control Flow — Iterators 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?