Memoisation in OCaml and a Reference List

Question

I am learning OCaml. I know that OCaml provides us with both imperative style of programming and functional programming.

I came across this code as part of my course to compute the n'th Fibonacci number in OCaml

let memoise f =
  let table = ref []
  in
  let rec find tab n =
    match tab with
    | []           -> 
            let v = (f n)
            in
            table := (n, v) :: !table;
            v
    | (n', v) :: t -> 
            if n' = n then v else (find t n)
  in
  fun n -> find !table n

let fibonacci2 = memoise fibonacci1

Where the function fibonacci1 is implemented in the standard way as follows:

let rec fibonacci1 n =
  match n with
  | 0 | 1 -> 1
  |     _ -> (fibonacci1 (n - 1)) + (fibonacci1 (n - 2))

Now my question is that how are we achieving memoisation in fibonacci2. table has been defined inside the function fibonacci2 and thus, my logic dictates that after the function finishes computation, the list table should get lost and after each call the table will get built again and again.

I ran some a simple test where I called the function fibonacci 35 twice in the OCaml REPL and the second function call returned the answer significantly faster than the first call to the function (contrary to my expectations).

I though that this might be possible if declaring a variable using ref gives it a global scope by default.

So I tried this

let f y = let x = ref 5 in y;;
print_int !x;;

But this gave me an error saying that the value of x is unbounded.

Why does this behave this way?

Jeffrey Scofield Jeffrey Scofield · Accepted Answer · 2016-04-14T16:23:32

The function memoise returns a value, call it f. (f happens to be a function). Part of that value is the table. Every time you call memoise you're going to get a different value (with a different table).

In the example, the returned value f is given the name fibonacci2. So, the thing named fibonacci2 has a table inside it that can be used by the function f.

There is no global scope by default, that would be a huge mess. At any rate, this is a question of lifetime not of scope. Lifetimes in OCaml last as long as an object can be reached somehow. In the case of the table, it can be reached through the returned function, and hence it lasts as long as the function does.

In your second example you are testing the scope (not the lifetime) of x, and indeed the scope of x is restricted to the subexpresssion of its let. (I.e., it is meaningful only in the expression y, where it's not used.) In the original code, all the uses of table are within its let, hence there's no problem.

Although references are a little tricky, the underlying semantics of OCaml come from lambda calculus, and are extremely clean. That's why it's such a delight to code in OCaml (IMHO).

Memoisation in OCaml and a Reference List

1 Answers