💻 computer science

Towards Bottom-Up Enumeration in miniKanren via Pruning and Memoization

Este artigo introduz dois combinadores da biblioteca miniKanren, `prune` e `defrel/bank`, que permitem a enumeração bottom-up com deduplicação observacional e memoização para melhorar significativamente o desempenho da síntese de programas relacionais em alvos profundos, ao mesmo tempo em que propõe uma variante ponderada para abordar casos onde a ordenação canônica depth-first falha em encontrar representantes compactos.

Autores originais: Nikolai Kudasov

Publicado 2026-07-29

📖 7 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Nikolai Kudasov

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você é um detetive tentando resolver um mistério, mas em vez de procurar pistas, você está tentando construir uma máquina que possa realizar um trabalho específico, como transformar o número 2 em 4, 3 em 9 e 4 em 16. Você não sabe a fórmula exata que a máquina usa; você apenas conhece os resultados. Isso é chamado de "Programação por Exemplo". Para encontrar a resposta, você poderia tentar construir todas as máquinas possíveis, uma por uma, começando com as engrenagens e alavancas mais simples, e testar cada uma para ver se funciona. Isso é um pouco como um chef tentando descobrir uma receita secreta cozinhando todas as combinações possíveis de farinha, açúcar e ovos até que uma tenha o sabor certo.

No mundo da ciência da computação, existe uma forma especial de pensar chamada "programação relacional". Em vez de dizer ao computador exatamente como encontrar a resposta passo a passo, você descreve o que a resposta parece, e deixa o computador descobrir o caminho. É como dizer a um robô: "Encontre-me um caminho através do labirinto", em vez de "Vire à esquerda, depois ande três passos e depois vire à direita". O computador é ótimo em explorar muitos camos ao mesmo tempo, mas tem um hábito complicado: ele tende a explorar os mesmos becos sem saída repetidamente, ou ficar preso em um túnel longo e sinuoso enquanto perde um atalho curto e inteligente logo ao lado. Este artigo aborda esse problema, ensinando o computador a ser um explorador mais inteligente e organizado.

O Problema: Perdendo-se no Labirinto

Imagine que você está tentando encontrar uma chave específica em um sótão gigante e bagunçado cheio de milhões de chaves. A maioria dessas chaves parece diferente, mas todas abrem exatamente a mesma porta. Se você for um explorador desastrado, pode pegar uma chave, testá-la, perceber que funciona e, então, passar horas pegando outras chaves que parecem diferentes, mas também funcionam, apenas para ter certeza. Você está perdendo tempo testando chaves que fazem exatamente o mesmo trabalho.

No mundo dos programas de computador, isso acontece o tempo todo. Quando um computador tenta construir um programa para transformar entradas em saídas, ele gera milhares de trechos de código de aparência diferente. Muitos desses trechos são "gêmeos" disfarçados — eles fazem exatamente a mesma coisa, embora pareçam diferentes por dentro. Um método de busca padrão de computador, que funciona como um explorador de mergulho profundo, verificará um gêmeo, depois o próximo, depois o próximo, tornando-se cada vez mais lento conforme o sótão aumenta. É como tentar encontrar uma agulha em um palheiro, mas o palheiro é feito de milhões de agulhas que todas parecem ligeiramente diferentes.

A Solução: O "Prune" e o "Bank"

Os autores deste artigo, Nikolai Kudasov, criaram duas ferramentas inteligentes para consertar essa bagunça. Pense nelas como um filtro mágico e uma biblioteca inteligente.

1. A Ferramenta "Prune" (O Filtro)
Imagine que você tem uma esteira transportadora de chaves sainendo de uma máquina. A ferramenta "Prune" é um guarda parado ao lado da esteira. Conforme cada chave chega, o guarda verifica qual porta ela abre. Se o guarda já viu uma chave que abre aquela mesma porta, ele simplesmente joga a nova chave no lixo sem nem testá-la. Ele mantém apenas a primeira chave que abre uma porta específica. Dessa forma, a esteira transportadora carrega apenas chaves únicas e úteis. O computador para de perder tempo com duplicatas.

2. A Ferramenta "Bank" (A Biblioteca Inteligente)
Agora, imagine que, em vez de construir chaves do zero toda vez que você precisa de uma, você tem uma biblioteca mágica. Quando você pede uma chave para a biblioteca, ela não te dá apenas uma; ela constrói uma prateleira inteira de chaves únicas uma única vez, de baixo para cima, e as salva. Se você pedir uma chave novamente mais tarde, a biblioteca apenas lhe entrega a que já construiu.

Na linguagem do artigo, isso é chamado de defrel/bank. Isso força o computador a construir sua lista de programas candidatos de uma forma específica e organizada (começando pelos mais simples) e salva os resultados. Se o computador precisar usar uma pequena parte de um programa mais tarde, ele não reconstrói essa parte; ele apenas pega a peça da "biblioteca". Isso economiza uma quantidade enorme de tempo porque o computador nunca precisa fazer o mesmo trabalho duas vezes.

A Reviravolta: Às vezes "Rápido" não é "Melhor"

Os autores também perceberam que ser organizado nem sempre é o suficiente. Às vezes, o "Bank" constrói suas prateleiras em uma ordem que é rápida para o computador, mas lenta para o humano. Por exemplo, o Bank pode construir todas as máquinas de "multiplicação" primeiro e, só muito mais tarde, construir as máquinas de "adição". Se a resposta que você procura é uma máquina de "adição", o computador pode ter que verificar milhares de máquinas de multiplicação antes de finalmente encontrar aquela que você precisa.

Para corrigir isso, eles criaram uma terceira ferramenta chamada defrel/bank-w (o Bank "Ponderado"). Esta ferramenta é como um bibliotecário que sabe que certos tipos de chaves têm mais probabilidade de serem a resposta. Ele usa uma "pontuação" especial para decidir quais chaves mostrar primeiro. Ele tenta mostrar as chaves mais simples e compactas primeiro, mesmo que estejam enterradas profundamente na biblioteca. Isso é ótimo se você quiser a solução mais elegante, mas pode ser mais lento se a resposta for, na verdade, uma máquina complexa e profunda.

O Que Eles Descobriram: Velocidade vs. Estratégia

Os autores testaram essas ferramentas em um conjunto de enigmas matemáticos e de strings (como transformar "Hello" em "Hello, World!"). Aqui está o que descobriram:

O "Bank" é um demônio da velocidade: Em 6 de 8 problemas matemáticos difíceis, a ferramenta defrel/bank foi de 9 a 99 vezes mais rápida do que o método de busca padrão antigo. Foi tão rápida que resolveu problemas em uma fração de segundo que o método antigo levava minutos para terminar.
Mas ele tem um ponto cego: O Bank é tão organizado que às vezes perde a resposta se essa resposta estiver escondida em uma parte da biblioteca que ele visita tardiamente. Por exemplo, se a resposta envolver a adição de números de uma forma específica (como $(1+x)^5$ ), o Bank pode ficar preso verificando milhares de exemplos de multiplicação primeiro. Nesses casos, o método antigo, mais lento, na verdade vence, porque verifica as coisas em uma ordem diferente.
O "Bank Ponderado" é uma troca: A ferramenta defrel/bank-w é excelente para encontrar as respostas mais compactas e elegantes. Ela encontrou a resposta certa para um enigma de string difícil em 10,4 milissegundos, superando os 31,5 milissegundos do método padrão. No entanto, para problemas matemáticos muito profundos, ela às vezes ficou presa tentando verificar muitas possibilidades e esgotou o tempo (timeout).

A Conclusão

Este artigo não afirma ter resolvido todos os problemas da ciência da computação. Em vez disso, mostra que, ao adicionar um pouco de "pruning" (filtrar duplicatas) e "banking" (salvar o trabalho para mais tarde), podemos fazer programas de computador que constroem outros programas muito, muito mais rápido.

Os autores sugerem que, se você estiver construindo um sistema para resolver enigmas, deve usar a ferramenta Bank como seu padrão, pois ela é geralmente a mais rápida. No entanto, se você estiver procurando por uma solução muito específica e compacta, ou se o problema for raso e simples, você pode querer usar o Bank Ponderado ou até mesmo o método antigo. Não se trata de uma ferramenta ser perfeita; trata-se de ter a ferramenta certa para o formato do enigma que você está tentando resolver. O artigo termina sugerindo que trabalhos futuros testarão essas ferramentas em enigmas ainda mais complexos, como construir programas que entendam listas ou dados tipados, para ver se esse aumento de velocidade se mantém no mundo real.

Resumo Técnico: Rumo à Enumeração Bottom-Up em miniKanren via Pruning e Memoização

Declaração do Problema

Sintetizadores modernos de Programação por Exemplo (PBE) tipicamente dependem de enumeração bottom-up com deduplicação observacional. Esta abordagem mantém uma lista de trabalho (worklist) de expressões candidatas, deduplica-as com base em seu comportamento em exemplos de entrada e as expande nível a nível até que uma correspondência seja encontrada. Embora altamente eficaz em contextos imperativos e funcionais, essa estratégia situa-se de forma desajeitada na programação relacional (especificamente o miniKanren), onde a disciplina de busca natural é a resolução top-down contra um fluxo justo (fair stream) de candidatos.

As receitas existentes de miniKanren para PBE, como escrever um intérprete relacional e executá-lo "para trás" ou usar uma abordagem de "enumerar-e-testar" com limites de profundidade, sofrem de ineficiências significativas em profundidades de busca realistas. O problema principal é que a árvore de busca contém muitas expressões comportamentalmente equivalentes. Um enumerador ingênuo limitado por profundidade cria uma nova tabela de deduplicação em cada nível recursivo, falhando em reutilizar o trabalho realizado nos níveis anteriores. Isso leva a uma explosão exponencial no espaço de busca, onde candidatos comportamentalmente idênticos são reavaliados repetidamente.

Metodologia

Os autores propõdem dois pequenos combinadores de biblioteca construídos sobre um núcleo $\mu$ Kanren não modificado para preencher a lacuna entre a síntese PBE bottom-up e a programação relacional. Esses combinadores introduzem enumeração bottom-up e deduplicação observacional sem alterar a disciplina de busca do hospedeiro.

1. O Combinador `prune`

O primeiro combinador, prune, filtra um fluxo de respostas baseado em uma função de chave fornecida pelo usuário.

Mecanismo: Ele envolve um objetivo (goal) e emite no máximo um estado por valor distinto da função de chave (por exemplo, o comportamento de entrada/saída de uma expressão candidata).
Tratamento de Variáveis Lógicas: Para lidar com casos onde a chave depende de variáveis lógicas não vinculadas, o prune utiliza um valor sentinela (skip-prune). Se uma chave não puder ser computada porque um termo ainda não é ground, o estado é emitido sem ser registrado na tabela de deduplicação. Ele está sujeito à deduplicação apenas quando a variável é vinculada e o termo torna-se ground.
Escopo: A deduplicação é estritamente por chamada. Uma nova tabela de dispersão (hash table) é criada para cada invocação de prune para evitar confundir "visto como uma variável externa" com "visto como uma variável interna", o que quebraria a completude em definições recursivas.

2. O Combinador `defrel/bank`

O segundo combinador, defrel/bank, estende o prune para alcançar uma verdadeira enumeração bottom-up com deduplicação compartilhada em todos os locais de chamada de uma relação.

Variáveis Canônicas: Ele faz a memoização de uma relação contra variáveis canônicas frescas (as primeiras $N$ variáveis frescas de um estado vazio), representando a chamada mais geral da relação.
O "Banco" (Bank): O corpo da relação é executado uma única vez contra essas variáveis canônicas para produzir um fluxo canônico (o "banco"). Este fluxo é construído bottom-up e contém exatamente um representante por classe de equivalência (determinada pela chave #:prune).
Replay: Chamadas subsequentes à relação não reexecutam o corpo. Em vez disso, elas reproduzem (replay) o fluxo canônico contra os argumentos específicos do chamador. Isso envolve percorrer a substituição canônica, renomear variáveis internas para o namespace do chamador e unificar os resultados com os argumentos do chamador.
Eficiência: Esta abordagem garante que o trabalho de deduplicação seja realizado apenas uma vez por consulta (run ... ), independentemente de quantas vezes a relação é chamada recursivamente.

3. A Variante `defrel/bank-w` (Best-First)

O defrel/bank padrão usa recursão depth-first, o que enviesa a ordem de enumeração (por exemplo, favorecendo cadeias de espinha direita de multiplicação sobre adição). Para abordar casos onde a solução alvo reside profundamente na ordem depth-first, os autores introduzem o defrel/bank-w.

Fluxos Pesados (Weighted Streams): Esta variante anexa limites superiores admissíveis (pesos) a células de fluxo imaturas.
Decaimento de Profundidade (Depth-Decay): Um fator de decaimento é aplicado aos pesos nos locais de chamada recursiva. Isso garante que representantes mais rasos tenham pesos menores e sejam emitidos primeiro pela lógica de mesclagem ordenada (mplus-w).
Heurísticas Preguiçosas (Lazy Heuristics): O sistema utiliza uma disciplina de "teto preguiçoso" (lazy-ceiling) onde os pesos são espiados sem forçar o thunk subjacente, evitando loops infinitos durante a construção do fluxo canônico. Isso implementa uma busca do tipo A*, onde o teto de peso atua como uma heurística admissível.

Principais Contribuições

prune: Um combinador genérico de deduplicação de fluxo de resposta chaveado em funções fornecidas pelo usuário, suportado por auxiliares (ground-key, when-ground) para elevar funções de nível de termo em chaves de prune.
defrel/memo e defrel/bank: Combinadores para memoização de relação contra variáveis canônicas frescas. O defrel/bank especificamente fornece enumeração bottom-up com deduplicação compartilhada, transplantando efetivamente o padrão de "lista de trabalho" padrão do PBE para o ambiente relacional.
defrel/bank-w: Uma variante best-first com decaimento de profundidade que utiliza pesos em fluxos imaturos para recuperar a enumeração best-first, permitindo que o sistema encontre representantes compactos mesmo quando a ordem depth-first natural os ignora.
Truques de Implementação: O artigo detalha otimizações de engenharia, como o uso de pairing heaps para mesclagens ordenadas e técnicas de "colapso de thunk", para garantir que a abordagem de memoização performe competitivamente com baselines limitadas por profundidade.

Resultados

Os autores apresentam uma avaliação empírica preliminar em benchmarks de PBE de aritmética e strings (profundidades 0–6).

Ganhos de Desempenho: Em 6 de 8 alvos aritméticos profundos, o defrel/bank é 9–99× mais rápido que o baseline limitado por profundidade (bounded). Isso ocorre porque o bank evita o re-pruning de subexpressões em cada nível recursivo.
Viés de Ordem de Enumeração: O desempenho do defrel/bank é altamente dependente da ordem de enumeração. Ele se destaca quando o alvo da solução reside cedo na ordem depth-first canônica (ex: $x^k$ ou $x^k + c$ ). No entanto, ele tem dificuldades ou sofre timeouts em alvos como $(1+x)^k$ , que aparecem muito tarde no fluxo canônico (ex: posição 243.158 para profundidade 4).
Trade-offs de Best-First: O defrel/bank-w encontra com sucesso representantes compactos para alvos como $(1+x)^k$ precocemente na busca. Contudo, ele incorre em um "custo de largura" (breadth-first cost): emitir uma célula de profundidade $K$ requer a emissão de todas as células de profundidade $<K$ . Em espaços de comportamento largos (milhares de comportamentos distintos na profundidade 3), isso leva a timeouts em al alvos aritméticos profundos onde o defrel/bank teria sucesso.
Comparação com Baseline do Hospedeiro: Um baseline de linguagem hospedeira não relacional (host-bank) performa bem em alvos rasos e famílias de $(1+x)^k$ , mas falha catastroficamente em alvos de espinha direita profundos devido ao custo de construir um banco exaustivo fora do motor relacional. O defrel/bank mantém a interface relacional enquanto recupera a maior parte do ganho de velocidade do host-bank onde o viés de enumeração é favorável.

Significância e Alegações

O artigo afirma que esses combinadores trazem com sucesso a ferramenta padrão de enumeração bottom-up com deduplicação observacional para o ambiente relacional sem deixar o paradigma relacional ou mudar a disciplina de busca do hospedeiro.

Semântica de Opt-in: A abordagem é estritamente opt-in. Não altera a semântica das relações padrão do miniKanren; a deduplicação só se aplica a relações explicitamente envolvidas em prune ou definidas via defrel/bank.
Completude: Os autores argumentam que o pruning preserva a completude em relação à equivalência fornecida pelo usuário. Para cada comportamento, pelo menos um representante é encontrado.
Limitações: Os autores são modestos quanto ao escopo, observando que a avaliação é preliminar, limitada a dois domínios (aritmética e string) e depende de uma gramática específica. Eles reconhecem que o defrel/bank não é uma solução universal; seu sucesso depende da interação entre a forma do alvo e a ordem de enumeração. Eles afirmam explicitamente que a conjunção justa (fair conjunction) não pode resolver o viés de enumeração do defrel/bank porque o viés reside em quais células existem no banco, não em como elas são intercaladas.
Trabalhos Futuros: O artigo identifica várias direções para trabalhos futuros, incluindo o aprofundamento (iterative deepening) sobre o corpo canônico para corrigir o viés do $(1+x)^k$ sem custos de largura, detecção de saturação e extensão da abordagem para stores de restrições mais ricas e outros domínios PBE (ex: vetores de bits, listas).

Em resumo, o artigo demonstra que, ao memoizar relações contra variáveis canônicas e realizar o pruning por equivalência observacional, é possível alcançar ganhos significativos de desempenho na síntese PBE relacional, desde que a ordem de enumeração se alinhe com a estrutura do alvo.