Pi-calcul

En pratique, un programme écrit en π-calcul (ou terme) décrit systématiquement un processus, généralement noté P, Q, R… Les processus représentent aussi bien les processus légers en anglais : threads ou processus lourds et aucune hypothèse n'est faite sur l'emplacement du processus : à ce niveau d'abstraction, celui-ci peut être exécuté sur n'importe quel composant ou n'importe quel ordinateur. Un langage de programmation concret ajoutera un compilateur ou un environnement d'exécution intelligent ou nécessitera plus de précisions pour savoir où placer le processus.

Plutôt que des données explicites, les programmes écrits en π-calcul manipulent des noms, le plus souvent notés a, b, c… x, y, z. Un nom est une construction abstraite qui peut, à ce niveau, représenter n'importe quel type d'information. Les noms sont utilisés comme des canaux : tout processus qui connaît le nom a peut écrire sur a ou lire depuis a. Les canaux diffèrent des variables et des constantes au sens où chaque lecture doit correspondre à une seule et unique écriture -- le processus qui écrit sur a envoie donc une information au processus qui lit sur a. Les informations, de nouveau, sont des noms. Un langage de programmation concret ajoutera des types de base (entiers, booléens) et des structures de données traditionnelles.

En particulier, un système est décrit uniquement sous la forme d'un terme : en π-calcul, il n'y a pas de différence, syntaxique ou sémantique, entre le code et les données.

Note : il existe plusieurs variantes canoniques du π-calcul. Cet article présente le π-calcul polyadique asynchrone à réplication gardée avec comparaison de noms.

Le processus le plus simple est le processus nil, noté 0. Ce terme ne fait rien – il s'agit d'un processus qui a terminé de s'exécuter.

Un terme plus compliqué est l'émission (asynchrone) d'un message : le processus ${\displaystyle a\langle b\rangle }$ émet sur le canal a l'information b. L'émission est asynchrone au sens où le processus n'attend pas de réponse et continue son exécution même si aucun processus n'a reçu l'information. Comme il est très facile d'écrire une macro pour la communication synchrone à partir de cette primitive de communication asynchrone, il ne s'agit pas d'une limitation.

La réception d'un message se note ${\displaystyle a(x).P}$ et se comporte de la manière suivante : si un processus de la forme ${\displaystyle a\langle b\rangle }$ est présent, il y a communication entre les processus. Le processus récepteur continue alors sous la forme ${\displaystyle P\{x\leftarrow b\}}$, c'est-à-dire comme le processus P dans lequel le nom x représente le message b. Ceci est similaire à un appel de fonction dans un langage traditionnel. Les différences principales sont les suivantes :

• s'il n'existe aucun processus récepteur sur le canal a, émettre sur le canal a ne constitue pas une erreur -- le message est simplement mis en attente jusqu'à ce qu'un récepteur soit prêt à écouter sur le canal a
• il peut y avoir plusieurs processus récepteurs prêts à écouter sur le canal a à un moment donné -- en cas de communication, l'un d'entre eux est choisi arbitrairement (dans le π-calcul, ceci peut servir à modéliser plusieurs agents prêts à fournir le même service)
• la fonction est « effacée » après avoir été appelée et ne renvoie jamais de valeur -- à ce sens, la communication ressemble plus à un goto avec paramètres ou à un join avec paramètres qu'à un appel de fonction proprement dit.

Si P et Q sont deux processus, ${\displaystyle P|Q}$ est la composition parallèle de P et Q, qui représente le fait que P et Q sont exécutés simultanément.

Un processus peut créer un nouveau nom. Comme tous les noms, celui-ci sera a priori un canal de communication. Ainsi, le processus ${\displaystyle (\nu x)P}$ (prononcer new x P) crée un nouveau canal, qui sera désigné sous le nom x dans P. Contrairement à l'opération new x ou dans de nombreux langages, ${\displaystyle (\nu x)}$ produit une constante x. De plus, comme l'état entier du système est représenté dans la syntaxe du terme (sans mémoire), ${\displaystyle (\nu x)P}$ représente aussi le fait que x a été créé à un moment ou à un autre et que P est susceptible d'utiliser x. Par la suite de l'exécution, si ${\displaystyle (\nu x)P}$ est en parallèle avec le processus Q (ce que nous noterons ${\displaystyle (\nu x)P|Q}$) et si P communique la valeur de x à Q, le terme deviendra ${\displaystyle (\nu x)(P|Q)}$ pour représenter le fait que P et Q peuvent tous deux utiliser x.

Un processus peut tester l'égalité entre deux noms. Ainsi, si a et b représentent le même nom, ${\displaystyle {\text{if}}\ a=b\ {\text{then}}\ P\ {\text{else}}\ Q}$ réagira comme P, sinon comme Q.

La notation P + Q dénote un processus qui se comporte tout aussi bien comme P que comme Q.

Il est possible de faire référence à une infinité de copies d'un processus P par la notation !P. Cette syntaxe n'a donc pas la signification usuelle not P utilisée par la plupart des langages de programmation !

Le rôle du gestionnaire d'impression est de recevoir des requêtes d'impression, de localiser une imprimante disponible et de transmettre la requête à l'imprimante. Si aucune imprimante n'est disponible, la requête est mise en attente. Lorsqu'une imprimante a terminé un travail, elle est considérée comme de nouveau en attente.

Plus formellement, une imprimante est représentée par un canal ${\displaystyle printer_{1}}$, ${\displaystyle printer_{2}}$ … Effectuer une impression sur une imprimante ${\displaystyle printer_{i}}$ revient à envoyer un message sur ce canal composé

• du document à imprimer
• d'un canal à employer pour prévenir que l'impression est terminée (technique dite de callback, souvent employée pour la programmation asynchrone).

Pour cet exemple, la réserve d'imprimantes peut être représentée comme un ensemble de messages émis sur le canal ${\displaystyle spool}$, chacun contenant le nom d'un canal ${\displaystyle printer_{i}}$. Localiser une imprimante disponible revient donc à recevoir un nom d'imprimante sur le canal ${\displaystyle spool}$. Remettre l'imprimante dans la réserve revient à réémettre le nom de l'imprimante sur ce même canal. Pour « protéger » la réserve d'imprimante, le nom du canal ${\displaystyle spool}$ sera considéré comme local, c'est-à-dire que le gestionnaire sera préfixé par ${\displaystyle (\nu spool)}$.

Pour cet exemple, faire appel au gestionnaire d'impression consiste à envoyer un message sur le canal ${\displaystyle spooler}$, composé

• du document à imprimer
• d'un canal à employer pour prévenir que l'impression est terminée.

La réception sur ${\displaystyle spool}$ est répliquée car le service peut être invoqué un nombre arbitraire de fois.

Ainsi, le gestionnaire d'impression peut être défini par ${\displaystyle {\begin{array}{rcl}SPOOLER&=&(\nu spool)(\\&&\ \ spool\langle printer_{1}\rangle |spool\langle printer_{2}\rangle |spool\langle printer_{3}\rangle |\cdots |spool\langle printer_{n}\rangle \\&&\ \ |!spooler(task,callback).spool(p).(\nu w)(p\langle task,w\rangle |w().(callback\langle \rangle |spool\langle p\rangle ))\\&&)\end{array}}}$

Dans ce qui précède

• ${\displaystyle task\,}$ est le nom local donné au document à imprimer
• ${\displaystyle callback\,}$ est le nom local donné au canal sur lequel émettre un message pour prévenir que le gestionnaire d'impression a terminé son travail
• ${\displaystyle spool(p)\,}$ attend qu'une imprimante ${\displaystyle p}$ soit disponible
• ${\displaystyle (\nu w)\,}$ définit un canal sur lequel l'imprimante doit émettre un message pour prévenir le gestionnaire d'impression qu'elle a terminé son travail
• ${\displaystyle p\langle task,w\rangle }$ demande à l'imprimante d'imprimer le document ${\displaystyle task}$
• ${\displaystyle w()\,}$ attend que l'imprimante ait émis son message de fin de travail
• ${\displaystyle callback\langle \rangle }$ permet au gestionnaire d'impression d'émettre son message de fin de travail
• ${\displaystyle spool\langle p\rangle }$ permet de replacer ${\displaystyle p}$ dans la liste des imprimantes disponibles

Par suite, invoquer le gestionnaire d'impression consistera à placer en présence du terme précédent un terme tel que ${\displaystyle CLIENT=(\nu cb)(spooler\langle document,cb\rangle |cb().P)}$

Ce terme émet une requête d'impression et attend que la requête soit achevée pour exécuter ${\displaystyle P}$.

Note : cette section s'apparente à observer la trace d'un programme à l'aide d'un débogueur et est donc, de manière prévisible, peu lisible.

Mis en présence, le processus ${\displaystyle CLIENT}$, le processus ${\displaystyle SPOOLER}$ et un ensemble d'imprimantes ${\displaystyle PRINTERS}$ réagissent de la manière suivante :

${\displaystyle {\begin{array}{rcl}CLIENT|SPOOLER|PRINTERS&=&(\nu cb)(spooler\langle document,cb\rangle |cb().P)\\&&|(\nu spool)(\\&&\ \ spool\langle printer_{1}\rangle |spool\langle printer_{2}\rangle |spool\langle printer_{3}\rangle |\cdots |spool\langle printer_{n}\rangle \\&&\ \ |!spooler(task,callback).spool(p).(\nu w)(\\&&\ \ \ \ p\langle task,w\rangle |w().(callback\langle \rangle |spool\langle p\rangle )\\&&\ \ )\\&&)\\&&|PRINTERS\end{array}}}$

${\displaystyle {\begin{array}{rcl}CLIENT|SPOOLER|PRINTERS&\longrightarrow &(\nu cb)(\\&&\ \ cb().P|(\nu spool)(\\&&\ \ \ \ spool\langle printer_{1}\rangle |spool\langle printer_{2}\rangle |spool\langle printer_{3}\rangle |\cdots |spool\langle printer_{n}\rangle \\&&\ \ \ \ |!spooler(task,callback).spool(p).(\nu w)(p\langle task,w\rangle |w().(callback\langle \rangle |spool\langle p\rangle ))\\&&\ \ \ \ |spool(p).(\nu w)(p\langle document,w\rangle |w().(cb\langle \rangle |spool\langle p\rangle ))\\&&\ \ )\\&&)\\&&|PRINTERS\end{array}}}$

${\displaystyle {\begin{array}{rcl}CLIENT|SPOOLER|PRINTERS&\longrightarrow &(\nu cb)(\\&&\ \ cb().P|(\nu spool)(\\&&\ \ \ \ spool\langle printer_{2}\rangle |spool\langle printer_{3}\rangle |\cdots |spool\langle printer_{n}\rangle \\&&\ \ \ \ |!spooler(task,callback).spool(p).(\nu w)(p\langle task,w\rangle |w().(callback\langle \rangle |spool\langle p\rangle ))\\&&\ \ \ \ |(\nu w)(printer_{1}\langle document,w\rangle |w().(cb\langle \rangle |spool\langle printer_{1}\rangle ))\\&&\ \ )\\&&)\\&&|PRINTERS\end{array}}}$

${\displaystyle {\begin{array}{rcl}CLIENT|SPOOLER|PRINTERS&\longrightarrow ^{*}&(\nu cb)(\\&&\ \ cb().P|(\nu spool)(\\&&\ \ \ \ spool\langle printer_{2}\rangle |spool\langle printer_{3}\rangle |\cdots |spool\langle printer_{n}\rangle \\&&\ \ \ \ |!spooler(task,callback).spool(p).(\nu w)(p\langle task,w\rangle |w().(callback\langle \rangle |spool\langle p\rangle ))\\&&\ \ \ \ |cb\langle \rangle |spool\langle printer_{1}\rangle \\&&\ \ )\\&&)\\&&|PRINTERS\end{array}}}$

${\displaystyle {\begin{array}{rcl}CLIENT|SPOOLER|PRINTERS&\longrightarrow &P|(\nu spool)(\\&&\ \ spool\langle printer_{2}\rangle |spool\langle printer_{3}\rangle |\cdots |spool\langle printer_{n}\rangle \\&&\ \ |!spooler(task,callback).spool(p).(\nu w)(p\langle task,w\rangle |w().(callback\langle \rangle |spool\langle p\rangle ))\\&&\ \ |spool\langle printer_{1}\rangle \\&&)\\&&|PRINTERS\end{array}}}$

${\displaystyle {\begin{array}{rcl}CLIENT|SPOOLER|PRINTERS&\equiv &P|SPOOLER|PRINTERS\end{array}}}$

À l'aide des divers outils du π-calcul, il est possible de caractériser le gestionnaire d'impression par ses propriétés.

Tout comme les fonctions et variables dans un langage de programmation traditionnel, les canaux du π-calcul peuvent être typés afin de certifier que les messages qui transitent sur ces canaux ont toujours le même format. Dans le cas du gestionnaire d'impression :

• ${\displaystyle spooler\,}$ permet de communiquer des couples composés d'un document et d'un nom de canal sur lequel aucune information ne transite
• chaque ${\displaystyle printer_{i}\,}$ permet de communiquer des couples composés d'un document et d'un nom de canal sur lequel aucune information ne transite
• ${\displaystyle spool\,}$ permet de communiquer des noms de canaux qui respectent la même politique que ${\displaystyle printer_{i}}$
• ${\displaystyle task\,}$ est un nom de document
• ${\displaystyle callback\,}$ et ${\displaystyle w}$ sont des noms de canaux sur lesquels aucune information ne transite

Un système de types simple permet d'associer à chaque nom de canal le type des informations qui peuvent circuler sur ce canal. Une manière de noter cela est

• ${\displaystyle \Gamma \vdash callback:Channel()}$ (soit ${\displaystyle \Gamma \,}$, l'ensemble des informations de typage connues en ce point du programme, spécifie que ${\displaystyle callback\,}$ est un nom canal sur lequel aucune information ne transite)
• ${\displaystyle \Gamma \vdash spooler:Channel(Document,Channel())}$
• ${\displaystyle \Gamma \vdash printer_{i}:Channel(Document,Channel())}$
• …

Ces informations peuvent aisément être vérifiées statiquement (i.e. au cours de la compilation) par un logiciel approprié.

Tout comme les modules et les classes dans de nombreux langages de programmation introduisent des notions de méthodes et de champs publics ou privés, les canaux du π-calcul peuvent être typés afin de certifier que seuls certains agents peuvent écrire sur un canal ou que seuls certains agents peuvent lire sur un canal. Ainsi, dans le cadre du gestionnaire d'impression, on souhaitera probablement s'assurer que

• seul le gestionnaire d'impression est autorisé à recevoir des requêtes sur le canal ${\displaystyle spool}$, pour des raisons de sécurité
• pour chaque canal ${\displaystyle printer_{i}}$, seule l'imprimante correspondante est autorisée à recevoir des requêtes sur ce canal
• seuls les gestionnaires d'impression sont autorisés à émettre des requêtes sur les canaux ${\displaystyle printer_{i}}$
• le gestionnaire d'impression n'est pas autorisé à écrire sur le document
• …

Typiquement, afin d'assurer le respect de cette politique de sécurité, un système de types examinera de quelle manière les noms de ces canaux sont distribués (étape assimilable à la liaison dynamique dans les langages traditionnels).

Ainsi, les informations de type du gestionnaire d'impression pourront être complétées en ${\displaystyle \Gamma \vdash spooler:Channel(Document[read],Channel()[write])[read,write]}$. En adoptant ce type, le gestionnaire d'impression s'engage à respecter la politique suivante : ${\displaystyle spooler}$ est un canal qui permet d'émettre ou de recevoir. Sur le canal transitent deux informations : un Document, qui est un canal en lecture seule, et un canal, en écriture seule.

Note : cette garantie de sécurité, tout comme le typage public/privé/protégé/… ou interface/mise en œuvre procède d'une analyse statique. Un composant inconnu et non vérifié peut donc violer la politique de sécurité. Pour assurer que seuls des composants vérifiés sont exécutés sur une machine, il peut être nécessaire de faire appel à des techniques telles que le Code Porteur de Preuves ou/et des vérifications dynamiques de typage de code reçu de tierces parties.