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, pour assurer l'efficacité du programme. 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, et ont la capacité de traiter des flux de données en entrée et en sortie. Un flux de données est un flux de termes. Nous traiterons de 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 commence son calcul une fois que tous les termes d'entrée ont été reçus et que le nombre de termes d'entrée est connu par le programme. Le programme devra produire tous les termes en sortie avant d'émettre le résultat. Cela met en oeuvre une forme de parallélisme.
Tel un fractale, un programme, s'il est suffisament complexe, comprendra des sous-programmes qui se comportent comme des programmes. Un programme contiendra des sous-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.
Cela permet de mettre en oeuvre la pile des appels avec un contexte distinct pour chaque appel d'un sous-programme.
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. Autre avantage, comme il n'y a qu'un terme résultat, on pourra utiliser la notation du physicien qui reprend le nom de la fonction (le nom du programme) pour désigner son résultat sous forme d'une variable, à partir de variables d'entrées par défaut (constituant un système de coordonnées par défaut).
Le programme est 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. 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. Si on ne considère que des suites aplatie, que d'un seul niveau, appelées "Séquence", alors deux interprétations simple peuvent être faite de la virgule, concaténation ou emboitement.
Soit on considère que la virgule est un opérateur associatif de `(T"*""×"T"*")->T"*"` qui admet la séquence vide `()` comme élément neutre.
On note les variables contenenant une séquence de terme par une lettre préfixée par une étoile. Ainsi `x` désigne un élément inconnu appartennt à `T` et `"*"x` est une autre variable qui désigne une séquence de termes inconnue appartenant à `T"*"`.
Sa forme fonctionnelle se note `sf"concatenar"("*x,*y")`.
`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)`
...
La séquence correspond au produit cartésien. Elle possède 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"(".,.")`, et l'élément neutre `()`. Le magma devient alors un monoïde engendré par `T`. Et ce monoïde est libre.
On exprime cette propriété en proposant une implémentation des séquences et de la fonction `sf"concatenar"(".,.")` qui effectue la concaténation de deux séquences pour produire une séquence.
Soit on considère que la virgule est un opérateur de `(T"×"T"*")->T"*"` et de syntaxe prioritaire à droite, et qui admet la séquence vide `()` comme élément neutre à droite. Sa forme fonctionnelle se note `sf"coma"("x,"*"y")`.
`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 unaire `P(".")` satisfait tous les termes, nous écrivons :
`AAx, P(x)`
Et pour affirmer qu'une proposition multi-aire `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 le 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.
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, qui permet de définir des arbres, consiste à l'identifier à un opérateur binaire, représenté par un point central «`"·"`», correspondant à l'opérateur d'un magma libre, et 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 constantes `"*"u, "*"v, "*"w.` de type « Séquence »
On obtient un langage alpha étendu, c'est à dire un ensemble de 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. C'est cette condition, qui peut être imposée en choisissant d'utiliser que des opérateurs où seul le dernier membre de l'appel peut éventuellement être de type Séquence, qui permet d'implémenter une fontion d'unification de complexité linéaire.
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` peut posséder une entrée d'arité variable. Et il n'y a pas de raison de se limiter à cela. La fonction `f` devra pouvoir possèder `n` entrées d'arité variables. Ces `n` entrées d'arité variable peuvent être écrites en utilisant un second opérateur virgule `"།"` de priorité syntaxique plus faible et permettant ainsi de passer en argument une séquence de séquences. Exemples :
`f("*"x ། "*"y ། "*"z)`
`f(a,b,"*"x ། c,"*"y ། "*"z)`
Puis il est possible d'ajouter comme dernier argument une variable contenant une séquence de séquences, toujours 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 de complexité linéaire, rendant cette solution pertinente. Les séquences sont d'un seul niveau, et lorsque nous avons besoin d'avoir un niveau supplémentaire on utilise une nouvelle virgule de priorité syntaxique plus faible, 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 Prototype
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 l'interpréteur est une fonction, `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, si c'est une variable, lorsqu'on demandera qu'elle retourne son contenu, elle retournera elle-même, et représentera ainsi une variable libre susceptible 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 susceptile de s'unifier à toute fonction.
`f("*"x) ↬ f("*"x)`
Mais détaillons l'évaluation de `f("*"x)`. Cette expression comprend deux variables `f` et `"*"x`. Et on applique l'une sur l'autre, ce qui peut se noter en utilisant l'application d'application notée `"@"(".,...")`, c'est dire par l'expression `"@"(f,"*"x)`.
Lorsque l'on évalue le terme `f("*"x)` on commence par évaluer la variable `f` qui étant libre retourne `f`, puis on l'applique à la variable `"*"x` ce qui produit le terme `f("*"x)` où `"*"x` n'est pas évalué, car c'est le progrmme `f` qui décide s'il faut évaluer ou pas ses arguments, et comme `f` est une variable libre, l'application d'une variable libre sur quelque chose retourne le terme composé sans rien évaluer.
Comme il n'y a pas de différence entre donnée et programme, évaluer une donnée consiste à exécuter un programme. La donnée représentée par le terme `x` est donc un programme. Et le résultat de son exécution dépend de l'état du système, ou plus précisément d'un ensemble de variables appelé la base de `x`. C'est une partie du contexte.
Les variables, qui jouent un rôle paradigmatique, sont caractérisées par un état qui est une caractérisation plus complète que leur seul contenu. Le contenu d'une variable ne désigne que le terme auquel la variable permet d'accéder, alors que son état caratérise complètement la variable dans le système.
Le contexte représente l'état du système, c'est à dire l'état de toutes les variables. L'évaluation d'une donnée, c'est à dire l'évaluation d'un terme `x`, ne va pas seulement produire un terme résultat, mais va modifier l'état du système. Cette modification du système est appelé l'effet de bord, et il couvre un ensemble de variables suceptibles d'être modifiées par l'évaluation du terme en question, et que l'on appelle le bord de `x`, et qui constitue une partie du contexte.
Si des termes `x,y,z` ont des bords disjoints de chaque base et de chaque bord, ils peuvent être évalués dans n'importe quel ordre, l'état du système sera le même à la fin. Par contre si le bord de `x` n'est pas disjoint de la base et du bord de `y` alors l'exécution de `x` puis de `y` pourra ne pas avoir le même effet que l'exécution de `y` puis de `x`.
On utilise le point-virgule pour composer en série les programmes. Ainsi, l'évaluation de `x";"y";"z` procédera à l'évaluation de `x` puis de `y` puis de `z`. L'évaluation d'un terme produit un terme. Les résultats intermédiaires ne sont pas gardés, seul celui obtenu par le dernier calcul est retenu et fait office de résultat.
Si on souhaite appliquer la composition série à une séquence de programmes `x,y,z`, on utilise la fonction `sf"evaluar_en_serie"(x,y,z)`.
`sf"evaluar_en_serie"(x,y,z) = x";"y";"z`
L'appel `f(x,y,z,"*"u)` ne présage pas si les termes `x,y,z,"*"u` vont être évalués ou non ou même plusieurs fois, ni dans quel ordre ils vont être traités. Certaines fonctions peuvent ne pas évaluer certains termes d'entrées et prendre leurs expressions telles quelles sans les évaluer. D'autre fonction vont évaluer plusieurs fois leurs arguments. C'est la fonction `f` qui va déterminer les traitements et l'ordre des traitements de ses arguments. Par contre l'appel doit être formalisé en une séquence `(x,y,z,"*"u)` transmise à la fonction `f(...)` avant qu'elle ne commence son traitement.
Si au lieu d'un tel appel nous avons simplement une séquence de termes `a,b,c`, que se passe-t-il ?. L'évaluation de la séquence par l'interpréteur sécrit :
`sf"evaluar(a,b,c)"`
Les termes `a,b,c` sont évalués par la fonction `sf"evaluar"` qui évalue dans l'ordre chaque temre de la séquence `(a,b,c)` et retourne le résultat sous forme de séquence `sf"evaluar"(a),sf"evaluar"(b), sf"evaluar"(c)`. Tandis que `x";"y";"z` correspond à `sf"evaluar_en_serie"(x,y,z)` et ne retourne comme résultat que le dernier terme évalué..
Unix a inventé le concept de processus avec son environnement propre, et le concept d'exécution en arrière plan. A chaque fois qu'il crée un processus, il duplique le contexte du processus parent pour en donnée un au fils, autrement-dit, il fait une copie de l'état du système qu'il met à disposition du nouveau processus.
On note `x#` la création d'un processus pour calculer `x` en arrière plan. Une fois `x` calculé, le contexte obtenu et abandonné, seul le résultat est gardé `sf"evaluar"(x)"`. On note `x#y` la composition parallèle. Le programme `x` est calculé en arrière plan et le programme `y` est calculé au premier plan, tout deux à partir d'un même contexte initial qui a été dédoublé, mais le contexte résultant sera celui modifié par `y`, car celui modifié par `x` n'est pas gardé, seul le résultat est gardé. Le résultat sera la séquence des deux résultats.
Si on souhaite évaluer en parallèle les termes `a,b,c`, on notera `a#b#c`. Cela veut dire que l'évaluation de `a` de `b` et de `c` se font à chaque fois à partir d'un même contexte initiale. Puis `a` et `b` sont exécutés en arrière plan dans des processus isolés où le conctext final n'est pas gardé, seul les résultats sont gardés et mis dans une séquence.
L'opérateur point-virgule, appelé l'opérateur de composition série de programmes, aura une priorité synaxique plus faible que celle de l'opérateur dièse, appelé l'opérateur de composition parallèle de programmes. Exemple :
`a";"b"#"c";"d`
L'évaluation de ce terme évalue en parallèle `a";"b` et `c";"d`. Les effets de bord de `a` peuvent modifier l'évaluation de `b` et les effets de bord de `c` peuvent modifier l'évaluation de `d`. Mais l'évaluation de `a";"b` n'aura pas d'effet de bord sur l'évaluation de `c";"d`. Le résultat sera une séquence de deux termes, et le contexte final sera celui créé par `c";"d`
La séquence non-singleton n'étant pas un terme, l'opérateur virgule aura la priorité la plus faible.
Dupliquer le contexte est une opération lourde. c'est pourquoi il est pertinent de concevoir la notion de contexte partiel, désignant une petite partie du contexte c'est à dire un petit ensemble de variables, une séquence de variables. Etant donné un tel contexte partiel noté `"*"v`. On redéfinie la notion d'éxecution parallèle en le limitant à ce contexte partiel. Le programme `x#^("*"v)` est executé dans un sous contexte où toutes les variables de la séquence `"*"v` sont copiées et créées comme variables locales. L'exécution de `x#^("*"v)y` s'exécute en parallèle pour les variables de la séquence `"*"v`, et s'exécute en série pour les autres variables.
Un flux de termes peut ne pas avoir de fin et donc être de taille infinie, en revanche une séquence ou un terme doit être de taille finie.
La séquence à vocation à regrouper les arguments d'entrée d'une fonction sur laquelle 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 le démon comme un argument dès l'établissement de la connexion du flux.
La calculabilité met en exergue deux concepts importants qu'est la séquence de données représentée 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 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 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 `□`. 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 `∎`. Ces deux termes sont associés à des mécanismes d'exception.
Le flux peut-être synchrone ou asynchrone. 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 façon dont les sous-programmes peuvent être interconnectés par des flux constitue une sorte de topologie qui découle de la vision fractale du programme. Le flux est un canal reliant une sortie flux d'un programme à une entrée flux d'un programme. Le flux peut aussi être convertie en une séquence, à condition qu'il se termine. Le canal peut avoir plusieurs entrées, cela signifie qu'il y a plusieurs processus qui peuvent émettre et qui vont ainsi intercalé leur émission dans le canal, le premier processus demandant d'émettre d'abord. Le canal peut avoir plusieurs sorties, cela signifie qu'il y a plusieurs processus d'écoute qui vont pouvoir capturer des termes arrivants par ce canal, le premier demandant la capture d'abord.
Et le flux peut être cloné plusieurs fois, c'est à dire former plusieurs canaux ayant les mêmes sources mais pouvant avoir d'autres processus d'écoutes.
Le flux synchrone bloque l'émetteur, et il peut y avoir plusieurs émetteurs, tant que le récepteur n'a pas retiré le terme transmis, et il peut y avoir plusieurs récepteurs. 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 disponible. 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.
Nous avons plusieurs types de variable :
Et dont le principe est qu'elles puissent être unifiés avec d'autres données de même type avec une complexité linéaire.
La valeur de ©z à un instant donné est le terme placé en tête du flux ©z, qui peut être `□` si le flux est vide, et qui peut être `∎` si le flux est terminé. La tête du flux joue le rôle d'une variable d'entrée de type terme.
Pour clarifier nos exemples, consédérons un langage `a,b,s("."), f(".,."), g(".,.,."),k("...")`
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 "|" f(f(a,y),x)`
L'opérateur `"|"` appliqué à la séquence de variables muettes `x,y,z` et au terme ` f(f(a,y),x)` produit la fonction correspondante. Autrement dit ce terme est un programme, que l'on peut appliquer directement à 2 arguments `(u,v)` :
`(x,y,z "|" f(f(a,y),x))(u,v) ↬ f(f(a,v),u)`
Vous remarquerez que le premier membre définit 2 nouvelle variables libres `x,y` dont la portée s'étend 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 2 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. Notez 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 à 2. Cela a pour conséquence que appliquée à 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 "=" s(a),"|" f(f(a,y),x)`
L'opérateur d'égalité est de priorité syntaxique plus forte que celle de la virgule. La fonction ainsi construite est d'arité 1 ou 2. Elle s'applique nécessairement à un premier membre désigné par la variable muette `x` car ce membre n'a pas de valeur par défaut. Le membres suivant dans l'appel peut être omis car il a une valeur par défaut.
Etant donné une variable `z`. Notez que la fonction nullaire `() "|" z` n'est pas identique au terme `z`. En effet, l'évaluation de `z()` va exécuter le programme contenue dans la variable `z` en ne prenant aucun argument, tandis que `(() "|" z)()` est égale à `z`. Et si la variable `z` est libre, l'évaluation de `z()` donnera le terme `z()` et non le terme `z`.
Nous avons une notation plus explicite, où figure la déclaration des variables muettes :
`AAx, x|->f(x,x)`
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 de la fonction, c'est à dire au bloc où se trouve cette déclaration. Ainsi ce terme désigne un ensemble d'arrêtes définissant le graphe d'une fonction, et ainsi définie une fonction sans lui donner de nom. On peut alors appliquer cette fonction à l'entrée `u` :
`(AAx, x|->f(x,x)) (u) ↬ f(u,u)`
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, devant contenir toutes les variables déclarées universellement, 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), (x,f(x,x),f(a, y))|->g(x,y,b)`
Cela définit une fonction qui appliquée à `b,f(b,b),f(a,s(a))` retourne `g(b,s(a),b)`. En revanche appliqué à `a,f(a,b),f(a,a)`, elle retourne `sf"nada"` qui indique que l'on applique la fonction en dehors de son domaine de définition.
On définit une fonction par morceau par une séquence de fonctions. Exemple de fonction définie en trois morceaux :
`AA(x,y)`
`(s(x),y)|->f(x,y)`
`(x,s(y))|->g(x,y,x)`
`(x,y)|->g(x,x,y)`
Le passage à la ligne correspond à un opérateur de priorité syntaxique plus faible. 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)`
`s(x)|->f(x,x)`
`(s(x),y)|->f(x,y)`
`(x,y,a)|->f(y,x)`
Cette fonction est suceptible de prendre 1 ou 2 ou 3 arguments.
`AA(x,"*"u,"*"v)`
`(x,x)|->f(x,y)`
`(x,h("*"u),"*"v)|->f(g(x,"*"v),"*"u)`
`(x,"*"u)|->"*"u`
Cette fonction est suceptible de prendre 2 ou plus d'arguments.
Le méta-opérateur `AA` permet d'ajouter des variables libres au langage. Il peut être interprété de deux façons l'une logique, l'autre comme énumérateur.
L'expression `AAx` désigne un énumérateur de tout les termes du langage sans utiliser la variable muette.
---- 9 mai 2025 ----
`AA(x,y,z), g(x,g(y,x))`
---- 8 mai 2025 ----
Si on déclare de nouvelles variables libres apparaissant dans le corps de la fonction mais n'apparaissant pas dans la tête de la fonction, tel que par exemple :
`AA(x,y), x|->f(x,y)`
Cette fonction appliquée à `a` retourne `f(a,y)` où `y` est une variable libre non affectée, et donc restera libre dans le terme retourné en dehors du bloc. si `y` était déjà définie dans le bloc, la variable nouvellement créée doit être renomé en `v_1` par exemple, et le terme retourné serait `f(x,v_1)` où `v_1` serait une variable libre ajouté au contexte. `v_1` a été créé par l'opérateur `AA` dans le bloc de définition de la fonction.
Reste à savoir si on répète l'opération en appliquant cette même fonction à `b` ce qui retourne `f(b,y)` où il faut renommer `y`. On renomme cet `y` en `v_1` ou en `v_2`, selon une vision statique ou dynamique ? Pour répondre à cette question, on définit l'opérateur de déclaration de variable indépendament de la définition d'une fonction.
Un programme non-compilé se présente comme un terme appelé bloc de codes. C'est une succession de sous-programmes s'exécutant en série ou en parallèle selon l'opérateur les liants, "`;`" ou "`#`" .
Si dans un bloc de code qui représente un programme, on rencontre la déclaration d'une variable `AAx`. Celle-ci va ajouter au contexte du bloc de code une nouvelle variable libre `x` (pouvant masquer l'éventuelle variable de même nom provenant d'un héritage d'un contexte parent. Si le programme produit un terme résultat contenant cette variable, celle-ci devra être renommée si une variable de même nom existe. Elle constituera une variable libre.
Il existe alors deux formes d'appel de ce programme, l'un dit statique dans lequel les variables créées dans le bloque de code sont toujours les mêmes et sont libérés au moment de l'exécution de la déclaration, l'autre dit dynamique dans lequel les variables créées dans le bloque de code sont toujours des nouvelles variables libres. Ou bien cela peut être spécifié lors de la déclaration de variables libre :
`"estático" AA`
`"dinámico" AA`
...
---- 8 mai 2025 ----
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 ----