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

[Neel Krishnaswami <neelk@alum.mit.edu>]

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