Memoization in Erlang?

[Pete Kazmier]

The other day while reading something about dynamic programming in the
#erlang channel, I decided to try and implement memoization in Erlang.
I've included an implementation at the end of this message (please
bear in mind I'm still a newbie).  As a result of my endeavor, I have
a few questions:

1) Writing higher-order functions seems to be complicated in Erlang
   because there is no support for varargs.  Thus, in my example, I
   have this kludge to return an N-arg closure.  Is there a better
   way of handling this keeping in mind that the wrapper function
   should have the same interface as the memoized one?

2) In my kludge, I use erlang:fun_info/1 which states that it is
   intended for debugging use.  Does this preclude its use in my code?
   Should I instead just define memoize1/1, memoize2/1, memoize3/1,
   etc ...

3) In lieu of my kludge, I started to wonder if I could dynamically
   construct a string of code, then somehow compile that on the fly,
   and return the resulting function to the caller.  Is this even
   possible?  If so, would it have access to the closed over variable?

4) Are there better ways to implement memoization in Erlang?  Would
   using the process dictionary be a bad idea?  My first thought was
   to store the cached values in it, and then the whole thing could be
   implemented in a single function without the use of processes.

     memoize(Fun) ->
         fun(Arg) ->
             case get(Arg) of
                 undefined -> Value = Fun(Arg), put(Arg, Value), Value;
                 Value     -> Value
             end
         end.

    However, it seems from my reading that most people would frown
    upon its use.  I'm not sure if this use would be an exception to
    the rule, or if its a prime example of why it shouldn't be used.

Thanks,
Pete


%% Attempt at memoization in Erlang.
%%
%% Usage:
%% 
%% 2> F = fun(X,Y) -> io:format("Computing~n",[]), X+Y end.
%% #Fun<erl_eval.12.118843560>
%% 3> G = memoize:memoize(F).
%% #Fun<memoize.2.70634243>
%% 4> G(1,1).
%% Computing
%% 2
%% 5> G(1,1).
%% 2
%% 6>

-module(memoize).
-export([memoize/1, loop/2]).

memoize(Fun) ->
    Pid = spawn(?MODULE, loop, [Fun, dict:new()]),
    case erlang:fun_info(Fun, arity) of
        {arity, 0} ->
            fun() -> callit(Pid, []) end;
        {arity, 1} -> 
            fun(A1) -> callit(Pid, [A1]) end;
        {arity, 2} -> 
            fun(A1, A2) -> callit(Pid, [A1, A2]) end;
        {arity, 3} -> 
            fun(A1, A2, A3) -> callit(Pid, [A1, A2, A3]) end;
        {arity, 4} -> 
            fun(A1, A2, A3, A4) -> callit(Pid, [A1, A2, A3, A4]) end;
        {arity, _} ->
            exit(Pid, normal),
            erlang:error("Erlang's lack of varargs stinks doesn't it?")
    end.

callit(Pid, Args) ->
    Pid ! {memo, self(), Args},
    receive 
        {_, {'EXIT', Reason}} -> erlang:error(Reason);
        {fresh, Value}        -> Value;
        {cache, Value}        -> Value
    end.

loop(Fun, Cache) ->
    receive 
        {memo, From, Args} ->
            case dict:find({args, Args}, Cache) of
                {ok, Value} ->
                    From ! {cache, Value},
                    loop(Fun, Cache);
                error       ->
                    Value = (catch apply(Fun, Args)),
                    From ! {fresh, Value},
                    loop(Fun, dict:store({args, Args}, Value, Cache))
            end
    end.