Concurrent restrição lógica de programação - Concurrent constraint logic programming

Concurrent lógica de programação restrição é uma versão da lógica de programação restrição destinado principalmente a programação processos concorrentes em vez de (ou além) resolvendo problema da satisfação de restrições . Gols em lógica de programação restrição são avaliadas simultaneamente; um processo simultâneo é, por conseguinte, programado como a avaliação de uma meta pelo intérprete .

Sintaticamente, restrições simultâneos programas lógicos são semelhantes a programas não-concorrentes, a única exceção sendo que as cláusulas incluem guardas , que são restrições que podem bloquear a aplicabilidade da cláusula sob algumas condições. Semanticamente, concorrente lógica de programação restrição é diferente de suas versões não-simultâneos porque uma avaliação objetivo se destina a realizar um processo simultâneo em vez de encontrar uma solução para um problema. Mais notavelmente, esta diferença afeta a forma como o intérprete se comporta quando mais de uma cláusula é aplicável: a lógica de programação restrição não concorrente de forma recursiva tenta todas as cláusulas do contrato; concorrente lógica de programação restrição escolhe apenas um. Este é o efeito mais evidente de um destinado a direcionalidade do intérprete, que nunca rever uma escolha que tomou anteriormente. Outros efeitos disso são a possibilidade semântica de ter um objetivo que não pode ser provado, enquanto toda a avaliação não falha, e uma maneira particular para equacionar uma meta e uma cabeça cláusula.

Restrição manipulação regras pode ser visto como uma forma de lógica de programação restrição concorrente, mas são usados para programar um simplificador constrangimento ou solver, em vez de processos concorrentes.

Descrição

Na lógica de programação de restrição, os objetivos do objetivo atual são avaliadas sequencialmente, geralmente proceder de um LIFO ordem em que os objetivos mais recentes são avaliadas primeiro. A versão simultânea da programação lógica permite avaliar gols em paralelo : cada gol é avaliada por um processo, e os processos executados simultaneamente. Estes processos interagem através da loja restrição: um processo pode adicionar uma restrição para a loja de restrição enquanto outro verifica se a restrição é imposta pela loja.

Adicionando uma restrição à loja é feito como em lógica de programação restrição regular. Verificando vinculação de uma restrição é feita através de guardas de cláusulas. Guardas exigem uma extensão sintática: a cláusula de lógica de programação restrição concorrente é escrito como H :- G | Bonde Gé uma restrição chamado o guarda da cláusula. Grosso modo, uma nova variante desta cláusula pode ser usado para substituir um literal no objetivo somente se o guarda está implicado pela loja restrição após a equação da literal ea cabeça cláusula é adicionado a ele. A definição precisa desta regra é mais complicado, e é dado abaixo.

A principal diferença entre a programação lógica restrição não concorrente e simultânea é que a primeira é destinada a pesquisa, enquanto o segundo visa implementar processos concorrentes. Essa diferença afeta se as escolhas podem ser desfeitas, se os processos estão autorizados a não terminar, e como os objetivos e as cabeças cláusula são equiparados.

A primeira diferença semântica entre a programação lógica restrição regular e simultânea é sobre a condição quando mais de uma cláusula pode ser usada para provar um objetivo. lógica de programação não concorrente tenta todas as cláusulas possíveis quando reescrevendo uma meta: se o objetivo não pode ser provado, enquanto substituindo-o com o corpo de uma variante fresco de uma cláusula, outra cláusula for provado, se houver. Isso ocorre porque o objetivo é provar a meta: todas as formas possíveis para provar a meta são julgados. Por outro lado, concorrente lógica de programação restrição visa processos de programação paralela. Na programação concorrente geral, se um processo faz uma escolha, esta escolha não pode ser desfeita. A versão simultânea da programação lógica restrição implementa processos, permitindo-lhes tomar decisões, mas se comprometer com eles uma vez que foram tomadas. Tecnicamente, se mais do que uma cláusula pode ser usada para reescrever um literal no gol, a versão não concorrente tenta por sua vez, todas as cláusulas, enquanto a versão concorrente escolhe uma única cláusula arbitrária: ao contrário da versão não-concorrente, as demais cláusulas nunca vai ser julgado. Estas duas formas diferentes para lidar com múltiplas escolhas são freqüentemente chamados de "não sei não determinismo" e "não se importam não-determinismo".

Ao reescrever um literal no gol, as únicas cláusulas consideradas são aqueles cuja guarda está implicado pela união da loja de restrição e a equação da literal com a cabeça cláusula. Os guardas fornecem uma maneira para dizer qual cláusulas não devem ser considerados em tudo. Isto é particularmente importante dado o compromisso com uma única cláusula da programação lógica restrição concorrente: uma vez que uma cláusula foi escolhido, esta escolha nunca será reconsiderada. Sem guardas, o intérprete poderia escolher uma cláusula de "errado" para reescrever um literal, enquanto existem outros "bons" cláusulas. Na programação não concorrente, isso é menos importante, como o intérprete sempre tenta todas as possibilidades. Na programação simultânea, o intérprete compromete a uma única possibilidade, sem tentar as outras.

Um segundo efeito da diferença entre o não concorrente e a versão simultâneo é que concomitante programação lógica restrição é especificamente concebido para permitir que os processos para executar sem que encerra. Processos não-terminais são comuns em geral no processamento concorrente; a versão simultânea da programação lógica restrição implementa-los por não usar a condição de falha: se nenhuma cláusula é aplicável para reescrever um objetivo, o processo de avaliação desta meta pára em vez de fazer toda a avaliação falhar como em lógica de programação restrição não concorrente. Como resultado, o processo de avaliação de um objetivo pode ser interrompido porque nenhuma cláusula está disponível para prosseguir, mas ao mesmo tempo os outros processos continuam em execução.

Sincronização entre os processos que estão resolvendo diferentes objetivos é conseguido através do uso de guardas. Se a meta não pode ser reescrito, porque todas as cláusulas que poderiam ser usados têm um guarda que não está vinculada pela loja restrição, o processo de resolver este objetivo é bloqueado até que os outros processos adicionar as restrições que são necessárias para implicar a guarda de pelo menos um das cláusulas aplicáveis. Esta sincronização está sujeito a bloqueios : se todas as metas são bloqueados, será adicionada sem novas restrições e, portanto, nenhuma meta nunca vai ser desbloqueado.

Um terceiro efeito da diferença entre a programação lógica concorrente e não concorrente está na forma como um objetivo é equiparada à cabeça de uma variante fresco de uma cláusula. Operacionalmente, isso é feito por verificar se as variáveis ​​na cabeça pode ser equiparado a um acordo de tal forma da cabeça é igual à meta. Esta regra diferente da regra correspondente para a programação lógica restrição na medida em que só permite a adição de restrições na variável de formulário = prazo, em que a variável é um dos cabeça. Esta limitação pode ser visto como uma forma de direccionamento, em que a meta e a cabeça cláusula são tratadas de maneira diferente.

Precisamente, a regra de dizer se uma nova variante H:-G|Bde uma cláusula pode ser usada para reescrever um objetivo Aé a seguinte. Em primeiro lugar, é verificado se Ae Htêm o mesmo predicado. Em segundo lugar, é verificado se existe uma maneira para equiparar com dada a loja restrição atual; contrário à lógica de programação regular, isso é feito sob unificação unilateral , que só permite que uma variável da cabeça para ser igual a um termo. Em terceiro lugar, o guarda está marcada para a vinculação da loja de restrição e as equações geradas na segunda etapa; o guarda pode conter variáveis que não são mencionados na cabeça cláusula: estas variáveis são interpretados existencialmente. Este método para decidir a aplicabilidade de uma variante fresco de uma cláusula para a substituição de um objetivo pode ser compacta expressa da seguinte forma: a loja restrição atual implica que existe uma avaliação das variáveis da cabeça e da guarda de modo que a cabeça é igual a o objetivo eo guarda está implicado. Na prática, vinculação pode ser verificado com um método incompleta. ${\ Displaystyle A}$${\ H} displaystyle$

Uma extensão para a sintaxe e semântica da programação lógica concorrente é o tell atômica . Quando o intérprete utiliza uma cláusula, a guarda é adicionado ao armazenamento de restrição. No entanto, também são adicionados os constrangimentos do corpo. Devido ao compromisso com esta cláusula, o intérprete não recuar se as restrições do corpo são inconsistentes com a loja. Esta condição pode ser evitado pelo uso de tell atômica, que é uma variante em que a cláusula de conter uma espécie de "segundo guarda" que só é verificada a consistência. Essa cláusula está escrito H :- G:D|B. Esta cláusula é usada para reescrever um literal somente se Gestá implicado pela loja restrição e Dé consistente com ele. Neste caso, tanto Ge Dsão adicionados à loja restrição.

História

O estudo da lógica de programação restrição concorrente começou no final da década de 1980, quando alguns dos princípios da lógica de programação simultânea foram integrados na programação lógica restrição por Michael J. Maher . As propriedades teóricas de lógica de programação restrição concorrente mais tarde foram estudados por vários autores, como Vijay A. Saraswat .

Veja também

• Curry , um funcional linguagem de programação lógica, que permite programar sistemas concorrentes [1] .
• ToonTalk
• Jano
• Alice

Referências

• Marriott, Kim; Peter J. Stuckey (1998). Programação com restrições: Uma introdução . MIT Press. ISBN  0-262-13341-5
• Frühwirth, Thom; Abdennadher Slim (2003). Fundamentos da programação por restrições . Springer.ISBN  3-540-67623-6
• Jaffar, Joxan; Michael J. Maher (1994). "Lógica de programação Restrição: uma pesquisa". Jornal da programação lógica . 19/20: 503-581. DOI : 10.1016 / 0.743-1.066 (94) 90033-7 .

Específico