Пи-исчисление

<math>\pi</math>-исчисление в теоретической информатике  — исчисление процессов, изначально разработанное Робином Милнером, Иоахимом Парровом и Дэвидом Уолкером как продолжение работы над исчислением общающихся систем. Целью <math>\pi</math>-исчисления является возможность описать параллельные вычисления, конфигурация которых может меняться на протяжении вычисления.

Неформальное определение

<math>\pi</math>-исчисление принадлежит к семейству исчислений процессов. Фактически <math>\pi</math>-исчисление как λ-исчисление настолько минимально, что не содержит примитивов, таких как числа, булевы выражения, структуры данных, переменные, функции или операторы управления потоком (например, if-then-else, while).

Конструкции процесса

Центральным для <math>\pi</math>-исчисления является понятие имени. Простота исчисления заключается в двойной роли имён, которые выступают и как каналы связи и как переменные. В исчислении доступны следующие конструкции процесса (точные определения даны в следующих секциях):

• конкуренция, обозначается <math>P \mid Q</math>, где <math>P</math> и <math>Q</math> — два процесса или потока, выполняемых конкурентно.
• связь, где
  • префикс ввода <math>c\left(x\right).P</math> — процесс, ожидающий сообщение, отправленное по каналу связи <math>c</math>, перед тем как продолжаться как <math>P</math>, привязывающий полученное имя к имени <math>x</math>. Как правило, это моделирует процесс ожидания связи из сети, или метку c, которую можно использовать с помощью операции goto c.
  • префикс вывода <math>\overline{c} \langle y \rangle.P</math> описывает, что имя <math>y</math> передаётся через канал <math>c</math>, перед тем как продолжаться как <math>P</math>. Как правило, это моделирует отправку сообщения через сеть или операцию goto c.
• репликация, обозначается <math>!\,P</math>, которая может быть рассмотрена как процесс, который может всегда создавать новую копию <math>P</math>. Как правило, эти модели или сетевой сервис или метка c, ожидающая любое число goto c операций.
• создание нового имени, обозначается <math>\left(\nu x\right)P</math>, которое может быть рассмотрено как процесс, размещающий новую константу <math>x</math> внутри <math>P</math>. Константы <math>\pi</math>-исчисления определяются только через своё имя и всегда являются каналами связи.
• ноль процесс, обозначается 0, процесс, выполнение которого завершено и остановлено.

Однако минимализм <math>\pi</math>-исчисления не позволяет писать программы в обычном смысле слова, но исчисление может легко расширяться. В частности, просто определить структуры управления (такие как рекурсия, циклы и секвенциальная композиция) и типы данных (такие как функции первого порядка, значения истинности, списки и целые числа). Кроме того, были предложены расширения <math>\pi</math>-исчисления, которые принимают во внимание распределение и криптографию с публичным ключом. Применяется <math>\pi</math>-исчисление благодаря Абади и Фурнье, внёсших эти различные дополнения на формальной основе посредством расширения <math>\pi</math>-исчисления с произвольными типами данных.

Небольшой пример

Ниже расположен пример процесса, который состоит из трёх параллельных компонент. Канал <math>x</math> известен только из двух первых компонент.

<math>

\begin{align}

    &  \begin{align}
               (\nu x) \; & ( \; \overline{x} \langle z \rangle . \; 0 \\  
                          & | \; x(y). \; \overline{y}\langle x \rangle . \; x(y). \; 0 \; ) 
       \end{align} \\

| \; & z(v) . \; \overline{v}\langle v \rangle . 0

\end{align} </math>

Первые две компоненты способны связываться через канал <math>x</math>, при этом <math>y</math> связывается с <math>z</math>. Следующий шаг процесса:

<math>

\begin{align}

 & \begin{align} 
     ( \nu x) \; ( \; & 0 \\
                 | \; & \overline{z} \langle x \rangle . \; x(y). \; 0 \; ) 
   \end{align}

 \\
 

| \; & z(v). \; \overline{v}\langle v \rangle . \; 0

\end{align} </math>

В этом примере <math>y</math> не затрагивается, потому что это определено во внутреннем объёме^{[уточнить]}. Теперь вторая и третья параллельные компоненты могут связаться через канал <math>z</math>, при этом <math>v</math> связывается через <math>x</math>. Следующий шаг процесса:

<math>

\begin{align}

(\nu x)        ( \; & 0 \\
               | \; & x(y). \; 0  \\
               | \; & \overline{x}\langle x \rangle . \; 0 \; )  

\end{align} </math>

Отрывок, характеризующий Пи-исчисление

Пьер во время проводов гостей долго оставался один с Элен в маленькой гостиной, где они сели. Он часто и прежде, в последние полтора месяца, оставался один с Элен, но никогда не говорил ей о любви. Теперь он чувствовал, что это было необходимо, но он никак не мог решиться на этот последний шаг. Ему было стыдно; ему казалось, что тут, подле Элен, он занимает чье то чужое место. Не для тебя это счастье, – говорил ему какой то внутренний голос. – Это счастье для тех, у кого нет того, что есть у тебя. Но надо было сказать что нибудь, и он заговорил. Он спросил у нее, довольна ли она нынешним вечером? Она, как и всегда, с простотой своей отвечала, что нынешние именины были для нее одними из самых приятных.
Кое кто из ближайших родных еще оставались. Они сидели в большой гостиной. Князь Василий ленивыми шагами подошел к Пьеру. Пьер встал и сказал, что уже поздно. Князь Василий строго вопросительно посмотрел на него, как будто то, что он сказал, было так странно, что нельзя было и расслышать. Но вслед за тем выражение строгости изменилось, и князь Василий дернул Пьера вниз за руку, посадил его и ласково улыбнулся.
– Ну, что, Леля? – обратился он тотчас же к дочери с тем небрежным тоном привычной нежности, который усвоивается родителями, с детства ласкающими своих детей, но который князем Василием был только угадан посредством подражания другим родителям.
И он опять обратился к Пьеру.
– Сергей Кузьмич, со всех сторон , – проговорил он, расстегивая верхнюю пуговицу жилета.
Пьер улыбнулся, но по его улыбке видно было, что он понимал, что не анекдот Сергея Кузьмича интересовал в это время князя Василия; и князь Василий понял, что Пьер понимал это. Князь Василий вдруг пробурлил что то и вышел. Пьеру показалось, что даже князь Василий был смущен. Вид смущенья этого старого светского человека тронул Пьера; он оглянулся на Элен – и она, казалось, была смущена и взглядом говорила: «что ж, вы сами виноваты».
«Надо неизбежно перешагнуть, но не могу, я не могу», думал Пьер, и заговорил опять о постороннем, о Сергее Кузьмиче, спрашивая, в чем состоял этот анекдот, так как он его не расслышал. Элен с улыбкой отвечала, что она тоже не знает.
Когда князь Василий вошел в гостиную, княгиня тихо говорила с пожилой дамой о Пьере.
– Конечно, c'est un parti tres brillant, mais le bonheur, ma chere… – Les Marieiages se font dans les cieux, [Конечно, это очень блестящая партия, но счастье, моя милая… – Браки совершаются на небесах,] – отвечала пожилая дама.
Князь Василий, как бы не слушая дам, прошел в дальний угол и сел на диван. Он закрыл глаза и как будто дремал. Голова его было упала, и он очнулся.
– Aline, – сказал он жене, – allez voir ce qu'ils font. [Алина, посмотри, что они делают.]
Княгиня подошла к двери, прошлась мимо нее с значительным, равнодушным видом и заглянула в гостиную. Пьер и Элен так же сидели и разговаривали.
– Всё то же, – отвечала она мужу.
Князь Василий нахмурился, сморщил рот на сторону, щеки его запрыгали с свойственным ему неприятным, грубым выражением; он, встряхнувшись, встал, закинул назад голову и решительными шагами, мимо дам, прошел в маленькую гостиную. Он скорыми шагами, радостно подошел к Пьеру. Лицо князя было так необыкновенно торжественно, что Пьер испуганно встал, увидав его.
– Слава Богу! – сказал он. – Жена мне всё сказала! – Он обнял одной рукой Пьера, другой – дочь. – Друг мой Леля! Я очень, очень рад. – Голос его задрожал. – Я любил твоего отца… и она будет тебе хорошая жена… Бог да благословит вас!…
Он обнял дочь, потом опять Пьера и поцеловал его дурно пахучим ртом. Слезы, действительно, омочили его щеки.
– Княгиня, иди же сюда, – прокричал он.
Княгиня вышла и заплакала тоже. Пожилая дама тоже утиралась платком. Пьера целовали, и он несколько раз целовал руку прекрасной Элен. Через несколько времени их опять оставили одних.
«Всё это так должно было быть и не могло быть иначе, – думал Пьер, – поэтому нечего спрашивать, хорошо ли это или дурно? Хорошо, потому что определенно, и нет прежнего мучительного сомнения». Пьер молча держал руку своей невесты и смотрел на ее поднимающуюся и опускающуюся прекрасную грудь.