Encoding of inferrable records

Question

As you probably know, records are somewhat special in ocaml, as each label has to be uniquely assigned to a nominal record type, i.e. the following function cannot be typed without context:

let f r = r.x

Proper first class records (i.e. things that behave like tuples with labels) are trivially encoded using objects, e.g.

let f r = r#x 

when creating the objects in the right way (i.e. no self-recursion, no mutation), they behave just like records.

I am however, somewhat unhappy with this solution for two reasons:

1. when making records updatetable (i.e. by adding an explicit "with_l" method for each label l), the type is somewhat too loose (it should be the same as the original record). Admitted, one can enforce this equality, but this is still inconvenient.

2. I have the suspicion that the OCaml compiler does not infer that these records are actually immutable: In a function

   let f r = r#x + r#x

would the compiler be able to run a common subexpression elimination?

For these reasons, I wonder if there is a better encoding:

Is there another (aside from using objects) type-safe encoding (e.g. using polymorphic variants) of records with inferrable type in OCaml? Can this encoding avoid the problems mentioned above?

Answer 1

Is there another (aside from using objects) type-safe encoding (e.g. using polymorphic variants) of records with inferrable type in OCaml?

For immutable records, yes. There is a standard theoretical duality between polymorphic records ("inferrable" records as you describe) and polymorphic variants. In short, a record { l_1 = v_1; l_2 = v_2; ...; l_n = v_n } can be implemented by

function `l_1 k -> k v_1 | `l_2 k -> k v_2 | ... | `l_n k -> k v_n

and then the projection r.l_i becomes r (`l_i (fun v -> v)). For instance, the function fun r -> r.x is encoded as fun r -> r (`x (fun v -> v)). See also the following example session:

# let myRecord = (function `field1 k -> k 123 | `field2 k -> k "hello") ;;
    (* encodes { field1 = 123; field2 = "hello" } *)
val myRecord : [< `field1 of int -> 'a | `field2 of string -> 'a ] -> 'a = <fun>
# let getField1 r = r (`field1 (fun v -> v)) ;;
    (* fun r -> r.field1 *)
val getField1 : ([> `field1 of 'a -> 'a ] -> 'b) -> 'b = <fun>
# getField1 myRecord ;;
- : int = 123
# let getField2 r = r (`field2 (fun v -> v)) ;;
    (* fun r -> r.field2 *)
val getField2 : ([> `field2 of 'a -> 'a ] -> 'b) -> 'b = <fun>
# getField2 myRecord ;;
- : string = "hello"

For mutable records, we can add setters like:

let ref1 = ref 123
let ref2 = ref "hello"
let myRecord =
  function
  | `field1 k -> k !ref1
  | `field2 k -> k !ref2
  | `set_field1(v1, k) -> k (ref1 := v1)
  | `set_field2(v2, k) -> k (ref2 := v2)

and use them like myRecord (`set_field1(456, fun v -> v)) and myRecord (`set_field2("world", fun v -> v)) for example. However, localizing ref1 and ref2 like

let myRecord =
  let ref1 = ref 123 in
  let ref2 = ref "hello" in
  function
  | `field1 k -> k !ref1
  | `field2 k -> k !ref2
  | `set_field1(v1, k) -> k (ref1 := v1)
  | `set_field2(v2, k) -> k (ref2 := v2)

causes a value restriction problem and requires a little more polymorphic typing trick (which I omit here).

Can this encoding avoid the problems mentioned above?

The "common subexpression elimination" for (the encoding of) r.x + r.x can be done only if OCaml knows the definition of r and inlines it. (Sorry my previous answer was inaccurate here.)

Answer 2

Very roughly speaking, an OCaml object is a hash table whose keys are its method name hash. (The hash of a method name can be obtained by Btype.hash_variant of OCaml compiler implementation.)

Just like objects, you can encode polymorphic records using (int, Obj.t) Hashtbl.t. For example, a function to get a value of a field l can be written as follows:

(** [get r "x"]  is poly-record version of [r.x] *)
let get r k = Hashtbl.find t (Btype.hash_variant k))

Since it is easy to access the internals unlike objects, the encoding of {r with l = e} is trivial:

 (** [copy_with r [(k1,v1);..;(kn,vn)]] is poly-record version of
     [{r with k1 = v1; ..; kn = vn}] *) 
 let copy_with r fields =
   let r = Hashtbl.copy r in
   List.iter (fun (k,v) -> Hashtbl.replace r (Btype.hash_variant k) v) fields

and the creation of poly-records:

 (** [create [(k1,v1);..(kn,vn)]] is poly-record version of [{k1=v1;..;kn=vn}] *)
 let create fields = copy_with fields (Hashtbl.create (List.length fields))

Since all the types of the fields are squashed into one Obj.t, you have to use Obj.magic to store various types into this implementation and therefore this is not type-safe by itself. However, we can make it type-safe wrapping (int, Obj.t) Hashtbl.t with phantom type whose parameter denotes the fields and their types of a poly-record. For example,

<x : int; y : float> Poly_record.t

is a poly-record whose fields are x : int and y : float.

Details of this phantom type wrapping for the type safety is too long to explain here. Please see my implementation https://bitbucket.org/camlspotter/ppx_poly_record/src . To tell short, it uses PPX preprocessor to generate code for type-safety and to provide easier syntax sugar.

Compared with the encoding by objects, this approach has the following properties:

• The same type safety and the same field access efficiency as objects
• It can enjoy structural subtyping like objects, what you want for poly-records.
• {r with l = e} is possible
• Streamable outside of a program safely, since hash tables themselves have no closure in it. Objects are always "contaminated" with closures therefore they are not safely streamable.

Unfortunately it lacks efficient pattern matching, which is available for mono-records. (And this is why I do not use my implementation :-( ) I feel for it PPX reprocessing is not enough and some compiler modification is required. It will not be really hard though since we can make use of typing of objects.

Ah and of course, this encoding is very side effective therefore no CSE optimization can be expected.

Answer 3

If I understand you correctly you're looking for a very special kind of polymorphism. You want to write a function that will work for all types, such that the type is a record with certain fields. This sounds more like a syntactic polymorphism in a C++ style, not as semantic polymorphism in ML style. If we will slightly rephrase the task, by capturing the idea that a field accessing is just a syntactic sugar for a field projection function, then we can say, that you want to write a function that is polymorphic over all types that provide a certain set of operations. This kind of polymorphism can be captured by OCaml using one of the following mechanisms:

1. functors
2. first class modules
3. objects

I think that functors are obvious, so I will show an example with first class modules. We will write a function print_student that will work on any type that satisfies the Student signature:

module type Student = sig
  type t
  val name : t -> string
  val age : t -> int
end


let print_student (type t)
    (module S : Student with type t = t) (s : t) =
  Printf.printf "%s %d" (S.name s) (S.age s)

The type of print_student function is (module Student with type t = 'a) -> 'a -> unit. So it works for any type that satisfies the Student interface, and thus it is polymorphic. This is a very powerful polymorphism that comes with a price, you need to pass the module structure explicitly when you're invoking the function, so it is a System F style polymorphism. Functors will also require you to specify concrete module structure. So both are not inferrable (i.e., not an implicit Hindley-Milner-like style polymorphism, that you are looking for). For the latter, only objects will work (there are also modular implicits, that relax the explicitness requirement, but they are still not in the trunk, but they will actually answer your requirements).

With object-style row polymorphism it is possible to write a function that is polymorphic over a set of types conforming to some signature, and to infer this signature implicitly from the function definintion. However, such power comes with a price. Since object operations are encoded with methods and methods are just function pointers that are assigned dynamically in the runtime, you shouldn't expect any compile time optimizations. It is not possible to perform any static analysis on something that is bound dynamically. So, of course, no Common Subexpression elimination, nor inlining. For functors and first class modules, the optimization is possible on a newer branch of the compiler with flamba (See 4.03.0+flambda opam switch). But on a regular compiler installation no inlining will be performed.

Different approaches

What concerning other techniques. First of all we can use camlp{4,5}, or ppx or even m4 and cpp to preprocess code, but this would be hardly idiomatic and of doubtful usefulness.

Another way, is instead of writing a function that is polymorphic, we can try to find a suitable monomorphic data type. A direct approach would be to use a list of polymorphic variants, e.g.,

type attributes = [`name of string | `age of int]
type student = attribute list  

In fact we even don't need to specify all these types ahead, and our function can require only those fields that are needed, a form of a row polymorphism:

let rec name = function
  | [] -> raise Not_found
  | `name n -> n
  | _ :: student -> name student

The only problem with this encoding, is that you cannot guarantee that the same named attribute can occur once and only once. So it is possible that a student doesn't have a name at all, or, that is worser, it can have more then one names. Depending on your problem domain it can be acceptable.

If it is not, then we can use GADT and extensible variants to encode heterogenous maps, i.e., an associative data structures that map keys to different type (in a regular (homogenous) map or assoc list value type is unified). How to construct such containers is beyond the scope of the answer, but fortunately there're at least two available implementations. One, that I use personally is called universal map (Univ_map) and is provided by a Core library (Core_kernel in fact). It allows you to specify two kinds of heterogenous maps, with and without a default values. The former corresponds to a record with optional field, the latter has default for each field, so an accessor is a total function. For example,

 open Core_kernel.Std

 module Dict = Univ_map.With_default

 let name = Dict.Key.create ~name:"name" ~default:"Joe" sexp_of_string
 let age  = Dict.Key.create ~name:"age"  ~default:18 sexp_of_int

 let print student = 
   printf "%s %d" 
     (Dict.get student name) (Dict.get age name)

You can hide that you're using universal map using abstract type, as there is only one Dict.t that can be used across different abstractions, that may break modularity. Another example of heterogeneous map implementation is from Daniel Bunzli. It doesn't provide With_default kind of map, but has much less dependencies.

P.S. Of course for such a redundant case, where this only one operation it is much easier to just pass this operation explicitly as function, instead of packing it into a structure, so we can write function f from your example as simple as let f x r = x r + x r. But this would be the same kind of polymoprism as with first class modules/functors, just simplified. And I assume, that your example was specifically reduced to one field, and in your real use case you have more complex set of fields.