柯里化记忆化

wiki

例如

  local mtest = weak_memoize_m_to_n( function(...) print 'exec' return ... end )

  print( mtest(nil,2) )    --> "exec", "nil,2"
  print( mtest(nil,2) )    --> "nil,2"
  collectgarbage()
  print( mtest ( nil,2 ) ) --> "exec", "nil,2"
  print( mtest ( ) )       --> "exec", ""
  print( mtest ( nil ) )   --> "exec", "nil"

该设计等效于类似于 [memoize.lua] 的参数树技术。但是，该树是隐式构建的，而不是显式构建的，通过递归地将 M>1 个情况简化为 M-1 个情况。

Lua 代码

  local _ENV = setmetatable({},{__index=_G})

  -- this code can be made more memory and speed efficient by
  -- defining catch() in C.  but, a table.unpack approach will also
  -- work. 
  function catch(...)
    local rvals = {...}
    local n = select('#',...)
    return function()
      return table.unpack(rvals,1,n)
    end
  end

  local weak_mt= {__mode='kv'}
  local function weak_table() return setmetatable({},weak_mt) end
  local function strong_table() return {} end

  local null = {}

  local function arg2key(arg)
    return (arg == nil and null) or arg
  end

  -- build a memoization function that can handle the 1-argument 
  -- to n rvals case.  
  local function new_memoizer_1_to_n(newtable)
    return function(fun)
      local lookup = newtable()

      return function (arg)
        local k = arg2key(arg)
        local r=lookup[k]
        if r then
          return r()
        end
        r=catch( fun(arg) )
        lookup[k] = r
        return r()
      end

    end
  end

  local function new_memoizer_m_to_n( newtable, memoize_1_to_n )

    -- return a memoization of f that assumes m arguments.
    local function memoize_m_to_n(m,f)
      --  handle the m==0 case
      if m==0 then
        local memoized
        return function()
          if memoized then
            return memoized()
          end
          memoized = catch(f())
          return memoized()
        end
      end

      if m==1 then
        return memoize_1_to_n(f)
      end

      local lookup = newtable()

      -- handle the general m-to-n case, for m>=2. 
      return function(arg, ...)

        local k = arg2key(arg)
        local r = lookup[k]

        if r then
          return r(...)
        end
    
        -- create a new (m-1) argument memoizer that will handle 
        -- this arg value in the future.  
        r = memoize_m_to_n(m-1, function(...)
          return f(arg,...)
        end)

        lookup[k]=r
        return r(...)
      end
    end

    -- return a memoizer that dispatches between the different m-argument cases.
    return function(f)
      local m_to_memoized = newtable()
      return function(...)
        local m = select('#',...)
        local memoized = m_to_memoized[m]
        if memoized then
          return memoized(...)
        end
        memoized = memoize_m_to_n(m,f)
        m_to_memoized[m]=memoized
        return memoized(...)
      end
    end
  end

  weak_memoize_1_to_n =  new_memoizer_1_to_n(weak_table)
  strong_memoize_1_to_n =  new_memoizer_1_to_n(strong_table)

  weak_memoize_m_to_n = new_memoizer_m_to_n(weak_table,weak_memoize_1_to_n)
  strong_memoize_m_to_n = new_memoizer_m_to_n(strong_table,strong_memoize_1_to_n)

  return _ENV

在 C 中实现 catch()

通过在 C-API 中实现 catch()，可以提高内存使用率和性能。虽然它们的存储容量限制为 255 个值；但 C-闭包比 Lua 的通用表更轻、更快的数据结构。

  static int throw_upvalues(lua_State *L) {
    int n1=lua_tointeger(L,lua_upvalueindex(1));
    luaL_checkstack(L,n1-1,"too many upvalues");
    for(int i=2; i<=n1; i++) {
      lua_pushvalue(L,lua_upvalueindex(i));
    }
    return n1-1;
  }

  static int catch_args(lua_State *L) {
    int n1 = lua_gettop(L)+1;
    if(n1>MAXUPVAL) {
      return luaL_error(L,"can't catch more than %d args. (catch() called with %d arguments).",MAXUPVAL-1, n1-1);
    }
    lua_pushinteger(L,n1);
    lua_insert(L,1);
    lua_pushcclosure(L,throw_upvalues,n1);
    return 1;
  }

另请参阅

许多其他 Lua 记忆化实现散布在网络上。 FuncTables 页面似乎是事实上的 wiki 链接中心。但是，该主题也经常出现在 lua 用户列表中；并且在档案中发布了一些基于字符串序列化的不错实现 [1]，[2]。