CSc 520 — Principles of Programming Languages31 : Control Structures — IteratorsChristian CollbergDepartment of Computer ScienceUniversity of [email protected] 2008 Christian CollbergApril 7, 20081 Iterators• FOR-loops are typically used to iterate over some range of enumerable values.• Iterators are used to iterate over an abstraction, such as the elements of a list, the nodes of a tree,the edges of a graph, etc.• For example,for n := tree_nodes_in_inorder(T) doprint nendIterators in Java2 Iterators in Java• In object-oriented languages it is typical to create an enumeration object i which contains thecurrent state of the iteration:LinkedList<String> L = new LinkedList<String>();L.add("Bebe");L.add("Wendy");L.add("Nelly");Iterator<String> i = L.iterator();while (i.hasNext()) {String c = i.next();System.out.println(c);}• This is not as clean as in languages with built-in support for iterators.13 Java 1.5 extended for-loop• As of Java 1.5, the for-loop has been augmented so you can sayLinkedList<String> L = new LinkedList<String>();L.add("Bebe");L.add("Wendy");L.add("Nelly");for (String c : L)System.out.println(c);• However, this is just syntactic sugar for calls to the Iterator class.4 Java 1.5 extended for-loop• You can tell that this is just syntactic sugar by looking at the bytecode the compiler generates (usejavap -c Iter):29: aload_130: invokevirtual #8; // LinkedList.iterator:33: astore_234: aload_235: invokeinterface #9,1; // java/util/Iterator.hasNext40: ifeq 6343: aload_244: invokeinterface #10,1; // java/util/Iterator.next49: checkcast #11; // java/lang/String52: astore_353: getstatic #12; // java/lang/System.out56: aload_357: invokevirtual #13; // java/io/PrintStream.println60: goto 342Ruby iterators5 Blocks• Let’s write a simple Ruby for loop to search through an array looking for a particular value:$flock = ["huey","dewey","louie"]def isDuck?(name)for i in 0...$flock.lengthif $flock[i] == name thenreturn trueendendreturn falseendputs isDuck?("dewey"), isDuck?("donald")6 Iterators• Ruby’s iterators are an easier way to do this.• The Array class implements a method find that iterates through the array.def isDuck?(name)$flock.find do |x|x == nameendendputs isDuck?("dewey")puts isDuck?("donald")7 Yield• A block is enclosed within { } or do...end. Arguments to the block (there can be more than one) aregiven within |...|.• A block is passed to a method by giving it after the list of “normal” parameters.• The method invokes the block by using yield.• yield can take an argument which the method passed back to the block.38 Yield. . .def triplets()yield "huey"yield "dewey"yield "louie"endtriplets() {|d| puts d}triplets() do |d|puts dend9 Factorial• Here’s the factorial function, as an iterator.def fac(n)f = 1for i in 1..nf *= iyield fendendfac(5) {|f| puts f}10 Passing arguments• yield can pass more than one value to the block.def fac(n)f = 1for i in 1..nf *= iyield i,fendendfac(5) do |i,x|puts "#{i}! = #{x}"end11 Nesting iterators• Iterators can be nested.fac(3) do |i,x|fac(3) do |j,y|puts "#{i}! * #{j}! = #{x*y}"4endend12 Scope• A local variable which is active when the block is started up, can be accessed (and modified) withinthe block.def sumfac(n)y = 0fac(n) do |i,x|y = y + xendreturn yendputs sumfac(5)13 Implementing Array#find• We can implement our own find method:def find(arr)for i in 0..arr.lengthif yield arr[i] then return true endendreturn falseendputs find($flock) {|x| x=="dewey"}puts find($flock) {|x| x=="donald"}14 Array#collect• collect applies the block to every element of an array, creating a new array. This is similar to Haskell’smap.$flock = ["huey","dewey","louie"]$flock.each {|x| puts x}puts $flock.collect {|x| x.length}puts $flock.collect do |x|"junior woodchuck, General " + xend15 Array#inject• inject(init) is similar to Haskell’s foldl.• inject() without an argument is like Haskell’s foldl1, i.e. it uses the first element of the array asthe starting value.5x = $flock.inject("") do |elmt,total|total = elmt + " " + totalendputs xx = $flock.inject() do |elmt,total|total = elmt + " " + totalendputs x6Icon Generators16 Icon GeneratorsProcedures are really generators; they can return 0, 1, or a sequence of results. There are three casesfail The procedure fails and generates no value.return e The procedure generates one value, e.suspend e The procedure generates the value e, and makes itself ready to possibly generate more values.procedure To(i,j)while i <= j do {suspend ii+:= 1}end17 Exampleprocedure To(i,j)while i <= j do {suspend ii+:= 1}endprocedure main()every k := To(1,3) dowrite(k)end18 simple.icnprocedure P()suspend 3suspend 4suspend 5endprocedure main()every k := P() dowrite(k)end719 simple.icn. . .> setenv TRACE 100> simple: main()simple.icn : 8 | P()simple.icn : 2 | P suspended 33simple.icn : 9 | P resumedsimple.icn : 3 | P suspended 44simple.icn : 9 | P resumedsimple.icn : 4 | P suspended 55simple.icn : 9 | P resumedsimple.icn : 5 | P failedsimple.icn : 10 main failed8Iterators in CLU20 CLU-Style Iterators• Iterators were pioneered by CLU, a (dead) class-based language from MIT.setsum = proc(s:intset) returns(int)sum : int := 0for e:int in intset$elmts(s) dosum := sum + eendreturn sumend setsum21 CLU-style Iterators. . .• Procedure setsum computes the sum of the elements in a set of integers.• setsum iterates over an instance of the abstract type intset using the intset$elmts iterator.• Each time around the loop, intset$elmts yields a new element, suspends itself, and returns controlto the loop body.22 CLU-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 + 1endend elmtsend intset23 CLU-style Iterators. . .• A CLU cluster is a typed module; a C++ class, but without inheritance.• CLU makes a clear distinction between the abstract type (the cluster as seen from the outside), andits representation (the cluster from the inside). The rep clause defines the relationship between thetwo.924 CLU-style Iterators. . .elmts = iter(s:cvt) yields(int)i : int := rep$low(s)while i <= rep$high(s) doyield (s[i])i = i + 1endend elmts25 CLU-style Iterators. . .• s:cvt says that the operation converts its argument from the abstract to the representation type.• rep$low and rep$high are the bounds of the array representation.• yield returns the
View Full Document
Unlocking...