Re: Memoizing Functions - yet another attempt

Possibly. But I suspect there may be two slight drawbacks with storing arguments directly:

There's certainly some drawbacks inherent in any approach. Function memoization, like table copying, is probably something that doesn't have one clear "correct" semantic in Lua.

(1) How does one manage memory? If the parameter table creates a strong reference, the arguments will not be garbage collected. If it’s a weak reference, what does it means for the cache stability?

If you want the cache to be collectable by the GC, marking any result lookup tables as weak is sufficient, provided that you're storing result lists inside a collectable object, (like the closures created by the catch() function in my CurriedMemoization hack). Because each result list is a collectable type, and because the only direct reference to those lists is the result lookup table, the whole cache will get scrubbed on a full gc pass.

Of course, one doesn't always want the cache to be scrubbed. That's why I tend to want at least 2 different versions of any memoization function -- a strongly cached version and a weakly cached version.

(2) If parameters are keyed by identity, how does one deal with mutable structures such as, well, tables?

Well, they're handled by reference; which is either helpful or troublesome depending on what the table is being used for.

I'll often write hacks that anticipate the mutability of their results -- for example, I'll implement lazy data initialization by wrapping an object creation call inside a memoized function.

get_image = strong_memoize(

function(name,...)

return new_image(name,... )

end)

function draw_image(name)

get_image(name).draw()

end

In practice, I usually avoid writing memoized functions that expect table arguments. But, again, there are cases where referencing the same cache given a mutable argument is a feature you can take advantage of. For example, here's a trick for associating a unique set of supplemental values with an object:

get_temporary_values = weak_memoize( function(object) return {} end )

(Though with any of my n-result memoizers, this only works if you know the GC will be turned off for the lifetime of the temporaries.)

If you know you want results to be cached by value, rather than by reference, then a string-based serialization approach is certainly a reasonable option. My own memoize.lua file contains a couple different memoization flavors; including one that uses string-serialization to implement by-value argument lookup. However, it's the by-reference functions that I find myself using most of the time.

-Sven