Programação lógica
Origem: Wikipédia, a enciclopédia livre.
Se tem algum conhecimento sobre este assunto, por favor verifique a consistência e o rigor deste artigo.
Programação Lógica é a programação que faz uso de modelos de chamadas de afirmações e objetivos. John McCarthy [1958] foi o primeiro a publicar uma proposta de uso da lógica matemática para programação. A primeira linguagem de programação lógica foi a Planner, que caracterizou os modelos de chamada dos planos processuais para afirmações e objetivos. Com necessidade de adaptação aos sistemas de memória limitada, disponíveis quando foi desenvolvida, Planner usava estruturas de controle de backtracking, portanto um único caminho computacional tinha que ser armazenado por vez. Em seguida o Prolog foi desenvolvido como uma simplificação do Planner que tinha modelos de chamada apenas para objetivos (também baseado em backtracking. A partir do Planner foram desenvolvidas as linguagens de programação QA-4, Popler, Conniver, e QLISP. As linguagens de programação Mercury, Visual Prolog, Oz e Frill, desenvolvidas do Prolog. Atualmente existem linguagens de programação lógica (não baseadas em backtracking) derivadas do Planner (e.g. Ether) e derivadas do Prolog (ver Shapiro [1989] para uma visão geral).
[editar] Historia
Programação lógica é uma ideia que tem sido investigada no contexto da inteligencia artificial pelo menos desde o momento em que John McCarty [1958] propôs: "programas para manipular com sentenças instrumentais comuns apropriadas à linguagem formal (muito provavelmente uma parte do cálculo de predicado). O programa básico formará conclusões imediatas a partir de uma lista de premissas. estas conclusões serão tanto sentenças declarativas quanto imperativas. Quando uma sentença imperativa é deduzida, o programa toma uma ação correspondente.
[editar] Base em lógica matemática
O sentido da programação lógica é trazer o estilo da lógica matemática à programação de computadores. Matemáticos e filósofos encontram na lógica uma ferramenta eficaz para desenvolvimento de corpos de teoria. Vários problemas são naturalmente expressos como teorias. Dizer que um problema precisa de solução frequentemente equivale a perguntar se uma nova hipótese é consistente com uma teoria existente ou se é conseqüência dela. A lógica proporciona uma maneira de provar se uma questão é verdadeira ou falsa. O processo de construir uma prova é bem conhecido, portanto a lógica é um meio confiável de responder perguntas. Sistemas de programação lógica automatizam este processo. A inteligência artificial teve importante influência no desenvolvimento de programação lógica.
[editar] Prolog
Prolog foi uma linguagem de programação apresentada em 1972 por Colmerauer em Marseille e, mais formalmente por Kowalski em 1974, e foi explicitamente apresentada como baseada na lógica matemática. A base dessa alegação era que um programa Prolog podia literalmente ser lido como um conjunto de formulas em um subconjunto de lógica de primeira ordem, herdando o modelo de teoria e prova da lógica de primeira ordem. Uma cláusula
H :- B1, ..., Bn
Pode também ser lida como uma implicação lógica (sua leitura declarativa)
B1 e ... e Bn implica H
onde todas as variáveis da clausula são universalmente quantificadas, ou como uma regra de encadeamento reverso (sua leitura processual) onde os estados que querem provar H, precisam provar B1 através de Bn. A semântica processual foi também formulada como uma construção de uma prova por refutação usando resolução linear (resolução LUSH ou SLD). A relação próxima entre a semântica declarativa e processual resulta numa característica distinta das linguagens de programação lógica, embora a relação se torne mais complexa quando há negação, disjunção e outros quantificadores são permitidos em programas.
[editar] Negação em programação lógica
Se um programa consiste das cláusulas H :- B1 , ..., Bn onde H, B1, ..., Bn são todas fórmulas atômicas da lógica de predicados, então o programa é chamado definitivo ou um programa de cláusulas de Horn. As semânticas declarativas e processuais ou programas lógicos definitivos são diretamente adotados da lógica de predicados. Com a inclusão da negação, a relação com a lógica clássica torna- se menos direta. A regra de inferência assim chamada negação-como-falha indica isso, se um objetivo Q não pode ser provado em um programa, então sua negação not(Q) é considerada uma prova. Isto claramente não é o caso geral na lógica clássica; é possível que nem Q ou not(Q) sejam conseqüência de um conjunto de axiomas. Como resultado, esta regra leva a algumas anomalias lógicas e dificuldades práticas. Uma regra de prova por encadeamento reverso associada à negação-como-falha é incompleta, isto significa que é incapaz de provar todas as conseqüências lógicas que seguem da leitura declarativa de seus programas. Contudo, a maioria dos dialetos Prolog implementam a negação como falha tipicamente usando os caracteres \+.
Ainda que incompleta, a regra de negação como falha é uma sólida regra de inferência (sob certas restrições) respeitando a conclusão de um programa. Conclusão de um programa lógico foi inicialmente definida por Keith Clark basicamente assemelhava-se a considerar o conjunto de todas as cláusulas do programa, com o mesmo predicado, do lado esquerdo,
H :- Corpo1 .... H :- Corpok
Como uma única fórmula equivalente
H sse (Corpo ou ... ou Corpo)
aonde sse significa equivalência (se e somente se). Escrever a conclusão também requer o uso explícito de predicado de igualdade e a inclusão de um conjunto de axiomas apropriados por igualdade. A noção de conclusão é estreitamente relacionada à técnica de circunscrição de McCarty para desenvolver um raciocínio não monotônico, e a suposição de um mundo fechado.
[editar] Implementação Prolog
A primeira implementação Prolog foi a Marseille Prolog, desenvolvida em 1972. O uso de Prolog como uma linguagem de programação prática teve seu grande momento com o desenvolvimento de um compilador por David Warren em Edinburgh, em 1977. experimentos demonstraram que o Edinburgh Prolog podia competir com a velocidade de processamento de outras linguagens de programação simbólica assim como Lisp. O Prolog Edinburgh tornou-se o padrão de facto e influenciou a definição de Prolog padrão ISO.
[editar] Limitações do uso da lógica matemática para programação
John MacCarthy propôs que a lógica matemática fosse usada como a fundação para a epistemologia de sistemas de computatores. Sobre a liderança de Marvin Minsky e Seymour Papert uma abordagem diferente baseada em abordagens processuais foi desenvolvida no MIT. Quando Planner foi desenvolvido, levantou-se o questioanemnto sobre o relacionamento entre as duas abordagens. Robert Kowalski desenvolveu a tese que "computação pode ser provada por dedução" e citou com aprovação "Computação é uma dedução controlada." que ele atribuiu a Pat Hayes em seu artigo de 1988 no início da história do Prolog. Ao contrário de Kowalski e Hayes, Carl Hweitt desenvolveu a tese que dedução lógica era incapaz de levar computação concorrente em sistemas abertos. A resposta à questão sobre a relação entre as abordagens lógica e processual é que a abordagem processual tem semântica matemática diferente (ver semântica denotacional) da semântica da lógica matemática (ver teoria dos modelos).
[editar] Programação lógica concorrente
Keith Clark, Hervé Gallaire, Steve Gregory, Vijay Saraswat, Udi Shapiro, Kazunori Ueda, etc. desenvolveram um tipo de Prolog concorrente que passa mensangens aos sistemas usando unificação de variáveis compartilhadas e fluxo de estrutura de dados para mensagens. Esforços foram feitos para basear esses sistemas em lógica matemática, e elas foram usadas como a base para o Projeto Japonês da Quinta Geração de Computadores.
Como o modelo de Ator, os sistemas com o Prolog concorrente são baseados em passagem de mensagens e consequentemente estavam sujeitos a mesma indeterminação. Esta foi a base de um argumento de Carl Hewitt e Gul Agha [1998] reinvidicando que os sistemas com Prolog concorrente nem eram dedutivos nem lógicos.
[editar] Programação de lógica de ordem superior
Diversos pesquisadores extenderam a programação lógica com as características da [[Programação de ordem superior] derivadas da Lógica de ordem superior, assim como variáveis de predicado. Tais linguagens incluem as extenções do Prolog HiLog e λProlog.
[editar] Programação lógica linear
Baseada na programação logica dentro da lógica linear resultou no design de linguagens de programação lógica que são considerávelmente mais custosas do que aquelas baseadas na lógica clássica. Programas com Cláusulas de Horn (Prolog) podem apenas representar uma mudança de estado pela mudança em argumentos para predicados. Na programação lógica linear, pode-se usar o logica linear ambiente para dar suporte à mudança de estado. Alguns designs iniciais das linguagens de programação lógica baseadas na lógica linear, incluem LO[Andreoli & Pareschi, 1991], Lolli [Hodas & Miller, 1994], ACL [Kobayashi & Yonezawa, 1994], e Forum [Miller, 1996]. Forum proporciona a interpretação objetiva-direta de toda a lógica linear.
[editar] Domínios das Aplicações
- Sistema especialista, onde o programa gera uma recomendação ou resposta para um modelo grande do domínio da aplicação.
- Prova de teorema automatizada, onde o programa gera teoremas, extendendo os existentes no corpo da teoria.
[editar] Ver Também
- Teoria da Computação
- Teoria dos Conjuntos
- Lógica
- Linguagens de Programação
- Métodos Formais
- Paradigma de programação
- Programação Funcional
[editar] Referencias
- Artigo Logic Programming
