Iterators and Iterators and Generators Generators

(1)

Iterators and Iterators and

Generators Generators

Giuseppe Attardi Giuseppe Attardi

Dipartimento di Informatica Dipartimento di Informatica

Università di Pisa Università di Pisa

(2)

What is an iterator?

 An Iterator is an object that can be used to An Iterator is an object that can be used to control the iteration behavior of a loop

control the iteration behavior of a loop

 A generator A generator yieldsyields values one at a time values one at a time instead of returning all values

instead of returning all values

 The benefits of using generators:The benefits of using generators:

 Generates values on demand

 Requires less memory

 Allows the caller to start processing immediately

 Improves the performance of an application

(3)

Example: Tree Traversal Example: Tree Traversal

 Tree is a very common Tree is a very common data structure

data structure

 A lot of applications:A lot of applications:

 File system

 Video categorization

 ...

 Find and process data Find and process data contained in a certain of contained in a certain of

tree nodes tree nodes

Find blue nodes and do something with the

information stored in them

slide by Hayouan Li

(4)

All-In-One Solution All-In-One Solution

Code reuse problem Code reuse problem ReadBlue(Node n) { ReadBlue(Node n) { if (n.color == Blue) if (n.color == Blue) Read(n);

Read(n);

for (Node child: n.children()) for (Node child: n.children()) ReadBlue(child);

ReadBlue(child);

}}

WriteBlue(Node n) { WriteBlue(Node n) { if (n.color == Blue) if (n.color == Blue)

Write(n, what_ever);

for (Node child: n.children()) for (Node child: n.children()) WriteBlue(child);

WriteBlue(child);

}}

PlayBlue(Node n) {...}

EmptyBlue(Node n) {...}

Find blue nodes and do something on each

slide by Hayouan Li

(5)

With Function Objects With Function Objects

MapBlue(Node n, func(Node n)) { MapBlue(Node n, func(Node n)) { if (n.color == Blue)

if (n.color == Blue) func(n);

func(n);

for (Node child: n.children()) for (Node child: n.children()) MapBlue(child, func);

MapBlue(child, func);

}}

Read(Node n) {...}

Write(Node n) { what_ever; ...};

MapBlue(root, Read);

MapBlue(root, Write);

MapBlue(root, Write); Find blue nodes and do

something on each

slide by Hayouan Li

(6)

Visitor Pattern Visitor Pattern

 Pass object that visits the nodesPass object that visits the nodes

 Better integrated with OO paradigmBetter integrated with OO paradigm

 Still fairly complexStill fairly complex

(7)

Tree Tree

interface Tree { } interface Tree { }

class Node implements Tree { class Node implements Tree { List<Tree> children;List<Tree> children;

}}

class Leaf implements Tree { class Leaf implements Tree { int value;int value;

}}

(8)

Visitor on a Tree Visitor on a Tree

interface Visitable { interface Visitable {

void accept(Visitor v);void accept(Visitor v);

}}

interface Visitor { interface Visitor {

void visit(Visitable v);void visit(Visitable v);

}}

class VisitableNode extends Node, implements Visitable { class VisitableNode extends Node, implements Visitable { void accept(Visitor v) {void accept(Visitor v) {

v.visit(this);

for (VisitableNode c: children) for (VisitableNode c: children) c.accept(visitor);c.accept(visitor);

}}

class VisitableLeaf extends Leaf, implements Visitable { class VisitableLeaf extends Leaf, implements Visitable { void accept(Visitor v) { v.visit(this); }void accept(Visitor v) { v.visit(this); }

(9)

Visitor Usage Visitor Usage

class Printer implements Visitor { class Printer implements Visitor { void visit(VisitableNode n) { }void visit(VisitableNode n) { }

void visit(VisitableLeaf l) { print(l.value); }void visit(VisitableLeaf l) { print(l.value); } }}

(10)

CMM Garbage Collector CMM Garbage Collector

 Generational Mostly Copying CollectorGenerational Mostly Copying Collector

 Tricolor markingTricolor marking

 white object are copied to NextGeneration white object are copied to NextGeneration

and turned into gray by function scavenge(x) and turned into gray by function scavenge(x)

 gray objects are turned to black by invoking gray objects are turned to black by invoking x.traverse()

x.traverse()

 x.traverse() in turn call scavenge(p) for all x.traverse() in turn call scavenge(p) for all pointers p in x

pointers p in x

(11)

CMM Phases CMM Phases

Root Set

Heap Root

Set

Heap Root

Set

Heap

Before Collection

After Page Promotion

After Compaction

(12)

CMM Visitor Pattern CMM Visitor Pattern

class CmmObject { class CmmObject {

void* operator new(size_t, CmmHeap*);void* operator new(size_t, CmmHeap*);

virtual void traverse() = 0; // accept visiting virtual void traverse() = 0; // accept visiting GCGC

void mark();void mark();

};};

class Node : public CmmObject { class Node : public CmmObject { void traverse() {void traverse() {

scavenge(left); // GC visitscavenge(left); // GC visit

scavenge(right); // GC visitscavenge(right); // GC visit };};

(13)

Iterators

(14)

C++ Template Enumeration C++ Template Enumeration

template<class T>

class EnumerableVector : std::vector<T> { class EnumerableVector : std::vector<T> {

public:

Enumeration getEnumeration() { Enumeration getEnumeration() {

return (Enumeration(this));

}}

class Enumeration { … } class Enumeration { … } };};

(15)

Enumeration (2) Enumeration (2)

class Enumeration { class Enumeration {

private:

vector<T> const* vp;vector<T> const* vp;

unsigned idx;unsigned idx;

public:

Enumeration(vector<T> const* vector) :Enumeration(vector<T> const* vector) : vp(vector), idx(0) { } vp(vector), idx(0) { }

T const& next() { // uses 'TT const& next() { // uses 'T‘‘

if (idx == vp->size())if (idx == vp->size())

throw NoSuchElementException(index);throw NoSuchElementException(index);

return (*vp)[idx++];return (*vp)[idx++];

}}

bool hasNext() { return idx < vp->size(); }bool hasNext() { return idx < vp->size(); } };};

(16)

Enumeration (3) Enumeration (3)

EnumerableVector<int> ev;

……

EnumerableVector<int>::Enumeration EnumerableVector<int>::Enumeration

en = ev.getEnumeration();

while (en.hasNext()) while (en.hasNext())

cout << en.next() << endl;

(17)

C# Iterators C# Iterators

interface IEnumerable<T>

interface IEnumerator<T> : IDisposable interface IEnumerator<T> : IDisposable {{

bool MoveNext();bool MoveNext();

T Current { get; }T Current { get; } void Dispose();void Dispose();

}}

(18)

Java Enumeration Interface Java Enumeration Interface

interface Enumeration<T> { interface Enumeration<T> {

boolean hasMoreElements();boolean hasMoreElements();

T nextElement();T nextElement();

}}

(19)

Java Iterator Interface Java Iterator Interface

interface Iterator<T> { interface Iterator<T> { boolean hasNext();boolean hasNext();

T next();T next();

void remove();void remove();

}}

(20)

Java for loop Java for loop

ArrayList<String> items;

for (String item : items) { for (String item : items) {

System.out.println(item);

} }

Works for any object that implements the Works for any object that implements the Iterable

Iterable interfaceinterface

(21)

Java Iterable Interface Java Iterable Interface

interface Iterable<T> { interface Iterable<T> { Iterator<T> iterator();Iterator<T> iterator();

void forEach(Consumer<? super T> action);void forEach(Consumer<? super T> action);

default Spliterator<T> spliterator();default Spliterator<T> spliterator();

}}

(22)

Java 8: forEach + lambda Java 8: forEach + lambda

Map<String, Integer> items = Map<String, Integer> items =

new HashMap<>();

items.put("A", 10); … items.put("A", 10); … items.forEach((k,v)->

items.forEach((k,v)->

System.out.println("Item: " + k + " System.out.println("Item: " + k + "

Count: " + v));

// method reference // method reference

items.forEach(System.out::println);

(23)

Python Iterators Python Iterators

 Obtain an iterator. Method in iterable class:Obtain an iterator. Method in iterable class:

def __iter__(self): … def __iter__(self): …

 Iterator interface. Single methodIterator interface. Single method def __next__(self): …

def __next__(self): …

 Termination by raisingTermination by raising

StopIterationException StopIterationException

 Builtin function Builtin function iter()iter() takes an iterable takes an iterable object and returns an iterator

object and returns an iterator

(24)

Generators

(25)

What is a generator?

 A generator is an iterator (not viceversa)A generator is an iterator (not viceversa)

 A method or a function can be turned into a A method or a function can be turned into a generator by a specific language construct generator by a specific language construct

like:

yield

(26)

Problem: collecting all Problem: collecting all

results results

 An accumulator is neededAn accumulator is needed Nodes FindBlue(Node n) { Nodes FindBlue(Node n) {

Nodes buf = new Nodes();

if (n.color == Blue) if (n.color == Blue)

buf.append(n);

for (Node child: n.children()) for (Node child: n.children())

buf.append(FindBlue(child));

return buf;

}}

Nodes B = FindBlue(root);

for (Node b: B) { for (Node b: B) {

Read(b);

Write(b);

Play(b);

Empty(b);

}}

(27)

With a Generator With a Generator

Enumerator<Node> FindBlue(Node n) { Enumerator<Node> FindBlue(Node n) { if (n.color == Blue)

if (n.color == Blue) yield return n;

yield return n;

for (Node child: n.children()) for (Node child: n.children()) FindBlue(child);

FindBlue(child);

}}

for (Node n: FindBlue(root)) { for (Node n: FindBlue(root)) { Read(n);

Read(n);

Write(n);

Play(n);

Empty(n);

Delete(n);

}}

(28)

Generator vs Stateful Generator vs Stateful

Function Function

 GeneratorGenerator

 Language-level construct that keeps runtime state of a function across invocations

 Uses simple instructions with clear semantics

• yield break

• yield return

 Stateful Function, i.e. closureStateful Function, i.e. closure

 Must be implemented by user

 Requires complex control structures

 Visitor PatternVisitor Pattern

(29)

Yield Operator Yield Operator

 Available in:Available in:

 C#

 JavaScript

 Python

 Ruby

 Special case of closure (or continuation)Special case of closure (or continuation)

(30)

Infinite Sequence Infinite Sequence

def fib():

first = 0 first = 0

second = 1 second = 1

yield first yield first

yield second yield second

while True:

next = first + second next = first + second

yield next yield next

first = second first = second

second = next second = next for n in fib():

for n in fib():

print n print n

(31)

Compiler turn into a closure- Compiler turn into a closure- like like

def fib():

first = [0]first = [0]

second = [1]second = [1]

def next():def next():

res = first[0] + second[0]res = first[0] + second[0]

first[0] = second[0]first[0] = second[0]

second[0] = ressecond[0] = res return resreturn res

return nextreturn next

(32)

Tree Visit Tree Visit

class Node():

def __init__(self, label):

self.label = label self.label = label

self.left = None self.left = None

self.right = None self.right = None

(33)

Hand coded iterator Hand coded iterator

class Node():

……

def __iter__(self):

return TreeIterator(self) return TreeIterator(self)

class TreeIterator():

def __init__(self, node):

self.stack = [node]

# state can be either: 'goLeft', 'visit', 'goRight'

# state can be either: 'goLeft', 'visit', 'goRight' self.state = 'goLeft'

self.state = 'goLeft'

(34)

Iteration method Iteration method

def next(self):

while self.stack:while self.stack:

node = self.stack[-1]node = self.stack[-1] # stack top# stack top if self.state == 'goLeft':if self.state == 'goLeft':

if node.left:if node.left:

self.stack.append(node.left)self.stack.append(node.left)

else:else:

self.state = 'visit'self.state = 'visit' elif self.state == 'visit':elif self.state == 'visit':

self.state = self.state = ‘‘ goRightgoRight’’ return node.labelreturn node.label

elif self.state == 'goRight':elif self.state == 'goRight':

self.stack.pop()self.stack.pop() # its visit is complete# its visit is complete

if node.right:if node.right:

self.state = 'goLeft'self.state = 'goLeft'

self.stack.append(node.right)self.stack.append(node.right)

else:else:

self.state = 'visitself.state = 'visit‘‘ # no fully visited nodes are on the stack # no fully visited nodes are on the stack self.stack.pop()self.stack.pop()

raise StopIteration raise StopIteration

(35)

Testing the iterator Testing the iterator

n0 = Node(0); n1 = Node(1); n2 = n0 = Node(0); n1 = Node(1); n2 =

Node(2) Node(2)

n3 = Node(3); n4 = Node(4); n5 = n3 = Node(3); n4 = Node(4); n5 =

Node(5) Node(5)

n0.left = n1 n0.left = n1

n0.right = n2 n0.right = n2

n1.right = n4 n1.right = n4

for n in n0:

print nprint n

(36)

Expansion of the for loop Expansion of the for loop

it = n0.__iter__() it = n0.__iter__() try:try:

while True:

v = it.next()v = it.next() print v

print v

catch StopIteration:

continue continue

(37)

Inorder Visit Inorder Visit

def inorder(t):

if t:

for x in inorder(t.left):

yield x yield x

yield t.label yield t.label

for x in inorder(t.right):

yield x yield x

(38)

Tree insertion Tree insertion

class Node():

def __init__(self, label):

self.label = label self.left = None self.right = None def insert(self, val):

if self.label < val:

if self.right:

self.right.insert(val) else:

self.right = Node(val) elif self.left:

self.left.insert(val) else:

self.left = Node(val)

(39)

Test Test

r = Node(0) r = Node(0)

for i in [2, 1, -2, -1, 3]:

r.insert(i) r.insert(i)

for v in inorder(r):

print vprint v

-2 -1 0 1 2 3 -2 -1 0 1 2 3

(40)

Example Example

def map(func, iterable):

result = []result = []

for item in iterable:for item in iterable:

result.append(func(item))result.append(func(item)) return resultreturn result

def imap(func, iterable):

for item in iterable:for item in iterable:

yield func(item)yield func(item)

(41)

'yield' and 'try'/'finally' 'yield' and 'try'/'finally'

 Python does not allow 'yield' inside a 'try' Python does not allow 'yield' inside a 'try' block with a 'finally' clause:

block with a 'finally' clause:

try:try:

yield xyield x

yield xyield x finally:finally:

print xprint x

 'yield' inside 'finally' or in 'try'/'except' is 'yield' inside 'finally' or in 'try'/'except' is allowed

allowed