tagtypes & metatables are still not fundamental enough!?!?

["Peter Hill" <corwin@...>]

There is something that has been bothering me about metamethods (and
tagmethods) for a while.

Specifically... looking at the current metatypes (and the old tagtypes) it
seems to me that they both exceed Lua's 'minimalist' principle. Ie, not to
provide complex structures but rather to provide the basic mechanisms for
people to use to implement those complex structures.

To see what I mean let's get back to basics. I would imagine the evolution
of metamethods would have gone something like as follows [Lua creators &
others who have been there from the start please feel free to correct me
:-)].

(a) Lua is an embedded language, so that exceptional conditions (eg, trying
to add to a table such as "{}+2") needed to be trapped. Initially there was
probably only a single error function "error()" but it might also have taken
some kind of error key as well as the error message, eg "error('add','trying
to add a non-number')", perhaps even with the extra parameters (if the 'arg'
type existed at this stage).

(b) This monolithic exception trapping is a bit cumbersome when trying just
to trap one type of error, so perhaps specific traps might have evolved. Eg,
an "_add()" function called whenever 'add' failed:

    function internal_add(op1,op2)
      o1 = tonumber(op1)
      o2 = tonumber(op2)
      if (o1 and o2) then
        return o1+o2
      elseif _add then
        return _add(op1,op2)
      else
        error('Trying to add non-numbers')
      end
    end

(c) This was all good & fine but it had two problems. Firstly, if one wants
different behaviour for different subtypes one needs to store the subtype
somewhere. Tables *could* have some sort of internal tag, eg {_tag=123}, but
userdata needed something more. The second problem was to then have a way to
dispatch based on each different type. A resolution for this was 'tags' and
'tagmethods'. The data subtype was attached to the table/userdata as an
integer, and an internal table was created for tagmethods indexed by that
tag.

(d) [Lua5] The tagmethod internal array was rather un-Lua-like in nature so
a refactoring to use the existing Table type was done. Since such tables
then had a Lua reference, an arbitrary tag integer was no longer needed (the
reference could be used instead). Also, the previous drift away from the
'exception' model (ie, only call a metamethod if something out of the usual
happened) was countered by removing the 'get' event.

Whew!

The thing about all of this is that the current method is extra complex
while still imposing usage constraints.

For example, the "add" metamethod is dual-dispatch (rather than
multidispatch); first checking the type of the left argument only (and doing
a single-dispatch on that if it exists) and then doing similarly on the
right side if needed.

Consider the following example...

First I implement an indefinite-size number package, "Longnum", that
includes metamethods for 'add' etc. I then create a complex number package,
"Complex", implemented as a pair of Longnum's. Now adding two complex
numbers together is fine (this is just a normal metamethod) but what if I
want to create mixed functions that add longnums with complex numbers? The
basic principle is simple:

  function add_cl(c,l)
    return c + Complex.new(l,0)
  end

  function add_lc(l,c)
    return Complex.new(l,0) + c
  end

but how does one set up dispatch metamethods? "add_cl" is fine... we just
have to modify our exisiting "add" metamethod for Complex to check its right
argument to see if it, too, is Complex or whether it is a Longnum which
needs to be converted.

But what of "add_lc"? It would have to be added to Longnum's "add"
metamethod. But the complex number module is built completely on top of the
Longnum module; Longnum shouldn't know it exists. Ie, you should be able to
"require()" Longnums for your program without ever needing to "require()"
Complex (it's an optional extra). But the current metamethod scheme destroys
that, either requiring Longnum to know about Complex, or requiring Complex
to tinker with Longnum's "add" metamethod (probably the more modular
choice). In either case the arbitrary "left metamethod / right metamethod"
scheme does not produce a pretty result.


-- SUGGESTION --

A more general core implementation of 'exception trapping' could be done as
follows.

(a) First, get back to the 'old days' of simple single global trapping
functions, eg: "_add", which are called if the system can't handle arguments
as presented. Note: I would like to also see a "_print" event for when
"print()" if given a non-standard argument (as a fallback for pretty debug
printing). These are, basically, just traps for core (and library)
exceptions.

(b) Add a subtype to tables / userdata. These are similar to the old 'tags'
(ie, a unique integer) however NO INTERNAL tagmethod table is allocated. In
this case these subtypes are JUST a unique integer, nothing more.

These have similar basic functions to tags, but since they have no
tagmethods etc I'll call them (to save possible confusion) "typ" instead.
So we have:

  -- Return a new 'typ' integer (by incrementing an internal counter).
  t = newtyp()

  -- Set the 'typ' of a table, returning that table.
  x = settyp(x,t)

  -- Return the 'typ' of an object. Just like Lua4 simple objects (numbers,
  -- strings, etc) have a fixed 'typ' assigned.
  t = typ(x)


To demonstate that such a technique is more fundamental, I have included
below sample implementations (using the "add" event as an example) of:
(1) Lua5 metamethods
(2) Lua4 tagmethods
(3) Multidispatch

----------------

(1) An example implementation of Lua5 metatables using 'typ' & '_add'.

do
  -- In the new system one can't attach (meta)tables to an object... just a
  -- 'typ' integer. Thus we need to keep an internal lookup to associate
  -- each metatable with a unique 'typ'.
  -- Note: I should probably use weak keys with these tables...?
  local typ_meta = {} -- 'typ' (given the metatable).
  local meta_typ = {} -- metatable (given the 'typ').

  function getmetatable(t)
    return meta_typ[typ(t)]
  end

  function setmetatable(t,m)
    local tp -- There is an internal 'typ' associated with each metatable.
    if m then
      -- Get the 'typ' (create a new one if this metatable is new).
      tp = typ_meta[m]
      if not tp then
        tp = newtyp()
        typ_meta[m] = tp
        meta_typ[tp] = m
      end
    else
      tp = typ{} -- reset to the 'typ' of an unadorned table.
    end
    settyp(t,tp) -- Associate the object with the metatable via a 'typ'.
  end

  function _add(op1,op2)
    -- The global '_add' event is called if "tonumber(op1) and
    -- tonumber(op2)" is not true.
    local h = getmetatable(op1)["__add"] or getmetatable(op2)["__add"]
    if h then
      -- call the handler with both operands
      return h(op1, op2)
    else  -- no handler available: default behavior
      error("unexpected type at arithmetic operation")
    end
  end

end

----------------

(2) An example implementation of Lua4's tagmethods using 'typ' & '_add'.

do
  -- Basically we just implement the old tagtable using Lua tables.

  -- This table is indexed by 'tag', returning for each tag a table of
  -- tagmethods (for that 'tag') indexed by event name.
  local tag_table = {}

  function tag(t)
    return typ(t)
  end

  function settag(t,tg)
    return settyp(t,tg)
  end

  function gettagmethod(tg, event)
    local tgt = tag_table[tg]
    return tgt and tgt[event]
  end

  function settagmethod(tg, event, newmethod)
    -- Get the tag methods for this 'tag' (create a methods table if
    -- absent).
    local tgt = tag_table[tg]
    if not tgt then
      tgt = {}
      tag_table[tg] = tgt
    end
    -- Get the tagmethod for this event (to return) and set the new
    -- tagmethod. Note: Currently don't check that the 'event' is valid.
    tgm = tgt[event]
    tgt[event] = newmethod
    return tgm
  end

  function copytagmethods(tagto, tagfrom)
    local tf = tag_table[tagfrom]
    local tt
    if tf then
      tt = {}
      for v,i in tf,next do tt[i] = v end
    end
    tag_table[tagto] = tt
  end

  function _add(op1, op2)
    local tm = gettagmethod(tag(op1), "add")
      or gettagmethod(tag(op2), "add")
      or gettagmethod(0, "add")
    if tm then
      -- call the method with both operands and an extra argument with
      -- the event name
      return tm(op1, op2, "add")
    else  -- no tag method available: default behavior
      error("unexpected type at arithmetic operation")
    end
  end

end

----------------

-- (3) An example implementation of a multi-dispatch using 'typ' & '_add'.

do
  -- Dispatch table for all events. Keyed by a string made of event &
  -- argument 'typ'. Eg: "add:123:456"
  local dispatch = {}

  function getdispatch(event, ...)
    local t = event
    for i = 1,arg.n do
      t = t .. ":" .. typ(arg[i])
    end
    return dispatch[t]
  end

  function setdispatch(event, m, ...)
    local t = event
    for i = 1,arg.n do
      t = t .. ":" .. typ(arg[i])
    end
    local om = dispatch[t]
    dispatch[t] = m
    return om
  end

  function _add(op1,op2)
    local t1 = typ(op1)
    local t2 = typ(op2)
    local m = dispatch["add:" .. t1 .. ":" .. t2]
    if m then
      m(op1,op2)
    else
      error('Adding non-numbers')
    end
  end

end

-- Example of use of Multidispatch.

do -- Complex

Complex =
{
typ = newtyp()

new =
  function(r,i)
    local c = {real=r, imag=i}
    return settyp(c,Complex.typ)
  end

add =
  function(c1,c2)
    return Complex.new(c1.real+c2.real, c1.imag+c2.imag)
  end

print =
  function(c1)
    write("[" .. c1.real .. " + i" c1.imag .. "]")
  end
}

local function addcn(c,n)
  return Complex.add(c, Complex.new(m,0))
end

local function addnc(n,c)
  return Complex.add(Complex.new(m,0), c)
end

setdispatch("add", Complex.add, Complex.typ, Complex.typ)
setdispatch("add", addcn, Complex.typ, typ(0))
setdispatch("add", addnc, typ(0), Complex.typ)
setdispatch("print", Complex.print, Complex.typ)

end -- Complex

c = Complex.new(11,22)
print(c+c,c+2,4+c)

*cheers*
Peter Hill.