Mail/M'écrire


Chapitre 4  ALGORITHME DE RECONNAISSANCE DES COMBINATEURS INVERSIBLES

(André Brouty)
Cet exposé est sous licence libre LLDD.
Cette reconnaissance a lieu ici dans CL0+ext.

4.1  POSITION DU PROBLÈME.

Étant donné un combinateur, par exemple
(B(B(C B C)(B(C(B(B(C(B B C)C))B)C)))C)
ou
(B(B(B(B W)B)C(B W B)(B W B))K)
dire si ce combinateur est inversible dans le monoïde (CL0+ext,B,I); si oui quel est son inverse? Si non pourquoi? Pour répondre à cette question nous utiliserons les résultats théoriques du chapitre 2. Nous connaissons la forme des combinateurs inversibles, il doivent être éléments de P. On rappelle que P est défini récursivement par:
  1. I est dans P.
  2. Si P1,P2,…,Pn sont dans P alors
    λ(x0 x1 x2… xn)(x0 (P1 xf(1))(P2 xf(2))… (Pn xf(n))) est aussi dans P. f désigne toujours une permutation de {1 2 … n}.
Mais du point de vue de l'implémentation il est préférable de remplacer la condition 1 par la condition
1'. P est dans P où P est un permutateur régulier.
La nouvelle définition obtenue est évidemment équivalente à la précédente car I est un permutateur régulier particulier et que dans la condition 2 ci-dessus il suffit de remplacer P1 P2 P3 … Pn par I pour obtenir un permutateur régulier.Ceci va nous permettre d'éliminer I dans les abstractions et de donner les inverses en termes de B et C exclusivement. Si on veut donc s'en tenir aux critères d'inversibilité developpés dans le chapitre 2 il nous faut prendre la λ-expression en forme normale associée au combinateur si elle existe. Étant donné que nous disposons de la règle d'extensionalité nous pouvons toujours associer une λ-expression à un combinateur, mais celle-ci aura une forme normale si et seulement si le combinateur en a une. On va donc travailler sur cette λ-expression associée au combinateur pour laquelle il suffira de vérifier son appartenance à P. On devra donc dans un premier temps transformer le combinateur donné sous forme de λ-expression qui sera mise en forme normale de tête.On devra obtenir une expression du genre
λ(x0 x1… xn)(x0(P1xf(1))(P2 xf(2))… (Pn xf(n)))     (4.1)
où les Pi doivent avoir la même forme pour être assuré de l'inversibilité. D'abord une remarque simple va nous faciliter le travail: la définition des λ-expressions inversibles ne fait intervenir à chaque niveau que des permutations des variables. Aucune de ces variables n'est dupliquée ni supprimée. La liste des variables devient donc inutile. De plus les variables seront représentées par des nombres consécutifs à partir de zéro ce qui nous permettra de faire des tests sur des nombres plutôt que sur des caractères alphabétiques. L'expression (4.1) ci-dessus sera donc codée:
(0 (P1 f(1))(P2 f(2))…(Pn f(n)))     (4.2)
On peut faire de même avec les autres combinateurs:
C = λ(x0 x1 x2)(x0 x2 x1) sera codé (0 2 1)
B = λ(x0 x1 x2)(x0 (x1 x2)) sera codé (0 (1 2))
S = λ(x0 x1 x2)(x0 x2 (x1 x2)) sera codé (0 2 (1 2))
W = λ(x0 x1)(x0 x1 x1) sera codé (0 1 1)
K = λ(x0 x1)(x0) ne peut pas être codé sans ambiguité dans ce système. Cependant nous le coderons (0) mais un compteur de variables associé à chaque codage nous permettra de savoir si le compte de variables y est. Ainsi I et K seront tous deux codés (0) mais le compteur de variables indiquera zéro pour I et un pour K permettant ainsi de savoir qu'il ne sont pas équivalents. Reprenons donc la forme (4.2):
(0 (P1 f(1))(P2 f(2))…(Pn f(n)))
Après avoir bien entendu vérifié que cette liste commence par 0 (régularité du combinateur), il suffit apparemment d'étudier chaque sous liste (Pi f(i)), de récupérer f(i) pour controler la permutation des variables au premier niveau et vérifier de la même manière que Pi veut bien à son tour se mettre sous la forme (4.2). Malheureusement pour nous la situation n'est pas aussi simple car les combinateurs, même inversibles n'auront qu'assez rarement le bon goût de vouloir se mettre sous la forme (4.2). Il faudra donc les y forcer. La raison en est que chaque λ-expression peut être représentée par une infinité de combinateurs équivalents. On peut avoir ainsi des combinateurs qui dupliquent un nombre arbitraire de fois des termes pour les détruire ensuite; c'est le cas du second exemple donné au début de ce chapitre qui n'est rien d'autre que I (on peut même montrer qu'il est équivalent à I sans utiliser l'extensionalité). Quelques exemples illustreront parfaitement les difficultés rencontrées mieux qu'un long discours. Soient donc les cinq combinateurs suivants:
C1=B(C(C(B(B(B(B C)B))C)C)K)B
C2=B(C(B(B(C(B C)C)B))C)B
C3=B(C(B C)(C B I))B
C4=(B(B(B C(C B K))(B W))B
C5=C(C(B(B(B(B(B(B W)B))B)(B C))B)(C B))(K I)
Malgré leur apparence de diversité ces cinq combinateurs sont équivalents et inversibles, et ne représentent rien d'autres qu'une forme compliquée du fameux permutateur C.

Mettons les sous forme de λ-expression en forme normale de tête et comparons les à la forme théorique (4.2) où C est codé (0 2 1)
C1 devient (0 (K 2 C) 1)
C2 devient (0 (C(C 2)) 1)
C3 devient (0 (C B I 2) 1)
C4 devient (0 (K 2 1) 1)
C5 devient (0 (C B(K I 1) 2) 1)
Comme annoncé ces cinq combinateurs sont équivalents à C écrit sous la forme (0 (I 2) 1).

Dans les deux premiers exemples la sous liste n'a pas du tout la forme prévue par la théorie pour être déclarée inversible puisqu'il n'y a pas de variable en fin de liste; il nous faut donc s'y ramener. Pour C1 la sous liste (K 2 C) n'est pas en forme normale. La mise en forme normale donne (4.2) et le codage (0 (2) 1) qui ne sera reconnu par l'algorithme comme étant C que si on déparenthèse le 2. Pour C2 la sous liste (C(C 2)) est en forme normale; il convient alors de faire une abstraction pour mettre la variable en fin de liste, on obtient (B C C 2) qui répond bien à la forme théorique, B C C étant I. On vient donc de mettre en évidence deux stratégies différentes d'une situation analogue.

Examinons C3: la sous liste (C B I 2) répond parfaitement à la forme théorique; on récupère le 2 et on va analyser C B I qui n'est autre que l'identité et c'est gagné. Mais c'est une stratégie dangereuse comme l'illustre l'exemple C4.

Ici la sous liste (K 2 1) a bien une variable en fin de liste comme prévu par la théorie mais ce n'est pas la bonne. Une mise en forme normale résout le problème. Ceci nous ramène à l'exemple C3 où on peut se demander si la variable 2 en fin de liste est bien la bonne d'autant plus que l'expression (C B I 2) n'est pas en forme normale. Appliquons alors la stratégie de C4. Une mise en forme normale nous donne (B 2 I) et nous fait perdre la forme théorique, nous nous retrouvons dans le cas C2 où une abstraction nous ramène au cas C3 d'où risque de bouclage.

Ici aussi nous venons de mettre en évidence deux stratégies différentes d'un cas analogue. Pour l'exemple C5 la sous liste (C B(K I 1) 2) contient bien une variable en fin de liste qui est la bonne mais le reste de l'expression contient une autre variable qui est amenée à disparaitre si on met l'expression en forme normale mais on perd du même coup la forme théorique une abstraction nous y ramène et nous nous retrouvons dans le cas C3. A la lumière de ces quelques exemples une stratégie commence à se dessiner.

4.2  STRATÉGIE DE RECHERCHE.

Il faut avant tout exprimer le combinateur sous forme de λ-expression en forme normale de tête ce qui va nous permettre de vérifier la régularité (présence du zéro en début de liste), puis on passe ensuite à l'étude des sous listes s'il y en a. Dans le cas contraire les éléments de la liste doivent être tous des variables et constituer une permutation; c'est un cas facile à étudier. Plaçons nous donc dans l'hypothèse où il y a des sous listes et passons à leur étude.

Les exemples précédents montrent que même si la sous liste se présente sous la forme théorique il ne faut pas en tenir compte (cas C3, C5). On met donc la sous liste en forme normale et on regarde s'il y a des variables. Trois cas se présentent alors:
  1. il n'y a pas de variable: échec on n'obtiendra jamais la forme théorique
  2. il y a une seule variable: on l'abstrait et on recupère le début de la liste pour recommencer l'analyse.
  3. il y a plus d'une variable: échec trop de variables pour obtenir la forme théorique.
En realité l'algorithme ne suit pas exactement cette stratégie car l'exemple C3 montre qu'une mise en forme normale sytématique peut nous obliger à faire l'opération inverse qu'est l'abstraction pour nous ramener au point de départ, ce qui est très couteux. Nous procédons donc ainsi.   1. SI le combinateur représenté par la sous liste est en forme normale ET
    possède une variable en fin de liste
    ALORS SI on trouve d'autres variables: échec
        SINON on a la forme théorique.
  2. SINON SI ce combinateur ne contient pas de variable: échec
        SINON S'il contient une seule variable
            ALORS SI cette variable est en fin de liste: succès
                SINON on l'abstrait et retour en 2.
  3.         SINON on met l'expression en forme normale puis
            SI le combinateur obtenu contient plusieurs variables
             ou pas du tout échec
            SINON on abstrait cette variable et retour en 1.

Les exemples C1 C2 C3 C4 et C5 seront donc tous reconnus comme étant C et auront pour inverse C.

4.3  RÉCUPÉRATION DE L'INVERSE.

Une fois reconnue à tous les niveaux la forme théorique nous pouvons affirmer l'inversibilité du combinateur. Il reste donc à donner son inverse. Pour cela il faut inverser chaque permutation à chaque niveau et les replacer à l'endroit convenable dans la liste représentant l'inverse du combinateur écrit sous forme de λ-expression. L'étude d'un petit exemple va mettre clairement en évidence la stratégie suivie.

Rappelons d'abord la forme théorique d'une λ-expression en forme normale et de son inverse:
P=(0 (P1 f(1)) (P2 f(2))… (Pn f(n)))
P−1=(0 (Pf−1(1)−1 f−1(1)) (Pf−1(2)−1 f−1(2))… (Pf−1(n)−1 f−1(n)))
où f−1 désigne l'inverse de la permutation f et Pi−1 l'inverse du combinateur Pi. Prenons l'exemple:
B(B(C B(B C(B C)))(B(B C(C B C))))C
qui s'écrit en forme normale de tête:
(0 (C 3) (B C(B C) 1) 2)
La permutation du premier niveau à récupérer et à controler comme étant bien une permutation est (0 3 1 2); puis on met C sous forme normale de tête, on obtient (0 2 1) et de même pour B C(B C) qui donne (0 2 3 1); ce sont des permutateurs réguliers le combinateur ci-dessus est donc décrété inversible. Sa forme normale complète en terme de λ-expression est:
(0 ((0 2 1) 3) ((0 2 3 1) 1) 2)
et c'est elle qu'il nous faut inverser puis abstraire. D'abord on peut remarquer qu'il y a des parenthèses dont on pourrait se passer moyennant une petite convention; on peut en effet écrire:
(0 (0 2 1) 3 (0 2 3 1) 1 2)
à condition de convenir que le nombre qui suit une sous liste est la variable associée au combinateur representé par la sous liste. Ceci à l'avantage de faire apparaitre chaque permutation comme étant la liste des atomes d'une liste et se repère très facilement avec cette convention d'écriture. En réalité pour des raisons de facilité de programmation dues au langage LISP utilisé nous écrivons ce combinateur comme suit:
(0 3 (0 2 1) 1 (0 2 3 1) 2)
On a donc:
(0 f(1) P1 f(2) P2 f(3) P3)
(0 3 (0 2 1) 1 (0 2 3 1) 2)
Ici P3 correspond à I qui est repéré par son absence. Il nous faut donc récupérer la liste suivante:
(0 f−1(1) Pf−1(1)−1 f−1(2) Pf−1(2)−1 f−1(3) Pf−1(3)−1)
Or
(0 f(1) f(2) f(3)) = (0 3 1 2)
donc
(0 f−1(1) f−1(2) f−1(3)) = (0 2 3 1)
On vient donc de récupérer l'inverse de la permutation du premier niveau il nous faut maintenant calculer les Pf−1(i)−1. On a
Pf−1(1)−1=P2−1=(0 3 1 2)
Pf−1(2)−1=P3−1=I
Pf−1(3)−1=P1−1=C
L'inverse correspond donc à la liste:
(0 2 (0 3 1 2) 3 1 (0 2 1))
On met ensuite cette liste sous la forme correspondant à la λ-expression. On obtient:
(0 ((0 3 1 2) 2) 3 ((0 2 1) 1))
et on l'abstrait en commençant par les permutateurs du fond de la liste ce qui donne:
(0 (B(B C)C 2) 3 (C 1))
Puis on abstrait à nouveau le résultat obtenu et ceci jusqu'à ce qu'il n'y ait plus de zéro en début de liste. Résultat final:
C(C(B(B(B(B B C))B)(B C)(B(B C)C))C.
Les pages suivantes présentent le programme correspondant écrit en VLISP sur le système MULTICS de l'Université de Rennes ainsi qu'une petite session montrant ses possibilités. Ce programme dans cette version est volontairement bavard. Il occupe 2348 doublets en mémoire.

Quelques remarques et réflexions en guise de conclusion