Semantics of recursive function declarations

Learning
1

I am studying dynamic programming and I wrote the following as an exercise

let rec fibonacci = 
  let cache : (int,int) Hashtbl.t = Hashtbl.create 100 in
  fun n -> if n <= 1 then 1 else
  match Hashtbl.get_opt n with
  | Some x -> x
  | None -> let x = (fibonacci (n-1)) + (fibonacci (n-2)) in
            Hashtbl.add cache n x;
            x

When I came back to it later I thought for a moment it might be buggy, and that I should rewrite it as

let fibonacci = 
 let cache : (int,int) Hashtbl.t = Hashtbl.create 100 in
 let rec f n = 
   if n <= 1 then 1 else 
   match Hashtbl.find_opt cache n with
   | Some x -> x
   | None -> let x = (f (n-1)) + (f (n-2)) in
             Hashtbl.add cache n x;
             x
 in
 f

I had to test the first bit of code and time it to make sure it was running in linear time.

After all, why doesn’t the first bit of code reallocate a new cache every time fibonacci is called?

I get it after thinking about it for a while but it’s an interesting distinction between thinking of a recursive function call as a “goto” - i.e., go back to the first line of the function - and thinking about a recursive declaration as binding a name to a value which is permitted to refer to itself.

It’s pretty tricky, I think. I understand why let f = let x = (imperative code) in fun x → e only causes the imperative code to run once at the time of declaration of f, but it seems somehow trickier to convince myself of this when f is recursive.

2

If the missing rec keyword is not a typo and you meant

let rec fibonacci =
  let cache : (int,int) Hashtbl.t = Hashtbl.create 100 in
  fun n -> ...

a point to keep in mind is that this is not a definition of a recursive function. This is the definition of a recursive value, which happens to be a function.

In particular, this means that the definition follows the usual evaluation rule and that the name fibonacci in the body of the recursive definition refers to the future final value of this evaluation.

Typically, looking at the lambda IR for this version is quite instructive:

(let (letrec_function_context/374 = (caml_alloc_dummy 1))
  (letrec
    (fibonacci/274
       (function n/360[int] : int
         (if (<= n/360 1) 1
           (let
             (*match*/372 =
                (apply (field_imm 6 (global Stdlib__Hashtbl!))
                  (field_imm 0 letrec_function_context/374) n/360))
             (if (isint *match*/372)
               (let
                 (x/362 =[int]
                    (+ (apply fibonacci/274 (- n/360 1))
                      (apply fibonacci/274 (- n/360 2))))
                 (seq
                   (apply (field_imm 11 (global Stdlib__Hashtbl!))
                     (field_imm 0 letrec_function_context/374) n/360 x/362)
                   x/362))
               (field_imm 0 *match*/372))))))
    (seq
      (caml_update_dummy letrec_function_context/374
        (let
          (cache/316 = (apply (field_imm 0 (global Stdlib__Hashtbl!)) 0 100))
          (makeblock 0 cache/316)))
3

It was a typo, thank you, fixed!