[LONG] Re: types recursifs ...

From: Christian Boos (boos@arthur.u-strasbg.fr)
Date: Wed May 14 1997 - 17:00:13 MET DST


Date: Wed, 14 May 1997 17:00:13 +0200
Message-Id: <199705141500.RAA02346@arthur.u-strasbg.fr>
From: Christian Boos <boos@arthur.u-strasbg.fr>
To: Sven LUTHER <luther@phivolcs.dost.gov.ph>
Subject: [LONG] Re: types recursifs ...
In-Reply-To: <33795E2D.7993B0CA@phivolcs.dost.gov.ph>
        <33795E2D.7993B0CA@phivolcs.dost.gov.ph>

[long french version below, with code examples]

Hello,

  I would first reply to Sven that recursive types are allowed in the O'Caml
langage, under some conditions. Let's quote the manual :

| Recursive types
|
| The type expression typexpr as ' ident denotes the same type as typexpr,
| and also binds the type variable ident to type typexpr both in typexpr and
| in the remaining part of the type. If the type variable ident actually
| occurs in typexpr, a recursive type is created. Recursive types are allowed
| as long as any recursion crosses a type constructor or an object type.
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

In the french version below, I also give 2 small & useless examples...

  Next, Sven asked about module and type extension possibilities.
There is a little support for that: the 'include' keyword which can be
used to include a signature inside another.
Then, why is there no 'include' for structure definitions ?

This topic suggested me to bring back the hotly debatted concept of
dynamic structure creation... see the forthcoming mail!

==================================================================

Sven LUTHER writes:
> Didier Rousseau wrote:
> > ...
> > Sven LUTHER wrote:
> > > ...
> > > si ('a t as 'a) designe un type recursif alors 'a et 'a t devrait etre
> > > les memes types
>
> En fait ce que je voulais c'est bel et bien definir un type recursif,
> c'est a dire du type :
>
> 'a t as 'a, ou peut etre 'a list as 'a.
>
> cela est-il possible en Caml ?
>
> d'apres la discution sur ce sujet, je ne pense pas que ce soit possible.
>

Si, c'est possible, mais il faut passer par l'utilisation d'un constructeur,
ou bien utiliser une classe, comme indique dans la doc (htmlman/node5.5.html),
que je me permets de citer :

| Recursive types
|
| The type expression typexpr as ' ident denotes the same type as typexpr,
| and also binds the type variable ident to type typexpr both in typexpr and
| in the remaining part of the type. If the type variable ident actually
| occurs in typexpr, a recursive type is created. Recursive types are allowed
| as long as any recursion crosses a type constructor or an object type.
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Les types recursifs sont interessants pour construire des fonctions
"autoregeneratrices" (si je ne m'abuse cela correspond a du "continuation-
passing style").

Exemple :

| type 'a generator = G of 'a * (unit -> 'a generator)
|
| # let gen t =
| let last = pred (Array.length t) in
| let rec forward i () =
| let i', dir =
| if i < last then (succ i, forward) else (pred i, backward)
| in
| G (t.(i'), dir i')
| and backward i () =
| let i', dir =
| if i > 0 then (pred i, backward) else (succ i, forward)
| in
| G (t.(i'), backward i')
| in
| (G (t.(0), forward 0))
|
|
| let next (G (v, g)) = (v, g ())
| ;;
| val gen : 'a array -> 'a generator = <fun>
| val next : 'a generator -> 'a * 'a generator = <fun>
| # let g = gen [| 0; 1; 2 |];;
| val g : int generator = G (0, <fun>)
| # let (v, g) = next g;;
| val v : int = 0
| val g : int generator = G (1, <fun>)
| # let (v, g) = next g;;
| val v : int = 1
| val g : int generator = G (2, <fun>)
| # let (v, g) = next g;;
| val v : int = 2
| val g : int generator = G (1, <fun>)
| # let (v, g) = next g;;
| val v : int = 1
| val g : int generator = G (0, <fun>)
| # let (v, g) = next g;;
| val v : int = 0
| val g : int generator = G (1, <fun>)
| # let (v, g) = next g;;
| val v : int = 1
| val g : int generator = G (0, <fun>)
| #

On peut bien sur trouver des exemples plus utiles (mais certainement
plus longs !).

Encore un autre, le combinateur Y :

en SML: (issu de la comp.lang.ml FAQ)

| datatype 'a t = T of 'a t -> 'a
|
| val y = fn f => (fn (T x) => (f (fn a => x (T x) a)))
| (T (fn (T x) => (f (fn a => x (T x) a))))

en O'Caml (ou en Caml-Light):

| # type 'a t = T of ('a t -> 'a);;
| type 'a t = | T of ('a t -> 'a)
|
| # let y f = let g (T x) = f (fun a -> x (T x) a) in g (T g);;
| val y : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>
|
| # y (fun f a -> if a = 0 then 1 else f (pred a) * a) 5;;
| - : int = 120
|
| # let map g = y (fun f a -> match a with [] -> [] | h::t -> g h :: f t);;
| val map : ('a -> 'b) -> 'a list -> 'b list = <fun>

------------------------------------------------------------------

> y a-t-il un autre mecanisme pour etendre un type, voir un module, un peu
> a la facon
> de l'heritage pour les objets, quelque choses qui permettrait d'etendre
> un type ou un
> module, eventuellement dynamiquement ?

Pour etendre un module, ou au moins son type, il y a le fameux
"include MODULE_TYPE", non documente. Il en a ete fait mention lors de
discussions precedentes sur cette liste
(cf. http://pauillac.inria.fr/caml/caml-list/0602.html )
Il permet de definir un nouveau type de module en realisant simplement
l'inclusion textuelle de la specification d'un autre type de module.

Par contre, pour definir l'implementation, il n'y a rien de tel : on est
oblige de redefinir toutes les valeurs :

On a par exemple :

| # module type A_t = sig val a : int end;;
| module type A_t = sig val a : int end
| # module type Aext_t = sig include A_t val b : int end;;
| module type Aext_t = sig val a : int val b : int end

Mais :

| module A = struct let a = 1 end;;
| module A : sig val a : int end
| # module Aext = include A let b = 1 end;;
| Characters 14-21:
| Syntax error

obligeant a ecrire :

| # module Aext = struct let a = A.a let b = 2 end;;
| module Aext : sig val a : int val b : int end

Pourquoi pas un 'include' pour l'implementation ?
Il serait toujours possible de redefinir certaines valeurs apres
l'inclusion.

Pour etendre un module dynamiquement ... c'est une autre histoire.
A l'heure actuelle, il n'y a meme aucune possibilite d'instancier
dynamiquement des modules, ce qui est bien dommage.

A ce sujet, voir mon prochain mail ...

-- Christian



This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:10 MET