Lazy evaluation

Discussion in 'Ruby' started by Michael Neumann, Apr 30, 2004.

  1. Hi,

    I am currently hacking a Packrat parser just for fun. I need to mix
    values (like numbers, strings etc.) together with lazy values. I want to
    make processing these values as transparent as possible.

    I don't want to use something like this inside my program:

    if val.is_a? Lazy
    val.value
    else
    val
    end

    Currently, I've implemented it with a ValueHolder class, and a Lazy
    class, both implementing the #value protocol:

    class Lazy
    def self.[](*args, &block)
    new(*args, &block)
    end

    def initialize(*args, &block)
    raise "no block given" if block.nil?
    @block = block
    @block_evaluated = false
    @args = args
    end

    def value
    if @block_evaluated
    @value
    else
    @block_evaluated = true
    @value = @block.call(*@args)
    @block = @args = nil # free memory
    @value
    end
    end
    end
    class ValueHolder
    attr_accessor :value

    def self.[](*args, &block)
    new(*args, &block)
    end

    def initialize(value)
    @value = value
    end
    end

    But then I have to use the value method very often and the actions the
    user of the packrat parser writes becomes hard to understand due to very
    high usage of #value.

    Another possible solution would be to use a LazyDelegator. But that too
    has some disadvantages, e.g. when doing many calculations on this value,
    or passing the value to some extension that requires this to be a String
    etc.. The ultimate solution would be a LazyDelegator which then turns
    into the actual value. IIRC, Smalltalk had some command with which an
    object could turn into some other object?

    Actually, what I'd like to have is:

    a = 5
    a.becomes("a string")
    a #=> "a string"

    Any comments or suggestions?

    Regards,

    Michael
    Michael Neumann, Apr 30, 2004
    #1
    1. Advertising

  2. At 03:45 01/05/2004 +0900, you wrote:
    >Hi,
    >
    >I am currently hacking a Packrat parser just for fun. I need to mix
    >values (like numbers, strings etc.) together with lazy values. I want to
    >make processing these values as transparent as possible.
    >
    >I don't want to use something like this inside my program:
    >
    > if val.is_a? Lazy
    > val.value
    > else
    > val
    > end
    >
    >Currently, I've implemented it with a ValueHolder class, and a Lazy
    >class, both implementing the #value protocol:
    >
    > class Lazy
    > def self.[](*args, &block)
    > new(*args, &block)
    > end
    >
    > def initialize(*args, &block)
    > raise "no block given" if block.nil?
    > @block = block
    > @block_evaluated = false
    > @args = args
    > end
    >
    > def value
    > if @block_evaluated
    > @value
    > else
    > @block_evaluated = true
    > @value = @block.call(*@args)
    > @block = @args = nil # free memory
    > @value
    > end
    > end
    > end
    > class ValueHolder
    > attr_accessor :value
    >
    > def self.[](*args, &block)
    > new(*args, &block)
    > end
    >
    > def initialize(value)
    > @value = value
    > end
    > end
    >
    >But then I have to use the value method very often and the actions the
    >user of the packrat parser writes becomes hard to understand due to very
    >high usage of #value.
    >
    >Another possible solution would be to use a LazyDelegator. But that too
    >has some disadvantages, e.g. when doing many calculations on this value,
    >or passing the value to some extension that requires this to be a String
    >etc.. The ultimate solution would be a LazyDelegator which then turns
    >into the actual value. IIRC, Smalltalk had some command with which an
    >object could turn into some other object?
    >
    >Actually, what I'd like to have is:
    >
    > a = 5
    > a.becomes("a string")
    > a #=> "a string"
    >
    >Any comments or suggestions?
    >
    >Regards,
    >
    > Michael


    Comments ? Not much. Besides the fact that we both need some kind of a
    Reference class to inherit from.

    You to do:
    class LazyValue < Reference
    ...

    Me to do:
    class LogicVariable < Reference

    In both cases we want automatic dereferencing of the object when its
    value is required.

    As far as I know the least intrusive notation is to use the [] and []=
    accessors that you can redefine. Be carefull with []=, the assigned
    value is not under its control (use xx.[]= yy syntax instead).

    I expect soon to have the issue striking again while implementing
    "Future". Kind of lazy evaluation. A "Future" is the result of a
    method call that is not available yet, but you don't mind, until
    you need it, then you block until it is available. That is a
    useful concept for distributed computing.

    BTW: I too miss Smalltalk's becomes(). Sometimes you can use
    replace(), but it is not as general (you can change the value,
    not the class).

    Yours,

    Jean-Hugues



    -------------------------------------------------------------------------
    Web: http://hdl.handle.net/1030.37/1.1
    Phone: +33 (0) 4 92 27 74 17
    Jean-Hugues ROBERT, Apr 30, 2004
    #2
    1. Advertising

  3. Jean-Hugues ROBERT wrote:

    > BTW: I too miss Smalltalk's becomes(). Sometimes you can use
    > replace(), but it is not as general (you can change the value,
    > not the class).


    We're working on it: http://evil.rubyforge.org/

    > Yours,
    > Jean-Hugues


    Regards,
    Florian Gross
    Florian Gross, Apr 30, 2004
    #3
  4. On Sat, May 01, 2004 at 05:38:03AM +0900, Jean-Hugues ROBERT wrote:
    > At 03:45 01/05/2004 +0900, you wrote:
    > >Hi,
    > >
    > >I am currently hacking a Packrat parser just for fun. I need to mix
    > >values (like numbers, strings etc.) together with lazy values. I want to
    > >make processing these values as transparent as possible.
    > > [...]
    > >Any comments or suggestions?
    > >
    > >Regards,
    > >
    > > Michael

    >
    > Comments ? Not much. Besides the fact that we both need some kind of a
    > Reference class to inherit from.
    >
    > You to do:
    > class LazyValue < Reference
    > ...
    >
    > Me to do:
    > class LogicVariable < Reference
    >
    > In both cases we want automatic dereferencing of the object when its
    > value is required.


    Something like the Delegator class in delegate.rb is useful.
    I wrote my own lazy version:

    class Lazy
    self.methods.reject{|m| m =~ /^__(.*)__$/}.each {|m|
    eval "def #{m}(*args, &block) __getobj__.send:)'#{m}', *args, &block) end"
    }

    def initialize(*args, &block)
    raise "no block given" if block.nil?
    @args, @block = args, block
    end

    def __getobj__
    if @block
    @value = @block.call(*@args)
    @block = @args = nil
    end
    return @value
    end

    def marshal_dump
    __getobj__
    end

    def marshal_load(obj)
    @value = obj
    end

    def method_missing(id, *args, &block)
    __getobj__.send(id, *args, &block)
    end
    end

    And to replace all Lazy objects with their values, I can now use
    obj = Marshal.load(Marshal.dump(obj)).

    > As far as I know the least intrusive notation is to use the [] and []=
    > accessors that you can redefine. Be carefull with []=, the assigned
    > value is not under its control (use xx.[]= yy syntax instead).


    Hm, don't really understand that.

    > I expect soon to have the issue striking again while implementing
    > "Future". Kind of lazy evaluation. A "Future" is the result of a
    > method call that is not available yet, but you don't mind, until
    > you need it, then you block until it is available. That is a
    > useful concept for distributed computing.


    Hm, sounds a bit like Oz :) or similar to promises in E-lang?

    Regards,

    Michael
    Michael Neumann, Apr 30, 2004
    #4
  5. Michael Neumann

    Phil Tomson Guest

    Re: Lazy evaluation (evil)

    In article <c6uh31$gaq2i$-berlin.de>,
    Florian Gross <> wrote:
    >Jean-Hugues ROBERT wrote:
    >
    >> BTW: I too miss Smalltalk's becomes(). Sometimes you can use
    >> replace(), but it is not as general (you can change the value,
    >> not the class).

    >
    >We're working on it: http://evil.rubyforge.org/


    Just took a quick look at evil.

    So is the intent to use Ruby/DL to load the ruby.so (or ruby.dll) that
    gets created when you compile Ruby to be a shared lib?
    I had a similar idea... good to see someone try it.

    Any user docs?


    Phil
    Phil Tomson, May 1, 2004
    #5
  6. Re: Lazy evaluation (evil)

    Phil Tomson wrote:

    >> http://evil.rubyforge.org/

    > Just took a quick look at evil.
    >
    > So is the intent to use Ruby/DL to load the ruby.so (or ruby.dll) that
    > gets created when you compile Ruby to be a shared lib?


    We're not using that yet -- currently all we do is use Ruby/DL to get
    pointers to the internal structure of Ruby objects.

    However using ruby.so might allow us to provide more features.

    > Any user docs?


    Not yet, but I think I'll make that a priority.

    Some interesting things to try out:

    class Qux; end; class Bar; end
    class Foo
    inherit Qux
    inherit Bar
    # you now have a class which inherits from both Qux and Bar
    end

    obj = "foobar"; obj.freeze
    obj.unfreeze; obj.reverse!

    obj_a = Object.new
    obj_a.instance_eval { @a = 5 }
    obj_b = Object.new
    obj_b.become(obj_a)
    obj_b.instance_eval { @a } # => 5

    object_klass = Object.clone
    object_klass.class = Object

    x = KernellessObject.new
    x.methods # => undefined method methods

    There's more and I'm pretty sure that we'll soon be able to provide more.

    Regards,
    Florian Gross
    Florian Gross, May 1, 2004
    #6
  7. At 06:47 01/05/2004 +0900, you wrote:
    >On Sat, May 01, 2004 at 05:38:03AM +0900, Jean-Hugues ROBERT wrote:
    > > At 03:45 01/05/2004 +0900, you wrote:
    > > >Hi,
    > > >
    > > >I am currently hacking a Packrat parser just for fun. I need to mix
    > > >values (like numbers, strings etc.) together with lazy values. I want to
    > > >make processing these values as transparent as possible.
    > > > [...]
    > > >Any comments or suggestions?
    > > >
    > > >Regards,
    > > >
    > > > Michael

    > >
    > > Comments ? Not much. Besides the fact that we both need some kind of a
    > > Reference class to inherit from.
    > >
    > > You to do:
    > > class LazyValue < Reference
    > > ...
    > >
    > > Me to do:
    > > class LogicVariable < Reference
    > >
    > > In both cases we want automatic dereferencing of the object when its
    > > value is required.

    >
    >Something like the Delegator class in delegate.rb is useful.
    >I wrote my own lazy version:
    >
    > class Lazy
    > self.methods.reject{|m| m =~ /^__(.*)__$/}.each {|m|
    > eval "def #{m}(*args, &block) __getobj__.send:)'#{m}', *args,
    > &block) end"
    > }
    >
    > def initialize(*args, &block)
    > raise "no block given" if block.nil?
    > @args, @block = args, block
    > end
    >
    > def __getobj__
    > if @block
    > @value = @block.call(*@args)
    > @block = @args = nil
    > end
    > return @value
    > end
    >
    > def marshal_dump
    > __getobj__
    > end
    >
    > def marshal_load(obj)
    > @value = obj
    > end
    >
    > def method_missing(id, *args, &block)
    > __getobj__.send(id, *args, &block)
    > end
    > end


    If this is not transparent, this is very close to transparent !

    If I understand the code correctly, an instance of class Lazy delegates
    to self.__getobj__() everything. I guess that besides the fact the only the
    Lazy
    object itself implements :__getobj__, the key difference is the fact that
    the object ids are different, but you can't tell because object_id() gets
    delegated too (however __id__() can tell and __send__() is still there for
    whatever reason I need to figure out).

    This for sure works for Lazy, Future (Promise in some languages, Defered
    in some others) and any other read-only cases. This is the rvalue case.

    The lvalue case is another beast:
    def meth( x ) x = [x, "world"] end
    r = Refererence.new
    r = "Hello"
    meth( r, "World")
    p r # => Should be ["Hello", World]

    Once solved I will be able to implement LogicVariable:
    v = LogicVariable.new
    v = free
    p match [[["x"]]], [[[v]]] # True
    p v # => "x", changed as a side effect of match
    v = "y"
    p match [[["x"]]], [[[v]]] # False, "x" != "y"
    p v # => "y", unchanged

    As a reminder: I need LogicVariable to prototype a new "match" builtin
    and its "assign" variation in an RCR. "assign" does what Ruby does
    today in multiple assignments and when it assigns actual parameters
    to formal ones (for method calls and proc calls), and more. "match"
    does both assignment and comparison (when previous value already bound)

    So far I implemented:
    v = LogicPointer.new
    v.free!
    p match [[["x"]]], [[[v]]] # True
    p v[] # => "x"
    v[] = "y"
    p match [[["x"]]], [[[v]]] # False
    p v[] # => "y"
    Which is close, besides the additional []

    Thanks to your code, I think I will be able to:
    v = LogicDelegator.new
    v.free!
    p match [[["x"]]], [[[v]]] # True
    p v[] # => "x"
    v[] = "y"
    p match [[["x"]]], [[[v]]] # False
    p v # => "y", note the absence of []
    Which is one step in the good direction. Thanks.

    >And to replace all Lazy objects with their values, I can now use
    >obj = Marshal.load(Marshal.dump(obj)).


    I am sorry but I am not familiar with Marshal much yet. I guess
    you serializes and then rebuild the object, but I don't see the
    magic to make that efficient (I assumed @value was serialized too)

    > > As far as I know the least intrusive notation is to use the [] and []=
    > > accessors that you can redefine. Be carefull with []=, the assigned
    > > value is not under its control (use xx.[]= yy syntax instead).

    >
    >Hm, don't really understand that.


    a = x[] = b # a == b, whatever the value returned by method x.[]=()
    a = x.[]= b # a == value actually returned by method x.[]=()

    > > I expect soon to have the issue striking again while implementing
    > > "Future". Kind of lazy evaluation. A "Future" is the result of a
    > > method call that is not available yet, but you don't mind, until
    > > you need it, then you block until it is available. That is a
    > > useful concept for distributed computing.

    >
    >Hm, sounds a bit like Oz :) or similar to promises in E-lang?


    I guess. There are multiple names for this concept.
    http://www.c2.com/cgi/wiki?FutureObjects
    I think its called Defered in Twisted. Future must have been the
    first name, back in the mid 80s.

    >Regards,
    > Michael


    Thanks again.

    Yours,

    Jean-Hugues



    -------------------------------------------------------------------------
    Web: http://hdl.handle.net/1030.37/1.1
    Phone: +33 (0) 4 92 27 74 17
    Jean-Hugues ROBERT, May 1, 2004
    #7
  8. Michael Neumann

    ts Guest

    Re: Lazy evaluation (evil)

    >>>>> "F" == Florian Gross <> writes:

    F> obj_a = Object.new
    F> obj_a.instance_eval { @a = 5 }
    F> obj_b = Object.new
    F> obj_b.become(obj_a)
    F> obj_b.instance_eval { @a } # => 5

    Well, this is a P language for me this ...


    Guy Decoux
    ts, May 1, 2004
    #8
  9. Re: Lazy evaluation (evil)

    ts wrote:

    > F> obj_a = Object.new
    > F> obj_a.instance_eval { @a = 5 }
    > F> obj_b = Object.new
    > F> obj_b.become(obj_a)
    > F> obj_b.instance_eval { @a } # => 5
    >
    > Well, this is a P language for me this ...


    It should look more like a very powerful S language which is a major
    influence of Ruby to you.

    Regards,
    Florian Gross
    Florian Gross, May 1, 2004
    #9
  10. Michael Neumann

    ts Guest

    Re: Lazy evaluation (evil)

    >>>>> "F" == Florian Gross <> writes:

    F> It should look more like a very powerful S language which is a major
    F> influence of Ruby to you.

    I hope that you've seen what you are trying to solve


    Guy Decoux
    ts, May 1, 2004
    #10
  11. Re: Lazy evaluation (evil)

    Florian Gross <> wrote:
    > ts wrote:
    > >
    > > Well, this is a P language for me this ...

    >
    > It should look more like a very powerful S language which is a major
    > influence of Ruby to you.



    What is S and P language ?

    --
    Simon Strandgaard
    Simon Strandgaard, May 1, 2004
    #11
  12. Re: Lazy evaluation (evil)

    il Sat, 1 May 2004 18:30:59 +0900, Simon Strandgaard
    <> ha scritto::


    >What is S and P language ?


    well, S should stand for smalltalk, p should be..
    dunno.. I believe perl
    gabriele renzi, May 1, 2004
    #12
  13. Re: Lazy evaluation (evil)

    ts wrote:

    > I hope that you've seen what you are trying to solve


    I'm not solving, I'm providing. It is interesting to see how this gets
    used to solve or provide yet more, however.

    Regards,
    Florian Gross
    Florian Gross, May 1, 2004
    #13
  14. Michael Neumann

    ts Guest

    Re: Lazy evaluation (evil)

    >>>>> "F" == Florian Gross <> writes:

    F> I'm not solving, I'm providing.

    Then, like I've said, it's a P language


    Guy Decoux
    ts, May 1, 2004
    #14
  15. Re: Lazy evaluation (evil)

    Simon Strandgaard wrote:

    >Florian Gross <> wrote:
    >
    >
    >>ts wrote:
    >>
    >>
    >>> Well, this is a P language for me this ...
    >>>
    >>>

    >>It should look more like a very powerful S language which is a major
    >>influence of Ruby to you.
    >>
    >>

    >
    >
    >What is S and P language ?
    >
    >


    I'm guessing that

    S = Smalltalk
    P = Perl

    --
    Mark Sparshatt
    Mark Sparshatt, May 1, 2004
    #15
  16. On Sat, May 01, 2004 at 05:36:06PM +0900, Jean-Hugues ROBERT wrote:
    >
    > [...]
    >
    > This for sure works for Lazy, Future (Promise in some languages, Defered
    > in some others) and any other read-only cases. This is the rvalue case.
    >
    > The lvalue case is another beast:
    > def meth( x ) x = [x, "world"] end
    > r = Refererence.new
    > r = "Hello"
    > meth( r, "World")
    > p r # => Should be ["Hello", World]
    >
    > Once solved I will be able to implement LogicVariable:
    > v = LogicVariable.new
    > v = free
    > p match [[["x"]]], [[[v]]] # True
    > p v # => "x", changed as a side effect of match
    > v = "y"
    > p match [[["x"]]], [[[v]]] # False, "x" != "y"
    > p v # => "y", unchanged


    You might also have a look at the algebra module. But they are in the
    lucky position of not needing to assign to variables.

    > As a reminder: I need LogicVariable to prototype a new "match" builtin
    > and its "assign" variation in an RCR. "assign" does what Ruby does
    > today in multiple assignments and when it assigns actual parameters
    > to formal ones (for method calls and proc calls), and more. "match"
    > does both assignment and comparison (when previous value already bound)
    >
    > So far I implemented:
    > v = LogicPointer.new
    > v.free!
    > p match [[["x"]]], [[[v]]] # True
    > p v[] # => "x"
    > v[] = "y"
    > p match [[["x"]]], [[[v]]] # False
    > p v[] # => "y"
    > Which is close, besides the additional []


    Hmm, it doesn't look that bad. The [] reminds me of "cells".

    > v.free!
    > p match [[["x"]]], [[[v]]] # True
    > p v[] # => "x"
    > v[] = "y"
    > p match [[["x"]]], [[[v]]] # False
    > p v[] # => "y"
    >
    > Thanks to your code, I think I will be able to:
    > v = LogicDelegator.new
    > v.free!
    > p match [[["x"]]], [[[v]]] # True
    > p v[] # => "x"
    > v[] = "y"
    > p match [[["x"]]], [[[v]]] # False
    > p v # => "y", note the absence of []
    > Which is one step in the good direction. Thanks.


    But the problem is that "v[]" and "v" are still very different! The
    difference is not seen when using "p", as "p" calls "inspect" on the
    object, which gets delegated. But you probably don't want to use inspect
    all the time. So better use the explicit [] and []= methods.

    Personally, I'd prefer l.v and l.v= instead of l.[] and l.[]= but that
    is probably only due to very high usage of [ and ] in your example
    above.

    BTW, what are you exactly implementing?

    > >And to replace all Lazy objects with their values, I can now use
    > >obj = Marshal.load(Marshal.dump(obj)).

    >
    > I am sorry but I am not familiar with Marshal much yet. I guess
    > you serializes and then rebuild the object, but I don't see the
    > magic to make that efficient (I assumed @value was serialized too)


    It's just a "deep_clone". All Lazy objects marshal @value instead of
    itself, thus after Marshal.load there are no more Lazy objects. You are
    in the same situation as if you had replaced all Lazy objects with their
    value object via "become". Of course this is only useful if you're doing
    heavy calculations on the data (not sure whether it makes sense for an
    AST).

    Regards,

    Michael
    Michael Neumann, May 1, 2004
    #16
  17. Re: Lazy evaluation (evil)

    On Sat, May 01, 2004 at 06:30:59PM +0900, Simon Strandgaard wrote:
    > Florian Gross <> wrote:
    > > ts wrote:
    > > >
    > > > Well, this is a P language for me this ...

    > >
    > > It should look more like a very powerful S language which is a major
    > > influence of Ruby to you.

    >
    >
    > What is S and P language ?


    I guess, it stands for Smalltalk and Perl.

    Regards,

    Michael
    Michael Neumann, May 1, 2004
    #17
  18. Re: Lazy evaluation (evil)

    ts wrote:

    >>>>>>"F" == Florian Gross <> writes:

    >
    >
    > F> I'm not solving, I'm providing.
    >
    > Then, like I've said, it's a P language


    So Ruby is a P language because it has callcc?

    Regards,
    Florian Gross
    Florian Gross, May 1, 2004
    #18
  19. Michael Neumann

    ts Guest

    Re: Lazy evaluation (evil)

    >>>>> "F" == Florian Gross <> writes:

    F> So Ruby is a P language because it has callcc?

    No, ruby is a R language :)


    Guy Decoux
    ts, May 1, 2004
    #19
  20. Re: Lazy evaluation (evil)

    ts wrote:

    > F> So Ruby is a P language because it has callcc?
    > No, ruby is a R language :)


    What's the difference between P and R language in this case then if it
    is not that a feature should try to solve concrete problems?

    Regards,
    Florian Gross
    Florian Gross, May 1, 2004
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    3
    Views:
    314
  2. sturlamolden
    Replies:
    9
    Views:
    724
    Antoon Pardon
    May 3, 2007
  3. Ken Pu
    Replies:
    3
    Views:
    657
    Steven D'Aprano
    Jan 16, 2009
  4. Boris Borcic
    Replies:
    0
    Views:
    535
    Boris Borcic
    Jan 16, 2009
  5. Boris Borcic
    Replies:
    0
    Views:
    535
    Boris Borcic
    Jan 16, 2009
Loading...

Share This Page