From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id HAA27673; Thu, 24 Apr 2003 07:26:20 +0200 (MET DST)
X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id HAA26533 for <caml-list@pauillac.inria.fr>; Thu, 24 Apr 2003 07:26:18 +0200 (MET DST)
Received: from axiom.anu.edu.au (axiom.anu.edu.au [150.203.127.200])
	by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h3O5QGH22886
	for <caml-list@inria.fr>; Thu, 24 Apr 2003 07:26:17 +0200 (MET DST)
Received: from pulp.anu.edu.au (pulp.anu.edu.au [150.203.126.25])
	by axiom.anu.edu.au (8.11.2/8.11.2/SuSE Linux 8.11.1-0.5) with ESMTP id h3O5QE229390
	(using TLSv1/SSLv3 with cipher EDH-RSA-DES-CBC3-SHA (168 bits) verified NO)
	for <caml-list@inria.fr>; Thu, 24 Apr 2003 15:26:14 +1000
Received: from pulp.anu.edu.au (localhost [127.0.0.1])
	by pulp.anu.edu.au (8.12.9/8.12.9/Debian-3) with ESMTP id h3O5PZQ6014712
	for <caml-list@inria.fr>; Thu, 24 Apr 2003 15:25:35 +1000
Received: (from abate@localhost)
	by pulp.anu.edu.au (8.12.9/8.12.9/Debian-3) id h3O5PYgG014709
	for caml-list@inria.fr; Thu, 24 Apr 2003 15:25:34 +1000
Date: Thu, 24 Apr 2003 15:25:34 +1000
From: Pietro Abate <Pietro.Abate@anu.edu.au>
To: caml-list@inria.fr
Subject: [Caml-list] memoization and CPS
Message-ID: <20030424052534.GA6003@anu.edu.au>
Mail-Followup-To: Pietro Abate <Pietro.Abate@anu.edu.au>,
	caml-list@inria.fr
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
X-Operating-System: GNU/Linux
X-Organization: Research School of Information Science and Engineering (Australian National University)
User-Agent: Mutt/1.5.4i
X-Spam: no; 0.00; pietro:01 abate:01 memoization:01 fibonacci:01 memoize:01 hash:01 hashtbl:01 recfib:01 stow:01 rec:01 match:02 partially:02 computations:03 cps:04 let:04 
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

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