Memoization in Erlang?

Vlad Dumitrescu vlad_dumitrescu@REDACTED
Wed Feb 1 10:00:56 CET 2006


 
Hi!

A similar approach to that suggested by Ulf is to use a parse transform. You
define a transformation of the code that at takes place at compile time and
you can do whatever you like with the code. I have somewhere at home a
memoization implementation doing that, I'll look for it.

The basic idea is that you write a function as usual, for example
	ff(X, Y) ->
		X*Y.

You mark the function as memoizable and declare the parse transform to be
used
	-memoize({ff, 2}).
	-compile({parse_transform, memoize}).

The transform makes the compiled code look something like
	ff(X, Y) ->
		case memo_db:search({?MODULE, ff, 2, {X, Y}}) of
			{ok, Value} ->
				Value;
			false ->
				Res = ff_1(X, Y),
				memo_db:store({?MODULE, ff, 2, {X, Y}},
Res),
				Res
		end.

	ff_1(X, Y) ->
		X*Y.

You are then free to implement memo_db as you like, using ets for example. 

Writing parse transforms isn't for the weakhearted, however :-) But not so
more difficult than "regular" dynamic code generation. Ulf has published
here on the list a module that helps a lot,
www.erlang.org/ml-archive/erlang-questions/200511/msg00080.html 

Best regards,
Vlad




More information about the erlang-questions mailing list