4.4Programaçã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 o 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 inúmeros detalhes de como uma computação especificada progredirá.

A maioria das linguagens de programação, incluindo Lisp, é organizada em torno do cálculo dos valores de funções matemáticas. Linguagens orientadas a expressões (como Lisp, Fortran e Algol) se aproveitam do "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). No entanto, existem linguagens de programação radicalmente diferentes que relaxam essa tendência. Vimos um exemplo disso em 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 um 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 totalmente liberado 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, entre o conjunto de redes matematicamente equivalentes, uma rede adequada para especificar uma computação específica.

O avaliador de programas não determinístico de 4.3 também se afasta da visão de que programar é sobre a construção de algoritmos para calcular 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 lida com relações em vez de funções de valor único. A programação lógica estende essa ideia combinando uma visão relacional da programação com um tipo poderoso de correspondência de padrões simbólicos chamado unificação.²⁶²

Essa 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 de "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 Lisp, poderíamos definir append em termos do construtor básico de listas cons, como fizemos em 2.2.1:

(define (append x y)
  (if (null? x) 
      y 
      (cons (car x) (append (cdr x) y))))

Este procedimento pode ser considerado uma tradução para Lisp das duas regras a seguir, a primeira das quais cobre o caso em que a primeira lista está vazia e a segunda lida com o caso de uma lista não vazia, que é um cons de duas partes:

• Para qualquer lista y, a lista vazia e y se juntam para formar y.
• Para qualquer u, v, y e z, (cons u v) e y se juntam para formar (cons u z) se v e y se juntarem para formar z.²⁶³

Usando o procedimento append, podemos responder a perguntas como:

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

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

Encontre uma lista y que, ao ser concatenada com (a b), produza (a b c d).

Encontre todos os x e y que, ao serem concatenados, formem (a b c d).

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

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

Anteriormente neste capítulo, exploramos a tecnologia de implementação de interpretadores e descrevemos os elementos essenciais para um interpretador de uma linguagem semelhante ao Lisp (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 do Lisp, achamos conveniente descrevê-la em termos da mesma estrutura geral que temos usado até agora: 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 que um interpretador para uma linguagem como Lisp. No entanto, veremos que nosso interpretador de linguagem de consulta contém muitos dos mesmos elementos encontrados no interpretador de 4.1. Em particular, haverá uma parte "eval" que classifica expressões de acordo com o tipo e uma parte "apply" que implementa o mecanismo de abstração da linguagem (procedimentos no caso do Lisp e regras no caso da programação lógica). Além disso, uma estrutura de dados de quadro desempenha um papel central na implementação, determinando a correspondência entre símbolos e seus valores associados. Um aspecto adicional interessante de nossa implementação da linguagem de consulta é que fazemos uso substancial de fluxos, que foram introduzidos no Capítulo 3.

4.4.1Recuperação de Informações Dedutivas

A programação lógica se destaca em fornecer interfaces para bancos de dados para recuperação de informações. A linguagem de consulta que implementaremos neste capítulo foi projetada para ser usada dessa maneira.

Para ilustrar o que o sistema de consulta faz, mostraremos como ele pode ser usado para gerenciar o banco de dados de registros de pessoal da Microshaft, uma próspera empresa de alta tecnologia na área de Boston. A linguagem fornece acesso direcionado por padrão a informações de pessoal e também pode tirar proveito de regras gerais para fazer deduções lógicas.

Um banco de dados de exemplo

O banco de dados de pessoal da Microshaft contém asserções sobre o pessoal da empresa. Aqui estão as informações sobre Ben Bitdiddle, o residente especialista em computação:

(address (Bitdiddle Ben) 
         (Slumerville (Ridge Road) 10))
(job (Bitdiddle Ben) (computer wizard))
(salary (Bitdiddle Ben) 60000)

Cada asserção é uma lista (neste caso, uma tripla) cujos elementos podem ser listas.

Como residente especialista, Ben é responsável pela divisão de computação da empresa e supervisiona dois programadores e um técnico. Aqui estão as informações sobre eles:

(address (Hacker Alyssa P) 
         (Cambridge (Mass Ave) 78))
(job (Hacker Alyssa P) (computer programmer))
(salary (Hacker Alyssa P) 40000)
(supervisor (Hacker Alyssa P) (Bitdiddle Ben))

(address (Fect Cy D) 
         (Cambridge (Ames Street) 3))
(job (Fect Cy D) (computer programmer))
(salary (Fect Cy D) 35000)
(supervisor (Fect Cy D) (Bitdiddle Ben))

(address (Tweakit Lem E) 
         (Boston (Bay State Road) 22))
(job (Tweakit Lem E) (computer technician))
(salary (Tweakit Lem E) 25000)
(supervisor (Tweakit Lem E) (Bitdiddle Ben))

Há também um estagiário de programação, que é supervisionado por Alyssa:

(address (Reasoner Louis) 
         (Slumerville (Pine Tree Road) 80))
(job (Reasoner Louis) 
     (computer programmer trainee))
(salary (Reasoner Louis) 30000)
(supervisor (Reasoner Louis) 
            (Hacker Alyssa P))

Todas essas pessoas estão na divisão de computação, como indicado pela palavra computer como o primeiro item em suas descrições de trabalho.

Ben é um funcionário de alto nível. Seu supervisor é o grande chefe da empresa:

(supervisor (Bitdiddle Ben) (Warbucks Oliver))
(address (Warbucks Oliver) 
         (Swellesley (Top Heap Road)))
(job (Warbucks Oliver) 
     (administration big wheel))
(salary (Warbucks Oliver) 150000)

Além da divisão de computação supervisionada por Ben, a empresa tem uma divisão de contabilidade, consistindo de um contador-chefe e seu assistente:

(address (Scrooge Eben) 
         (Weston (Shady Lane) 10))
(job (Scrooge Eben) 
     (accounting chief accountant))
(salary (Scrooge Eben) 75000)
(supervisor (Scrooge Eben) (Warbucks Oliver))

(address (Cratchet Robert) 
         (Allston (N Harvard Street) 16))
(job (Cratchet Robert) (accounting scrivener))
(salary (Cratchet Robert) 18000)
(supervisor (Cratchet Robert) (Scrooge Eben))

Há também uma secretária para o grande chefe:

(address (Aull DeWitt) 
         (Slumerville (Onion Square) 5))
(job (Aull DeWitt) (administration secretary))
(salary (Aull DeWitt) 25000)
(supervisor (Aull DeWitt) (Warbucks Oliver))

O banco de dados também contém asserções sobre quais tipos de trabalhos podem ser feitos por pessoas que ocupam outros tipos de trabalhos. Por exemplo, um especialista em computação pode fazer os trabalhos de um programador de computador e de um técnico de computador:

(can-do-job (computer wizard) 
            (computer programmer))

(can-do-job (computer wizard) 
            (computer technician))

Um programador de computador poderia substituir um estagiário:

(can-do-job (computer programmer)
            (computer programmer trainee))

Além disso, como é bem conhecido,

(can-do-job (administration secretary)
            (administration big wheel))

Consultas simples

A linguagem de consulta permite que os usuários recuperem informações do banco de dados fazendo consultas em resposta ao prompt do sistema. Por exemplo, para encontrar todos os programadores de computador, pode-se dizer:

;;; Entrada da consulta:
(job ?x (computer programmer))

O sistema responderá com os seguintes itens:

;;; Resultados da consulta:
(job (Hacker Alyssa P) (computer programmer))
(job (Fect Cy D) (computer programmer))

A consulta de entrada especifica que estamos procurando entradas no banco de dados que correspondam a um determinado padrão. Neste exemplo, o padrão especifica entradas consistindo de três itens, dos quais o primeiro é o símbolo literal job, o segundo pode ser qualquer coisa e o terceiro é a lista literal (computer programmer). O "qualquer coisa" que pode ser o segundo item na lista correspondente é especificado por uma variável de padrão, ?x. A forma geral de uma variável de padrão é um símbolo, tomado como o nome da variável, precedido por um ponto de interrogação. Veremos abaixo por que é útil especificar nomes para variáveis de padrão em vez de apenas colocar ? nos padrões para representar "qualquer coisa". O sistema responde a uma consulta simples mostrando todas as entradas no banco de dados que correspondem ao padrão especificado.

Um padrão pode ter mais de uma variável. Por exemplo, a consulta:

(address ?x ?y)

listará todos os endereços dos funcionários.

Um padrão pode não ter variáveis, caso em que a consulta simplesmente determina se esse padrão é uma entrada no banco de dados. Se for, haverá uma correspondência; se não, não haverá correspondências.

A mesma variável de padrão pode aparecer mais de uma vez em uma consulta, especificando que o mesmo "qualquer coisa" deve aparecer em cada posição. É por isso que as variáveis têm nomes. Por exemplo:

(supervisor ?x ?x)

encontra todas as pessoas que se supervisionam (embora não haja tais asserções em nosso banco de dados de exemplo).

A consulta:

(job ?x (computer ?type))

corresponde a todas as entradas de trabalho cujo terceiro item é uma lista de dois elementos cujo primeiro item é computer:

(job (Bitdiddle Ben) (computer wizard))
(job (Hacker Alyssa P) (computer programmer))
(job (Fect Cy D) (computer programmer))
(job (Tweakit Lem E) (computer technician))

Esse mesmo padrão não corresponde a:

(job (Reasoner Louis) 
     (computer programmer trainee))

porque o terceiro item na entrada é uma lista de três elementos, e o terceiro item do padrão especifica que deve haver dois elementos. Se quiséssemos mudar o padrão para que o terceiro item pudesse ser qualquer lista começando com computer, poderíamos especificar²⁶⁶:

(job ?x (computer . ?type))

Por exemplo:

(computer . ?type)

corresponde aos dados:

(computer programmer trainee)

com ?type como a lista (programmer trainee). Também corresponde aos dados:

(computer programmer)

com ?type como a lista (programmer), e corresponde aos dados:

(computer)

com ?type como a lista vazia ().

Podemos descrever o processamento de consultas simples pela linguagem de consulta da seguinte forma:

• O sistema encontra todas as atribuições às variáveis no padrão de consulta que satisfazem o padrão—ou seja, todos os conjuntos de valores para as variáveis tais que, se as variáveis de padrão forem instanciadas com (substituídas por) os valores, o resultado estará no banco de dados.
• O sistema responde à consulta listando todas as instanciações do padrão de consulta com as atribuições de variáveis que a satisfazem.

Observe que, se o padrão não tiver variáveis, a consulta se reduz a uma determinação de se esse padrão está no banco de dados. Se estiver, a atribuição vazia, que não atribui valores a variáveis, satisfaz esse padrão para esse banco de dados.

Exercício 4.55: Dê consultas simples que recuperem as seguintes informações do banco de dados:

1. todas as pessoas supervisionadas por Ben Bitdiddle;
2. os nomes e empregos de todas as pessoas na divisão de contabilidade;
3. os nomes e endereços de todas as pessoas que moram em Slumerville.

Consultas compostas

Consultas simples formam as operações primitivas da linguagem de consulta. Para formar operações compostas, a linguagem de consulta fornece meios de combinação. Uma coisa que torna a linguagem de consulta uma linguagem de programação lógica é que os meios de combinação espelham os meios de combinação usados na formação de expressões lógicas: and, or e not. (Aqui and, or e not não são os primitivos do Lisp, mas sim operações embutidas na linguagem de consulta.)

Podemos usar and da seguinte forma para encontrar os endereços de todos os programadores de computador:

(and (job ?person (computer programmer))
     (address ?person ?where))

O resultado é:

(and (job (Hacker Alyssa P) 
          (computer programmer))
     (address (Hacker Alyssa P) 
              (Cambridge (Mass Ave) 78)))

(and (job (Fect Cy D) (computer programmer))
     (address (Fect Cy D) 
              (Cambridge (Ames Street) 3))

Em geral:

(and ⟨query₁⟩ ⟨query₂⟩ … ⟨queryₙ⟩)

é satisfeito por todos os conjuntos de valores para as variáveis de padrão que satisfazem simultaneamente $⟨quer{y}_1⟩$ … $⟨quer{y}_n⟩$.

Como para consultas simples, o sistema processa uma consulta composta encontrando todas as atribuições às variáveis de padrão que satisfazem a consulta, então exibindo instanciações da consulta com esses valores.

Outro meio de construir consultas compostas é através de or. Por exemplo:

(or (supervisor ?x (Bitdiddle Ben))
    (supervisor ?x (Hacker Alyssa P)))

encontrará todos os funcionários supervisionados por Ben Bitdiddle ou Alyssa P. Hacker:

(or (supervisor (Hacker Alyssa P) 
                (Bitdiddle Ben))
    (supervisor (Hacker Alyssa P) 
                (Hacker Alyssa P)))

(or (supervisor (Fect Cy D) 
                (Bitdiddle Ben))
    (supervisor (Fect Cy D) 
                (Hacker Alyssa P)))

(or (supervisor (Tweakit Lem E) 
                (Bitdiddle Ben))
    (supervisor (Tweakit Lem E) 
                (Hacker Alyssa P)))

(or (supervisor (Reasoner Louis) 
                (Bitdiddle Ben))
    (supervisor (Reasoner Louis) 
                (Hacker Alyssa P)))

Em geral:

(or ⟨query₁⟩ ⟨query₂⟩ … ⟨queryₙ⟩)

é satisfeito por todos os conjuntos de valores para as variáveis de padrão que satisfazem pelo menos um de $⟨quer{y}_1⟩$ … $⟨quer{y}_n⟩$.

Consultas compostas também podem ser formadas com not. Por exemplo:

(and (supervisor ?x (Bitdiddle Ben))
     (not (job ?x (computer programmer))))

encontra todas as pessoas supervisionadas por Ben Bitdiddle que não são programadores de computador. Em geral:

(not ⟨query₁⟩)

é satisfeito por todas as atribuições às variáveis de padrão que não satisfazem $⟨quer{y}_1⟩$.²⁶⁷

A forma final de combinação é chamada lisp-value. Quando lisp-value é o primeiro elemento de um padrão, ele especifica que o próximo elemento é um predicado Lisp a ser aplicado ao resto dos elementos (instanciados) como argumentos. Em geral:

(lisp-value ⟨predicate⟩ ⟨arg₁⟩ … ⟨argₙ⟩)

será satisfeito por atribuições às variáveis de padrão para as quais o ⟨predicate⟩ aplicado aos $⟨ar{g}_1⟩$ … $⟨ar{g}_n⟩$ é verdadeiro. Por exemplo, para encontrar todas as pessoas cujo salário é maior que $30.000, poderíamos escrever²⁶⁸:

(and (salary ?person ?amount)
     (lisp-value > ?amount 30000))

Exercício 4.56: Formule consultas compostas que recuperem as seguintes informações:

1. os nomes de todas as pessoas que são supervisionadas por Ben Bitdiddle, juntamente com seus endereços;
2. todas as pessoas cujo salário é menor que o de Ben Bitdiddle, juntamente com seus salários e o salário de Ben Bitdiddle;
3. todas as pessoas que são supervisionadas por alguém que não está na divisão de computação, juntamente com o nome e o emprego do supervisor.

Regras

Além de consultas primitivas e consultas compostas, a linguagem de consulta fornece meios para abstrair consultas. Esses são dados por regras. A regra:

(rule (lives-near ?person-1 ?person-2)
      (and (address ?person-1 
                    (?town . ?rest-1))
           (address ?person-2 
                    (?town . ?rest-2))
           (not (same ?person-1 ?person-2))))

especifica que duas pessoas moram perto uma da outra se moram na mesma cidade. A cláusula final not impede que a regra diga que todas as pessoas moram perto de si mesmas. A relação same é definida por uma regra muito simples:²⁶⁹:

(rule (same ?x ?x))

A seguinte regra declara que uma pessoa é um "grande chefe" em uma organização se ela supervisiona alguém que, por sua vez, é um supervisor:

(rule (wheel ?person)
      (and (supervisor ?middle-manager 
                       ?person)
           (supervisor ?x ?middle-manager)))

A forma geral de uma regra é:

(rule ⟨conclusion⟩ ⟨body⟩)

onde ⟨conclusion⟩ é um padrão e ⟨body⟩ é qualquer consulta.²⁷⁰ Podemos pensar em uma regra como representando um grande (ou mesmo infinito) conjunto de asserções, ou seja, todas as instanciações da conclusão da regra com atribuições de variáveis que satisfazem o corpo da regra. Quando descrevemos consultas simples (padrões), dissemos que uma atribuição a variáveis satisfaz um padrão se o padrão instanciado estiver no banco de dados. Mas o padrão não precisa estar explicitamente no banco de dados como uma asserção. Ele pode ser uma asserção implícita implicada por uma regra. Por exemplo, a consulta:

(lives-near ?x (Bitdiddle Ben))

resulta em:

(lives-near (Reasoner Louis) (Bitdiddle Ben))
(lives-near (Aull DeWitt) (Bitdiddle Ben))

Para encontrar todos os programadores de computador que moram perto de Ben Bitdiddle, podemos perguntar:

(and (job ?x (computer programmer))
     (lives-near ?x (Bitdiddle Ben)))

Como no caso de procedimentos compostos, as regras podem ser usadas como partes de outras regras (como vimos com a regra lives-near acima) ou até mesmo ser definidas recursivamente. Por exemplo, a regra:

(rule (outranked-by ?staff-person ?boss)
      (or (supervisor ?staff-person ?boss)
          (and (supervisor ?staff-person 
                           ?middle-manager)
               (outranked-by ?middle-manager 
                             ?boss))))

diz que um funcionário é superado por um chefe na organização se o chefe é o supervisor da pessoa ou (recursivamente) se o supervisor da pessoa é superado pelo chefe.

Exercício 4.57: Defina uma regra que diga que a pessoa 1 pode substituir a pessoa 2 se a pessoa 1 faz o mesmo trabalho que a pessoa 2 ou alguém que faz o trabalho da pessoa 1 também pode fazer o trabalho da pessoa 2, e se a pessoa 1 e a pessoa 2 não são a mesma pessoa. Usando sua regra, dê consultas que encontrem o seguinte:

1. todas as pessoas que podem substituir Cy D. Fect;
2. todas as pessoas que podem substituir alguém que está sendo pago mais do que elas, juntamente com os dois salários.

Exercício 4.58: Defina uma regra que diga que uma pessoa é um "grande chefe" em uma divisão se a pessoa trabalha na divisão, mas não tem um supervisor que trabalha na divisão.

Exercício 4.59: Ben Bitdiddle perdeu uma reunião demais. Temendo que seu hábito de esquecer reuniões possa custar-lhe o emprego, Ben decide fazer algo a respeito. Ele adiciona todas as reuniões semanais da empresa ao banco de dados da Microshaft, afirmando o seguinte:

(meeting accounting (Monday 9am))
(meeting administration (Monday 10am))
(meeting computer (Wednesday 3pm))
(meeting administration (Friday 1pm))

Cada uma das afirmações acima é para uma reunião de uma divisão inteira. Ben também adiciona uma entrada para a reunião da empresa que abrange todas as divisões. Todos os funcionários da empresa participam dessa reunião.

(meeting whole-company (Wednesday 4pm))

1. Na manhã de sexta-feira, Ben quer consultar o banco de dados para todas as reuniões que ocorrem naquele dia. Qual consulta ele deve usar?
2. Alyssa P. Hacker não está impressionada. Ela acha que seria muito mais útil poder perguntar por suas reuniões especificando seu nome. Então, ela projeta uma regra que diz que as reuniões de uma pessoa incluem todas as reuniões whole-company mais todas as reuniões da divisão dessa pessoa. Preencha o corpo da regra de Alyssa.
3. Alyssa chega ao trabalho na manhã de quarta-feira e se pergunta quais reuniões ela tem que participar naquele dia. Tendo definido a regra acima, qual consulta ela deve fazer para descobrir isso?

Exercício 4.60: Ao fazer a consulta:

(lives-near ?person (Hacker Alyssa P))

Alyssa P. Hacker é capaz de encontrar pessoas que moram perto dela, com quem ela pode ir para o trabalho. Por outro lado, quando ela tenta encontrar todos os pares de pessoas que moram perto uma da outra, consultando:

(lives-near ?person-1 ?person-2)

ela percebe que cada par de pessoas que moram perto uma da outra é listado duas vezes; por exemplo:

(lives-near (Hacker Alyssa P) (Fect Cy D))
(lives-near (Fect Cy D) (Hacker Alyssa P))

Por que isso acontece? Existe uma maneira de encontrar uma lista de pessoas que moram perto uma da outra, na qual cada par aparece apenas uma vez? Explique.

Lógica como programas

Podemos considerar uma regra como um tipo de implicação lógica: Se uma atribuição de valores a variáveis de padrão satisfaz o corpo, então ela satisfaz a conclusão. Consequentemente, podemos considerar a linguagem de consulta como tendo a capacidade de realizar deduções lógicas com base nas regras. Como exemplo, considere a operação append descrita no início de 4.4. Como dissemos, append pode ser caracterizada pelas duas regras a seguir:

• Para qualquer lista y, a lista vazia e y se juntam para formar y.
• Para qualquer u, v, y e z, (cons u v) e y se juntam para formar (cons u z) se v e y se juntarem para formar z.

Para expressar isso em nossa linguagem de consulta, definimos duas regras para uma relação:

(append-to-form x y z)

que podemos interpretar como "x e y se juntam para formar z":

(rule (append-to-form () ?y ?y))
(rule (append-to-form (?u . ?v) ?y (?u . ?z))
      (append-to-form ?v ?y ?z))

A primeira regra não tem corpo, o que significa que a conclusão vale para qualquer valor de ?y. Observe como a segunda regra faz uso da notação de cauda pontilhada para nomear o car e o cdr de uma lista.

Dadas essas duas regras, podemos formular consultas que calculam o append de duas listas:

;;; Entrada da consulta:
(append-to-form (a b) (c d) ?z)

;;; Resultados da consulta:
(append-to-form (a b) (c d) (a b c d))

O que é mais impressionante, podemos usar as mesmas regras para fazer a pergunta "Qual lista, quando concatenada com (a b), produz (a b c d)?" Isso é feito da seguinte forma:

;;; Entrada da consulta:
(append-to-form (a b) ?y (a b c d))

;;; Resultados da consulta:
(append-to-form (a b) (c d) (a b c d))

Também podemos pedir todos os pares de listas que se juntam para formar (a b c d):

;;; Entrada da consulta:
(append-to-form ?x ?y (a b c d))

;;; Resultados da consulta:
(append-to-form () (a b c d) (a b c d))
(append-to-form (a) (b c d) (a b c d))
(append-to-form (a b) (c d) (a b c d))
(append-to-form (a b c) (d) (a b c d))
(append-to-form (a b c d) () (a b c d))

O sistema de consulta pode parecer exibir uma quantidade considerável de inteligência ao usar as regras para deduzir as respostas às consultas acima. Na verdade, como veremos na próxima seção, o sistema está seguindo um algoritmo bem determinado ao desvendar as regras. Infelizmente, embora o sistema funcione de forma impressionante no caso do append, os métodos gerais podem falhar em casos mais complexos, como veremos em 4.4.3.

Exercício 4.61: As seguintes regras implementam uma relação next-to que encontra elementos adjacentes de uma lista:

(rule (?x next-to ?y in (?x ?y . ?u)))
(rule (?x next-to ?y in (?v . ?z))
      (?x next-to ?y in ?z))

Qual será a resposta às seguintes consultas?

(?x next-to ?y in (1 (2 3) 4))
(?x next-to 1 in (2 1 3 1))

Exercício 4.62: Defina regras para implementar a operação last-pair do Exercício 2.17, que retorna uma lista contendo o último elemento de uma lista não vazia. Verifique suas regras em consultas como (last-pair (3) ?x), (last-pair (1 2 3) ?x) e (last-pair (2 ?x) (3)). Suas regras funcionam corretamente em consultas como (last-pair ?x (3))?

Exercício 4.63: O seguinte banco de dados (veja Gênesis 4) traça a genealogia dos descendentes de Ada até Adão, por meio de Caim:

(son Adam Cain) (son Cain Enoch)
(son Enoch Irad) (son Irad Mehujael)
(son Mehujael Methushael)
(son Methushael Lamech)
(wife Lamech Ada) (son Ada Jabal)
(son Ada Jubal)

Formule regras como "Se $S$ é o filho de $f$, e $f$ é o filho de $G$, então $S$ é o neto de $G$" e "Se $W$ é a esposa de $M$, e $S$ é o filho de $W$, então $S$ é o filho de $M$" (o que supostamente era mais verdadeiro nos tempos bíblicos do que hoje) que permitirão ao sistema de consulta encontrar o neto de Caim; os filhos de Lamech; os netos de Metusalém. (Veja Exercício 4.69 para algumas regras para deduzir relacionamentos mais complicados.)

4.4.2Como o Sistema de Consulta Funciona

Na seção 4.4.4, apresentaremos uma implementação do interpretador de consultas como uma coleção de procedimentos. Nesta seção, damos uma visão geral que explica a estrutura geral do sistema independentemente de detalhes de implementação de baixo nível. Depois de descrever a implementação do interpretador, estaremos em posição de entender algumas de suas limitações e algumas das maneiras sutis pelas quais as operações lógicas da linguagem de consulta diferem das operações da lógica matemática.

Deve ficar claro que o avaliador de consultas deve realizar algum tipo de busca para corresponder consultas a fatos e regras no banco de dados. Uma maneira de fazer isso seria implementar o sistema de consultas como um programa não determinístico, usando o avaliador amb de 4.3 (veja Exercício 4.78). Outra possibilidade seria gerenciar a busca com a ajuda de fluxos. Nossa implementação segue essa segunda abordagem.

O sistema de consulta é organizado em torno de duas operações centrais chamadas correspondência de padrões e unificação. Primeiro descrevemos a correspondência de padrões e explicamos como essa operação, juntamente com a organização da informação em termos de fluxos de quadros, nos permite implementar tanto consultas simples quanto compostas. Em seguida, discutimos a unificação, uma generalização da correspondência de padrões necessária para implementar regras. Finalmente, mostramos como todo o interpretador de consultas se encaixa através de um procedimento que classifica expressões de maneira análoga à forma como eval classifica expressões para o interpretador descrito em 4.1.

Correspondência de padrões

Um correspondente de padrões é um programa que testa se algum dado se encaixa em um padrão especificado. Por exemplo, a lista de dados ((a b) c (a b)) corresponde ao padrão (?x c ?x) com a variável de padrão ?x vinculada a (a b). A mesma lista de dados corresponde ao padrão (?x ?y ?z) com ?x e ?z ambos vinculados a (a b) e ?y vinculado a c. Ela também corresponde ao padrão ((?x ?y) c (?x ?y)) com ?x vinculado a a e ?y vinculado a b. No entanto, ela não corresponde ao padrão (?x a ?y), já que esse padrão especifica uma lista cujo segundo elemento é o símbolo a.

O correspondente de padrões usado pelo sistema de consulta recebe como entradas um padrão, um dado e um quadro que especifica vinculações para várias variáveis de padrão. Ele verifica se o dado corresponde ao padrão de uma forma que seja consistente com as vinculações já presentes no quadro. Se for o caso, ele retorna o quadro dado, aumentado por quaisquer vinculações que possam ter sido determinadas pela correspondência. Caso contrário, ele indica que a correspondência falhou.

Por exemplo, usar o padrão (?x ?y ?x) para corresponder a (a b a) dado um quadro vazio retornará um quadro especificando que ?x está vinculado a a e ?y está vinculado a b. Tentar a correspondência com o mesmo padrão, o mesmo dado e um quadro especificando que ?y está vinculado a a falhará. Tentar a correspondência com o mesmo padrão, o mesmo dado, e um quadro em que ?y está vinculado a b e ?x não está vinculado retornará o quadro dado, aumentado por uma vinculação de ?x a a.

O correspondente de padrões é todo o mecanismo necessário para processar consultas simples que não envolvem regras. Por exemplo, para processar a consulta

(job ?x (computer programmer))

nós varremos todas as asserções na base de dados e selecionamos aquelas que correspondem ao padrão em relação a um quadro inicialmente vazio. Para cada correspondência que encontramos, nós usamos o quadro retornado pela correspondência para instanciar o padrão com um valor para ?x.

Fluxos de quadros

O teste de padrões contra quadros é organizado através do uso de fluxos. Dado um único quadro, o processo de correspondência percorre as entradas da base de dados uma por uma. Para cada entrada da base de dados, o correspondente gera ou um símbolo especial indicando que a correspondência falhou ou uma extensão do quadro. Os resultados para todas as entradas da base de dados são coletados em um fluxo, que é passado por um filtro para eliminar as falhas. O resultado é um fluxo de todos os quadros que estendem o quadro dado por meio de uma correspondência com alguma asserção na base de dados.²⁷¹

Em nosso sistema, uma consulta recebe um fluxo de entrada de quadros e realiza a operação de correspondência descrita acima para cada quadro no fluxo, como indicado em Figura 4.4. Ou seja, para cada quadro no fluxo de entrada, a consulta gera um novo fluxo consistindo de todas as extensões daquele quadro por correspondências com asserções na base de dados. Todos esses fluxos são então combinados para formar um grande fluxo, que contém todas as extensões possíveis de cada quadro no fluxo de entrada. Esse fluxo é a saída da consulta.

Para responder a uma consulta simples, usamos a consulta com um fluxo de entrada consistindo de um único quadro vazio. O fluxo de saída resultante contém todas as extensões ao quadro vazio (ou seja, todas as respostas à nossa consulta). Esse fluxo de quadros é então usado para gerar um fluxo de cópias do padrão de consulta original com as variáveis instanciadas pelos valores em cada quadro, e esse é o fluxo que é finalmente impresso.

Consultas compostas

A verdadeira elegância da implementação de fluxos de quadros é evidente quando lidamos com consultas compostas. O processamento de consultas compostas faz uso da capacidade do nosso correspondente de exigir que uma correspondência seja consistente com um quadro especificado. Por exemplo, para lidar com o and de duas consultas, como

(and (can-do-job 
                ?x 
                (computer programmer trainee))
               (job ?person ?x))

(informalmente, “Encontre todas as pessoas que podem fazer o trabalho de um estagiário de programação de computadores”), primeiro encontramos todas as entradas que correspondem ao padrão

(can-do-job ?x (computer programmer trainee))

Isso produz um fluxo de quadros, cada um dos quais contém uma vinculação para ?x. Então, para cada quadro no fluxo, encontramos todas as entradas que correspondem a

(job ?person ?x)

de uma forma que seja consistente com a vinculação dada para ?x. Cada uma dessas correspondências produzirá um quadro contendo vinculações para ?x e ?person. O and de duas consultas pode ser visto como uma combinação em série das duas consultas componentes, como mostrado em Figura 4.5. Os quadros que passam pelo primeiro filtro de consulta são filtrados e ainda mais estendidos pela segunda consulta.

Figura 4.6 mostra o método análogo para calcular o or de duas consultas como uma combinação paralela das duas consultas componentes. O fluxo de entrada de quadros é estendido separadamente por cada consulta. Os dois fluxos resultantes são então mesclados para produzir o fluxo de saída final.

Mesmo a partir desta descrição de alto nível, é aparente que o processamento de consultas compostas pode ser lento. Por exemplo, como uma consulta pode produzir mais de um quadro de saída para cada quadro de entrada, e cada consulta em um and recebe seus quadros de entrada da consulta anterior, uma consulta and poderia, no pior caso, ter que realizar um número de correspondências que é exponencial no número de consultas (veja Exercício 4.76).²⁷² Embora sistemas para lidar apenas com consultas simples sejam bastante práticos, lidar com consultas complexas é extremamente difícil.²⁷³

Do ponto de vista do fluxo de quadros, o not de alguma consulta age como um filtro que remove todos os quadros para os quais a consulta pode ser satisfeita. Por exemplo, dado o padrão

(not (job ?x (computer programmer)))

nós tentamos, para cada quadro no fluxo de entrada, produzir quadros de extensão que satisfaçam (job ?x (computer programmer)). Removemos do fluxo de entrada todos os quadros para os quais tais extensões existem. O resultado é um fluxo consistindo apenas daqueles quadros em que a vinculação para ?x não satisfaz (job ?x (computer programmer)). Por exemplo, ao processar a consulta

(and (supervisor ?x ?y)
               (not (job ?x (computer programmer))))

a primeira cláusula gerará quadros com vinculações para ?x e ?y. A cláusula not então filtrará esses quadros, removendo todos os quadros em que a vinculação para ?x satisfaz a restrição de que ?x é um programador de computadores.²⁷⁴

A forma especial lisp-value é implementada como um filtro semelhante em fluxos de quadros. Usamos cada quadro no fluxo para instanciar quaisquer variáveis no padrão, então aplicamos o predicado Lisp. Removemos do fluxo de entrada todos os quadros para os quais o predicado falha.

Unificação

Para lidar com regras na linguagem de consulta, devemos ser capazes de encontrar as regras cujas conclusões correspondem a um padrão de consulta dado. As conclusões das regras são como asserções, exceto que elas podem conter variáveis, então precisaremos de uma generalização da correspondência de padrões—chamada unificação—na qual tanto o “padrão” quanto o “dado” podem conter variáveis.

Um unificador recebe dois padrões, cada um contendo constantes e variáveis, e determina se é possível atribuir valores às variáveis que tornarão os dois padrões iguais. Se for o caso, ele retorna um quadro contendo essas vinculações. Por exemplo, unificar (?x a ?y) e (?y ?z a) irá especificar um quadro em que ?x, ?y e ?z devem estar todos vinculados a a. Por outro lado, unificar (?x ?y a) e (?x b ?y) falhará, porque não há valor para ?y que possa tornar os dois padrões iguais. (Para os segundos elementos dos padrões serem iguais, ?y teria que ser b; no entanto, para os terceiros elementos serem iguais, ?y teria que ser a.) O unificador usado no sistema de consulta, como o correspondente de padrões, recebe um quadro como entrada e realiza unificações que são consistentes com esse quadro.

O algoritmo de unificação é a parte tecnicamente mais difícil do sistema de consultas. Com padrões complexos, realizar a unificação pode parecer exigir dedução. Para unificar (?x ?x) e ((a ?y c) (a b ?z)), por exemplo, o algoritmo deve inferir que ?x deve ser (a b c), ?y deve ser b e ?z deve ser c. Podemos pensar nesse processo como resolver um conjunto de equações entre os componentes do padrão. Em geral, essas são equações simultâneas, que podem exigir manipulação substancial para resolver.²⁷⁵ Por exemplo, unificar (?x ?x) e ((a ?y c) (a b ?z)) pode ser pensado como especificar as equações simultâneas

?x = (a ?y c)
          ?x = (a b ?z)

Essas equações implicam que

(a ?y c) = (a b ?z)

que por sua vez implica que

a = a, ?y = b, c = ?z,

e, portanto, que

?x = (a b c)

Em uma correspondência de padrões bem-sucedida, todas as variáveis de padrão se tornam vinculadas, e os valores aos quais elas estão vinculadas contêm apenas constantes. Isso também é verdadeiro para todos os exemplos de unificação que vimos até agora. Em geral, no entanto, uma unificação bem-sucedida pode não determinar completamente os valores das variáveis; algumas variáveis podem permanecer desvinculadas e outras podem estar vinculadas a valores que contêm variáveis.

Considere a unificação de (?x a) e ((b ?y) ?z). Podemos deduzir que ?x = (b ?y) e a = ?z, mas não podemos resolver para ?x ou ?y. A unificação não falha, pois é certamente possível tornar os dois padrões iguais atribuindo valores a ?x e ?y. Como essa correspondência de forma alguma restringe os valores que ?y pode assumir, nenhuma vinculação para ?y é colocada no quadro resultante. A correspondência, no entanto, restringe o valor de ?x. Qualquer valor que ?y tenha, ?x deve ser (b ?y). Uma vinculação de ?x ao padrão (b ?y) é, portanto, colocada no quadro. Se um valor para ?y for posteriormente determinado e adicionado ao quadro (por uma correspondência de padrões ou unificação que é exigida para ser consistente com esse quadro), o ?x previamente vinculado se referirá a esse valor.²⁷⁶

Aplicando regras

A unificação é a chave para o componente do sistema de consulta que faz inferências a partir de regras. Para ver como isso é realizado, considere o processamento de uma consulta que envolve a aplicação de uma regra, como

(lives-near ?x (Hacker Alyssa P))

Para processar essa consulta, primeiro usamos o procedimento de correspondência de padrões comum descrito acima para ver se há alguma asserção na base de dados que corresponda a esse padrão. (Não haverá nenhuma neste caso, já que nossa base de dados não inclui asserções diretas sobre quem mora perto de quem.) O próximo passo é tentar unificar o padrão da consulta com a conclusão de cada regra. Descobrimos que o padrão se unifica com a conclusão da regra

(rule (lives-near ?person-1 ?person-2)
                (and (address ?person-1 
                              (?town . ?rest-1))
                     (address ?person-2 
                              (?town . ?rest-2))
                     (not (same ?person-1 ?person-2))))

resultando em um quadro especificando que ?person-2 está vinculado a (Hacker Alyssa P) e que ?x deve estar vinculado a (ter o mesmo valor que) ?person-1. Agora, em relação a esse quadro, avaliamos a consulta composta dada pelo corpo da regra. Correspondências bem-sucedidas estenderão esse quadro, fornecendo uma vinculação para ?person-1 e, consequentemente, um valor para ?x, que podemos usar para instanciar o padrão de consulta original.

Em geral, o avaliador de consultas usa o seguinte método para aplicar uma regra ao tentar estabelecer um padrão de consulta em um quadro que especifica vinculações para algumas das variáveis do padrão:

• Unifique a consulta com a conclusão da regra para formar, se bem-sucedido, uma extensão do quadro original.
• Em relação ao quadro estendido, avalie a consulta formada pelo corpo da regra.

Observe como isso é semelhante ao método para aplicar um procedimento no avaliador eval/apply para Lisp:

• Vincule os parâmetros do procedimento aos seus argumentos para formar um quadro que estenda o ambiente original do procedimento.
• Em relação ao ambiente estendido, avalie a expressão formada pelo corpo do procedimento.

A semelhança entre os dois avaliadores não deve ser surpreendente. Assim como as definições de procedimentos são o meio de abstração em Lisp, as definições de regras são o meio de abstração na linguagem de consulta. Em cada caso, desenrolamos a abstração criando vinculações apropriadas e avaliando o corpo da regra ou do procedimento em relação a essas vinculações.

Consultas simples

Vimos anteriormente nesta seção como avaliar consultas simples na ausência de regras. Agora que vimos como aplicar regras, podemos descrever como avaliar consultas simples usando tanto regras quanto asserções.

Dado o padrão de consulta e um fluxo de quadros, produzimos, para cada quadro no fluxo de entrada, dois fluxos:

• um fluxo de quadros estendidos obtidos pela correspondência do padrão contra todas as asserções na base de dados (usando o correspondente de padrões), e
• um fluxo de quadros estendidos obtidos pela aplicação de todas as regras possíveis (usando o unificador).²⁷⁷

Anexar esses dois fluxos produz um fluxo que consiste em todas as formas que o padrão dado pode ser satisfeito de forma consistente com o quadro original. Esses fluxos (um para cada quadro no fluxo de entrada) são agora todos combinados para formar um grande fluxo, que, portanto, consiste em todas as formas que qualquer um dos quadros no fluxo de entrada original pode ser estendido para produzir uma correspondência com o padrão dado.

O avaliador de consultas e o loop de controle

Apesar da complexidade das operações de correspondência subjacentes, o sistema é organizado de forma muito semelhante a um avaliador para qualquer linguagem. O procedimento que coordena as operações de correspondência é chamado qeval, e ele desempenha um papel análogo ao do procedimento eval para Lisp. Qeval recebe como entradas uma consulta e um fluxo de quadros. Sua saída é um fluxo de quadros, correspondendo a correspondências bem-sucedidas com o padrão de consulta, que estendem algum quadro no fluxo de entrada, como indicado em Figura 4.4. Como eval, qeval classifica os diferentes tipos de expressões (consultas) e despacha para um procedimento apropriado para cada um. Há um procedimento para cada forma especial (and, or, not e lisp-value) e um para consultas simples.

O loop de controle, que é análogo ao procedimento driver-loop para os outros avaliadores neste capítulo, lê consultas do terminal. Para cada consulta, ele chama qeval com a consulta e um fluxo que consiste em um único quadro vazio. Isso produzirá o fluxo de todas as correspondências possíveis (todas as extensões possíveis ao quadro vazio). Para cada quadro no fluxo resultante, ele instancia a consulta original usando os valores das variáveis encontrados no quadro. Esse fluxo de consultas instanciadas é então impresso.²⁷⁸

O loop de controle também verifica o comando especial assert!, que sinaliza que a entrada não é uma consulta, mas sim uma asserção ou regra a ser adicionada à base de dados. Por exemplo,

(assert!
           (job (Bitdiddle Ben)
                (computer wizard)))
          
          (assert!
           (rule (wheel ?person)
                 (and (supervisor 
                       ?middle-manager ?person)
                      (supervisor
                       ?x ?middle-manager))))

4.4.3A programação lógica é lógica matemática?

Os meios de combinação usados na linguagem de consulta podem, a princípio, parecer idênticos às operações and, or e not da lógica matemática, e a aplicação de regras da linguagem de consulta é, de fato, realizada através de um método legítimo de inferência.²⁷⁹ Essa identificação da linguagem de consulta com a lógica matemática não é realmente válida, no entanto, porque a linguagem de consulta fornece uma estrutura de controle que interpreta as declarações lógicas de forma procedural. Podemos frequentemente aproveitar essa estrutura de controle. Por exemplo, para encontrar todos os supervisores de programadores, poderíamos formular uma consulta em qualquer uma de duas formas logicamente equivalentes:

(and (job ?x (computer programmer))
               (supervisor ?x ?y))

ou

(and (supervisor ?x ?y)
               (job ?x (computer programmer)))

Se uma empresa tiver muito mais supervisores do que programadores (o caso usual), é melhor usar a primeira forma em vez da segunda, porque a base de dados deve ser varrida para cada resultado intermediário (quadro) produzido pela primeira cláusula do and.

O objetivo da programação lógica é fornecer ao programador técnicas para decompor um problema computacional em dois problemas separados: “o que” deve ser computado e “como” isso deve ser computado. Isso é realizado selecionando um subconjunto das declarações da lógica matemática que seja poderoso o suficiente para descrever qualquer coisa que se queira computar, mas fraco o suficiente para ter uma interpretação procedural controlável. A intenção aqui é que, por um lado, um programa especificado em uma linguagem de programação lógica deve ser um programa efetivo que pode ser executado por um computador. O controle (“como” computar) é efetuado usando a ordem de avaliação da linguagem. Devemos ser capazes de organizar a ordem das cláusulas e a ordem dos subobjetivos dentro de cada cláusula para que a computação seja feita em uma ordem considerada efetiva e eficiente. Ao mesmo tempo, devemos ser capazes de ver o resultado da computação (“o que” computar) como uma simples consequência das leis da lógica.

Nossa linguagem de consulta pode ser considerada como um subconjunto procedimentalmente interpretável da lógica matemática. Uma asserção representa um fato simples (uma proposição atômica). Uma regra representa a implicação de que a conclusão da regra vale para aqueles casos em que o corpo da regra vale. Uma regra tem uma interpretação procedural natural: Para estabelecer a conclusão da regra, estabeleça o corpo da regra. As regras, portanto, especificam computações. No entanto, como as regras também podem ser consideradas como declarações da lógica matemática, podemos justificar qualquer “inferência” realizada por um programa lógico afirmando que o mesmo resultado poderia ser obtido trabalhando inteiramente dentro da lógica matemática.²⁸⁰

Loops infinitos

Uma consequência da interpretação procedural de programas lógicos é que é possível construir programas desesperadamente ineficientes para resolver certos problemas. Um caso extremo de ineficiência ocorre quando o sistema entra em loops infinitos ao fazer deduções. Como um exemplo simples, suponha que estamos configurando uma base de dados de casamentos famosos, incluindo

(assert! (married Minnie Mickey))

Se agora perguntarmos

(married Mickey ?who)

não obteremos resposta, porque o sistema não sabe que se $A$ é casado com $B$, então $B$ é casado com $A$. Então, afirmamos a regra

(assert! (rule (married ?x ?y)
                         (married ?y ?x)))

e novamente consultamos

(married Mickey ?who)

Infelizmente, isso levará o sistema a um loop infinito, como segue:

• O sistema descobre que a regra married é aplicável; ou seja, a conclusão da regra (married ?x ?y) se unifica com sucesso com o padrão de consulta (married Mickey ?who) para produzir um quadro em que ?x está vinculado a Mickey e ?y está vinculado a ?who. Então, o interpretador prossegue para avaliar o corpo da regra (married ?y ?x) nesse quadro—em efeito, para processar a consulta (married ?who Mickey).
• Uma resposta aparece diretamente como uma asserção na base de dados: (married Minnie Mickey).
• A regra married também é aplicável, então o interpretador novamente avalia o corpo da regra, que desta vez é equivalente a (married Mickey ?who).

O sistema está agora em um loop infinito. De fato, se o sistema encontrará a resposta simples (married Minnie Mickey) antes de entrar no loop depende de detalhes de implementação sobre a ordem em que o sistema verifica os itens na base de dados. Este é um exemplo muito simples dos tipos de loops que podem ocorrer. Coleções de regras inter-relacionadas podem levar a loops muito mais difíceis de antecipar, e a aparência de um loop pode depender da ordem das cláusulas em um and (veja Exercício 4.64) ou de detalhes de baixo nível sobre a ordem em que o sistema processa consultas.²⁸¹

Problemas com not

Outra peculiaridade no sistema de consulta diz respeito a not. Dada a base de dados de 4.4.1, considere as duas consultas a seguir:

(and (supervisor ?x ?y)
               (not (job ?x (computer programmer))))
          
          (and (not (job ?x (computer programmer)))
               (supervisor ?x ?y))

Essas duas consultas não produzem o mesmo resultado. A primeira consulta começa por encontrar todas as entradas na base de dados que correspondem a (supervisor ?x ?y), e então filtra os quadros resultantes, removendo aqueles em que o valor de ?x satisfaz (job ?x (computer programmer)). A segunda consulta começa filtrando os quadros de entrada para remover aqueles que podem satisfazer (job ?x (computer programmer)). Como o único quadro de entrada é vazio, ela verifica a base de dados para ver se há algum padrão que satisfaça (job ?x (computer programmer)). Como geralmente há entradas dessa forma, a cláusula not filtra o quadro vazio e retorna um fluxo vazio de quadros. Consequentemente, toda a consulta composta retorna um fluxo vazio.

O problema é que nossa implementação de not realmente serve como um filtro sobre valores para as variáveis. Se uma cláusula not é processada com um quadro em que algumas das variáveis permanecem desvinculadas (como ?x no exemplo acima), o sistema produzirá resultados inesperados. Problemas semelhantes ocorrem com o uso de lisp-value—o predicado Lisp não pode funcionar se alguns de seus argumentos estiverem desvinculados. Veja Exercício 4.77.

Há também uma maneira muito mais séria em que o not da linguagem de consulta diferente do not da lógica matemática. Em lógica, interpretamos a declaração “não $P$” para significar que $P$ não é verdadeira. No sistema de consulta, no entanto, “não $P$” significa que $P$ não é dedutível a partir do conhecimento na base de dados. Por exemplo, dada a base de dados de pessoal de 4.4.1, o sistema deduziria alegremente todos os tipos de declarações not, como que Ben Bitdiddle não é um fã de beisebol, que não está chovendo lá fora, e que 2 + 2 não é 4.²⁸² Em outras palavras, o not de linguagens de programação lógica reflete a chamada suposição de mundo fechado de que toda a informação relevante foi incluída na base de dados.²⁸³

Exercício 4.64: Louis Reasoner exclui por engano a regra outranked-by (4.4.1) da base de dados. Quando ele percebe isso, ele rapidamente a reinstala. Infelizmente, ele faz uma pequena mudança na regra e a digita como

(rule (outranked-by ?staff-person ?boss)
            (or (supervisor ?staff-person ?boss)
                (and (outranked-by ?middle-manager
                                   ?boss)
                     (supervisor ?staff-person 
                                 ?middle-manager))))

Logo após Louis digitar essa informação no sistema, DeWitt Aull vem descobrir quem supera Ben Bitdiddle. Ele faz a consulta

(outranked-by (Bitdiddle Ben) ?who)

Depois de responder, o sistema entra em um loop infinito. Explique por quê.

Exercício 4.65: Cy D. Fect, ansioso pelo dia em que ele subirá na organização, faz uma consulta para encontrar todas as rodas (usando a regra wheel de 4.4.1):

(wheel ?who)

Para sua surpresa, o sistema responde

;;; Resultados da consulta:
          (wheel (Warbucks Oliver))
          (wheel (Bitdiddle Ben))
          (wheel (Warbucks Oliver))
          (wheel (Warbucks Oliver))
          (wheel (Warbucks Oliver))

Por que Oliver Warbucks é listado quatro vezes?

Exercício 4.66: Ben tem generalizado o sistema de consulta para fornecer estatísticas sobre a empresa. Por exemplo, para encontrar o total de salários de todos os programadores de computadores, será possível dizer

(sum ?amount
               (and (job ?x (computer programmer))
                    (salary ?x ?amount)))

Em geral, o novo sistema de Ben permite expressões da forma

(accumulation-function ⟨variável⟩
                                 ⟨padrão de consulta⟩)

onde accumulation-function pode ser coisas como sum, average ou maximum. Ben raciocina que deve ser fácil implementar isso. Ele simplesmente alimentará o padrão de consulta a qeval. Isso produzirá um fluxo de quadros. Ele então passará esse fluxo por uma função de mapeamento que extrai o valor da variável designada de cada quadro no fluxo e alimentará o fluxo resultante de valores para a função de acumulação. Assim que Ben completa a implementação e está prestes a testá-la, Cy passa por perto, ainda intrigado com o resultado da consulta wheel em Exercício 4.65. Quando Cy mostra a Ben a resposta do sistema, Ben geme, “Oh, não, meu esquema de acumulação simples não funcionará!”

O que Ben acabou de perceber? Esboce um método que ele pode usar para salvar a situação.

Exercício 4.67: Projete uma maneira de instalar um detector de loops no sistema de consulta para evitar os tipos de loops simples ilustrados no texto e em Exercício 4.64. A ideia geral é que o sistema deve manter algum tipo de histórico de sua cadeia atual de deduções e não deve começar a processar uma consulta que já está trabalhando. Descreva que tipo de informação (padrões e quadros) é incluída nesse histórico e como a verificação deve ser feita. (Depois de estudar os detalhes da implementação do sistema de consulta em 4.4.4, você pode querer modificar o sistema para incluir seu detector de loops.)

Exercício 4.68: Defina regras para implementar a operação reverse de Exercício 2.18, que retorna uma lista contendo os mesmos elementos de uma lista dada em ordem inversa. (Dica: Use append-to-form.) Suas regras podem responder tanto a (reverse (1 2 3) ?x) quanto a (reverse ?x (1 2 3))?

Exercício 4.69: Começando com a base de dados e as regras que você formulou em Exercício 4.63, projete uma regra para adicionar “grandes” a uma relação de neto. Isso deve permitir que o sistema deduza que Irad é o bisneto de Adam, ou que Jabal e Jubal são os tetranetos de Adam. (Dica: Represente o fato sobre Irad, por exemplo, como ((great grandson) Adam Irad). Escreva regras que determinam se uma lista termina com a palavra grandson. Use isso para expressar uma regra que permite derivar a relação ((great . ?rel) ?x ?y), onde ?rel é uma lista que termina com grandson.) Teste suas regras em consultas como ((great grandson) ?g ?ggs) e (?relationship Adam Irad).

4.4.4Implementando o Sistema de Consulta

A seção 4.4.2 descreveu como o sistema de consulta funciona. Agora preenchemos os detalhes apresentando uma implementação completa do sistema.

4.4.4.1O Loop de Controle e a Instanciação

O loop de controle para o sistema de consulta repetidamente lê expressões de entrada. Se a expressão for uma regra ou asserção a ser adicionada à base de dados, então a informação é adicionada. Caso contrário, a expressão é assumida como uma consulta. O loop de controle passa essa consulta para o avaliador qeval junto com um fluxo inicial de quadros consistindo de um único quadro vazio. O resultado da avaliação é um fluxo de quadros gerados pela satisfação da consulta com valores de variáveis encontrados na base de dados. Esses quadros são usados para formar um novo fluxo consistindo de cópias da consulta original em que as variáveis são instanciadas com valores fornecidos pelo fluxo de quadros, e esse fluxo final é impresso no terminal:

(define input-prompt  ";;; Entrada da consulta:")
          (define output-prompt ";;; Resultados da consulta:")
          
          (define (query-driver-loop)
            (prompt-for-input input-prompt)
            (let ((q (query-syntax-process (read))))
              (cond ((assertion-to-be-added? q)
                     (add-rule-or-assertion! 
                      (add-assertion-body q))
                     (newline)
                     (display 
                      "Asserção adicionada à base de dados.")
                     (query-driver-loop))
                    (else
                     (newline)
                     (display output-prompt)
                     (display-stream
                      (stream-map
                       (lambda (frame)
                         (instantiate
                          q
                          frame
                          (lambda (v f)
                            (contract-question-mark v))))
                       (qeval q (singleton-stream '()))))))))

Aqui, como nos outros avaliadores neste capítulo, usamos uma sintaxe abstrata para as expressões da linguagem de consulta. A implementação da sintaxe de expressão, incluindo o predicado assertion-to-be-added? e o seletor add-assertion-body, é dada em 4.4.4.7. Add-rule-or-assertion! é definido em 4.4.4.5.

Antes de fazer qualquer processamento em uma expressão de entrada, o loop de controle a transforma sintaticamente em uma forma que torna o processamento mais eficiente. Isso envolve mudar a representação das variáveis de padrão. Quando a consulta é instanciada, quaisquer variáveis que permaneçam desvinculadas são transformadas de volta para a representação de entrada antes de serem impressas. Essas transformações são realizadas pelos dois procedimentos query-syntax-process e contract-question-mark (4.4.4.7).

Para instanciar uma expressão, nós a copiamos, substituindo quaisquer variáveis na expressão por seus valores em um quadro dado. Os valores são eles mesmos instanciados, já que eles podem conter variáveis (por exemplo, se ?x em exp está vinculado a ?y como resultado da unificação e ?y está por sua vez vinculado a 5). A ação a ser tomada se uma variável não puder ser instanciada é dada por um argumento procedural para instantiate.

(define (instantiate 
                   exp frame unbound-var-handler)
            (define (copy exp)
              (cond ((var? exp)
                     (let ((binding 
                            (binding-in-frame 
                             exp frame)))
                       (if binding
                           (copy 
                            (binding-value binding))
                           (unbound-var-handler 
                            exp frame))))
                    ((pair? exp)
                     (cons (copy (car exp)) 
                           (copy (cdr exp))))
                    (else exp)))
            (copy exp))

Os procedimentos que manipulam vinculações são definidos em 4.4.4.8.

4.4.4.2O Avaliador

O procedimento qeval, chamado pelo query-driver-loop, é o avaliador básico do sistema de consultas. Ele recebe como entradas uma consulta e um fluxo de quadros (frames), e retorna um fluxo de quadros estendidos. Ele identifica formas especiais por meio de um despacho direcionado por dados usando get e put, assim como fizemos na implementação de operações genéricas no Capítulo 2. Qualquer consulta que não seja identificada como uma forma especial é assumida como uma consulta simples, a ser processada por simple-query.

(define (qeval query frame-stream)
              (let ((qproc (get (type query) 'qeval)))
                (if qproc
                    (qproc (contents query) frame-stream)
                    (simple-query query frame-stream))))

Type e contents, definidos em 4.4.4.7, implementam a sintaxe abstrata das formas especiais.

Consultas simples

O procedimento simple-query lida com consultas simples. Ele recebe como argumentos uma consulta simples (um padrão) junto com um fluxo de quadros, e retorna o fluxo formado pela extensão de cada quadro por todas as correspondências da consulta no banco de dados.

(define (simple-query query-pattern 
                                  frame-stream)
              (stream-flatmap
               (lambda (frame)
                 (stream-append-delayed
                  (find-assertions query-pattern frame)
                  (delay 
                    (apply-rules query-pattern frame))))
               frame-stream))

Para cada quadro no fluxo de entrada, usamos find-assertions (4.4.4.3) para corresponder o padrão contra todas as asserções no banco de dados, produzindo um fluxo de quadros estendidos, e usamos apply-rules (4.4.4.4) para aplicar todas as regras possíveis, produzindo outro fluxo de quadros estendidos. Esses dois fluxos são combinados (usando stream-append-delayed, 4.4.4.6) para formar um fluxo de todas as maneiras que o padrão dado pode ser satisfeito de forma consistente com o quadro original (veja Exercício 4.71). Os fluxos para os quadros individuais de entrada são combinados usando stream-flatmap (4.4.4.6) para formar um grande fluxo de todas as maneiras que qualquer um dos quadros no fluxo de entrada original pode ser estendido para produzir uma correspondência com o padrão dado.

Consultas compostas

Consultas and são tratadas como ilustrado em Figura 4.5 pelo procedimento conjoin. Conjoin recebe como entradas os conjuntos e o fluxo de quadros e retorna o fluxo de quadros estendidos. Primeiro, conjoin processa o fluxo de quadros para encontrar o fluxo de todas as extensões possíveis de quadros que satisfazem a primeira consulta na conjunção. Então, usando isso como o novo fluxo de quadros, ele aplica recursivamente conjoin ao restante das consultas.

(define (conjoin conjuncts frame-stream)
              (if (empty-conjunction? conjuncts)
                  frame-stream
                  (conjoin (rest-conjuncts conjuncts)
                           (qeval 
                            (first-conjunct conjuncts)
                            frame-stream))))

A expressão

(put 'and 'qeval conjoin)

configura qeval para despachar para conjoin quando uma forma and é encontrada.

Consultas or são tratadas de forma semelhante, como mostrado em Figura 4.6. Os fluxos de saída para os vários disjuntos do or são computados separadamente e mesclados usando o procedimento interleave-delayed de 4.4.4.6. (Veja Exercício 4.71 e Exercício 4.72.)

(define (disjoin disjuncts frame-stream)
              (if (empty-disjunction? disjuncts)
                  the-empty-stream
                  (interleave-delayed
                   (qeval (first-disjunct disjuncts) 
                          frame-stream)
                   (delay (disjoin 
                           (rest-disjuncts disjuncts)
                           frame-stream)))))
            (put 'or 'qeval disjoin)

Os predicados e seletores para a sintaxe de conjuntos e disjuntos são dados em 4.4.4.7.

Filtros

Not é tratado pelo método delineado em 4.4.2. Tentamos estender cada quadro no fluxo de entrada para satisfazer a consulta sendo negada, e incluímos um determinado quadro no fluxo de saída apenas se ele não puder ser estendido.

(define (negate operands frame-stream)
              (stream-flatmap
               (lambda (frame)
                 (if (stream-null? 
                      (qeval (negated-query operands)
                             (singleton-stream frame)))
                     (singleton-stream frame)
                     the-empty-stream))
               frame-stream))
            (put 'not 'qeval negate)

Lisp-value é um filtro semelhante a not. Cada quadro no fluxo é usado para instanciar as variáveis no padrão, o predicado indicado é aplicado, e os quadros para os quais o predicado retorna falso são filtrados do fluxo de entrada. Um erro resulta se houver variáveis de padrão não vinculadas.

(define (lisp-value call frame-stream)
              (stream-flatmap
               (lambda (frame)
                 (if (execute
                      (instantiate
                       call
                       frame
                       (lambda (v f)
                         (error 
                          "Unknown pat var: LISP-VALUE" 
                          v))))
                     (singleton-stream frame)
                     the-empty-stream))
               frame-stream))
            (put 'lisp-value 'qeval lisp-value)

Execute, que aplica o predicado aos argumentos, deve eval a expressão do predicado para obter o procedimento a ser aplicado. No entanto, ele não deve avaliar os argumentos, pois eles já são os argumentos reais, não expressões cuja avaliação (em Lisp) produzirá os argumentos. Observe que execute é implementado usando eval e apply do sistema Lisp subjacente.

(define (execute exp)
              (apply (eval (predicate exp) 
                           user-initial-environment)
                     (args exp)))

A forma especial always-true fornece uma consulta que é sempre satisfeita. Ela ignora seu conteúdo (normalmente vazio) e simplesmente passa todos os quadros no fluxo de entrada. Always-true é usado pelo seletor rule-body (4.4.4.7) para fornecer corpos para regras que foram definidas sem corpos (ou seja, regras cujas conclusões são sempre satisfeitas).

(define (always-true ignore frame-stream) 
              frame-stream)
            (put 'always-true 'qeval always-true)

Os seletores que definem a sintaxe de not e lisp-value são dados em 4.4.4.7.

4.4.4.3Encontrando Asserções por Correspondência de Padrões

Find-assertions, chamado por simple-query (4.4.4.2), recebe como entrada um padrão e um quadro. Ele retorna um fluxo de quadros, cada um estendendo o dado por uma correspondência no banco de dados do padrão dado. Ele usa fetch-assertions (4.4.4.5) para obter um fluxo de todas as asserções no banco de dados que devem ser verificadas para uma correspondência contra o padrão e o quadro. A razão para fetch-assertions aqui é que podemos aplicar testes simples que eliminarão muitas das entradas no banco de dados do conjunto de candidatos para uma correspondência bem-sucedida. O sistema ainda funcionaria se eliminássemos fetch-assertions e simplesmente verificássemos um fluxo de todas as asserções no banco de dados, mas a computação seria menos eficiente porque precisaríamos fazer muito mais chamadas ao correspondente.

(define (find-assertions pattern frame)
              (stream-flatmap 
                (lambda (datum) 
                  (check-an-assertion datum pattern frame))
                (fetch-assertions pattern frame)))

Check-an-assertion recebe como argumentos um padrão, um objeto de dados (asserção) e um quadro e retorna ou um fluxo de um elemento contendo o quadro estendido ou the-empty-stream se a correspondência falhar.

(define (check-an-assertion 
                     assertion query-pat query-frame)
              (let ((match-result
                     (pattern-match 
                      query-pat assertion query-frame)))
                (if (eq? match-result 'failed)
                    the-empty-stream
                    (singleton-stream match-result))))

O correspondente de padrão básico retorna ou o símbolo failed ou uma extensão do quadro dado. A ideia básica do correspondente é verificar o padrão contra o objeto de dados, elemento por elemento, acumulando vinculações para as variáveis do padrão. Se o padrão e o objeto de dados forem iguais, a correspondência é bem-sucedida e retornamos o quadro de vinculações acumuladas até agora. Caso contrário, se o padrão for uma variável, estendemos o quadro atual vinculando a variável ao dado, desde que isso seja consistente com as vinculações já no quadro. Se o padrão e o dado forem ambos pares, correspondemos (recursivamente) o car do padrão contra o car do dado para produzir um quadro; neste quadro, então correspondemos o cdr do padrão contra o cdr do dado. Se nenhum desses casos for aplicável, a correspondência falha e retornamos o símbolo failed.

(define (pattern-match pat dat frame)
              (cond ((eq? frame 'failed) 'failed)
                    ((equal? pat dat) frame)
                    ((var? pat) 
                     (extend-if-consistent 
                      pat dat frame))
                    ((and (pair? pat) (pair? dat))
                     (pattern-match 
                      (cdr pat) 
                      (cdr dat)
                      (pattern-match
                       (car pat) (car dat) frame)))
                    (else 'failed)))

Aqui está o procedimento que estende um quadro adicionando uma nova vinculação, se isso for consistente com as vinculações já no quadro:

(define (extend-if-consistent var dat frame)
              (let ((binding (binding-in-frame var frame)))
                (if binding
                    (pattern-match 
                     (binding-value binding) dat frame)
                    (extend var dat frame))))

Se não houver vinculação para a variável no quadro, simplesmente adicionamos a vinculação da variável ao dado. Caso contrário, correspondemos, no quadro, o dado contra o valor da variável no quadro. Se o valor armazenado contiver apenas constantes, como deve ser se foi armazenado durante a correspondência de padrões por extend-if-consistent, então a correspondência simplesmente testa se os valores armazenados e novos são iguais. Se forem, ele retorna o quadro inalterado; se não, ele retorna uma indicação de falha. O valor armazenado pode, no entanto, conter variáveis de padrão se foi armazenado durante a unificação (veja 4.4.4.4). A correspondência recursiva do padrão armazenado contra o novo dado adicionará ou verificará vinculações para as variáveis neste padrão. Por exemplo, suponha que temos um quadro no qual ?x está vinculado a (f ?y) e ?y não está vinculado, e desejamos aumentar este quadro com uma vinculação de ?x a (f b). Procuramos ?x e descobrimos que ele está vinculado a (f ?y). Isso nos leva a corresponder (f ?y) contra o novo valor proposto (f b) no mesmo quadro. Eventualmente, essa correspondência estende o quadro adicionando uma vinculação de ?y a b. ?X permanece vinculado a (f ?y). Nunca modificamos uma vinculação armazenada e nunca armazenamos mais de uma vinculação para uma dada variável.

Os procedimentos usados por extend-if-consistent para manipular vinculações são definidos em 4.4.4.8.

Padrões com caudas pontilhadas

Se um padrão contiver um ponto seguido por uma variável de padrão, a variável de padrão corresponderá ao restante da lista de dados (em vez do próximo elemento da lista de dados), assim como seria de se esperar com a notação de cauda pontilhada descrita em Exercício 2.20. Embora o correspondente de padrões que implementamos não procure por pontos, ele se comporta como desejamos. Isso ocorre porque o primitivo read do Lisp, que é usado por query-driver-loop para ler a consulta e representá-la como uma estrutura de lista, trata pontos de uma maneira especial.

Quando read vê um ponto, em vez de fazer o próximo item ser o próximo elemento de uma lista (o car de um cons cujo cdr será o restante da lista), ele faz o próximo item ser o cdr da estrutura de lista. Por exemplo, a estrutura de lista produzida por read para o padrão (computer ?type) poderia ser construída avaliando a expressão (cons 'computer (cons '?type '())), e aquela para (computer . ?type) poderia ser construída avaliando a expressão (cons 'computer '?type).

Assim, conforme pattern-match compara recursivamente cars e cdrs de uma lista de dados e um padrão que tinha um ponto, ele eventualmente corresponde a variável após o ponto (que é um cdr do padrão) contra uma sublista da lista de dados, vinculando a variável a essa lista. Por exemplo, correspondendo o padrão (computer . ?type) contra (computer programmer trainee) corresponderá ?type à lista (programmer trainee).

4.4.4.4Regras e Unificação

Apply-rules é o análogo de regras de find-assertions (4.4.4.3). Ele recebe como entrada um padrão e um quadro, e forma um fluxo de quadros estendidos aplicando regras do banco de dados. Stream-flatmap mapeia apply-a-rule ao longo do fluxo de regras possivelmente aplicáveis (selecionadas por fetch-rules, 4.4.4.5) e combina os fluxos resultantes de quadros.

(define (apply-rules pattern frame)
              (stream-flatmap 
               (lambda (rule)
                 (apply-a-rule rule pattern frame))
               (fetch-rules pattern frame)))

Apply-a-rule aplica regras usando o método delineado em 4.4.2. Ele primeiro aumenta seu quadro de argumentos unificando a conclusão da regra com o padrão no quadro dado. Se isso for bem-sucedido, ele avalia o corpo da regra neste novo quadro.

Antes que qualquer uma dessas coisas aconteça, no entanto, o programa renomeia todas as variáveis na regra com novos nomes únicos. A razão para isso é evitar que as variáveis para diferentes aplicações de regras se confundam umas com as outras. Por exemplo, se duas regras usarem uma variável chamada ?x, então cada uma pode adicionar uma vinculação para ?x ao quadro quando for aplicada. Esses dois ?x não têm nada a ver um com o outro, e não devemos ser enganados pensando que as duas vinculações devem ser consistentes. Em vez de renomear variáveis, poderíamos criar uma estrutura de ambiente mais inteligente; no entanto, a abordagem de renomeação que escolhemos aqui é a mais direta, mesmo que não seja a mais eficiente. (Veja Exercício 4.79.) Aqui está o procedimento apply-a-rule:

(define (apply-a-rule rule
                                  query-pattern
                                  query-frame)
              (let ((clean-rule 
                     (rename-variables-in rule)))
                (let ((unify-result
                       (unify-match query-pattern
                                    (conclusion clean-rule)
                                    query-frame)))
                  (if (eq? unify-result 'failed)
                      the-empty-stream
                      (qeval (rule-body clean-rule)
                             (singleton-stream 
                              unify-result))))))

Os seletores rule-body e conclusion que extraem partes de uma regra são definidos em 4.4.4.7.

Geramos nomes de variáveis únicos associando um identificador único (como um número) a cada aplicação de regra e combinando esse identificador com os nomes de variáveis originais. Por exemplo, se o identificador de aplicação de regra for 7, podemos mudar cada ?x na regra para ?x-7 e cada ?y na regra para ?y-7. (Make-new-variable e new-rule-application-id são incluídos com os procedimentos de sintaxe em 4.4.4.7.)

(define (rename-variables-in rule)
              (let ((rule-application-id 
                     (new-rule-application-id)))
                (define (tree-walk exp)
                  (cond ((var? exp)
                         (make-new-variable 
                          exp 
                          rule-application-id))
                        ((pair? exp)
                         (cons (tree-walk (car exp))
                               (tree-walk (cdr exp))))
                        (else exp)))
                (tree-walk rule)))

O algoritmo de unificação é implementado como um procedimento que recebe como entradas dois padrões e um quadro e retorna ou o quadro estendido ou o símbolo failed. O unificador é como o correspondente de padrões, exceto que ele é simétrico—variáveis são permitidas em ambos os lados da correspondência. Unify-match é basicamente o mesmo que pattern-match, exceto que há código extra (marcado com “***” abaixo) para lidar com o caso em que o objeto no lado direito da correspondência é uma variável.

(define (unify-match p1 p2 frame)
              (cond ((eq? frame 'failed) 'failed)
                    ((equal? p1 p2) frame)
                    ((var? p1)
                     (extend-if-possible p1 p2 frame))
                    ((var? p2)
                     (extend-if-possible 
                      p2 
                      p1 
                      frame))        ; ***
                    ((and (pair? p1) 
                          (pair? p2))
                     (unify-match 
                      (cdr p1) 
                      (cdr p2)
                      (unify-match 
                       (car p1)
                       (car p2)
                       frame)))
                    (else 'failed)))

Na unificação, assim como na correspondência de padrões unilateral, queremos aceitar uma proposta de extensão do quadro apenas se ela for consistente com as vinculações existentes. O procedimento extend-if-possible usado na unificação é o mesmo que o extend-if-consistent usado na correspondência de padrões, exceto por duas verificações especiais, marcadas com “***” no programa abaixo. No primeiro caso, se a variável que estamos tentando corresponder não estiver vinculada, mas o valor que estamos tentando corresponder for ele mesmo uma (diferente) variável, é necessário verificar se o valor está vinculado, e se estiver, corresponder seu valor. Se ambas as partes da correspondência não estiverem vinculadas, podemos vincular qualquer uma à outra.

A segunda verificação lida com tentativas de vincular uma variável a um padrão que inclui essa variável. Tal situação pode ocorrer sempre que uma variável é repetida em ambos os padrões. Considere, por exemplo, unificar os dois padrões (?x ?x) e (?y ⟨expressão envolvendo ?y⟩) em um quadro onde ambos ?x e ?y não estão vinculados. Primeiro ?x é correspondido contra ?y, fazendo uma vinculação de ?x a ?y. Em seguida, o mesmo ?x é correspondido contra a expressão dada envolvendo ?y. Como ?x já está vinculado a ?y, isso resulta em corresponder ?y contra a expressão. Se pensarmos no unificador como encontrando um conjunto de valores para as variáveis de padrão que tornam os padrões iguais, então esses padrões implicam instruções para encontrar um ?y tal que ?y seja igual a a expressão envolvendo ?y. Não há um método geral para resolver tais equações, então rejeitamos tais vinculações; esses casos são reconhecidos pelo predicado depends-on?.²⁸⁴ Por outro lado, não queremos rejeitar tentativas de vincular uma variável a si mesma. Por exemplo, considere unificar (?x ?x) e (?y ?y). A segunda tentativa de vincular ?x a ?y corresponde ?y (o valor armazenado de ?x) contra ?y (o novo valor de ?x). Isso é tratado pela cláusula equal? de unify-match.

(define (extend-if-possible var val frame)
              (let ((binding (binding-in-frame var frame)))
                (cond (binding
                       (unify-match
                        (binding-value binding) val frame))
                      ((var? val)                   ; ***
                       (let ((binding 
                              (binding-in-frame 
                               val
                               frame)))
                         (if binding
                             (unify-match
                              var 
                              (binding-value binding) 
                              frame)
                             (extend var val frame))))
                      ((depends-on? val var frame)  ; ***
                       'failed)
                      (else (extend var val frame)))))

Depends-on? é um predicado que testa se uma expressão proposta para ser o valor de uma variável de padrão depende da variável. Isso deve ser feito relativamente ao quadro atual porque a expressão pode conter ocorrências de uma variável que já tem um valor que depende de nossa variável de teste. A estrutura de depends-on? é uma simples caminhada recursiva em árvore na qual substituímos pelos valores das variáveis sempre que necessário.

(define (depends-on? exp var frame)
              (define (tree-walk e)
                (cond ((var? e)
                       (if (equal? var e)
                           true
                           (let
                             ((b (binding-in-frame 
                                  e 
                                  frame)))
                              (if b
                                  (tree-walk 
                                   (binding-value b))
                                  false))))
                      ((pair? e)
                       (or (tree-walk (car e))
                           (tree-walk (cdr e))))
                      (else false)))
              (tree-walk exp))

4.4.4.5Mantendo o Banco de Dados

Um problema importante no projeto de linguagens de programação lógica é o de organizar as coisas de forma que o menor número possível de entradas irrelevantes no banco de dados seja examinado ao verificar um determinado padrão. Em nosso sistema, além de armazenar todas as asserções em um grande fluxo, armazenamos todas as asserções cujos cars são símbolos constantes em fluxos separados, em uma tabela indexada pelo símbolo. Para buscar uma asserção que pode corresponder a um padrão, primeiro verificamos se o car do padrão é um símbolo constante. Se for, retornamos (para serem testados usando o correspondente) todas as asserções armazenadas que têm o mesmo car. Se o car do padrão não for um símbolo constante, retornamos todas as asserções armazenadas. Métodos mais inteligentes também poderiam tirar vantagem de informações no quadro, ou tentar otimizar o caso em que o car do padrão não é um símbolo constante. Evitamos construir nossos critérios para indexação (usando o car, lidando apenas com o caso de símbolos constantes) no programa; em vez disso, chamamos predicados e seletores que incorporam nossos critérios.

(define THE-ASSERTIONS the-empty-stream)
            
            (define (fetch-assertions pattern frame)
              (if (use-index? pattern)
                  (get-indexed-assertions pattern)
                  (get-all-assertions)))
            
            (define (get-all-assertions) THE-ASSERTIONS)
            
            (define (get-indexed-assertions pattern)
              (get-stream (index-key-of pattern)
                          'assertion-stream))

Get-stream procura um fluxo na tabela e retorna um fluxo vazio se nada estiver armazenado lá.

(define (get-stream key1 key2)
              (let ((s (get key1 key2)))
                (if s s the-empty-stream)))

As regras são armazenadas de forma semelhante, usando o car da conclusão da regra. As conclusões das regras são padrões arbitrários, no entanto, então elas diferem das asserções em que podem conter variáveis. Um padrão cujo car é um símbolo constante pode corresponder a regras cujas conclusões começam com uma variável, bem como regras cujas conclusões têm o mesmo car que o padrão. Assim, ao buscar regras que podem corresponder a um padrão cujo car é um símbolo constante, buscamos todas as regras cujas conclusões começam com uma variável, bem como aquelas cujas conclusões têm o mesmo car que o padrão. Para esse propósito, armazenamos todas as regras cujas conclusões começam com uma variável em um fluxo separado em nossa tabela, indexado pelo símbolo ?.

(define THE-RULES the-empty-stream)
            
            (define (fetch-rules pattern frame)
              (if (use-index? pattern)
                  (get-indexed-rules pattern)
                  (get-all-rules)))
            
            (define (get-all-rules) THE-RULES)
            
            (define (get-indexed-rules pattern)
              (stream-append
               (get-stream (index-key-of pattern)
                           'rule-stream)
               (get-stream '? 'rule-stream)))

Add-rule-or-assertion! é usado por query-driver-loop para adicionar asserções e regras ao banco de dados. Cada item é armazenado no índice, se apropriado, e em um fluxo de todas as asserções ou regras no banco de dados.

(define (add-rule-or-assertion! assertion)
              (if (rule? assertion)
                  (add-rule! assertion)
                  (add-assertion! assertion)))
            
            (define (add-assertion! assertion)
              (store-assertion-in-index assertion)
              (let ((old-assertions THE-ASSERTIONS))
                (set! THE-ASSERTIONS
                      (cons-stream assertion 
                                   old-assertions))
                'ok))
            
            (define (add-rule! rule)
              (store-rule-in-index rule)
              (let ((old-rules THE-RULES))
                (set! THE-RULES
                      (cons-stream rule old-rules))
                'ok))

Para realmente armazenar uma asserção ou uma regra, verificamos se ela pode ser indexada. Se puder, a armazenamos no fluxo apropriado.

(define (store-assertion-in-index assertion)
              (if (indexable? assertion)
                  (let ((key (index-key-of assertion)))
                    (let ((current-assertion-stream
                           (get-stream 
                            key 'assertion-stream)))
                      (put key
                           'assertion-stream
                           (cons-stream 
                            assertion
                            current-assertion-stream))))))
            
            (define (store-rule-in-index rule)
              (let ((pattern (conclusion rule)))
                (if (indexable? pattern)
                    (let ((key (index-key-of pattern)))
                      (let ((current-rule-stream
                             (get-stream 
                              key 'rule-stream)))
                        (put key
                             'rule-stream
                             (cons-stream 
                              rule
                              current-rule-stream)))))))

Os procedimentos a seguir definem como o índice do banco de dados é usado. Um padrão (uma asserção ou uma conclusão de regra) será armazenado na tabela se começar com uma variável ou um símbolo constante.

(define (indexable? pat)
              (or (constant-symbol? (car pat))
                  (var? (car pat))))

A chave sob a qual um padrão é armazenado na tabela é ? (se ele começar com uma variável) ou o símbolo constante com o qual ele começa.

(define (index-key-of pat)
              (let ((key (car pat)))
                (if (var? key) '? key)))

O índice será usado para recuperar itens que podem corresponder a um padrão se o padrão começar com um símbolo constante.

(define (use-index? pat)
              (constant-symbol? (car pat)))

Exercício 4.70: Qual é o propósito das vinculações let nos procedimentos add-assertion! e add-rule!? O que estaria errado com a seguinte implementação de add-assertion!? Dica: Lembre-se da definição do fluxo infinito de uns em 3.5.2: (define ones (cons-stream 1 ones)).

(define (add-assertion! assertion)
              (store-assertion-in-index assertion)
              (set! THE-ASSERTIONS
                    (cons-stream assertion 
                                 THE-ASSERTIONS))
              'ok)

4.4.4.6Operações de Fluxo

O sistema de consultas usa algumas operações de fluxo que não foram apresentadas em Capítulo 3.

Stream-append-delayed e interleave-delayed são como stream-append e interleave (3.5.3), exceto que eles recebem um argumento atrasado (como o procedimento integral em 3.5.4). Isso adia o loop em alguns casos (veja Exercício 4.71).

(define (stream-append-delayed s1 delayed-s2)
              (if (stream-null? s1)
                  (force delayed-s2)
                  (cons-stream
                   (stream-car s1)
                   (stream-append-delayed (stream-cdr s1)
                                          delayed-s2))))
            
            (define (interleave-delayed s1 delayed-s2)
              (if (stream-null? s1)
                  (force delayed-s2)
                  (cons-stream
                   (stream-car s1)
                   (interleave-delayed 
                    (force delayed-s2)
                    (delay (stream-cdr s1))))))

Stream-flatmap, que é usado em todo o avaliador de consultas para mapear um procedimento sobre um fluxo de quadros e combinar os fluxos resultantes de quadros, é o análogo de fluxo do procedimento flatmap introduzido para listas ordinárias em 2.2.3. Ao contrário do flatmap ordinário, no entanto, acumulamos os fluxos com um processo de intercalação, em vez de simplesmente anexá-los (veja Exercício 4.72 e Exercício 4.73).

(define (stream-flatmap proc s)
              (flatten-stream (stream-map proc s)))
            
            (define (flatten-stream stream)
              (if (stream-null? stream)
                  the-empty-stream
                  (interleave-delayed
                   (stream-car stream)
                   (delay (flatten-stream
                           (stream-cdr stream))))))

O avaliador também usa o seguinte procedimento simples para gerar um fluxo consistindo de um único elemento:

(define (singleton-stream x)
              (cons-stream x the-empty-stream))

4.4.4.7Procedimentos de Sintaxe de Consulta

Type e contents, usados por qeval (4.4.4.2), especificam que uma forma especial é identificada pelo símbolo em seu car. Eles são os mesmos que os procedimentos type-tag e contents em 2.4.2, exceto pela mensagem de erro.

(define (type exp)
              (if (pair? exp)
                  (car exp)
                  (error "Unknown expression TYPE"
                         exp)))
            
            (define (contents exp)
              (if (pair? exp)
                  (cdr exp)
                  (error "Unknown expression CONTENTS"
                         exp)))

Os seguintes procedimentos, usados por query-driver-loop (em 4.4.4.1), especificam que regras e asserções são adicionadas ao banco de dados por expressões da forma (assert! ⟨regra-ou-asserção⟩):

(define (assertion-to-be-added? exp)
              (eq? (type exp) 'assert!))
            
            (define (add-assertion-body exp)
              (car (contents exp)))

Aqui estão as definições de sintaxe para as formas especiais and, or, not e lisp-value (4.4.4.2):

(define (empty-conjunction? exps) (null? exps))
            (define (first-conjunct exps) (car exps))
            (define (rest-conjuncts exps) (cdr exps))
            (define (empty-disjunction? exps) (null? exps))
            (define (first-disjunct exps) (car exps))
            (define (rest-disjuncts exps) (cdr exps))
            (define (negated-query exps) (car exps))
            (define (predicate exps) (car exps))
            (define (args exps) (cdr exps))

Os seguintes três procedimentos definem a sintaxe das regras:

(define (rule? statement)
              (tagged-list? statement 'rule))
            
            (define (conclusion rule) (cadr rule))
            
            (define (rule-body rule)
              (if (null? (cddr rule))
                  '(always-true)
                  (caddr rule)))

Query-driver-loop (4.4.4.1) chama query-syntax-process para transformar variáveis de padrão na expressão, que têm a forma ?symbol, no formato interno (? symbol). Ou seja, um padrão como (job ?x ?y) é realmente representado internamente pelo sistema como (job (? x) (? y)). Isso aumenta a eficiência do processamento de consultas, pois significa que o sistema pode verificar se uma expressão é uma variável de padrão verificando se o car da expressão é o símbolo ?, em vez de ter que extrair caracteres do símbolo. A transformação de sintaxe é realizada pelo seguinte procedimento:²⁸⁵

(define (query-syntax-process exp)
              (map-over-symbols expand-question-mark exp))
            
            (define (map-over-symbols proc exp)
              (cond ((pair? exp)
                     (cons (map-over-symbols 
                            proc (car exp))
                           (map-over-symbols 
                            proc (cdr exp))))
                    ((symbol? exp) (proc exp))
                    (else exp)))
            
            (define (expand-question-mark symbol)
              (let ((chars (symbol->string symbol)))
                (if (string=? (substring chars 0 1) "?")
                    (list '? (string->symbol
                              (substring
                               chars 
                               1 
                               (string-length chars))))
                    symbol)))

Uma vez que as variáveis são transformadas dessa forma, as variáveis em um padrão são listas começando com ?, e os símbolos constantes (que precisam ser reconhecidos para indexação do banco de dados, 4.4.4.5) são apenas os símbolos.

(define (var? exp) (tagged-list? exp '?))
            (define (constant-symbol? exp) (symbol? exp))

Variáveis únicas são construídas durante a aplicação de regras (em 4.4.4.4) por meio dos seguintes procedimentos. O identificador único para uma aplicação de regra é um número, que é incrementado cada vez que uma regra é aplicada.

(define rule-counter 0)
            
            (define (new-rule-application-id)
              (set! rule-counter (+ 1 rule-counter))
              rule-counter)
            
            (define (make-new-variable 
                     var rule-application-id)
              (cons '? (cons rule-application-id
                             (cdr var))))

Quando query-driver-loop instancia a consulta para imprimir a resposta, ele converte quaisquer variáveis de padrão não vinculadas de volta para a forma correta para impressão, usando

(define (contract-question-mark variable)
              (string->symbol
               (string-append "?"
                 (if (number? (cadr variable))
                     (string-append
                      (symbol->string (caddr variable))
                      "-"
                      (number->string (cadr variable)))
                     (symbol->string (cadr variable))))))

4.4.4.8Quadros e Vinculações

Quadros são representados como listas de vinculações, que são pares variável-valor:

(define (make-binding variable value)
              (cons variable value))
            
            (define (binding-variable binding)
              (car binding))
            
            (define (binding-value binding)
              (cdr binding))
            
            (define (binding-in-frame variable frame)
              (assoc variable frame))
            
            (define (extend variable value frame)
              (cons (make-binding variable value) frame))

Exercício 4.71: Louis Reasoner se pergunta por que os procedimentos simple-query e disjoin (4.4.4.2) são implementados usando operações explícitas de delay, em vez de serem definidos como segue:

(define (simple-query 
                     query-pattern frame-stream)
              (stream-flatmap
               (lambda (frame)
                 (stream-append
                  (find-assertions query-pattern frame)
                  (apply-rules query-pattern frame)))
               frame-stream))
            
            (define (disjoin disjuncts frame-stream)
              (if (empty-disjunction? disjuncts)
                  the-empty-stream
                  (interleave
                   (qeval (first-disjunct disjuncts)
                          frame-stream)
                   (disjoin (rest-disjuncts disjuncts)
                            frame-stream))))

Você pode dar exemplos de consultas onde essas definições mais simples levariam a comportamentos indesejáveis?

Exercício 4.72: Por que disjoin e stream-flatmap intercalam os fluxos em vez de simplesmente anexá-los? Dê exemplos que ilustrem por que a intercalação funciona melhor. (Dica: Por que usamos interleave em 3.5.3?)

Exercício 4.73: Por que flatten-stream usa delay explicitamente? O que estaria errado com defini-lo como segue:

(define (flatten-stream stream)
              (if (stream-null? stream)
                  the-empty-stream
                  (interleave (stream-car stream)
                              (flatten-stream 
                               (stream-cdr stream)))))

Exercício 4.74: Alyssa P. Hacker propõe usar uma versão mais simples de stream-flatmap em negate, lisp-value, e find-assertions. Ela observa que o procedimento que é mapeado sobre o fluxo de quadros nesses casos sempre produz ou o fluxo vazio ou um fluxo de um único elemento, então nenhuma intercalação é necessária ao combinar esses fluxos.

1. Preencha as expressões ausentes no programa de Alyssa.

   (define (simple-stream-flatmap proc s)
                 (simple-flatten (stream-map proc s)))
               
               (define (simple-flatten stream)
                 (stream-map ⟨??⟩
                             (stream-filter ⟨??⟩ 
                                            stream)))

2. O comportamento do sistema de consultas muda se o alterarmos dessa forma?

Exercício 4.75: Implemente para a linguagem de consulta uma nova forma especial chamada unique. Unique deve ter sucesso se houver exatamente um item no banco de dados que satisfaça uma consulta especificada. Por exemplo,

(unique (job ?x (computer wizard)))

deve imprimir o fluxo de um único elemento

(unique (job (Bitdiddle Ben)
                         (computer wizard)))

já que Ben é o único mago da computação, e

(unique (job ?x (computer programmer)))

deve imprimir o fluxo vazio, já que há mais de um programador de computador. Além disso,

(and (job ?x ?j) 
                 (unique (job ?anyone ?j)))

deve listar todos os empregos que são preenchidos por apenas uma pessoa, e as pessoas que os preenchem.

Há duas partes para implementar unique. A primeira é escrever um procedimento que lida com essa forma especial, e a segunda é fazer qeval despachar para esse procedimento. A segunda parte é trivial, já que qeval faz seu despacho de forma direcionada por dados. Se seu procedimento for chamado uniquely-asserted, tudo o que você precisa fazer é

(put 'unique 'qeval uniquely-asserted)

e qeval despachará para esse procedimento para cada consulta cujo type (car) seja o símbolo unique.

O verdadeiro problema é escrever o procedimento uniquely-asserted. Ele deve receber como entrada o contents (cdr) da consulta unique, junto com um fluxo de quadros. Para cada quadro no fluxo, ele deve usar qeval para encontrar o fluxo de todas as extensões ao quadro que satisfazem a consulta dada. Qualquer fluxo que não tenha exatamente um item nele deve ser eliminado. Os fluxos restantes devem ser passados de volta para serem acumulados em um grande fluxo que é o resultado da consulta unique. Isso é semelhante à implementação da forma especial not.

Teste sua implementação formando uma consulta que liste todas as pessoas que supervisionam exatamente uma pessoa.

Exercício 4.76: Nossa implementação de and como uma combinação em série de consultas (Figura 4.5) é elegante, mas é ineficiente porque, ao processar a segunda consulta do and, devemos varrer o banco de dados para cada quadro produzido pela primeira consulta. Se o banco de dados tiver $n$ elementos, e uma consulta típica produzir um número de quadros de saída proporcional a $n$ (digamos $n/k$), então varrer o banco de dados para cada quadro produzido pela primeira consulta exigirá $n^2/k$ chamadas ao correspondente de padrões. Outra abordagem seria processar as duas cláusulas do and separadamente, então procurar por todos os pares de quadros de saída que são compatíveis. Se cada consulta produzir $n/k$ quadros de saída, então isso significa que devemos realizar $n^2/k^2$ verificações de compatibilidade—um fator de $k$ menor que o número de correspondências exigidas em nosso método atual.

Desenvolva uma implementação de and que use essa estratégia. Você deve implementar um procedimento que receba dois quadros como entradas, verifique se as vinculações nos quadros são compatíveis e, se forem, produza um quadro que mescle os dois conjuntos de vinculações. Essa operação é semelhante à unificação.

Exercício 4.77: Em 4.4.3 vimos que not e lisp-value podem fazer com que a linguagem de consulta dê respostas “erradas” se essas operações de filtragem forem aplicadas a quadros nos quais as variáveis não estão vinculadas. Desenvolva uma maneira de corrigir essa deficiência. Uma ideia é realizar a filtragem de forma “atrasada” anexando ao quadro uma “promessa” de filtrar que é cumprida apenas quando variáveis suficientes tiverem sido vinculadas para tornar a operação possível. Poderíamos esperar para realizar a filtragem até que todas as outras operações tivessem sido realizadas. No entanto, por questões de eficiência, gostaríamos de realizar a filtragem o mais cedo possível para reduzir o número de quadros intermediários gerados.

Exercício 4.78: Redesenhe a linguagem de consulta como um programa não determinístico a ser implementado usando o avaliador de 4.3, em vez de como um processo de fluxo. Nessa abordagem, cada consulta produzirá uma única resposta (em vez do fluxo de todas as respostas) e o usuário poderá digitar try-again para ver mais respostas. Você deve descobrir que muito do mecanismo que construímos nesta seção é subsumido pela busca não determinística e retrocesso. Você provavelmente também descobrirá, no entanto, que sua nova linguagem de consulta tem diferenças sutis de comportamento em relação à implementada aqui. Você pode encontrar exemplos que ilustram essa diferença?

Exercício 4.79: Quando implementamos o avaliador Lisp em 4.1, vimos como usar ambientes locais para evitar conflitos de nomes entre os parâmetros de procedimentos. Por exemplo, ao avaliar

(define (square x) 
              (* x x))
            
            (define (sum-of-squares x y)
              (+ (square x) (square y)))
            
            (sum-of-squares 3 4)

não há confusão entre o x em square e o x em sum-of-squares, porque avaliamos o corpo de cada procedimento em um ambiente que é especialmente construído para conter vinculações para as variáveis locais. No sistema de consultas, usamos uma estratégia diferente para evitar conflitos de nomes ao aplicar regras. Cada vez que aplicamos uma regra, renomeamos as variáveis com novos nomes que são garantidos como únicos. A estratégia análoga para o avaliador Lisp seria abolir ambientes locais e simplesmente renomear as variáveis no corpo de um procedimento cada vez que aplicamos o procedimento.

Implemente para a linguagem de consulta um método de aplicação de regras que use ambientes em vez de renomeação. Veja se você pode construir sobre sua estrutura de ambiente para criar construções na linguagem de consulta para lidar com grandes sistemas, como o análogo de regras de procedimentos com estrutura de blocos. Você pode relacionar algo disso ao problema de fazer deduções em um contexto (por exemplo, “Se eu supor que $P$ fosse verdadeiro, então eu seria capaz de deduzir $A$ e $B$.”) como um método de resolução de problemas? (Este problema é aberto. Uma boa resposta provavelmente vale um Ph.D.)