Smalltalk › Cincom › VisualWorks

Iterator

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

9 messages Options

Wouter Gazendam

Iterator

Hi,

Just to share some idea I had today. Today I was writing some code
iterating over a tree. I wanted to do something like:

tree allNodes detect: [:elem | elem isFoo].

Given that the tree does have a #allNodesDo: but no #allNodes I could
have implemented a

TreeNode>>allNodes
| coll |
coll := OrderedCollection new.
self allNodesDo: [:elem | coll add: elem].
^coll

or implement a

TreeNode>>detectNodeFoo
self allNodesDo: [:elem | coll elem isFoo ifTrue: [^elem]].
self raiseFooNotFound

But then the idea of a Iterator struck me:

Define Iterator as a subclass of Collection and with 'fetchBlock' as instVar.
Next, implement:
Iterator>>do: aBlock
fetchBlock value: aBlock

So you could implement #allNodes as:

TreeNode>>allNodes
^Iterator new fetchBlock: [:bl | self allNodesDo: bl]

and then run

tree allNodes detect: [:elem | elem isFoo].

but also do all sorts of other nifty tricks like:

tree allNodes asOrderedCollection.

and #select:'s and #collects:

Does anyone recognise this pattern? Does it already have an other name?

Cheers,

Wouter Gazendam

CosmoCows B.V.

Reinout Heeck-2

Re: Iterator

Hoi Wouter!

Whenever I see the identifier 'Iterator' my mind automatically thinks
'Stream'.

But that is not what you are doing, a stream wraps the collection (or
better: wraps a data source).

Rather than wrapping the data source you seem to be extending the result
object to hold on to a block that is only used during
instantiation/initialization of the result object.

As a thought experiment I suggest you rename #allNodes to
#asOrderedCollection and then explain to yourself why it returns an
Iterator instead of an OrderedCollection.

To me it seems that you are mixing 'building a result' with the result
itself.

R
-

> Hi,
>
> Just to share some idea I had today. Today I was writing some code
> iterating over a tree. I wanted to do something like:
>
> tree allNodes detect: [:elem | elem isFoo].
>
> Given that the tree does have a #allNodesDo: but no #allNodes I could
> have implemented a
>
> TreeNode>>allNodes
> | coll |
> coll := OrderedCollection new.
> self allNodesDo: [:elem | coll add: elem].
> ^coll
>
> or implement a
>
> TreeNode>>detectNodeFoo
> self allNodesDo: [:elem | coll elem isFoo ifTrue: [^elem]].
> self raiseFooNotFound
>
> But then the idea of a Iterator struck me:
>
> Define Iterator as a subclass of Collection and with 'fetchBlock' as
> instVar.
> Next, implement:
> Iterator>>do: aBlock
> fetchBlock value: aBlock
>
> So you could implement #allNodes as:
>
> TreeNode>>allNodes
> ^Iterator new fetchBlock: [:bl | self allNodesDo: bl]
>
> and then run
>
> tree allNodes detect: [:elem | elem isFoo].
>
> but also do all sorts of other nifty tricks like:
>
> tree allNodes asOrderedCollection.
>
> and #select:'s and #collects:
>
> Does anyone recognise this pattern? Does it already have an other name?
>
> Cheers,
>
> Wouter Gazendam
>
> CosmoCows B.V.
>
>

Paul Baumann

RE: Iterator

In reply to this post by Wouter Gazendam

Wouter,

The Strategy pattern is applied in similar ways to create
TraversalStrategy kinds of objects for specific purposes. I think the VW
way for finding methods in the image is an example of that. Your class
could be described as a configurable traversal strategy with a twist in
that it is intended for polymorphism with Collection protocol.

I'm fairly sure the idea has been presented before--Travis could
probably point to specific examples. It reminds me of one of the things
that are so clever that people forget to use it. If someone has to
declare #nodesDo: methods to define what a 'node' is then they might
just use that instead of going the extra step of declaring a
#nodeIterator (or #deepNodeIterator) method that would answer an
Iterator instance to adapt #nodesDo: sends to support Collection
protocol.

Collections are usually more efficient at answering their size than
iterating their contents. A concern with your Iterator would be that
some common usage patterns could perform less efficiently by incurring
iteration/traversal costs more than once. A hidden cost of misuse of
your Iterator is that pushing and popping stack frames is more expensive
than iterating a collection of objects that has already been collected.

One characteristic of your Iterator is that it does "just-in-time"
iteration. A benefit is that it can avoid creating a large collection in
memory. Detecting an object with your Iterator is faster than building a
collection and then detecting an object in that collection. Note that
these benefits also apply to #nodesDo: alone.

The idea has value, refine the implementation. The approach reflects a
way of thinking about objects in graphs rather than collections. The
benefit of adapting an iteration for use in place of a collection could
easily be forgotten. That could be a challenge.

Paul Baumann

-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On
Behalf Of Wouter Gazendam
Sent: Friday, March 30, 2007 7:40 AM
To: [hidden email]
Subject: Iterator

Hi,

Just to share some idea I had today. Today I was writing some code
iterating over a tree. I wanted to do something like:

tree allNodes detect: [:elem | elem isFoo].

Given that the tree does have a #allNodesDo: but no #allNodes I could
have implemented a

TreeNode>>allNodes
| coll |
coll := OrderedCollection new.
self allNodesDo: [:elem | coll add: elem].
^coll

or implement a

TreeNode>>detectNodeFoo
self allNodesDo: [:elem | coll elem isFoo ifTrue: [^elem]].
self raiseFooNotFound

But then the idea of a Iterator struck me:

Define Iterator as a subclass of Collection and with 'fetchBlock' as
instVar.
Next, implement:
Iterator>>do: aBlock
fetchBlock value: aBlock

So you could implement #allNodes as:

TreeNode>>allNodes
^Iterator new fetchBlock: [:bl | self allNodesDo: bl]

and then run

tree allNodes detect: [:elem | elem isFoo].

but also do all sorts of other nifty tricks like:

tree allNodes asOrderedCollection.

and #select:'s and #collects:

Does anyone recognise this pattern? Does it already have an other name?

Cheers,

Wouter Gazendam

CosmoCows B.V.

--------------------------------------------------------
This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired.

Andre Schnoor

Re: Iterator

In reply to this post by Wouter Gazendam

I would always do these things the plain recursive style, because I
originally started programming with LISP. Smalltalk being polymorphic,
there's no reason to invent iterators. Most "complicated" traversals can
be implemented with a single recursive method only:

TreeNode>>detect: aBlock ifNone: failBlock
(self value: aBlock)
ifTrue:[ ^self ].
self children do: [:child |
| found |
(found := child detect: aBlock ifNone: nil) notNil
ifTrue:[ ^found ]
].
^failBlock value

Now call this with

myTree detect:[ :node | node isFoo ] ifNone: nil

Andre

Wouter Gazendam wrote:

Nicolas Cellier-3

Re: Iterator

However, if you think of ProgramNodeEnumerator, you get a nice example of
iterator on abstract syntax tree (AST).

And the advantage of such is to provide genericity.

See, on the ProgramNode side, you just have to define a single message to
traverse the tree.

And in ProgramNodeEnumerator subclasses, you program only a message for
specific nodes on which you want to perform an action.

Also, such enumerator subclass can gather state in inst var instead of passing
a bunch of arguments in the message send stack.

If you would have to program this in ProgramNode side, i guess you would
generate a lot more messages.

I used this pattern on symbolic expressions. This enabled to factor a lot of
code. For example, generating code for several target languages (C, FORTRAN,
ADA, LaTeX, Matlab, ...).

Nicolas

Le Samedi 31 Mars 2007 12:15, Andre Schnoor a écrit :

> I would always do these things the plain recursive style, because I
> originally started programming with LISP. Smalltalk being polymorphic,
> there's no reason to invent iterators. Most "complicated" traversals can
> be implemented with a single recursive method only:
>
> TreeNode>>detect: aBlock ifNone: failBlock
> (self value: aBlock)
> ifTrue:[ ^self ].
> self children do: [:child |
>
> | found |
>
> (found := child detect: aBlock ifNone: nil) notNil
> ifTrue:[ ^found ]
> ].
> ^failBlock value
>
> Now call this with
>
> myTree detect:[ :node | node isFoo ] ifNone: nil
>
> Andre
>
> Wouter Gazendam wrote:
> > Hi,
> >
> > Just to share some idea I had today. Today I was writing some code
> > iterating over a tree. I wanted to do something like:
> >
> > tree allNodes detect: [:elem | elem isFoo].
> >
> > Given that the tree does have a #allNodesDo: but no #allNodes I could
> > have implemented a
> >
> > TreeNode>>allNodes
> >
> > | coll |
> >
> > coll := OrderedCollection new.
> > self allNodesDo: [:elem | coll add: elem].
> > ^coll
> >
> > or implement a
> >
> > TreeNode>>detectNodeFoo
> > self allNodesDo: [:elem | coll elem isFoo ifTrue: [^elem]].
> > self raiseFooNotFound
> >
> > But then the idea of a Iterator struck me:
> >
> > Define Iterator as a subclass of Collection and with 'fetchBlock' as
> > instVar.
> > Next, implement:
> > Iterator>>do: aBlock
> > fetchBlock value: aBlock
> >
> > So you could implement #allNodes as:
> >
> > TreeNode>>allNodes
> > ^Iterator new fetchBlock: [:bl | self allNodesDo: bl]
> >
> > and then run
> >
> > tree allNodes detect: [:elem | elem isFoo].
> >
> > but also do all sorts of other nifty tricks like:
> >
> > tree allNodes asOrderedCollection.
> >
> > and #select:'s and #collects:
> >
> > Does anyone recognise this pattern? Does it already have an other name?
> >
> > Cheers,
> >
> > Wouter Gazendam
> >
> > CosmoCows B.V.

Andre Schnoor

Re: Iterator

nicolas cellier wrote:

However, if you think of ProgramNodeEnumerator, you get a nice example of 
iterator on abstract syntax tree (AST).

And the advantage of such is to provide genericity.

I think blocks are generic enough.

See, on the ProgramNode side, you just have to define a single message to 
traverse the tree.

Yes: #children (or equivalent) ;-)

And in ProgramNodeEnumerator subclasses, you program only a message for 
specific nodes on which you want to perform an action.

Also, such enumerator subclass can gather state in inst var instead of passing 
a bunch of arguments in the message send stack.

Ok, I agree this makes sense, if there are a lot of state transitions that depend on the node sequence. But in general, you could also keep track of states in the outer scope like this:

   | any state vars |
   myTree withAllChildrenDo:[ :node |
     "do anything with the state vars" ].

Where #withAllChildrenDo: is implemented similar to my previous example. What I actullay wanted to say is: An Iterator can be just a single message (implemented for the affected classes) and everything else is done in a block that is passed to the message (IMHO).

However, if #children happens to create a lot of garbage, it'd possibly be better to re-implement #withAllChildredDo: for the respective classes.

If you would have to program this in ProgramNode side, i guess you would 
generate a lot more messages.

No, just #children.

Andre

I used this pattern on symbolic expressions. This enabled to factor a lot of 
code. For example, generating code for several target languages (C, FORTRAN, 
ADA, LaTeX, Matlab, ...).

Nicolas

Le Samedi 31 Mars 2007 12:15, Andre Schnoor a écrit :

I would always do these things the plain recursive style, because I
originally started programming with LISP. Smalltalk being polymorphic,
there's no reason to invent iterators. Most "complicated" traversals can
be implemented with a single recursive method only:

TreeNode>>detect: aBlock ifNone: failBlock
    (self value: aBlock)
        ifTrue:[ ^self ].
    self children do: [:child |

       | found |

       (found := child detect: aBlock ifNone: nil) notNil
          ifTrue:[ ^found ]
    ].
    ^failBlock value

Now call this with

    myTree detect:[ :node | node isFoo ] ifNone: nil

Andre

Wouter Gazendam wrote:

Hi,

Just to share some idea I had today. Today I was writing some code
iterating over a tree. I wanted to do something like:

tree allNodes detect: [:elem | elem isFoo].

Given that the tree does have a #allNodesDo: but no #allNodes I could
have implemented a

TreeNode>>allNodes

    | coll |

    coll := OrderedCollection new.
    self allNodesDo: [:elem | coll add: elem].
    ^coll

or implement a

TreeNode>>detectNodeFoo
    self allNodesDo: [:elem | coll elem isFoo ifTrue: [^elem]].
    self raiseFooNotFound

But then the idea of a Iterator struck me:

Define Iterator as a subclass of Collection and with 'fetchBlock' as
instVar.
Next, implement:
Iterator>>do: aBlock
    fetchBlock value: aBlock

So you could implement #allNodes as:

TreeNode>>allNodes
    ^Iterator new fetchBlock: [:bl | self allNodesDo: bl]

and then run

    tree allNodes detect: [:elem | elem isFoo].

but also do all sorts of other nifty tricks like:

    tree allNodes asOrderedCollection.

and #select:'s and #collects:

Does anyone recognise this pattern? Does it already have an other name?

Cheers,

Wouter Gazendam

CosmoCows B.V.

Nicolas Cellier-3

Re: Iterator

Yes, you are right, such enumarator pattern becomes interesting only if
a lot of code can be factored, or if complexity inside the block would
require a specialized class.

Also, it does double the send stack depth with double dispatching, but
i'am not sure how it affect efficiency (speed can matter when processing
large trees).

Nicolas

Andre Schnoor a écrit :

> nicolas cellier wrote:
>> However, if you think of ProgramNodeEnumerator, you get a nice example of
>> iterator on abstract syntax tree (AST).
>>
>> And the advantage of such is to provide genericity.
>>
> I think blocks are generic enough.
>
>> See, on the ProgramNode side, you just have to define a single message to
>> traverse the tree.
>>
> Yes: #children (or equivalent) ;-)
>
>> And in ProgramNodeEnumerator subclasses, you program only a message for
>> specific nodes on which you want to perform an action.
>>
>> Also, such enumerator subclass can gather state in inst var instead of passing
>> a bunch of arguments in the message send stack.
>>
> Ok, I agree this makes sense, if there are a lot of state transitions
> that depend on the node sequence. But in general, you could also keep
> track of states in the outer scope like this:
>
> | any state vars |
> myTree withAllChildrenDo:[ :node |
> "do anything with the state vars" ].
>
> Where #withAllChildrenDo: is implemented similar to my previous example.
> What I actullay wanted to say is: An Iterator can be just a single
> message (implemented for the affected classes) and everything else is
> done in a block that is passed to the message (IMHO).
>
> However, if #children happens to create a lot of garbage, it'd possibly
> be better to re-implement #withAllChildredDo: for the respective classes.
>
>> If you would have to program this in ProgramNode side, i guess you would
>> generate a lot more messages.
>>
> No, just #children.
>
> Andre
>
>
>> I used this pattern on symbolic expressions. This enabled to factor a lot of
>> code. For example, generating code for several target languages (C, FORTRAN,
>> ADA, LaTeX, Matlab, ...).
>>
>> Nicolas
>>
>> Le Samedi 31 Mars 2007 12:15, Andre Schnoor a écrit :
>>
>>> I would always do these things the plain recursive style, because I
>>> originally started programming with LISP. Smalltalk being polymorphic,
>>> there's no reason to invent iterators. Most "complicated" traversals can
>>> be implemented with a single recursive method only:
>>>
>>> TreeNode>>detect: aBlock ifNone: failBlock
>>> (self value: aBlock)
>>> ifTrue:[ ^self ].
>>> self children do: [:child |
>>>
>>> | found |
>>>
>>> (found := child detect: aBlock ifNone: nil) notNil
>>> ifTrue:[ ^found ]
>>> ].
>>> ^failBlock value
>>>
>>> Now call this with
>>>
>>> myTree detect:[ :node | node isFoo ] ifNone: nil
>>>
>>> Andre
>>>
>>> Wouter Gazendam wrote:
>>>
>>>> Hi,
>>>>
>>>> Just to share some idea I had today. Today I was writing some code
>>>> iterating over a tree. I wanted to do something like:
>>>>
>>>> tree allNodes detect: [:elem | elem isFoo].
>>>>
>>>> Given that the tree does have a #allNodesDo: but no #allNodes I could
>>>> have implemented a
>>>>
>>>> TreeNode>>allNodes
>>>>
>>>> | coll |
>>>>
>>>> coll := OrderedCollection new.
>>>> self allNodesDo: [:elem | coll add: elem].
>>>> ^coll
>>>>
>>>> or implement a
>>>>
>>>> TreeNode>>detectNodeFoo
>>>> self allNodesDo: [:elem | coll elem isFoo ifTrue: [^elem]].
>>>> self raiseFooNotFound
>>>>
>>>> But then the idea of a Iterator struck me:
>>>>
>>>> Define Iterator as a subclass of Collection and with 'fetchBlock' as
>>>> instVar.
>>>> Next, implement:
>>>> Iterator>>do: aBlock
>>>> fetchBlock value: aBlock
>>>>
>>>> So you could implement #allNodes as:
>>>>
>>>> TreeNode>>allNodes
>>>> ^Iterator new fetchBlock: [:bl | self allNodesDo: bl]
>>>>
>>>> and then run
>>>>
>>>> tree allNodes detect: [:elem | elem isFoo].
>>>>
>>>> but also do all sorts of other nifty tricks like:
>>>>
>>>> tree allNodes asOrderedCollection.
>>>>
>>>> and #select:'s and #collects:
>>>>
>>>> Does anyone recognise this pattern? Does it already have an other name?
>>>>
>>>> Cheers,
>>>>
>>>> Wouter Gazendam
>>>>
>>>> CosmoCows B.V.
>>>>
>>
>>
>>

Alan Knight-2

Re: Iterator

In reply to this post by Wouter Gazendam

I'm with Reinout in that when I see "Iterator" I think "Stream". And I do like having operations like detect:, collect:, etc. available on streams. I also have a vague recollection of someone describing a mechanism for implementing a stream on top of any collection that provided do:, but I can't recall the context. It used two proceses, if I recall.

At 07:39 AM 3/30/2007, Wouter Gazendam wrote:

Hi,

Just to share some idea I had today. Today I was writing some code
iterating over a tree. I wanted to do something like:

tree allNodes detect: [:elem | elem isFoo].

Given that the tree does have a #allNodesDo: but no #allNodes I could
have implemented a

TreeNode>>allNodes
        | coll |
        coll := OrderedCollection new.
        self allNodesDo: [:elem | coll add: elem].
        ^coll

or implement a

TreeNode>>detectNodeFoo
        self allNodesDo: [:elem | coll elem isFoo ifTrue: [^elem]].
        self raiseFooNotFound

But then the idea of a Iterator struck me:

Define Iterator as a subclass of Collection and with 'fetchBlock' as instVar.
Next, implement:
Iterator>>do: aBlock
        fetchBlock value: aBlock

So you could implement #allNodes as:

TreeNode>>allNodes
        ^Iterator new fetchBlock: [:bl | self allNodesDo: bl]

and then run

        tree allNodes detect: [:elem | elem isFoo].

but also do all sorts of other nifty tricks like:

        tree allNodes asOrderedCollection.

and #select:'s and #collects:

Does anyone recognise this pattern? Does it already have an other name?

Cheers,

Wouter Gazendam

CosmoCows B.V.

Alan Knight [|], Cincom Smalltalk Development

[hidden email]

http://www.cincom.com/smalltalk

"The Static Typing Philosophy: Make it fast. Make it right. Make it run." - Niall Ross

Reinout Heeck-2

Re: Iterator

Alan Knight wrote:
> I'm with Reinout in that when I see "Iterator" I think "Stream". And I
> do like having operations like detect:, collect:, etc. available on
> streams. I also have a vague recollection of someone describing a
> mechanism for implementing a stream on top of any collection that
> provided do:, but I can't recall the context. It used two proceses, if
> I recall.
More formally: turning an internal iterator (#do:) into an external
iterator (a stream).

Like Alan says, VW does not implement this in an orthogonal way:
non-sequenceable collections don't have #readStream and streams don't
have the *ect: interface. (but what should these *ect: methods return -
a stream or a collection :-)

Anyway this discussion was a while ago:
http://groups.google.nl/group/comp.object/browse_thread/thread/9ceeb5a8bac6729b/2db52e4bc56313fe

There are examples in that thread implementing this
-using an extra thread
-using coroutines
-using exceptions

Cheers,
Reinout
-------