Iterator class not working


#1

Hi,

in order to understand ruby better (and for fun reasons of course) I try
to
write an iterator class. this way I want to understand ‘binding’ and
‘callcc’ better.

however, it does not work! :frowning:

any help will be greatly appreciated!!!


class Iterator

def initialize(enum)
@context = binding
end

def next
enum = eval(“enum”, @context)
@context, item = callcc do |cont|
enum.each do |item|
cont.call binding, item
end
end
item
end

end

names = %w{mary gordy john jane elwood}

it = Iterator.new(names)

3.times do
puts it.next
end

mary
mary
mary

Best regards
Peter


#2

On 3/24/06, Peter E. removed_email_address@domain.invalid wrote:

any help will be greatly appreciated!!!
enum = eval(“enum”, @context)
@context, item = callcc do |cont|
enum.each do |item|
cont.call binding, item

                    ^
                    |

------------------------+
you are missing “state” here, each time you call next, you start to
iterate
over your “enum” and
jump out of the iterator at the first iteration, that is giving you
“mary”
all the time.

  end

3.times do

Well I see why it does not work, but I fail to see your design behind
the
thing
it could be done like this
class Iterator
def initialize(*args); @items=args;@i=-1;end

def next

@i+=1; return @items[@i] unless block_given?; yield @items[@i]; end
end
but I do not really know what that would be good for.

Cheers
Robert


Deux choses sont infinies : l’univers et la bêtise humaine ; en ce qui
concerne l’univers, je n’en ai pas acquis la certitude absolue.

  • Albert Einstein

#3

Hello Robert,

thanks for your feedback.

Yield’ing and using Array.[] seems obvious but I want class ‘Iterator’
to
work for any ‘Enumerable’, not only ‘Array’.

The intention for using ‘binding’ is that I expect / hope it will keep
track
of the enumeration state inside ‘Enumeration.each’. However, I don’t
know if
that’s possible in ruby at all.


#4

Peter E. schrieb:

Yield’ing and using Array.[] seems obvious but I want class ‘Iterator’ to
work for any ‘Enumerable’, not only ‘Array’.

The intention for using ‘binding’ is that I expect / hope it will keep track
of the enumeration state inside ‘Enumeration.each’. However, I don’t know if
that’s possible in ruby at all.

Peter, I think you can’t use bindings for that. All the continuations
based iterator implementations I’ve seen use at least two continuations.
You can find them in the mailing list archives. Of course that’s much
less fun than implementing it for yourself.

Regards,
Pit


#5

On 3/24/06, Peter E. removed_email_address@domain.invalid wrote:

of the enumeration state inside ‘Enumeration.each’. However, I don’t know

however, it does not work! :frowning:

you are missing “state” here, each time you call next, you start to

end

thing
Robert


Deux choses sont infinies : l’univers et la bêtise humaine ; en ce qui
concerne l’univers, je n’en ai pas acquis la certitude absolue.

  • Albert Einstein

and you want lazy evaluation, converting the Enumeration into an array
is
not an option, right?
I think what we need here are coroutines and we do not have them (yet).
I fail to see a solution, hopefully somebody brighter will enlighten us
:wink:

Cheers
Robert


Deux choses sont infinies : l’univers et la bêtise humaine ; en ce qui
concerne l’univers, je n’en ai pas acquis la certitude absolue.

  • Albert Einstein

#6

On Fri, 2006-03-24 at 21:38 +0900, Peter E. wrote:

Hi,

in order to understand ruby better (and for fun reasons of course) I try to
write an iterator class. this way I want to understand ‘binding’ and
‘callcc’ better.

Here is a slightly modified version of your code that doesn’t cover
everything, but should get you going in the right direction.

code

class Iterator
def initialize(enum)
@yield = lambda do
enum.each do |item|
@yield = callcc { |cc|
@next.call cc, item
}
end
raise “Exhausted”
end
end

def next
@yield, item = callcc do |cc|
@next = cc
@yield.call
end
item
end
end

names = %w{mary gordy john jane elwood}

it = Iterator.new(names)

6.times do
puts it.next
end

outputs

mary
gordy
john
jane
elwood
-:9:in initialize': Exhausted (RuntimeError) from -:16:innext’
from -:14:in `next’
from -:27
from -:26

All you need to bear in mind when using continuations this way is that
what you’re effectively needing is to ‘emulate’ two call stacks on a
single thread (maybe your ‘next’ stack and your ‘yield’ stack) and to
chop between them by calling the appropriate continuation.

In some respects it’s similar to having two threads in a synchronized
stop/start setup, which is another way you can implement the above. In
fact…

http://www.rubyquiz.com/quiz66.html

I’ll leave the details (proper end handling and so on) to you. Btw, I
know this doesn’t use binding but I found that to be a fairly
unintuitive way to do it. The binding use in your original code was fine
in itself I think, but you can’t use it to retain state the way I think
you were hoping for.


#7

On Fri, 2006-03-24 at 22:45 +0900, Robert D. wrote:

I think what we need here are coroutines and we do not have them (yet).

A while ago, while rather more bored than I’d have liked, I came up with
a toy coroutine idea that was kind of fun for a bit :slight_smile:

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/180136


#8

On 3/24/06, Ross B. removed_email_address@domain.invalid wrote:


Ross B. - removed_email_address@domain.invalid

Well it really will take me hours to figure your magic out, but looks
like
coroutines to me.
This is really impressive.
Cheers


Deux choses sont infinies : l’univers et la bêtise humaine ; en ce qui
concerne l’univers, je n’en ai pas acquis la certitude absolue.

  • Albert Einstein

#9

Just a small fix:

On Fri, 2006-03-24 at 22:49 +0900, Ross B. wrote:

def initialize(enum)
@yield = lambda do
enum.each do |item|

  •   @yield = callcc { |cc|
    
  •   callcc { |cc|
    
      @next.call cc, item
    }
  end
  raise "Exhausted"
end

end

Doesn’t really hurt (as currently written) but it’s unnecessary and
could cause confusion.


#10

Thanks for all you help.

Finally, using two nested continuations works well…

Here’s my working code … I am very curious about
optimization and alternatives from you guts. Afterall
I found this issue a very exciting one!!

class Iterator

def initialize(obj, method = :each)
@obj = obj
@method = method
end

def next
raise “done” if @done
@iteration.call if @iteration
@iteration, @current = callcc do |loop|
@obj.send(@method) do |item|
callcc do |state|
loop.call state, item
end
end
nil
end
@current
end

end

names = %w{peter paul mary gordy john jane elwood}

it = Iterator.new(names)
while item = it.next
puts item
end

it = Iterator.new(“Teststring”, :each_byte)
while item = it.next
puts item.chr
end

peter
paul
mary
gordy
john
jane
elwood
T
e
s
t
s
t
r
i
n
g


#11

really UGLY typo!!

don’t take it personal :slight_smile:

optimization and alternatives from you gu_t_s. Afterall

guys!!!


#12

aargh, again…

remove that line, please:

raise “done” if @done


#13

On 3/24/06, Ross B. removed_email_address@domain.invalid wrote:

    }
  end
  raise "Exhausted"
end

end

Doesn’t really hurt (as currently written) but it’s unnecessary and
could cause confusion.


Ross B. - removed_email_address@domain.invalid

Well I got it!
Was I missing something or is my solution really better?

---------------------------------- 8< --------------------------
class Iterator
class Exhausted < Exception; end
def initialize( enum )
@enum = enum
@next = nil
end

def next
    return @next.call if @next
    @enum.each do
        |item|
        callcc{ |cc|
            @next = cc
            return item
        }
    end # do
    raise Exhausted, "No more items :("
end # def next

end # class Iterator

i = Iterator.new( %w{ Ringo John P. George } )
loop do; puts i.next; end


Deux choses sont infinies : l’univers et la bêtise humaine ; en ce qui
concerne l’univers, je n’en ai pas acquis la certitude absolue.

  • Albert Einstein

#14

Indeed, you topped my solution my needing one callcc less…

I allowed myself to change it a little so it will return
nil once the enumeration is done and does not need exceptions:

class Iterator
def initialize( enum )
@enum = enum
@next = nil
end

def next
@next.call if @next
@enum.each do |item|
callcc do |cc|
@next = cc
return item
end
end
nil
end
end

i = Iterator.new( %w{ Ringo John P. George } )

while item = i.next
puts item
end


#15

On Fri, 2006-03-24 at 23:43 +0900, Robert D. wrote:

Well I got it!
Was I missing something or is my solution really better?

Well, if you’re going to cheat and use return … :slight_smile:

Seriously though, I like that one. Shows how it’s important to remember
the ‘normal’ stuff when you’re thinking in this high level stuff :slight_smile:

And yes, I guess it is better:

  user     system      total        real

Iterator1 4.730000 0.040000 4.770000 ( 4.877037)
Iterator2 2.840000 0.050000 2.890000 ( 2.960747)
Iterator3 2.800000 0.130000 2.930000 ( 2.998121)
Iterator4 2.040000 0.020000 2.060000 ( 2.131763)

(1 = my updated, easy to follow version of Peter’s original, 2 = same
version with one callcc and one catch, 3 = Peter’s second
implementation, 4 = your callcc/return implementation)

As you can see, though, they’re all pretty slow when it comes right down
to it (this was only over (0…50000).to_a) - some of the
FasterGenerator quiz entries I mentioned achieved quite amazing speeds
over that many iterations and more - you should check them out.


#16

On 3/24/06, Ross B. removed_email_address@domain.invalid wrote:

implementation, 4 = your callcc/return implementation)
I have no merit than ;), no it is true that I have not understood a bit of
your continuation stuff, when I realized what callcc really does, I
realized
that I was wrong about the coroutines.
Ty for the acknowledgement but I learnt it from your code!
Cheers


Deux choses sont infinies : l’univers et la bêtise humaine ; en ce qui
concerne l’univers, je n’en ai pas acquis la certitude absolue.

  • Albert Einstein

#17

Peter E. schrieb:

class Iterator

end

i = Iterator.new( %w{ Ringo John P. George } )

while item = i.next
puts item
end

Peter, test your code with

puts i.next
puts i.next

I don’t think you can get away with only one continuation.

Regards,
Pit


#18

Hello,

What is the benefit in ruby of allowing the following syntax:

in irb:

irb(main):005:0> 1 + + + + 3
=> 4
irb(main):006:0> 1 + - + 3
=> -2
irb(main):007:0> 1 - - - - 3
=> 4
irb(main):008:0> 1 - + - 3
=> 4
irb(main):010:0> 1 - ±3
=> 4

Is this a feature or a gotcha?

Nate


#19

On Sat, 25 Mar 2006, Nate Smith wrote:

Hello,

What is the benefit in ruby of allowing the following syntax:

in irb:

irb(main):005:0> 1 + + + + 3
=> 4

you are just saying

1 + (+(+(+3)))

in otherwords you have made 3 very positive. if you could not do
that
you’d not be able to do this:

jib:~ > ruby -e’ p 41 - -1 ’
42

C is going to allow this too:

jib:~ > cat a.c && gcc a.c && a.out
main(){ printf ("%d\n", 41 + + + 1); }
42

it’s just a result of binding/associvity.

regards.

-a


#20

whoa, amazing + surprising!!!

now, I have to check that code again … :slight_smile: