Untitled

Introdução
O presente texto foi organizado em duas partes tratando os paradigmas de programação lógica e
funcional a partir do ponto de vista de seus respectivos formalismos matemáticos: o princı́pio de
resolução e a teoria de reescrita. O conteúdo e estrutura, assim como os tópicos mais relevantes das
áreas de pesquisa são abordados.
A primeira parte (Programação Lógica —O princı́pio de resolução) é organizada nos
seguintes capı́tulos:
1. Apresentam-se os fundamentos da lógica matemática necessários para a compreenssão do princı́pio de resolução. Estudam-se as linguagens e teorias de primeira ordem, a sua semântica, o
processo de skolemização, os modelos de Herbrand e a relação entre a lógica de primeira ordem
e a lógica clausal.
2. Introduz-se a unificação como mecanismo de ligação de variáveis na resolução, assim como as
noções de substituição e unificador mais geral. Apresenta-se um algoritmo de unificação e estudase sua correção e completude.
3. Motiva-se a utilidade geral em matemática e computação da teoria de pontos fixos utilizando os
teoremas de ponto fixo de Brouwer e de Banach. Estudam-se, então, as noções de ordem parcial,
de limite superior e inferior máximo e mı́nimo, de reticulado, de função monótona, contı́nua, a
teoria dos pontos fixos na lógica, etc. O princı́pio de indução transfinita é também introduzido
para provar os teoremas de existência de pontos fixos.
4. Examina-se a semântica dos programas declarativos e a SLD-resolução incluindo provas formais
da sua correção e completude (refutacional). São incluı́das seções tratando a regra de corte, a
independência da resolução e estratégias de resolução.
5. Sem muito rigor, apresentam-se os problemas para o tratamento de informação negativa segundo
o princı́pio de resolução. Introduz-se a suposição de mundo fechado, a noção de falha finita e a
programação com completação.
1
2
Diversas aplicações da programação lógica são ilustradas através de exemplos simples implementados em XSB-Prolog [SSW+ 94] ou em SICST U S-Prolog [Pro95] incluı́dos nesta primeira
parte.
As referências recomendadas sobre lógica matemática são [Yas71], [End72], [CK90], [BM86],
[EFT84], [Bur98] e [Cai88]. Sobre o princı́pio de resolução e programação lógica podem ser consultados
[Ber95], [Fit96], [Gal87], [Llo87] e [NM90].
A segunda parte (Programação funcional —A teoria de reescrita) é organizada nos seguintes
capı́tulos:
6. Introduz-se o estudo da teoria de reescrita como mecanismo algébrico para dedução de teoremas
equacionais em variedades. Motiva-se o leitor com exemplos simples e explicativos que esclarecem a idéia geral da reescrita no contexto da computação funcional, e revelam as propriedades
fundamentais dos sistemas de reescrita. Introduz-se o cálculo λ como um sistema de reescrita
em lógicas de ordem superior. A adequabilidade computacional da teoria de reescrita, observa-se
demonstrando que as funções parciais recursivas são definı́veis no cálculo λ.
7. Estudam-se os sistemas de redução como relações binárias simples sobre conjuntos, assim como
suas propriedades básicas: confluência, comutatividade, terminação (ou noetherianidade), o conceito de forma normal, etc. Além disto, estudam-se critérios para confluência, dentre os quais
destacam-se a propriedade de Church-Rosser e o lema de Newman. A construção de ordens
parciais noetherianas para o teste da terminação também é abordada.
8. Tratam-se as especificações equacionais de tipos abstratos de dados e os sistemas de reescrita
de termos, a sua importância na demonstração automática de teoremas e as ordens de redução
como mecanismo simples para o teste da terminação. Examina-se o critério dos pares crı́ticos
e o procedimento de completação de Knuth-Bendix. A correção do método de completação é
estudada usando a noção de complexidade das provas de teoremas equacionais.
9. Os sistemas de reescrita condicionais, por brevidade CTRSs, representam a mais importante
extensão dos sistemas de reescrita de termos. Tal extensão admite regras de reescrita com
condições equacionais. A inclusão de condições gerais dentro das especificações algébricas puramente equacionais foi proposta por O’Donnell na década de 70 [O’D77], mas somente no princı́pio
dos 80 aparecem os primeiros estudos profundos para o caso de condições puramente equacionais
realizados por Kaplan [Kap83], [Kap84a]. Kaplan estuda os diferentes mecanismos de avaliação
das condições e seleciona a avaliação padrão demonstrando a correção desta pelo teorema do
3
ponto fixo. Para atacar o problema da indecidibilidade da reescrita dos CTRSs padrão, Kaplan
define a propriedade de simplificação [Kap84b] e Jouannaud e Walmann definen os CTRSs redutivos [JW86]; tal propriedade (e classe de CTRSs) são logo generalizados por Sivakumar na
bem conhecida propriedade de decrescimento [Siv89] (veja também [DOS87], [DOS88]). Outros
trabalhos relevantes no tratamento dos CTRSs são o trabalho de Remy e Zhang [ZR85] e a
tese de Navarro [NG87], onde se define um certo tipo de reescrita hierárquica, que posterga a
avaliação das condições. Outros trabalhos, tratam um tipo especial de sistemas condicionais que
incluem, além das condições equacionais, condições gerais em teorias de primeira ordem com
certas restrições, de forma que seja possı́vel misturar a reescrita pura com outros mecanismos
computacionais (como a programação lógica) que muitas vezes resultam mais eficientes [AR95a],
[AR95b].
As propriedades de confluência e terminação para os CTRSs são tratadas em profundidade por
Bergstra e Klop [BK86] e por Gramlich [Gra95]. Essas propriedades são pesquisadas para os
CTRSs com condições gerais em [AR94].
Entre outros, Jouannaud e Walmann [JW86], Kaplan e Remy [KR89], Sivakumar [Siv89] e
Ganzinger [Gan88], [Gan91] têm tratado a completação dos CTRSs.
10. Estreitamento (Narrowing) estende a reescrita como mecanismo de solução de equações. Após
observar a reescrita como um mecanismo apropriado na demonstração de teoremas (equacionais)
e como um modelo computacional que assimila o paradigma de programação funcional, o estreitamento é um mecanismo baseado em reescrita usado na solução de equações e portanto relevante
na combinação dos paradigmas lógico e funcional veja por exemplo [Red86], [Fur91], [Han94]
e [Der96]. O tratamento do tema por Middeldrop e Hamoen [MH91] é apropriado, pois eles
incluem o caso condicional e o puramente equacional. Também o tema é abordado para ambos casos por Dershowitz e Okada [DO90], por Loria na sua tese de doutorado [Lor93] e por
Bockmayr [Boc93].
Apesar da segunda parte do livro não vir acompanhada de implementações de exemplos,
o sistema RRL (Rewrite Rule Laboratory) [KZ89] é sugerido como ferramenta prática para ilustrar as
aplicações práticas do mecanismo de completação. Adicionalmente linguagens de programação como
ELAN [BKKM02], Maude [Mes00] e CafeObj [DF02] podem também ser utilizadas.
As principais referências gerais sobre teoria da reescrita são [DJ90], [AM90], [Klo92],
[Pla93], [Ave95] e [BN98], [KK02], [Ohl02], [vR03].
4
Subsequentemente são enumeradas algumas das extensões e aplicações da teoria básica de
reescrita de maior relevância e atualidade que foram omitidas no presente livro:
• A redução módulo uma teoria equacional é de grande relevância para manipulação via
técnicas de reescrita de propriedades equacionais não orientáveis, em particular, podem-se considerar os casos associativo e associativo-comutativo que ocorrem com maior frequência na prática.
É fundamental estudar neste tipo de redução os algoritmos de matching e unificação módulo
teorias equacionais. O tratamento original é devido a Jouannaud e Kirchner [JK86], mas a
apresentação de Avenhaus é apropriada [Ave95].
• Outros tópicos especiais que recentemente vêm sendo pesquisados na área são os CTRSs de
ordem superior, CTRSs com premissas pré-construı́das, sı́ntese de programas com técnicas de
reescrita e demonstrações indutivas (ou na teoria inicial). Com relação aos CTRSs de ordem
superior, uma fonte completa de informação é a tese de doutorado de van Oostrom [vO94] e
com relação aos CTRSs com premissas pré-construı́das [AR93]. A construção de programas
com técnicas de reescrita foi estudada por Loria [Lor93] e as demonstrações indutivas têm sido
tratadas, entre outros, por Avenhaus e Becker [AB92], Becker [Bec94], Becker e Wirth [WB95]
e Gramlich e Wirth [WG94].
• O estudo da semântica operacional de linguagens de programação é realizado no contexto de
ferramentas teóricas como o cálculo lambda. Neste, noções básicas como o conceito de substituição devem ser formulados de manera explı́cita, de forma que todas as operações envolvidas
nesta estejam formalizadas. Dessa forma, obtém-se teórias sólidas compatı́veis com as reais
implementações de linguagens de programação e especificação modernas e do futuro. Nestas
teorias, atributos desejáveis, como por exemplo, sistemas de tipos elaborados [Bar92], podem
ser formuladas de maneira robusta simplificando o processo de implementação das linguagens de
programação e especificação. Esse estudo deu origem a uma nova área de pesquisa denominada
substituições explı́citas [ACCL91]. Destacam-se neste contexto variantes do cálculo lambda,
nas quais a notação simbólica usual das variáveis é substituı́da por uma notação com ı́ndices,
idéia formulada originalmente por N.G. de Buijn [dB72], realização da operação de unificação
[DHK00, ARK01, dMARK08] e formulações de sistemas de tipos elaborados. De fato, ambientes
computacionais robustos como ΛProlog [NM88], são resultados de uma boa formulação de um
cálculo de substituições explı́cito robusto [NW98].
• A teoria de reescrita vem sendo promovida e está sendo utilizada como um novo paradigma
5
de programação baseado em duas antigas idéias subjacentes a quasi todos os ambientes computacionais: matching e substituição [KM01]. Em particular, reescrita-lógica [MOM02], um
paradigma baseado em reescrita, mas que aplica mecanismos lógicos (como estratégias) para um
controle computacional adequado da aplicação das regras de reescrita tem grande impacto na
atualidade. Destacam-se sistemas previamente mencionados como ELAN [BKKM02], Maude
[Mes00] e CafeObj [DF02]. Esses sistemas estão sendo utilizados com sucesso na especificação,
modelagem e verificação de diversos objetos computacionais que não se limitam a programas
mas atingem o próprio hardware [AS99, ARLJH06].
Cap. 1
Cap. 6
Cap. 2
Cap. 7
Cap. 3
Cap. 8
Cap. 4
Cap. 9
Cap. 5
Cap. 10
I. Princı́pio de resolução
II. Teoria de reescrita
Figura 1: Grafo de dependências dos capı́tulos
Os capı́tulos estão organizados segundo as dependências ilustradas na Figura 1. A primeira
parte, consistente dos capı́tulos 1-5, e a segunda parte, consistente dos capı́tulos 6-10, podem ser estudadas independentemente em disciplinas semestrais de formalismos e semântica da programação lógica
6
e de teoria de reescrita, respectivamente. Nesses casos, é recomendável a realização de exercı́cios e
pequenos projetos computacionais. Os capı́tulos 1-4, 6-8 e 10 são recomendados para uma disciplina
avançada em teoria da computação do ponto de vista dos fundamentos, lógica e semântica da computação, como é o caso da disciplina introdutória do programa de pós-graduação em matemática na
área teoria da computação, lecionada desde 1995, e da disciplina de teoria da computação do programa
de pós-graduação em informática da Universidade de Brası́lia.
Parte I
PROGRAMAÇÃO LÓGICA
— O princı́pio de resolução —
7