From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <oleg@okmij.org>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: *
X-Spam-Status: No, score=1.6 required=5.0 tests=AWL,NO_REAL_NAME,SPF_FAIL 
	autolearn=disabled version=3.1.3
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38])
	by yquem.inria.fr (Postfix) with ESMTP id E7F28BC50
	for <caml-list@yquem.inria.fr>; Tue,  3 Oct 2006 07:10:01 +0200 (CEST)
Received: from selenite.metnet.navy.mil (selenite.metnet.navy.mil [192.16.167.32])
	by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id k9359tUp023670
	(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=FAIL)
	for <caml-list@inria.fr>; Tue, 3 Oct 2006 07:10:01 +0200
Received: (qmail 1593 invoked by uid 107); 3 Oct 2006 05:09:50 -0000
Received: from unknown (HELO Adric.metnet.fnmoc.navy.mil) (10.100.105.102)
  by selenite.metnet.navy.mil with SMTP; 3 Oct 2006 05:09:50 -0000
Received: by Adric.metnet.fnmoc.navy.mil (Postfix, from userid 760)
	id CBA5CAC04; Mon,  2 Oct 2006 22:06:02 -0700 (PDT)
To: diego.fernandez_pons@etu.upmc.fr
Cc: caml-list@inria.fr
Subject: Re: More problems with memoization
Reply-To: oleg@pobox.com
Errors-To: oleg@okmij.org
From: oleg@pobox.com
Message-Id: <20061003050602.CBA5CAC04@Adric.metnet.fnmoc.navy.mil>
Date: Mon,  2 Oct 2006 22:06:02 -0700 (PDT)
X-Miltered: at discorde with ID 4521F0A3.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!
X-Spam: no; 0.00; memoization:01 oleg:01 locality:01 fib:01 fib:01 replacing:01 camlp:01 camlp:01 trivial:01 recursion:01 implements:01 memoized:01 wrote:01 rec:01 rec:01 


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