函式表

wiki

它並非完全等價，因為遺憾地，Lua 中有些地方並未檢查 __call 元方法（請參閱 LuaVirtualization）。其中之一正是 __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 提供了下列增強功能，支援物件方法、具有多個引數和傳回值的方法、具有 nil 引數和傳回值的方法、弱參考以利快取記憶體值，以及一個「__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"

作函式表的較長範例，這裡有一個很巧妙的啤酒瓶數實作（儘管它遠不如 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 -- 如何將全域變數繫結到取值器/設定器函數（可能以 C 撰寫）
• TableFuncs, TableFuncsTwo -- 某種程度上是函數表格的相反函數，建立包含長駐狀態的函數
• MutableFunctions - 函數表格的相反函數，建立具有表格語義的函數。

其他 memoize 實作

• [memoize] PenLight 中的函數?
• [memoize.lua] github 上的套件，支援多個參數和傳回值
• [multikey.memoize] github 上的另一個套件，支援多個參數和傳回值
• CurriedMemoization -- 另一個多個參數、多個傳回值的實作。這個實作能準確快取取用或傳回 nil 的函數結果。