Re: Memoizing Functions - yet another attempt

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

On Sun, Dec 15, 2013 at 9:50 AM, Dirk Laurie <dirk.laurie@gmail.com> wrote:

2013/12/15 Sir Pogsalot <sir.pogsalot@gmail.com>:

This brings me back to the point that drove Petite Abeile's head
to explode: if the contents of a table `tbl` has changed, do we
want a memoized function to still return the value from the
last time that `tbl` was the argument?

Is doing so really "the more correct approach"?

Hmm I am not sure.

The wikipedia page seems to suggest that pure functions only operate on immutable objects.  It lists a 'length()' function as an example of a pure function because it would always return the same value for a string, but that would only be possible if strings cannot be modified between calls to length() --> immutable.

On the other hand...

I could modify args_to_str() "deep-expand" tables in the call to a sequence of all values (including the hash part) in pairs() order.  SO args_to_str('a', { 'b', 'c', { 'd', 'e', 'f' } }, 'g') becomes '1|{2|3|{4|5|6}|7' and can be used to look up previous calls with similar table constructions (but not the same identity).  This isn't foolproof because userdata can act like tables as well...

On a side note I just learned a way to speed up deep comparisons of tables. :-)  (and copies)

Here's the code:

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

Testing it:

Lua 5.2.2  Copyright (C) 1994-2013 Lua.org, PUC-Rio

> package.path = './?.lua;' .. package.path

> memoize = require 'memoize'

> = memoize(table.unpack, { 'a', 'b', 'c', { 'd', 'e', 'f', { 'g', 'h', 'i' }}})

call signature: "{1|2|3|{4|5|6|{7|8|9}}}" calling: function: 0x41fe40

a b c table: 0x1bc3d50

> return  memoize(table.unpack, { 'a', 'b', 'c', { 'd', 'e', 'f', { 'g', 'h', 'i' }}})

call signature: "{1|2|3|{4|5|6|{7|8|9}}}" not calling: function: 0x41fe40

a b c table: 0x1bc3d50

I see a possible problem, though.  Perhaps the cached returns should be deep-copied...