4.3Variações em um Esquema — Computação Não Determinística

Nesta seção, estendemos o avaliador de Scheme para suportar um paradigma de programação chamado computação não determinística, incorporando ao avaliador um mecanismo que suporta busca automática. Esta é uma mudança muito mais profunda na linguagem do que a introdução da avaliação preguiçosa na 4.2.

A computação não determinística, assim como o processamento de fluxos, é útil para aplicações de "gerar e testar". Considere a tarefa de começar com duas listas de números inteiros positivos e encontrar um par de inteiros — um da primeira lista e outro da segunda — cuja soma seja um número primo. Vimos como lidar com isso usando operações de sequência finita na 2.2.3 e com fluxos infinitos na 3.5.3. Nossa abordagem foi gerar a sequência de todos os pares possíveis e filtrá-los para selecionar os pares cuja soma é um número primo. Se realmente geramos toda a sequência de pares primeiro, como na Capítulo 2, ou intercalamos a geração e a filtragem, como na Capítulo 3, é irrelevante para a imagem essencial de como a computação é organizada.

A abordagem não determinística evoca uma imagem diferente. Imagine simplesmente que escolhemos (de alguma forma) um número da primeira lista e um número da segunda lista e exigimos (usando algum mecanismo) que a soma deles seja um número primo. Isso é expresso pelo seguinte procedimento:

(define (prime-sum-pair list1 list2)
  (let ((a (an-element-of list1))
        (b (an-element-of list2)))
    (require (prime? (+ a b)))
    (list a b)))

Pode parecer que este procedimento apenas reformula o problema, em vez de especificar uma maneira de resolvê-lo. No entanto, este é um programa não determinístico legítimo.²⁴⁶

A ideia-chave aqui é que expressões em uma linguagem não determinística podem ter mais de um valor possível. Por exemplo, an-element-of pode retornar qualquer elemento da lista fornecida. Nosso avaliador de programas não determinísticos funcionará escolhendo automaticamente um valor possível e rastreando a escolha. Se um requisito subsequente não for atendido, o avaliador tentará uma escolha diferente e continuará tentando novas escolhas até que a avaliação seja bem-sucedida ou até que acabem as escolhas. Assim como o avaliador preguiçoso libertou o programador dos detalhes de como os valores são atrasados e forçados, o avaliador de programas não determinísticos libertará o programador dos detalhes de como as escolhas são feitas.

É instrutivo contrastar as diferentes imagens de tempo evocadas pela avaliação não determinística e pelo processamento de fluxos. O processamento de fluxos usa avaliação preguiçosa para desacoplar o tempo em que o fluxo de respostas possíveis é montado do tempo em que os elementos reais do fluxo são produzidos. O avaliador suporta a ilusão de que todas as respostas possíveis estão dispostas diante de nós em uma sequência atemporal. Com a avaliação não determinística, uma expressão representa a exploração de um conjunto de mundos possíveis, cada um determinado por um conjunto de escolhas. Alguns dos mundos possíveis levam a becos sem saída, enquanto outros têm valores úteis. O avaliador de programas não determinísticos suporta a ilusão de que o tempo se ramifica e que nossos programas têm diferentes históricos de execução possíveis. Quando chegamos a um beco sem saída, podemos revisitar um ponto de escolha anterior e prosseguir por um ramo diferente.

O avaliador de programas não determinísticos implementado abaixo é chamado de avaliador amb porque é baseado em uma nova forma especial chamada amb. Podemos digitar a definição acima de prime-sum-pair no loop de controle do avaliador amb (junto com as definições de prime?, an-element-of e require) e executar o procedimento da seguinte forma:

;;; Entrada do Amb-Eval:
(prime-sum-pair '(1 3 5 8) '(20 35 110))

;;; Iniciando um novo problema
;;; Valor do Amb-Eval:
(3 20)

O valor retornado foi obtido após o avaliador repetidamente escolher elementos de cada uma das listas, até que uma escolha bem-sucedida foi feita.

A seção 4.3.1 introduz amb e explica como ele suporta o não determinismo através do mecanismo de busca automática do avaliador. A 4.3.2 apresenta exemplos de programas não determinísticos, e a 4.3.3 fornece os detalhes de como implementar o avaliador amb modificando o avaliador comum de Scheme.

4.3.1Amb e Busca

Para estender o Scheme para suportar não determinismo, introduzimos uma nova forma especial chamada amb.²⁴⁷ A expressão

(amb ⟨e₁⟩ ⟨e₂⟩ … ⟨eₙ⟩)

retorna o valor de uma das $n$ expressões $⟨e_i⟩$ "ambigamente". Por exemplo, a expressão

(list (amb 1 2 3) (amb 'a 'b))

pode ter seis valores possíveis:

(1 a) (1 b) (2 a) (2 b) (3 a) (3 b)

Amb com uma única escolha produz um valor comum (único).

Amb sem escolhas — a expressão (amb) — é uma expressão sem valores aceitáveis. Operacionalmente, podemos pensar em (amb) como uma expressão que, quando avaliada, faz com que a computação "falhe": a computação é abortada e nenhum valor é produzido. Usando essa ideia, podemos expressar o requisito de que uma expressão de predicado específica p deve ser verdadeira da seguinte forma:

(define (require p)
  (if (not p) (amb)))

Com amb e require, podemos implementar o procedimento an-element-of usado acima:

(define (an-element-of items)
  (require (not (null? items)))
  (amb (car items) 
       (an-element-of (cdr items))))

An-element-of falha se a lista estiver vazia. Caso contrário, ele retorna ambiguamente o primeiro elemento da lista ou um elemento escolhido do resto da lista.

Também podemos expressar intervalos infinitos de escolhas. O seguinte procedimento potencialmente retorna qualquer número inteiro maior ou igual a algum $n$ dado:

(define (an-integer-starting-from n)
  (amb n (an-integer-starting-from (+ n 1))))

Isso é semelhante ao procedimento de fluxo integers-starting-from descrito na 3.5.2, mas com uma diferença importante: o procedimento de fluxo retorna um objeto que representa a sequência de todos os números inteiros começando com $n$, enquanto o procedimento amb retorna um único número inteiro.²⁴⁸

Abstratamente, podemos imaginar que avaliar uma expressão amb faz com que o tempo se ramifique em ramos, onde a computação continua em cada ramo com um dos valores possíveis da expressão. Dizemos que amb representa um ponto de escolha não determinístico. Se tivéssemos uma máquina com um número suficiente de processadores que pudessem ser alocados dinamicamente, poderíamos implementar a busca de maneira direta. A execução prosseguiria como em uma máquina sequencial, até que uma expressão amb fosse encontrada. Nesse ponto, mais processadores seriam alocados e inicializados para continuar todas as execuções paralelas implícitas pela escolha. Cada processador prosseguiria sequencialmente como se fosse a única escolha, até que terminasse ao encontrar uma falha, ou subdividisse ainda mais, ou terminasse.²⁴⁹

Por outro lado, se tivermos uma máquina que pode executar apenas um processo (ou alguns processos concorrentes), devemos considerar as alternativas sequencialmente. Poderíamos imaginar modificar um avaliador para escolher aleatoriamente um ramo a seguir sempre que encontrar um ponto de escolha. No entanto, a escolha aleatória pode facilmente levar a valores que falham. Poderíamos tentar executar o avaliador repetidamente, fazendo escolhas aleatórias e esperando encontrar um valor que não falhe, mas é melhor buscar sistematicamente todos os caminhos de execução possíveis. O avaliador amb que desenvolveremos e trabalharemos nesta seção implementa uma busca sistemática da seguinte forma: quando o avaliador encontra uma aplicação de amb, ele inicialmente seleciona a primeira alternativa. Essa seleção pode levar a uma nova escolha. O avaliador sempre escolherá inicialmente a primeira alternativa em cada ponto de escolha. Se uma escolha resultar em uma falha, o avaliador automaticamente²⁵⁰ retrocede ao ponto de escolha mais recente e tenta a próxima alternativa. Se ele esgotar as alternativas em qualquer ponto de escolha, o avaliador retrocederá ao ponto de escolha anterior e retomará a partir daí. Esse processo leva a uma estratégia de busca conhecida como busca em profundidade ou retrocesso cronológico.²⁵¹

Loop de Controle

O loop de controle para o avaliador amb tem algumas propriedades incomuns. Ele lê uma expressão e imprime o valor da primeira execução bem-sucedida, como no exemplo prime-sum-pair mostrado acima. Se quisermos ver o valor da próxima execução bem-sucedida, podemos pedir ao interpretador para retroceder e tentar gerar uma segunda execução bem-sucedida. Isso é sinalizado digitando o símbolo try-again. Se qualquer expressão exceto try-again for fornecida, o interpretador iniciará um novo problema, descartando as alternativas não exploradas no problema anterior. Aqui está uma interação de exemplo:

;;; Entrada do Amb-Eval:
(prime-sum-pair '(1 3 5 8) '(20 35 110))

;;; Iniciando um novo problema
;;; Valor do Amb-Eval:
(3 20)

;;; Entrada do Amb-Eval:
try-again

;;; Valor do Amb-Eval:
(3 110)

;;; Entrada do Amb-Eval:
try-again

;;; Valor do Amb-Eval:
(8 35)

;;; Entrada do Amb-Eval:
try-again

;;; Não há mais valores de
(prime-sum-pair 
 (quote (1 3 5 8)) 
 (quote (20 35 110)))

;;; Entrada do Amb-Eval:
(prime-sum-pair '(19 27 30) '(11 36 58))

;;; Iniciando um novo problema
;;; Valor do Amb-Eval:
(30 11)

Exercício 4.35: Escreva um procedimento an-integer-between que retorna um número inteiro entre dois limites dados. Isso pode ser usado para implementar um procedimento que encontra triplas pitagóricas, ou seja, triplas de números inteiros $(i,j,k)$ entre os limites dados, tais que $i\le j$ e $i^2+j^2=k^2$, da seguinte forma:

(define (a-pythagorean-triple-between low high)
  (let ((i (an-integer-between low high)))
    (let ((j (an-integer-between i high)))
      (let ((k (an-integer-between j high)))
        (require (= (+ (* i i) (* j j)) 
                    (* k k)))
        (list i j k)))))

Exercício 4.36: O Exercício 3.69 discutiu como gerar o fluxo de todas as triplas pitagóricas, sem limite superior no tamanho dos números inteiros a serem pesquisados. Explique por que simplesmente substituir an-integer-between por an-integer-starting-from no procedimento do Exercício 4.35 não é uma maneira adequada de gerar triplas pitagóricas arbitrárias. Escreva um procedimento que realmente fará isso. (Ou seja, escreva um procedimento para o qual digitar repetidamente try-again geraria, em princípio, todas as triplas pitagóricas.)

Exercício 4.37: Ben Bitdiddle afirma que o seguinte método para gerar triplas pitagóricas é mais eficiente do que o do Exercício 4.35. Ele está correto? (Dica: Considere o número de possibilidades que devem ser exploradas.)

(define (a-pythagorean-triple-between low high)
  (let ((i (an-integer-between low high))
        (hsq (* high high)))
    (let ((j (an-integer-between i high)))
      (let ((ksq (+ (* i i) (* j j))))
        (require (>= hsq ksq))
        (let ((k (sqrt ksq)))
          (require (integer? k))
          (list i j k))))))

4.3.2Exemplos de Programas Não Determinísticos

A seção 4.3.3 descreve a implementação do avaliador amb. Primeiro, no entanto, damos alguns exemplos de como ele pode ser usado. A vantagem da programação não determinística é que podemos suprimir os detalhes de como a busca é realizada, expressando nossos programas em um nível mais alto de abstração.

Quebra-Cabeças Lógicos

O seguinte quebra-cabeça (tirado de Dinesman 1968) é típico de uma grande classe de quebra-cabeças lógicos simples:

Baker, Cooper, Fletcher, Miller e Smith moram em diferentes andares de um prédio de apartamentos que contém apenas cinco andares. Baker não mora no último andar. Cooper não mora no primeiro andar. Fletcher não mora nem no último nem no primeiro andar. Miller mora em um andar mais alto que Cooper. Smith não mora em um andar adjacente ao de Fletcher. Fletcher não mora em um andar adjacente ao de Cooper. Onde cada um mora?

Podemos determinar quem mora em cada andar de maneira direta, enumerando todas as possibilidades e impondo as restrições dadas:²⁵²

(define (multiple-dwelling)
  (let ((baker (amb 1 2 3 4 5))
        (cooper (amb 1 2 3 4 5))
        (fletcher (amb 1 2 3 4 5))
        (miller (amb 1 2 3 4 5))
        (smith (amb 1 2 3 4 5)))
    (require
     (distinct? (list baker cooper fletcher 
                      miller smith)))
    (require (not (= baker 5)))
    (require (not (= cooper 1)))
    (require (not (= fletcher 5)))
    (require (not (= fletcher 1)))
    (require (> miller cooper))
    (require
     (not (= (abs (- smith fletcher)) 1)))
    (require 
     (not (= (abs (- fletcher cooper)) 1)))
    (list (list 'baker baker)
          (list 'cooper cooper)
          (list 'fletcher fletcher)
          (list 'miller miller)
          (list 'smith smith))))

Avaliar a expressão (multiple-dwelling) produz o resultado

((baker 3) (cooper 2) (fletcher 4)
 (miller 5) (smith 1))

Embora este procedimento simples funcione, ele é muito lento. O Exercício 4.39 e o Exercício 4.40 discutem algumas possíveis melhorias.

Exercício 4.38: Modifique o procedimento multiple-dwelling para omitir o requisito de que Smith e Fletcher não moram em andares adjacentes. Quantas soluções existem para este quebra-cabeça modificado?

Exercício 4.39: A ordem das restrições no procedimento multiple-dwelling afeta a resposta? Afeta o tempo para encontrar uma resposta? Se você acha que importa, demonstre um programa mais rápido obtido a partir do dado, reordenando as restrições. Se você acha que não importa, argumente seu caso.

Exercício 4.40: No problema de múltiplas moradias, quantos conjuntos de atribuições existem de pessoas para andares, tanto antes quanto depois do requisito de que as atribuições de andares sejam distintas? É muito ineficiente gerar todas as possíveis atribuições de pessoas para andares e depois deixar o retrocesso eliminá-las. Por exemplo, a maioria das restrições depende de apenas uma ou duas das variáveis de pessoa-andar e, portanto, pode ser imposta antes que os andares tenham sido selecionados para todas as pessoas. Escreva e demonstre um procedimento não determinístico muito mais eficiente que resolve este problema, baseado na geração apenas daquelas possibilidades que ainda não foram descartadas por restrições anteriores. (Dica: Isso exigirá um aninhamento de expressões let.)

Exercício 4.41: Escreva um programa comum de Scheme para resolver o quebra-cabeça de múltiplas moradias.

Exercício 4.42: Resolva o seguinte quebra-cabeça "Mentirosos" (de Phillips 1934):

Cinco alunas fizeram um exame. Seus pais — pensavam elas — mostraram um interesse excessivo no resultado. Elas, portanto, concordaram que, ao escrever para casa sobre o exame, cada uma faria uma afirmação verdadeira e uma falsa. As seguintes são as passagens relevantes de suas cartas:

• Betty: “Kitty foi a segunda no exame. Eu fiquei apenas em terceiro.”
• Ethel: “Você ficará feliz em saber que eu fiquei em primeiro. Joan foi a segunda.”
• Joan: “Eu fiquei em terceiro, e a pobre Ethel foi a última.”
• Kitty: “Eu fiquei em segundo. Mary foi apenas a quarta.”
• Mary: “Eu fiquei em quarto. O primeiro lugar foi ocupado por Betty.”

Qual foi, de fato, a ordem em que as cinco alunas ficaram?

Exercício 4.43: Use o avaliador amb para resolver o seguinte quebra-cabeça:²⁵³

O pai de Mary Ann Moore tem um iate, assim como cada um de seus quatro amigos: Coronel Downing, Sr. Hall, Sir Barnacle Hood e Dr. Parker. Cada um dos cinco também tem uma filha e cada um nomeou seu iate em homenagem à filha de um dos outros. O iate de Sir Barnacle é o Gabrielle, o Sr. Moore é dono do Lorna; o Sr. Hall é dono do Rosalind. O Melissa, de propriedade do Coronel Downing, é nomeado em homenagem à filha de Sir Barnacle. O pai de Gabrielle é dono do iate que é nomeado em homenagem à filha do Dr. Parker. Quem é o pai de Lorna?

Tente escrever o programa de forma que ele seja executado eficientemente (veja o Exercício 4.40). Também determine quantas soluções existem se não soubermos que o sobrenome de Mary Ann é Moore.

Exercício 4.44: O Exercício 2.42 descreveu o "quebra-cabeça das oito rainhas" de colocar rainhas em um tabuleiro de xadrez de forma que nenhuma ataque a outra. Escreva um programa não determinístico para resolver este quebra-cabeça.

Análise de Linguagem Natural

Programas projetados para aceitar linguagem natural como entrada geralmente começam tentando analisar a entrada, ou seja, combinar a entrada com alguma estrutura gramatical. Por exemplo, podemos tentar reconhecer frases simples consistindo de um artigo seguido por um substantivo seguido por um verbo, como "O gato come." Para realizar tal análise, devemos ser capazes de identificar as partes do discurso de palavras individuais. Poderíamos começar com algumas listas que classificam várias palavras:²⁵⁴

(define nouns 
  '(noun student professor cat class))

(define verbs 
  '(verb studies lectures eats sleeps))

(define articles '(article the a))

Também precisamos de uma gramática, ou seja, um conjunto de regras descrevendo como elementos gramaticais são compostos de elementos mais simples. Uma gramática muito simples pode estipular que uma frase sempre consiste em duas partes — uma frase nominal seguida por uma frase verbal — e que uma frase nominal consiste em um artigo seguido por um substantivo. Com essa gramática, a frase "O gato come" é analisada da seguinte forma:

(sentence
 (noun-phrase (article the) (noun cat))
 (verb eats))

Podemos gerar tal análise com um programa simples que tem procedimentos separados para cada uma das regras gramaticais. Para analisar uma frase, identificamos suas duas partes constituintes e retornamos uma lista desses dois elementos, marcados com o símbolo sentence:

(define (parse-sentence)
  (list 'sentence
         (parse-noun-phrase)
         (parse-word verbs)))

Uma frase nominal, de forma semelhante, é analisada encontrando um artigo seguido por um substantivo:

(define (parse-noun-phrase)
  (list 'noun-phrase
        (parse-word articles)
        (parse-word nouns)))

No nível mais baixo, a análise se resume a verificar repetidamente que a próxima palavra não analisada é um membro da lista de palavras para a parte do discurso necessária. Para implementar isso, mantemos uma variável global *unparsed*, que é a entrada que ainda não foi analisada. Cada vez que verificamos uma palavra, exigimos que *unparsed* não esteja vazia e que comece com uma palavra da lista designada. Se for o caso, removemos essa palavra de *unparsed* e retornamos a palavra junto com sua parte do discurso (que é encontrada no início da lista):²⁵⁵

(define (parse-word word-list)
  (require (not (null? *unparsed*)))
  (require (memq (car *unparsed*) 
                 (cdr word-list)))
  (let ((found-word (car *unparsed*)))
    (set! *unparsed* (cdr *unparsed*))
    (list (car word-list) found-word)))

Para iniciar a análise, tudo o que precisamos fazer é definir *unparsed* como a entrada completa, tentar analisar uma frase e verificar que nada sobrou:

(define *unparsed* '())
(define (parse input)
  (set! *unparsed* input)
  (let ((sent (parse-sentence)))
    (require (null? *unparsed*))
    sent))

Podemos agora testar o analisador e verificar que ele funciona para nossa frase de teste simples:

;;; Entrada do Amb-Eval:
(parse '(the cat eats))

;;; Iniciando um novo problema
;;; Valor do Amb-Eval:
(sentence 
 (noun-phrase (article the) (noun cat))
 (verb eats))

O avaliador amb é útil aqui porque é conveniente expressar as restrições de análise com a ajuda de require. A busca automática e o retrocesso realmente valem a pena, no entanto, quando consideramos gramáticas mais complexas onde há escolhas para como as unidades podem ser decompostas.

Vamos adicionar à nossa gramática uma lista de preposições:

(define prepositions 
  '(prep for to in by with))

e definir uma frase preposicional (por exemplo, "para o gato") como uma preposição seguida por uma frase nominal:

(define (parse-prepositional-phrase)
  (list 'prep-phrase
        (parse-word prepositions)
        (parse-noun-phrase)))

Agora podemos definir uma frase como uma frase nominal seguida por uma frase verbal, onde uma frase verbal pode ser um verbo ou uma frase verbal estendida por uma frase preposicional:²⁵⁶

(define (parse-sentence)
  (list 'sentence
         (parse-noun-phrase)
         (parse-verb-phrase)))

(define (parse-verb-phrase)
  (define (maybe-extend verb-phrase)
    (amb 
     verb-phrase
     (maybe-extend 
      (list 'verb-phrase
            verb-phrase
            (parse-prepositional-phrase)))))
  (maybe-extend (parse-word verbs)))

Enquanto estamos nisso, também podemos elaborar a definição de frases nominais para permitir coisas como "um gato na classe". O que costumávamos chamar de frase nominal, agora chamaremos de frase nominal simples, e uma frase nominal será agora uma frase nominal simples ou uma frase nominal estendida por uma frase preposicional:

(define (parse-simple-noun-phrase)
  (list 'simple-noun-phrase
        (parse-word articles)
        (parse-word nouns)))

(define (parse-noun-phrase)
  (define (maybe-extend noun-phrase)
    (amb 
     noun-phrase
     (maybe-extend 
      (list 'noun-phrase
            noun-phrase
            (parse-prepositional-phrase)))))
  (maybe-extend (parse-simple-noun-phrase)))

Nossa nova gramática nos permite analisar frases mais complexas. Por exemplo

(parse '(the student with the cat 
         sleeps in the class))

produz

(sentence
 (noun-phrase
  (simple-noun-phrase (article the) 
                      (noun student))
  (prep-phrase (prep with)
               (simple-noun-phrase
                (article the)
                (noun cat))))
 (verb-phrase
  (verb sleeps)
  (prep-phrase (prep in)
               (simple-noun-phrase
                (article the)
                (noun class)))))

Observe que uma determinada entrada pode ter mais de uma análise legal. Na frase "O professor dá aulas para o aluno com o gato", pode ser que o professor esteja dando aulas com o gato, ou que o aluno tenha o gato. Nosso programa não determinístico encontra ambas as possibilidades:

(parse '(the professor lectures to 
         the student with the cat))

produz

(sentence
 (simple-noun-phrase (article the) 
                     (noun professor))
 (verb-phrase
  (verb-phrase
   (verb lectures)
   (prep-phrase (prep to)
                (simple-noun-phrase
                 (article the) 
                 (noun student))))
  (prep-phrase (prep with)
               (simple-noun-phrase
                (article the) 
                (noun cat)))))

Pedir ao avaliador para tentar novamente produz

(sentence
 (simple-noun-phrase (article the) 
                     (noun professor))
 (verb-phrase (verb lectures)
              (prep-phrase 
               (prep to)
               (noun-phrase
                (simple-noun-phrase
                 (article the) 
                 (noun student))
                (prep-phrase 
                 (prep with)
                 (simple-noun-phrase
                  (article the) 
                  (noun cat))))))

Exercício 4.45: Com a gramática dada acima, a seguinte frase pode ser analisada de cinco maneiras diferentes: "O professor dá aulas para o aluno na classe com o gato." Dê as cinco análises e explique as diferenças nos significados entre elas.

Exercício 4.46: Os avaliadores em 4.1 e 4.2 não determinam em que ordem os operandos são avaliados. Veremos que o avaliador amb os avalia da esquerda para a direita. Explique por que nosso programa de análise não funcionaria se os operandos fossem avaliados em alguma outra ordem.

Exercício 4.47: Louis Reasoner sugere que, como uma frase verbal é um verbo ou uma frase verbal seguida por uma frase preposicional, seria muito mais direto definir o procedimento parse-verb-phrase da seguinte forma (e de forma semelhante para frases nominais):

(define (parse-verb-phrase)
  (amb (parse-word verbs)
       (list 
        'verb-phrase
        (parse-verb-phrase)
        (parse-prepositional-phrase))))

Isso funciona? O comportamento do programa muda se trocarmos a ordem das expressões no amb?

Exercício 4.48: Estenda a gramática dada acima para lidar com frases mais complexas. Por exemplo, você poderia estender frases nominais e verbais para incluir adjetivos e advérbios, ou poderia lidar com frases compostas.²⁵⁷

Exercício 4.49: Alyssa P. Hacker está mais interessada em gerar frases interessantes do que em analisá-las. Ela argumenta que, simplesmente mudando o procedimento parse-word para que ele ignore a "frase de entrada" e sempre tenha sucesso e gere uma palavra apropriada, podemos usar os programas que construímos para análise para fazer geração. Implemente a ideia de Alyssa e mostre as primeiras meia dúzia de frases geradas.²⁵⁸

4.3.3Implementando o Avaliador Amb

A avaliação de uma expressão comum de Scheme pode retornar um valor, pode nunca terminar ou pode sinalizar um erro. No Scheme não determinístico, a avaliação de uma expressão pode, além disso, resultar na descoberta de um beco sem saída, caso em que a avaliação deve retroceder a um ponto de escolha anterior. A interpretação do Scheme não determinístico é complicada por este caso extra.

Construiremos o avaliador amb para o Scheme não determinístico modificando o avaliador analisador de 4.1.7.²⁵⁹ Como no avaliador analisador, a avaliação de uma expressão é realizada chamando um procedimento de execução produzido pela análise dessa expressão. A diferença entre a interpretação do Scheme comum e a interpretação do Scheme não determinístico estará inteiramente nos procedimentos de execução.

Procedimentos de execução e continuações

Lembre-se de que os procedimentos de execução para o avaliador comum tomam um argumento: o ambiente de execução. Em contraste, os procedimentos de execução no avaliador amb tomam três argumentos: o ambiente e dois procedimentos chamados procedimentos de continuação. A avaliação de uma expressão terminará chamando um desses dois procedimentos de continuação: Se a avaliação resultar em um valor, a continuação de sucesso será chamada com esse valor; se a avaliação resultar na descoberta de um beco sem saída, a continuação de falha será chamada. A construção e chamada de continuações apropriadas é o mecanismo pelo qual o avaliador não determinístico implementa o retrocesso.

É trabalho da continuação de sucesso receber um valor e prosseguir com a computação. Junto com esse valor, a continuação de sucesso é passada outra continuação de falha, que será chamada posteriormente se o uso desse valor levar a um beco sem saída.

É trabalho da continuação de falha tentar outro ramo do processo não determinístico. A essência da linguagem não determinística está no fato de que expressões podem representar escolhas entre alternativas. A avaliação de tal expressão deve prosseguir com uma das alternativas indicadas, mesmo que não se saiba de antemão quais escolhas levarão a resultados aceitáveis. Para lidar com isso, o avaliador escolhe uma das alternativas e passa esse valor para a continuação de sucesso. Junto com esse valor, o avaliador constrói e passa uma continuação de falha que pode ser chamada mais tarde para escolher uma alternativa diferente.

Uma falha é acionada durante a avaliação (ou seja, uma continuação de falha é chamada) quando um programa de usuário rejeita explicitamente a linha de ataque atual (por exemplo, uma chamada para require pode resultar na execução de (amb), uma expressão que sempre falha — veja 4.3.1). A continuação de falha em mãos naquele ponto fará com que o ponto de escolha mais recente escolha outra alternativa. Se não houver mais alternativas a serem consideradas naquele ponto de escolha, uma falha em um ponto de escolha anterior é acionada, e assim por diante. As continuações de falha também são invocadas pelo loop de controle em resposta a uma solicitação try-again, para encontrar outro valor da expressão.

Além disso, se uma operação de efeito colateral (como a atribuição a uma variável) ocorrer em um ramo do processo resultante de uma escolha, pode ser necessário, quando o processo encontrar um beco sem saída, desfazer o efeito colateral antes de fazer uma nova escolha. Isso é realizado fazendo com que a operação de efeito colateral produza uma continuação de falha que desfaz o efeito colateral e propaga a falha.

Em resumo, as continuações de falha são construídas por

• expressões amb — para fornecer um mecanismo para fazer escolhas alternativas se a escolha atual feita pela expressão amb levar a um beco sem saída;
• o loop de controle de nível superior — para fornecer um mecanismo para relatar falha quando as escolhas são esgotadas;
• atribuições — para interceptar falhas e desfazer atribuições durante o retrocesso.

As falhas são iniciadas apenas quando um beco sem saída é encontrado. Isso ocorre

• se o programa do usuário executar (amb);
• se o usuário digitar try-again no loop de controle de nível superior.

As continuações de falha também são chamadas durante o processamento de uma falha:

• Quando a continuação de falha criada por uma atribuição termina de desfazer um efeito colateral, ela chama a continuação de falha que interceptou, a fim de propagar a falha de volta ao ponto de escolha que levou a essa atribuição ou ao nível superior.
• Quando a continuação de falha para um amb esgota as escolhas, ela chama a continuação de falha que foi originalmente dada ao amb, a fim de propagar a falha de volta ao ponto de escolha anterior ou ao nível superior.

Estrutura do avaliador

Os procedimentos de sintaxe e representação de dados para o avaliador amb, e também o procedimento básico analyze, são idênticos aos do avaliador de 4.1.7, exceto pelo fato de que precisamos de procedimentos de sintaxe adicionais para reconhecer a forma especial amb:²⁶⁰

(define (amb? exp) (tagged-list? exp 'amb))
(define (amb-choices exp) (cdr exp))

Também devemos adicionar ao despacho em analyze uma cláusula que reconhecerá esta forma especial e gerará um procedimento de execução apropriado:

((amb? exp) (analyze-amb exp))

O procedimento de nível superior ambeval (semelhante à versão de eval dada em 4.1.7) analisa a expressão dada e aplica o procedimento de execução resultante ao ambiente dado, junto com duas continuações dadas:

(define (ambeval exp env succeed fail)
  ((analyze exp) env succeed fail))

Uma continuação de sucesso é um procedimento de dois argumentos: o valor obtido e outra continuação de falha a ser usada se esse valor levar a uma falha subsequente. Uma continuação de falha é um procedimento sem argumentos. Portanto, a forma geral de um procedimento de execução é

(lambda (env succeed fail)
  ;; `succeed` é (lambda (value fail) …)
  ;; `fail` é (lambda () …)
  …)

Por exemplo, executar

(ambeval ⟨exp⟩
         the-global-environment
         (lambda (value fail) value)
         (lambda () 'failed))

tentará avaliar a expressão dada e retornará ou o valor da expressão (se a avaliação for bem-sucedida) ou o símbolo failed (se a avaliação falhar). A chamada para ambeval no loop de controle mostrado abaixo usa procedimentos de continuação muito mais complicados, que continuam o loop e suportam a solicitação try-again.

A maior parte da complexidade do avaliador amb resulta da mecânica de passar as continuações enquanto os procedimentos de execução se chamam. Ao passar pelo código a seguir, você deve comparar cada um dos procedimentos de execução com o procedimento correspondente para o avaliador comum dado em 4.1.7.

Expressões simples

Os procedimentos de execução para os tipos mais simples de expressões são essencialmente os mesmos que os do avaliador comum, exceto pela necessidade de gerenciar as continuações. Os procedimentos de execução simplesmente têm sucesso com o valor da expressão, passando a continuação de falha que lhes foi passada.

(define (analyze-self-evaluating exp)
  (lambda (env succeed fail)
    (succeed exp fail)))

(define (analyze-quoted exp)
  (let ((qval (text-of-quotation exp)))
    (lambda (env succeed fail)
      (succeed qval fail))))

(define (analyze-variable exp)
  (lambda (env succeed fail)
    (succeed (lookup-variable-value exp env)
             fail)))

(define (analyze-lambda exp)
  (let ((vars (lambda-parameters exp))
        (bproc (analyze-sequence 
                (lambda-body exp))))
    (lambda (env succeed fail)
      (succeed (make-procedure vars bproc env)
               fail))))

Observe que a busca de uma variável sempre "tem sucesso". Se lookup-variable-value falhar ao encontrar a variável, ele sinaliza um erro, como de costume. Tal "falha" indica um bug no programa — uma referência a uma variável não ligada; não é uma indicação de que devemos tentar outra escolha não determinística em vez da que está sendo tentada atualmente.

Condicionais e sequências

Condicionais também são tratados de maneira semelhante ao avaliador comum. O procedimento de execução gerado por analyze-if invoca o procedimento de execução do predicado pproc com uma continuação de sucesso que verifica se o valor do predicado é verdadeiro e prossegue para executar o consequente ou a alternativa. Se a execução de pproc falhar, a continuação de falha original para a expressão if é chamada.

(define (analyze-if exp)
  (let ((pproc (analyze (if-predicate exp)))
        (cproc (analyze (if-consequent exp)))
        (aproc (analyze (if-alternative exp))))
    (lambda (env succeed fail)
      (pproc env
             ;; continuação de sucesso para avaliar
             ;; o predicado para obter `pred-value`
             (lambda (pred-value fail2)
               (if (true? pred-value)
                   (cproc env succeed fail2)
                   (aproc env succeed fail2)))
             ;; continuação de falha para
             ;; avaliar o predicado
             fail))))

Sequências também são tratadas da mesma forma que no avaliador anterior, exceto pelas manobras no subprocedimento sequentially que são necessárias para passar as continuações. Ou seja, para executar sequencialmente a e depois b, chamamos a com uma continuação de sucesso que chama b.

(define (analyze-sequence exps)
  (define (sequentially a b)
    (lambda (env succeed fail)
      (a env
         ;; continuação de sucesso para chamar `a`
         (lambda (a-value fail2)
           (b env succeed fail2))
         ;; continuação de falha para chamar `a`
         fail)))
  (define (loop first-proc rest-procs)
    (if (null? rest-procs)
        first-proc
        (loop (sequentially first-proc 
                            (car rest-procs))
              (cdr rest-procs))))
  (let ((procs (map analyze exps)))
    (if (null? procs)
        (error "Empty sequence: ANALYZE"))
    (loop (car procs) (cdr procs))))

Definições e atribuições

Definições são outro caso em que devemos nos esforçar para gerenciar as continuações, porque é necessário avaliar a expressão de valor da definição antes de realmente definir a nova variável. Para realizar isso, o procedimento de execução do valor da definição vproc é chamado com o ambiente, uma continuação de sucesso e a continuação de falha. Se a execução de vproc for bem-sucedida, obtendo um valor val para a variável definida, a variável é definida e o sucesso é propagado:

(define (analyze-definition exp)
  (let ((var (definition-variable exp))
        (vproc (analyze 
                (definition-value exp))))
    (lambda (env succeed fail)
      (vproc env
             (lambda (val fail2)
               (define-variable! var val env)
               (succeed 'ok fail2))
             fail))))

Atribuições são mais interessantes. Este é o primeiro lugar onde realmente usamos as continuações, em vez de apenas passá-las. O procedimento de execução para atribuições começa como o de definições. Ele primeiro tenta obter o novo valor a ser atribuído à variável. Se essa avaliação de vproc falhar, a atribuição falha.

Se vproc for bem-sucedido, no entanto, e prosseguirmos para fazer a atribuição, devemos considerar a possibilidade de que este ramo da computação possa falhar posteriormente, o que exigirá que retrocedamos da atribuição. Assim, devemos arranjar para desfazer a atribuição como parte do processo de retrocesso.²⁶¹

Isso é realizado dando a vproc uma continuação de sucesso (marcada com o comentário “*1*” abaixo) que salva o valor antigo da variável antes de atribuir o novo valor à variável e prosseguir da atribuição. A continuação de falha que é passada junto com o valor da atribuição (marcada com o comentário “*2*” abaixo) restaura o valor antigo da variável antes de continuar a falha. Ou seja, uma atribuição bem-sucedida fornece uma continuação de falha que interceptará uma falha subsequente; qualquer falha que de outra forma chamaria fail2 chama este procedimento em vez disso, para desfazer a atribuição antes de realmente chamar fail2.

(define (analyze-assignment exp)
  (let ((var (assignment-variable exp))
        (vproc (analyze 
                (assignment-value exp))))
    (lambda (env succeed fail)
      (vproc env
             (lambda (val fail2)    ; *1*
               (let ((old-value
                      (lookup-variable-value 
                       var 
                       env)))
                 (set-variable-value!
                  var 
                  val 
                  env)
                 (succeed 
                  'ok
                  (lambda ()    ; *2*
                    (set-variable-value! 
                     var
                     old-value
                     env)
                    (fail2)))))
             fail))))

Aplicações de procedimentos

O procedimento de execução para aplicações não contém novas ideias, exceto pela complexidade técnica de gerenciar as continuações. Essa complexidade surge em analyze-application, devido à necessidade de rastrear as continuações de sucesso e falha enquanto avaliamos os operandos. Usamos um procedimento get-args para avaliar a lista de operandos, em vez de um simples map como no avaliador comum.

(define (analyze-application exp)
  (let ((fproc (analyze (operator exp)))
        (aprocs (map analyze (operands exp))))
    (lambda (env succeed fail)
      (fproc env
             (lambda (proc fail2)
               (get-args 
                aprocs
                env
                (lambda (args fail3)
                  (execute-application
                   proc args succeed fail3))
                fail2))
             fail))))

Em get-args, observe como o cdr na lista de procedimentos de execução aproc e o cons na lista resultante de args são realizados chamando cada aproc na lista com uma continuação de sucesso que chama recursivamente get-args. Cada uma dessas chamadas recursivas para get-args tem uma continuação de sucesso cujo valor é o cons do argumento recém-obtido na lista de argumentos acumulados:

(define (get-args aprocs env succeed fail)
  (if (null? aprocs)
      (succeed '() fail)
      ((car aprocs) 
       env
       ;; continuação de sucesso para este `aproc`
       (lambda (arg fail2)
         (get-args 
          (cdr aprocs)
          env
          ;; continuação de sucesso para
          ;; chamada recursiva a `get-args`
          (lambda (args fail3)
            (succeed (cons arg args)
                     fail3))
          fail2))
       fail)))

A aplicação real do procedimento, que é realizada por execute-application, é realizada da mesma forma que para o avaliador comum, exceto pela necessidade de gerenciar as continuações.

(define (execute-application 
         proc args succeed fail)
  (cond ((primitive-procedure? proc)
         (succeed 
          (apply-primitive-procedure 
           proc args)
          fail))
        ((compound-procedure? proc)
         ((procedure-body proc)
          (extend-environment 
           (procedure-parameters proc)
           args
           (procedure-environment proc))
          succeed
          fail))
        (else (error "Unknown procedure type: 
                      EXECUTE-APPLICATION"
                     proc))))

Avaliando expressões amb

A forma especial amb é o elemento-chave na linguagem não determinística. Aqui vemos a essência do processo de interpretação e a razão para rastrear as continuações. O procedimento de execução para amb define um loop try-next que percorre os procedimentos de execução para todos os valores possíveis da expressão amb. Cada procedimento de execução é chamado com uma continuação de falha que tentará o próximo. Quando não há mais alternativas para tentar, toda a expressão amb falha.

(define (analyze-amb exp)
  (let ((cprocs
         (map analyze (amb-choices exp))))
    (lambda (env succeed fail)
      (define (try-next choices)
        (if (null? choices)
            (fail)
            ((car choices) 
             env
             succeed
             (lambda ()
               (try-next (cdr choices))))))
      (try-next cprocs))))

Loop de controle

O loop de controle para o avaliador amb é complexo, devido ao mecanismo que permite ao usuário tentar novamente ao avaliar uma expressão. O loop usa um procedimento chamado internal-loop, que toma como argumento um procedimento try-again. A intenção é que chamar try-again deve prosseguir para a próxima alternativa não tentada na avaliação não determinística. Internal-loop ou chama try-again em resposta ao usuário digitando try-again no loop de controle, ou inicia uma nova avaliação chamando ambeval.

A continuação de falha para esta chamada a ambeval informa ao usuário que não há mais valores e reinicia o loop de controle.

A continuação de sucesso para a chamada a ambeval é mais sutil. Imprimimos o valor obtido e então invocamos o loop interno novamente com um procedimento try-again que será capaz de tentar a próxima alternativa. Este procedimento next-alternative é o segundo argumento que foi passado para a continuação de sucesso. Normalmente, pensamos neste segundo argumento como uma continuação de falha a ser usada se o ramo de avaliação atual falhar posteriormente. Neste caso, no entanto, concluímos uma avaliação bem-sucedida, então podemos invocar o ramo de falha alternativo para procurar avaliações bem-sucedidas adicionais.

(define input-prompt  ";;; Entrada do Amb-Eval:")
(define output-prompt ";;; Valor do Amb-Eval:")

(define (driver-loop)
  (define (internal-loop try-again)
    (prompt-for-input input-prompt)
    (let ((input (read)))
      (if (eq? input 'try-again)
          (try-again)
          (begin
            (newline)
            (display 
             ";;; Iniciando um novo problema ")
            (ambeval 
             input
             the-global-environment
             ;; continuação de sucesso do `ambeval`
             (lambda (val next-alternative)
               (announce-output 
                output-prompt)
               (user-print val)
               (internal-loop 
                next-alternative))
             ;; continuação de falha do `ambeval`
             (lambda ()
               (announce-output
                ";;; Não há mais valores de")
               (user-print input)
               (driver-loop)))))))
  (internal-loop
   (lambda ()
     (newline)
     (display 
      ";;; Não há problema atual")
     (driver-loop))))

A chamada inicial para internal-loop usa um procedimento try-again que reclama que não há problema atual e reinicia o loop de controle. Este é o comportamento que ocorrerá se o usuário digitar try-again quando não houver avaliação em andamento.

Exercício 4.50: Implemente uma nova forma especial ramb que é como amb, exceto que busca alternativas em ordem aleatória, em vez da esquerda para a direita. Mostre como isso pode ajudar com o problema de Alyssa no Exercício 4.49.

Exercício 4.51: Implemente um novo tipo de atribuição chamado permanent-set! que não é desfeito em caso de falha. Por exemplo, podemos escolher dois elementos distintos de uma lista e contar o número de tentativas necessárias para fazer uma escolha bem-sucedida da seguinte forma:

(define count 0)
(let ((x (an-element-of '(a b c)))
      (y (an-element-of '(a b c))))
  (permanent-set! count (+ count 1))
  (require (not (eq? x y)))
  (list x y count))

;;; Iniciando um novo problema
;;; Valor do Amb-Eval:
(a b 2)

;;; Entrada do Amb-Eval:
try-again

;;; Valor do Amb-Eval:
(a c 3)

Quais valores seriam exibidos se tivéssemos usado set! aqui em vez de permanent-set!?

Exercício 4.52: Implemente um novo construto chamado if-fail que permite ao usuário capturar a falha de uma expressão. If-fail toma duas expressões. Ele avalia a primeira expressão como de costume e retorna como de costume se a avaliação for bem-sucedida. Se a avaliação falhar, no entanto, o valor da segunda expressão é retornado, como no seguinte exemplo:

;;; Entrada do Amb-Eval:
(if-fail 
 (let ((x (an-element-of '(1 3 5))))
   (require (even? x))
   x)
 'all-odd)

;;; Iniciando um novo problema
;;; Valor do Amb-Eval:
all-odd

;;; Entrada do Amb-Eval:
(if-fail
 (let ((x (an-element-of '(1 3 5 8))))
   (require (even? x))
   x)
 'all-odd)

;;; Iniciando um novo problema
;;; Valor do Amb-Eval:
8

Exercício 4.53: Com permanent-set! como descrito no Exercício 4.51 e if-fail como no Exercício 4.52, qual será o resultado de avaliar

(let ((pairs '()))
  (if-fail 
   (let ((p (prime-sum-pair 
             '(1 3 5 8) 
             '(20 35 110))))
     (permanent-set! pairs 
                     (cons p pairs))
     (amb))
   pairs))

Exercício 4.54: Se não tivéssemos percebido que require poderia ser implementado como um procedimento comum que usa amb, a ser definido pelo usuário como parte de um programa não determinístico, teríamos que implementá-lo como uma forma especial. Isso exigiria procedimentos de sintaxe

(define (require? exp) 
  (tagged-list? exp 'require))

(define (require-predicate exp) 
  (cadr exp))

e uma nova cláusula no despacho em analyze

((require? exp) (analyze-require exp))

assim como o procedimento analyze-require que lida com expressões require. Complete a seguinte definição de analyze-require.

(define (analyze-require exp)
  (let ((pproc (analyze 
                (require-predicate exp))))
    (lambda (env succeed fail)
      (pproc env
             (lambda (pred-value fail2)
               (if ⟨??⟩
                   ⟨??⟩
                   (succeed 'ok fail2)))
             fail))))

(define (distinct? items)
  (cond ((null? items) true)
        ((null? (cdr items)) true)
        ((member (car items) (cdr items)) false)
        (else (distinct? (cdr items))))