Lazy evaluation

ruby-talk
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

2

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

···

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

Web: @jhr is virteal, virtually real
Phone: +33 (0) 4 92 27 74 17

3

Michael Neumann wrote:

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 guess this is beside the point but are you sure you really need an
explicit way to encapsulate lazy values to implement packrat parsing? I
did a packrat parser some time back but it was more like “memoize for
later”; maybe I didn’t read the packrat papers enough… :wink:

Can you comment on how you use the lazy values and how they help you
write the packrat parser? From my reading of the papers he presents it
in a lazy framework but you can unroll the laziness by memoization of
the partial results of a recursive decent parser.

Regards,

Robert Feldt

4

I’m not suggesting that anyone actually do this, but I have a lazily-
evaluated object that looks something like this:

class LazyFoo
def method_missing(*args, &block)
$foo = Foo.new
$foo.send(*args, &block)
end

Kernel.instance_methods.each do |m|
  next if m == '__send__'
  next if m == '__id__'
  eval <<-END
    def #{m}(*args, &block)
      method_missing(:#{m}, *args, &block)
    end
  END
end

end

$foo = LazyFoo.new

Obviously this only works with global variables, and it doesn’t work if
you pass the variable around. IMO Object#become is a much cleaner
solution, and while there are some limitations with every Object#become
I’ve seen thus far for Ruby 1.6 and 1.8, I hope that we will have a
clean implementation of Object#become in a future version of Ruby, so
that we can have nice lazy evaluation without using delegates.

Paul

···

On Sat, May 01, 2004 at 03:45:04AM +0900, Michael Neumann wrote:

Any comments or suggestions?

5

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

6

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 :slight_smile: or similar to promises in E-lang?

Regards,

Michael

···

On Sat, May 01, 2004 at 05:38:03AM +0900, Jean-Hugues ROBERT wrote:

At 03:45 01/05/2004 +0900, you wrote:

7

Michael Neumann wrote:

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 guess this is beside the point but are you sure you really need an
explicit way to encapsulate lazy values to implement packrat parsing? I
did a packrat parser some time back but it was more like “memoize for
later”; maybe I didn’t read the packrat papers enough… :wink:

Hm, it’s probably me who didn’t read the papers enough :slight_smile:

Can you comment on how you use the lazy values and how they help you
write the packrat parser? From my reading of the papers he presents it
in a lazy framework but you can unroll the laziness by memoization of
the partial results of a recursive decent parser.

I am currently using lazy values for actions that return semantic
values. But I am not sure whether I need this or not. I’ll have to
rewrite it a bit… you can have a look at it soon (the sources are not
yet there, but I’ll try to upload them this evening):

http://rubyforge.org/projects/packrat

What I am really looking for is a easy scannerless (I don’t like tokens :slight_smile:
parser generator for Ruby. I know your Rockit parser, but I’ve admit
that I didn’t tried it too much as it seems to be a bit outdated.
Speed is not a big deal for me, just ease of use.

Regards,

Michael

···

On Mon, May 03, 2004 at 09:02:02PM +0900, Robert Feldt wrote:

8

In article c6uh31$gaq2i$1@ID-7468.news.uni-berlin.de,

···

Florian Gross flgr@ccan.de 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

9

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

···

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:

Web: http://hdl.handle.net/1030.37/1.1
Phone: +33 (0) 4 92 27 74 17

10

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

11

[…]

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

···

On Sat, May 01, 2004 at 05:36:06PM +0900, Jean-Hugues ROBERT wrote:

12

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

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

Guy Decoux

13

ts wrote:

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

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

14

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

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

Guy Decoux

15

What is S and P language ?

···

Florian Gross flgr@ccan.de 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.

–
Simon Strandgaard

16

well, S should stand for smalltalk, p should be…
dunno… I believe perl

···

il Sat, 1 May 2004 18:30:59 +0900, Simon Strandgaard neoneye@adslhome.dk ha scritto::

What is S and P language ?

17

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

18

Simon Strandgaard wrote:

···

Florian Gross flgr@ccan.de 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

19

I guess, it stands for Smalltalk and Perl.

Regards,

Michael

···

On Sat, May 01, 2004 at 06:30:59PM +0900, Simon Strandgaard wrote:

Florian Gross flgr@ccan.de 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 ?

20

What about Scheme and Python?

···

On Sat, 01 May 2004 18:30:59 +0900, Simon Strandgaard wrote:

Florian Gross flgr@ccan.de 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 ?