4.4 Programação Lógica

No capítulo 1, enfatizamos que a ciência da computação lida com conhecimento imperativo (como fazer), enquanto a matemática lida com conhecimento declarativo (o que é). De fato, as linguagens de programação exigem que o programador expresse conhecimento de uma forma que indique os métodos passo a passo para resolver problemas específicos. Por outro lado, linguagens de alto nível fornecem, como parte da implementação da linguagem, uma quantidade substancial de conhecimento metodológico que libera o usuário da preocupação com numerosos detalhes de como uma computação especificada progredirá.

A maioria das linguagens de programação, incluindo JavaScript, é organizada em torno do cálculo dos valores de funções matemáticas. Linguagens orientadas a expressões (como Lisp, C, Python e JavaScript) capitalizam o "trocadilho" de que uma expressão que descreve o valor de uma função também pode ser interpretada como um meio de calcular esse valor. Por causa disso, a maioria das linguagens de programação é fortemente tendenciosa em direção a computações unidirecionais (computações com entradas e saídas bem definidas). Existem, no entanto, linguagens de programação radicalmente diferentes que relaxam esse viés. Vimos um exemplo na seção 3.3.5, onde os objetos de computação eram restrições aritméticas. Em um sistema de restrições, a direção e a ordem da computação não são tão bem especificadas; ao realizar uma computação, o sistema deve, portanto, fornecer conhecimento mais detalhado de "como fazer" do que seria o caso com uma computação aritmética comum. Isso não significa, no entanto, que o usuário seja liberado completamente da responsabilidade de fornecer conhecimento imperativo. Existem muitas redes de restrições que implementam o mesmo conjunto de restrições, e o usuário deve escolher do conjunto de redes matematicamente equivalentes uma rede adequada para especificar uma computação particular.

O avaliador de programa não determinístico da seção 4.3 também se afasta da visão de que programação é sobre construir algoritmos para computar funções unidirecionais. Em uma linguagem não determinística, as expressões podem ter mais de um valor e, como resultado, a computação está lidando com relações em vez de funções de valor único. A programação lógica estende essa ideia combinando uma visão relacional de programação com um tipo poderoso de correspondência de padrões simbólicos chamado unificação.¹

Esta abordagem, quando funciona, pode ser uma maneira muito poderosa de escrever programas. Parte do poder vem do fato de que um único fato "o que é" pode ser usado para resolver vários problemas diferentes que teriam diferentes componentes "como fazer". Como exemplo, considere a operação append, que recebe duas listas como argumentos e combina seus elementos para formar uma única lista. Em uma linguagem procedural como JavaScript, poderíamos definir append em termos do construtor de lista básico pair, como fizemos na seção 2.2.1:

function append(x, y) {
    return is_null(x)
           ? y
           : pair(head(x), append(tail(x), y));
}

Esta função pode ser vista como uma tradução para JavaScript das duas regras seguintes, a primeira das quais cobre o caso em que a primeira lista está vazia e a segunda das quais lida com o caso de uma lista não vazia, que é um pair de duas partes:

• Para qualquer lista y, a lista vazia e y fazem append para formar y.
• Para quaisquer u, v, y e z, pair(u, v) e y fazem append para formar pair(u, z) se v e y fazem append para formar z.²

Usando a função append, podemos responder perguntas como:

Encontre o append de list("a", "b") e list("c", "d").

Mas as mesmas duas regras também são suficientes para responder aos seguintes tipos de perguntas, que a função não pode responder:

Encontre uma lista y que faz append com list("a", "b") para produzir list("a", "b", "c", "d").

Encontre todos x e y que fazem append para formar list("a", "b", "c", "d").

Em uma linguagem de programação lógica, o programador escreve uma "função" append declarando as duas regras sobre append dadas acima. O conhecimento "como fazer" é fornecido automaticamente pelo interpretador para permitir que este único par de regras seja usado para responder a todos os três tipos de perguntas sobre append.³

As linguagens de programação lógica contemporâneas (incluindo a que implementamos aqui) têm deficiências substanciais, no sentido de que seus métodos gerais de "como fazer" podem levá-las a loops infinitos espúrios ou outro comportamento indesejável. A programação lógica é um campo ativo de pesquisa em ciência da computação.⁴

No início deste capítulo, exploramos a tecnologia de implementação de interpretadores e descrevemos os elementos que são essenciais para um interpretador para uma linguagem semelhante a JavaScript (na verdade, para um interpretador de qualquer linguagem convencional). Agora aplicaremos essas ideias para discutir um interpretador para uma linguagem de programação lógica. Chamamos essa linguagem de linguagem de consulta, porque é muito útil para recuperar informações de bancos de dados formulando consultas, ou perguntas, expressas na linguagem. Embora a linguagem de consulta seja muito diferente de JavaScript, acharemos conveniente descrever a linguagem nos mesmos termos da estrutura geral que temos usado o tempo todo: como uma coleção de elementos primitivos, juntamente com meios de combinação que nos permitem combinar elementos simples para criar elementos mais complexos e meios de abstração que nos permitem considerar elementos complexos como unidades conceituais únicas. Um interpretador para uma linguagem de programação lógica é consideravelmente mais complexo do que um interpretador para uma linguagem como JavaScript. No entanto, veremos que nosso interpretador de linguagem de consulta contém muitos dos mesmos elementos encontrados no interpretador da seção 4.1. Em particular, haverá uma parte "avaliar" que classifica expressões de acordo com o tipo e uma parte "aplicar" que implementa o mecanismo de abstração da linguagem (funções no caso de JavaScript, e regras no caso de programação lógica). Além disso, um papel central é desempenhado na implementação por uma estrutura de dados de frame, que determina a correspondência entre símbolos e seus valores associados. Um aspecto adicional interessante de nossa implementação de linguagem de consulta é que fazemos uso substancial de streams, que foram introduzidos no capítulo 3.

Footnotes

1. A programação lógica cresceu a partir de uma longa história de pesquisa em prova automática de teoremas. Os primeiros programas de prova de teoremas conseguiam muito pouco, porque buscavam exaustivamente o espaço de provas possíveis. O grande avanço que tornou tal busca plausível foi a descoberta no início dos anos 1960 do algoritmo de unificação e do princípio de resolução (Robinson 1965). A resolução foi usada, por exemplo, por Green e Raphael (1968) (veja também Green 1969) como base para um sistema dedutivo de resposta a perguntas. Durante a maior parte deste período, os pesquisadores se concentraram em algoritmos que são garantidos para encontrar uma prova se ela existe. Tais algoritmos eram difíceis de controlar e direcionar para uma prova. Hewitt (1969) reconheceu a possibilidade de mesclar a estrutura de controle de uma linguagem de programação com as operações de um sistema de manipulação lógica, levando ao trabalho em busca automática mencionado na seção 4.3.1 (nota de rodapé 47). Ao mesmo tempo em que isso estava sendo feito, Colmerauer, em Marselha, estava desenvolvendo sistemas baseados em regras para manipular linguagem natural (veja Colmerauer et al. 1973). Ele inventou uma linguagem de programação chamada Prolog para representar essas regras. Kowalski (1973; 1979) em Edimburgo, reconheceu que a execução de um programa Prolog poderia ser interpretada como provando teoremas (usando uma técnica de prova chamada resolução de cláusula de Horn linear). A fusão dessas duas vertentes levou ao movimento de programação lógica. Assim, ao atribuir crédito pelo desenvolvimento da programação lógica, os franceses podem apontar para a gênese do Prolog na Universidade de Marselha, enquanto os britânicos podem destacar o trabalho na Universidade de Edimburgo. De acordo com pessoas do MIT, a programação lógica foi desenvolvida por esses grupos em uma tentativa de descobrir sobre o que Hewitt estava falando em sua brilhante mas impenetrável tese de doutorado. Para uma história da programação lógica, veja Robinson 1983. ↩

2. Para ver a correspondência entre as regras e a função, deixe x na função (onde x não está vazio) corresponder a pair(u, v) na regra. Então z na regra corresponde ao append de tail(x) e y. ↩

3. Isso certamente não alivia o usuário do problema inteiro de como computar a resposta. Existem muitos conjuntos matematicamente equivalentes de regras diferentes para formular a relação append, apenas alguns dos quais podem ser transformados em dispositivos eficazes para computar em qualquer direção. Além disso, às vezes a informação "o que é" não dá nenhuma pista de "como" computar uma resposta. Por exemplo, considere o problema de computar o y tal que y² = x. ↩

4. O interesse em programação lógica atingiu o pico durante o início dos anos 1980, quando o governo japonês iniciou um projeto ambicioso visando construir supercomputadores super-rápidos otimizados para executar linguagens de programação lógica. A velocidade de tais computadores deveria ser medida em LIPS (Inferências Lógicas Por Segundo) em vez dos usuais FLOPS (Operações de Ponto Flutuante Por Segundo). Embora o projeto tenha sido bem-sucedido no desenvolvimento de hardware e software conforme planejado originalmente, a indústria internacional de computadores se moveu em uma direção diferente. Veja Feigenbaum e Shrobe 1993 para uma avaliação geral do projeto japonês. A comunidade de programação lógica também seguiu em frente para considerar a programação relacional baseada em técnicas diferentes da simples correspondência de padrões, como a capacidade de lidar com restrições numéricas como as ilustradas no sistema de propagação de restrições da seção 3.3.5. ↩