Re: Memoizing Functions - yet another attempt

[Petite Abeille <petite.abeille@...>]

On Dec 17, 2013, at 5:58 AM, Dirk Laurie <dirk.laurie@gmail.com> wrote:

> 2013/12/16 Sven Olsen <sven2718@gmail.com>:
> 
>> Function memoization, like table copying, is probably something that
>> doesn't have one clear "correct" semantic in Lua.
> +1. This is the crux.


In the spirit of the festive season, introducing ‘memoization a la carte’...


(1) The basics

local function Key( aSigner, ... )
  local aBuffer = {}

  for anIndex = 1, select( '#', ... ) do
    aBuffer[ #aBuffer + 1 ] = aSigner( select( anIndex, ... ) )
  end

  return table.concat( aBuffer )
end

local function Memoize( aFunction, aSigner )
  local aCache = {}
  local aSigner = aSigner or Signer

  return function( ... )
    local aKey = Key( aSigner, ... )
    local aValue = aCache[ aKey ] or table.pack( aFunction( ... ) )

    aCache[ aKey ] = aValue

    return table.unpack( aValue, 1, aValue.n )
  end
end

This takes care of packing/unpacking parameters and values. As well as mapping a set of parameters to previous values.

The meat of the mapping is provided by that mysterious ‘signer’ function.


(2) Basic signer

Converts a value to a string and tag its type to it. And that’s that.

local function Signer( aValue )
  return ( tostring( aValue or '' ) or '' ) .. type( aValue ):sub( 1, 2 )
end

Example:

print( Key( Signer, nil, true, 'a', 1, { 1, 2 } ) )

> nitrueboast1nutable: 0x7fc0e8c0d010ta



(3) Identity signer

Similar to the basic signer, but instead of converting values to strings, it keeps a numbered identity  map, and assigning new number to each new value (ala Sir Pogsalot).

local function IdentitySigner()
  local aCache = setmetatable( {}, { __mode = 'k' } )
  local aCount = 0

  return function( aValue )
    if aValue == nil then
      return '0.'
    end

    if not aCache[ aValue ] then
      aCount = aCount + 1
      aCache[ aValue ] = tostring( aCount ) .. '.'
    end

    return aCache[ aValue ]
  end
end

Example:

print( Key( IdentitySigner(), nil, true, 'a', 1, { 1, 2 } ) )

> 0.1.2.3.4.


(4) Table signer

This signer recursively traverses any table it encounters and sign its individual elements.

local function TableSigner( aSigner )
  local aSigner = aSigner or Signer
  local aSet = {}
  local aCounter = 0

  return function( aValue )
    if type( aValue ) == 'table' and not aSet[ aValue ] then
      local self = debug.getinfo( 1, 'f' ).func
      local aBuffer = {}

      aCounter = aCounter + 1
      aSet[ aValue ] = ( '%dta' ):format( aCounter )

      for aTableKey, aTableValue in pairs( aValue ) do
        aBuffer[ #aBuffer + 1 ] = self( aTableKey ) .. self( aTableValue )
      end

      table.sort( aBuffer )
      aBuffer[ #aBuffer + 1 ] = 'ta'
      aSet[ aValue ] = table.concat( aBuffer )
    end

    return aSet[ aValue ] or aSigner( aValue )
  end
end

Example:

print( Key( TableSigner(), nil, true, 'a', 1, { 1, 2 } ) )

> nitrueboast1nu1nu1nu2nu2nuta


(5) Table identity signer

A Christmas special, a table signer with an identity signer.

Example:

print( Key( TableSigner( IdentitySigner() ), nil, true, 'a', 1, { 1, 2 } ) )

> 0.1.2.3.3.3.4.4.ta


Putting it all together, with various usage examples:

local aSigner = TableSigner( IdentitySigner() )
local open = Memoize( io.open, aSigner )
local gsub = Memoize( string.gsub, aSigner )
local modf = Memoize( math.modf, aSigner )
local concat = Memoize( table.concat, aSigner )
local pack = Memoize( table.pack, aSigner )
local unpack = Memoize( table.unpack, aSigner )
local none = Memoize( function() return {} end, aSigner )
local void = Memoize( function() end, aSigner )

print( 'open', 1, open( 'TestMemoize.lua', 'rb' ) )
print( 'open', 2, open( 'TestMemoize.lua', 'rb' ) )
print( 'open', 3, open( 'TestMemoize.lua', 'rb' ) )
print( 'open', 4, open( 'TestMemoize.lua', 'r' ) )
print( 'open', 5, open( 'TestMemoize.lua', 'r' ) )
print( 'open', 6, open( 'TestMemoize.lua', 'r' ) )

print( 'gsub', 1, gsub( '1 2 3', '%d+', '%1!' ) )
print( 'gsub', 2, gsub( '1 2 3', '%d+', '%1!' ) )
print( 'gsub', 3, gsub( '1 2 3', '%d+', '%1!' ) )

print( 'modf', 1, modf( 1.2 ) )
print( 'modf', 2, modf( 1.2 ) )
print( 'modf', 3, modf( 1.2 ) )
print( 'modf', 4, modf( 3.4 ) )
print( 'modf', 5, modf( 3.4 ) )
print( 'modf', 6, modf( 3.4 ) )

local aTable = {  1, 2, 3, 4, 5, 6 }
print( 'concat', 1, concat( aTable ) )
print( 'concat', 2, concat( aTable ) )
print( 'concat', 3, concat( { 1, 2, 3, 4, 5, 6 } ) )
print( 'concat', 4, concat( aTable, '.' ) )
print( 'concat', 5, concat( aTable, '.' ) )
print( 'concat', 6, concat( aTable, ':' ) )
print( 'concat', 7, concat( aTable, ':' ) )
print( 'concat', 8, concat( aTable, ';' ) )
print( 'concat', 9, concat( aTable, ';' ) )

print( 'pack', 1, pack( 1, 2, 3, 4, 5, 6 ) )
print( 'pack', 2, pack( 1, 2, 3, 4, 5, 6 ) )
print( 'pack', 3, pack( nil, nil, nil, 1, 2, 3, 4, 5, 6, nil, nil, nil ) )
print( 'pack', 4, pack( nil, nil, nil, 1, 2, 3, 4, 5, 6, nil, nil, nil, true, 0, false ) )
print( 'pack', 5, pack( '1', '23' ) )
print( 'pack', 6, pack( '12', '3' ) )

print( 'unpack', 1, unpack( aTable ) )
print( 'unpack', 2, unpack( aTable, 1, 3 ) )
print( 'unpack', 3, unpack( { 1, 2, 3 } ) )

print( 'none', 1, none() )
print( 'none', 2, none() )
print( 'none', 3, none() )

print( 'void', 1, void() )
print( 'void', 2, void() )
print( 'void', 3, void( true, false, nil ) )
print( 'void', 4, void( true, nil, false ) )
print( 'void', 5, void( 1 ) )
print( 'void', 6, void( '1' ) )

local foo = Memoize( function( aTable) return aTable, table.unpack( aTable ) end, TableSigner( IdentitySigner() ) )

print( 'foo', 1, foo( { 1, 2, 3 } ) )
print( 'foo', 2, foo( { 1, 2, 3 } ) )
print( 'foo', 3, foo( { a = 1, b = 2, c = 3 } ) )
print( 'foo', 4, foo( { a = 1, b = 2, c = 3 } ) )
print( 'foo', 5, foo( { {}, {}, {} } ) )
print( 'foo', 6, foo( { {}, {}, {} } ) )
print( 'foo', 7, foo( aTable ) )
aTable[ #aTable + 1 ] = aTable
aTable[ #aTable + 1 ] = aTable
aTable[ #aTable + 1 ] = aTable
aTable[ #aTable + 1 ] = true
aTable[ aTable ] = aTable
aTable[ _G ] = _G
print( 'foo', 8, foo( aTable ) )
print( 'foo', 9, foo( aTable ) )

print( 'Signer', ( '%q' ):format( Key( Signer ) ) )
print( 'Signer', ( '%q' ):format( Key( Signer, nil ) ) )
print( 'IdentitySigner', ( '%q' ):format( Key( IdentitySigner() ) ) )
print( 'IdentitySigner', ( '%q' ):format( Key( IdentitySigner(), nil ) ) )
print( 'TableSigner', ( '%q' ):format( Key( TableSigner() ) ) )
print( 'TableSigner', ( '%q' ):format( Key( TableSigner(), nil ) ) )
print( 'TableIdentitySigner', ( '%q' ):format( Key( TableSigner( IdentitySigner() ) ) ) )
print( 'TableIdentitySigner', ( '%q' ):format( Key( TableSigner( IdentitySigner() ), nil ) ) )

Share the holiday cheer, share the insanity.