Memoization in Erlang?

[Pete Kazmier]

"Ulf Wiger \(AL/EAB\)" <ulf.wiger@REDACTED> writes:

> I'm not going to comment on the general approach,
> just answer the specific questions.

Does this imply my general approach is fundamentally wrong?

> Pete Kazmier wrote:
>> 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?
>
> In this particular case, perhaps apply(Module, Function, Args)
> would be better than using funs?

I do not understand, could you explain further?  I use apply in
loop/2, and my original implementation of memoize/1 was like this:

memoize(Fun) ->
    Pid = spawn(?MODULE, loop, [Fun, dict:new()]),
    fun(Args) -> callit(Pid, Args) end.

But the problem with this is that the function returned from memoize/1
no longer adheres to the interface of the original function.  I.e., if
the original function took 3 args, the closure returned from memoize/1
would only take a single argument that should be a list of 3 args.  As
a result, the two functions cannot be used interchangeably which is
important to me.  However, perhaps I misunderstood your comment.

>> 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 ...
>
> Instead of fun_info/1, you could use the guard function
> is_function(F, Arity), i.e.
>
>      if is_function(F, 0) ->
>              fun() -> callit(Pid, []) end;
>         is_function(F, 1) -> 
>              fun(A1) -> callit(Pid, [A1]) end;
>         is_function(F, 2) -> 
>              ...
>      end.

Perfect!  This will do very nicely.

>> 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?
>
> It is.
>
> Here's an example of how to generate "forms", compiling
> them, and then loading them into a running system:

[example snipped]

Thank you.  I will have to investigate this further this weekend when
I have more time.  One question that does come to the top of my mind
is regarding the use of erl_eval.  It seems that in most languages,
using eval us frowned upon and is a general indication that one is
doing something that one probably shouldn't be doing.  Is this the
case in Erlang as well?  In this context, would any performance issues
with the use of the eval be limited to just the creation of the
closure, or would they be involved each time the closure is actually
invoked?

>> 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.
>
> Using the process dictionary in a process that you
> control altogether is not necessarily a bad idea,
> but in your example code, I don't think you'd have
> trouble using e.g. dict.erl and caching the data
> in a dictionary 'loop variable' instead.

After reading some of the other responses by Vlad, it seems that an
ets table might be a good alternative.  This is what I came up with,
it would have to be modified to include the Module in the key as well
for robustness and I should use the guard function that Ulf pointed
out to me.  I think I like this version better because its less
complex. 

-module(memoets).
-export([memoize/1]).

memoize(Fun) ->
    catch ets:new(memo, [named_table]),
    case erlang:fun_info(Fun, arity) of
        {arity, 0} ->
            fun() -> callit(Fun, []) end;
        {arity, 1} -> 
            fun(A1) -> callit(Fun, [A1]) end;
        {arity, 2} -> 
            fun(A1, A2) -> callit(Fun, [A1, A2]) end;
        {arity, 3} -> 
            fun(A1, A2, A3) -> callit(Fun, [A1, A2, A3]) end;
        {arity, 4} -> 
            fun(A1, A2, A3, A4) -> callit(Fun, [A1, A2, A3, A4]) end;
        {arity, _} ->
            erlang:error("Erlang's lack of varargs sucks doesn't?")
    end.

callit(Fun, Args) ->
    case ets:lookup(memo, {Fun, Args}) of
        [] -> 
            Value = apply(Fun, Args),
            ets:insert(memo, {{Fun, Args}, Value}),
            Value;
        [{{Fun, Args}, Value}] -> 
            Value
    end.

            
Thanks for the help.  As a newcomer to Erlang, I appreciate the
insights.  I still wish Erlang had varargs as all of my higher order
functions have the above verbose code for returning the appropriate
closure, and the alternative to restricting the use of the HOF with
functions that take a single list argument artificially limits the
usefulness of them.

-Pete