Your thoughts on #memo ?

[Intransition]

Like to get some thoughts on the following technique for memoization:

# Memoize a method.
#
# class MemoExample
# attr_accessor :a
# def m
# memo{ @a }
# end
# end
#
# ex = MemoExample.new
#
# ex.a = 10
# ex.m #=> 10
#
# ex.a = 20
# ex.m #=> 10
#
def memo(&block)
key = eval('__method__', block)
val = block.call
singleton_class = (class << self; self; end)
singleton_class.__send__define_method, key){ val }
val
end

Downside / upsides to the approach? Any suggestions for improvement?
Or is this just an altogether bad idea?

 

[Robert Klemme]

Like to get some thoughts on the following technique for memoization:

=A0# Memoize a method.
=A0#
=A0# =A0 class MemoExample
=A0# =A0 =A0 attr_accessor :a
=A0# =A0 =A0 def m
=A0# =A0 =A0 =A0 memo{ @a }
=A0# =A0 =A0 end
=A0# =A0 end
=A0#
=A0# =A0 ex =3D MemoExample.new
=A0#
=A0# =A0 ex.a =3D 10
=A0# =A0 ex.m =A0#=3D> 10
=A0#
=A0# =A0 ex.a =3D 20
=A0# =A0 ex.m =A0#=3D> 10
=A0#
=A0def memo(&block)
=A0 =A0key =3D eval('__method__', block)
=A0 =A0val =3D block.call
=A0 =A0singleton_class =3D (class << self; self; end)
=A0 =A0singleton_class.__send__define_method, key){ val }
=A0 =A0val
=A0end

I could not get that to work on 1.9.1:

17:33:49 ~$ irb19
Ruby version 1.9.1
irb(main):001:0> def memo(&block)
key =3D eval('__method__', block)
val =3D block.call
singleton_class =3D (class << self; self; end)
singleton_class.__send__define_method, key){ vairb(main):002:1> l }
key =3D eval('__method__', block)
irb(main):003:1> val =3D block.call
irb(main):004:1> singleton_class =3D (class << self; self; end)
irb(main):005:1> singleton_class.__send__define_method, key){ val }
irb(main):006:1> val
irb(main):007:1> end
=3D> nil
irb(main):008:0> class ME
irb(main):009:1> attr_accessor :a
irb(main):010:1> def m;memo { @a }; end
irb(main):011:1> end
=3D> nil
irb(main):012:0> ex=3DME.new
=3D> #<ME:0x10049a74>
irb(main):013:0> ex.a=3D10
=3D> 10
irb(main):014:0> ex.m
TypeError: wrong argument type Proc (expected Binding)
from (irb):2:in `eval'
from (irb):2:in `memo'
from (irb):10:in `m'
from (irb):14
from /opt/bin/irb19:12:in `<main>'
irb(main):015:0>

Also I believe the results would not be like your comments suggest
since you redefine the method all the time. Am I missing something?

Downside / upsides to the approach? Any suggestions for improvement?
Or is this just an altogether bad idea?

I do not see the advantage over plain definition of

def ex.m; 10; end

since you are storing a single value anyway. It seems your approach
is only advantageous if you need to access instance variables because
then it spares some ugly syntax. But since you have to call #memo
explicitly you can even pass the value to bind to the method as well,
e.g.

def memo(name, val)
(class << self; self; end).define_method(name){ val }
end

ex.memo :a, 10

As long as you have to invoke the method setting the value explicitly
you do not gain anything, do you? Somehow I must be missing something
but I can't see it right now.

Kind regards

robert


--=20
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

 

[Andrew Wagner]

[Note: parts of this message were removed to make it a legal post.]

Yikes. There's rarely a good reason to need to call eval. And the rest of
this seems really awkward, too. I would recommend watching Dave Thomas'
metaprogramming screencast, where he solves the metaprogramming problem
(literally) 9 different ways, and talks about the pros and cons. It's at
http://pragprog.com/screencasts/v-dtrubyom/the-ruby-object-model-and-metaprogrammingand
you can either get just episode 5, or get the whole screencast, it's
well worth the money.

 

[Intransition]

I could not get that to work on 1.9.1:

17:33:49 ~$ irb19
Ruby version 1.9.1
irb(main):001:0> =A0def memo(&block)
=A0 =A0key =3D eval('__method__', block)
=A0 =A0val =3D block.call
=A0 =A0singleton_class =3D (class << self; self; end)
=A0 =A0singleton_class.__send__define_method, key){ vairb(main):002:1> = l }
=A0 =A0key =3D eval('__method__', block)
irb(main):003:1> =A0 =A0val =3D block.call
irb(main):004:1> =A0 =A0singleton_class =3D (class << self; self; end)
irb(main):005:1> =A0 =A0singleton_class.__send__define_method, key){ va= l }
irb(main):006:1> =A0 =A0val
irb(main):007:1> =A0end
=3D> nil
irb(main):008:0> class ME
irb(main):009:1> attr_accessor :a
irb(main):010:1> def m;memo { @a }; end
irb(main):011:1> end
=3D> nil
irb(main):012:0> ex=3DME.new
=3D> #<ME:0x10049a74>
irb(main):013:0> ex.a=3D10
=3D> 10
irb(main):014:0> ex.m
TypeError: wrong argument type Proc (expected Binding)
=A0 =A0 =A0 =A0 from (irb):2:in `eval'
=A0 =A0 =A0 =A0 from (irb):2:in `memo'
=A0 =A0 =A0 =A0 from (irb):10:in `m'
=A0 =A0 =A0 =A0 from (irb):14
=A0 =A0 =A0 =A0 from /opt/bin/irb19:12:in `<main>'
irb(main):015:0>

Looks like you can't pass a Proc to eval in 1.9+. Wonder why that was
gotten rid of? Ironically I only leaned one could even do that at all
a few month ago! I love having to unlearn.

Looks like it can be fixed with:

key =3D eval('__method__', block.binding)

Also I believe the results would not be like your comments suggest
since you redefine the method all the time. =A0Am I missing something?

After the first time, the original method would no longer be
accessible (at least not via normal method calling).

I do not see the advantage over plain definition of

def ex.m; 10; end

since you are storing a single value anyway. =A0It seems your approach
is only advantageous if you need to access instance variables because
then it spares some ugly syntax. =A0But since you have to call #memo
explicitly you can even pass the value to bind to the method as well,
e.g.

=A0def memo(name, val)
=A0 =A0(class << self; self; end).define_method(name){ val }
=A0end

=A0ex.memo :a, 10

As long as you have to invoke the method setting the value explicitly
you do not gain anything, do you? =A0Somehow I must be missing something
but I can't see it right now.

Yes, part of the reason for this design is to avoid restating the
method name. That's the only reason a block is used in fact, to gain
access to the callers binding so as to get the method name.

The use case for #memo is an alternative to:

def m
@m ||=3D ....
end

But differs in that it avoids the need for an instance variable. I
tend to use the "@m ||=3D" idiom a lot, though I wonder about it's
threading implications, and whether something like #memo would be more
robust.

 

[Caleb Clausen]

The use case for #memo is an alternative to:

def m
@m ||= ....
end

But differs in that it avoids the need for an instance variable. I
tend to use the "@m ||=" idiom a lot, though I wonder about it's
threading implications, and whether something like #memo would be more
robust.

Your #memo method is no more re-entrant than the instance variable
example you gave above. If you want it to be re-entrant, you need to
have a mutex.

Also, I seem to recall that methods defined via define_method are
slower than methods defined via def. But I couldn't see a way to
rewrite your code using def instead...

 

[Benoit Daloze]

Like to get some thoughts on the following technique for memoization:

=A0# Memoize a method.
=A0#
=A0# =A0 class MemoExample
=A0# =A0 =A0 attr_accessor :a
=A0# =A0 =A0 def m
=A0# =A0 =A0 =A0 memo{ @a }
=A0# =A0 =A0 end
=A0# =A0 end
=A0#
=A0# =A0 ex =3D MemoExample.new
=A0#
=A0# =A0 ex.a =3D 10
=A0# =A0 ex.m =A0#=3D> 10
=A0#
=A0# =A0 ex.a =3D 20
=A0# =A0 ex.m =A0#=3D> 10
=A0#
=A0def memo(&block)
=A0 =A0key =3D eval('__method__', block)
=A0 =A0val =3D block.call
=A0 =A0singleton_class =3D (class << self; self; end)
=A0 =A0singleton_class.__send__define_method, key){ val }
=A0 =A0val
=A0end

Downside / upsides to the approach? Any suggestions for improvement?
Or is this just an altogether bad idea?

It looks a bit weird, and eval is really ugly^

I recently wrote two crazy implementations of memoize:

http://github.com/eregon/project_euler/blob/master/014.rb#L64-93

The second seems rather inefficient, while the first seems good.
I'm here saving the only argument to determine what to cache.

It is pretty bad because it redefines the method, however all the
meta-programming stuff is rather interesting, I think.

What do you think of it?

B.D.

 

[Intransition]

It looks a bit weird, and eval is really ugly^

I recently wrote two crazy implementations of memoize:

http://github.com/eregon/project_euler/blob/master/014.rb#L64-93

The second seems rather inefficient, while the first seems good.
I'm here saving the only argument to determine what to cache.

It is pretty bad because it redefines the method, however all the
meta-programming stuff is rather interesting, I think.

What do you think of it?

I find the approach of extending Method interesting. I will have to
play with that.

Are you always getting the same method object and thus the same cache
for memoize2?

 

[Intransition]

Your #memo method is no more re-entrant than the instance variable
example you gave above. If you want it to be re-entrant, you need to
have a mutex.

Ah, thanks Caleb. So to be on the "safe" side I will have to use a
mutex for any memoization code I might devise --there's no way around
it.

Also, I seem to recall that methods defined via define_method are
slower than methods defined via def. But I couldn't see a way to
rewrite your code using def instead...

Well, speed wise, I imagine the mutex will really take care of
that ;-)