Re: [Caml-list] syntax of private constructors in CVS version

[Pierre Weis <pierre.weis@inria.fr>]

> > As you should already know, usual sum and product types in Caml
> > correspond to the mathematical notion of free algebraic data
> > structures. This is fairly useful and allows the modelization of a lot
> > of common data structures in practical programming
> > situations. However, besides the free algebra structures,
> > mathematicians use a lot of non-free algebras (so-called structures
> > defined via generators and relations). Private types aim at giving a
> > way to modelize those non-free structures. Equivalenetly, you can
> > think of private types as providing a way to implement types equipped
> > with invariants, quotient structures (i.e. sets of equivalence classes
> > for some equivalence relation on a free algebra), or data types with
> > canonical normal forms.
> 
> 
> Well said. If I may add: this can already be done using
> 
> classes, or abstraction of modules. However these tools
> are much *too* heavyweight, because they also hide the
> algebraic structure of the types completely.
> 
> The user then must provide all the accessor functions,
> for example, instead of using record labels or pattern matching.

Absolutely. That's just the idea behind private types: ensure the
necessary invariants but keep the ease of rpogramming new functions
via pattern matching (and save the burden to provide all the
accessors).

> For immutable values, establishing an invariant at construction
> time is enough to ensure the invariant is preserved: therefore,
> it is enough to make construction abstract to ensure all values
> of the type satisfy the invariants.

Exactly.

> Just for interest, this is not the case for mutable objects,
> for example:
> 
> 	type rational = private { mutable x: float; mutable y: float };
> 	...
> 	let mess_up_invariant (z:rational) = z.y <- 0.0
> 
> Be interested to know the treatment of records with mutable fields.
> Are they permitted? Or are the mutators disallowed?

Records with mutable fields are permitted. Mutators explicitely exported
as functions are allowed, other mutations are forbidden.

I once wrote a lot of arithmetics and helped people writing core
arithmetics libraries for Caml. I always thought we had a major flaw
in the design of the library, due to type abstraction: we were
constantly oscillating between two conflicting attitudes; on the one
hand, using abstract data types all over the place to preserve
invariants and on the other hand turning to concrete types, not to be
forced to code everything ourself within the module implementing the
ADT.

I think private types are also a good answer to the
problem. Implementation of rational numbers would use a record with
mutable fields, and define a rational creation and a normalization
functions, preserving invariants:

type rat = {
  mutable numerator : int;
  mutable denominator : int;
};;

let rec mk_rat n d =
 if d = 0 then failwith "mk_rat: null denominator" else
 if d < 0 then mk_rat (- n) (- d) else
 { numerator = n; denominator = d};;

(* Left as an exercise *)
let gcd n m = 1;;

let normalize_rat r =
 let g = gcd r.numerator r.denominator in
 if g <> 1 then begin
   r.numerator <- r.numerator / g;
   r.denominator <- r.denominator / g
 end;;

Then interface of the module would abstract creation and mutation:

type rat = private {
  mutable numerator : int;
  mutable denominator : int;
};;

val mk_rat : int -> int -> rat;;

val normalize_rat : rat -> unit;;

This way, there is no need to define access to numerator and
denominator, or even to write printing functions: the user can write
them easily:

open Rat;;

let print_rat r =
 normalize_rat r;
 match r with
 | { numerator = n; denominator = d} -> Printf.printf "%d/%d" n d;;   

Also, any attempt to mutate a rational is now statically rejected by
the typechecker:

let r = mk_rat 1 2 in
r.numerator <- 4;

Cannot assign field numerator of private type Rat.rat.

Hence, in a sense, private types can also serve as a primitive way to
turn a mutable data type into an immutable one outside its defining
implementation, provided that no mutating functions are exported.

A small addition for the language, a big step for the programmer :)

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners