[Caml-list] memoization and CPS

[Pietro Abate <Pietro.Abate@anu.edu.au>]

Hi all,
I'm trying to understand and merge these two programming techniques:
memoization and CPS. Gogling around I found these two nice
implementations of the fibonacci function. I'm now trying to merge
these two technique and write a memo-cps-fib function, but I suspect
I'm missing something important... are these two styles compatible ?
Or the very nature of the CPS make impossible to exploit memoization ?

tnx,
p

-------------
let memoize f =
  let hash = Hashtbl.create 20 in
  let rec f' a =
    try Hashtbl.find hash a
    with Not_found ->
      let b = f f' a in
        Hashtbl.add hash a b; b
  in
    f';;

let recfib recfib = function
  | 0 | 1 -> 1
  | n -> recfib (n-1) + recfib (n-2);;

let fib = memoize recfib;;
---------------

let rec fibcps i k =
    match i with
    |1 |0 -> k 1
    |_ ->
            fibcps (i - 1) ( fun v1 ->
            fibcps (i - 2) ( fun v2 ->
                k ( v1 + v2 )
            ))
;;

let new_memoize () =
  let stow = Hashtbl.create 20 in
  fun f x -> try
     Hashtbl.find stow x
  with Not_found ->
     let v = f x in
     Hashtbl.add stow x v;
     v
;;
(* doesn't work... *)
let ff i = fibcps i (fun x->x) ;;

(* doesn't work either... *)
let k = new_memoize () (fun x->x);;
let ff i = fibcps i k;;

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

(* it partially works (it dosen't cache intermidiate 
computations), but it's not CPS *)
let ff = new_memoize () fib;;

-- 
Civilization advances by extending the number
of important operations which we can perform 
without thinking. (Alfred North Whitehead)

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners