Iterate over two lists in parallel

[Gavin Sinclair]

On Monday, March 24, 2003, 1:54:53 PM, Julian wrote:

>> Now I'm responding to my own messages, which is dangerously close to
>> talking to myself. But another, more common, problem where generators
>> have the advantage is trying to iterate over two lists in parallel.
>>

> Never understimate the amazing power of call/cc.

> (Programming in a language that lacks it is like commuting to work
> without a personal teleporter... :-)

The above quote is from the thread concerned with producing slides
comparing Ruby and Python.

I'd like someone, hopefully including Julian and Jim (Weirich), to
demonstrate how to iterate over twop lists in parallel. Extra marks
for setting a realistic example problem and solving it!

Gavin

[Julian Snitow]

k. :-)

With block iterators:

#!/usr/bin/ruby -w

class Array
def splice(foo)
((foo.size > size) ? foo.size : size).times do |i|
yield self[i] if self[i]
yield foo[i] if foo[i]
end
end
end

animals = ["monkey", "goat", "cow", "ox", "lizard", "lion", "bat",
"gorilla", "tiger", "frog"]
vehicles = ["car", "plane", "bicycle", "catapult", "unicycle", "hang
glider", "bus", "pogo stick", "boat", "train", "gondola", "skateboard",
"ski lift"]

animals.splice(vehicles) { |val| puts val }

################################

And now a completely contrived example using continuations, since as
we've shown above, this problem doesn't require anything so powerful.

#!/usr/bin/ruby -w

animals = ["monkey", "goat", "cow", "ox", "lizard", "lion", "bat",
"gorilla", "tiger", "frog"]
vehicles = ["car", "plane", "bicycle", "catapult", "unicycle", "hang
glider", "bus", "pogo stick", "boat", "train", "gondola", "skateboard",
"ski lift"]

puts callcc { |outsideWorld|

cc, dd = nil, nil
curr, other = callcc { |cc|
cc.call callcc { |dd|
dd.call animals, vehicles
}
}
# Here is where the continuation ``cc'' begins

if(x = curr.shift)
puts x
end

if curr == [] && other == []
outsideWorld.call "Free at last!"
else
dd.call other, curr
end

}
# Continuation (locally known as 'outsideWorld' in the preceding block)
begins here.

puts "... And now the program can end."

# :-)
######################################

Or have I misinterpreted the problem? It seems too trivial to be a
"show me that this is possible" kind of problem... :-(

[Gavin Sinclair]

On Monday, March 24, 2003, 3:35:23 PM, Julian wrote:

> Or have I misinterpreted the problem? It seems too trivial to be a
> "show me that this is possible" kind of problem... :-(

Thanks for the solution. You didn't misunderstand the problem, nor
did I doubt it was possible. But Jim mentioned that walking two lists
in parallel was a special case that Ruby's iterators don't handle very
gracefully. So I wanted to see what "the Ruby way" was.

Thanks also for reinforcing that I shall never understand
continuations!

Gavin

[Julian Snitow]

In all fairness, my continuation-based solution was much more convoluted
than it had to be. I was just having so much fun with them I couldn't
help myself... ;-)

Ok, the basics of continuations:

A continuation (in theory) represents "the rest of the program" from the
point that it's created. Imagine you're walking down the street and you
come to a fork in the road. You don't know whether to go left or right,
so you generate a "continuation".

Road
Left-or-right?
generate a continuation called "choice"
| \--Go left
| |---walk around
| |---find a mean dog
| \---get bitten by the mean, terribly hungry dog
| \---that wasn't a good idea.
| \---tell "choice" that left was a bad idea
|
|----according to "choice", left was a bad idea
\----let's go right instead.

Now, the real magic of continuations happens when you have more than one
of them.

Say when you got bitten by the dog, you generated another continuation
called "got bitten", before telling "choice" that left was a bad idea.

So, you're walking along, un-bitten, since you went right at the fork in
the road after all, and suddenly you're hit by an oncoming train.

You decide that getting bitten by the dog was preferable to this, so you
kindly ask the continuation named "got bitten" to take you back to the
alley where you were lying bleeding from the dog bite, but at least
hadn't been hit by a train. ;-)

The moral of the story: When in doubt, just stay home.

For a more in-depth look at continuations, see "Run, Lola, Run", "The
Legend of Zelda: Ocarina of Time", and "Back to the Future: Part II" :-)

[Hal E. Fulton]

----- Original Message -----
From: "Julian Snitow" <vang...@yahoo.com>
Newsgroups: comp.lang.ruby
To: "ruby-talk ML" <ruby...@ruby-lang.org>
Sent: Monday, March 24, 2003 11:59 AM
Subject: Re: Iterate over two lists in parallel

> Ok, the basics of continuations:

[snippage]

Once again, a wonderful explanation.

This makes me think that continuations would be
good where real decision trees are used, e.g., in
chess programs and such.

> For a more in-depth look at continuations, see "Run, Lola, Run", "The
> Legend of Zelda: Ocarina of Time", and "Back to the Future: Part II" :-)

:) Don't forget _Groundhog Day_...

Cheers,
Hal

[dbl...@superlink.net]

Hi --

Isn't that more of an 'do until' structure? :-)

David

--
David Alan Black
home: dbl...@superlink.net
work: blac...@shu.edu
Web: http://pirate.shu.edu/~blackdav

[Jim Weirich]

On Sun, 2003-03-23 at 22:15, Gavin Sinclair wrote:

> I'd like someone, hopefully including Julian and Jim (Weirich), to
> demonstrate how to iterate over twop lists in parallel. Extra marks
> for setting a realistic example problem and solving it!

Here's my take on this ... you can find an HTML version (that's a bit
more readable) at http://w3.one.net/~jweirich/talks/same_fringe/

-----------------------------------------------------------------------
#!/usr/bin/env ruby

# = Introduction
#
# [On Monday, March 24, 2003 in ruby-talk, Gavin Sinclair writes]
# "I'd like someone, hopefully including Julian and Jim (Weirich), to
# demonstrate how to iterate over two lists in parallel. Extra marks
# for setting a realistic example problem and solving it!"
#
# How can I refuse an offer like that!
#
# Here's what's ahead ... We will start with the Same Fringe problem.
# Then we will implement the solution three times (once by converting
# everything to arrays, once with a hand-written external iterator,
# and once with a generator). We will finish up with a discussion of
# how the generator implementation works (using continuations) works
# in Ruby.
#
# Sound good?
#
# = The Same Fringe Problem
#
# Lets imagine that we have a binary tree filled with sorted data.
# This kind of tree is a common data structure used to implement
# hash-like tables where the keys are stored in sorted order.
#
# These binary trees have the property that depth-first visit of the
# leaf nodes will visit the leaves in sorted order (we are ignoring
# interior nodes for this example). However, two trees containing the
# same leaf nodes may be structured differently (due to the order in
# which nodes are inserted into the tree).
#
# We want to write some code that will determine if two binary trees
# have the same fringe (i.e. leaf) nodes.
#
# == Example
#
# Consider the following trees ...
#
# tree1 tree2 tree3
# o o o
# / \ / \ / \
# A o o C o C
# / \ / \ / \
# B C A B A X
#
# Trees 1 and 2 have the same fringe leaves, although they are
# internally structured differently. Tree 3 does not have the same
# fringe as either tree 1 or 2, due to the leaf node X.
#
# = The Code
#
# So lets take a look at the code to handle this problem.
#
# == Class Node
#
# We will use a Node class to represent the interior nodes of our
# binary tree (leaf nodes will simply be strings). A node has an
# accessor for its left and right children.

class Node
attr_accessor :left, :right

def initialize(left, right)
@left, @right = left, right
end
end

# Iterating through a binary tree is pretty easy. You just
# recursively visit the left children and then the right children.
# Since we are ignoring the interior nodes, we don't have to worry
# about pre-order vs post-order.
#
# We use implement the iteration in term of +each+ and include
# +Enumerable+, making our trees respond to the standard Ruby internal
# iterator protocol.

class Node
include Enumerable

def each(&block)
handle_child(self.left, &block)
handle_child(self.right, &block)
end

def handle_child(value, &block)
case value
when Node
value.left.each(&block)
value.right.each(&block)
else
yield(value)
end
end
end

# == External Iterators
#
# Internal iterators are difficult to use in solving the same-fringe
# problem. The reason is that we want to walk both trees, one element
# at a time, so we can compare the elements. Because internal
# iterators encapsulate the iteration algorithm, it is difficult to
# change the algorithm to handle two trees.
#
# Fortunately it is easy to solve the same-fringe problem with
# external iterators. In the following code, assume an iterator
# provides a method named +get+ that returns the next available item
# from the iterator. When the iterator is done, +get+ will return
# nil.
#
# == Same Fringe Function Using External Iterators
#
# Here is the same_fringe function written with external iterators.
# The function takes two iterators as arguments, one iterator for each
# of the two trees being compared. Same_fringe will only return true
# if each element from both trees are identical all the way to the end
# of the list. Since the iterators just return a sequence of leaf
# nodes, we are ignoring the tree structure during the comparison.

def same_fringe(it1, it2)
while v1 = it1.get
v2 = it2.get
return false if v1 != v2
end
return v1 == it2.get
end

# Notice that +same_fringe+ doesn't care what kind of iterator it is
# given, as long as the iterator conforms to the +get+ specification
# we gave. We will write several iterators and pass them to
# +same_fringe+.
#
# == Support Code
#
# Before we write some iterators, here is some support code that we
# will use in the demonstration.
#
# *show* will show the contents of a tree using the given iterator.
# *show* is a good example of using our external iterator.

def show(msg, it)
print msg
while v = it.get
print " ", v
end
puts
end

# *show_sf* will run the +same_fringe+ function with the given
# iterators and show the results.

def show_sf(msg, expect, it1, it2)
result = same_fringe(it1, it2)
puts "Same Fringe, #{msg}, should be #{expect}, was #{result}"
fail "Unexected Result!" if expect != result
end

# Finally, *demonstrate* will create some trees and display them.
# *Demonstrate* expects a block that will return an iterator of the
# appropriate type.

def demonstrate(msg)
tree1 = Node.new("A", Node.new("B", "C"))
tree2 = Node.new(Node.new("A", "B"), "C")
tree3 = Node.new(Node.new("A", "X"), "C")

puts "Using #{msg} ..."
show("Tree1 = ", yield(tree1))
show("Tree2 = ", yield(tree2))
show("Tree3 = ", yield(tree3))
show_sf("tree1 vs tree2", true,
yield(tree1),
yield(tree2))
show_sf("tree1 vs tree3", false,
yield(tree1),
yield(tree3))
puts
end

# ----
#
# == Array Iterator
#
# Our first external iterator will be one that walks through an array.
# An array iterator is trivial to implement (as you can see). Also,
# it is easy to convert a tree to an array since the Node objects
# support the +Enumerable+ protocol. We just need to call +to_a+ and
# we have an array of leaf nodes.
#
# Here is the array iterator...

class ArrayIterator
def initialize(collection)
@array = collection.to_a.dup
end
def get
@array.shift
end
end

# We use our +demonstrate+ function to show that the array iterater
# does do its job.

demonstrate("Array Iterator") { |tree| ArrayIterator.new(tree) }

# === Output for Array Iterator

#
# Using Array Iterator ...
# Tree1 = A B C
# Tree2 = A B C
# Tree3 = A X C
# Same Fringe, tree1 vs tree2, should be true, was true
# Same Fringe, tree1 vs tree3, should be false, was false

# ----
#
# == Tree Iterator
#
# Although trivial to write, the array iterator suffers from a
# potential problem. The tree must be converted to an array before
# the +same_fringe+ function can even begin to look at leaf nodes. If
# the tree is large, then this can be problematic.
#
# Can we create an external iterator that examines the tree "in
# place"? Certainly! Here is the code.

class TreeIterator
def initialize(node)
@tree = node
@stack = []
end

# Get the next leaf node.
def get
if @tree
t = @tree
@tree = nil
left_most(t)
elsif ! @stack.empty?
node = @stack.pop
left_most(node.right)
else
nil
end
end

# Find the left-most leaf from +node+.
def left_most(node)
while Node === node
@stack.push(node)
node = node.left
end
node
end
end

# And again we use the +demonstrate+ method to show that the
# TreeIterator works.

demonstrate("Tree Iterator") { |tree| TreeIterator.new(tree) }

# === Output for Tree Iterator
#
# Using Tree Iterator ...
# Tree1 = A B C
# Tree2 = A B C
# Tree3 = A X C
# Same Fringe, tree1 vs tree2, should be true, was true
# Same Fringe, tree1 vs tree3, should be false, was false

# ----
#
# == Generators
#
# The tree iterator works great, but it was a big pain to code up.
# Did you notice the explicit stack that was used to remember the
# nodes that had not yet been processed? It works, but the logic is
# much more obscure than the internal iterator logic.
#
# Wouldn't it be nice if it were possible to write an external
# iterator reusing the logic from the internal iterator.
#
# Fortunately, it is possible to do exactly that using generators. A
# generator is simply a resumable function. After a generator returns
# a value, the next time it is called it starts executing immediately
# after the last return, remembering the values of all the local
# variables in the function.
#
# Python generators use the keyword *yield* to designate returning a
# value and the resumption point in a generator. Since Ruby already
# uses *yield* for blocks, we will use a *generate* method to return
# generated values.
#
# Here is a simple example that generates the squares of the numbers 0
# through 3. Notice that the iteration logic goes into a block given
# to the generator constructor. The generator object returned from
# the constructor can be used as an iterator, just like our Tree and
# Array iterators.
#
# $ irb --simple-prompt
# >> require 'generator'
# => true
# >> it = Generator.new { |g| 4.times { |i| g.generate(i**2) } }
# => #<Generator:0x401f24e8 @resume=#<Continuation:0x401f24ac>>
# >> it.get
# => 0
# >> it.get
# => 1
# >> it.get
# => 4
# >> it.get
# => 9
# >> it.get
# => nil
# >> exit
# $
#
# We will look at the guts of the generator in a moment. In the
# meantime, lets use a generator to solve the same-fringe problem.
#
# First we load the generator code.

require 'generator'

# Then we define a function that creates our generator for us. Since
# we already have an internal iterator that works, we will simply use
# that in the iteration logic of our generator.

def tree_generator(tree)
Generator.new do |generator|
tree.each { |value| generator.generate(value) }
end
end

# And we show that the generator works.

demonstrate("Generator") { |tree| tree_generator(tree) }

# === Output for Tree Iterator
#
# Using Generator ...
# Tree1 = A B C
# Tree2 = A B C
# Tree3 = A X C
# Same Fringe, tree1 vs tree2, should be true, was true
# Same Fringe, tree1 vs tree3, should be false, was false

# ----
#
# == Writing the Generator Code
#
# So how are generators written in Ruby? ... Very Carefully!
#
# No, seriously! We need to use continuations.
#
# === Continuations
#
# The key to writing generators is using continuations. A
# continuation is a callable object (i.e. you can send a :call message
# to a continuation) that encodes the return point of a function.
# Continuations are created by given the +callcc+ (or "Call with
# Current Continuation") method a block. +callcc+ passes its own
# continuation (the "current" continuation) to the block as a
# parameter. When the continuation is called, that particular
# instance of +callcc+ will return immediately with the value passed
# in the call argument list.
#
# Here's a short example ...
#
# x = callcc do |continuation|
# puts "In CALLCC"
# continuation.call("HI")
# puts "This is never printed"
# end
# puts "X = #{x}"
#
# Will print ...
#
# In CALLCC
# X = HI
#
# In this example, callcc looks like a version of setjump/longjump in
# C where the continuation plays the role of the jump buffer. There
# is one big difference. In C, you must never call longjump outside
# the scope of the setjump call. A continuation is allowed to be
# called anywhere! Even outside the scope of the callcc method.
#
# We can use this fact to create resumable functions. The following
# function will return once (returning a 1). We then resume the
# function and it returns a second time, assigning 2 to x.
#
# def resumable
# callcc do |continuation|
# $resume_point = continuation
# return 1
# end
# return 2
# end
#
# x = resumable
# puts "Again, X = #{x}"
# $resume_point.call if x != 2
#
# Will print ...
#
# Again, X = 1
# Again, X = 2
#
# Wow! This gives use the tools we need to create resumable functions.
# The key is to capture a continuation that will allow us to resume a
# function at the point we need.
#
# === The Generator Class
#
# The key to our generator design is tracking the two different
# continuations we need. The @resume_generator continuation will be
# called from the main code (via the +get+ function) and will resume
# into the generator. The @resume_mainline continuation will be
# used by the generator to return to the mainline code.
#
# Here's the start of our generator class.

class Generator

# The initialize function is carefully designed to initialize the
# @resume_generator instance variable. We use +callcc+ to capture
# the continuation we want, and then return _early_ from +initialize+.
# The rest of +initialize+ will be run the first time we resume the
# generator.
#
def initialize
callcc do |continuation|
@resume_generator = continuation
return
end
yield(self)
while true
generate(nil)
end
end

# The +get+ method is called from the mainline code to resume the
# generator (to eventually return the next value). Our tasks are to
# ...
# * Capture the mainline continuation.
# * Resume the generator.

def get
callcc do |continuation|
@resume_mainline = continuation
@resume_generator.call
end
end
#
# Finally we have the +generate+ method. It is called from the
# generator to return values to the mainline code. Our tasks are to
# ...
# * Capture the continuation for the generator.
# * Resume the mainline code, while returning the next generated
# value.
#
def generate(value)
callcc do |continuation|
@resume_generator = continuation
@resume_mainline.call(value)
end
end
end

# And that's it.
#
# ----
#
# = Further Reading
#
# [http://www.cs.indiana.edu/hyplan/dfried/appcont.pdf]
# <em>Lecture notes -- Applications of continuations</em>,
# Daniel Friedman
#
# [http://www.ps.uni-sb.de/~duchier/python/continuations.html]
# <em>Continuations made simple and Illustrated</em>,
# Denys Duchier
#
# Search for "continuations" on Google for even more references.

--
-- Jim Weirich jwei...@one.net http://w3.one.net/~jweirich
---------------------------------------------------------------------
"Beware of bugs in the above code; I have only proved it correct,
not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)

[Gavin Sinclair]

On Tuesday, March 25, 2003, 12:50:42 PM, Jim wrote:

> On Sun, 2003-03-23 at 22:15, Gavin Sinclair wrote:

>> I'd like someone, hopefully including Julian and Jim (Weirich), to
>> demonstrate how to iterate over twop lists in parallel. Extra marks
>> for setting a realistic example problem and solving it!

> Here's my take on this ... you can find an HTML version (that's a bit
> more readable) at http://w3.one.net/~jweirich/talks/same_fringe/

Thanks Jim, that's *excellent*. I wonder if people are going to make
use of the Generator class.

What are the CPU and memory implications of using Generator?

Gavin

[Julian Snitow]

dbl...@superlink.net wrote:
> Hi --
>
> On Tue, 25 Mar 2003, Hal E. Fulton wrote:
>
>
>>----- Original Message -----
>>From: "Julian Snitow" <vang...@yahoo.com>
>>Newsgroups: comp.lang.ruby
>>To: "ruby-talk ML" <ruby...@ruby-lang.org>
>>Sent: Monday, March 24, 2003 11:59 AM
>>Subject: Re: Iterate over two lists in parallel
>>
>>
>>
>>>Ok, the basics of continuations:
>>
>>[snippage]
>>

quoted.snip!

>
> Isn't that more of an 'do until' structure? :-)
>
>
> David
>

As I understand it, you can define any known control structure using
continuations. (That's why the definition of the Scheme language
(``R5RS'') takes just 50 pages.) Everything else is just semantic
sugar. :-)

[Hal E. Fulton]

----- Original Message -----
From: "Jim Weirich" <jwei...@one.net>
To: "ruby-talk ML" <ruby...@ruby-lang.org>
Sent: Monday, March 24, 2003 7:50 PM
Subject: Re: Iterate over two lists in parallel

> Here's my take on this ... you can find an HTML version (that's a bit
> more readable) at http://w3.one.net/~jweirich/talks/same_fringe/

Jim,

I've been playing with this for about an hour,
and I've only managed to convince myself that
I don't actually understand it.

What I tried to do was encapsulate this
functionality in a module called Gen, so
that I could, for instance, do this:

class Array
include Gen
end

x = [5, 6, 7, 8, 9]

loop do
a = x.get
break if x.nil?
p a
end

Yes, I know the loop is trivial and an internal
iterator would suffice here. The point is that
I can't figure out this simple task. :(

Can you illuminate?

Thanks,
Hal

[Julian Snitow]

Jim Weirich wrote:
>
> [snip!]

>
> Here's my take on this ... you can find an HTML version (that's a bit
> more readable) at http://w3.one.net/~jweirich/talks/same_fringe/
>

> [snippety!]

Ooh... That is chock full of heady goodness! :-D

*throws out my admittedly much-inferior prototypical generator class*

Here's something else I've been poking around with. It's a generic
external iterator for any collection that supports the :each method.

#!/usr/bin/ruby -w

class ExternalIterator
def initialize(collection)
@collection = collection
@cont = nil
end
def get
@cont.call if @cont
@collection.each { |elem|
callcc { |@cont|
return elem
}
}
@cont = nil # reset the continuation and return nil
end
end

ex = ExternalIterator.new( ["foo", "bar", "baz", "qux", "florp", "zarg",
"narg"] )

while(x = ex.get)
puts x
end

puts "-----"
puts ex.get

##################################
# Here's the output:
foo
bar
baz
qux
florp
zarg
narg
-----
foo
###################################

Since it uses "each" to generate values, once you've gone through all
the values (and the final 'nil'), you can use the same iterator object
to iterate through the collection again.

This seems a lot less "magical" than your uber-cool Generator class, but
with the ability to turn :each "inside out", can anyone think of some
problems that still require generators?

Also, it just occured to me that it might be more Rubylike to have a
mixin method like

module Iteration
class ExternalIterator
# class definition same as above
end

def iter
ExternalIterator.new(self)
end
end

Then you'd just do something like

class Array
include Iteration
end

ex = ["foo", "bar", "baz", "qux", "florp", "bzaa", "worble"].iter

# then call ex.get whenever you want the next value
###################################

[Hal E. Fulton]

----- Original Message -----
From: "Julian Snitow" <vang...@yahoo.com>
Newsgroups: comp.lang.ruby

To: "ruby-talk ML" <ruby...@ruby-lang.org>
Sent: Tuesday, March 25, 2003 12:42 AM
Subject: Re: Iterate over two lists in parallel

> Also, it just occured to me that it might be more Rubylike to have a
> mixin method like
>
> module Iteration
> class ExternalIterator
> # class definition same as above
> end
>
> def iter
> ExternalIterator.new(self)
> end
> end
>
> Then you'd just do something like
>
> class Array
> include Iteration
> end
>
> ex = ["foo", "bar", "baz", "qux", "florp", "bzaa", "worble"].iter
>
> # then call ex.get whenever you want the next value
> ###################################

My thoughts exactly. :)

See my post from ten minutes ago.

Hal

[Jim Weirich]

On Tue, 2003-03-25 at 00:25, Hal E. Fulton wrote:

> I've been playing with this for about an hour,
> and I've only managed to convince myself that
> I don't actually understand it.
>
> What I tried to do was encapsulate this
> functionality in a module called Gen, so
> that I could, for instance, do this:
>
> class Array
> include Gen
> end
>
> x = [5, 6, 7, 8, 9]
>
> loop do
> a = x.get
> break if x.nil?
> p a
> end
>
> Yes, I know the loop is trivial and an internal
> iterator would suffice here. The point is that
> I can't figure out this simple task. :(
>
> Can you illuminate?

I don't know what you have in Gen, but I would expect it to work
something like this ...

x = [5,6,7,8,9]
it = x.iterator
loop do
a = it.get
break if a.nil?
p a
end

A generator is really just a fancy external iterator. So you need an
operation to create it (hence the iterator call). You then use the
iterator to, ummm, iterator; not the array itself.

The iterator method will probably look something like this ....

def iterator
Generator.new { |g| each { |it| g.generate(it) } }
end

That's the only thing you would need to mixin. Generator can still
stand alone.

Does that help?

[Hal E. Fulton]

----- Original Message -----
From: "Jim Weirich" <jwei...@one.net>
To: "ruby-talk ML" <ruby...@ruby-lang.org>
Sent: Tuesday, March 25, 2003 12:57 AM
Subject: Re: Iterate over two lists in parallel

> I don't know what you have in Gen, but I would expect it to work
> something like this ...
>
> x = [5,6,7,8,9]
> it = x.iterator
> loop do
> a = it.get
> break if a.nil?
> p a
> end
>
> A generator is really just a fancy external iterator. So you need an
> operation to create it (hence the iterator call). You then use the
> iterator to, ummm, iterator; not the array itself.
>
> The iterator method will probably look something like this ....
>
> def iterator
> Generator.new { |g| each { |it| g.generate(it) } }
> end
>
> That's the only thing you would need to mixin. Generator can still
> stand alone.
>
> Does that help?

Yes... I was mistaken in that I was initializing the
generator all right, but then was calling a method
of Array... and wondering why I got Continuations out. :D

I'd really rather use the object itself to
iterate, even if I must initialize it.

Something like:

x = [5,6,7,8,9]
x.reset

loop do
a = x.get

# ...
end

C'est possible?

Hal

[Pit Capitain]

On 25 Mar 2003 at 14:25, Hal E. Fulton wrote:

> What I tried to do was encapsulate this
> functionality in a module called Gen, so
> that I could, for instance, do this:
>
> class Array
> include Gen
> end
>
> x = [5, 6, 7, 8, 9]
>
> loop do
> a = x.get
> break if x.nil?
> p a
> end

Hal,

you could try it with

require 'generator'

module Gen
def get
unless @generator
@generator = Generator.new do |generator|
each { |value| generator.generate(value) }
end
end
@generator.get
end
end

Simply create a generator as in Jim's excellent tutorial if necessary
and then call its get Method.

Or even

require 'generator'

module Enumerable
def generator
Generator.new do |gen|
each { |value| gen.generate(value) }
end
end
end

g = [ 5, 6, 7, 8, 9 ].generator

loop do
a = g.get

break if a.nil?
p a
end

If you go this route, you can create multiple independent generators
of the same Enumerable.

Regards,
Pit

[Hal E. Fulton]

----- Original Message -----
From: "Hal E. Fulton" <hal...@hypermetrics.com>
To: "ruby-talk ML" <ruby...@ruby-lang.org>
Sent: Tuesday, March 25, 2003 1:22 AM
Subject: Re: Iterate over two lists in parallel

> I'd really rather use the object itself to
> iterate, even if I must initialize it.
>
> Something like:
>
> x = [5,6,7,8,9]
> x.reset
> loop do
> a = x.get
> # ...
> end
>
> C'est possible?

Sprry to reply to my own post, but another
small issue is that the generator always
returns nil after it exhausts the collection.

But what if a collection contains nil values?

I think I'd like an 'end?' method or something.
At worst, we could define a meta-nil value, but
I'm betting that's not necessary.

Hal

[Julian Snitow]

>
> Sprry to reply to my own post, but another
> small issue is that the generator always
> returns nil after it exhausts the collection.
>
> But what if a collection contains nil values?
>
> I think I'd like an 'end?' method or something.
> At worst, we could define a meta-nil value, but
> I'm betting that's not necessary.
>
> Hal
>
>

I don't know about generators, but for traversing a collection, my
iterator externalizer class (which I posted not 15 minutes ago ;-) can
handle this with trivial changes. Here it is, ready to eat, just add
water, etc. You will not find a nicer iterator class, or I will
self.eat(@hat) :-)

######## put this in 'iteration.rb' or something like that ###
module Iteration
class ExternalIterator
def initialize(collection, deathThroes=false)

@collection = collection
@cont = nil

@deathThroes = deathThroes

end
def get
@cont.call if @cont
@collection.each { |elem|
callcc { |@cont|
return elem
}
}
@cont = nil # reset the continuation

return nil unless @deathThroes
throw :iter_done
end
end
def iter(deathThroes=false)
ExternalIterator.new(self, deathThroes)
end
end
#####################################

And here's an example of it in use:

######### foo.rb ####################

require 'iteration.rb'

class FooCollectionClass # anything with a FooClass#each method
include Iteration
end

myFoo = FooCollectionClass.new

iterator = myFoo.iter(true)

catch(:iter_done)
while(true)
puts "The next element is: #{iterator.get}"
end
end

####################################

There. Now Ruby has external iterators. ;-)

Julian

[Julian Snitow]

Julian Snitow (i.e., I) wrote:
> Here it is, ready to eat, just add
> water, etc. You will not find a nicer iterator class, or I will
> self.eat(@hat) :-)
>

[snip]

> catch(:iter_done)
> while(true)
> puts "The next element is: #{iterator.get}"
> end
> end
>
> ####################################
>
> There. Now Ruby has external iterators. ;-)
>
> Julian
>

The last bit of the foo.rb example should read:

catch(:iter_done) {
while(true)
x = iterator.get
puts "The next element is: #{x}"
end
}

######

Apparently for some reason "#{iterator.get}" instead of using a static
expands weirdly in that loop. (Ruby 1.6.8)

/me nibbles the brim of his fedora (not quite hat-eating-worthy, but
still... it's good to be humbled every now and then... )

I'm wondering what's inside the string-expansion that changes the
behavior like that...

[gabriele renzi]

il Mon, 24 Mar 2003 17:58:24 GMT, Julian Snitow <vang...@yahoo.com>
ha scritto::

>
>Ok, the basics of continuations:

<snip/>

thanks, that was a wonderful explanation..
But I'm a dumb guy and I stil don't grok the whole continuation thing.

It seem to me that continuation are actually empowered GOTO, am I
wrong?

The difference is that all the changes beetween the label and the goto
call get discarded (this fits with a previous declaration that
begin/rescue was just a subset of continuation)...

If I understood this thing right, won't continnuations add a *huge*
level of unpredictability to the code?

And, to use Continuations in ruby are we tracing whatever happens in
every forked way we step down ?

PS
I think I'll love continuations since the previous post till the
eternity anyway.
I loved "Back to the future*" , "Groundhog day ", and "Run, lola,
run".
And I played Zelda* for years :)

[Jim Weirich]

On Tue, 2003-03-25 at 02:26, Hal E. Fulton wrote:

> Sprry to reply to my own post, but another
> small issue is that the generator always
> returns nil after it exhausts the collection.
>
> But what if a collection contains nil values?
>
> I think I'd like an 'end?' method or something.
> At worst, we could define a meta-nil value, but
> I'm betting that's not necessary.

Yeah, my tutorial glossed over that part. Having a standard for
external iterators will really help them be more useful. I would
suggest more? instead of end?. This allows you to write loops in terms
of the positive rather than a negative test. I.e.

while it.more?

Python iterators throw an exception when they are done. This means you
have one less method call to make in a loop. I'm uncomfortable with the
exception, it seems to be premature optimization. However, if you do go
that route, then I like Julian's use of catch/throw over an exception
(exceptions in my mind indicate a failure).

[Jim Weirich]

On Tue, 2003-03-25 at 02:22, Hal E. Fulton wrote:

> I'd really rather use the object itself to
> iterate, even if I must initialize it.
>
> Something like:
>
> x = [5,6,7,8,9]
> x.reset
> loop do
> a = x.get
> # ...
> end
>
> C'est possible?

It is possible to do it this way. In fact, Bertrand Meyer likes this
style in that his Eiffel library defines his iterators as part of the
collection object. I've never liked it though. Consider the following
..

def outer_function
stuff.reset
while stuff.more?
inner_function(stuff)
end
end

def inner_function(list)
list.reset # Oops ... we just blew away the iteration
while list.more? # in the outer function
do_somthing
end
end

[Han Holl]

Julian Snitow <vang...@yahoo.com> wrote in message
[ cut ]

>
> Also, it just occured to me that it might be more Rubylike to have a
> mixin method like
>
> module Iteration
> class ExternalIterator
> # class definition same as above
> end
>
> def iter
> ExternalIterator.new(self)
> end
> end
>
> Then you'd just do something like
>
> class Array
> include Iteration
> end
>
> ex = ["foo", "bar", "baz", "qux", "florp", "bzaa", "worble"].iter
>
> # then call ex.get whenever you want the next value
> ###################################

It may be more Rubyesque, but unfortunately it doesn't work:

puts ex.get
puts "---"
puts ex.get
puts "***"

produces:
foo
---
bar
---
baz
---
qux
---
florp
---
bzaa
---
worble
---
nil
---
foo
***

[Robert Klemme]

"Jim Weirich" <jwei...@one.net> schrieb im Newsbeitrag
news:1048592848.27719.6.camel@traken...

> Yeah, my tutorial glossed over that part. Having a standard for
> external iterators will really help them be more useful. I would
> suggest more? instead of end?. This allows you to write loops in terms
> of the positive rather than a negative test. I.e.
>
> while it.more?

What about "until it.end?"?

> Python iterators throw an exception when they are done. This means you
> have one less method call to make in a loop. I'm uncomfortable with the
> exception, it seems to be premature optimization. However, if you do go
> that route, then I like Julian's use of catch/throw over an exception
> (exceptions in my mind indicate a failure).

Well, if python iterators provide a tester for more elements then an
exception is in order IMHO. Java iterators do have boolean hasNext() as
well as Object next(). The latter throws if there are no more elements -
trying to get an element after the end is clearly an error, isn't it?

Regards

robert

[Paul Brannan]

On Tue, Mar 25, 2003 at 07:41:25AM +0900, Hal E. Fulton wrote:
> This makes me think that continuations would be good where real
> decision trees are used, e.g., in chess programs and such.

It may make a chess program easier to understand, but it will probably
slow it down. In Ruby, the cost of constructing a continuation that I
may or may not use is too high for almost anything I want to use
continuations for.

Paul

[Paul Brannan]

On Tue, Mar 25, 2003 at 05:43:11PM +0900, Julian Snitow wrote:
> Apparently for some reason "#{iterator.get}" instead of using a static
> expands weirdly in that loop. (Ruby 1.6.8)
>
> /me nibbles the brim of his fedora (not quite hat-eating-worthy, but
> still... it's good to be humbled every now and then... )
>
> I'm wondering what's inside the string-expansion that changes the
> behavior like that...

I think the problem is that you are returning directly from your
continution.

The first time get() is called, you create a continuation and store it
in @cont. When you return from the continuation, you always return to
the place where get() was first called. It's a little clearer if you
unroll your loop:

class Array
include Iteration
end

foo = [1, 2, 3]
iterator = foo.iter(false)

p iterator.get() #=> 1
p iterator.get() #=> 2
3
nil
1

iterator.get() gets called, returns 1, then 1 gets printed.
iterator.get() is called on the next line, then is returned to the
previous line, and 2 is printed. This continues until iteration is
complete and nil is returned.

I think this is why most other parallel iterators are implemented using
two continuations instead of one.

Paul

[Mauricio Fernández]

On Tue, Mar 25, 2003 at 10:03:09PM +0900, Han Holl wrote:
> Julian Snitow <vang...@yahoo.com> wrote in message
> [ cut ]
> >
> > Also, it just occured to me that it might be more Rubylike to have a
> > mixin method like
> >
> > module Iteration
> > class ExternalIterator
> > # class definition same as above
> > end
> >
> > def iter
> > ExternalIterator.new(self)
> > end
> > end
> >
> > Then you'd just do something like
> >
> > class Array
> > include Iteration
> > end
> >
> > ex = ["foo", "bar", "baz", "qux", "florp", "bzaa", "worble"].iter
> >
> > # then call ex.get whenever you want the next value
> > ###################################
>
> It may be more Rubyesque, but unfortunately it doesn't work:

The problem is not related to the use of Module#include, and it can be fixed:

batsman@tux-chan:/tmp$ expand -t 2 s.rb

class ExternalIterator
def initialize(collection)
@collection = collection
@cont = nil

@outer = nil
end
def get
callcc do |@outer|

@cont.call if @cont
@collection.each { |elem|
callcc { |@cont|

@outer.call elem

}
}
@cont = nil # reset the continuation and return nil
end
end

end

module Iteration
ExternalIterator = ::ExternalIterator

def iter
ExternalIterator.new(self)
end
end

class Array
include Iteration
end

arr = ["foo", "bar", "baz", "qux", "florp", "bzaa", "worble"]
ex = arr.iter

puts ex.get
puts "---"
puts ex.get
puts "***"

puts "=" * 80
ex = ExternalIterator.new(arr)

puts ex.get
puts "---"
puts ex.get
puts "***"

batsman@tux-chan:/tmp$ ruby s.rb
foo
---
bar
***
================================================================================
foo
---
bar
***

Don't mix that with Thread :)

--
_ _
| |__ __ _| |_ ___ _ __ ___ __ _ _ __
| '_ \ / _` | __/ __| '_ ` _ \ / _` | '_ \
| |_) | (_| | |_\__ \ | | | | | (_| | | | |
|_.__/ \__,_|\__|___/_| |_| |_|\__,_|_| |_|
Running Debian GNU/Linux Sid (unstable)
batsman dot geo at yahoo dot com

Save yourself from the 'Gates' of hell, use Linux." -- like that one.
-- The_Kind @ LinuxNet

[Mauricio Fernández]

Credits go to Han Holl [67861] for finding this:

batsman@tux-chan:/tmp$ expand -t 2 u.rb

######## put this in 'iteration.rb' or something like that ###
module Iteration
class ExternalIterator
def initialize(collection, deathThroes=false)
@collection = collection
@cont = nil
@deathThroes = deathThroes
end
def get
@cont.call if @cont
@collection.each { |elem|
callcc { |@cont|
return elem
}
}
@cont = nil # reset the continuation
return nil unless @deathThroes
throw :iter_done
end
end
def iter(deathThroes=false)
ExternalIterator.new(self, deathThroes)
end
end

class Array; include Iteration; end

arr = ["foo", "bar", "baz", "qux", "florp", "bzaa", "worble"]
ex = arr.iter

puts ex.get
puts "---"
puts ex.get
puts "***"

batsman@tux-chan:/tmp$ ruby u.rb

foo
---
bar
---
baz
---
qux
---
florp
---
bzaa
---
worble
---
nil
---
foo
***

I guess this means that...

Object.const_get("Julian Snitow").send("eat!".intern, "hat")

Here's the class I propose as nicer (cause not (less?) buggy):

batsman@tux-chan:/tmp$ expand -t 2 u.rb

######## put this in 'iteration.rb' or something like that ###
module Iteration
class ExternalIterator
def initialize(collection, deathThroes=false)
@collection = collection
@cont = nil
@deathThroes = deathThroes

@outer = nil
end
def get
callcc do |@outer|

@cont.call if @cont
@collection.each { |elem|
callcc { |@cont|

@outer.call elem

}
}
@cont = nil # reset the continuation

@outer.call nil unless @deathThroes
throw :iter_done # does this still work? TEST ME!!!
end

end
end
def iter(deathThroes=false)
ExternalIterator.new(self, deathThroes)
end
end

class Array; include Iteration; end

arr = ["foo", "bar", "baz", "qux", "florp", "bzaa", "worble"]
ex = arr.iter

puts ex.get
puts "---"
puts ex.get
puts "***"

batsman@tux-chan:/tmp$ ruby u.rb
foo
---
bar
***

--
_ _
| |__ __ _| |_ ___ _ __ ___ __ _ _ __
| '_ \ / _` | __/ __| '_ ` _ \ / _` | '_ \
| |_) | (_| | |_\__ \ | | | | | (_| | | | |
|_.__/ \__,_|\__|___/_| |_| |_|\__,_|_| |_|
Running Debian GNU/Linux Sid (unstable)
batsman dot geo at yahoo dot com

Sic transit discus mundi
-- From the System Administrator's Guide, by Lars Wirzenius

[Julian Snitow]

Presumably you'd test for nil, making this like a non-destructive
version of the shift method. (I.e., the collection itself doesn't have
to manage the state of the iteration.)

[Julian Snitow]

Not quite. ;) Array#shift returns nil when the collection is empty, so
I used that behavior, too. So once you've got nil, the iteration is
over, and any further calls to ex.get will be those of a new iteration.

[Julian Snitow]

Whoops. On testing it, you're right. The first call *does* spit out
the entire list.

@hat << Condiments::Ketchup
self.eat(@hat) # mmmm... hatty

[Julian Snitow]

Julian Snitow wrote:
> Han Holl wrote:
>
>>
>> It may be more Rubyesque, but unfortunately it doesn't work:
>>

Now that I've tested it, it appears you're right. (I've already eaten
my hat ;)

I think my mistake was to assume that return would play nicely with the
continuations (as a return defined in terms of callcc would).

[Johan Holmberg]

Gavin Sinclair <gsin...@soyabean.com.au> writes:
>
> I'd like someone, hopefully including Julian and Jim (Weirich), to
> demonstrate how to iterate over twop lists in parallel. Extra marks
> for setting a realistic example problem and solving it!
>

> Gavin
>

Maybe this is off-topic,
but I can't see anyone mentioning the 'enum' package by Joel VanderWerf.

Here is a solution to "Iterate over two lists in parallel"
using that package:

#------------------------------
require 'enum/op'
include EnumerableOperator

alist = [11, 22, 33, 44]
blist = ["a", "b", "c", "d"]
clist = 1001..1004

for a,b,c in diagonal(alist,blist,clist)
puts "got #{a}, #{b} and #{c}"
end

#------------------------------

/Johan Holmberg

[Joel VanderWerf]

It's kind of a cheat, though. Unlike the solutions using continuations,
this diagonal thing actually converts the inputs to arrays, if they
aren't already. So if you want to do parallel enumeration of infinite
sequences, such as PRNGs, you never even get the first tuple. OTOH, for
small sequences, the overhead of converting to arrays (if necessary)
might be less than the overhead of instantiating continuations. IIRC,
continuations are on the same order of magnitude as threads, in that
respect.