This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

[Caml-list] memoization and CPS
• Pietro Abate
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2003-04-24 (05:26) From: Pietro Abate Subject: [Caml-list] memoization and CPS
```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
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
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