Your thoughts on #memo?

ruby-talk
1

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?

2

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

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 = eval('__method__', block)
   val = block.call
   singleton_class = (class << self; self; end)
   singleton_class.__send__(:define_method, key){ vairb(main):002:1> l }
   key = eval('__method__', block)
irb(main):003:1> val = block.call
irb(main):004:1> singleton_class = (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
=> 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
=> nil
irb(main):012:0> ex=ME.new
=> #<ME:0x10049a74>
irb(main):013:0> ex.a=10
=> 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

···

2010/8/23 Intransition <transfire@gmail.com>:

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

3

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.

···

On Mon, Aug 23, 2010 at 11:18 AM, Intransition <transfire@gmail.com> wrote:

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?

4

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

I recently wrote two crazy implementations of memoize:

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.

···

On 23 August 2010 17:18, Intransition <transfire@gmail.com> wrote:

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?

5

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 = eval('__method__', block)
val = block.call
singleton_class = (class << self; self; end)
singleton_class.__send__(:define_method, key){ vairb(main):002:1> l }
key = eval('__method__', block)
irb(main):003:1> val = block.call
irb(main):004:1> singleton_class = (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
=> 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
=> nil
irb(main):012:0> ex=ME.new
=> #<ME:0x10049a74>
irb(main):013:0> ex.a=10
=> 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>

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 = eval('__method__', block.binding)

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

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

> 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.

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 ||= ....
  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.

···

On Aug 23, 11:37 am, Robert Klemme <shortcut...@googlemail.com> wrote:

6

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?

···

On Aug 23, 1:52 pm, Benoit Daloze <erego...@gmail.com> wrote:

On 23 August 2010 17:18, Intransition <transf...@gmail.com> wrote:

> 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?

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

I recently wrote two crazy implementations of memoize:

project_euler/014.rb at master · eregon/project_euler · GitHub

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?

7

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...

···

On 8/23/10, Intransition <transfire@gmail.com> wrote:

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.

8

> 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.

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

···

On Aug 23, 12:47 pm, Caleb Clausen <vikk...@gmail.com> wrote:

On 8/23/10, Intransition <transf...@gmail.com> wrote: