Memoization in Erlang?

[Ulf Wiger (AL/EAB)]

Pete Kazmier wrote:

> > I'm not going to comment on the general
> > approach, just answer the specific questions.
> 
> Does this imply my general approach is fundamentally
> wrong?

No, it just means that I didn't spend enough time
thinking about the general approach. Answering the
specific questions requires less thought. (:


> > 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:

Actually, let me take that back. What I meant
was that using {Mod,Function,Args} tuples
could be more flexible, as apply(Mod,Function,Args)
naturally takes a variable number of arguments.

Another approach might be:

-define(eval(Expr) -> memo:eval(fun() -> Expr end)).

eval(F) when is_function(F, 0) ->
  case memo_db:lookup(F) of
     {ok, Cached} -> Cached;
     error ->
        Value = F(),
        memo_db:store(F, Value),
        Value
  end



This has the wonderful advantage that you can
memoize any expression. F uniquely identifies
the closure, including bound environment, so
it will serve as a key.

The memo_db module may well use the process
dictionary, as far as I'm concerned. (:

> 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 general, one should be careful with meta-
programming, but it's great fun, and can also
be extremely useful. As long as one is aware of 
the drawbacks (e.g. that it makes the code difficult
to read, and makes static analysis impractical),
erl_eval and the apply() BIF can be wonderful tools.

> 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?

The function would be interpreted, so actual 
execution would be much slower.

One nice use of erl_eval is of course that you
can accept code from the outside (say, a web form)
and interpret it, using a "blacklist" of functions
that you don't want to allow from untrusted code.
You can of course compile on the fly as well, if 
you intend to run the code frequently. You can of
course do both: interpret initially, and then 
compile if the program turns out to be called often.

/Uffe