Unique identifier for function object

Learning
1

I have a type which, among other fields, contains a field to cache the result of an expensive operation.

type t = {
  (* ... *)
  mutable result_cache: int option;
}

where mutable_cache starts as None. Then there’s this expensive_fun : t -> int, which in fact first checks if .result_cache is Some x, and if yes just returns x, else actually computes the function, stores the result in .result_cache and returns the value.

This works fine if there’s just one expensive_fun. I was to extend it for the case when there are several different expensive_funs (which of course return different results, all of which need to be cached). My idea was writing

module M = Map.Make(???)
type t = {
  (* ... *)
  mutable result_cache: int M.t;
}

where the cache would be somehow a map from functions to results. This apparently would work, but this needs a way to give a unique identifier to each function (the key in the map), which I don’t know how to do! I’m thinking each function has a fixed address in the code, right, so that is a unique identifier? Am I correct? But what if the function is actually a “runtime-allocated/generated closure”, then this isn’t true anymore, because it gets shifted around by the gc? I guess I’m a bit confused because I don’t have a clear picture of how first-class functions are represented.

2

It would be easier to write a wrapper function memo that memoizes functions of type t -> int. Then you could do e.g.

let expensive_fun1 = memo expensive_fun1
let expensive_fun2 = memo expensive_fun2
...

And now you can use these new wrapped versions which will maintain their own internal caches.

3

You can use a custom hash table for that. The polymorphic hash function works on closures. You just need to specify physical equality for testing hash key collisions:

That is somethig like:

module Func = struct
  type nonrec t = t -> int
  let equal = ( == )
  let hash = Hasthbl.seeded_hash
end 

(** 'a Func_tbl.t = (t -> int, 'a) Hashtbl.t *)
module Func_tbl =  Hashtbl.MakeSeeded (Pred)

Be aware however that this hashes closures not functions. In the following:

let f a (x : t) = 3
let g0 = f "ha"
let g1 = f "hi"

if you cache g0 and g1 they will cache twice.

4

Another approach that has the virtue of giving you an actual integer the system guarantees is temporally unique among all other such identifiers in the system is to wrap your expensive function in an object method and use the Oo.id function to obtain the identifier of the object.