Hacia la enumeración bottom-up en miniKanren mediante poda y memoización

Un artículo preprint publicado en arXiv propone dos combinadores de biblioteca sobre miniKanren para trasladar la enumeración ascendente (bottom-up) con deduplicación observacional —técnica habitual en los sintetizadores relacionales programa-a-ejemplo (PBE)— al ámbito de la programación lógica relacional. El primero de los combinadores, llamado prune, elimina duplicados de un flujo de respuestas a partir de una clave definida por el usuario, normalmente el comportamiento de entrada y salida de cada candidato. El segundo, defrel/bank, memoiza una relación frente a variables frescas canónicas, de modo que se construye un único flujo podado de forma ascendente y se reutiliza en todos los puntos de llamada. Los autores también describen una variante ponderada, defrel/bank-w, que adjunta cotas superiores admisibles a flujos todavía no maduros para recuperar la enumeración por mejor primero cuando el orden canónico en profundidad omite representantes compactos. En una batería preliminar de PBE con objetivos de síntesis aritmética y de cadenas de texto, defrel/bank supera de forma notable al límite base con acotación por profundidad en la mayoría de los objetivos profundos, aunque pierde en una pequeña familia de casos en los que el orden canónico en profundidad no captura representantes compactos. Los autores posponen una evaluación empírica más amplia a una versión extendida del trabajo. La contribución se sitúa en la intersección entre lenguajes de programación relacional y síntesis inductiva, áreas donde la eficiencia de la enumeración es un cuello de botella conocido.