Asp Forum - Ruby design question: lazy construction of object graph containing forward references

Its Me

1/6/2005 6:59:00 AM

Seeking help, Ruby gurus ...

Consider the following Ruby object graph being constructed. It has forward
references in line (2) and (3) to x.forward_ref, something that will only
come into existence in line (7). It has a reference in line (4) and (5) to
an as-yet unresolved forward reference from line (2). And it operates on an
unresolved reference on line (6).

1) x = OpenStruct.new
2) y = OpenStruct.new(:f0 => x, :f1=>x.forward_ref)
3) z = [x, y, x.forward_ref]
4) w = y.f1
5) foo(y.f1)
6) bar(y.f1.f2)
7) x.forward_ref = Object.new

I want to build such structures lazily, but be lazy only when the laziness
is needed i.e. not for :f0=>x, or [x, y, ...], or y.f1. And I would like to
force resolution of (selected or all) unresolved references either:
a) at a time of my choosing (raising exceptions if needed), or
b) incrementally whenever a given reference becomes resolvable, or
c) when something is done with that reference i.e. some method invoked on it
(line 6).

I can assume that all accessors are just that: accessors i.e. no worry about
changing the order of mutator operations. The graph gets built monotonically
i.e. all slots are either uninitialized, or initialized, but not modified
once initialized.

I can assume that 'nil' is a distinguished sentinel value indicating an
uninitialized slot (instance variables, array at some index, hash value at
some key), but I don't know how much that will help for nil.method_missing
since even nil has a whole heap of defined methods. I can change any of the
assignment methods as needed.

What would be a good way to accomplish this? I was thinking I could create a
trail of proc-like things representing bits of suspended computation (a bit
like 'futures'), but can't really figure out how, or if it would be a good
approach. Do continuations offer some magic that would help?

Thanks!

10 Answers

Its Me

1/6/2005 8:48:00 AM

"itsme213" <itsme213@hotmail.com> wrote in message
news:kl5Dd.1593$ho.126@fe2.texas.rr.com...

> 1) x = OpenStruct.new
> 2) y = OpenStruct.new(:f0 => x, :f1=>x.forward_ref)
> 3) z = [x, y, x.forward_ref]
> 4) w = y.f1
> 5) foo(y.f1)
> 6) bar(y.f1.f2)
> 7) x.forward_ref = Object.new
>
> I want to build such structures lazily, but be lazy only when the laziness
> is needed i.e. not for :f0=>x, or [x, y, ...], or y.f1.

Oops, typo: should have been "..., or [x, y, ...], but lazy for y.f1".

Florian Gross

1/6/2005 2:11:00 PM

itsme213 wrote:

> I want to build such structures lazily, but be lazy only when the laziness
> is needed i.e. not for :f0=>x, or [x, y, ...], or y.f1. And I would like to
> force resolution of (selected or all) unresolved references either:
> a) at a time of my choosing (raising exceptions if needed), or
> b) incrementally whenever a given reference becomes resolvable, or
> c) when something is done with that reference i.e. some method invoked on it
> (line 6).

I'm not sure if I'm overlooking something, but I'd use blocks for this.
E.g.

foo = LazyStruct.new
bar = LazyStruct.new
foo.bar { bar.foo }
bar.foo = 5

Pardon the poor example. Does this make sense?

Its Me

1/6/2005 3:22:00 PM

"Florian Gross" <flgr@ccan.de> wrote in message
news:344v8dF44miunU2@individual.net...
> itsme213 wrote:
>
> > I want to build such structures lazily, but be lazy only when the
laziness
> > is needed i.e. not for :f0=>x, or [x, y, ...], or y.f1. And I would like
to
> > force resolution of (selected or all) unresolved references either:
> > a) at a time of my choosing (raising exceptions if needed), or
> > b) incrementally whenever a given reference becomes resolvable, or
> > c) when something is done with that reference i.e. some method invoked
on it
> > (line 6).
>
> I'm not sure if I'm overlooking something, but I'd use blocks for this.
> E.g.
>
> foo = LazyStruct.new
> bar = LazyStruct.new
> foo.bar { bar.foo }
> bar.foo = 5
>
> Pardon the poor example. Does this make sense?

It would, but I was not clear : changing the ordering of construction of the
objects and links is not an option. I could have other uses of bar.foo, or
foo.bar either before or after your code fragment.

Thanks, though!

Carlos

1/6/2005 4:18:00 PM

[itsme213 <itsme213@hotmail.com>, 2005-01-06 08.01 CET]
> Consider the following Ruby object graph being constructed. It has forward
> references in line (2) and (3) to x.forward_ref, something that will only
> come into existence in line (7). It has a reference in line (4) and (5) to
> an as-yet unresolved forward reference from line (2). And it operates on an
> unresolved reference on line (6).
>
> 1) x = OpenStruct.new
> 2) y = OpenStruct.new(:f0 => x, :f1=>x.forward_ref)
> 3) z = [x, y, x.forward_ref]
> 4) w = y.f1
> 5) foo(y.f1)
> 6) bar(y.f1.f2)
> 7) x.forward_ref = Object.new
>
> I want to build such structures lazily, but be lazy only when the laziness
> is needed i.e. not for :f0=>x, or [x, y, ...], or y.f1. And I would like to
> force resolution of (selected or all) unresolved references either:
> a) at a time of my choosing (raising exceptions if needed), or
> b) incrementally whenever a given reference becomes resolvable, or
> c) when something is done with that reference i.e. some method invoked on it
> (line 6).

Why not delegators?

Anyway, I can't make the delegator to reinitialize with a new object :(.
Need to study delegators... I don't even know what's happening in my code!

require 'delegate'

class RawOpenStruct
def method_missing name, *args
name = name.id2name
setter = name.sub!(/=$/, "")
iv = "@"+name
if instance_variables.include? iv
del = instance_variable_get(iv)
if setter
del.__send__ :initialize, args.first
else
return del
end
else
if setter
del = SimpleDelegator.new args.first
else
del = SimpleDelegator.new MySuperVivifier.new
del.__getobj__.__setdelegator__ del
end
return instance_variable_set(iv, del)
end
end
end

class MySuperVivifier
def method_missing name, *args
# vivify!
name = name.id2name
# the following __send__ :initialize only sets the object
# it doesn't create the methods.
# and also the methods __setdelegator__ and method_missing
# should be deleted
# I need study delegators :))
@delegator.__send__ :initialize, 42

@delegator.__getobj__.__send__ name.to_sym, *args
end

def __setdelegator__ delegator
@delegator=delegator
end
end

x = RawOpenStruct.new
y = RawOpenStruct.new
y.f1 = x.forward_ref
z = [x, y, x.forward_ref]
w = y.f1
p y.f1
p y.f1 + 34
p y.f1.methods
p y.f1.class
p y.f1.class.ancestors
p y.f1.size # BOOM!
x.forward_ref = Object.new

Assaph Mehr

1/6/2005 11:37:00 PM

Here's an implementation of lazy forward references. Notice that if you
assign to a variable before reading it, the previous lazy
initialization will be overwritten.

__BEGIN CODE__
class Object
def singleton_class
class << self; self; end
end
end

module LazyForwardRef
def forward_ref(meth, &bl)
self.singleton_class.send :define_method, meth, lambda{
self.singleton_class.send :define_method, meth, lambda {
self.singleton_class.send :attr_accessor, meth
instance_variable_set "@#{meth}", bl.call
}
return send(meth)
}
self.singleton_class.send :define_method, "#{meth}=", lambda{
|args|
self.singleton_class.send :define_method, meth, lambda {
self.singleton_class.send :attr_accessor, meth
instance_variable_set "@#{meth}", *args
}
return send(meth)
}
end
end

require 'pp'

x = Object.new
x.extend LazyForwardRef

begin
p x.foo
rescue NoMethodError => detail
pp detail
pp [x, x.methods.sort - Object.instance_methods]
end

x.forward_ref(:foo) { Hash[1,2,3,4] }
pp [x, x.methods.sort - Object.instance_methods]

p x.foo
pp [x, x.methods.sort - Object.instance_methods]

x.foo = 'Something else'
pp x

p x.foo

puts "\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n\n"

y = Object.new
y.extend LazyForwardRef

y.forward_ref(:bar) { [1,2,3,4] }
pp [y, y.methods.sort - Object.instance_methods]
y.bar= 10
pp [y, y.methods.sort - Object.instance_methods]
p y.bar

Its Me

1/7/2005 5:46:00 PM

Wow! Self-modifying code makes my head spin. It seems to almost do logical
variable (1-way) unification. Could it be adapted to get the behavior I want
below?

x = Object.new; x.extend LazyForwardRef
x.forward_ref(:foo)
p x.foo #=> something for 'uninitialized'

y = Object.new; y.extend LazyForwardRef
y.forward_ref(:bar)
p y.bar #=> something for 'uninitialized'
x.foo = y.bar
p x.foo #=> something for 'suspended/lazy'

y.bar = 10

p y.bar #=> 10
p x.foo #=> 10 (or still 'suspended/lazy' if 10 is too difficult)

x.resolve_ref(:foo)
p x.foo #=> 10

Many thanks.

"Assaph Mehr" <assaph@gmail.com> wrote in message
news:1105054617.978569.32830@f14g2000cwb.googlegroups.com...
> Here's an implementation of lazy forward references. Notice that if you
> assign to a variable before reading it, the previous lazy
> initialization will be overwritten.
>
> __BEGIN CODE__
> class Object
> def singleton_class
> class << self; self; end
> end
> end
>
> module LazyForwardRef
> def forward_ref(meth, &bl)
> self.singleton_class.send :define_method, meth, lambda{
> self.singleton_class.send :define_method, meth, lambda {
> self.singleton_class.send :attr_accessor, meth
> instance_variable_set "@#{meth}", bl.call
> }
> return send(meth)
> }
> self.singleton_class.send :define_method, "#{meth}=", lambda{
> |args|
> self.singleton_class.send :define_method, meth, lambda {
> self.singleton_class.send :attr_accessor, meth
> instance_variable_set "@#{meth}", *args
> }
> return send(meth)
> }
> end
> end
>
>
> require 'pp'
>
> x = Object.new
> x.extend LazyForwardRef
>
> begin
> p x.foo
> rescue NoMethodError => detail
> pp detail
> pp [x, x.methods.sort - Object.instance_methods]
> end
>
>
> x.forward_ref(:foo) { Hash[1,2,3,4] }
> pp [x, x.methods.sort - Object.instance_methods]
>
> p x.foo
> pp [x, x.methods.sort - Object.instance_methods]
>
> x.foo = 'Something else'
> pp x
>
> p x.foo
>
> puts "\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n\n"
>
> y = Object.new
> y.extend LazyForwardRef
>
> y.forward_ref(:bar) { [1,2,3,4] }
> pp [y, y.methods.sort - Object.instance_methods]
> y.bar= 10
> pp [y, y.methods.sort - Object.instance_methods]
> p y.bar
>

georgesawyer

1/9/2005 1:45:00 AM

"itsme213" <itsme213@hotmail.com> Jan 6, 2005 at 06:59 AM wrote:
>Consider [a kind of] Ruby object graph being constructed .... The
>graph gets built monotonically; i.e., all slots are either
>uninitialized, or initialized, but not modified once initialized.

I recommend Ruby constants.

>I would like to force resolution of (selected or all) unresolved
>references, either:
>a) at a time of my choosing (raising exceptions if needed), or
>b) incrementally whenever a given reference becomes resolvable, or
>c) when something is done with that reference, i.e. some method
> [is] invoked on it ....

>I can assume that 'nil' is a distinguished sentinel value
>indicating an uninitialized slot, ... but I don't know how much
>that will help .... [E]ven nil has a whole heap of defined
>methods. I can change any of the assignment methods as needed.

Or perhaps not nil, as below.

>What would be a good way to accomplish this? I was thinking I
>could create a trail of proc-like things representing bits of
>suspended computation (a bit like 'futures')

Cool!

>but can't really figure ... if it would be a good approach. Do
>continuations offer some magic that would help?

The following dynamic capability can support, I believe,
your graph:

=>class A ;end
=>A::B =5
=>print A.const_defined?( :B) ;A.const_defined? :C
truefalse

=>class A ;remove_const( :B) ;end
=>A.const_defined? :B
false

The class Module is the parent class of the class Class. Module
defines these methods.

georgesawyer

1/9/2005 1:45:00 AM

Assaph Mehr

1/9/2005 11:17:00 PM

Here's a (rather naive) implementation of what you specify. Please note
the following:
- The syntax is a bit kludgy, since you assign using a block.
- The order in which you call the dereference is important. See the
last bit for an example.
- The previous implementation did the dereference on the first call.
This version requires explicit dereference. This is the only way I can
think of to solve the situation where some of the calls to y.bar need
to return the forward reference (a block) and some need to return the
value (after dereferencing).

One (very ugly) way to solve some of this is with a global reference
store. Unfortunately, blocks recieving blocks is still not available in
1.8. Am not sure what the final syntax and format will be in 2.0.

Cheers,
Assaph

ps. sorry for the lack of code formatting. Blame the google groups web
interface.

__BEGIN_CODE__

class Object
def singleton_class
class << self; self; end
end
end

module LazyForwardRef

def self.extended o
o.instance_variable_set '@forward_references', Hash.new
end

def forward_ref sym, &val_block
def val_block.to_s() 'suspended' end if val_block
@forward_references[sym] = val_block
end

def resolve_references
@forward_references.each do |sym, val_block|
self.singleton_class.send :attr_accessor, sym
self.send "#{sym}=", val_block.call
end
end

def method_missing sym, *args
if sym.to_s =~ /=$/
val_block = args.first
def val_block.to_s() 'suspended' end if val_block
@forward_references[sym] = val_block
elsif Proc === @forward_references[sym]
@forward_references[sym]
else
'uninitialized'
end
end
end

x = Object.new; x.extend LazyForwardRef
x.forward_ref(:foo)
p x.foo #=> something for 'uninitialized'

y = Object.new; y.extend LazyForwardRef
y.forward_ref(:bar)
p y.bar #=> something for 'uninitialized'

x.forward_ref(:foo) { y.bar }
p x.foo #=> something for 'suspended/lazy'

y.forward_ref(:bar) { 10 }

p y.bar #=> still suspended
y.resolve_references
p y.bar #=> 10

p x.foo #=> 10 (or still 'suspended/lazy' if 10 is too difficult)

x.resolve_references
p x.foo #=> 10

puts '--- wrong resolve order ---'
x = Object.new; x.extend LazyForwardRef
y = Object.new; y.extend LazyForwardRef
x.forward_ref(:qux) { y.qux }
y.forward_ref(:qux) { 'qux' }
x.resolve_references
p x.qux
y.resolve_references
p y.qux
p x.qux
x.resolve_references
p x.qux

georgesawyer

1/14/2005 10:51:00 PM

Instead of (class-scoped) constants, I think they must be frozen object
variables.

comp.lang.ruby

Ruby design question: lazy construction of object graph containing forward references

Its Me

Its Me

Florian Gross

Its Me

Carlos

Assaph Mehr

Its Me

georgesawyer

georgesawyer

Assaph Mehr

georgesawyer

x Login to ForumsZone