Memoizing functions with multiple inputs

[Rob Hoelz <rob@...>]

Hello everyone,

I'm trying to write a multiple dispatch method system for Lua using my
object system, of which the cornerstone is this:

Object = {}
function Object:clone(obj)
  return setmetatable(obj or {}, {__index = self})
end

Since I have to lookup the correct multimethod for every call, I'd like
to memoize the generic calls to improve performance.  There's also the
issue of looking up the correct method for a given set of objects.
Here's my current implementation:

local function cachelookup(s, ...)
  local t = s.cache[arg.n]

  for i = 1, arg.n do
    if not t then
      break
    end
    t = t[arg[i]]
  end

  return t
end

local function methodlookup(s, ...)
  -- similar to cachelookup, but it compensates for inheritance
end

local genericMt = {__call = function(s, ...)
  local f = cachelookup(s, ...) or methodlookup(s, ...)
  if f then
    return f(...)
  else
    error('No such multimethod')
  end
end}

function defgeneric()
  local generic = {
    cache = {},
    methods = {}
  }

  return setmetatable(generic, genericMt)
end

function defmethod(generic, f, ...)
  -- adds f to generic's methods with ... as the objects required to
  -- call it
end

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?

Thanks,
Rob Hoelz