Func Tables

wiki

An important insight is that in Lua there is very little difference between a function and a table with a __call metamethod. I refer to the latter as functables, and they are incredibly useful. For example, it is almost trivial to write a memoizing functable which caches the result of a given function. By using the __call metamethod we can allow the table to be used as though it were the function; in fact, we could even give it the name of the original function, making the change almost invisible.

: 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

Func Tables

See Also