Re: More problems with memoization

[oleg@pobox.com]

Diego Olivier wrote:

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

But it almost does:

let make_mem = fun table f ->
  function 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 = function
  | 0 -> 0
  | 1 -> 1
  | n -> mem fib (n - 1) + mem fib (n - 2)
and mem = make_mem (ref [])
;;

 fib 35;;
 - : int = 9227465
instantaneous.

The biggest difference is replacing "fib_mem" in your code with
"mem fib" in mine. The same number of characters in either case...
And yes, this can be done via camlp4... OTH, with camlp4 it is quite
trivial to convert a let rec expression to the one involving open
recursion. So, we can write something like

let fib n = funM MyModule n -> let rec fib function 0 -> 1 ... in fib n;;

and, depending on what MyModule actually implements, obtain either the usual
or the memoized Fibonacci (or even partially unrolled to any desired degree).