PROLOG
é uma linguagem de programação sequencial, projetada
para funcionar eficientemente em uma máquina de von Neumann explorando
sua abilidade de executar a gerência eficiente da pilha. PROLOG sequencial
pode ser paralelizado, e muita pesquisa é devotada às maneiras
eficazes de fazer isso [Crammond 1985; Lusk et al.1988; Baron et al.1988;
Warren 1987 ]. Não obstante, PROLOG, se executado sequencialmente
ou paralelamente, não deve ser denominado uma linguagem de programação
concorrente. Para compreender porque PROLOG e outras linguagens sequenciais
paralelizáveis não podem ser denominados linguagens concorrentes,
é útil distinguir entre dois tipos de sistemas ou de programas:
transformacional e reativo [Harel e Pnueli 1985]. A distinção
é próxima à distinção entre sistemas
fechados e abertos [Hewitt 1985]. Um sistema (fechado) transformacional
recebeu uma entrada no começo de sua operação e rende
uma saída em sua extremidade. Por outro lado, a finalidade de um
sistema (aberto) reativo não é necessariamente obter um resultado
final, mas manter alguma interação com seu ambiente. Alguns
sistemas reativos, tais como sistemas operacionais, sistemas de gerência
da base de dados, etc., idealmente nunca terminam e neste sentido não
rendem um resultado final. Todas as linguagens sequenciais clássicas
em geral, e PROLOG no detalhe, foram projetados com a visão transformacional
na mente. Estas linguagens contêm algumas potencialidades interativas
básicas de E/S, mas geralmente estas potencialidades não
são um componente integrado da linguagem e às vezes, como
em PROLOG, são divorciados completamente de seu modelo básico
da computação.
Pode-se parecer
que a distinção entre sistemas transformacionais e os reativos
não estão relacionados diretamente aos sistemas concorrentes,
e talvez poderia haver uns sistemas transformacionais concorrentes assim
como reativos concorrentes. Certamente, há os sistemas concorrentes
que exploram o paralelismo e conseguem o desempenho elevado nas aplicações
que são transformacionais de natureza, tal como a solução
de problemas numéricos grandes. Depois de Harel[1987], nós
chamamos os sistemas concorrentes que são transformacionais de sistemas
paralelos. Entretanto, se nós investigarmos os componentes de qualquer
sistema concorrente, se transformacional ou reativo, nós encontramos
estes componentes sendo reativos; eles mantêm a interação
contínua mínima com os outros componentes e se possivel também
com o ambiente.
Daqui, parece
haver um aspecto comum a todos os sistemas ou algoritmos concorrentes,
independentemente de que sua arquitetura é do alvo de se explorar
a simultaneidade para conseguir um desempenho mais elevado, a distribuição
física, ou a interação melhor com seu ambiente. O
aspecto comum é que uma linguagem que os descreva e os implementa
precisa especificar os processos reativos - a criação, interconexão,
comportamento interno, comunicação e sincronização
deles.
Muitos
modelos computacionais abstratos são não determinísticos,
incluindo máquinas não deterministica de Turing, autômatos
finitos não deterministicos, e programas lógicos. Os sistemas
reativos são também não deterministicos. Entretanto,
a natureza do não determinismo anterior é muito diferente
dessa empregada por último. Kowalski [1979] adequadamente denominou
o não determinismo de dois tipos, o primeiro tipo não determinismo
don't-know, e o segundo tipo não determinismo don't-care. O não
determinismo do don't-care é chamado frequentemente de indeterminismo.
A interpretação
não determinística don't-know implica que o programador não
precisa saber qual das escolhas especificas no programa é correto;
é de responsabilidade da execução do programa escolher
corretamente quando diversas transições são permitidas.
Formalmente, isto é alcançado especificando resultados somente
de computações com sucesso. Os exemplos de tais resultados
são o conjunto de strings aceitas por um autômato finito não
determinístico, ou os pares de respostas das substituições
das computações bem sucedidas de um programa lógico.
O não
determinismo don't-know é uma ferramenta muito conveniente para
especificar sistemas fechados transformacionais, como testemunhado pela
linguagem PROLOG. Entretanto, parece ser incompatível com sistemas
reativos abertos. A essência do não determinismo don't-know
é que as computações de falha "não contam"
e somente as computações bem sucedidas podem produzir resultados
observáveis. Entretanto, não é possível, em
geral, saber adiantado se uma computação sucederá
ou falhará; daqui, uma computação não determinística
don't-know não pode produzir uma saída parcial antes que
termine, com isso, não pode ser reativa (Um documento relatado com
uma similar conclusão é dada em Ueda [1989]).
A interpretação
do não determinismo don't-care, por outro lado, requer que os resultados
de computações falhas sejam observáveis. Daqui, uma
computação do não determinismo don't-care pode produzir
uma saída parcial (substituições parciais da resposta,
no exemplo de programas lógicos concorrentes) ainda que não
saiba se a computação eventualmente secederá ou falhará.
O não
determinismo do don't-care parece ser desnecessário, torna-se às
vezes um incômodo, na especificação de sistemas transformacionais,
mas é essencial na especificação de sistemas reativos
concorrentes.
Embora o não
determinismo de modelos computacionais abstratos seja interpretado geralmente
como não determinismo don't-know, tais modelos estão também
abertos à interpretação do don't-care. Por exemplo,
os autômatos finitos não deterministicos podem ser usados
para especificar linguagens formais [Hopcroft e Ulman 1979] (não
determinismo don't-know) ou sistemas reativos de estado-finito [Manna e
Pnueli 1988] (não determinismo don't-care). O modelo de programação
lógica está também aberto a estas duas interpretações.
PROLOG faz exame da interpretação don't-know, uma vez que
linguagem lógica concorrente, sendo um equipamento especifico de
sistemas abertos reativos, tomam a interpretação do don't-care.
Formalmente,
as duas interpretações do não determinismo induzem
noções diferentes da equivalência do conjunto de programas.
Suponha alguma noção de equivalência de duas (ou falhando
ou sucedendo) computações. Por exemplo, em programas lógicos
duas computações com o mesmo objetivo inicial são
equivalentes se tiverem a mesma substituição da resposta
e a mesma modo de término. Sob a interpretação don't-know,
dois programas são equivalentes se tiverem computações
equivalentes, se bem sucedido ou não.
Nós
enfatizamos que as linguagens lógicas concorrentes não são
originais em adotar a interpretação do não determinismo
don't-care. Preferivelmente, quase todos os modelos concorrentes e de linguagens
de programação concorrentes, incluindo CSP [Hoare 1978,1985],
CCS [Milner 1980], UNITY [Chandy e Misra 1988], Occam [INMOS Ltd. 1984
], Ada, e outros, fazem exame desta aproximação também.
A diferença é que as linguagens lógicas concorrentes
têm como um antepassado um modelo computacional não determinístico
abstrato a - o programa lógico - cujo não determinismo pode
ser interpretado como don't-know e como don't-care. Os outros modelos e
linguagens concurrentes não relacionaram modelos ou as linguagens
que incorporam o não determinismo don't-know.
Um sentido
ativo da pesquisa na programação da lógica explora
as linguagens (não reativas) paralelas que incorporam ambos não
determinismo don't-know e o don't-care [Yang 1986; Yang e Aiso 1986; Saraswat
1985, 1987b, 1987c, 1989; Haridi e Brand 1988; Bahgat e Gregory 1989; Takeuchi
et al.1987 ]. O objetivo destas linguagens é executar mais eficientemente
programas lógicos explorando o determinismo, um controle mais sofisticado,
e um paralelismo.
As linguagens lógicas concorrentes são linguagens lógicas de programação que podem especificar sistemas abertos reativos e assim podem ser usadas para executar sistemas concorrentes e algoritmos paralelos. Um programa lógico cocncorrente é um programa lógico com não-deterministico don't-care aumentado com sincronização. Um programa lógico aumentado assim pode realizar as noções básicas da concorrência: processos, comunicação, sincronização, e indeterminismo. A leitura de processos de programas lógicos [van Emden e de Lucena 1982 ], empregada por programas lógicos concorrentes é diferente da leitura processual empregada por PROLOG. Na leitura de processos de programas lógicos, cada átomo p(Ti...Tn) é visto como um processo, cujo o estado do programa ("contador programa") sejam o predicado p/n e o estado dos dados ( "registrador de processos") é a seqüência de termos Ti,..., Tn. O objetivo ao todo é visto como uma rede de processos concorrentes, cujo o teste padrão do processo da interconexão é especificado pelas variáveis lógicas compartilhadas entre átomos do objetivo. Os processos comunicam-se instanciando variáveis lógicas compartilhadas e sincronizam-se esperando variáveis lógicas para serem instanciadas. Esta vista é sumariada na tabela 2.
Os comportamentos possíveis de um processo são especificados pelas cláusulas de Horn que têm a seguinte forma:
Cabeça :- Guarda | Corpo.
Uma cláusula guardada de Horn é similar a uma alternativa em um comando guardado [Dijkstra 1985]. A cabeça e o guarda especificam as circunstâncias sob qual a transição de reduzir pode usar a cláusula, assim como o efeito da transição no estado resultante. Isto é explicado mais abaixo. O corpo especifica o estado do processo após ter feito exame da transição: Um processo pode parar (corpo vazio), mudar o estado (corpo unitário), ou transformar-se em diversos processos concorrentes (um corpo conjunto). Isto é sumariado na tabela 3.
As
linguagens lógicas concorrentes empregam a interpretação
do não determinismo don't-care. Intuitivamente, isto significa que
uma vez que uma transição foi feita a computação
é realizada e não pode realizar backtrack ou explorar na
paralela outras alternativas. Formalmente, isto é realizado fazendo
observações de resultados parciais da computação,
assim como os resultados finais de sucessos, falhas e deadlocks [Gerth
et al. 1988; Gaifman et al. 1989].
A cabeça
e o guarda de uma cláusula especificam circunstâncias em usar
a cláusula para a redução. Uma cláusula pode
ser usada para reduzir um átomo do objetivo se somente se as circunstâncias
specificadas na cabeça e no guarda são satisfeitas pelo átomo.
As linguagens lógicas concorrentes diferem em o que pode ser especificado
pela cabeça e pelo protetor. Uma linguagem lógica concorrente
"flat" incorpora um jogo de predicados primitivos; nas linguagens
examinadas, estes incluem predicados principalmente da igualdade, da desigualdade
e da aritmética. Um guarda em linguagens "flat"consiste
na seqüência (possivelmente vazio) de átomos destes predicados.
Em uma linguagem não "flat", por outro lado, o guarda
pode conter predicados primitivos e definidos, e assim, as computações
do guarda podem ser arbitrariamente complexas. Desde que os guardas de
uma linguagem não "flat" são definidos recursivamentes
por cláusulas, uma computação dela da forma a uma
árvore And/Or dos processos é uma coleção "flat";
daqui, seu nome. As linguagens "flat" receberam a maioria da
atenção recente dos investigadores, porque se encontrou que
sua simplicidade e acessibilidade para execução eficiente
vêm em um custo relativamente baixo quanto a expressividade e a conveniência,
quando comparado às linguagens não "flat".
Os processos
concorrentes comunicam-se instanciando variáveis lógicas
compartilhadas e sincronizam-se esperando variáveis para serem instanciadas.
A instanciação da variável é realizada na maioria
das linguagens lógicas concorrentes pela unificação.
Três aproximações foram propostas à especificação
da sincronização na programação lógica
concorrente: input matching (chamado também unificação
de entrada, unificação de sentido único, ou apenas
combinação) [Clark e Gregory 1981, 1986; Ueda 1986b], unificação
read-only [Shapiro 1983b], e condições determinadas [Yang
e Aiso 1986]. Todos compartilham do mesmo princípio geral: A redução
de um átomo do objetivo com uma cláusula pode ser suspensa
até que os argumentos do átomo estejam instanciados mais
adiante. Uma vez que o átomo está instanciado suficientemente
a redução pode tornar-se ativada ou terminalmente desativada,
dependendo das circunstâncias especificadas pela cabeça e
guarda. Visto que o input matching é o mecanismo mais simples e
o mais útil da sincronização, nós apresentamo-lo
aqui. Combinar um átomo A do objetivo com uma cabeça da cláusula
A' :-- G | B sucede se A for um exemplo de A'; em tal caso, retorna a substituição
mais geral "q" tais que A = A'q. Falha se o átomo do objetivo
e a cabeça não forem unificáveis. Se não, suspende.
Mais precisamente,
match(A, A') = q, se o q for a substituição
mais-geral tais que A = A'q,
falha,
se mgu(A, A')=fail,
suspende
de outra maneira.
Ao contrário da unificação, há somente uma substituição mais geral. Usando matching para reduzir um objetivo com uma cláusula atrasa a redução até que o objetivo esteja instanciado suficientemente, de modo que sua unificação com a cabeça da cláusula possa ser completa sem variáveis instanciadas do objetivo. Os exemplos são dados na tabela 4.
A natureza do fluxo de dados de matching é evidente: Uma "instrução" (cláusula) está ativada assim que "dados" suficientes (variáveis instanciadas) cheguem. Embora simples, matching é considerado na prática suficientemente poderoso para tudo. As linguagens na família de programação lógica concorrente diferem principalmente nas potencialidades de seu mecanismo de saída. Em um lado do spectrum, há as linguagens que reservam somente matching antes da seleção da cláusula e executam a unificação após a seleção da cláusula. Na outra extremidade, há as linguagens que reservam matching e unificação como testes antes de tal compromisso. O teste de unificação na sua forma mais geral assume os mecanismos poderosos da sincronização usados nos modelos mais convencionais tais como "multiple simultaneous test-and-set" e "CSP-like output guards".
Será ilustrado os vários aspectos da programação lógica concorrente discutidos nas seções seguintes, usando uma linguagem lógica concorrente simples, FCP ( | ), (lê-se FCP-comit).
Definições: -Predicados de teste de guarda: Nós assumimos um conjunto finito fixo para predicados de teste de guarda, incluindo integer(X), X<Y, X=Y, e X<>Y.
-Cláusula guardada: Uma cláusula guardada é uma fórmula da forma: A :- G1,..., Gm | B1, ..., Bn , m, n >=0, onde A, G1 ,...Gm, e B1,.., Bn são átomos, cada predicado Gi, i=1,...,m, são predicados de teste de guarda, e as variáveis Gi ocorrem em A. Se a guarda é vazia (m=0), então o operador de commit "|" é omitido. Um corpo vazio (n=0) é denotado por true.
-Programa FCP( | ): Um programa FCP ( | ) é uma sequência finita de cláusulas guardadas, que contém a cláusula X=X como a única cláusula com predicado cabeça "=".
Note que "=" é um predicado primitivo em FCP ( | ) que não pode ser redefinido pelo programa.
Vamos mostrar um exemplo simples de programa lógico concorrentes, escritos em FCP ( | ), e o programa correspondente em programação lógica. A seguir definimos um programa lógico concorrente sum(Xs, S), que unifica S com a soma dos elementos do fluxo de entrada Xs:
Em FCP:
sum (Xs,S) :- sum' (Xs, 0, S).
sum' ([ ], P, S) :- P=S.
sum' ([X|Xs], P, S) :- plus(X, P, P'), sum' (Xs, P', S).
plus(0,0,X) :- X=0.
plus(0,1,X) :- X=1.
plus(1,0,X) :- X=1.
plus(2,0,X) :- X=2.
plus(2,1,X) :- X=3.
plus(2,2,X) :- X=4.
Em Prolog:
sum (Xs,S) :- sum' (Xs, 0, S).
sum' ([ ], S, S).
sum' ([X|Xs], P, S) :- plus(X, P, P'), sum'(Xs, P', S).
plus(0,0,0).
plus(0,1,1).
plus(1,0,1).
plus(2,0,2).
plus(2,1,3).
plus(2,2,4).
Podemos observar duas diferenças entre os dois programas. A primeira está na base da cláusula sum', onde a unificação da soma parcial P com a resposta S é explicitada no corpo. Isto é necessário porque em FCP ( | ) o objetivo é combinado (matching) com a cabeça da cláusula, não unificada com ela, isso porque se a unificação não fosse a correta não é possível fazer backtracking. A segunda é na definição de plus que é modificada para refletir a direção da computação. Note também que cada cláusula tem o operador commit "|" implícito, que é omitido por convenção da sintaxe, pois a guarda é vazia. Em contraste com Prolog, o programa em linguagem concorrente tem somente computações com sucesso no objetivo inicial sum(Xs,S), onde Xs é uma lista de inteiros e S é uma variável.
Aqui examinaremos a conduta dos programas FCP ( | ) via exemplos e ilustraremos as básicas técnicas de programação lógica concorrente.
Um processo produtor p(X), que unifica X com "a" e pára, pode ser definido usando uma simples cláusula programa:
p(X) :- X=a .
Um consumidor c(X) que espera até X ser "a" e então pára é definido como:
c(a).
O progresso da computação do escritor e do leitor conectados pela variável X é (considerando que os objetivos são reduzidos da esquerda para a direita):
<p(X), c(X); e > ..........reduce(1,1)
<X=a, c(X); e >............reduce(1,=)
<c(a); {X -> a}>..........reduce(2,2)
<true; {X -> a}>.
O estado final é um estado de sucesso, e isso é a única computação possível a partir do estado inicial. Muitos consumidores podem consumir o mesmo valor, dando o efeito de transmissão. A computação com estado inicial
<p(X), c(X), c(X),..., c(X); e>,
reduz p(X), unifica X=a, e então reduz todos os objetivos c(a) um por um.
Um processo p2(X) que não deterministicamente escolhe para unificar X com "a" ou com "b" é definido como:
P2(X) :- X= a.
P2(X) :- X= b.
Há duas possíveis computações se nós usarmos o escritor p2 em vez de p do exemplo anterior: uma com sucesso, identica a anterior, e uma com falha.
<p2(X), c(X); e >.....reduce(1,2)
<X=b, c(X); e >.......reduce(1,=)
<c(b); {X -> b}>.......Fail(1)
<fail; {X -> b}>.
Em vez de c(X), nós usaremos um leitor não-determinístico c2(X), que aceita tanto "a" ou "b" como valores de X,
c2(a).
c2(b).
então em vez da última computação
falhar, ela procede e termina com sucesso.
O processo
c2(X) tem duas alternativas. Onde uma é tomada completamente pelo
ambiente. p2(X) também tem duas alternativas. Porém o ambiente
não tem efeito nas escolhas. Um exemplo intermediário é
o processo cp(X, Y, Z), que funciona assim: se X=a, então unifica
Z com a. Se Y=b, então unifica Z com b. Se ambos X=a e Y=b, então
não deterministicamente escolhe uma das duas
cp(a, Y, Z) :- Z=a.
cp(X, b, Z) :- Z=b.
Começando do estado inicial : <p2(X), p2(Y), cp(X,Y,Z); e>, há muitas possíveis computações, dependendo da escolha do objetivo e da cláusula. Então há cinco possíveis computações. Três das quatro escolhas dos dois processos p2 unicamente determina o comportamento de cp(X, Y, Z). Por exemplo, se p2(X) unifica X=a e p2(Y) unifica Y=a, então cp precisa unificar Z=a. Se X=b e Y=a, então cp falha e a computação falha. De qualquer modo, se p2(X) escolhe X=a e p2(Y) escolhe Y=b, então cp tem uma escolha: pode reduzir com a primeira cláusula e unificar Z=a, ou com a segunda e unificar Z=b. Ambas computações são possíveis.
Assumimos
um processo X : = E, que avalia a expressão aritmética E
e unifica X com este valor. (isto pode ser definido em FCP( | ) usando
os mais primitivos processos aritméticos, como em "plus"
mostrado anteriormente). Um processo integers(From, To, Xs), que, pega
inteiros From e To, produz a sequência [From, From+1, ..., To], pode
ser definido assim:
% integers(From, To, Ns) <= Ns é
a lista dos inteiros de From até To.
integers (From, To, Ns) :- From > To | Ns =
[].
integers (From, To, Ns) :- From =< To | Ns = [From!Ns'],
From'
: = From+1,
integers
(From', To, Ns').
Um
produtor de fluxo mais interessante é fib (N, Ns), que produz os
elementos da série de Fibonacci menor ou igual a N.
% fib(N, Ns) <= Ns é a série
de Fibonacci menor ou igual que N.
fib (N, Ns) :- fib' (N, 0, 1, Ns).
fib' (N, N1, N2, Ns) :- N < N1 | Ns = [].
fib' (N, N1, N2, Ns) :- N >= N1 | Ns = [N1 | Ns'],
N3
: = N1+N2,
fib'
(N, N2, N3, Ns').
É
um processo que soma os elementos de uma sequência de entrada. O
processo a seguir lê dois vetores de tamanhos iguais, representados
pela sequência de números, e calcula o produto entre eles.
% ip (Xs, Ys, S) <= S é o
produto interno de Xs e Ys.
ip (Xs, Ys, S) :- ip1 (Xs, Ys, 0, S).
ip1 ([ ], [ ], P, S) :- P = S.
ip1 ([X | Xs], [Y | Ys], P, S) :- P' : = P + X * Y, ip1(Xs, Ys, P', S).
O
processo seguinte multiplica a sequência de entrada por algum inteiro,
para produzir a sequência de saída.
% multiply (In, , N, Out) <= Out
é a sequência resultante da multiplicação de
cada elemento da sequência In por N.
multiply ([ ], N, Out) :- Out = [ ].
multiply ([X | In], N, Out) :- Out = [Y | Out'],
Y
: = X*N,
multiply
(In, N, Out').
O distribuidor
de fluxo seguinte tem um fluxo de entrada e dois fluxos de saída.
Se uma mensagem de entrada send(1, X) é recebida, X é enviado
para o primeiro fluxo de saída, e se send(2, X) é recebida,
X é enviado para o segundo fluxo de saída.
% distribute (In, Out1, Out2) <=
In é uma sequência de elementos da forma send(1,_) e send(2,_).
Out1 é uma sequência de Xs que vem de send(1,X) de In, e Out2
é uma sequência de Xs que vêm de send(2,_) de In.
distribute ([send(1,X) | In], Out1, Out2) :- Out1
= [X | Out1'],
distribute
(In, Out1', Out2).
distribute ([send(2,X) ! In], Out1, Out2) :- Out2 = [X | Out2'],
distribute
(In, Out1, Out2').
distribute ([ ], Out1, Out2) :- Out1 = [ ],
Out2
= [ ].
O
processo adiante recebe duas sequências ordenadas de inteiros e produz
uma união das sequências, tamém ordenada.
% Omerge (In1, In2, Out) <= Se In1
e In2 são sequências ordenadas de números, então
Out é a união ordenada de In1 e In2.
Omerge ([X | In1], [Y | In2], Out) :- X =<
Y | Out = [X ! Out'],
Omerge
(In1, [Y | In2], Out').
Omerge ([X | In1], [Y | In2], Out) :- X > Y | Out = [Y ! Out'],
Omerge
([X | In1], In2, Out').
Omerge ([ ], In2, Out) :- In2 = Out.
Omerge (In1, [ ], Out) :- In1 = Out.
Vamos comparar as linguagens P-Prolog, Prolog Concorrente, Parlog e GHC, todas concorrentes. As diferenças das três últimas linguagens para a primeira estão sublinhadas.
quicksort( Unsorted, Sorted ) :- qsort ( Unsorted,
Sorted, [ ] ).
qsort ( [ X | Unsorted] , Sorted, Rest) :- partition ( Unsorted, X, Smaller,
Larger ),
qsort
( Smaller, Sorted, [X | Sorted1] ),
qsort
( Larger, Sorted1, Rest).
qsort ( [ ], Rest, Rest).
partition ( [X | Xs], A, Smaller, [X | Larger]) :- A<X : partition(
Xs, A, Smaller, Larger).
partition ( [X | Xs], A, [X | Smaller], Larger) :- A>=X : partition(
Xs, A, Smaller, Larger).
partition ( [ ], _ , [ ], [ ]).
quicksort( Unsorted, Sorted ) :- qsort ( Unsorted,
Sorted, [ ] ).
qsort ( [ X | Unsorted] , Sorted, Rest) :- partition ( Unsorted?,
X, Smaller, Larger ),
qsort
( Smaller?, Sorted, [X | Sorted1] ),
qsort
( Larger?, Sorted1, Rest).
qsort ( [ ], Rest, Rest).
partition ( [X | Xs], A, Smaller, [X | Larger]) :- A<X : partition(
Xs?, A, Smaller, Larger).
partition ( [X | Xs], A, [X | Smaller], Larger) :- A>=X : partition(
Xs?, A, Smaller, Larger).
partition ( [ ], _ , [ ], [ ]).
mode quicksort ( ?, ^).
mode quicksort ( ?, ^, ^).
mode partition ( ?, ?, ^, ^).
quicksort( Unsorted, Sorted ) :- qsort ( Unsorted,
Sorted, [ ] ).
qsort ( [ X | Unsorted] , Sorted, Rest) :- partition ( Unsorted, X, Smaller,
Larger ),
qsort
( Smaller, Sorted, [X | Sorted1] ),
qsort
( Larger, Sorted1, Rest).
qsort ( [ ], Rest, Rest).
partition ( [X | Xs], A, Smaller, [X | Larger]) :- A<X : partition(
Xs, A, Smaller, Larger).
partition ( [X | Xs], A, [X | Smaller], Larger) :- A>=X : partition(
Xs, A, Smaller, Larger).
partition ( [ ], _ , [ ], [ ]).
quicksort( Unsorted, Sorted ) :- true :
qsort ( Unsorted, Sorted, [ ] ).
qsort ( [ X | Unsorted] , Sorted, Rest) :- true : partition ( Unsorted,
X, Smaller, Larger ),
qsort
( Smaller, Sorted, [X | Sorted1] ),
qsort
( Larger, Sorted1, Rest).
qsort ( [ ], Rest0, Rest1) :- true : Rest0 = Rest1.
partition ( [X | Xs], A, Smaller, Larger) :- A<X : Larger = [ X |
L1 ], partition( Xs, A, Smaller, L1).
partition ( [X | Xs], A, Smaller, Larger) :- A>=X : Smaller = [ X
| L1], partition( Xs, A, S1,Larger).
partition ( [ ], _ , Smaller, Larger) :- true : Smaller = [ ], Larger
= [ ].
Podemos observar que P-Prolog é bem mais simples que as outras três. Em Prolog Concorrente temos que saber quais variáveis são read-only. Em PARLOG temos que adicionar uma declaração de modo para cada predicado. Em GHC precisamos evitar que as variáveis do objetivo unifiquem com qualquer instância antes de passar pelo commit. Em P-Prolog, exceto pela substituição do operador commit ':' pelo operador de corte '!', o programa é exatamente o mesmo se escrito em programação lógica sequêncial (PROLOG).
Podemos concluir que operacionalmente, o modelo da computação lógica concorrente consiste em um jogo dinâmico de processos concorrentes, que se comunicam instanciando as variáveis lógicas compartilhadas, sincronizando esperando variáveis para serem instanciadas, e fazendo as escolhas não-deterministicas, baseadas na possibilidade da avaliação dos valores das variáveis. As linguagens lógicas concorrentes são as linguagens de programação de alto-nível para sistemas paralelos e distribuídos que oferecem uma escala larga de conhecimento e da nova técnica de programação concorrente. Sendo linguagens de programação lógica, preservam muitas vantagens do modelo de programação lógica abstrata, incluindo a leitura lógica dos programas e das computações, da conveniência de representar estruturas de dados com os termos lógicos e de manipulá-los através da unificação, e da acessibilidade a meta-programação. Além disso, sendo concorrente, essas linguagens são aplicadas para um melhor e mais rápido processamento.
Referências Utilizadas:
- @Article{Shap89,
Author
= "Shapiro, Ehud",
Title
= "The Family of {Concurrent} {Logic} {Programming} {Languages}",
Journal
= "{ACM} computing surveys",
Publisher
= "{ACM} PRESS",
Year
= "1989",
Number
= "3",
Volume
= "21",
Pages
= "412--510" }
- @Inproceedings{Yang86,
Author
= "Yang, Rong and Aiso, Hideo",
Title
= "{P-Prolog: a Parallel Logic Language Based on Exclusive Relation}",
Booktitle
= "Third International Conference on Logic Programming, London",
Month
={July},
Year
= "1986",
Editor
= "Shapiro, Ehud",
Pages
= "255--269",
Publisher
= "Springer-Verlag" }
- @Book{Yang87,
Author
= "Yang, Rong",
Title
= "{P-Prolog a Parallel Logic Programming Language}",
Publisher
= "World Scientific, Singapore",
Note
= "{Series in Computer Science}",
Volume
= "9",
Year
= "1987" }