Memoization, evaluation and environment

Learning
1

Hi,
I’m wondering how the following facts (related to definition of closures) should be interpreted and whether it is in relation with evaluation, environment handling or semantics of reference (things are not very clear for me, reformulations would be welcome).

  • In pure programming style, I may write let id x = x as well as let id = fun x -> x and obtain exactly the same function (in the sense that they are observationnally equivalent). That is, whether I put arguments on the left or on the right-hand side of the defining =, nothing changes.

  • In contrast with that, let us compare the two function mem_list and mem_list' below:

let mem_list = 
  let cache = ref [] in
   fun n -> cache := n :: !cache ; !cache;;

mem_list 3 ;;           (* outputs [ 3 ] *)      
mem_list 4 ;;            (* outputs [ 4 ; 3 ] *)

Thus, mem_list memoizes a list given by the user and its type is weakly polymorphic '_weak1 -> '_weak1 list. Now, let us change the code and just put the parameter n on the left-hand side:

let mem_list' n = 
  let cache = ref [ ] in
   cache := n :: !cache ; !cache;;

mem_list' 3 ;; (* outputs [ 3 ] *)
mem_list' 4 ;; (*outputs [ 4 ] *)

Now, there is no memoization, and the type of mem_list' is (fully) polymorphic 'a -> 'a list.

My surprise (which perhaps a little bit naive) comes from the fact that, morally, the variable n is “pure variable” and I would have thought that it’s place does not matter.

So, I’m trying to understand why things happen like this and how to abstract them up:

  • I guess that it has something to do with how environments are defined in OCaml. Is there a place where I may find the specification of environments?
  • But has it something to do with the operational semantics of the let ... in construction in OCaml? Again, a pointer would be welcome
2

First, note that let foo x = ... is just syntactic sugar for let foo = fun x -> ....

Second, you are wondering about the difference between

let foo =
  fun x -> ...

and

let foo =
  let y = bar in
  fun x -> ...

The second version executes bar, then creates a closure that associates to y the resulting value of that execution. So, the situation can be explained by: 1. environments only contain values, 2. let in constructs update environments eagerly to account for potential side effects.

3 Likes
3

Also,

let mem_list = 
  let cache = ref [] in
   fun n -> cache := n :: !cache ; !cache;;

is (almost) equivalent to

let cache = ref [] ;;
let mem_list = 
   fun n -> cache := n :: !cache ; !cache;;

except that when you put the cache definition inside the let in you cannot access it (it’s become a local variable instead of a global one) but it’s still out there in the system somewhere

1 Like
4

There is another way to see it. What you call a global variable is actually a variable local to the module. So, if it was shadowed by another definition from this module or if it was missing from the module signature, even this “global” variable would become inaccessible.

2 Likes
5

Ok, thanks for the explanations @silene and @jonathandoyle !