π calculus

A la hora de afrontar cualquier problema lo suficientemente complicado, uno de los principales problemas a los que nos enfrentamos es el de conseguir pensar con suficiente claridad acerca del mismo. Esto implica caracterizarlo de forma adecuada, eliminando todos los elementos superfluos o subproblemas no esenciales, lo que supone casi siempre, siguiendo el ejemplo de uno mis héroes intelectuales (http://en.wikipedia.org/wiki/Wittgenstein), conseguir un lenguaje que nos permita razonar de forma exacta sobre dicho problema.

Ese lenguaje siempre es el de las matemáticas y cuando el problema tiene que ver con la computación, toma forma de cálculo, no como el cálculo diferencial, sino en la acepción que se usa en lógica: la de un sistema formal para la manipulación de expresiones simbólicas. El 'calculus' más relevante para la computación y el más conocido es el cálculo lambda de Alonzo Church y compañía, que supone la base de cualquier lenguaje de programación funcional, pero otros muchos calculi han sido construidos para el estudio de problemas concretos.

El Cálculo Pi, es uno de ellos. Pretende faciliar el estudio de procesos paralelos de computación que evolucionan dinámicamente. A pesar de lo ambicioso del objetivo, los componentes del cálculo π no podían ser más simples:

Un proceso se identifica por una letra mayúscula:

P, Q, R...

Cuando los procesos se ejecutan en paralelo el proceso se identifican por el símbolo '|':

P | Q | R

Así se expresarían tres procesos que se ejecutan paralelamente. Pero lo interesante viene cuando los procesos empiezan a comunicarse entre sí:

P = <y>x.P'

Expresa que el proceso P envía el nombre 'x' por el canal 'y' y sigue comportandose como P'.  Por el contrario:

P = y(x).P'

Indica que el proceso P espera recibir el nombre 'x' por el canal 'y' y a continuación se sigue comportando como P'. A través de los canales se pueden enlazar los procesos, por ejemplo:

<y>x.P | y(z).Q

En este ejemplo el proceso P envía por el canal 'y' el nombre 'x', el proceso Q recibe el nombre por el canal 'y' y en el contexto de Q renombra 'z' con el nombre 'x' enviado {x/z}. Si expandimos la expresión:

<y>x.P | y(z).Q -> P|Q{x/z}

Tendríamos el proceso P ejecutándose en paralelo con el proceso Q donde el nombre 'z' pasa a valer 'x'.

El calculo tiene sólo unos cuantos símbolos más: P! sería un proceso recursivo de tal forma que P! = P! | P, y una forma de expresar que un canal es privado a dos procesos.

La aportación seminal del Cálculo Pi como cálculo de procesos, es la brillante idea de tratar tanto canales como símbolos de la misma manera, como nombres que se pueden enviar por otros canales con lo que se puede "enviar el proceso" pasando canales de comunicación, si hay colisión de nombres se hace una alfa-conversión como en el cálculo lambda:

P | Q | R

<x1>y1.y1(z1) | x1(y2).<z2>y2  |  z2(x3).<x3>"hola"

Si computamos este sistema:

y1(z1) | {y1/y2}.<z2>y2 | z2(x3).<x3>"hola"

y1(z1) |  <z2>y1 | z2(x3).<x3>"hola"

y1(z1) |  0  |  {y1/x3}.<x3>"hola"

y1(z1) | 0 | <y1>"hola"

{"hola"/z1} | 0 | 0

"hola" | 0 | 0

0 | 0 |0

Podemos observar como el proceso P le ha pasado un enlace hacia si mismo a R a través de Q y R luego le ha enviado la cadena "hola" a través del enlace enviado.

Lo atractivo del Cálculo Pi es que su álgebra asociada nos permite tratar formalmente problemas de computación paralela y responder a preguntas como "¿se comportan dos sistemas de la misma manera?" lo que se conoce como el problema de bisimulación, Y problemas de computación paralela los hay muy interesantes, piénsese en el web y el envío de enlaces hacia servidores a través de documentos HTML.

servido por Antonio 3 comentarios compártelo