On propose de redécouvrir les concepts informatiques contemporains à travers une génèse, une construction d'un langage de programmation, par une succession de choix canoniques propres à la calculabilité issue des mathématiques, qui nous libère des arbitraires et nous révèle de nouveaux concepts.
Nous partons du principe qu'il n'y a pas de différence entre donnée et programme, entre représentation conceptuelle et représentation physique du programme. Une concision est nécessaire autant pour l'un que pour l'autre. Nous nous libérons du hardware pour nous intéresser qu'au langage.
Car, au niveau conceptuel où nous nous plaçons, où la donnée est l'égal du programme, tout est langage.
Au départ se trouve un texte écrit linéairement, une suite de caractères.
La norme utilisée pour désigner les caractères est l'Unicode en UTF-8. C'est un standard quasi-universel qui contient les caractères de la plus part des langues du monde, et qui peut potentiellement s'agrandire.
C'est le premier stade, définissant un socle, notre hardware en quelque sorte. Il met en oeuvre un flux de caractères.
Le langage est défini par une grammaire. L'analyse syntaxique faite par la grammaire va d'abord traduire ce flux de caractères en un flux de mots, une première étape nécessaire, puis va traduire ce flux de mots en un flux de termes dans notre langage. Où l'on entend par terme une composition d'opérateurs d'arité variables produisant un opérateur d'arité variable.
La grammaire est mémorisée dans un contexte. Sans la grammaire, la donnée ne peut pas être interprétée.
On ne peut pas penser la définition d'un langage dans le langage lui-même. C'est pourquoi on utilise un méta-langage permettant de définir le langage. On se dédouble en quelque sorte pour se regarder. Et ce méta-langage qui inclut des formalisations plus savantes se réincorpore dans le langage par la suite.
La grammaire va traduire la suite de caractères en une suite de termes du langage. La donnée étant par principe identique à un programme, on choisira des termes qui correspondent à des programmes au sens topologique où on l'entend. L'approche s'effectue par le haut.
La question devient « Qu'est ce qu'un programme ? ». Le programme est par principe de taille finie, c'est pourquoi le terme est par principe de taille finie. Certains programmes appelés « Démon » peuvent avoir vocation à ne jamais s'arréter, traitant au moins un flux de données c'est à dire un flux de termes, en entrée et/ou en sortie. Nous traiterons cette catégorie en second lieu.
En dehors de la catégorie "Démon", un programme possède une entrée finie et une sortie finie. Il procède ainsi à un calcul utilisant une suite de termes en entrée pour produire une suite de termes en sortie. Il traite les termes reçut en entrée dans un ordre quelconques permettant le parallélisme. Mais pour ce faire, il est nécessaire que tous les termes d'entrée ait été reçus et que le nombre de termes d'entrée soit à ce moment là connu par le programme avant que celui-ci ne démarre son traitement. Et le programme ne traitera pas nécessairement toutes les termes transmis en entrées. En revanche le programme devra produire tous les termes en sortie avant d'émettre le résultat. Le programme produit les termes de sortie dans un ordre quelconque permettant le parallélisme.
Tel un fractal, un programme, s'il est suffisament complexe, comprendra des sous-programmes qui se comportent comme des programmes, c'est à dire ayant une entrée finie et une sortie finie. La programmation consistera alors à raccorder les différentes sorties aux différentes entrées de ces différents sous-programmes.
On se restreint aux seuls programmes et sous-programmes ne proposant qu'un seul terme en sortie, et que nous appelons « Fonction ». Notez que cette restriction n'altère ni le domaine de calculabilité, ni sa complexité, car la suite de termes résultats peut toujours être regroupée dans un terme unique servant de résultat.
Le programme est alors une fonction multi-aire qui s'applique à plusieurs termes numérotés de `1` à `n` pour produire un terme.
Le programme étant un terme, si nous considérons un premier terme appelé `alpha`, nous obtenons la définition du langage alpha. C'est un langage engendré par un élément `alpha` qui constitue le premier terme qui joue le rôle de fonction multi-aire s'appliquant à des termes pour produire un terme. Selon la notation anglaise, on peut alors combiner `alpha` en formant des termes tels que : `alpha`, `alpha(alpha)`, `alpha(alpha,alpha)`, `alpha(alpha)(alpha)`, `alpha(alpha(alpha)(alpha),alpha)`, etc..
Ce langage correspond à une structure libre où l'on considère tous les termes d'expression distincts désignant des éléments distinct. Posons la question à ChatGPT o1 :
En algèbre.
On considère un élément `alpha`.
On définit ce qu'est un terme par les trois axiomes suivants :
1) `alpha` est un terme.
2) Un terme peut se composer avec une liste de termes pour produire un terme.
3) La liste vide notée `()`, est autorisée.
Voici des exemples de termes : `alpha`, `alpha(alpha)`, `alpha(alpha,alpha)`, `alpha(alpha(alpha),alpha)(alpha)`, `alpha()`, `alpha()()`.Si chaque terme distincte de ce langage désigne un élément distinct, l'ensemble des termes forme alors une structure libre. Comment peut on appeler cette structure libre ?
Réponse de ChatGPT : Raisonnement en 18 secondes
En termes d’algèbre universelle, la famille de tous ces termes (où l’on distingue bien chaque terme syntaxiquement) s’appelle simplement l’algèbre libre engendrée par `alpha` pour la signature considérée. On parle aussi d’algèbre de termes ou d’absolument libre, selon la terminologie.
En effet, la construction «termes = éléments distincts» est exactement la manière dont on définit, en algèbre universelle, la free algebra sur un ensemble de générateurs (ici, un seul symbole `alpha`, qui peut être utilisé avec toute arité). Les «axiomes» que vous listez (alpha est un terme, on peut composer un terme avec une liste de termes pour former un nouveau terme, etc.) décrivent précisément la syntaxe d’un langage où `alpha` est une opération d’arité variable (ou une famille d’opérations `alpha_n` pour chaque arité `n`), et où l’on n’identifie aucun terme avec un autre. C’est le sens même d’«algèbre libre».
La suite de termes qui a vocation à être transmise à une fonction, forme un type de donnée particulier appelé séquence ou n-uplet. Dans la notation par défaut, la virgule est utilisée pour séparer les termes dans une séquence. La séquence est necéssairement de taille finie. Elle constitue un objet un peu plus générale que le terme, possédant une arité de sortie qui est son nombre de composantes. La séquence vide `()` est d'arité de sortie `0`, un terme est une séquence d'arité de sortie `1`, un couple de termes est une séquence d'arité de sortie `2`, un triplet de termes est une séquence d'arité de sortie `3`, etc..
On note `bbbT` l'ensemble des termes.
On note `bbbT"*"` l'ensemble les séquences de termes.
On utilise l'opérateur de Kleene (une étoile en exposant `"*"` ) qui, appliqué à un ensemble retourne l'ensemble des suites finies ou vide d'éléments de cet ensemble, avec cette simplification que chaque élément de l'ensemble est identifié à la suite singleton le contenant. Notez que, `bbbT"*"` contient les termes en tant que suite singleton et contient la suite vide qui n'est pas un terme.
`() in bbbT"*"`
`bbbT ⊂ bbbT"*"`
On note `bbbT"×"bbbT` l'ensemble des couples de termes, on note `bbbT"×"bbbT"×"bbbT` l'ensemble des triplets de termes, etc..
`(bbbT"×"bbbT) ⊂ bbbT"*"`
`(bbbT"×"bbbT"×"bbbT) ⊂ bbbT"*"`
`(bbbT"×"bbbT"×"bbbT"×"bbbT) ⊂ bbbT"*"`
...
Dans une séquence, par défaut on utilise la virgule pour séparer les termes. La virgule joue alors un rôle d'un opérateur binaire de syntaxe centrée. Deux interprétations simple peuvent être faite, et dans ces deux interprétations, la séquence ne peut être que d'un seul niveau :
Soit on considère que la virgule est un opérateur associatif de `(T"*""×"T"*")->T"*"` et qui effectue la concaténation de deux séquences pour produire une séquence. Sa forme fonctionnelle se note `sf"concatenar"(".,.")`.
`x,y " =" sf"concatenar"(x,y)`
`x,y,z "=" sf"concatenar"(x,sf"concatenar"(y,z))`
`x,y,z "=" sf"concatenar"(sf"concatenar"(x,y),z)`
`x,y,z,t "=" sf"concatenar"(x,sf"concatenar"(y,sf"concatenar"(z,t)))`
`x,y,z,t "=" sf"concatenar"(x,sf"concatenar"(sf"concatenar"(y,z),t))`
`x,y,z,t "=" sf"concatenar"(sf"concatenar"(x,y),sf"concatenar"(z,t))`
`x,y,z,t "=" sf"concatenar"(sf"concatenar"(x,sf"concatenar"(y,z)),t)`
`x,y,z,t "=" sf"concatenar"(sf"concatenar"(sf"concatenar"(x,y),z),t)`
...
La séquence correspond au produit cartésien. Elle possède donc une propriété de liberté qui peut s'exprimer comme suit : L'ensemble `T"*"` munie de l'opération `sf"concatenar"(".,.")` forme un magma, auquel on ajoute l'associativité de `sf"concatenar"(".,.")`. Le magma devient alors un semi-groupe engendré par `T`. Et ce semi-groupe est libre. On exprime cette propriété en affirmant que à partir de l'ensemble des termes et en utilisant la fonction `sf"concatenar"(".,.")` on peut atteindre tous les éléments de `T"*"`.
`"<"T, sf"concatenar"(".,.")">" = T"*"`
Soit on considère que la virgule est un opérateur de `(T"×"T"*")->T"*"` et de syntaxe prioritaire à droite. Sa forme fonctionnelle se note `sf"coma"(".,.")`.
`x,y " = " sf"coma"(x,y)`
`x,y,z "=" sf"coma"(x,sf"coma"(t,z))`
`x,y,z,t "=" sf"coma"(x,sf"coma"(t,sf"coma"(z,t)))`
...
Le premier argument de `sf"coma"(".,.")` doit être un terme et son second argument doit être une séquence. Et rappelez-vous, un terme est une séquence singleton, et la séquence vide n'est pas un terme.
La séquence correspond au produit cartésien. Elle possède donc une propriété de liberté qui peut s'exprimer ici simplement par l'injectivité de la fonction `sf"coma"(".,.")` :
`AA(x,y,"*"u,"*"v), (x"≠"y "ou" "*"u"≠""*"v) => (sf"coma"(x,"*"u) "≠" sf"coma"(y,"*"v))`
Et que l'on présente généralement sous sa forme contraposée :
`AA(x,y,"*"u,"*"v), (sf"coma"(x,"*"u) "=" sf"coma"(y,"*"v)) => (x"="y "et" "*"u"=""*"v)`
Le fait de choisir un sens syntaxique prioritaire pour l'opérateur virgule rend unique la traduction d'une séquence en remplaçant la virgule par la fonction `sf"coma"`.
Nous définissons deux types de variable, les termes qui sont des éléments de `bbbT` et les séquences qui sont des éléments de `bbbT"*"` et qui comprennent les termes. Les variables de type « Terme » se note `x, y, z...`. Les variables de type « Séquence » se note `"*"x, "*"y, "*"z...`. L'étoile qui spécifie le type de variable fait partie du nom de la variable, faisant que `x` et `"*"x` sont deux variables distinctes et de type distinct mais non-disjoint, l'une désignant un terme, l'autre désignant un type plus vaste appelé séquence et comprenant les termes.
De par la syntaxe utilisée, nous savons quel est le type de la variable. La variable `x` est de type « Terme ». La variable `"*"x` est de type « Séquence ». Pour affirmer qu'une proposition `P(".")` satisfait tous les termes, nous écrivons :
`AAx, P(x)`
Et pour affirmer qu'une proposition `P(".")` satisfait toutes les séquences, nous écrivons :
`AA "*"x, P("*"x)`
On note `bbbT^n` l'ensemble des n-uplets de termes. Ainsi `bbbT^2` `"="` `bbbT"×"bbbT`, `bbbT^3` `"="` `bbbT"×"bbbT"×"bbbT`, etc.. Puis par convention, on note `bbbT^0` `"="` `{()}` l'ensemble singleton contenant la séquence vide. On note l'union disjointe en utilisant le signe `"+"` de priorité syntaxique plus faible que le produit cartésien `"×"`. Nous avons cette égalité :
`bbbT"*" = {()} + bbbT + bbbT"×"bbbT + bbbT"×"bbbT"×"bbbT+ ...`
`bbbT"*" = bbbT^0 "+" bbbT^1 "+" bbbT^2 "+" bbbT^3 "+" ...`
L'introduction de variables de type « Terme » `x,y,z,...` dans le langage alpha, va nous permettre de définir des ensembles génériques de termes et de séquences dans langage alpha. Voici quelques exemples :
Ces ensembles génériques ont une propriété intéressante, on peut facilement calculer leur intersection en procédant à l'unification des termes qui les désignent. Le langage alpha à cette propriété particulièrement intéressante pour l'informatique, il possède une opération d'unification de complexité linéaire lorsque les termes sont mémorisés sous forme d'arbre permettant le partage de données. Par exemple considérons les deux termes suivants :
`alpha(x,y)(alpha,y,t,alpha)`
`alpha(alpha(z),alpha)(z,z,t,z)`
L'unification se fait en parcourant en parallèle les deux termes et en affectant les variables autant que possible. On obtient la suite d'affectations des variables suivante : `x"="alpha(z)`, `y"="alpha`, `z"="alpha`. Et l'unification retourne comme résultat :
`alpha(alpha(alpha),alpha)(alpha,alpha,t,alpha)`
Le résultat désigne un ensemble qui correspond à l'intersection des deux ensembles désignés par les deux termes initiaux. Chacun des termes définit un ensemble générique de termes. L'unification retourne l'intersection qui est également un ensemble générique.
Si on tente d'unifier deux constantes distinctes ou deux séquences de tailles différentes, l'unification retourne la séquence vide qui représente l'ensemble vide. En particulier aucun terme ne s'unifit à `()`, et `()` n'est pas un terme, c'est pourquoi l'ensemble vide est désigné par la séquence vide `()`.
L'application d'unification noté `sf"unif"("*"x,"*"y)` s'applique à deux séquences pour produire une séquence :
`bbbT"*""×"bbbT"*" -> bbbT"*"`
`("*"x,"*"y) |-> sf"unif"("*"x,"*"y)`
L'application d'unification peut s'appliquer à une séquence de séquences pour calculer l'intersection commune à chacune des séquences membres de la séquence de séquences. Et le calcul s'avère toujours de complexité linéaire.
Nous définissons un troisième types de variable, les séquences de séquences de termes, `bbbT"**"`. On utilise l'opérateur de Kleene une seconde fois pour définir les suites de suites d'éléments.
Les variables de type « Terme » se notent `x, y, z,...`.
Les variables de type « Séquence de termes » se notent `"*"x, "*"y, "*"z,....`
Et les variable de type « Séquence de séquences de termes » se notent `"**"x, "**"y, "**"z,....`
L'application d'unification se déclare comme suit, et elle est de complexité linéaire :
`bbbT"**"-> bbbT"*"`
`("**"x) |-> sf"unif"("**"x)`
La troisième interprétation de la virgule qui est la plus générale consiste à l'identifier à un opérateur binaire générale, représenté par un point central «`"·"`» auquel on donne une priorité syntaxique à droite.
`a"·"b"·"c"·"d = a"·"(b"·"(c"·"d))`
Ce terme représente la liste `a,b,c` composée avec `d` c'est à dire `a"·"b"·"c"·"d`
où `d` représente la fin de la liste, soit une sorte de label. Comme on ne considère qu'un seul type de liste, on utilisera toujours un même terme pour désigner la fin de liste, le terme `sf"nada"` qui veut dire rien, qui pointe sur rien. On voit comment la définition des listes comme composition d'opérateurs va induire une implémentation qui est celle du langage LISP.
`[a,b,c] =a"·"(b"·"(c"·"sf"nada"))= a"·"b"·"c"·"sf"nada"`
Pour transformer les séquences en termes qui seront des listes, on définit la fonction multi-aire `sf"Lista"(...)` que l'on note entre crochets. Exemples :
`sf"Lista"(x,y,z) = [x,y,z]`
`sf"Lista"(x,sf"Lista"(a,b),z) = [x,[a,b],z]`
`sf"Lista"() = []`
`sf"Lista"(sf"Lista"(),sf"Lista"()) = ["[]","[]"]`
On ajoute les opérations de base sur les listes que l'on trouve dans le langage LISP, les opérateurs `sf"car"` et `sf"cdr"`
`sf"car"("["x,y,z"]")` retourne `x`
`sf"cdr"("["x,y,z"]")` retourne `[y,z]`
`sf"cdr"("["x"]")` retourne `[]`
`sf"cdr"("[]")` retourne `sf"nada"`
`sf"car"("[]")` retourne `sf"nada"`
D'un point de vue informatique, le terme `sf"nada"` désigne un pointeur pointant sur rien. L'opération `sf"cons"` correspond à :
`sf"cons"(x, [y])` retourne `[x,y]`
`sf"cons"(x, [])` retourne `[x]`
`sf"cons("[x], [y]")"` retourne `[[x],y]`
`sf"cons"(x, f)` retourne `x"·"f`
`sf"cons"(x, y"·"f)` retourne `x"·"y"·"f`
`sf"cons"(x, y"·"sf"nada")` retourne `[x,y]`
Puis on ajoute les opérations symétriques agissant par l'autre bout de la liste `sf"icar"`, `sf"icdr"`
Pour introduire la fonction `sf"unif"` dans notre langage. Soit on choisie de recourir à la fonction liste `["..."]` pour utiliser les séquences comme des termes. Exemple d'appel :
`sf"unif("[x,y,z],[u,v,w]")"`
`sf"unif("[x,y,z],[u,v,w],[a,b,c]")"`
Soit on en fait un opérateur binaire noté `"∧"` de priorité inférieure à la virgule. Exemples d'appels :
`x,y,z ∧ u,v,w`
`x,y,z ∧ u,v,w ∧ a,b,c`
Etant donné le langage alpha engendré par l'unique constante `alpha`. On considère des variables `x,y,z,` et des variables séquentielles `"*"u, "*"v, "*"w.`
On intègre ces variables dans le langage alpha par une extension élémentaire, C'est àdire que l'on ajoute au langage les constantes `x,y,z` de type « Terme » et les constante `"*"u, "*"v, "*"w.` de type « Séquence »
On obtient un langage alpha étendu, c'est à dire un ensemble des termes étendus, que l'on note comme suit :
`bbbT[x,y,z,"*"u,"*"v ,"*"w]`
C'est l'ensemble des termes comprenant ces variables et ces variables séquentielles énumérées entre crochet. L'ensemble des séquences de termes étendus se note comme suit :
`bbbT[x,y,z,"*"u,"*"v ,"*"w]"*"`
Pour pouvoir utiliser ces variables de Type Séquence, on utilise la fonction `sf"coma"(".,.")` de `(T"×"T"*")->T"*"` que l'on note sous sa forme d'opérateur virgule, un opérateur binaire de syntaxe centrée et de syntaxe prioritaire à droite faisant que `x,y,z,t = x,(y,(z,t))`
De ce fait, il ne peut y avoir dans une séquence au plus qu'une variable séquentielle comme membre et celle-ci doit être placée à la fin de la séquence.
Exemples de termes comprenant des variables et des variables séquentielles :
`alpha("*"u)`
`alpha("*"u)(x,"*"v)(alpha,y)`
`x(y,x("*"u),y,"*"v)`
Exemples de séquences comprenant des variables et des variables séquentielles :
`"*"u`
`x,"*"u "==" sf"coma"(x,"*"u)`
`x,alpha(x),"*"u "==" sf"coma"(x,sf"coma"(alpha(x),"*"u))`
`x,alpha(y,"*"u),y,"*"v "==" sf"coma"(x,sf"coma"(alpha(y,"*"u),sf"coma"(y,"*"v)))`
L'introduction de variables séquentielles `"*"u`, `"*"v,` `"*"w,...` nous permet de définir davantage d'ensembles génériques. Voici quelques exemples :
Dans une séquence séparée par des virgules, il ne peut y avoir au plus qu'une seule variable séquentielles et celle-ci doit être placée à la fin de la séquence. Sans quoi il se produit à un moment que le premier argument de la fonction `sf"coma"(".,.")` n'est pas un terme.
L'unification remplace le cas échéant les variables séquentielles qui sont toujours unique dans une séquence et placée en fin de séquence, par une séquence de termes se terminant éventuellement par une variable séquentielle. Ainsi lorsque l'on doit unifier `"*"u` avec le reste d'une séquence `(x,y,"*"v)`, la variable `"*"u` va pointer sur cette nouvelle séquence, ce qui est possible lorsque les termes sont mémorisées sous forme d'arbre permettant le partage de données. Ainsi l'unification reste de complexité linéaire.
La séquence vide n'étant pas un terme, lorsqu'une fonction retourne la séquence vide, cela correspond en faite à un exception. Il est possible de gérer ces exceptions de façon presque naturel en créant des éléments spéciaux auquel on accorde des comportements par défaut spéciaux. C'est le cas de la séquence vide.
Dans notre langage tous se ramène à un empilement de fonctions. Lorsqu'une fonction retourne une séquence vide qui sert de terme d'entrée à une autre fonction, telle une exception, lorsque cet fonctions va utiliser cette donnée, elle s'interrompra et retournera aussitôt la séquence vide. En revanche, lorsqu'une fonction retourne une séquence vide qui sert de séquence d'entrée ou de fin d'entrée d'arité variable à une autre fonction, cela n'entraine aucune perturbation. En d'autre terme, là où on attend un terme, si une séquence vide arrive, alors l'exception se propagera. En revanche, là où on attend une séquence, l'arrivé d'une séquence vide ne créra pas d'exception.
Une fonction `f` possèdant une entré d'arité variable, pourrait possèder une seconde entrée d'arité variable. L'appel pourrait ressemblé à `"*"x "<"f">" "*"y` où `"<"f">"` serait la forme d'opérateur binaire de `f` avec une pririté syntaxique inférieur à celle de la virgule. Et elle pourrait possèder n entrées d'arité variables que l'on pourrait écrire en utilisant un second opérateur virgule `"།"` permettant de passer en argument une séquence de séquence. Exemples :
`f("*"x ། "*"y ། "*"z)`
`f(a,b,"*"x ། c,"*"y ། "*"z)`
Et il est possible d'ajouter comme argument une séquence variable de séquences placée en fin de séquence de séquences. Exemple :
`f(a,b,"*"x ། c,"*"y །"**"u)`
Et le mécanisme d'unification est toujours linéaire. Les séquences sont d'un seul niveau, et lorsque nous avons besoin d'avoir un niveau suplémentaire on utilise une nouvelle virgule, ici `"།"`. Et les séquences et de séquences sont encore d'un seul niveau. Pour toujours garder une complexité linéaire de l'opération d'unification, il faut utiliser un symbole virgule distinct pour chaque niveau d'emboitement de séquences et placer au dernier terme de la séquence l'éventuel variable séquencielle d'ordre suivant. Nous avons :
Opérateur Variable séquencielle
Notre langage est interprété par un interpréteur. Lorsque l'on soumet un terme à l'interpréteur, celui-ci va l'évaluer relativement à un contexte en cours contenant la grammaire, et retourner un terme résultat. On notera `X↬Y` avec une priorité syntaxique la plus faible de toute, pour indiquer que l'évaluation du terme `X` par l'interpréteur retourne le terme `Y`. La forme fonctionnelle de cet opérateur se note `sf"evaluar(.)"`. Ainsi `sf"evaluar"(X)=Y`
Une donnée `f`, si elle n'est pas définie alors elle se comportera comme suit: Lorsque l'on demandera son évaluation c'est à dire lorsqu'on demandera qu'elle retourne son contenu, elle retournera elle-même, et représentera ainsi une variable libre suceptile de s'unifier à toute donnée.
`f↬f`
Un programme `f` appliqué à une séquence quelconque de termes `"*"x` servant d'entrée, se note `f("*"x)`. Si le programme `f` n'est pas défini alors il se comportera comme suit: Lorsque l'on demandera l'exécution de son programme avec comme entrée la séquence `"*"x`, il retournera comme résultat le terme `f("*"x)`, et représentera ainsi une fonction libre suceptile de s'unifier à toute fonction.
`f("*"x) ↬ f("*"x)`
L'appel `f(x,y,z,"*"u)` ne présage ni la façon ni l'ordre dans le quel vont être traité les termes `x,y,z,"*"u`. Certaines fonctions peuvent ne pas évaluer certains termes d'entrées et prendre leurs expressions telles quelles sans les évaluer. C'est la fonction `f` qui va déterminer comment et dans quel ordre sont traité ses arguments.
En revanche, si au lieu d'un tel appel nous avons une séquence de termes `a,b,c`, personne n'est là pour indiquer dans quel ordre seront évaluées ces 3 termes, en série ou en parallèle ?
S'ils s'évaluent en parallèle, cela veut dire qu'ils s'évaluent à partir d'un même contexte initial. Et s'ils s'évaluent en série, cela veut dire que l'évaluation de `a` peut modifier le contexte à partir duquel sera évalué `b` qui modifiera encore davantage le contexte à partir duquel sera évalué `c`.
Pour spécifier une évaluation en série, on utilisera l'opérateur point-virgule à la place de l'opérateur virgule. Et pour spécifier une évaluation en parallèle, on utilisera l'opérateur dièse à la place de l'opérateur virgule. L'opérateur point-virgule aura une priorité synaxique plus faible que celle de l'opérateur dièse. Exemple
`a";"b"#"c";"d`
L'évaluation de ce terme calcul en parallèle `a;b` et `c;d`. Le résultat sera `a";"b"#"c";"d` avec des effets de bord de `a` qui va modifier `b` et des effet de bord de `c` qui va modifier `d`. Mais le calcul de `a";"b` n'aura pas d'effet de bord sur c";"d
Le dièse et le point-virgule peuvent être utilisé indifféremment pour constituer des séquences. On réserve la virgule lorsque la séquence est évalué par les fonctions qui déterminent déjà cela.
Lorsque l'on soumet une séquence à l'interpréteur, celui-ci va évaluer la séquence en respectant ces directives séries et parallèles, en revanche il ne sera pas interpréter la virgule.
Un flux de termes peut ne pas avoir de fin et donc être de taille infinie, en revanche une séquence comme un terme doit être de taille finie.
La séquence à vocation à regrouper les arguments d'entrée d'une fonction sur laquel un mécanisme d'unification peut s'appliquer Tandis que le flux de données qui peut être sans fin va voir son premier terme traité par la fonction comme un argument dès l'établissement de la connexion du flux.
La calculabilité met en exergue deux concepts important qu'est la séquence de données représenté par la variable muette `"*"x` et qui est suceptible de s'unifier à d'autres séquences, et le flux de données représenté par la variable muette `©x` qui peut être sans fin et où le taitement des données commence dès l'établissement de la connexion du flux, celui-ci présentant son premier terme comme un argument d'entrée.
Les flux ou canaux sont des éléments essentiels de programmation, c'est pourquoi ils seront identifiés à des éléments ordinaires avec toutes les commoditées qui les accompagnent, sur lesquels on ajoutera par dessus les méthodes spécifiques aux canaux.
La plus part du temps les flux se terminent. Apparait donc un terme spécifique pour indiquer la fin du flux de termes. C'est le terme de fin-de-transmission. On le notera `∎`.
Le flux est un canal reliant une sortie à une entrée. Le flux est un canal pouvant relier plusieurs sorties à plusieurs entrées. Et le flux peut être cloné plusieurs fois.
S'il est synchrone alors il forme un mécanisme rigide de transmission de termes. S'il est asynchrone alors il forme une file de termes. La variable désignant le flux se comporte comme une variable contenant le premier terme du flux. Mais un flux peut être vide. Apparait donc un terme spécifique pour indiquer un flux vide. C'est le terme désignant rien, noté `sf"nada"` ou de façon court par le symbole `□`.
Le flux synchrone bloque l'émetteur, et il peut y avoir plusieurs émetteurs sur un même flux, tant que le récepteur n'a pas retiré le terme transmis, et il peut y avoir plusieurs récepteurs sur un même flux. Chaque flux cloné est suceptible de bloquer les émetteurs, celui-ci devra attendre que l'un des récepteurs est retiré le terme transmis, et ceci dans chaque clone du flux.
Le flux asynchrone ne bloque plus les émetteurs, mais la file de termes que représente le flux peut s'accroître considérablement et dépasser la taille mémoire disponnible. Pour éviter cette erreur, le flux asynchrone comprend un mécanisme de retour d'information au près des émetteurs sur la taille du flux et également de chacun de ses clones (car il peut également être cloné plusieurs fois).
Nous avons trois types de variable, les termes tel que la variable `x` qui désigne un élément de `bbbT`, les séquences de termes telle que la variable `"*"y` qui désigne un élément de `bbbS`, et dont le principe est qu'il puisse être unifiié avec d'autre séquences de termes, et le flux de termes tel que la variable `©z` qui désigne un canal, et dont la valeur qu'il représente à un instant donné est le terme placé en tête du flux, qui peut être `□` si le flux est vide, et qui peut être `∎` si le flux est fermé. Et la tête du flux joue le rôle d'une entrée.
On définit une fonction `"|"` appelé constructeur de fonction. Il prend en premier argument une séquence de variables muettes distinctes et en second argument un programme écrit dans le langage augmenté des variables muettes, qui peuvent venir masquer des variables de même noms déjà existantes. Et on le munie d'une syntaxe centrée de priorité plus faible que la virgule, le transformant ainsi en un opérateur. Par exemple :
`x,y,z "|" c(x,c(y,x),z)`
L'opérateur `"|"` appliqué à la séquence de variables muettes `x,y,z` et au terme `f(x,d(y,x),z)` produit la fonction correspondante. Autrement dit ce terme est un programme, que l'on peut appliquer directement à 3 arguments :
`(x,y,z "|" d(x,c(y,x),z))(u,v,w) ↬ d(u,c(v,u),w)`
Vous remarquerez que le premier membre définit 3 nouvelle variables libres `x,y,z` dont la portée s'étend juste sur le corps de la fonction. Il y a donc un contexte propre au corps de la fontion qui contient un langage enrichie de ces 3 variables supplémentaires. La fonction `"|"` prend comme premier argument une séquence composée de variables, et elle n'évalue pas ces variables, elle prend seulement leur nom qu'elle rajoute au contexte comme nouvelles variables, masquant les variables de même noms déjà référencées dans le contexte, pour former un nouveau contexte dont la portée s'arrête au second membre appelé le corps de la fonction. Noter que la fonction ainsi produite peut s'appliquer à un terme contenant des variables de même noms que celles utilisé dans l'appel, sans que cela n'ait d'importance, car les variables d'appel sont muette, ce sont de nouvelles variables libres.
La fonction ainsi définie est d'arité fixe, égale à 3. Cela a pour conséquence que appliqué à une séquence de taille différente, la fonction retourne `sf"nada"`. On peut proposer un autre comportement, en spécifiant des valeurs par défauts des derniers arguments. Exemple :
`x,y=a,z=a(x) "|" c(x,c(y,x),z)`
Dans cet exemple, la fonction ainsi définie est d'arité 1 ou 2 ou 3.
Nous avons une notation plus explicite, où figure la déclaration des variables muettes :
`AA(x,y,z), (x,y,z)|->d(x,c(y,x),z)`
Et où le meta-opérateur `"↦"` est un simple opérateur de construction de couple, construisant une arrête appartenant au graphe de la fonction que l'on définit. La méta-opération est transférée à l'opérateur de déclaration de variable universelle `AA` qui prend en argument une liste de nouvelles variables dont la portée s'étend au corps au corps de la fonction, c'est à dire au seul bloc où se trouve cette déclaration. Ainsi ce terme désigne un ensemble d'arrêtes définissant le graphe d'une fonction. La fonction est définit par son graphe qui est l'ensemble des arrêtes :
`(AA(x,y,z), (x,y,z)|->d(x,c(y,x),z)) (u,v,w) ↬ d(u,c(v,u),w)`
On perfectionne la définition de fonction. Le premier membre de l'opérateur de construction de fonction, devient un terme quelconque appelé la tête de la fonction tandis que le second membre est appelé le corps de la fonction. Cela restreint le domaine de définition aux seuls termes qui s'unifient avec la tête de la fonction. Exemple :
`AA(x,y,z,t), (x,d(x,x),z(a, y))|->d(x,c(y,b),t)`
Cela définit une fonction qui appliquée à `c,d(c,c),b(a,d(a))` retourne `d(c,c(d(a),b),t)` où `t` est une variable libre non affectée, et donc restera libre dans le terme retourné en dehors du bloc. En revanche appliqué à `a,d(a,a),a`, elle retourne `sf"nada"` qui indique que l'on applique la fonction en dehors de son domaine de définition, et qui peux représenter l'ensemble vide `Ø`.
On définit une fonction par morceau par une séquence de fonctions. Exemple de fonction définie en trois morceaux :
`AA(x,y)`
`(a(x),y)|->b(x,y)`
`(b(x),y)|->c(x,y)`
`(x,y)|->d(x,y)`
Le passage à la ligne est un alias du point-virgule et de la virgule. Par défaut, la fonction va utiliser la première sous-fonction qui marche c'est à dire qui aboutit à un résultat autre que `sf"nada"`. On peut également par le même procédé définir des fonctions ayant plusieurs arités. Exemple
`AA(x,y)`
`a(x)|->b(x,y)`
`(b(x),y)|->c(x,y)`
`(x,y,a)|->d(x,y)`
Cette fonction est suceptible de prendre 1 ou 2 ou 3 arguments.
`AA(x,"*"u,"*"v)`
`(x,x)|->a(x,y)`
`(x,a("*"u),"*"v)|->c(x("*"u),"*"v)`
`(x,"*"u)|->"*"u`
Cette fonction est suceptible de prendre 2 ou plus d'arguments.
On autorise maintenant aux fonctions de retrouner des séquences. Mais, pour toujours garder une complexité linéaire de l'opération d'unification, il faut dans le cas où la fonction retourne une séquence, que l'appel de celle-ci soit le dernier terme d'une séquence. Et de même pour les séquences de séquences, etc.. La fonction possèdera donc un type de résultat. Un terme est de tous les types, c'est une séquence singleton, c'est une séquence de séquence singleton, etc.. La fonction qui retourne toujours un terme est de type de résultat « Terme ». La fonction qui retourne un terme ou une séquence est de type de résultat « Séquence », etc..
Néanmoins, une fonction ayant un type de résutat « Séquence » n'est pas très pratique puisque son appel ne peut être placé qu'au dernier terme d'une séquence. C'est pourquoi on utilise le terme `sf"nada"` lorsque la fonction retourne la séquence vide par exemple, cela permet de définir des fonctions de type de résultat « Terme » avec ce terme `sf"nada"` qui est produit lorsqu'il n'y a pas de résultat et auquel est associé des règles d'exception.
Une fonction unaire est un programme qui ne prend pas d'argument. Il est néanmoins dépendant du contexte, son exécution produira des résultats différents selon le contexte. Considérons une fonction unaire `p`. La fonction est ici désignée par une lettre qui est une variable `p` contenant le programme écrit dans notre langage. Mais elle peut être désigné directement par le programme. L'appel se fait en accollant des parenthèses `()`. Le terme `p()` s'évalue en effectuant le programme contenue dans `p`, tandis que le terme `p` s'évalue en retournant le programme contenue dans `p`.
---- 2 avril 2025 ----
On définit un nouveau genre d'appel sous forme d'une composition en liste où les éléments sont séparés par des caractères blancs comme en Haskel. Étant donnée des fonctions `f,g` d'arité fixe 2 , et des fonctions `x,y,z,t,u,v`, d'arité fixe nulle.
La composition `f x` va retourner une fonction unaire `(AAy, y|->f(x(),y))`
La composition `f x y` va retourner `f(x(),y())`
La composition `f x y z t` va retourner `f(x(),y()) z() t()`
La composition `f x g y z t` va retourner `f(x(),g(y(),z())) t()`
Avec des fonctions d'arité multiple programmée par morceau comme au chapitre 16.1, la fonction prend un nombre d'argument qui peut varier selon la valeurs même des arguments. Il n'y a pas d'appel de fonction, juste une composition où tous les éléments vont être exécuter comme fonction
---- 30 mar 2025 ----