Re: Memoizing functions with multiple inputs

[Rob Hoelz <rob@...>]

On Thu, 2008-09-11 at 13:06 -0500, Javier Guerra wrote:
> On Thu, Sep 11, 2008 at 12:44 PM, Rob Hoelz <rob@hoelzro.net> wrote:
> > Hello everyone,
> >
> > I'm trying to write a multiple dispatch method system for Lua using my
> > object system, of which the cornerstone is this:
> .........
> > Using a tree-like memoization cache is fairly clear, but I have the
> > feeling that there's a better way to do this.  Any hints/suggestions?
> 
> to use multiple inputs as key to the memoization table, you can either
> nest tables (what you call tree-like), or join all inputs into a
> single string and use that as key.
> 
> 
> but, i don't really get your object implementation, and it seems you
> want to use memoization to speed up method lookup.  if so, you should
> really rethink your object infrastructure.  if lookup is so expensive,
> it might be better to copy all inherited methods in the new class
> metatable.
> 
> of course, i find myself caring less and less about class-based OOP.
> i especially don't find the inheritance concept worth in real life the
> troubles it carries.
> 

My object system is actually prototypical; Object is there for
convenience and kind of as a "master prototype."  With the
implementation I provided above, I can do things like:

sparky = Object:clone() -- a prototypical dog

function sparky:bark()
  print 'Woof!'
end

sparkys_evil_clone = sparky:clone()
sparkys_evil_clone:bark() -- prints 'Woof!'

function sparkys_evil_clone:bark()
  print 'Evil woof!'
end

sparkys_evil_clone:bark() -- prints 'Evil woof!'

Like this, I can change sparky.bark if needed, and all objects
delegating to sparky will be able to make use of that change, assuming
they don't override it.  Even then, they can forward the method up the
inheritance chain.  Method lookup with metatables is fast enough; that's
not what I'm memoizing.  I want to write a multimethod system (akin to
CLOS or Dylan) on top of my object system that my object system can use,
but doesn't have to.  In order to do that efficiently, I need to memoize
which methods correspond to which combinations of objects.  Here's an
example:

--[[
Object hierarchy:
               Object
                  /\
                 /  \
                A    B
               /      \
              D        C
             /
            E
]]

A = Object:clone()
B = Object:clone()
C = B:clone()
D = A:clone()
E = D:clone()

g = defgeneric()

defmethod(g, function (left, right)
  print 'A B'
end, A, B)

defmethod(g, function(left, right)
  print 'D B'
end, D, B)

g(A, B) -- prints A B
g(D, B) -- prints D B
g(A, C) -- prints A B
g(E, B) -- prints D B
g(E, C) -- prints D B

Thanks,
Rob Hoelz