Re: Soliciting criticism of memoize function

[Mark Hamburg <mark_hamburg@...>]

Some issues to deal with in getting a generic memoize to work correctly:

1. Do you need to support memoization for f( nil )? If so, you  
potentially need to handle this separately (but see below).

2. Do you handle nil results from f correctly? Efficiently?

The easiest way to deal with nil is to use a magic value in its place.  
For example, a custom table. We also need to cope with NaN as a  
parameter since it can't be used as a table key. This leads to  
something like the following (untested):

local kNil = { }
local kNaN = { }

local kCacheMode = 'k' -- but see note below

local function encodeKey( k )
	if k == nil then
		return kNil
	elseif k ~= k then
		return kNaN
	else
		return k
	end
end

local decodeHelper = { kNil = kNil, kNaN = 0 / 0 }

local function decodeKey( k )
	local v = decodeHelper[ k ]
	if not v then
		return k
	end
	if v == kNil then
		return nil
	else
		return v
	end
end

local function encodeValue( v )
	if v == nil then
		return kNil
	else
		return v
	end
end

local function decodeValue( v )
	if v == kNil then
		return nil
	else
		return v
	end
end

function memoize( f )

	local function update( t, k, ... )
		assert( select( '#', ... ) == 1 )
		local v = ...
		t[ k ] = v
		return v
	end

	local function index( t, k )		
		return update( t, k, encodeValue( f( decodeKey( k ) ) )
	end

	local cache = setmetatable( { }, { __mode = kCacheMode, __index =  
index } )

	return function( x, ... )
		assert( select( '#', ... ) == 0 )
		return decodeValue( cache[ encodeKey( x ) ] )
	end

end

(Hey. If you are going to check the number of arguments, you ought to  
handle nil and NaN correctly as well...)

3. Cache mode gets tricky for a couple of reasons.

The first is that semi-weak tables can lead to cyclic situations since  
all of the values get marked. For example, if we memoize:

	function( x ) return { x } end

then nothing will ever get collected.

The second is that strings are considered values and hence will tend  
to get marked anyway as keys even if they aren't referenced elsewhere.  
Hence, a safer choice though it results in a memoization cache that  
doesn't last as long is to use a fully weak table.

Mark