[Q]: Mutable variant types in Caml Light 0.7

[Q]: Mutable variant types in Caml Light 0.7

[Christian Boos]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1517 bytes --]



Bonjour,

J'aimerais avoir un avis sur le problème suivant.

Pour définir des types "union", il y a deux approches possibles :

a)	type t = A of int * float * string

ou bien

b)	type t = A 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

 - sur le plan souplesse d'utilisation, b) > a) :
    a) une indication 'mutable' s'applique obligatoirement à
       l'ensemble des champs, qui de ce fait sont alloués en tant que
       n-uplets. On perd donc les avantages mentionnés précedemment,
       sans avoir de réel confort d'utilisation.
    b) bien sûr, il est ici possible de déclarer chaque champ
       'mutable'.

Si ce raisonnement est correct, une amélioration pourrait alors être
effectuée, permettant de cumuler efficacité et souplesse :
  - soit une grosse refonte de la syntaxe des types, pour avoir des
déclarations à la SML (mais plus expressives, en raison du 'mutable') :
	
	type t = A of { a:int; mutable b:float; c:string; }

  - soit en faisant une modification sur la syntaxe de l'extension 3.6
permettant d'avoir des types "union" mutables :

	type t = A of int * (mutable float) * string


... par ailleurs, qu'en est-il de ce problème en CSL ?


Merci pour vos conseils !


------------------------------------------------------------------
Christian Boos
Doctorant en Informatique
ULP - Strasbourg.

Re: [Q]: Mutable variant types in Caml Light 0.7

[Pierre Weis]

[ 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
----------------------------------------------------------------------------

Re: [Q]: Mutable variant types in Caml Light 0.7

[Andrew Conway]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1290 bytes --]



Christian Boos wrote:
> ...
>Si ce raisonnement est correct, une amélioration pourrait alors être
>effectuée, permettant de cumuler efficacité et souplesse :
>  - soit une grosse refonte de la syntaxe des types, pour avoir des
>déclarations à la SML (mais plus expressives, en raison du 'mutable') :
>	
>	type t = A of { a:int; mutable b:float; c:string; }
>
>  - soit en faisant une modification sur la syntaxe de l'extension 3.6
>permettant d'avoir des types "union" mutables :
>
>	type t = A of int * (mutable float) * string

Moi aussi!

Why I would like it? Well, although I generally like strictness, 
sometimes lazy lists are useful. So I decided to make some lazy list
routines. I used the following type:

type 't lazylist =
          EndLL 
        | Element of 't llcont
        | Unconstructed of (unit -> 't lazylist)
and 't llcont = { value : 't ; mutable next : 't lazylist}
;;

The trouble is that takes 5 words per evaluated element, whereas 
with Christian's suggestion it could be done in 3 words like 
normal lists, as well as avoiding the ugliness in the above type
definition. Neither are huge things for me, but since it has already been
suggested, I second it.

( Incidentally, is there a nicer basic structure for lazy lists? )
			
Thanks again,

			Andrew.
 

Re: [Q]: Mutable variant types in Caml Light 0.7

[Pierre Weis]

> Why I would like it? Well, although I generally like strictness, 
> sometimes lazy lists are useful. So I decided to make some lazy list
> routines. I used the following type:
> 
> type 't lazylist =
>           EndLL 
>         | Element of 't llcont
>         | Unconstructed of (unit -> 't lazylist)
> and 't llcont = { value : 't ; mutable next : 't lazylist}
> ;;
> 
> The trouble is that takes 5 words per evaluated element, whereas 
> with Christian's suggestion it could be done in 3 words like 
> normal lists, as well as avoiding the ugliness in the above type
> definition. Neither are huge things for me, but since it has already been
> suggested, I second it.
> 
> ( Incidentally, is there a nicer basic structure for lazy lists? )

If you need lazy construction of lists that are consumed once unfrozen
you may use streams (in Caml Light only).

I do not discuss about efficiency of the representation of values,
since this issue is higly compiler dependent.
I just present my best way to implement lazyness in (core) Caml.

If you really want to use lazyness you probably need to start by
defining the type of frozen objects:

type 'a frozen =
  Freeze of (unit -> 'a)
| Val of 'a;;

Then you have to declare you're lazy data structures involving 'a
frozen parts.

For lazy lists you must use two types: one for the union of empty and
non-empty lists, the other for the kind of cells you use for your lazy
lists (are your list ``lazy in the head'' and ``lazy in the tail'' or
only ``lazy in the tail'' ?). I assume you want lists lazy in the
tail:

type 'a llist =
  Nil
| Cons of 'a cell

and 'a cell = { hd : 'a ; mutable tl : 'a llist frozen}
;;

Now you can define functions and functionals that carefully implements
call by need or call by name (with call by name, computations are not
shared: a frozen value may be ``forced'' as many times as necessary;
in contrast, with call by need, the frozen value is physically replaced by the
result of its computation, which is thus shared. I assume you want
call by need):

let rec mapl f = function
  Nil -> Nil
| Cons {hd = x; tl = Val l} ->
   Cons {hd = f x; tl = Freeze (function () -> mapl f l)}
| Cons ({hd = x; tl = Freeze th} as cell) ->
   let thunk () =  
     let tail = th() in cell.tl <- Val tail; mapl f tail in
   Cons {hd = f x; tl = Freeze thunk};;

let rec do_llist f n = function
  Nil -> ()
| Cons {hd = x; tl = Val l} ->
   if n > 0 then begin
    f x;
    do_llist f (n - 1) l end
| Cons ({hd = x; tl = Freeze th} as cell) ->
   if n > 0 then begin
    f x;
    let tail = th () in
    cell.tl <- Val tail;
    do_llist f (n - 1) tail end;;

Potentially infinite data are now available:

let rec nat = Cons {hd = 0; tl = Freeze (fun () -> mapl succ nat)};;
nat : int llist = Cons {hd=0; tl=Freeze <fun>}
#do_llist print_int 5 nat;;
01234- : unit = ()

And call by need is properly implemented:

#nat;;
- : int llist =
 Cons
  {hd=0;
   tl=
    Val
     (Cons
       {hd=1;
        tl=
         Val
          (Cons
            {hd=2;
             tl=Val (Cons {hd=3; tl=Val (Cons {hd=4; tl=Freeze <fun>})})})})}

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
----------------------------------------------------------------------------