Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

[Caml-list] Memoization

225 views
Skip to first unread message

Erik de Castro Lopo

unread,
Sep 8, 2006, 8:36:06 PM9/8/06
to caml...@inria.fr
Hi all,

While searching Google for info about memoization I found this
Slashdot post:

http://developers.slashdot.org/comments.pl?sid=142494&cid=11942528

which states:

I simply Googled for "memoization Ocaml" and found that code:

http://www.emeraldtiger.net/modules.php?op= modload &name=News&file=article&sid=9

The author pointed out how "sweet" polymorphism is... one block
of code that can be used to memoize any function.

Unfortunately, the URL is dead. Does anybody have another link for
that code or some other polymorphic memoizer?

Cheers,
Erik
--
+-----------------------------------------------------------+
Erik de Castro Lopo
+-----------------------------------------------------------+
"It is forbidden for a Muslim to be a loyal friend to someone who does
not believe in God and His Prophet, or someone who fights the religion
of Islam." -- Fifth grade text book from Saudi Arabia
http://www.washingtonpost.com/wp-dyn/content/article/2006/05/19/AR2006051901769_pf.html

_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs

Andrej Bauer

unread,
Sep 9, 2006, 12:12:59 AM9/9/06
to caml...@inria.fr
Erik de Castro Lopo wrote:
>
> Unfortunately, the URL is dead. Does anybody have another link for
> that code or some other polymorphic memoizer?
>

I use the code below to show my students what can be done with
higher-order functions. For a real implementation, we would have to use
something more efficient than association lists (but then you might end
up writing a polymorphic version of the Map module). Improvements are
welcome.

--------------------
(** [memo f] is a memoized version of function [f]. If [f] makes
recursive calls, those are not memoized. In this example we use simple
asociation lists. It would be better to use efficietn search trees.
Alas, ocaml Map module is not polymorphic (for a good reason?). *)

let memo f =
let m = ref [] in
fun x ->
try
List.assoc x !m
with
Not_found ->
let y = f x in
m := (x, y) :: !m ;
y


(** [memo_rec f] is a memoized version of a recursive function [f].
The recursive function must not make calls to itself directly, but
rather via an extra "self" parameter, see example below. *)

let memo_rec f =
let m = ref [] in
let rec g x =
try
List.assoc x !m
with
Not_found ->
let y = f g x in
m := (x, y) :: !m ;
y
in
g

(** [memo_test f stamp renew] is a memoized version of function [f],
where [stamp] and [renew] are used to invalidate memoized values and
force them being recomputed. For example, [f] could be a function
which reads the contents of a file, [stamp] the function which returns
the file's modification time, and [renew] the function which compares
two modification times. Note that we keep storing new values in an
association list without removing old ones, so this creates a memory
leak. An intelligent implementation would, again, use efficient search
trees. *)

let memo_test f stamp renew =
let m = ref [] in
fun x ->
try
let y, s = List.assoc x !m in
let t = stamp x in
if renew s t then
let y = f x in
m := (x, (y, t)) :: !m ; y
else
y
with
Not_found ->
let y = f x in
let s = stamp x in
m := (x, (y, s)) :: !m; y


(** Example: the Fibonacci sequence, unmemoized, very inefficient. *)
let rec fib_slow = function
0 -> 1
| 1 -> 1
| n -> fib_slow (n - 1) + fib_slow (n - 2)

(** Example: a memoized version of the Fibonacci sequence. *)
let fib_memo =
let rec fib self = function
0 -> 1
| 1 -> 1
| n -> self (n - 1) + self (n - 2)
in
memo_rec fib
--------------------

Erik de Castro Lopo

unread,
Sep 9, 2006, 3:59:33 AM9/9/06
to caml...@inria.fr
Andrej Bauer wrote:

> I use the code below to show my students what can be done with
> higher-order functions. For a real implementation, we would have to use
> something more efficient than association lists (but then you might end
> up writing a polymorphic version of the Map module). Improvements are
> welcome.

Thanks Andrej, thats interesting. Is there any reason you didn't
use a Hashtbl instead of the association list? I don't really think
the the ordering of the Map module is needed.

The particular function I'm trying to memoize is a function of
two integers. I was hoping it might be possible to write a
memoize function that memoizes any function of a small arbitrary
number of parameters. Thinking about it some more I'm beginning
to this this is not possible.

Cheers,
Erik
--
+-----------------------------------------------------------+
Erik de Castro Lopo
+-----------------------------------------------------------+

Saying Python is easier than C++ is like saying that turning a
light switch on or off is easier than operating a nuclear reactor.

Mike Lin

unread,
Sep 9, 2006, 11:50:42 AM9/9/06
to Erik de Castro Lopo
> The particular function I'm trying to memoize is a function of
> two integers. I was hoping it might be possible to write a
> memoize function that memoizes any function of a small arbitrary
> number of parameters. Thinking about it some more I'm beginning
> to this this is not possible.

It is not very costly to give multiple parameters as a tuple. I think
I remember reading that the native code compiler can do this without a
heap allocation. -Mike

William Neumann

unread,
Sep 9, 2006, 5:23:16 PM9/9/06
to Erik de Castro Lopo
(resending to include the mailing list)

On Sep 8, 2006, at 6:33 PM, Erik de Castro Lopo wrote:

> Unfortunately, the URL is dead. Does anybody have another link for
> that code or some other polymorphic memoizer?

You may want to take a look at this paper by Bruce McAdam that uses a
fix-point combinator to create all sorts of wrappers for functions,
including memoization. The examples ore in SML, but translate pretty
easily to OCaml.

http://www.lfcs.inf.ed.ac.uk/reports/97/ECS-LFCS-97-375/


William D. Neumann

"I eat T-bone steaks, I lift barbell plates, I'm sweeter than a
German chocolate cake. I'm the reflection of perfection, the number
one selection. I'm the man of the hour, the man with the power, too
sweet to be sour. The ladies' pet, the men's regret, where what you
see is what you get, and what you don't see, is better yet."

--Superstar Billy Graham

Jan Kybic

unread,
Sep 30, 2006, 4:54:41 AM9/30/06
to Erik de Castro Lopo
> While searching Google for info about memoization I found this

Hope this helps: A very simple memoization (not written by me) is

(* [memo f] creates a memoized version of a single parameter function [f] *)
val memo : ('a -> 'b) -> ('a -> 'b)


let memo f =
let h = Hashtbl.create 11 in
fun x -> try
Hashtbl.find h x
with Not_found ->
let r = f x in ( Hashtbl.add h x r; r )

This can be extended to function of two parameters as follows:

let memo2 f = curry ( memo ( uncurry f ) )

let uncurry f (x,y) = f x y

let curry f x y = f (x,y)

I further implemented a memoization system for my application based on
hash tables which also allows selective forgetting of cached values if
the memory is short. Let me know if you need it.

Jan

--
-------------------------------------------------------------------------
Jan Kybic <ky...@fel.cvut.cz> tel. +420 2 2435 5721
http://cmp.felk.cvut.cz/~kybic ICQ 200569450

Walid Taha

unread,
Oct 5, 2006, 11:26:10 PM10/5/06
to William Neumann

We recently had to put together a generic account of memoization in a
functional language (in our case OCaml) so that we can address a staging
problem in a generic manner. Section 3 of

http://www.cs.rice.edu/~taha/publications/conference/pepm06.pdf

is a low-impact buildup to memoization as a monadic library.

Walid.

|!DSPAM:4503307f144882042218820!

0 new messages