Forum: Ruby iterator class not working

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
Peter E. (Guest)
on 2006-03-24 14:38
(Received via mailing list)
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! :-(

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
Robert D. (Guest)
on 2006-03-24 15:17
(Received via mailing list)
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
Peter E. (Guest)
on 2006-03-24 15:28
(Received via mailing list)
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.
Pit C. (Guest)
on 2006-03-24 15:39
(Received via mailing list)
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
Robert D. (Guest)
on 2006-03-24 15:45
(Received via mailing list)
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! :-(
> > >
> > 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
;)

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
Ross B. (Guest)
on 2006-03-24 15:49
(Received via mailing list)
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:in `next'
        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.
Ross B. (Guest)
on 2006-03-24 15:54
(Received via mailing list)
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 :)

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/...
Robert D. (Guest)
on 2006-03-24 16:05
(Received via mailing list)
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
Ross B. (Guest)
on 2006-03-24 16:10
(Received via mailing list)
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.
Peter E. (Guest)
on 2006-03-24 16:26
(Received via mailing list)
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
Peter E. (Guest)
on 2006-03-24 16:28
(Received via mailing list)
really UGLY typo!!

don't take it personal :-)

> optimization and alternatives from you gu_t_s. Afterall

guys!!!!!
Peter E. (Guest)
on 2006-03-24 16:28
(Received via mailing list)
aargh, again...

remove that line, please:

> raise "done" if @done
Robert D. (Guest)
on 2006-03-24 16:43
(Received via mailing list)
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
Peter E. (Guest)
on 2006-03-24 16:53
(Received via mailing list)
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
Ross B. (Guest)
on 2006-03-24 17:07
(Received via mailing list)
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 ... :)

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 :)

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.
Robert D. (Guest)
on 2006-03-24 17:23
(Received via mailing list)
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
Pit C. (Guest)
on 2006-03-24 18:14
(Received via mailing list)
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
Nate Smith (Guest)
on 2006-03-24 18:22
(Received via mailing list)
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
unknown (Guest)
on 2006-03-24 18:32
(Received via mailing list)
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
Peter E. (Guest)
on 2006-03-24 18:33
(Received via mailing list)
whoa, amazing + surprising!!!

now, I have to check that code again ... :-)
Mike S. (Guest)
on 2006-03-24 18:43
(Received via mailing list)
On 24-Mar-06, at 11:32 AM, removed_email_address@domain.invalid wrote:

>
>
> you are just saying
>
>   1 + (+(+(+3)))
>
>
> in otherwords you have made 3 __very__ positive.  [...]

But be aware that ----4 doesn't make 4 very negative.

The unary + and - are useful, making

   x = -5

a little more conventional looking and convenient to write than

   x = 0 - 5

Mike

--

Mike S. <removed_email_address@domain.invalid>
http://www.stok.ca/~mike/

The "`Stok' disclaimers" apply.
This topic is locked and can not be replied to.