Considérerons un langage d'opérateurs d'arité fixe tel que par exemple `L = {a,f"(.)",r"(.,.)"}`. A ce stade, la seule fonctionnalité de l'opérateur est de se composer avec d'autres opérateurs pour former des termes clos tel que par exemple `r(r(a,f(a)),f(r(a,a)))`.
Certains mécanismes de composition d'opérateurs peuvent se factoriser. Par exemple, l'application d'un même argument, répété `n` fois, sur les `n` entrées d'un opérateur `n`-aire, pourrait s'écrire sans répeter `n` fois l'argument en adoptant une convention d'écriture particulière, ou ce qui revient au même, en introduisant d'autres opérateurs jouant ce rôle de mise en facteur. On verra alors apparaître un langage plus puissant, capable d'exprimer des compositions avec un nombre de symboles beaucoup moindre.
Les fonctions s'expriment de deux façons, soit à l'aide de l'opérateur de définition de fonction `"↦"`, soit en définissant à quoi est égal l'appel de la fonction `n`-aire sur une liste de `n` variables libres. Par exemple :
`f = (x_1,x_2,x_3) "↦" x_1"+"x_2"+"x_3`
`f(x_1,x_2,x_3) = x_1"+"x_2"+"x_3`
La tête de la fonction est constituée de la liste des `n` variables libres servant d'arguments d'entrée de la fonction. Dans l'exemple, il s'agit de `(x_1,x_2,x_3)`. Le corps de la fonction est un programme calculant la sortie. Dans l'exemple, il s'agit de `x_1"+"x_2"+"x_3`.
L'opérateur `"↦"` définit un programme, ou autrement dit, définit programmativement une fonction. Le symbole `f` est une variable libre que l'on affecte à un programme.
L'opérateur de définition de programme `"↦"` a une priorité syntaxique supérieure à celles des autres opérateurs pour sa gauche et une priorité inférieure à celle des autres opérateurs pour sa droite, faisant ainsi qu'il n'est pas nécessaire d'entourer de parenthèses la définition du programme.
Dernière remarque, il faut entendre ici par fonction, un programme, et non une fonction mathématique qui ne définit que le résultat de la fonction et pas le moyen d'y accéder. La terminologie de "fonction" désigne ici un programme c'est à dire un moyen effectif de calculer le résultat en sortie de la fonction pour une entrée quelconque. On adjoint alors deux autres résultats possibles, le `"FAIL"` lorsque le programme échoue dans son exécution, et l'infini de Turing, `oo`, lorsque le programme ne s'arrête jamais.
Nous allons d'abord décrire la notation polonaise, un moyen de composer les opérateurs connaissant leur arité, sans utiliser de parenthèse, en les mettant simplement en file indienne. Et nous reprendrons la définition des opérateurs de Kleen ; la projection, la composition série et la composition parallèle, qui permettent de construire toutes les formes de compositions d'opérateurs.
Les arités des opérateurs doivent être préalablement connues ce qui se fait en déclarant un langage. Par exemple :
`L = {a,b,c,f"(.)",g"(.)",h"(.)",r"(.,.)",s"(.,.)",t"(.,.)"}`
Une expression en notation polonaise est une suite d'opérateurs. Et on généralise d'emblée la définition pour intégrer toutes les suites d'opérateurs finies possibles `L"*"`. Chaque suite représente une liste de termes dite "terminale-close", c'est à dire où toutes les éventuelles opérandes manquantes se trouvent groupées à la fin du dernier terme de la liste de termes. Voici un exemple de liste de termes terminale-close :
`a,f(b),c,r(s(a,b),t(r(.,.),.))`
Et son expression en notation polonaise s'obtient en enlevant les parenthèses ainsi que les points représentant les arguments manquants :
`afbcrsabtr`
A chaque fois que l'on ajoute un opérateur à une telle suite d'opérateurs, celui-ci prend la place de la premère opérande non pourvue (représenté par un point), et s'il n'y a en pas, il constitue le terme suivant de la liste. Ces listes de termes terminales-closes sont un peu plus générales que les opérateurs générateurs. Elles possèdent une arité d'entrée `e` qui est le nombre d'opérandes non pourvues, et une arité de sortie `s` qui est le nombre de termes de la liste. Et on dit qu'elles ont une arité `(e,s)`. Par exemple l'arité de `f"(.)"` est `(1,1)`, et l'arité de `a,b,c` est `(0,3)`. Voici quelques exemples :
polonaise
terminale-close
La notation polonaise inverse s'obtient de la même façon mais en inversant la suite des opérateurs. Citons l'exemple remarquable de l'identité d'Euler qui fait intervenir chaque opérateur juste une seul fois ; l'addition `+`, la multiplication `**`, l'exponentiation `"↑"`, l'égalité `=`, et les cinq constantes mathématiques fondamentales `0,1,pi,e,i` :
`e^ipi + 1 = 0`
Cette identité d'Euler s'exprime en notation polonaise inverse comme suit :
`0 1 pi i**e "↑" "+" "="`
On note `pi_i` la projection de la composante numéro `i` d'un `n`-uplet.
`pi_i(x_1,x_2,x_3...,x_n) = x_i` `pi_i = (x_1,x_2,x_3,...,x_n)"↦"x_i`
`pi_i(x_1,x_2,x_3) = x_i` `pi_i = (x_1,x_2,x_3)"↦"x_i`
Le symbole `"."` est utilisé pour désigner les d'entrées dans l'ordre de leur apparition de gauche à droite, et on utilise les parenthèses spéciales `⟮⟯` pour construire des opérateurs. Par exemples l'opérateur `g⟮".,"a⟯` correspond à l'opérateur `x |-> g(x,a)`, et l'opérateur `g⟮g"⟮.,"a⟯,g⟮b",.⟯"⟯` correspond à l'opérateur `(x,y) |-> g(g(x,a),g(a,y))`.
Les parenthèses normales `()` sont utilisées pour construire les termes clos tel que `r(a,f(a))`. Puis on identifie tout terme avec la fonction zéro-aire produisant le terme, de tel sorte que nous pouvons écrire par exemple `r⟮a,f⟮a⟯⟯ = r⟮a,f(a)⟯ = r(a,f⟮a⟯) = r(a,f(a))`. Et nous pouvons dire que le compositeur `⟮⟯` et l'opérateur zéro-aire "`.`" complète le compositeur `()`, dans un langage d'opérateurs où chaque opérateurs peut être utilisé de plus comme opérateur zéro-aire, voir le langage d'opérateurs.
On note la composition série en utilisant les parenthèses `⟨ ⟩`. Ainsi l'expression `r⟨f,g,...⟩` désigne la composition série d'un opérateur `r` par les opérateurs `f,g,...`, produisant un opérateur d'arité égale à celle cummulée des opérateurs `f,g,...`. Cela produit un opérateur qui s'applique aux opérandes de `f` concaténées aux opérandes de `g` concaténées aux opérandes des suivants. La composition série va ainsi placer les opérandes sur les entrées non saturées dans l'ordre de leur apparition. Par exemples :
`r⟨f,a⟩` `x|->r(f(x), a)` `r⟨f,g⟩` `(x,y)|->r(f(x), g(y))` `r⟨f,s⟩` `(x,y,z)|->r(f(x), s(y,z))` `r⟨s,t⟩` `(x,y,z,u)|->r(s(x,y), t(z,u))`
On note la concaténations série d'opérateurs en l'entourant de parenthèses `⟨ ⟩`. Par exemple :
`⟨f,r,h,s⟩` `(x_1,x_2,x_3,x_4,x_5,x_6)|->f(x_1),r(x_2,x_3),h(x_4),s(x_5,x_6)`
On note la composition parallèle en utilisant les parenthèses `( )` normale lorsqu'il n'y a pas d'ambiguité, sinon on utilise les parenthèses colorées `color(red)"()"`. Ainsi l'expression `r(f,g,...)` désigne la composition parallèle d'un opérateur `r` par les opérateurs `f,g,...`, produisant un opérateur d'arité égale à l'arité la plus grande parmi l'arité des opérandes `f,g,...`. Cela produit un opérateur qui s'applique à une liste d'opérandes comme suit : la première opérande va s'appliquer à chaque opérateur s'il y a des entrées non pourvues, et ainsi de suite pour chaque opérande. La composition parallèle va ainsi démultiplier et distribuer chaque opérande sur toutes les entrées non saturées. Par exemples :
`r(f,a)` `x|->r(f(x), a)` ` r(f,g)` `x|->r(f(x), g(x))` `r(f,s)` `(x,y)|->r(f(x), s(x,y))` `r(s,t)` `(x,y)|->r(s(x,y), t(x,y))`
On note la concaténations parallèle d'opérateurs en l'entourant de ces mêmes parenthèses `( )`.
`(f,r,h,s)` `(x,y)|->f(x),r(x,y),h(x),s(x,y)`
Les compositions parallèles et séries peuvent se succéder. La composition étant associative, elles peuvent être évaluée dans n'importe quelle ordre. Par exemple soit l'opérateur `K = f(g_1,g_2)(h_1,h_2)`, et l'opérateur `g_2 = p(q_1,q_2)(r)`, alors l'opérateur `K` peut s'écrire `K = f(g_1, p(q_1, q_2)(r))(h_1, h_2)`. La composition est associative, c'est pourquoi il n'est pas nécessaire de présiser dans quel ordre se fait la composition parallèle. On précise l'arité des opérateurs disponibles en présentant un langage `L` explicitant les arités :
`L = {x, y, q_1"(.)", q_2"(.)", f"(.,.)", g_1"(.,.)", h_1"(.,.)", h_2"(.,.)", p"(.,.)", r"(.,.)"}`
Par exemple : `g_2 = p(q1,q2)(r)`. Nous avons donc `K = f(g1,g2)(h1,h2) = f(g1, p(q1, q2)(r))(h1, h2)` :
---- 9 novembre 2018 ----
Ce qui s'écrie plus simplement par :
f(p3, g(p1))(x,y,z) = f(z,g(x)) f(p3,3, g(p1,3)) = (x,y,z) --> f(z,g(x))
La logique polonaise empile une suite d'opérateurs en occupant les places libres "les plus récentes". L'ajout d'un opérateur n-aire insère n nouvelles places libres. Les n places libres sont créées dans l'ordre de droite à gauche de tel sorte que la plus récente est toujours celle la plus à gauche. La logique polonaise empile ainsi des opérateurs d'arités diverses tant qu'il y a des places libres et se termine lorsqu'il n'y a plus de place libre. On dit alors que le message est clos, ou que la composition est close.
L = {a, s(.),f(.,.)}
Pour intégrer dans cette logique polonaise la possibilité de calculer non pas de simples éléments mais d'autres opérateurs il faut pouvoir spécifier les variables d'un nouvel opérateur en construction, ou bien pouvoir permuter et projeter les variables d'un opérateur n-aire.
3) La logique polonaise avec numérotation des variables
On introduit n meta-opérateurs zéro-aire que sont les numéros des variables 1,2,3..n, et qui permettent de désigner les places libres bloquées d'un opérateur n-aire en construction, simplement en les numérotant.
La logique polonaise avec numérotation des variables, empile ainsi des opérateurs d'arités diverses tant qu'il y a des places libres et se termine lorsqu'il n'y a plus de place libre. On dit alors que le message est meta-clos, ou que la composition est meta-close. Le résultat définie un nouvelle opérateur qui possède une arité égale au plus grand numéro utilisé.
Un opérateur tel que par exemple (x,y,z)-->f(x,y,z) sera noté par la formule f(1,2,3).
Voici quelques exemples à partir d'un langage L :
L = {a, s(.),f(.,.)}
Le message meta-clos peut être perçu comme un programme. Il constitue un nouvel opérateur qui peut alors être composé comme les autres opérateurs. Lorsque l'on compose de tels programmes les un à la suite des autres de la même façon que l'on empile des opérateurs, on peut les fusionner en un seul programme en effectuant le liens des variables spécifiées dans chacun des programmes. La fusion se ramène aux règles suivantes de simplification du message :
Tout d'abord on insère les symbôles | de fin de programme entre chaque message meta-clos.
Voici quelques exemples de fusion :
L = {a, b, c, s(.),f(.,.)}
Pour des raisons de lisibilité on notera le programme par sa formule, c'est à dire en ajoutant les parenthèses selon l'arité des opérateurs. Nous avons s(1) = s. Mais s ne constitue pas un programme car il n'est pas meta-clos. Si on remplaçe s(1) par s dans les successions close de programmes, on obtient une succession close de programmes plus simples et de même résultat. De même f(1,2) = f, et nous pouvons le remplacer dans les successions close de programmes.
3.1) Généralisation, l'opérateur de composition série
On peut généraliser et considérer les programmes non meta-clos en les cloturants par défaut. Les formules non-meta close sont représentés avec des points pour désigner les place libres qui n'ont pas été affectées et qui sont toujours regroupé à la fin de la formule. Par exemple la formule f(f(a,.),.) contient deux places libres.
Il y a qu'une seule possibilités de cloture par défaut, qui respecte la logique polonaise. On cloture par des variables libres supplémentaires ayant des numéros succédant le plus grand numéro déja utilisé. Ainsi f=f(1,2), s=s(1), f(a,.)=f(a,1), f(3,.)=f(3,4) etc...Ainsi en remplaçant le message non meta-clos f1f par f1f23, le message f1faaa est bien égale au message f1f23aaa. Se pose alors la question de la fin de programme. Un programme f1f23 peut être considéré comme f1|f2|3 et le résultat en est complètement changé :
f1f23 = (x,y,z)-->f(x,f(y,z))
f1|f2|3 = f12|f23|3 = (x,y,z,t,u,v)-->f(f(t,u),v)
Pour lever cette ambiguité, on est donc obligé de formaliser la fin de programme par le meta opérateur |.
On remarque alors que l'opérateur |, noté également ° dans l'espace des formules, est un opérateur associatif qui définie d'une manière trés générale l'opération de composition série de deux opérateurs. On peut ainsi composer les opérateurs en une liste. Par exemple
f ° s ° f = f|s|f = f12|s1|f12 = f(s(f(1,2)),3).
Sémentiquement, ° désigne la composition série de deux opérateurs, et | désigne la succession série de deux programmes.
3.2) Généralisation aux listes
On peut vouloir s'intéresser aux listes. En enlevant la règle d'arret des messages lorsque il n'y a plus de place libre, on crée des messages qui désignent des listes. Ainsi le programme aaaa désigne la liste (a,a,a,a) qui constitue un opétateur d'arité d'entré égale à zéro (c'est une constante) et d'arité de sortie égale à 4 (c'est un quadruplet).
Voici quelques exemples de programme d'opérateur ayant une arié d'entré et une arité de sortie :
L = {a, s(.),f(.,.)}
d'entré
de sortie
Notez qu'il s'agit d'énumération plus tôt que de liste. En effet on ne peut pas définir avec ce moyen de liste de liste. Les listes sont concaténées en une seul liste, c'est pourquoi on les appellera énumérations séparées par des virgules et ne permettant pas un emboitement de parenthèses.
Jusqu'à présent les opérateurs du langage ont une arité de sortie égale à 1. On pourrait augmenter notre langage en ajoutant des opérateurs ayant une arité de sortie superieur à 1, mais cela n'apporte rien puisque l'on peut toujours remplacer un tel opérateur par ses composantes. C'est pourquoi il ne semble pas utile de considérer dans le langage des opérateurs d'arité de sortie autre que 1.
4) La logique polonaise avec permutations-projections
On introduit le meta-opérateur "." pour désigner les variables devant rester libres. Et on introduit les meta-opérateurs permutations-projections µ. Pour n = 2, il existe 3 permutations-projections. Et pour n = 3, il existe 13 permutations-projections :
Pour n = 4, il y a à peu près une soixantaine de permutations-projections.
La logique polonaise empile les opérateurs d'arités diverses ou l'opérateur "." qui occupe une place libre, tant qu'il y a des places libres et se termine lorsqu'il n'y a plus de place libre. On dit alors que le message est meta-clos, ou que la composition est meta-close. Et on peut ajouter à la fin du programme une permutation-projection qui possède une arité de sortie égale au nombre d'opérateur "." contenue dans le message.
Le programme ainsi terminé définie un nouvelle opérateur qui possède une arité égale à l'arité de l'opérateur permutation-projection si celui-ci est présent sinon possdède une arité égale au nombre d'opérateur "." figurant dans le message meta-clos.
Voici quelques exemples à partir d'un langage L :
L = {a, s(.),f(.,.)}
4.1) Généralisation aux listes
De même, on peut généraliser aux listes. On doit formaliser la composition série de deux programmes par un meta-opérateur. L'opérateur permutation-projection joue ce rôle. Il faut donc systématiquement le mettre pour séparer deux programmes consécutifs. Pour les permutations identités, on utilisera un opérateur | plus générale qui nous évitera à devoir préciser l'arité.
Le programme définie un nouvel opérateur qui possède une arité d'entrée égale à l'arité d'entré de l'opérateur permutation-projection, et possède une arité de sortie égale à la taille de la liste produite par le programme. Voici quelques exemples :
L = {a, s(.),f(.,.)}
de sortie
Nous introduisons de la même façon que précédement les opérateurs possédant une aritée de sortie supérieure à 1.
4.2) Relégation des permutations-projections au rang d'opérateur avec arité d'entré et de sortie.
Les meta-opérateurs permutations-projections peuvent déja être présent dans le langage L. Et plus précisement le langage L peut contenir un petit nombre de permutations-projections générant toutes les autres permutations-projections. Auquel cas, il n'est pas utile d'introduire dans le mécanisme de construction ces permutations-projections. Seul reste la composition série d'opérateur noté ° ou |, et l'évaluation des opérateurs évaluables tel que nos permutations-projections qui sont reléguées au rang de simple opérateur évaluable.
5) La logique polonaise avec la composition parallèle
On reprend l'idée de Kleen de composition parallèle et on applique une logique polonaise par dessus. On recherche un meta-opérateur qui doit nous permettre d'exprimer les arbres de suite de suite de Kleen sous forme d'un empilement. On utilise le symbôle de composition parallèle ° et un niveau de parenthèse pour chaque suite de suite de Kleen.
Les suite d'opérateurs d'arité diverse sont considéré comme des suite d'arité égale à l'arité maximale, et les opérateurs d'arité plus petite sont atteint par projection. La composition d'un opérateur d'arité n par une liste possèdant moins de n éléments et complété, on ajoute à la liste autant de fois que nécessaire le dernier élément de la liste. La composition d'un opérateur d'arité n par une liste possèdant plus de n éléments et scindée, on prend les n premier élément de la liste pour les combiner avec l'opérateur et on ajoute les éléments suivants dans une nouvelle liste avec le résultat de l'opérateur comme premier élément.
Par exemple :
L = {a, u(.), v(.), w(.), s(.), f(.,.), g(.,.), h(.,.)}
composition série
Les projections pin : (x1,x2,x3...,xn)-->xi doivent appartenir aux opérateurs mis à disposition.
Comme il existe encore un jeux de parenthèses, nous n'avons pas encore une logque polonaise. Le jeux de parenthèse ne doit pas mettre en oeuvre un mécanisme de liste de liste mais doit permettre une simple énumération, c'est pourquoi l'ajout d'une liste dans une liste constitue une nouvelle liste concatènant les deux liste et non pas une liste contenant une liste :
uv(wu(vw)) (u,v,w,u,v,w) f(u(vw)) (f(u,v),w)
Dans l'exemple suivant :
g°f(u°vv) g(f,u(v),v) g°fu°vv g(f,u)(v,v)
on remarque que le niveau de parenthèse ne modifie que le sense de l'opérateur ° placé dans ce niveau de parenthèse. On peut généraliser cette propriétés. Chaque niveau de parenthèse ouvre une suite de suite de Kleen et l'opérateur ° se décline dans cette suite de suite de Kleen. On numérote les opérateurs ° selon leur niveau de parenthèse ou il se situent. Dés lors en autorisant seulement l'incrémentation d'un ou une diminution quelconque du numéro de l'opérateur ° suivant dans le message, on peut supprimer les parenthèses qui n'apportent aucune informations supplémentaires. Par convention on commence par le numéro 0. Les numéros doivent être >= 0 et peuvent augmenter d'un ou diminuer de façon quelconque lorsque l'on passe d'un opérateur ° au suivant dans le message. Par exemple :
f0g1uvw0u f(g(u,v),w)(u) u0g1uv1w u(g(u,v)(w)) u0v1w u(v(w)) u0v0w u(v)(w) u0f1vw2u0v u(f(v,w(u)))(v)
Le codage reste complexe et ne permet pas de construire des algorithmes de balayage simple. En conclusion nous choisirons une méthode de construction progressive arité par arité de tous les opérateurs par composition parallèle.
6) Le codage des compositions parallèles
A partir d'un langage tel que L = {a,s(.),f(.,.)}, nous voulons balayer l'ensemble de tous les arbres de suites de suites de Kleen. Et nous allons le faire étape par étape, c'est à dire en partant de l'ensemble A = {a,r,f} des opérateurs élémentaires et en ajoutant toutes les opérateurs constructibles par une composition parrallèle. Dans l'exemple, il y a 6 compositions parallèles possibles :
On donne un nom à ces nouveaux opérateurs : b = s(a), u = s(s), g = s(f), c = f(a,a), v = f(s,s), h = f(f,f). Le langage est alors plus riche :
{a,b,c,s(.),u(.),v(.),f(.,.),g(.,.),h(.,.)}
Et nous recommençons à balayer l'ensemble des compositions parallèles possibles. Mais nous ne souhaitons pas recalculer ce qui à déja été fait. Pour cela il faut considérer n listes d'opérateurs de même arité, avec n pointeurs pour chaque opérateur d'arité supérieur à 0. Dans l'exemple il y a trois listes d'opérateurs :
L0 = [a]
L1 = [s] et p0_s pointe sur a, et p1_s pointe sur s, et p2_s pointe sur f
L2 = [f] et p1_f pointe sur a, et p1_f pointe sur f, et p2_f pointe sur f
Nous prenons l'opérateur s et nous l'appliquons à l'opérateur a, puis à l'opérateur s puis à l'opérateur f :
L0 = [a, s(a)]
L1 = [s, s(s)] et p0_s pointe sur s(a), et p1_s pointe sur s(s), et p2_s pointe sur s(f )
L2 = [f, s(f)] et p0_f pointe sur a, et p1_f pointe sur s, et p2_f pointe sur f
Nous prenons l'opérateur f et nous l'appliquons à l'opérateur a et s(a), puis à l'opérateur s et s(s) puis à l'opérateur f et s(f) :
L0 = [a, s(a), f(a,a), f(a,s(a)), f(s(a),a), f(s(a),s(a))]
L1 = [s, s(s), f(s,s), f(s,s(s)), f(s(s),s), f(s(s),s(s))] et p0_s pointe sur s(s) et p1_s pointe sur s(s), et p2_s pointe sur s(f )
L2 = [f, s(f), f(f,f), f(f,s(f)), f(s(f),f), f(s(f),s(f))] et p0_f pointe sur f(a,a), et p_f pointe sur f(s,s), et p2_f pointe sur f(f,f)
Nous prenons l'opérateur s et nous l'appliquons aux opérateurs s(a),...,f(s(a),s(a)), puis aux opérateurs s(s),...,f(s(s),s(s)), puis aux opérateurs s(f),...,f(s(f),s(f)) :
L0 = [a, s(a), f(a,a), f(a,s(a)), f(s(a),a), f(s(a),s(a)),s]
L1 = [s, s(s), f(s,s), f(s,s(s)), f(s(s),s), f(s(s),s(s))] et p0_s pointe sur s(s) et p1_s pointe sur s(s), et p2_s pointe sur s(f )
L2 = [f, s(f), f(f,f), f(f,s(f)), f(s(f),f), f(s(f),s(f))] et p0_f pointe sur f(a,a), et p_f pointe sur f(s,s), et p2_f pointe sur f(f,f)