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

[Caml-list] Memoizing (was: static variables...)
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2002-06-18 (08:40) From: William Lovas Subject: Re: [Caml-list] Memoizing (was: static variables...)
```On Mon, Jun 17, 2002 at 03:56:04PM +0200, Benedikt Rosenau wrote:
> I tried to memoize the Ackermann function
>
> # let rec ack m n =
>     if m = 0 then n + 1
>     else if n = 0 then ack (m - 1) 1
>     else ack (m - 1) (ack m (n - 1))
> val ack : int -> int -> int = <fun>
> # let my_ack = memoize ack;;
> val my_ack : int -> int -> int = <fun>
>
>
> The type checker deals with the 'a being an (int -> int).
> However, I noticed no speedup. So, I transformed the
> Ackermann to the tupled version, ie "let ackermann (m, n)...",
> but to no avail.
>
> What is the mistake?

Benedikt,

I think the problem is something like this: when you call memoize (and bind
the result, for that matter), you create a new closure (above, you call it
`my_ack').  This *closure* is memoized, but recursive calls inside it,
which refer to the original closure (`ack') are not.

Since Ackermann's function does a lot of repeated computation (correct me
if i'm wrong), it would benefit from a sort of "total memoization", but
i've been having a hard time figuring out how that would work in O'Caml.
I think this is what John Prevost was aiming to solve with his "delayed
binding" recursion, but i haven't managed to contrive a complete solution
using that method -- either we have only top-level calls to the function
being memoized, or no memoization goes on at all.  E.g.,

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

(* simple binding *)
let rec fib n = recfib fib n;;

(* through memoize *)
let rec wrong_fib_1 n = memoize (recfib wrong_fib_1) n;;

(* another way, also wrong *)
let wrong_fib_2 = memoize fib;;

(* *boggle* -- too tired to think about it, but also doesn't work *)
let rec wrong_fib_3 n = recfib (memoize (recfib wrong_fib_3)) n;;

Now, if we do:

wrong_fib_1 30;; (* takes a very long time *)
wrong_fib_1 30;; (* still takes a very long time -- not memoized
at all *)

wrong_fib_2 30;; (* takes a very long time -- shouldn't, if fully
memoized *)
wrong_fib_2 30;; (* instantaneous -- top-level is memoized *)

wrong_fib_3 30;; (* like wrong_fib_1, very slow *)
wrong_fib_3 30;; (* still slow -- no memoization happening *)

Note that we can observe the correct behaviour by writing the memoized
`fib' directly, e.g.:

let rec memo_fib =
let hash = Hashtbl.create 20 in
function
| 0 | 1 -> 1
| n -> if Hashtbl.mem hash n
then Hashtbl.find hash n
else let v = memo_fib (n-1) + memo_fib (n-2) in
(Hashtbl.replace hash n v;
v)
;;

memo_fib 30;; (* instantaneous -- all recursive calls are memoized *)

Unfortunately, this is not a very general solution.  I suspect a
general solution, like for example Mark-Jason Dominus's Perl module
Memoize.pm, requires a stateful environment (i think the Perl version
uses code references).  The problem with an elegant O'Caml solution, i
think, is that the inner recursive calls are part of the definition
environment of the recursive function (i.e. part of the closure), and
there's no way to change them without writing a new function (and thus
creating a new closure).

Does anyone have any thoughts on this?  Am i missing something obvious?

William
-------------------
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

```