miniKanren: enumeración ascendente con poda y memoización

Towards Bottom-Up Enumeration in miniKanren via Pruning and Memoization

Se presentan dos combinadores de biblioteca para miniKanren que introducen la enumeración ascendente con deduplicación observacional, herramienta estándar en sintetizadores programación por ejemplo (PBE) no relacionales. El primer combinador, prune, deduplica el flujo de respuestas según una clave definida por el usuario, típicamente el comportamiento de entrada/salida del candidato. El segundo, defrel/bank, memoiza una relación con variables canónicas frescas para construir un único flujo de respuestas podado de forma ascendente y reproducirlo en cada punto de llamada. También se discute una variante ponderada, defrel/bank-w, que asigna cotas superiores admisibles a flujos inmaduros para recuperar la enumeración best-first cuando el orden canónico en profundidad pierde representantes compactos. En un benchmark preliminar de síntesis aritmética y de cadenas, defrel/bank supera sustancialmente a la línea base con profundidad acotada en la mayoría de objetivos profundos, aunque pierde en una pequeña familia donde el orden canónico falla. Se deja una evaluación empírica más amplia para una versión extendida.