Re: More problems with memoization

Re: More problems with memoization

[oleg]

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

More problems with memoization

[Diego Olivier FERNANDEZ PONS]

     Bonjour,

I wrote the following (classical) memoized code for the fibonacci  
function and I have been unsuccessfully trying to generalize it with a  
higher order function.

let rec fib = function
   | 0 -> 0
   | 1 -> 1
   | n -> fib_mem (n - 1) + fib_mem (n - 2)
and fib_mem =
   let table = ref [] in
     function n ->
       try
	List.assoc n !table
       with Not_found ->
	let f_n = fib n in
	  table := (n, f_n) :: !table;
	  f_n

# val fib : int -> int = <fun>
# val fib_mem : int -> int = <fun>

It works: fib 35 answers instantaneously.

Now I want to achieve the same result with a higher order function  
[make_memo] and apply it to fib

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

#val make_mem : ('a -> 'b) -> 'a -> 'b

Very well. Notice that it has one less parameter than the code posted  
by Andrej Bauer which has type memo_rec : (('a -> 'b) -> 'a -> 'b) ->  
'a -> 'b. The only difference is the line

let f_n = f n in ...
with respect to
let f_n = f g n in ... where g is the anonymous function itself

in the same way Bauer's [fib_memo] uses an extra parameter [self]

let fib_memo =
   let rec fib self = function
     | 0 -> 1
     | 1 -> 1
     | n -> self (n - 1) + self (n - 2)
   in
     memo_rec fib


Now I try to apply make_mem to but it does not work

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

# This kind of expression is not allowed as right-hand side of `let rec'

Ok... usually one only need to expand to avoid the problem

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

# val fib : int -> int = <fun>
# val fib_mem : int -> int = <fun>

But know fib 35 takes several minutes to be computed !

I believe I understand why: I am computing a different fib_mem for  
each value of n and applying it just after, while I wanted a single  
fib_mem to be used for all computations. In the process, the  
tabulation vanishes.

The only work around I found is to lift the table argument in [make_mem]

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

# val make_mem : ('a * 'b) list ref -> ('a -> 'b) -> 'a -> 'b = <fun>

And build fib in the following way

let fib_mem = function n ->
   let table = ref [] and
       fib = function
	| 0 -> 0
	| 1 -> 1
	| n -> fib_mem (n - 1) + fib_mem (n - 2)
   in make_mem table fib n

# fib_mem 35: instantaneous

The problem is that the memoization is much more intrusive, which is  
what I was trying to avoid.

         Diego Olivier