[LONG] Re: types recursifs ...

[Christian Boos <boos@arthur.u-strasbg.fr>]

[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