[Caml-list] [q] on implementing of "memoization"

[Caml-list] [q] on implementing of "memoization"

[SooHyoung Oh]

In testing "memoization" of fib function, it is OK on
    let rec fib = ... and memo_fib n = memoize fib n;;
but it makes the ERROR on
    let rec fib = ... and memo_fib = memoize fib;;

The error message is
      This kind of expression is not allowed as right-hand side of `let rec'

Why does this error occur?
I can't find good description on ocaml manual.

One more thing:
Do you have any idea about ** generic ** and good implementation of
memoization?

The source is
----------------------------------
let lookup key table = List.assoc key !table;;
let insert key value table = table := (key, value) :: !table;;

let table = ref [];;
let memoize f n =
    try
        lookup n table
    with
    | Not_found ->
        let result = f n in
        insert n result table;
        result
;;

let rec fib = function
    | 0 -> 0
    | 1 -> 1
    | n -> memo_fib (n-1) + memo_fib (n-2)
and memo_fib n = memoize fib n
;;
----------------------

Thanks a lot!

---
SooHyoung Oh

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

Re: [Caml-list] [q] on implementing of "memoization"

[Yaron M. Minsky]

One thing you might want to try to keep track of is exceptions.  That
way, if a given memoized function throws an exception the first time, it
will keep on throwing that exception.

Another aproach I've found useful is cached memoization. Ttahat is, you
maintain an LRU cache of bounded size for the memoization.    You can
have the memoization function return both a ref to the maximum cache
size (so you can change it later) and the actual memoized function.

y

On Fri, 2003-04-11 at 21:20, SooHyoung Oh wrote:
> In testing "memoization" of fib function, it is OK on
>     let rec fib = ... and memo_fib n = memoize fib n;;
> but it makes the ERROR on
>     let rec fib = ... and memo_fib = memoize fib;;
> 
> The error message is
>       This kind of expression is not allowed as right-hand side of `let rec'
> 
> Why does this error occur?
> I can't find good description on ocaml manual.
> 
> One more thing:
> Do you have any idea about ** generic ** and good implementation of
> memoization?
> 
> The source is
> ----------------------------------
> let lookup key table = List.assoc key !table;;
> let insert key value table = table := (key, value) :: !table;;
> 
> let table = ref [];;
> let memoize f n =
>     try
>         lookup n table
>     with
>     | Not_found ->
>         let result = f n in
>         insert n result table;
>         result
> ;;
> 
> let rec fib = function
>     | 0 -> 0
>     | 1 -> 1
>     | n -> memo_fib (n-1) + memo_fib (n-2)
> and memo_fib n = memoize fib n
> ;;
> ----------------------
> 
> Thanks a lot!
> 
> ---
> SooHyoung Oh
> 
> -------------------
> 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
-- 
|--------/            Yaron M. Minsky              \--------|
|--------\ http://www.cs.cornell.edu/home/yminsky/ /--------|

Open PGP --- KeyID B1FFD916 (new key as of Dec 4th)
Fingerprint: 5BF6 83E1 0CE3 1043 95D8 F8D5 9F12 B3A9 B1FF D916



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

Re: [Caml-list] [q] on implementing of "memoization"

[Neel Krishnaswami]

SooHyoung Oh writes:
> 
> In testing "memoization" of fib function, it is OK on
>     let rec fib = ... and memo_fib n = memoize fib n;;
> but it makes the ERROR on
>     let rec fib = ... and memo_fib = memoize fib;;
> 
> The error message is
>       This kind of expression is not allowed as right-hand side of `let rec'
> 
> Why does this error occur? I can't find good description on ocaml
> manual.

The sorts of values you are allowed to use as the right-hand side of
a let rec expression is intentionally restricted, in order to prevent
people from being able to ever use an unitialized variable. If random
ML code were permitted, then you could write forms like this:

  let rec x = x

There's no sensible value x can be bound to! So there is a restriction
that you can only bind the rhs of a let rec to expressions that the
compiler can be sure will not lead to users accessing unitialized
variables. Currently, there are two classes of those, of which only
one is really important.[*] In particular, you can bind them to recursive
functions. Eg,

  let rec fact = fun n -> if n = 0 then 1 else n * fact (n - 1)

Here, we can be sure that fact will be defined before use, because it
is only referenced inside the body of the function, and the compiler
must obviously build the function before it can be called. 

That's why the first version of your code was accepted, and the second
didn't -- you defined a syntactic function expression in the first
version, and not in the second.

[*] The second legal kind of rhs is a constructor application -- eg,
you can write 'let rec ones = 1 :: ones' to get an infinite list of
ones. Kind of neat, but the manual is explicit that this is an
implementation-specific extension, and might go away. 

-- 
Neel Krishnaswami
neelk@alum.mit.edu

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