RE: [Caml-list] More problems with memoization

["Don Syme" <Don.Syme@microsoft.com>]

Hi Diego,

You may be interested in the approach to this kind of problem discussed
in http://dx.doi.org/10.1016/j.entcs.2005.11.038 (see also tech report
at http://research.microsoft.com/users/dsyme/papers/valrec-tr.pdf).
Under that approach you get to write the code in a natural way as shown
below: fib_mem is defined recursively, but the "cache" function has the
natural "(a -> b) -> (a -> b)" type and is abstract and reusable (no
details as to the nature of the internal table are revealed).  

let cache f =
  let table = ref [] in
  fun n ->
     try
       List.assoc n !table
     with Not_found ->
       let f_n = f n in
	  table := (n, f_n) :: !table;
	  f_n

let rec fib_mem = 
   cache (function 
	    | 0 -> 0
	    | 1 -> 1
	    | n -> fib_mem (n - 1) + fib_mem (n - 2))


The use of a computation on the right of a "let rec" is allowed by
systematically introducing initialization holes using lazy values and
forces.  There are disadvantages to this approach, as it introduces a
potential for initialization unsoundness somewhat similar to those in
most designs and implementations of recursive modules.  However the
paper argues that in the balance it is not unreasonable for a strict
language to accept this in order to gain modularity and localize the
potential for unsoundness.  It is even more compelling when often
working with abstract APIs such as Java and .NET GUI libraries.

While this isn't OCaml, and may not ever be the right design for OCaml,
I've found it a useful technique to know even when doing C#, C++ and
OCaml programming, as a broad range of recursion puzzles can be
addressed by modelling the problem the "natural" way (e.g. more like
Haskell) and then using a translation that introduces initialization
holes systematically.  The translation of your sample into OCaml using
"lazy" initialization holes is shown below (for single recursion you can
also just use a "option ref").  Note "cache" does not change,
maintaining the property that the caching function is abstract and
reusable.

let (!!) x = Lazy.force x
let rec fib_mem' = lazy 
   cache (function 
	    | 0 -> 0
	    | 1 -> 1
	    | n -> !!fib_mem' (n - 1) + !!fib_mem' (n - 2))
   
let fib_mem = !!fib_mem'

FWIW it is well known that laziness can be used in essentially this way,
e.g. see Michel Mauny's early papers on laziness in OCaml.  However I've
not seen a paper that argues the case for making this the default
interpretation of "let rec" in a strict language.

Cheers
Don

 
   


-----Original Message-----
From: caml-list-bounces@yquem.inria.fr
[mailto:caml-list-bounces@yquem.inria.fr] On Behalf Of Diego Olivier
FERNANDEZ PONS
Sent: 02 October 2006 16:29
To: Jon Harrop
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] More problems with memoization

     Bonjour,

Quoting Jon Harrop <jon@ffconsultancy.com>:
> I believe you want to "untie the knot" of recursion, creating an   
> higher-order, auxiliary fibonacci function fib_aux that accepts the  
> recursive call as an argument:
>
> # let rec fib_aux fib = function
>     | 0 | 1 as n -> n
>     | n -> fib(n - 1) + fib(n - 2);;
> val fib_aux : (int -> int) -> int -> int = <fun>
>
[...]
> You can recover the ordinary fibonacci function using the Y
combinator:
[...]
> You can write a higher-order memoization function that accepts an
argument
> with the type of fib_aux:
> # memoize fib_aux 35;;
> - : int = 9227465

Your solution is similar to Andrej Brauer's one which is exactly what  
I was trying to avoid because it is too much intrusive. When you break  
the recursion in two functions you change the type of [fib] from
[fib : int -> int] to [fib : (int -> int) -> int -> int)].

In my first example you keep the type of [fib] and add a second  
function [fib_mem]. You can use anyone indifferently and hide the  
latter with the .mli
val fib : int -> int = <fun>
val fib_mem : int -> int = <fun>

When you compare your solution with what I am trying to do you see  
there is a big difference in locality and transparency

let rec fib = function
   | 0 -> 0
   | 1 -> 1
   | n -> fib (n - 1) + fib (n - 2)

transformed into

let rec fib = function
   | 0 -> 0
   | 1 -> 1
   | n -> fib_mem (n - 1) + fib_mem (n - 2)
and fib_mem = make_mem fib

The latter could even be done automatically by a source to source  
transformation (if it worked).

         Diego Olivier

_______________________________________________
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