Func Tables

wiki

It is not completely equivalent because, sadly, there are a couple of places in Lua where the __call metamethod is not checked (see LuaVirtualization). One of these is the __index metamethod itself, with the result that functables cannot be used as __index metamethods; they have to be wrapped into a real function. But functables are available for functional composition, currying, and so on.

My first implementation of Memoize was written for Lua 4; here it is, updated for Lua 5:

do
  -- The marker table serves double duty. It is a private key in the
  -- hash, and also serves as the hashes metatable.

  local marker = {}

  -- If the key is not found, we use the saved function (stored with the
  -- private key) to generate a value, and save it.

  function marker.__index(t, k)
    local val = t[marker](k)
    t[k] = val
    return val
  end

  -- We make the table look like a function, just deferring to lookup

  function marker.__call(t, k)
    return t[k]
  end

  -- They'll hit an endless loop if they do Memoize(nil). So we do
  -- something reasonable. We could also report an error, of course.

  function Memoize(fn)
    local self = {[marker] = fn or function(x) return nil end}
    setmetatable(self, marker)
    return self
  end

end

Unfortunately, this stashes a private key in the functable which affects table iteration. ThomasWrensch made the useful suggestion that all memoized functions could be stored in a weak table, which is a minor change to the above code. However, I prefer the following solution which uses closures, even though it results in the creation of two tables and a closure for every function to be memoized.

function Memoize(fn)
    fn = fn or function(x) return nil end
    return setmetatable({},
      {
       __index = function(t, k)
                   local val = fn(k)
                   t[k] = val
                   return val
                 end,
       __call  = function(t, k)
                   return t[k]
                 end
      })
end

Dejay Clayton offers the following enhancements, which support object methods, methods with multiple arguments and return values, methods with nil arguments and return values, weak references for memoized values, and a "__forget" method to clear all memoization results for a particular memoized instance:

function pack( ... )
    return arg
end

function memoize( fn )
    local function fnKey( ... )
        local key = ""
        for i = 1, table.getn( arg ) do
            key = key .. "[" .. tostring( arg[ i ] ) .. "]"
        end
        return key 
    end

    local object = {
        __call  = function( targetTable, ... )
            local key = fnKey( ... )
            local values = targetTable.__memoized[ key ]

            if ( values == nil ) then
                values = pack( fn( ... ) )
                targetTable.__memoized[ key ] = values
            end

            if ( table.getn( values ) > 0 ) then
                return unpack( values )
            end

            return nil
        end,
        __forget = function( self ) self.__memoized = {} end,
        __memoized = {},
        __mode = "v",
    }

    return setmetatable( object, object )
end

Another very useful example of a functable is a function which has non-algorithmic exceptions. For example, in an implementation of plural(), we could stash exceptions in the table, leaving the function for algorithmic cases: adding "s" or "es" as appropriate, for example. This is just like the memoizing functable, except that it doesn't remember the result. (They are not incompatible; the memoizer can be "primed" with non-algorithmic exceptions, and that's often useful.)

Arguably, all this is just monkeying around with syntax, but it is an interesting way to look at program structure and I thank Lua for giving me this insight. In the case of plural(), for example, the plural function could be written traditionally with some sort of exception list, but that distracts from the pluralisation algorithm and also requires some sort of API to add to the exception list, whereas with the functable, adding to the exception list is seamless:

plural = To_Functable({},
           function(word)
             local gsub = string.gsub
             local nsubs
             -- some sample rules:
             -- if word ends in consonant "y", change "y" to "ies"
             word, nsubs = gsub(word, "([bcdfghjklmnpqrstvwxyz])y$", "%1ies")
             if nsubs > 0 then return word end 
             -- if word ends in a sibilant, append "es"
             word, nsubs = gsub(word, "([sxz])$", "%1es")
             if nsubs > 0 then return word end
             word, nsubs = gsub(word, "([cs]h)$", "%1es")
             if nsubs > 0 then return word end
             -- otherwise append "s"
             return word .. "s"
           end)
-- standard exceptions (many omitted)
plural.mouse = "mice"
plural.man = "men"
plural["right-of-way"] = "rights of way"

-- maybe we like some old-fashioned usages
plural.cow = "kine"

As a longer example of functables, here is a nifty bottles of beer implementation (although it is not nearly compact as Philippe's):

function To_Functable(t, fn)
  return setmetatable(t,
    {
     __index = function(t, k) return fn(k) end,
     __call = function(t, k) return t[k] end
    })
end

-- Functable bottles of beer implementation

spell_out = {
  "One", "Two", "Three", "Four", "Five",
  "Six", "Seven", "Eight", "Nine", "Ten",
  [0] = "No more",
  [-1] = "Lots more"
}

spell_out = To_Functable(spell_out, function(i) return i end)

bottles = To_Functable({"Just one bottle of beer"},
                       function(i)
                         return spell_out(i) .. " bottles of beer"
                       end)

function line1(i)
  return bottles(i) .. " on the wall, " .. bottles(i) .. "\n"
end

line2 = To_Functable({[0] = "Go to the store, Buy some more,\n"},
                     function(i)
                       return "Take one down and pass it around,\n"
                     end)

function line3(i)
  return bottles(i) .. " on the wall.\n"
end

function song(n)
  for i = n, 0, -1 do
    io.write(line1(i), line2(i), line3(i - 1), "\n")
  end
end

-- RiciLake

Here is another implementation of memoize. It is simpler and creates one table and one closure per memoized function. The return value is a true function. Data hiding abilities are stronger. A variant of the below is to include t as an input parameter or second return value to permit seeding as done in the plural example above. --DavidManura

function memoize(fn)
  local t = {}
  return function(x)
    local y = t[x]
    if y == nil then y = fn(x); t[x] = y end
    return y
  end
end

See Also

Some more fun with metamethods can be found in:

• AutomagicTables -- Perl style tables which autocreate subtables on demand
• BoundScalarGlobalsOne, BoundScalarGlobalsTwo -- How to bind a global to getter/setter functions, possibly written in C
• TableFuncs, TableFuncsTwo -- sort of the inverse of functables; create a function with persistent state
• MutableFunctions - inverse of functable; create a function having the semantics of tables.

Additional memoize implementations:

• [memoize] function in PenLight?
• [memoize.lua] package on github, supporting multiple parameters and return values
• [multikey.memoize] another package on github, supporting multiple parameters and return values
• CurriedMemoization -- another multiple parameter, multiple return value implementation. This one accurately caches the results of functions taking or returning nil.