Pular para o conteúdo principal

4.3.2 Exemplos 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, assim expressando nossos programas em um nível mais alto de abstração.

Quebra-cabeças Lógicos​

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

A empresa de software Gargle está se expandindo, e Alyssa, Ben, Cy, Lem e Louis estão se mudando para uma fileira de cinco escritórios privativos em um novo edifício. Alyssa não se muda para o último escritório. Ben não se muda para o primeiro escritório. Cy não fica nem no primeiro nem no último escritório. Lem se muda para um escritório depois do de Ben. O escritório de Louis não é ao lado do de Cy. O escritório de Cy não é ao lado do de Ben. Quem se muda para qual escritório?

Podemos determinar quem se muda para qual escritório de forma direta enumerando todas as possibilidades e impondo as restrições dadas:1

function office_move() {
const alyssa = amb(1, 2, 3, 4, 5);
const ben = amb(1, 2, 3, 4, 5);
const cy = amb(1, 2, 3, 4, 5);
const lem = amb(1, 2, 3, 4, 5);
const louis = amb(1, 2, 3, 4, 5);
require(distinct(list(alyssa, ben, cy, lem, louis)));
require(alyssa !== 5);
require(ben !== 1);
require(cy !== 5);
require(cy !== 1);
require(lem > ben);
require(math_abs(louis - cy) !== 1);
require(math_abs(cy - ben) !== 1);
return list(list("alyssa", alyssa),
list("ben", ben),
list("cy", cy),
list("lem", lem),
list("louis", louis));
}

Avaliar a expressão office_move() produz o resultado

list(list("alyssa", 3), list("ben", 2), list("cy", 4),
list("lem", 5), list("louis", 1))

Embora esta função simples funcione, ela é muito lenta. Os exercícios 4.37 e 4.38 discutem algumas possíveis melhorias.

Exercício 4.36

Modifique a função de mudança de escritório para omitir a exigência de que o escritório de Louis não seja ao lado do de Cy. Quantas soluções existem para este quebra-cabeça modificado?

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Removendo require(math_abs(louis - cy) !== 1);, o quebra-cabeça passa a ter 5 soluções (Alyssa, Ben, Cy, Lem, Louis):

AlyssaBenCyLemLouis
12435
12453
14253
32451
34251

A original (Alyssa 3, Ben 2, Cy 4, Lem 5, Louis 1) continua entre elas — as outras quatro eram exatamente as que a restrição de vizinhança Louis–Cy eliminava. Com amb, "quantas soluções" é literal: avalie office_move() e digite retry até a busca esgotar.

Exercício 4.37

A ordem das restrições na função de mudança de escritório afeta a resposta? Afeta o tempo para encontrar uma resposta? Se você acha que importa, demonstre um programa mais rápido obtido do dado reordenando as restrições. Se você acha que não importa, argumente seu caso.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

A resposta não muda; o tempo, sim.

  • Resposta: os require são filtros — cada um descarta as combinações que violam sua condição. O conjunto que sobrevive a todos é a interseção dos conjuntos aceitos, e interseção não depende da ordem. Qualquer permutação das restrições produz as mesmas soluções.
  • Tempo: nesta formulação, as cinco escolhas já foram feitas quando o primeiro require roda; o que a ordem controla é quanto trabalho é gasto por combinação antes da primeira falha. Vale a regra: primeiro os testes baratos e que mais reprovam, por último os caros. distinct é o teste mais caro (percorre a lista com member); as comparações são O(1). Reordenando —
require(ben !== 1);
require(cy !== 5);
require(cy !== 1);
require(alyssa !== 5);
require(lem > ben);
require(math_abs(cy - ben) !== 1);
require(math_abs(louis - cy) !== 1);
require(distinct(list(alyssa, ben, cy, lem, louis)));

— a maioria das 3125 combinações morre num teste O(1) barato e distinct só roda para as poucas sobreviventes. O ganho é um fator constante: para reduzir o número de combinações explorado, é preciso mudar a estrutura da busca — que é o exercício 4.38.

Exercício 4.38

No problema de mudança de escritório, quantos conjuntos de atribuições há de pessoas para escritórios, tanto antes quanto depois da exigência de que as atribuições de escritório sejam distintas? É muito ineficiente gerar todas as atribuições possíveis de pessoas para escritórios e depois deixar para o backtracking eliminá-las. Por exemplo, a maioria das restrições depende de apenas uma ou duas das nomes, pessoa-escritório, e podem assim ser impostas antes que escritórios tenham sido selecionados para todas as pessoas. Escreva e demonstre uma função não determinística muito mais eficiente que resolva este problema baseando-se em gerar apenas as possibilidades que não são já descartadas por restrições anteriores.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Contagem: sem exigir distinção, cada uma das 5 pessoas escolhe entre 5 escritórios: 55=31255^5 = 3125 atribuições. Com a exigência de escritórios distintos, sobram as permutações: 5!=1205! = 120. A formulação original explora as 3125 e usa require(distinct(...)) para jogar fora 3005 delas — depois de já ter feito todas as escolhas.

A versão eficiente entrelaça escolhas e restrições, e nem oferece opções que uma restrição unária já proíbe:

function office_move() {
const ben = amb(2, 3, 4, 5); // ben !== 1, já na escolha
const cy = amb(2, 3, 4); // cy !== 1 e cy !== 5
require(math_abs(cy - ben) !== 1); // só ben e cy: teste já!
const lem = amb(1, 2, 3, 4, 5);
require(lem > ben);
const alyssa = amb(1, 2, 3, 4); // alyssa !== 5
const louis = amb(1, 2, 3, 4, 5);
require(math_abs(louis - cy) !== 1);
require(distinct(list(alyssa, ben, cy, lem, louis)));
return list(list("alyssa", alyssa), list("ben", ben),
list("cy", cy), list("lem", lem),
list("louis", louis));
}

Por que funciona: o backtracking corta um ramo no ponto em que ele falha. Se require(math_abs(cy - ben) !== 1) roda logo após as escolhas de ben e cy, um par ruim é descartado antes que lem, alyssa e louis multipliquem esse ramo por 535^3 combinações condenadas. Cada restrição deve rodar assim que suas variáveis existirem — o princípio que os solucionadores de restrições chamam de propagação.

Exercício 4.39

Escreva um programa JavaScript comum para resolver o quebra-cabeça de mudança de escritório.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Laços aninhados fazem o papel do amb, e continue faz o papel do require que falha:

function office_move() {
for (let ben = 2; ben <= 5; ben = ben + 1) {
for (let cy = 2; cy <= 4; cy = cy + 1) {
if (math_abs(cy - ben) === 1) continue;
for (let lem = ben + 1; lem <= 5; lem = lem + 1) {
for (let alyssa = 1; alyssa <= 4; alyssa = alyssa + 1) {
for (let louis = 1; louis <= 5; louis = louis + 1) {
if (math_abs(louis - cy) !== 1 &&
distinct(list(alyssa, ben, cy, lem, louis))) {
return list(list("alyssa", alyssa),
list("ben", ben), list("cy", cy),
list("lem", lem),
list("louis", louis));
}
}
}
}
}
}
return "sem solução";
}

O ponto do exercício: compare com a versão amb. O programa comum é a busca — os laços são a enumeração, os continue são as podas, e a ordem dos laços é a estratégia. A versão não determinística diz apenas o que uma solução satisfaz; quem transforma isso em laços e retrocessos é o avaliador. O preço da conveniência aparece no exercício 4.38: quando a busca automática é ingênua, recuperar a eficiência exige reintroduzir manualmente o entrelaçamento que os laços davam de graça.

Exercício 4.40

Resolva o seguinte quebra-cabeça "Mentirosos" (adaptado de Phillips 1934):

Alyssa, Cy, Eva, Lem e Louis se encontram para um almoço de negócios no SoSoService. Suas refeições chegam uma após a outra, um tempo considerável depois que fizeram seus pedidos. Para entreter Ben, que os espera de volta no escritório para uma reunião, eles decidem cada um fazer uma declaração verdadeira e uma falsa sobre seus pedidos:

  • Alyssa: "A refeição de Lem chegou em segundo. A minha chegou em terceiro."
  • Cy: "A minha chegou primeiro. A de Eva chegou em segundo."
  • Eva: "A minha chegou em terceiro, e a do pobre Cy chegou por último."
  • Lem: "A minha chegou em segundo. A de Louis chegou em quarto."
  • Louis: "A minha chegou em quarto. A refeição de Alyssa chegou primeiro."

Qual foi a ordem real em que os cinco comensais receberam suas refeições?

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Cada pessoa recebe uma posição; "uma declaração verdadeira e uma falsa" é um ou-exclusivo:

function xor(p, q) {
return (p || q) && !(p && q);
}

function liars() {
const alyssa = amb(1, 2, 3, 4, 5);
const cy = amb(1, 2, 3, 4, 5);
const eva = amb(1, 2, 3, 4, 5);
const lem = amb(1, 2, 3, 4, 5);
const louis = amb(1, 2, 3, 4, 5);
require(distinct(list(alyssa, cy, eva, lem, louis)));
require(xor(lem === 2, alyssa === 3)); // Alyssa
require(xor(cy === 1, eva === 2)); // Cy
require(xor(eva === 3, cy === 5)); // Eva
require(xor(lem === 2, louis === 4)); // Lem
require(xor(louis === 4, alyssa === 1)); // Louis
return list(list("alyssa", alyssa), list("cy", cy),
list("eva", eva), list("lem", lem),
list("louis", louis));
}

Resposta (única): Lem chegou em 1º, Eva em 2º, Alyssa em 3º, Louis em 4º e Cy em 5º.

Conferindo: Alyssa disse "Lem 2º" (falso) e "minha 3º" (verdadeiro) ✓; Cy: "minha 1º" (falso), "Eva 2º" (verdadeiro) ✓; Eva: "minha 3º" (falso), "Cy por último" (verdadeiro) ✓; Lem: "minha 2º" (falso), "Louis 4º" (verdadeiro) ✓; Louis: "minha 4º" (verdadeiro), "Alyssa 1º" (falso) ✓ — cada um com exatamente uma verdade, como combinado.

Exercício 4.41

Use o avaliador amb para resolver o seguinte quebra-cabeça (adaptado de Phillips 1961):

Alyssa, Ben, Cy, Eva e Louis cada um escolhe um capítulo diferente do SICP JS e resolve todos os exercícios naquele capítulo. Louis resolve os exercícios no capítulo "Functions", Alyssa os do capítulo "Data", e Cy os do capítulo "State". Eles decidem verificar o trabalho uns dos outros, e Alyssa se oferece para verificar os exercícios do capítulo "Meta". Os exercícios do capítulo "Register Machines" são resolvidos por Ben e verificados por Louis. A pessoa que verifica os exercícios do capítulo "Functions" resolve os exercícios que são verificados por Eva. Quem verifica os exercícios do capítulo "Data"?

Tente escrever o programa para que ele rode eficientemente (veja exercício 4.37). Determine também quantas soluções existem se não nos for dito que Alyssa verifica os exercícios do capítulo "Meta".

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Duas atribuições em jogo: quem resolve cada capítulo (toda dada no enunciado: Louis–"Functions", Alyssa–"Data", Cy–"State", Ben–"Register Machines" e, por eliminação, Eva–"Meta") e quem verifica — onde só sabemos Alyssa–"Meta" e Louis–"Register Machines". Restam Ben, Cy e Eva verificando "Functions", "Data" e "State", com duas restrições: ninguém verifica o capítulo que resolveu, e quem verifica "Functions" resolve o capítulo que Eva verifica.

function chapters() {
// verificadores dos três capítulos restantes
const funcs = amb("ben", "cy", "eva");
const data = amb("ben", "cy", "eva");
const state = amb("ben", "cy", "eva");
require(distinct(list(funcs, data, state)));
require(state !== "cy"); // Cy resolveu "State"
// quem verifica "Functions" resolve o capítulo verificado por Eva
const eva_verifica = funcs === "eva" ? "functions"
: data === "eva" ? "data" : "state";
const funcs_resolve = funcs === "ben" ? "register machines"
: funcs === "cy" ? "state" : "meta";
require(funcs_resolve === eva_verifica);
return list("data verificado por", data);
}

Resposta: Ben verifica "Data". A configuração única é Cy–"Functions", Ben–"Data", Eva–"State" (cheque a restrição cruzada: quem verifica "Functions" é Cy, que resolve "State" — exatamente o capítulo que Eva verifica ✓).

Sem a pista de que Alyssa verifica "Meta", a verificação de Alyssa vira uma amb a mais e o quebra-cabeça passa a ter 2 soluções.

Exercício 4.42

O exercício 2.42 descreveu o "quebra-cabeça das oito rainhas" de colocar rainhas em um tabuleiro de xadrez de modo que nenhuma duas se ataquem. Escreva um programa não determinístico para resolver este quebra-cabeça.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

A formulação amb coloca uma rainha por coluna e valida a cada escolha — a lição do exercício 4.38 aplicada ao tabuleiro:

function queens(board_size) {
function is_safe(row, placed, dist) {
return is_null(placed)
? true
: head(placed) !== row &&
math_abs(head(placed) - row) !== dist &&
is_safe(row, tail(placed), dist + 1);
}
function place(col, placed) {
if (col > board_size) {
return placed;
} else {
const row = an_integer_between(1, board_size);
require(is_safe(row, placed, 1));
return place(col + 1, pair(row, placed));
}
}
return place(1, null);
}
queens(8);

placed guarda as linhas das colunas anteriores, mais recente primeiro, então a distância horizontal até cada rainha anterior é 1, 2, 3, … — mesma linha e mesma diagonal caem num único teste.

Por que o require fica dentro do laço de colocação: validar cada rainha ao colocá-la poda o ramo inteiro na primeira violação; um require único no fim (todas as 8 escolhidas) exploraria 88≈16,78^8 ≈ 16{,}7 milhões de combinações. É o mesmo programa do exercício 2.42 — mas o backtracking que lá construímos com flatmap e filter aqui vem de graça do avaliador. retry enumera as 92 soluções.

Análise sintática de linguagem natural​

Programas projetados para aceitar linguagem natural como entrada geralmente começam tentando analisar sintaticamente a entrada, isto é, fazer a entrada corresponder a alguma estrutura gramatical. Por exemplo, poderíamos tentar reconhecer sentenças simples consistindo de um artigo seguido por um substantivo seguido por um verbo, como "The cat eats." Para realizar tal análise, devemos ser capazes de identificar as classes gramaticais de palavras individuais. Poderíamos começar com algumas listas que classificam várias palavras:2

const nouns = list("noun", "student", "professor", "cat", "class");

const verbs = list("verb", "studies", "lectures", "eats", "sleeps");

const articles = list("article", "the", "a");

Também precisamos de uma gramática, isto é, um conjunto de regras descrevendo como elementos gramaticais são compostos a partir de elementos mais simples. Uma gramática muito simples poderia estipular que uma sentença sempre consiste de duas partes—uma frase nominal seguida por um verbo—e que uma frase nominal consiste de um artigo seguido por um substantivo. Com esta gramática, a sentença "The cat eats" é analisada da seguinte forma:

list("sentence",
list("noun-phrase", list("article", "the"), list("noun", "cat"),
list("verb", "eats"))

Podemos gerar tal análise com um programa simples que tem funções separadas para cada uma das regras gramaticais. Para analisar uma sentença, identificamos suas duas partes constituintes e retornamos uma lista desses dois elementos, marcada com o símbolo sentence:

function parse_sentence() {
return list("sentence",
parse_noun_phrase(),
parse_word(verbs));
}

Uma frase nominal, similarmente, é analisada encontrando um artigo seguido por um substantivo:

function parse_noun_phrase() {
return list("noun-phrase",
parse_word(articles),
parse_word(nouns));
}

No nível mais baixo, a análise sintática se resume a verificar repetidamente que a próxima palavra ainda não analisada é um membro da lista de palavras para a classe gramatical requerida. Para implementar isso, mantemos uma variável global not_yet_parsed, que é a entrada que ainda não foi analisada. Cada vez que verificamos uma palavra, exigimos que not_yet_parsed não esteja vazia e que ela deva começar com uma palavra da lista designada. Se sim, removemos aquela palavra de not_yet_parsed e retornamos a palavra junto com sua classe gramatical (que é encontrada no cabeçalho da lista):3

function parse_word(word_list) {
require(! is_null(not_yet_parsed));
require(! is_null(member(head(not_yet_parsed), tail(word_list))));
const found_word = head(not_yet_parsed);
not_yet_parsed = tail(not_yet_parsed);
return list(head(word_list), found_word);
}

Para iniciar a análise sintática, tudo o que precisamos fazer é definir not_yet_parsed como a entrada inteira, tentar analisar uma sentença e verificar que nada sobrou:

let not_yet_parsed = null;
function parse_input(input) {
not_yet_parsed = input;
const sent = parse_sentence();
require(is_null(not_yet_parsed));
return sent;
}

Agora podemos testar o analisador e verificar que ele funciona para nossa sentença de teste simples:

parse_input(list("the", "cat", "eats"));

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

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

const prepositions = list("prep", "for", "to", "in", "by", "with");

e definir uma frase preposicional (por exemplo, "for the cat") como sendo uma preposição seguida por uma frase nominal:

function parse_prepositional_phrase() {
return list("prep-phrase",
parse_word(prepositions),
parse_noun_phrase());
}

Agora podemos definir uma sentença como sendo uma frase nominal seguida por uma frase verbal, onde uma frase verbal pode ser ou um verbo ou uma frase verbal estendida por uma frase preposicional:4

function parse_sentence() {
return list("sentence",
parse_noun_phrase(),
parse_verb_phrase());
}
function parse_verb_phrase() {
function maybe_extend(verb_phrase) {
return amb(verb_phrase,
maybe_extend(list("verb-phrase",
verb_phrase,
parse_prepositional_phrase())));
}
return maybe_extend(parse_word(verbs));
}

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

function parse_simple_noun_phrase() {
return list("simple-noun-phrase",
parse_word(articles),
parse_word(nouns));
}
function parse_noun_phrase() {
function maybe_extend(noun_phrase) {
return amb(noun_phrase,
maybe_extend(list("noun-phrase",
noun_phrase,
parse_prepositional_phrase())));
}
return maybe_extend(parse_simple_noun_phrase());
}

Nossa nova gramática nos permite analisar sentenças mais complexas. Por exemplo

parse_input(list("the", "student", "with", "the", "cat",
"sleeps", "in", "the", "class"));

produz

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

Observe que uma entrada dada pode ter mais de uma análise legal. Na sentença "The professor lectures to the student with the cat," pode ser que o professor esteja palestrando com o gato, ou que o estudante tenha o gato. Nosso programa não determinístico encontra ambas as possibilidades:

parse_input(list("the", "professor", "lectures",
"to", "the", "student", "with", "the", "cat"));

produz

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

Pedir ao avaliador para tentar novamente produz

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

Exercício 4.43

Com a gramática dada acima, a seguinte sentença pode ser analisada de cinco maneiras diferentes: "The professor lectures to the student in the class with the cat." Forneça as cinco análises e explique as diferenças em nuances de significado entre elas.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

O verbo é lectures, seguido de três frases preposicionais — "to the student", "in the class", "with the cat" — e cada uma pode se prender ao verbo ou ao substantivo anterior. As cinco análises:

  1. lectures (to the student) (in the class) (with the cat) — o professor palestra ao aluno, o faz na sala, e o faz acompanhado do gato.
  2. lectures (to the student) (in the class (with the cat)) — a palestra é ao aluno, na sala em que fica o gato.
  3. lectures (to the student (in the class)) (with the cat) — o destinatário é o aluno que está na sala; o professor palestra com o gato ao lado.
  4. lectures (to the student (in the class (with the cat))) — o destinatário é o aluno que está na sala do gato.
  5. lectures (to the student (in the class) (with the cat)) — o destinatário é o aluno que está na sala e que tem o gato.

O retry do avaliador enumera exatamente essas cinco antes de esgotar a busca — a ambiguidade sintática do inglês vira, literalmente, pontos de escolha do amb: cada maybe_extend decide se a próxima preposição estende a frase atual ou é devolvida para quem está acima.

Exercício 4.44

Os avaliadores nas seções 4.1.1 e 4.2 não determinam em qual ordem as expressões de argumento são avaliadas. Veremos que o avaliador amb as avalia da esquerda para a direita. Explique por que nosso programa de análise não funcionaria se as expressões de argumento fossem avaliadas em alguma outra ordem.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

O analisador funciona por efeito colateral sobre a entrada: cada parse_word consome o próximo trecho de not_yet_parsed. Numa expressão como

list("sentence", parse_noun_phrase(), parse_verb_phrase())

a corretude depende de parse_noun_phrase() rodar antes de parse_verb_phrase() — a frase nominal vem primeiro na sentença de entrada. Se os argumentos fossem avaliados da direita para a esquerda, parse_verb_phrase() tentaria casar um verbo com "The", falharia, e nenhuma sentença jamais seria analisada; pior, uma ordem não especificada tornaria o programa dependente do humor do avaliador.

A ligação com o capítulo 3: enquanto os programas eram puros, a ordem de avaliação de argumentos era irrelevante (e o exercício 4.1 mostrou que o avaliador metacircular nem se comprometia com uma). Ao introduzir estado — a posição corrente da análise — a ordem virou parte do significado. O avaliador amb promete esquerda→direita justamente porque o backtracking precisa desfazer efeitos numa ordem previsível ao retroceder pelos pontos de escolha.

Exercício 4.45

Louis Reasoner sugere que, já que uma frase verbal é ou um verbo ou uma frase verbal seguida por uma frase preposicional, seria muito mais direto declarar a função parse_verb_phrase da seguinte forma (e similarmente para frases nominais):

function parse_verb_phrase() {
return amb(parse_word(verbs),
list("verb-phrase",
parse_verb_phrase(),
parse_prepositional_phrase()));
}

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

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Funciona — nesta ordem. Ao tentar a segunda alternativa do amb, a avaliação de list("verb-phrase", parse_verb_phrase(), parse_prepositional_phrase()) chama parse_verb_phrase() recursivamente, que tenta primeiro parse_word(verbs) — e consome um verbo da entrada antes de qualquer nova recursão. Cada nível desce só depois de comer um pedaço da sentença, então a recursão é limitada pelo tamanho da entrada. As árvores saem aninhadas à direita em vez do formato do maybe_extend, e a ordem em que o retry produz as análises muda, mas todas aparecem.

Trocando a ordem das alternativas, o programa entra em recursão infinita. A primeira alternativa passa a ser a recursiva: para analisar uma frase verbal, avalie parse_verb_phrase() — que, para analisar uma frase verbal, avalia parse_verb_phrase()… sem consumir nada da entrada entre uma chamada e a seguinte. É a armadilha clássica da recursão à esquerda em analisadores descendentes: a gramática "frase verbal = frase verbal + frase preposicional" é legítima como definição, mas transcrita diretamente vira um laço sem progresso. O maybe_extend do texto existe exatamente para converter essa recursão à esquerda em iteração: analise o núcleo primeiro, depois estenda enquanto der.

Exercício 4.46

Estenda a gramática dada acima para lidar com sentenças mais complexas. Por exemplo, você poderia estender frases nominais e frases verbais para incluir adjetivos e advérbios, ou poderia lidar com sentenças compostas.5

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Adjetivos, advérbios e conjunções entram como novas listas de palavras e novos nós na gramática:

const adjectives = list("adjective", "brilliant", "lazy", "curious");
const adverbs = list("adverb", "quickly", "carefully");
const conjunctions = list("conjunction", "and", "or");

// substantivo pode vir precedido de adjetivos: "the lazy cat"
function parse_simple_noun_phrase() {
return amb(list("simple-noun-phrase",
parse_word(articles), parse_word(nouns)),
list("simple-noun-phrase",
parse_word(articles), parse_word(adjectives),
parse_word(nouns)));
}

// verbo pode vir seguido de advérbio: "studies carefully"
function parse_simple_verb() {
return amb(parse_word(verbs),
list("adverbed-verb", parse_word(verbs),
parse_word(adverbs)));
}

// sentenças compostas: "the cat sleeps and the professor lectures"
function parse_compound_sentence() {
const first = parse_sentence();
return amb(first,
list("compound-sentence", first,
parse_word(conjunctions), parse_compound_sentence()));
}

O cuidado ao estender: cada alternativa nova deve consumir entrada antes de recursar (a lição do exercício 4.45) — por isso parse_compound_sentence analisa first antes de decidir se procura uma conjunção. Com "The lazy cat sleeps quickly and the brilliant professor lectures.", a gramática estendida produz a análise composta com os dois ramos anotados.

Exercício 4.47

Alyssa P. Hacker está mais interessada em gerar sentenças interessantes do que em analisá-las. Ela raciocina que simplesmente mudando a função parse_word para que ela ignore a "sentença de entrada" e em vez disso sempre tenha sucesso e gere uma palavra apropriada, podemos usar os programas que construímos para análise para fazer geração em vez disso. Implemente a ideia de Alyssa, e mostre a primeira meia dúzia ou mais de sentenças geradas.6

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Basta trocar parse_word por uma versão que ignora a entrada e escolhe uma palavra da categoria:

function parse_word(word_list) {
function an_element_of(items) {
require(!is_null(items));
return amb(head(items), an_element_of(tail(items)));
}
return list(head(word_list), an_element_of(tail(word_list)));
}

Nada mais muda — os mesmos parse_sentence, parse_noun_phrase etc. agora geram em vez de analisar, porque toda pergunta "que palavra vem agora?" virou um ponto de escolha. Pedindo a primeira sentença e digitando retry:

The student studies.
The student studies for the student.
The student studies for the student for the student.
The student studies for the student for the student for the student.
…

A observação da nota de rodapé, vivida na prática: o backtracking cronológico refaz sempre a escolha mais recente — que, nesta gramática, é o maybe_extend da última frase preposicional. O gerador "cai" na recursão das preposições e nunca mais volta para variar o substantivo ou o verbo. As sentenças são gramaticais, mas a amostragem é péssima — é o mesmo defeito do exercício 4.34 (o k que corre para o infinito), e a mesma cura: controlar a ordem das escolhas, seja reestruturando a gramática, seja com um amb de ordem aleatória (o ramb do exercício 4.48).

Footnotes​

  1. Nosso programa usa a seguinte função para determinar se os elementos de uma lista são distintos:

    function distinct(items) {
    return is_null(items)
    ? true
    : is_null(tail(items))
    ? true
    : is_null(member(head(items), tail(items)))
    ? distinct(tail(items))
    : false;
    }
    ↩
  2. Aqui usamos a convenção de que o primeiro elemento de cada lista designa a classe gramatical para o resto das palavras na lista. ↩

  3. Note que parse_word usa atribuição para modificar a lista de entrada ainda não analisada. Para que isso funcione, nosso avaliador amb deve desfazer os efeitos de atribuições quando ele retrocede. ↩

  4. Observe que esta definição é recursiva—um verbo pode ser seguido por qualquer número de frases preposicionais. ↩

  5. Este tipo de gramática pode se tornar arbitrariamente complexa, mas ela é apenas um brinquedo no que diz respeito à compreensão real de linguagem. A compreensão real de linguagem natural por computador requer uma mistura elaborada de análise sintática e interpretação de significado. Por outro lado, até analisadores de brinquedo podem ser úteis no suporte a linguagens de comando flexíveis para programas como sistemas de recuperação de informação. Winston 1992 discute abordagens computacionais para compreensão de linguagem real e também as aplicações de gramáticas simples a linguagens de comando. ↩

  6. Embora a ideia de Alyssa funcione muito bem (e seja surpreendentemente simples), as sentenças que ela gera são um pouco chatas—elas não amostram as sentenças possíveis desta linguagem de uma maneira muito interessante. Na verdade, a gramática é altamente recursiva em muitos lugares, e a técnica de Alyssa "cai em" uma dessas recursões e fica presa. Veja o exercício 4.48 para uma maneira de lidar com isso. ↩