Re: Memoizing Functions - yet another attempt

[Sir Pogsalot <sir.pogsalot@...>]

On Mon, Dec 16, 2013 at 12:33 AM, Philipp Janda <siffiejoe@gmx.net> wrote:

You probably already know this, but weak tables only work for garbage collected reference types with explicit constructions[1], e.g. tables and userdata, but not numbers, booleans, strings, and light C functions.

I didn't actually know that :o  I think it's just something I never consciously thought about until you mentioned it... how do those others get collected?  I guess what I wrote still stands for userdata at least?  Where do threads/coroutines stand in that?

The last two implementations listed here[2] don't do that. One uses object equality and some form of lookup tree, while the other uses object identity and nested tables. You should add your implementation to that page after you have fixed the following bug: `func()` and `func(nil)` are mapped to the same signature.

 

Thanks for pointing out the problem with f(nil) & f()!

I now prefix the call string with select('#', ...) .. ':'

(in memoize.call)

Here's the code/module I'm working with now:

local counter, guids, funcs

local init =
    function ()
        counter = 0
        funcs   = nil
        guids   = setmetatable({}, { __mode = 'k' })
    end

init()

local memoize = {}

local values =
    function (t)
        local tmp = {}

        for _, v in pairs(t) do
            table.insert(tmp, v)
        end

        return tmp
    end

-- turns a call into a list of object ids (NOT SERIALIZING)
-- example: (1, nil, 'cat', '', function() end) -> '3||7|38|27'
local args_to_str -- forward-declare

args_to_str =
    function (...)
        local ids = {}

        -- select() is important here
        for i = 1, select('#', ...) do
            local v = select(i, ...)

            if type(v) == 'table' then
                local tmp = values(v)
                ids[i] = '{' .. args_to_str(table.unpack(tmp)) .. '}'
            else
                if v ~= nil and not guids[v] then
                    counter  = counter + 1
                    guids[v] = counter
                end

                -- nil is tracked as a vacancy between ||
                ids[i] = guids[v] or ''
            end
        end

        -- the separator is important, should be a non-number
        return table.concat(ids, '|')
    end

memoize.call =
    function (f, ...)
        if not funcs    then funcs = setmetatable({}, { __mode = 'k' }) end
        if not funcs[f] then funcs[f] = {} end

        local call    = select('#', ...) .. ':' .. args_to_str(...)
        local returns = funcs[f]

        if not returns[call] then
            funcs[f][call] = table.pack(f(...))
            print(('call signature: %q \t calling: %s'):format(call, f))
        else
            print(('call signature: %q \t not calling: %s'):format(call, f))
        end

        return table.unpack(funcs[f][call])
    end

memoize.forget_call =
    function (f, ...)
        if not funcs[f] then return end

        -- forget this specific call
        funcs[f][args_to_str(...)] = nil
    end

memoize.forget =
    function (f)
        if f then
            funcs[f] = nil
        else
            init()
        end
    end

memoize.forget_everything = init

return setmetatable(memoize, { __call = function (_, ...) return memoize.call(...) end })

--------------------------------------

And here it is being tested:

Lua 5.2.2  Copyright (C) 1994-2013 Lua.org, PUC-Rio
> package.path = './?.lua;' .. package.path
> memoize = require 'memoize'
> t = memoize(table.pack, nil)
call signature: "1:"      calling: function: 0x420040
> t = memoize(table.pack)
call signature: "0:"      calling: function: 0x420040

:-)

I shall have to add mine to that page sometime, I didn't know memoizing functions was talked about *there*.