Type récursif

En programmation informatique et théorie des types, un type récursif est un type de données dont la définition fait appel au type lui‐même, de façon récursive. Cela permet entre autres des structures de données qui contiennent des sous‐structures du même type. Cette notion s'applique naturellement dans l'étude des listes et des arbres.

Exemples

Types algébriques

Les types algébriques sont de loin la forme la plus courante de types récursifs. Un exemple classique est le type liste. En syntaxe Haskell (avec une variable de type a qui rend cette définition polymorphe) :

data List a = Nil | Cons a (List a)

Autrement dit, une liste d’éléments de type a est soit une liste vide, soit une cellule contenant une donnée de type a (la « tête » de liste) et une autre liste (la « queue » de liste).

Autre exemple, le type des entiers naturels (voir l’arithmétique de Péano) peut être défini par :

  data Nat = Zero | Succ Nat

c’est‐à‐dire qu’un entier naturel est soit zéro, soit le successeur d’un entier naturel.

Types récursifs de fonctions

On peut avoir besoin d’une fonction qui se prend elle‐même en argument. Par exemple, si l’on souhaite écrire le combinateur de point fixe Y, qui permet de définir des fonctions récursives :

-- ne compile pas !
fix :: ((a -> b) -> a -> b) -> a -> b
fix f = let g x a = f (x x) a in g g

alors, bien que fix n’ait pas lui‐même un type récursif, sa définition en fait intervenir un. En effet, la variable x est appliquée à elle‐même donc, si l’on note $U$ son type, alors x est aussi une fonction prenant un argument de type $U$. On obtient alors un type récursif défini par l’équation $U=U\to B$ pour un certain type $B$.

De façon symétrique, il est parfois utile d’écrire une fonction qui se renvoie elle‐même, ou une autre fonction du même type (par exemple pour coder un automate ou un gestionnaire d’événements). Un exemple simplifié en langage C :

/* syntaxe C pour l’équation de types « function_t = (int → function_t) » ;
 * ne compile pas ! */
typedef function_t (*function_t) (int) ;

function_t f (int n)
{
	printf("%i", n) ;
	return f ;
}

int main (void)
{
	f(1)(2)(3) ; /* devrait écrire « 123 » */
	return 0 ;
}

Si l’on note $U$ le type de la fonction f, alors f est une fonction qui prend un entier (type $\mathrm {Int}$) et se renvoie elle‐même (type $U$) ; son type est donc aussi $\mathrm {Int} \to U$, d’où l’équation $U=\mathrm {Int} \to U$.

En fait, comme expliqué plus loin, de tels types récursifs ne sont pas permis tels quels par les langages C ni Haskell. Ces exemples fonctionnent en langage OCaml avec l’option de compilation -rectypes :

(* fix : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b ;
 * requiert l’option de compilation « -rectypes » *)
let fix f = let g x a = f (x x) a in g g

(* f : (int -> 'a) as 'a ;
 * requiert l’option de compilation « -rectypes » *)
let rec f n =
  Format.printf "%i" n ;
  f

let _ =
  f 1 2 3 (* écrit « 123 » *)

Théorie

En théorie des types, un type récursif a la forme $\mu \alpha .T$. Intuitivement, cette notation désigne le type $U$ représenté par l’expression $T$, dans lequel la variable de type $\alpha$ peut apparaître et désigne le type $U$ lui‐même.

Par exemple, si $T=\mathrm {Int} \to \alpha$, alors $U=\mu \alpha .\mathrm {Int} \to \alpha$ est le type d’une fonction qui prend un entier et renvoie une fonction de même type qu’elle‐même. On peut dérouler cette expression de type, en remplaçant dans $T$ la variable $\alpha$ par le type $U$ (ce qu’on note $T[U/\alpha ]$), ce qui donne $\mathrm {Int} \to U$. On peut itérer cette opération autant de fois que souhaité :

$U$

$\mathrm {Int} \to U$

$\mathrm {Int} \to (\mathrm {Int} \to U)$

$\mathrm {Int} \to (\mathrm {Int} \to (\mathrm {Int} \to U))$

$\vdots$

L’exemple ci‐dessus des entiers naturels s’écrit $\mathrm {Nat} =\mu \alpha .\mathbf {1} +\alpha$, où les deux bras du type somme représentent les constructeurs Zero et Succ, avec Zero ne prenant pas d'argument (représenté par le type unité) et Succ prenant un élément du type Nat lui‐même (représenté par la variable de type $\alpha$).

L’exemple des listes d’éléments de type $A$, quant à lui, s’écrit $\mathrm {List} A=\mu \alpha .\mathbf {1} +A\times \alpha$. Le type unité représente le constructeur Nil sans argument, le type produit $A\times \alpha$ représente le constructeur Cons ayant pour arguments une valeur de type $A$ et une autre valeur de type $\mathrm {List} A$. En déroulant :

$\mathrm {List} A$

$\mathbf {1} +A\times \mathrm {List} A$

$\mathbf {1} +A\times (\mathbf {1} +A\times \mathrm {List} A)$, soit $\mathbf {1} +A+A^{2}\times \mathrm {List} A$

$\mathbf {1} +A\times (\mathbf {1} +A+A^{2}\times \mathrm {List} A)$, soit $\mathbf {1} +A+A^{2}+A^{3}\times \mathrm {List} A$

$\mathbf {1} +A\times (\mathbf {1} +A+A^{2}+A^{3}\times \mathrm {List} A)$, soit $\mathbf {1} +A+A^{2}+A^{3}+A^{4}\times \mathrm {List} A$

$\vdots$

On obtient successivement le type des listes de longueur zéro ($1$), un ($A$), deux ($A^{2}$), trois ($A^{3}$), et ainsi de suite.

L’idée est que le type récursif $U$ vérifie l’équation informelle suivante :

$U=T[U/\alpha ]$

Dans les exemples précédents, elle s’écrit respectivement :

• $U=\mathrm {Int} \to U$
• $\mathrm {Nat} =\mathbf {1} +\mathrm {Nat}$
• $\mathrm {List} A=\mathbf {1} +A\times \mathrm {List} A$

Si l’on s’autorisait les expressions de type infinies, on pourrait dérouler à l’infini et écrire, respectivement :

• $U=\mathrm {Int} \to \mathrm {Int} \to \mathrm {Int} \to \ldots$ (une fonction curryfiée acceptant autant d’arguments de type $\mathrm {Int}$ que souhaité)
• $\mathrm {Nat} =\mathbf {1} +\mathbf {1} +\mathbf {1} +\ldots =\{0\,;1\,;2\,;\ldots \}$ (c’est en effet une union disjointe de singletons que l’on peut nommer $\{0\}$, $\{1\}$, $\{2\}$, etc.)
• $\mathrm {List} A=\mathbf {1} +A+A^{2}+A^{3}+\ldots =A^{*}$ (l’étoile de Kleene)

Ces expressions infinies sont cependant mal définies, car elles ne reflètent qu’un seul type solution alors que l’équation de types peut en admettre plusieurs. On résout l’ambigüité en choisissant le plus petit ou le plus grand point fixe du déroulement, comme expliqué dans la section « Données & co‐données ».

Pour donner un sens à cette égalité de types, on distingue deux formes de récursivité qui diffèrent dans la manière d’introduire et d’éliminer les types récursifs : l’équirécursivité et l’isorécursivité.

Types équirécursifs

Avec des types équirécursifs, un type $\mu \alpha .T$ et son déroulement $T[\mu \alpha .T/\alpha ]$ sont égaux — c'est-à-dire que ces deux expressions de type dénotent le même type. En fait, la plupart des théories de types équirécursifs vont plus loin et énoncent que deux expressions avec le même « déroulement infini » sont équivalentes. Cela complique le système de types, bien plus qu’avec des types isorécursifs. Les problèmes algorithmiques tels que la vérification des types ou l'inférence de types sont aussi plus difficiles. Comme la simple comparaison syntaxique n’est pas suffisante pour les types équirécursifs, il faut les convertir en une forme canonique, ce qui peut se faire en ${\mathcal {O}}(n\log n)$.

Les types équirécursifs capturent le caractère auto-référent (ou mutuellement référent) des définitions de types dans les langages procéduraux et orientés objet. Ils surviennent aussi dans la sémantique des objets et classes en théorie des types.

Types isorécursifs

Avec des types isorécursifs, un type $\mu \alpha .T$ et son déroulement $T[\mu \alpha .T/\alpha ]$ sont des types distincts et disjoints, néanmoins reliés par un isomorphisme qui se matérialise par des constructions de termes spécifiques. Plus précisément, on dispose de fonctions inverses $\mathrm {roll} :T[\mu \alpha .T/\alpha ]\to \mu \alpha .T$ et $\mathrm {unroll} :\mu \alpha .T\to T[\mu \alpha .T/\alpha ]$.

Les types isorécursifs sont très présents dans les langages fonctionnels sous la forme de types algébriques. De fait, les langages Haskell et OCaml (sauf avec l’option de compilation -rectypes) interdisent la récursion dans les alias de type — c’est‐à‐dire l’équirécursivité. Ainsi, les définitions suivantes sont illégales en Haskell :

type Bad = (Int, Bad)
type Evil = Bool -> Evil

Cette limitation existe car, à l’instar de typedef en langage C et contrairement aux types algébriques, les alias de types sont simplement remplacés par leur définition lors de la compilation. Les types algébriques permettent de contourner cette limitation en enveloppant l’expression récursive dans un constructeur :

data Good = Pair Int Good
data Fine = Fun (Bool->Fine)

Une façon de le comprendre est de remarquer que ce niveau d’indirection supplémentaire explicite les opérations d’enroulement et de déroulement du type : la construction d’une valeur (l’application d’un constructeur) enroule son type, tandis que sa destruction (par filtrage par motif) le déroule. Dans le dernier exemple :

roll :: (Bool->Fine) -> Fine
roll x = Fun x

unroll :: Fine -> (Bool->Fine)
unroll (Fun x) = x

Ceci permet d’écrire en Haskell le combinateur de point fixe vu plus haut :

data FunctionTakingItself b = R (FunctionTakingItself b -> b)

fix :: ((a -> b) -> a -> b) -> a -> b
fix f = let g y@(R x) a = f (x y) a in g (R g)

De même, on peut écrire en langage C l’exemple de fonction qui se renvoie elle‐même :

/* définition récursive du type encapsulée dans une structure */
struct function_t {
	struct function_t (*fun) (int) ;
};
typedef struct function_t function_t ;

/* définition mutuellement récursive de la fonction f et de son encapsulation g */
static function_t g ;
function_t f (int n)
{
	printf("%i", n) ;
	return g ;
}
static function_t g = { .fun = f } ;

int main (void)
{
	g.fun(1).fun(2).fun(3) ; /* écrit « 123 » */
	return 0 ;
}

Données & co‐données

Algébriquement, on peut définir le type $\mu \alpha .T$ comme un point fixe de la fonction $\alpha \mapsto T$ (qui à un type associe un type). La question est de choisir ce point fixe. On peut prendre soit le plus petit point fixe, soit le plus grand. On parle parfois de données dans le premier cas et de co‐données dans le second cas. Cette distinction est particulièrement importante en programmation totale (en), où l’on veut garantir la terminaison de tous les calculs. En effet, dans le cas des types algébriques :

• les données sont bien fondées et présentent donc un principe de récurrence, qui permet de les détruire (définir des fonctions sur ces données) récursivement de façon terminante ;
• les co‐données présentent un principe de co-récurrence, qui permet de les construire (définir de telles valeurs) récursivement de façon productive.

Ces deux notions sont duales.

Dans un langage total, ce sont les deux seules formes autorisées de récursivité. Ces deux restrictions visent à garantir un bon comportement des programmes.

• Que les données soient nécessairement finies assure la terminaison des fonctions qui les traitent, grâce au principe de récurrence.
• L’introduction des co‐données potentiellement infinies permet de retrouver une forme de non‐terminaison nécessaire pour réaliser des programmes à boucle d’ïnteraction, tels qu’un système d’exploitation, qui réagissent à un flux d’événements extérieurs. Ici, le bon comportement est garanti par la productivité des définitions co‐récursives : chaque étape de calcul produit une portion (un co‐constructeur) de co‐donnée, qui est donc exploitable par la suite.

Afin de ne pas risquer qu’une fonction définie par récurrence sur une donnée soit appelée sur une co‐donnée infinie, on considérera distincts les types de données et les types de co‐données, avec deux mots‐clés différents pour les définir.

Dans l’exemple précédent des listes, la fonction de types était $\alpha \mapsto \mathbf {1} +A\times \alpha$.

• Son plus petit point fixe est $A^{*}=\mathbf {1} +A+A^{2}+A^{3}+\ldots$, c’est‐à‐dire le type des listes finies.
• Son plus grand point fixe est $A^{*}+A^{\infty }$, c’est‐à‐dire l’ensemble des listes potentiellement infinies.

Si l’on n’avait pas le constructeur Nil (permettant de fonder une liste), alors la fonction serait $\alpha \mapsto A\times \alpha$ et alors :

• le plus petit point fixe est le type vide $\emptyset$, ne contenant aucune valeur (sans Nil, il est impossible de construire une liste finie) ;
• le plus grand point fixe est $A^{\infty }$, le type des listes infinies.

De même, dans l’exemple des entiers naturels, on considère $\alpha \mapsto \mathbf {1} +\alpha$ :

• le plus petit point fixe est $\mathbf {N} =\{0\}\cup \{1\}\cup \{2\}\cup \ldots =\mathbf {1} +\mathbf {1} +\mathbf {1} +\ldots$, le type des entiers naturels ;
• le plus grand point fixe est $\mathbf {N} \cup \{\infty \}$.

Et une remarque analogue s’applique pour le constructeur Zero.

Les langages Turing‐complets usuels ignorent cette nuance et permettent une récursivité non contrôlée. Il n’y a donc qu’un seul mot‐clé pour définir un type récursif, qui est implicitement le plus grand point fixe. Ainsi en Haskell :

data List a = Nil | Cons a (List a)

on peut utiliser ces listes comme des données, avec une fonction définie par récurrence (cette définition est bien fondée : chaque appel récursif se fait sur des données structurellement plus petites) :

length :: List a -> Int
length Nil           = 0
length (Cons _ tail) = 1 + length tail

ou comme des co‐données, avec une définition par co‐récurrence (cette définition est productive : chaque itération produit un constructeur) :

infinite_list :: List Int
infinite_list = Cons 1 infinite_list -- la liste [ 1, 1, 1, … ]

naturals :: List Int
naturals = naturals_from 0 where -- la liste [ 0, 1, 2, … ]
  naturals_from n = Cons n (naturals_from (n+1))

L’évaluation paresseuse permet d’écrire cette définition sans entrer dans une boucle infinie d’évaluation. On voit ainsi que la paresse est essentielle pour construire des co‐données dans un langage total.

Mais on peut également écrire des définitions récursives qui ne sont ni récurrentes ni co‐récurrentes, qu’elles soient pertinentes ou pas. Ainsi l’exemple précédent peut se réécrire de façon parfaitement valide suivant un idiome courant en Haskell (cette définition n’est pas co‐récurrente au sens le plus courant, à cause de l’appel à map) :

naturals :: List Int
naturals = Cons 0 (map succ naturals) -- la liste [ 0, 1, 2, … ]

Mais rien ne nous empêche d’écrire des programmes bogués :

stupid list = stupid (Cons 1 list)

idiot = length naturals

Voir aussi

• Induction structurelle
• Récursivité
• type algébrique de données

Références

(en) Cet article contient des extraits de la Free On-line Dictionary of Computing qui autorise l'utilisation de son contenu sous licence GFDL.