Re: [Caml-list] mutability analysis too strict?

[Francois Pottier <francois.pottier@inria.fr>]

On Mon, Dec 10, 2001 at 12:13:19PM +0200, Ohad Rodeh wrote:
> 
> How do you propose building a repository of polymorphic values then?

Unless I'm mistaken, the short answer is, you can't. As pointed out by
Rémi, your proposed interface:

  module type Repos = sig
    val put : 'a -> 'b -> unit
    val get : 'a -> 'b
  end

is inherently unsafe. One solution is to use several repositories
(i.e. several hash tables). You can wrap them up into a single module if you
wish, but the client will then need to tell which repository (i.e. which hash
table) he wishes to access:

  module type Repositories = sig
    type ('a, 'b) repository
    val put : ('a, 'b) repository -> 'a -> 'b -> unit
    val get : ('a, 'b) repository -> 'a -> 'b
  end

Not very useful, though, since this merely paraphrases the interface for hash
tables.

Another solution is to create a single repository where keys and/or objects
belong to a suitably defined `universal' (also known as `dynamic') type. That
is, the repository would be a hash table of type [(univ, univ) Hashtbl.t],
where the abstract type [univ] supports the following operations:

  type univ
  type 'a tag

  val new_tag: unit -> 'a tag
  val in: 'a tag -> 'a -> univ
  val out: 'a tag -> univ -> 'a

A value of arbitrary type can be turned into a [univ] value by attaching it
with an explicit tag, using [in]. It can later be retrieved by matching it
against the same tag, using [out]. ([out] may fail dynamically if the tags do
not match.) [out] is type-safe because it requires a tag; it would be unsound
for [out] to have type unit -> 'a (same problem as for [get] above).

One possible implementation for [univ], where a tag is implemented as a
reference cell, was posted to the list a while ago, but I can't find it at the
moment. Another possible implementation implements tags using exception names.
(In this variant, the type [tag] disappears, and [new_tag] is a functor which
produces specialized versions of [in] and [out].) These solutions are rather
tricky to implement; furthermore, they are inefficient and unsafe, because
[out] involves a run-time check. You are probably better off using several
hash tables.

-- 
François Pottier
Francois.Pottier@inria.fr
http://pauillac.inria.fr/~fpottier/
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr