💻 computer science

Towards Bottom-Up Enumeration in miniKanren via Pruning and Memoization

Este artículo introduce dos combinadores de la biblioteca miniKanren, `prune` y `defrel/bank`, que permiten la enumeración ascendente con deduplicación observacional y memoización para mejorar significativamente el rendimiento de la síntesis de programas relacionales en objetivos profundos, proponiendo además una variante ponderada para abordar casos donde el ordenamiento canónico de profundidad primero falla al encontrar representantes compactos.

Autores originales: Nikolai Kudasov

Publicado 2026-07-29

📖 7 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Nikolai Kudasov

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que eres un detective tratando de resolver un misterio, pero en lugar de buscar pistas, estás intentando construir una máquina que pueda hacer un trabajo específico, como convertir el número 2 en 4, el 3 en 9 y el 4 en 16. No conoces la fórmula exacta que usa la máquina; solo conoces los resultados. Esto se llama "Programación por Ejemplo". Para encontrar la respuesta, podrías intentar construir cada máquina posible, una por una, comenzando con los engranajes y palancas más simples, y probando cada una para ver si funciona. Esto es un poco como un chef que intenta encontrar una receta secreta horneando todas las combinaciones posibles de harina, azúcar y huevos hasta que una sepa bien.

En el mundo de la informática, existe una forma especial de pensar llamada "programación relacional". En lugar de decirle a la computadora exactamente cómo encontrar la respuesta paso a paso, describes qué aspecto tiene la respuesta y dejas que la computadora encuentre el camino. Es como decirle a un robot: "Encuéntrame un camino a través del laberinto", en lugar de "Gira a la izquierda, luego camina tres pasos y luego gira a la derecha". La computadora es excelente explorando muchos caminos a la vez, pero tiene un hábito difícil: tiende a explorar los mismos callejones sin salida una y otra vez, o se queda atrapada en un túnel largo y sinuoso mientras se pierde un atajo corto y astuto justo al lado. Este artículo aborda ese problema, enseñándole a la computadora a ser una exploradora más inteligente y organizada.

El Problema: Perderse en el Laberinto

Imagina que estás tratando de encontrar una llave específica en un ático gigante y desordenado lleno de millones de llaves. La mayoría de estas llaves se ven diferentes, pero todas abren la misma puerta. Si eres un explorador torpe, podrías tomar una llave, probarla, darte cuenta de que funciona, y luego pasar horas tomando otras llaves que se ven diferentes pero que también funcionan, solo para estar seguro. Estás perdiendo el tiempo revisando llaves que hacen exactamente el mismo trabajo.

En el mundo de los programas informáticos, esto sucede todo el tiempo. Cuando una computadora intenta construir un programa para convertir entradas en salidas, genera miles de fragmentos de código que se ven diferentes. Muchos de estos fragmentos son "gemelos" disfrazados: hacen exactamente lo mismo aunque se vean diferentes por dentro. Un método de búsqueda estándar de computadora, que funciona como un explorador de inmersión profunda, revisará un gemelo, luego el siguiente, luego el siguiente, volviéndose cada vez más lento a medida que el ático se hace más grande. Es como intentar encontrar una aguja en un pajar, pero el pajar está hecho de millones de agujas que todas se ven ligeramente diferentes.

La Solución: La "Poda" y el "Banco"

Los autores de este artículo, Nikolai Kudsov, idearon dos herramientas ingeniosas para solucionar este lío. Piensa en ellas como un filtro mágico y una biblioteca inteligente.

1. La herramienta de "Poda" (El Filtro)
Imagina que tienes una cinta transportadora de llaves saliendo de una máquina. La herramienta de "Poda" es un guardia parado junto a la cinta. A medida que llega cada llave, el guardia revisa qué puerta abre. Si el guardia ya ha visto una llave que abre esa misma puerta, simplemente lanza la nueva llave a la basura sin siquiera probarla. Solo conserva la primera llave que abre una puerta específica. De esta manera, la cinta transportadora solo lleva llaves únicas y útiles. La computadora deja de perder el tiempo con duplicados.

2. La herramienta del "Banco" (La Biblioteca Inteligente)
Ahora, imagina que en lugar de construir llaves desde cero cada vez que necesitas una, tienes una biblioteca mágica. Cuando le pides una llave a la biblioteca, no solo te da una; construye un estante entero de llaves únicas una sola vez, desde la base, y las guarda. Si pides una llave más tarde, la biblioteca simplemente te entrega la que ya construyó.

En el lenguaje del artículo, esto se llama defrel/bank. Obliga a la computadora a construir su lista de programas candidatos de una manera específica y organizada (comenzando con los más simples) y guarda los resultados. Si la computadora necesita usar una pieza pequeña de un programa más tarde, no la reconstruye; simplemente toma la pieza del "banco". Esto ahorra una cantidad masiva de tiempo porque la computadora nunca tiene que hacer el mismo trabajo dos veces.

El Giro: A veces "Rápido" no es "Lo Mejor"

Los autores también se dieron cuenta de que ser organizado no siempre es suficiente. A veces, el "Banco" construye sus estantes en un orden que es rápido para la computadora pero lento para el humano. Por ejemplo, el Banco podría construir primero todas las máquinas de "multiplicación" y mucho después construir las máquinas de "adición". Si la respuesta que buscas es una máquina de "adición", la computadora podría tener que revisar miles de máquinas de multiplicación antes de encontrar finalmente la que necesitas.

Para solucionar esto, crearon una tercera herramienta llamada defrel/bank-w (el Banco "Ponderado"). Esta herramienta es como un bibliotecario que sabe que algunos tipos de llaves tienen más probabilidades de ser la respuesta. Utiliza una "puntuación" especial para decidir qué llaves mostrarte primero. Intenta mostrarte las llaves más simples y compactas primero, incluso si están enterradas profundamente en la biblioteca. Esto es excelente si quieres la solución más elegante, pero puede ser más lento si la respuesta es una máquina compleja y profunda.

Lo que Encontraron: Velocidad vs. Estrategia

Los autores probaron estas herramientas en un conjunto de acertijos matemáticos y de cadenas (como convertir "Hello" en "Hello, World!"). Esto es lo que descubrieron:

El "Banco" es un demonio de la velocidad: En 6 de 8 problemas matemáticos difíciles, la herramienta defrel/bank fue de 9 a 99 veces más rápida que el método de búsqueda estándar. Fue tan rápida que resolvió en una fracción de segundo problemas que al método antiguo le tomaba minutos terminar.
Pero tiene un punto ciego: El Banco es tan organizado que a veces pierde la respuesta si esa respuesta está escondida en una parte de la biblioteca que visita tarde. Por ejemplo, si la respuesta implica sumar números de una manera específica (como $(1+x)^5$ ), el Banco podría quedarse atrapado revisando miles de ejemplos de multiplicación primero. En estos casos, el método antiguo y más lento en realidad gana porque revisa las cosas en un orden diferente.
El "Banco Ponderado" es un compromiso: La herramienta defrel/bank-w es excelente para encontrar las respuestas más compactas y elegantes. Encontró la respuesta correcta para un acertijo de cadenas complicado en 10.4 milisegundos, superando los 31.5 milisegundos del método estándar. Sin embargo, para problemas matemáticos muy profundos, a veces se quedaba trabada intentando revisar demasiadas posibilidades y agotaba el tiempo.

La Conclusión

Este artículo no pretende haber resuelto todos los problemas de la informática. En cambio, muestra que al añadir un poco de "poda" (filtrar duplicados) y "bancar" (guardar el trabajo para después), podemos hacer que los programas de computadora que construyen otros programas sean mucho, mucho más rápidos.

Los autores sugieren que, si estás construyendo un sistema para resolver acertijos, deberías usar la herramienta del Banco como tu opción predeterminada porque suele ser la más rápida. Sin embargo, si buscas una solución muy específica y compacta, o si el problema es superficial y simple, es posible que quieras usar el Banco Ponderado o incluso el método tradicional. No se trata de que una herramienta sea perfecta; se trata de tener la herramienta adecuada para la forma del acertijo que intentas resolver. El artículo termina sugiriendo que trabajos futuros probarán estas herramientas en acertijos aún más complejos, como construir programas que entiendan listas o datos tipados, para ver si esta aceleración se mantiene en el mundo real.

Resumen Técnico: Hacia la Enumeración Bottom-Up en miniKanren mediante Pruning y Memoización

Planteamiento del Problema

Los sintetizadores modernos de Programación por Ejemplo (PBE) suelen depender de la enumeración bottom-up con deduplicación observacional. Este enfoque mantiene una lista de trabajo de expresiones candidatas, las deduplica basándose en su comportamiento sobre ejemplos de entrada y las expande nivel por nivel hasta encontrar una coincidencia. Aunque es altamente efectivo en entornos imperativos y funcionales, esta estrategia se sitúa de forma incómoda en la programación relacional (específicamente en miniKanren), donde la disciplina de búsqueda natural es la resolución top-down contra un flujo justo de candidatos.

Las recetas existentes de miniKanren para PBE, como escribir un intérprete relacional y ejecutarlo "hacia atrás" o utilizar un enfoque de "enumerar y probar" con límites de profundidad, sufren de ineficiencias significativas en profundidades de búsqueda realistas. El problema principal es que el árbol de búsqueda contiene muchas expresiones conductualmente equivalentes. Un enumerador ingenuo limitado por profundidad crea una tabla de deduplicación fresca en cada nivel recursivo, fallando al no reutilizar el trabajo realizado en niveles previos. Esto conduce a una explosión exponencial en el espacio de búsqueda donde candidatos conductualmente idénticos son reevaluados repetidamente.

Metodología

Los autores proponen dos pequeños combinadores de librería construidos sobre un núcleo $\mu$ Kanren sin modificar para cerrar la brecha entre la síntesis PBE bottom-up y la programación relacional. Estos combinadores introducen la enumeración bottom-up y la deduplicación observacional sin alterar la disciplina de búsqueda del lenguaje anfitrión.

1. El combinador `prune`

El primer combinador, prune, filtra un flujo de respuestas basado en una función de clave suministrada por el usuario.

Mecanismo: Envuelve un objetivo y emite como máximo un estado por cada valor distinto de la función de clave (por ejemplo, el comportamiento de entrada/salida de una expresión candidata).
Manejo de Variables Lógicas: Para manejar casos donde la clave depende de variables lógicas aún no vinculadas, prune utiliza un valor centinela (skip-prune). Si una clave no puede ser computada porque un término aún no es ground, el estado se emite sin ser registrado en la tabla de deduplicación. Está sujeto a deduplicación solo una vez que la variable es vinculada y el término se vuelve ground.
Alcance: La deduplicación es estrictamente por llamada. Se crea una tabla hash fresca para cada invocación de prune para evitar confundir "visto como una variable externa" con "visto como una variable interna", lo que de otro modo rompería la completitud en definiciones recursivas.

2. El combinador `defrel/bank`

El segundo combinador, defrel/bank, extiende prune para lograr una verdadera enumeración bottom-up con deduplicación compartida en todos los sitios de llamada de una relación.

Variables Canónicas: Memoiza una relación contra variables frescas canónicas (las primeras $N$ variables frescas de un estado vacío), representando la llamada más general de la relación.
El "Banco" (Bank): El cuerpo de la relación se ejecuta una sola vez contra estas variables canónicas para producir un flujo canónico (el "banco"). Este flujo se construye bottom-up y contiene exactamente un representante por clase de equivalencia (determinada por la clave #:prune).
Replay: Las llamadas subsecuentes a la relación no reejecutan el cuerpo. En su lugar, reproducen (replay) el flujo canónico contra los argumentos específicos del llamador. Esto implica recorrer la sustitución canónica, renombrar las variables internas al espacio de nombres del llamador y unificar los resultados con los argumentos del llamador.
Eficiencia: Este enfoque asegura que el trabajo de deduplicación se realice solo una vez por consulta (run ...), independientemente de cuántas veces se llame la relación recursivamente.

3. La variante `defrel/bank-w` (Best-First)

El defrel/bank estándar utiliza recursión depth-first, lo que sesga el orden de enumeración (por ejemplo, favoreciendo cadenas de multiplicación de espina derecha sobre la suma). Para abordar casos donde la solución objetivo se encuentra profunda en el orden canónico, los autores introducen defrel/bank-w.

Flujos Ponderados (Weighted Streams): Esta variante adjunta límites superiores admisibles (pesos) a las células inmaduras del flujo.
Decaimiento de Profundidad (Depth-Decay): Se aplica un factor de decaimiento a los pesos en los sitios de llamada recursiva. Esto asegura que los representantes más superficiales tengan pesos menores y sean emitidos primero por la lógica de fusión ordenada (mplus-w).
Heurísticas Perezosas (Lazy Heuristics): El sistema utiliza una disciplina de "techo perezoso" (lazy-ceiling) donde los pesos se observan sin forzar el thunk subyacente, evitando bucles infinitos durante la construcción del flujo canónico. Esto implementa una búsqueda de estilo A* donde el techo del peso actúa como una heurística admisible.

Contribuciones Clave

prune: Un combinador de deduplicación de flujo de respuestas genérico basado en funciones de clave suministradas por el usuario, soportado por ayudantes (ground-key, when-ground) para elevar funciones de nivel de término a claves de poda.
defrel/memo y defrel/bank: Combinadores para la memoización de relaciones contra variables frescas canónicas. defrel/bank proporciona específicamente la enumeración bottom-up con deduplicación compartida, transplantando efectivamente el patrón de "lista de trabajo" estándar de PBE al entorno relacional.
defrel/bank-w: Una variante best-first con decaimiento de profundidad que utiliza pesos en flujos inmaduros para recuperar la enumeración best-first, permitiendo al sistema encontrar representantes compactos incluso cuando el orden depth-first natural los pasa por alto.
Trucos de Implementación: El artículo detalla optimizaciones de ingeniería, como el uso de montículos de emparejamiento (pairing heaps) para fusiones ordenadas y técnicas de "colapso de thunk", para asegurar que el enfoque de memoización sea competitivo con las líneas base limitadas por profundidad.

Resultados

Los autores presentan una evaluación empírica preliminar en benchmarks de PBE de aritmética y strings (profundidades 0–6).

Ganancias de Rendimiento: En 6 de 8 objetivos aritméticos profundos, defrel/bank es de 9 a 99 veces más rápido que la línea base limitada por profundidad (bounded). Esto se debe a que bank evita la repoda de subexpresiones en cada nivel recursivo.
Sesgo de Orden de Enumeración: El rendimiento de defrel/bank es altamente dependiente del orden de enumeración. Sobresale cuando la solución objetivo se encuentra temprano en el orden depth-first canónico (por ejemplo, $x^k$ o $x^k + c$ ). Sin embargo, tiene dificultades o agota el tiempo de ejecución en objetivos como $(1+x)^k$ , que aparecen muy tarde en el flujo canónico (por ejemplo, posición 243,158 para profundidad 4).
Compromisos de Best-First: defrel/bank-w encuentra con éxito representantes compactos para objetivos como $(1+x)^k$ de forma temprana en la búsqueda. Sin embargo, incurre en un "costo de breadth-first": emitir una celda de profundidad $K$ requiere emitir todas las celdas de profundidad $<K$ . En espacios de comportamiento anchos (miles de comportamientos distintos en profundidad 3), esto conduce a tiempos de espera en objetivos aritméticos profundos donde defrel/bank tiene éxito.
Comparación con la Línea Base del Lenguaje Anfitrión: Una línea base del lenguaje anfitrión no relacional (host-bank) funciona bien en objetivos superficiales y familias de $(1+x)^k$ , pero falla catastróficamente en objetivos de espina derecha profunda debido al costo de construir un banco exhaustivo fuera del motor relacional. defrel/bank mantiene la interfaz relacional mientras recupera la mayor parte de la mejora de velocidad de host-bank donde el sesgo de enumeración es favorable.

Significancia y Reivindicaciones

El artículo afirma que estos combinadores logran traer la herramienta estándar de la enumeración bottom-up con deduplicación observacional al entorno relacional sin abandonar el paradigma relacional ni cambiar la disciplina de búsqueda del anfitrión.

Semántica Optativa (Opt-in): El enfoque es estrictamente optativo. No altera la semántica de las relaciones estándar de miniKanren; la deduplicación solo se aplica a las relaciones envueltas explícitamente en prune o definidas vía defrel/bank.
Completitud: Los autores argumentan que la poda preserva la completitud con respecto a la equivalencia suministrada por el usuario. Para cada comportamiento, se encuentra al menos un representante.
Limitaciones: Son modestos sobre el alcance, señalando que la evaluación es preliminar, limitada a dos dominios (aritmética y strings), y depende de una gramática específica. Reconocen que defrel/bank no es una solución universal; su éxito depende de la interacción entre la forma del objetivo y el orden de enumeración. Establecen explícitamente que la conjunción justa no puede resolver el sesgo de enumeración de defrel/bank porque el sesgo reside en qué celdas existen en el banco, no en cómo se intercalan.
Trabajo Futuro: El artículo identifica varias direcciones para el trabajo futuro, incluyendo el endurecimiento de profundidad (iterative deepening) sobre el cuerpo canónico para corregir el sesgo de $(1+x)^k$ sin costos de breadth-first, la detección de saturación y la extensión del enfoque a almacenes de restricciones más ricos y otros dominios de PBE (por ejemplo, vectores de bits, listas).

En resumen, el artículo demuestra que, al memoizar relaciones contra variables canónicas y podar por equivalencia observacional, se pueden lograr mejoras significativas de rendimiento en la síntesis PBE relacional, siempre que el orden de enumeración se alinee con la estructura del objetivo.