Lua generic external memoization of recursive functions

["Александр Машин" <traditio.ru@...>]

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.

end

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])
    end
end

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