Re: Memoizing a function.

[Christian Vogler <cvogler@...>]

> What I'm wondering is if there is a way of making a general memoization
> pool. Someting in the tune of indexing the pool by function name and
> value/values. I would be pleased if there was an easy way of
> accomplishing this in one or a few lines of code per function. A
> preprocessor would do it too.

Sure there is. Lua's power is on par with other functional programming
languages. It just sometimes requires a slightly more roundabout way.

do
   local memopool = {}
   
   function call_memoized(f, arg)
      if not %memopool[f] then
	 %memopool[f] = {}
      end
      local funpool = %memopool[f]
      local memval = funpool[arg]
      if memval then
	 return memval.val
      else
	 local retval = f(arg)
	 funpool[arg] = { val=retval }
	 return retval
      end
   end
end

function fib(n)
   if n < 2 then
      return 1
   else
      return call_memoized(fib, n - 1) + call_memoized(fib, n - 2)
   end
end


A few notes: 

1. The reason why I store the return value in a table all by itself is
that this way "nil" continues to be a valid return value of the
memoized function.

2. You can extend this to functions with arbitrary numbers of
arguments, but this requires iterating over the table arg, which
contains all function arguments; and calling the memoized function
with Lua's builtin "call" function.

3. You could even memoize global functions that have not been written
with it in mind. All you have to do is something like this:

function memoize(name)
   local f = getglobal(name)
   local wrapper = function(arg)
		      return call_memoized(%f, arg)
		   end
   setglobal(name, wrapper) -- replaces the memoized function with the wrapper
end

function fib(n)
   if n < 2 then
      return 1
   else
      return fib(n - 1) + fib(n - 2)
   end
end

>>> memoize("fib")
>>> print(fib(100)) --> now fib() is called only 100 times.

Gotta love the power of languages like Lua. :-)

- Christian