函数表

wiki

它并不完全等效，因为不幸的是，Lua 中有一些地方没有检查 `__call` 元方法（参见 Lua 虚拟化）。其中之一是 `__index` 元方法本身，结果是函数表不能用作 `__index` 元方法；它们必须包装到一个真正的函数中。但函数表可用于函数组合、柯里化等。

我的第一个 Memoize 实现是为 Lua 4 编写的；这里更新了 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

不幸的是，这会在函数表中存储一个私有键，这会影响表迭代。 ThomasWrensch 提出了一个有用的建议，即所有记忆函数都可以在一个弱表中存储，这只是对上述代码的微小更改。但是，我更喜欢以下使用闭包的解决方案，即使它会导致为每个要记忆的函数创建两个表和一个闭包。

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 提供了以下增强功能，这些增强功能支持对象方法、具有多个参数和返回值的方法、具有空参数和返回值的方法、记忆值的弱引用以及一个 “__forget” 方法来清除特定记忆实例的所有记忆结果

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

函数表的另一个非常有用的例子是具有非算法异常的函数。例如，在 `plural()` 的实现中，我们可以将异常存储在表中，将函数留给算法情况：例如，根据需要添加 “s” 或 “es”。这就像记忆函数表一样，只是它不记住结果。（它们并不冲突；记忆器可以用非算法异常 “预先填充”，这通常很有用。）

可以说，所有这些都只是在语法上捣鼓，但这是一种看待程序结构的有趣方式，我感谢 Lua 给予我这种见解。例如，在 `plural()` 的情况下，复数函数可以用某种异常列表传统地编写，但这会分散对复数化算法的注意力，并且还需要某种 API 来添加到异常列表中，而使用函数表，添加到异常列表中是无缝的

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"

作为 functables 的一个更长的例子，这里有一个巧妙的啤酒瓶实现（虽然它不像 Philippe 的那么紧凑）。

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

这是另一个 memoize 的实现。它更简单，为每个被记忆的函数创建一个表和一个闭包。返回值是一个真正的函数。数据隐藏能力更强。下面的一种变体是将 t 作为输入参数或第二个返回值包含进来，以允许像上面 plural 示例中那样进行播种。--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

另请参阅

在以下位置可以找到更多关于元方法的有趣内容：

• AutomagicTables -- Perl 风格的表，按需自动创建子表
• BoundScalarGlobalsOne，BoundScalarGlobalsTwo -- 如何将全局变量绑定到 getter/setter 函数，可能用 C 语言编写
• TableFuncs，TableFuncsTwo -- 某种程度上是 functables 的反面；创建一个具有持久状态的函数
• MutableFunctions - functable 的反面；创建一个具有表语义的函数。

其他 memoize 实现

• [memoize] 函数在 PenLight?
• [memoize.lua] github 上的包，支持多个参数和返回值
• [multikey.memoize] github 上的另一个包，支持多个参数和返回值
• CurriedMemoization -- 另一个多参数、多返回值实现。这个实现准确地缓存了接受或返回 nil 的函数的结果。