lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

Dear all,

Is generic external memoization of recursive functions at all possible in Lua?

By 'external' I mean that the memoized function, when it is defined, is not required to know that it is going to be memoized later, and should recursively call itself by its own name, rather than the name of its memoized version:

local function fibonacci (n) -- this function does not know it is going to be memoized.

    return n < 3 and 1 or fibonacci (n - 2) + fibonacci (n - 1) -- I want to make these calls memoized too.


local fibonacci_memoized = memoize (fibonacci)

By 'generic' I mean that the memoization function should be universal: an improved version of:

local function memoize (func)
    local cache = {}
    return function (...)
        local params = table.concat ({...}, ',')
        cache [params] = cache [params] or {func (...)}
        return table.unpack (cache [params])

So, we need to substitute func with memoize (func) every time func calls func. I tried to alter _ENV, but achieved nothing. Perhaps, the debug library could help?

Alexander Mahsin