Memoization

Memoization

[Erik de Castro Lopo]

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

Re: [Caml-list] Memoization

[Andrej Bauer]

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

Re: [Caml-list] Memoization

[Erik de Castro Lopo]

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.

Re: [Caml-list] Memoization

[Mike Lin]

> 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

Re: [Caml-list] Memoization

[William Neumann]

(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

Re: [Caml-list] Memoization

[Walid Taha]

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.

|(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
|
|
|
|_______________________________________________
|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
|
|!DSPAM:4503307f144882042218820!

Re: [Caml-list] Memoization

[Jan Kybic]

> 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 <kybic@fel.cvut.cz>                       tel. +420 2 2435 5721
http://cmp.felk.cvut.cz/~kybic                      ICQ 200569450