4.3 Computação Não Determinística
Nesta seção, estendemos o avaliador JavaScript para suportar um paradigma de programação chamado computação não determinística construindo no avaliador uma facilidade para suportar busca automática. Esta é uma mudança muito mais profunda na linguagem do que a introdução da avaliação preguiçosa na seção 4.2.
A computação não determinística, como o processamento de streams, é útil para aplicações de "gerar e testar". Considere a tarefa de começar com duas listas de inteiros positivos e encontrar um par de inteiros — um da primeira lista e um da segunda lista — cuja soma seja prima. Vimos como lidar com isso com operações de sequência finita na seção 2.2.3 e com streams infinitos na seção 3.5.3. Nossa abordagem foi gerar a sequência de todos os pares possíveis e filtrar esses para selecionar os pares cuja soma é prima. Se realmente geramos a sequência inteira de pares primeiro como no capítulo 2, ou intercalamos a geração e a filtragem como no capítulo 3, é imaterial 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 sua soma seja prima. Isso é expresso pela seguinte função:
function prime_sum_pair(list1, list2) {
const a = an_element_of(list1);
const b = an_element_of(list2);
require(is_prime(a + b));
return list(a, b);
}
Pode parecer que esta função meramente reafirma o problema, em vez de especificar uma maneira de resolvê-lo. No entanto, este é um programa não determinístico legítimo.1
A ideia-chave aqui é que componentes 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 dada. Nosso avaliador de programa não determinístico funcionará escolhendo automaticamente um valor possível e mantendo o controle da 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 tenha sucesso, ou até que fiquemos sem 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 programa não determinístico 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 streams. O processamento de streams usa avaliação preguiçosa para desacoplar o tempo quando o stream de respostas possíveis é montado do tempo quando os elementos reais do stream 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, um componente 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 programa não determinístico suporta a ilusão de que o tempo se ramifica, e que nossos programas têm diferentes histórias de execução possíveis. Quando chegamos a um beco sem saída, podemos revisitar um ponto de escolha anterior e prosseguir ao longo de um ramo diferente.
O avaliador de programa não determinístico implementado abaixo é chamado de avaliador amb porque é baseado em uma nova forma sintática chamada amb. Podemos digitar a declaração acima de prime_sum_pair no loop do driver do avaliador amb (junto com declarações de is_prime, an_element_of e require) e executar a função da seguinte forma:
amb-evaluate input:
prime_sum_pair(list(1, 3, 5, 8), list(20, 35, 110));
Starting a new problem
amb-evaluate value:
[3, [20, null]]
O valor retornado foi obtido depois que o avaliador escolheu repetidamente elementos de cada uma das listas, até que uma escolha bem-sucedida fosse 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 seção 4.3.2 apresenta exemplos de programas não determinísticos, e a seção 4.3.3 fornece os detalhes de como implementar o avaliador amb modificando o avaliador JavaScript comum.