Cálculo de processos

Em ciência da computação, cálculo de processos (process calculus) é uma família diversificada de abordagens para modelar formalmente sistemas concorrentes. O cálculo de processos provê uma ferramenta de descrição de alto nível de interações, comunicações e sincronizações entre uma coleção de agentes ou processos independentes. Eles também fornecem leis algébricas que permitem descrições de processos serem manipuladas e analisadas, e permitem a formalização do raciocínio sobre equivalências entre processos (e.g. usando bisimulação). Principais exemplos de cálculo de processos incluem CSP, CCS, ACP, e LOTOS. Adições mais recentes incluíram o π-calculus, o cálculo de ambiente, PEPA, o cálculo de fusão e o join-calculus.

Características essenciais

Embora a variedade de cálculo de processos existentes seja muito grande (incluindo variantes que incorporam o comportamento estocástico, informações de tempo, e especializações para o estudo de interações moleculares), existem vários recursos que todos os cálculos de processos tem em comum:

• Representam interações entre processos independentes como comunicação (transmissão de mensagens).
• Descrevem processos e sistemas usando uma pequena coleção de primitivas, e operadores para combiná-las.
• Definem leis algébricas para operadores do processo, que permitem que as expressões sejam manipuladas usando raciocínio equacional.

Matemática dos processos

Para definir um processo, primeiro se começa com um conjunto de nomes (ou canais), cujo objetivo é prover meios de comunicação. Em várias implementações, canais tem uma estrutura interna rica para melhorar a eficiência, mas isso é abstraído na maioria dos modelos teóricos. Além dos nomes são necessários meios para formar novos processos a partir dos antigos. Os operadores básicos, sempre presentes de uma forma ou de outra, permitem:

• Composição paralela de processos
• Especificação de qual canal usar para enviar e receber dados
• Definir a sequência de interações
• Omissão de pontos de interação
• Recursão ou replicação de processo.

Composição paralela

Composição paralela de dois processos ${\mathit {P}}$ e ${\mathit {Q}}$, usualmente dada como $P\vert Q$, é a chave para distinguir o cálculo de processos de modelos sequenciais de computação. Composição paralela permite a computação em ${\mathit {P}}$ e ${\mathit {Q}}$ proceder independente e simultaneamente. Mas isso também permite interação, isto é sincronização e fluxo de informação de ${\mathit {P}}$ para ${\mathit {Q}}$ (e vice versa) em um canal compartilhado pelos dois. Crucialmente, um agente ou processo pode ser conectado a mais de um canal por vez.

Canais podem ser síncronos ou assíncronos. No caso de um canal síncrono, o agente que envia a mensagem espera até o outro agente receber. Canais assíncronos não requerem nenhuma sincronização. Em alguns processos, os próprios canais podem ser enviados em mensagens através de outros canais, permitindo que a topologia das interconexões do processo mude. Alguns processos também permitem a criação de canais durante a execução de uma computação.

Comunicação

Interação pode ser (mas não é sempre) um fluxo direto de informação. Isto é, entrada e saída podem ser distinguidas como primitivas de interação dupla. Cálculos de processo que fazem essa diferenciação tipicamente definem um operador de entrada (e.g. $x(v)$) e um operador de saída (e.g. $x\langle y\rangle$), ambos nomeiam um ponto de interação (aqui ${\mathit {x}}$) que é usado para sincronizar com uma primitiva de interação dual.

Informação deve ser trocada, o fluxo será do processo de saída para o de entrada. A primitiva de saída vai especificar os dados a serem enviados. Em $x\langle y\rangle$, esses dados são representados por $y$. Similarmente, se uma entrada espera receber dados, uma ou mais variáveis de fronteira vão agir como place-holders a serem substituídos por dados. Em $x(v)$, $v$ faz este papel. A escolha do tipo de dados que pode ser trocado em uma interação é uma das principais características de diferenciação dos cálculo de processos.

Composição sequencial

As vezes interações tem que ser temporalmente ordenadas. Por exemplo, pode ser desejável especificar algoritmos como: primeiro receba algum dado em ${\mathit {x}}$ e então envie esse dado para ${\mathit {y}}$. Composição sequencial pode ser usada para esses propósitos. A mesma é conhecida em outros modelos de computação. Em cálculo de processos, o operador de sequenciação é geralmente integrado com entrada ou saída, ou ambos. Por exemplo, o processo $x(v)\cdot P$ vai esperar por uma entrada em ${\mathit {x}}$. Só quando esta entrada chegar o processo ${\mathit {P}}$ vai ser ativado, com o dado recebido através de ${\mathit {x}}$ substituído pelo identificador ${\mathit {v}}$.

Semântica da redução

A principal regra operacional de redução, contendo a essência computacional do cálculo de processos, pode ser dada apenas em termos de composição paralela, sequenciação, entrada e saída. Os detalhes desta redução variam entre o cálculo, mas a essência permanece grosseiramente a mesma. A regra de redução é:

$x\langle y\rangle \cdot P\;\vert \;x(v)\cdot Q\longrightarrow P\;\vert \;Q[^{y}\!/\!_{v}]$

Interpretando:

1. O processo $x\langle y\rangle \cdot P$ envia uma mensagem, aqui ${\mathit {y}}$, através do canal ${\mathit {x}}$. Dualmente, o processo $x(v)\cdot Q$ recebe esta mensagem no canal ${\mathit {x}}$.
2. Uma vez que a mensagem tenha sido enviada, $x\langle y\rangle \cdot P$ se torna o processo ${\mathit {P}}$, enquanto $x(v)\cdot Q$ se torna o processo $Q[^{y}\!/\!_{v}]$, que é ${\mathit {Q}}$ com o place-holder ${\mathit {v}}$ substituído por ${\mathit {y}}$, o dado que foi recebido em ${\mathit {x}}$.

A classe dos processos que ${\mathit {P}}$ alcança como continuação da operação de saída influencia substancialmente as propriedades do cálculo.

Omissão

Processos não limitam o número de conexões que podem ser feitas em um dado ponto de interação. Mas pontos de interação permitem interferência (i.e. interação). Para a síntese de sistemas compactos, mínimos, a habilidade de restringir a interferência é crucial. Operações de omissão permitem o controle de conexões feitas entre pontos de interação quando compõem agentes em paralelo. Omitir pode ser denotado de vários modos. Por exemplo, em $\pi$-calculus a omissão de um nome ${\mathit {x}}$ em ${\mathit {P}}$ pode ser expressa como $(\nu \;x)P$, enquanto em CSP pode ser escrita como $P\setminus \{x\}$.

Recursão e replicação

As operações apresentadas até agora descrevem só interações finitas e consequentemente são insuficientes para uma computação completa, o que incluí comportamento não-terminal. Recursão e replicação são operações que permitem descrições finitas de comportamentos infinitos. Recursão é bem conhecida no mundo sequencial. Replicação $!P$ pode ser entendida como uma abreviação de uma composição paralela de um número contável infinito de ${\mathit {P}}$ processos:

$!P=P\mid !P$

Processo nulo

Cálculo de processos geralmente também incluem um processo nulo (também denotado como ${\mathit {nil}}$, $0$, ${\mathit {STOP}}$, $\delta$, ou algum outro símbolo apropriado) que não tem nenhum ponto de interação. É totalmente inativo e seu único propósito é atuar como âncora indutiva.

Álgebra de processos contínuos e discretos

Álgebra de processos tem sido estudada para tempo discreto e contínuo (tempo real ou denso).

História

Na primeira metade do século XX, vários formalismos foram propostos para capturar o conceito informal de uma função computável, com funções μ-recursivas, máquinas de Turing e cálculo lambda possivelmente sendo os melhores exemplos conhecidos hoje. O fato surpreendente de eles serem essencialmente equivalentes, no sentido de que eles são todos codificáveis uns nos outros, suporta a tese de Church-Turing. Outra característica compartilhada menos comentada: todos eles são mais prontamente entendidos como modelos de computação sequencial. A consolidação posterior da ciência da computação precisou de um formulação mais sutil da noção de computação, em particular representações explícitas de concorrência e comunicação. Modelos de concorrência como o cálculo de processos, Rede de Petri em 1962, e o modelo ator em 1973 emergiram a partir desta linha de investigação.

Pesquisas no cálculo de processos começaram a sério com o trabalho seminal de Robin Milner's sobre o cálculo de sistemas de comunicação (CCS) durante o período de 1973 a 1980. Processos de comunicação sequencial (CSP) de Charles Antony Richard Hoare apareceram em 1978, e foram então desenvolvidos em um cálculo de processos durante o início de 1980. Existiu um grande cruzamento de ideias entre CCS e CSP no seu desenvolvimento. Em 1982 Jan Bergstra e Jan Willem Klop começaram a trabalhar no que passou a ser conhecido como Álgebra de processos de comunicação (ACP), e introduziram o termo de processo de álgebra para descrever o seu trabalho. CCS, CSP e ACP constituem os três maiores ramos da família de cálculo de processos: a maioria dos outros processos podem traçar suas raízes a um destes ramos.

Pesquisa atual

Vários cálculos de processos vem sendo estudados, mas nem todos eles se encaixam no paradigma esboçado aqui. O exemplo mais proeminente pode ser o cálculo ambiente. Isto era de ser esperado já que os cálculos de processos são um campo ativo de estudo. A pesquisa corrente foca nos seguintes problemas:

• Desenvolver novos processos para melhor modelagem do fenômeno computacional.

• Encontrar subcálculos bem comportados de um dado processo. Isto é válido porque (1) a maioria dos cálculos é razoavelmente amplo no sentido de que eles são gerais e não se podem falar muito sobre processos arbitrários; e (2) aplicações computacionais raramente esgotam a totalidade de um cálculo. Ele usam apenas processos que são muito restritos em forma. Restringir a forma dos processos é principalmente estudado por meio de sistemas de tipo.

• Lógicas para processos que permitem raciocinar sobre (essencialmente) propriedades arbitrárias de processos, seguindo as ideias da lógica Hoare.

• Teoria comportamental: O que que significa dois processos serem o mesmo? Como podemos decidir se dois processos são diferentes ou não? Podemos encontrar representações para classes equivalentes de processos? Geralmente, processos são considerados ser o mesmo se nenhum contexto, que é um processo rodando em paralelo, pode detectar uma diferença. Infelizmente, fazer esta intuição ser precisa é sutil e, principalmente, produz caracterizações de igualdade (o que na maioria dos casos,também deve ser indecidível, como consequência do problema da parada). Bisimulações são ferramentas e técnicas que auxiliam o raciocínio sobre a equivalência de processos.

• A expressividade do cálculo: Experiência em programação mostra que alguns problemas são mais fáceis de resolver em certas linguagens do que em outras. Esse fenômeno necessita de uma caracterização mais precisa da expressividade do modelo computacional do cálculo do que a oferecida pela tese de Church-Turing. Um modo de fazer isso é considerar qualificações entre dois formalismos e observar que propriedades essa codificação pode preservar. Quanto mais propriedades podem ser preservadas, mais expressivo o alvo da codificação é. Para o cálculo de processos, os resultados são que os $\pi$-calculus síncronos são mais expressivos que sua variante assíncrona, tem o mesmo poder de expressividade do $\pi$-calculus de mais alta ordem, mas é menos do que o cálculo ambiente.

• Usando cálculo de processos para modelar sistemas biológicos ($\pi$-calculus estocástico, BioAmbients, Beta Binders, BioPEPA, Brane calculus). É esperado que a composicionalidade oferecida pelas ferramentas teóricas do processo podem ajudar os biólogos a organizar seu conhecimento mais formalmente.

Implementações de Software

As ideias por trás do processo algébrico tem chegado a diversas ferramentas incluindo:

• CADP [1]
• Concurrency Workbench
• mCRL2 toolset

Relacionamento com outros modelos de concorrência

A história monóide é o objeto livre que é genericamente capaz de representar as histórias de processos de comunicação individuais. Um cálculo de processos é, então, uma linguagem formal imposta em uma história monoid de uma forma consistente. Isto é, uma dessas histórias só pode gravar uma sequência de eventos, com sincronização, mas não especifica as transições de estado permitidas. Assim, um cálculo de processos é para uma dessas histórias o que uma linguagem formal é para um monóide livre (a linguagem formal é um subconjunto do conjunto de todas as possíveis seqüências de comprimento finito de um alfabeto gerado pela estrela de Kleene).

O uso de canais de comunicação é uma das características que distinguem o cálculo de processos de outros modelos de concorrência, tais como redes de Petri e o modelo Actor (ver modelo Actor e cálculo de processos). Uma das motivações fundamentais para a inclusão de canais no cálculo de processos foi permitir determinadas técnicas algébricas, tornando assim mais fácil para raciocinar sobre processos algebricamente.

Veja também

• Stochastic probe [2]

Outras leituras

• Matthew Hennessy: Algebraic Theory of Processes, The MIT Press, ISBN 0-262-08171-7.
• C. A. R. Hoare: Communicating Sequential Processes, Prentice Hall, ISBN 0-13-153289-8.
  • This book has been updated by Jim Davies at the Oxford University Computing Laboratory and the new edition is available for download as a PDF file at the Using CSP website.
• Robin Milner: A Calculus of Communicating Systems, Springer Verlag, ISBN 0-387-10235-3.
• Robin Milner: Communicating and Mobile Systems: the Pi-Calculus, Springer Verlag, ISBN 0-521-65869-1.
• Andrew Mironov: Theory of processes