From: Pierre Weis <weis@pauillac.inria.fr>
Message-Id: <199510191454.PAA20090@pauillac.inria.fr>
Subject: Re: [Q]: Mutable variant types in Caml Light 0.7
To: boos@gr6.u-strasbg.fr (Christian Boos)
Date: Thu, 19 Oct 1995 15:53:35 +0100 (MET)
In-Reply-To: <9510191031.AA19481@gr6> from "Christian Boos" at Oct 19, 95 11:31:13 am
[ English abstract at the end of the message]
> Pour définir des types "union", il y a deux approches possibles :
>
> a) type t1 = A1 of int * float * string
> b) type t2 = A2 of record
> and record = { a:int; b:float; c:string; }
>
> Je crois être en présence du dilemme suivant :
> - sur le plan efficacité, a) > b) :
> a) 'allocation à plat' -> économe en espace
> b) indirection vers l'enregistrement -> lent
Vous ne pouvez pas pre'sager de la manie`re dont le compilateur va
repre'senter vos donne'es.
(Par exemple pour Caml V3.1 vos hypothe`ses sont invalide'es: une
donne'e du type t1 prend le'ge`rement plus de place qu'une donne'e de
type t2: 2 cellules (donc 4 mots) contre un vecteur a` 3 cases.)
> - sur le plan souplesse d'utilisation, b) > a) :
A mon avis c'est de'cisif en faveur de b). Surtout dans la mesure ou`
un changement de compilateur risque de rendre caduque cette pseudo
optimisation.
> type t = A of { a:int; mutable b:float; c:string; }
Cette proposition a longtemps agite' la communaute' des de'veloppeurs
de Caml: faut-il distinguer types somme et types produit ou bien
conside'rer des types ``somme de produit'' ?
L'avantage de cette notion est de pouvoir surcharger les e'tiquettes
sans aucun proble`me puisque le constructeur le`ve toutes les
ambiguite's.
Le proble`me de l'approche est le statut du record argument du
constructeur A: ce ne peut pas e^tre une valeur de premie`re classe du
langage si l'on veut garder l'alge`bre de types actuelle de Caml (ce
qui entrai^ne que ce record n'a pas de type!), et si l'on veut allouer
la valeur de type t ``a` plat'' (ce qui signifie que le record n'a pas
d'existence autonome en dehors d'une valeur de type t construite avec
le constructeur A).
En conse'quence on ne peut pas admettre de lier ce record dans un
filtrage comme (function A x -> ...). Sinon on pourrait retourner le
record avec (function A x -> x) qui n'est pas typable. Pourtant il
faut bien nommer le record pour pouvoir acce'der a` ses champs, en
e'crivant par exemple (function A x -> x.a) qui n'est pas dangereux et
est de type t -> int.
Une solution e'ventuelle est de supprimer le mot-cle' of dans ce type
de de'finition (ce qui souligne que A n'a pas d'argument manipulable),
et d'interdire la liaison du record au filtrage:
type t = A { a:int; mutable b:float; c:string; }
Les filtrages A {a = 1; _} -> ... et match x with A _ -> x.a seraient
alors autorise's et A x -> interdit ...
Une solution plus simple et uniforme serait d'inte'grer le marqueur A
au record comme un champ sans valeur associe'e:
type t = {A; a:int; mutable b:float; c:string; }
On filtrerait et manipulerait alors normalement le record...
> type t = A of int * (mutable float) * string
Cette syntaxe a existe' dans une vieille version de Caml Light. Elle a
e'te' abandonne'e. D'ailleurs la notation mutable pour les arguments
de constructeurs de type somme tend a` disparai^tre: a` ma
connaissance elle n'existe plus en CSL.
[English
I give a short translation of the original message:
>To define "union" types in Caml, you may use:
> a) type t1 = A1 of int * float * string
>or
> b) type t2 = A2 of record
> and record = { a:int; b:float; c:string; }
>It seems that a) is more efficient (flat allocation and faster
>access), while b) is more convenient (and more precise if you want to
define mutable fields).
> One could imagine to get the best of the two approaches with
> definitions such that:
> type t = A of { a:int; mutable b:float; c:string; }
> that define a sum type constructor with a record argument.
My answer is that:
1) You cannot guess which of a) and b) is more efficient in space or
access time: this entirely depends on the compiler and its runtime
system. (The Caml V3.1 compiler invalidates the hypothesis since b)
leads to more compact values than a), and, on the average, faster accesses).
2) If b) is more suitable for your application use b) regardless to
efficiency, since you don't know what your compiler will do.
3) The new feature is known as the definition of sum-product types.
The problem is that the Caml type algebra does not support records as
anonymous types. Thus, the record which is argument of the sum
constructor A has no type. So it cannot be used as a regular value,
cannot be named, and thus we can't access to its fields. I propose to
define these constructors as tags explicitely included in their record
arguments as in:
type t = {A; a:int; mutable b:float; c:string; }
this solve the problem since now the record is a first-class citizen
value.
]
Pierre Weis
----------------------------------------------------------------------------
WWW Home Page: http://pauillac.inria.fr/~weis
Projet Cristal
INRIA, BP 105, F-78153 Le Chesnay Cedex (France)
E-mail: Pierre.Weis@inria.fr
Telephone: +33 1 39 63 55 98
Fax: +33 1 39 63 53 30
----------------------------------------------------------------------------