Pi-calcul

Les entités du π-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.

Les constructions du π-calcul

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

Informellement

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.

Formellement

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}$.

Exécution du gestionnaire d'impression

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}}}$

Propriétés du gestionnaire d'impression

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

Gestion des ressources

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Équivalence avec un autre gestionnaire d'impression

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?