Memoization in Erlang?

[Ulf Wiger (AL/EAB)]

Thomas Johnsson
> >
> What, you can do function equality in Erlang??
> I hadn't realized....

You mean I actually have to verify my
suggestions before posting them?  ;)

I will admit that I just plainly assumed
that it would work. My original suggestion
was to use erlang:fun_info(F) as a key.

> That's highly dubious ... When are two function
> equal according the the Erlang implementation?

Snipped from utils.c in erts/emulator/beam:

   case FUN_SUBTAG:
     {
       ErlFunThing* f1;
       ErlFunThing* f2;
       int num_free;
       int i;

       if (is_not_fun(b))
           return 0;
       f1 = (ErlFunThing *) fun_val(a);
       f2 = (ErlFunThing *) fun_val(b);
       if (f1->fe->module != f2->fe->module ||
           f1->fe->old_index != f2->fe->old_index ||
           f1->fe->old_uniq != f2->fe->old_uniq ||
           f1->num_free != f2->num_free) {
           return 0;
       }
       num_free = f1->num_free;
       for (i = 0; i < num_free; i++) {
           if (!EQ(f1->env[i], f2->env[i])) {
               return 0;
           }
       }
       return 1;
     }

I think this validates my claim.


> 25> fun()-> x end.
> #Fun<erl_eval.20.102880425>
> 26> (fun()-> x end) == (fun()-> x end).
> true

...which is fine.

> 27> (fun(X)-> X end) == (fun(X)-> X end).
> true

...also fine.

> 28> (fun(X)-> 2*X end) == (fun(X)-> X+X end).
> false

Seems ok. They are not equal, but equivalent.


> 29> (fun(X)-> X end) == (fun(Y)-> Y end).
> false

Again, equivalent, but not equal:

5> erlang:fun_info((fun(X) -> X end),env).                     
{env,[[],
      none,
      {eval,#Fun<shell.17.62614885>},
      [{clause,1,[{var,1,'X'}],[],[{var,1,'X'}]}]]}
6> erlang:fun_info((fun(Y) -> Y end),env).
{env,[[],
      none,
      {eval,#Fun<shell.17.62614885>},
      [{clause,1,[{var,1,'Y'}],[],[{var,1,'Y'}]}]]}

In practice for compiled code, two funs in the
same module will still have different indexes,
so comparing the environments will not happen.
In the shell, it _does_ seem to happen.

For the memoization support, if two equivalent
functions are compared and found to differ,
that means that you will evaluatem once separately,
which is probably OK. For memoization to work
the functions need to be free from side-effects,
so the end result will be slightly worse
performance (essentially a cache miss).

/Uffe