Re: [Caml-list] Memoizing (was: static variables...)

[William Lovas <wlovas@stwing.upenn.edu>]

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