💻 computer science

Towards Bottom-Up Enumeration in miniKanren via Pruning and Memoization

Cet article introduit deux combinateurs de la bibliothèque miniKanren, `prune` et `defrel/bank`, qui permettent une énumération ascendante avec déduplication observationnelle et mémoïsation afin d'améliorer significativement les performances de la synthèse de programmes relationnels sur des cibles profondes, tout en proposant une variante pondérée pour traiter les cas où l'ordonnancement canonique par recherche en profondeur échoue à trouver des représentants compacts.

Auteurs originaux : Nikolai Kudasov

Publié 2026-07-29

📖 8 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Nikolai Kudasov

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous êtes un détective essayant de résoudre un mystère, mais au lieu de chercher des indices, vous essayez de construire une machine capable d'accomplir une tâche spécifique, comme transformer le nombre 2 en 4, 3 en 9 et 4 en 16. Vous ne connaissez pas la formule exacte utilisée par la machine ; vous connaissez seulement les résultats. C'est ce qu'on appelle la « Programmation par l'exemple ». Pour trouver la réponse, vous pourriez essayer de construire chaque machine possible, une par une, en commençant par les engrenages et les leviers les plus simples, et en testant chacune d'elles pour voir si elle fonctionne. C'est un peu comme un chef qui essaierait de trouver une recette secrète en cuisinant toutes les combinaisons possibles de farine, de sucre et d'œufs jusqu'à ce que l'une d'elles ait le bon goût.

Dans le monde de l'informatique, il existe une façon particulière de penser appelée « programmation relationnelle ». Au lieu de dire à l'ordinateur exactement comment trouver la réponse étape par étape, vous décrivez ce à quoi la réponse ressemble, et vous laissez l'ordinateur trouver le chemin. C'est comme dire à un robot : « Trouve-moi un chemin à travers le labyrinthe », plutôt que « Tourne à gauche, puis fais trois pas, puis tourne à droite ». L'ordinateur est excellent pour explorer de nombreux chemins à la fois, mais il a une habitude délicate : il a tendance à explorer les mêmes impasses encore et encore, ou à rester coincé dans un tunnel long et sinueux alors qu'un raccourci court et astucieux se trouve juste à côté. Ce document s'attaque à ce problème en apprenant à l'ordinateur comment être un explorateur plus intelligent et plus organisé.

Le Problème : Se perdre dans le labyrinthe

Imaginez que vous essayiez de trouver une clé spécifique dans un immense grenier désordonné rempli de millions de clés. La plupart de ces clés se ressemblent, mais elles ouvrent toutes exactement la même porte. Si vous êtes un explorateur maladroit, vous pourriez ramasser une clé, l'essayer, réaliser qu'elle fonctionne, puis passer des heures à ramasser d'autres clés qui ont l'air différentes mais qui fonctionnent aussi, juste pour en être sûr. Vous perdez du temps à vérifier des clés qui font exactement le même travail.

Dans le monde des programmes informatiques, cela arrive tout le temps. Lorsqu'un ordinateur essaie de construire un programme pour transformer des entrées en sorties, il génère des milliers de fragments de code d'apparence différente. Beaucoup de ces fragments sont des « jumeaux » déguisés — ils font exactement la même chose même s'ils sont différents à l'intérieur. Une méthode de recherche informatique standard, qui fonctionne comme un explorateur en plongée profonde, vérifiera un jumeau, puis le suivant, puis le suivant, devenant de plus en vraiment plus lente à mesure que le grenier s'agrandit. C'est comme essayer de trouver une aiguille dans une botte de foin, mais la botte de foin est composée de millions d'aiguilles qui ont toutes l'air légèrement différentes.

La Solution : Le « Prune » et la « Bank »

Les auteurs de ce document, Nikolai Kudasov, ont trouvé deux outils ingénieux pour corriger ce désordre. Considérez-les comme un filtre magique et une bibliothèque intelligente.

1. L'outil « Prune » (Le Filtre)
Imaginez que vous avez un tapis roulant de clés sortant d'une machine. L'outil « Prune » est un garde debout à côté du tapis. À chaque fois qu'une clé arrive, le garde vérifie quelle porte elle ouvre. Si le garde a déjà vu une clé qui ouvre cette même porte, il jette simplement la nouvelle clé à la poubelle sans même la tester. Il ne garde que la toute première clé qui ouvre une porte spécifique. De cette façon, le tapis roulant ne transporte que des clés uniques et utiles. L'ordinateur cesse de perdre du temps sur les doublons.

2. L'outil « Bank » (La Bibliothèque Intelligente)
Maintenant, imaginez qu'au lieu de construire des clés à partir de zéro chaque fois que vous en avez besoin, vous avez une bibliothèque magique. Lorsque vous demandez à la bibliothèque une clé, elle ne vous en donne pas seulement une ; elle construit tout un rayon de clés uniques une seule fois, en partant du bas, et les sauvegarde. Si vous demandez une clé plus tard, la bibliothèque vous donne simplement celle qu'elle a déjà construite.

Dans le langage de l'article, cela s'appelle defrel/bank. Cela force l'ordinateur à construire sa liste de programmes candidats d'une manière spécifique et organisée (en commençant par les plus simples) et à sauvegarder les résultats. Si l'ordinateur a besoin d'utiliser un petit morceau d'un programme plus tard, il ne le reconstruit pas ; il le récupère simplement dans la « banque ». Cela permet de gagner un temps considérable car l'ordinateur ne fait jamais le même travail deux fois.

Le Twist : Parfois, « Rapide » n'est pas « Meilleur »

Les auteurs ont également réalisé que le simple fait d'être organisé n'est pas toujours suffisant. Parfois, la « Bank » construit ses rayons dans un ordre qui est rapide pour l'ordinateur mais lent pour l'humain. Par exemple, la Bank pourrait construire toutes les machines de « multiplication » d'abord, et bien plus tard, construire les machines d'« addition ». Si la réponse que vous cherchez est une machine d'« addition », l'ordinateur pourrait devoir vérifier des milliers de machines de multiplication avant de trouver enfin celle dont vous avez besoin.

Pour corriger cela, ils ont créé un troisième outil appelé defrel/bank-w (la Bank « Pondérée »). Cet outil est comme un bibliothécaire qui sait que certains types de clés sont plus susceptibles d'être la réponse. Il utilise un « score » spécial pour décider quelles clés vous montrer en premier. Il essaie de vous montrer les clés les plus simples et les plus compactes en premier, même si elles sont enfouies profondément dans la bibliothèque. C'est idéal si vous voulez la solution la plus élégante, mais cela peut être plus lent si la réponse est en fait une machine complexe et profonde.

Ce qu'ils ont découvert : Vitesse vs Stratégie

Les auteurs ont testé ces outils sur un ensemble d'énigmes mathématiques et de chaînes de caractères (comme transformer « Hello » en « Hello, World ! »). Voici ce qu'ils ont découvert :

La « Bank » est un bolide de vitesse : Sur 6 des 8 problèmes mathématiques difficiles, l'outil defrel/bank était 9 à 99 fois plus rapide que l'ancienne méthode de recherche standard. Il était si rapide qu'il résolvait en une fraction de seconde des problèmes qui prenaient des minutes à l'ancienne méthode.
Mais elle a un angle mort : La Bank est si organisée qu'elle manque parfois la réponse si celle-ci est cachée dans une partie de la bibliothèque qu'elle visite tardivement. Par exemple, si la réponse implique d'additionner des nombres d'une certaine manière (comme $(1+x)^5$ ), la Bank pourrait rester bloquée à vérifier des milliers d'exemples de multiplication d'abord. Dans ces cas, l'ancienne méthode plus lente gagne en réalité car elle vérifie les choses dans un ordre différent.
La « Bank Pondérée » est un compromis : L'outil defrel/bank-w est excellent pour trouver les réponses les plus compactes et élégantes. Il a trouvé la bonne réponse pour une énigme de chaîne de caractères complexe en 10,4 millisecondes, battant les 31,5 millisecondes de la méthode standard. Cependant, pour des problèmes mathématiques très profonds, il s'est parfois retrouvé bloqué en essayant de vérifier trop de possibilités et a expiré (timeout).

L'essentiel

Ce document ne prétend pas avoir résolu tous les problèmes de l'informatique. Au contraire, il montre qu'en ajoutant un peu de « pruning » (filtrage des doublons) et de « banking » (sauvegarde du travail pour plus tard), nous pouvons rendre les programmes informatiques qui construisent d'autres programmes beaucoup plus rapides.

Les auteurs suggèrent que si vous construisez un système pour résoudre des énigmes, vous devriez utiliser l'outil Bank par défaut car il est généralement le plus rapide. Cependant, si vous recherchez une solution très spécifique et compacte, ou si le problème est superficiel et simple, vous pourriez vouloir utiliser la Bank Pondérée ou même l'ancienne méthode. Il ne s'agit pas d'avoir un outil parfait, mais d'avoir le bon outil pour la forme de l'énigme que vous essayez de résoudre. Le document se termine en suggérant que les travaux futurs testeront ces outils sur des énigmes encore plus complexes, comme la construction de programmes comprenant des listes ou des données typées, pour voir si cette accélération se maintient dans le monde réel.

Résumé technique : Vers une énumération ascendante dans miniKanren via l'élagage et la mémoïsation

Énoncé du problème

Les synthétiseurs modernes de Programmation par l'Exemple (PBE) reposent généralement sur une énumération ascendante avec dédoublonnement observationnel. Cette approche maintient une liste de travail d'expressions candidates, les dédoublonne en fonction de leur comportement sur des exemples d'entrée, et les développe niveau par niveau jusqu'à ce qu'une correspondance soit trouvée. Bien que très efficace dans les contextes impératifs et fonctionnels, cette stratégie s'insère maladroitement dans la programmation relationnelle (plus précisément miniKanren), où la discipline de recherche naturelle est la résolution descendante contre un flux équitable de candidats.

Les recettes miniKanren existantes pour la PBE, telles que l'écriture d'un interprète relationnel exécuté « à l'envers » ou l'utilisation d'une approche « énumérer-et-tester » avec des bornes de profondeur, souffrent d'inefficiences significatives à des profondeurs de recherche réalistes. Le problème principal est que l'arbre de recherche contient de nombreuses expressions comportementalement équivalentes. Un énumérateur naïf limité par la profondeur crée une nouvelle table de dédoublonnement à chaque niveau récursif, échouant ainsi à réutiliser le travail effectué aux niveaux précédents. Cela conduit à une explosion exponentielle de l'espace de recherche où des candidats comportementalement identiques sont réévalués de manière répétée.

Méthodologie

Les auteurs proposent deux petits combinateurs de bibliothèque construits sur un noyau $\mu$ Kanren non modifié pour combler l'écart entre la synthèse PBE ascendante et la programmation relationnelle. Ces combinateurs introduisent l'énumération ascendante et le dédoublonnement observationnel sans altérer la discipline de recherche hôte.

1. Le combinateur `prune`

Le premier combinateur, prune, filtre un flux de réponses basé sur une fonction de clé fournie par l'utilisateur.

Mécanisme : Il enveloppe un but (goal) et émet au plus un état par valeur distincte de la fonction de clé (par exemple, le comportement entrée/sortie d'une expression candidate).
Gestion des variables logiques : Pour gérer les cas où la clé dépend de variables logiques non liées, prune utilise une valeur sentinelle (skip-prune). Si une clé ne peut être calculée car un terme n'est pas encore ancré (ground), l'état est émis sans être enregistré dans la table de dédoublonnement. Il est sujet au dédoublonnement uniquement une fois que la variable est liée et que le terme devient ancré.
Portée : Le dédoublonnement est strictement par appel. Une nouvelle table de hachage est créée pour chaque invocation de prune afin d'éviter de confondre « vu comme une variable externe » avec « vu comme une variable interne », ce qui briserait la complétude dans les définitions récursives.

2. Le combinateur `defrel/bank`

Le second combinateur, defrel/bank, étend prune pour parvenir à une véritable énumération ascendante avec un dédoublonnement partagé à travers tous les sites d'appel d'une relation.

Variables canoniques : Il mémoïse une relation par rapport à des variables fraîches canoniques (les $N$ premières variables fraîches d'un état vide), représentant l'appel le plus général de la relation.
La « banque » (bank) : Le corps de la relation est exécuté une seule fois contre ces variables canoniques pour produire un flux canonique (la « banque »). Ce flux est construit de manière ascendante et contient exactement un représentant par classe d'équivalence (déterminée par la clé #:prune).
Rejeu (Replay) : Les appels ultérieurs à la relation n'exécutent pas à nouveau le corps. Au lieu de cela, ils rejouent le flux canonique contre les arguments spécifiques de l'appelant. Cela implique de parcourir la substitution canonique, de renommer les variables internes dans l'espace de noms de l'appelant, et d'unifier les résultats avec les arguments de l'appelant.
Efficacité : Cette approche garantit que le travail de dédoublonnement n'est effectué qu'une seule fois par requête (run ...), quel que soit le nombre de fois que la relation est appelée récursivement.

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

Le defrel/bank standard utilise une récursion en profondeur, ce qui biaise l'ordre d'énumération (par exemple, en favorisant les chaînes de multiplication à spine droite sur l'addition). Pour traiter les cas où la solution cible se trouve profondément dans l'ordre canonique, les auteurs introduisent defrel/bank-w.

Flux pondérés (Weighted Streams) : Cette variante attache des bornes supérieures admissibles (poids) aux cellules de flux immatures.
Décroissance de la profondeur (Depth-Decay) : Un facteur de décroissance est appliqué aux poids aux sites d'appel récursifs. Cela garantit que les représentants plus superficiels ont des poids plus faibles et sont émis en premier par la logique de fusion triée (mplus-w).
Heuristiques paresseuses : Le système utilise une discipline de « plafond paresseux » (lazy-ceiling) où les poids sont consultés sans forcer la thunk sous-jacente, empêchant les boucles infinies lors de la construction du flux canonique. Cela implémente une recherche de type A* où le plafond de poids agit comme une heuristique admissible.

Contributions clés

prune : Un combinateur de dédoublonnement de flux de réponses générique indexé sur des fonctions fournies par l'utilisateur, supporté par des helpers (ground-key, when-ground) pour élever les fonctions de niveau terme en clés de pruning.
defrel/memo et defrel/bank : Combinateurs pour la mémoïsation de relations par rapport à des variables fraîches canoniques. defrel/bank fournit spécifiquement l'énumération ascendante avec un dédoublonnement partagé, transposant efficacement le modèle standard de « liste de travail » PBE dans le cadre relationnel.
defrel/bank-w : Une variante de type « meilleur d'abord » (best-first) avec décroissance de profondeur qui utilise des poids sur les flux immatures pour récupérer l'énumération de type meilleur d'abord, permettant au système de trouver des représentants compacts même lorsque l'ordre de profondeur naturelle les manque.
Astuces d'implémentation : Le papier détaille des optimisations d'ingénierie, telles que l'utilisation de tas de couplage (pairing heaps) pour les fusions triées et des techniques de « effondrement de thunk » (thunk-collapse), pour garantir que l'approche mémoïsée soit compétitive avec les bases de référence limitées par la profondeur.

Résultats

Les auteurs présentent une évaluation empirique préliminaire sur des benchmarks PBE arithmétiques et de chaînes (profondeurs 0–6).

Gains de performance : Sur 6 des 8 cibles arithmétiques profondes, defrel/bank est 9 à 99 fois plus rapide que la base de référence limitée par la profondeur (bounded). C'est parce que bank évite de re-pruner les sous-expressions à chaque niveau récursif.
Biais d'ordre d'énumération : La performance de defrel/bank est fortement dépendante de l'ordre d'énumération. Elle excelle lorsque la solution cible se trouve tôt dans l'ordre canonique de profondeur (ex: $x^k$ ou $x^k + c$ ). Cependant, elle peine ou expire sur des cibles comme $(1+x)^k$ , qui apparaissent très tard dans le flux canonique (ex: position 243 158 pour la profondeur 4).
Compromis Best-First : defrel/bank-w trouve avec succès des représentants compacts pour des cibles comme $(1+x)^k$ tôt dans la recherche. Cependant, il subit un « coût de largeur » (breadth-first cost) : émettre une cellule de profondeur $K$ nécessite d'émettre toutes les cellules de profondeur $< K$ . Sur des espaces de comportement larges (des milliers de comportements distincts à la profondeur 3), cela mène à des dépassements de temps sur des cibles arithmétiques profondes là où defrel/bank réussit.
Comparaison avec la base de référence hôte : Une base de référence dans le langage hôte non relationnel (host-bank) performe bien sur les cibles peu profondes et les familles $(1+x)^k$ , mais échoue de manière catastrophique sur les cibles à spine droite profondes en raison du coût de construction d'une banque exhaustive en dehors du moteur relationnel. defrel/bank conserve l'interface relationnelle tout en récupérant la majeure partie du gain de vitesse de host-bank là où le biais d'énumération est favorable.

Signification et affirmations

Le papier affirme que ces combinateurs parviennent à apporter l'outil standard de l'énumération ascendante avec dédoublonnement observationnel dans le cadre relationnel sans quitter le paradigme relationnel ni changer la discipline de recherche hôte.

Sémantique optionnelle : L'approche est strictement optionnelle. Le dédoublonnement ne s'applique qu'aux relations explicitement enveloppées dans prune ou définies via defrel/bank.
Complétude : Les auteurs soutiennent que le pruning préserve la complétude par rapport à l'équivalence fournie par l'utilisateur. Pour chaque comportement, au moins un représentant est trouvé.
Limites : Ils sont modestes quant à la portée, notant que l'évaluation est préliminaire, limitée à deux domaines (arithmétique et chaînes), et repose sur une grammaire spécifique. Ils reconnaissent que defrel/bank n'est pas une solution universelle ; son succès dépend de l'interaction entre la forme de la cible et l'ordre d'énumération. Ils déclarent explicitement que la conjonction équitable ne peut pas résoudre le biais d'énumération de defrel/bank car le biais réside dans quelles cellules existent dans la banque, et non dans comment elles sont entrelacées.
Travaux futurs : Le papier identifie plusieurs directions pour les travaux futurs, incluant l'endiguement itératif sur le corps canonique pour corriger le biais $(1+x)^k$ sans coûts de largeur, la détection de saturation, et l'extension de l'approche à des registres de contraintes plus riches et d'autres domaines PBE (ex: vecteurs de bits, listes).

En résumé, le papier démontre qu'en mémoïsant les relations par rapport à des variables canoniques et en élaguant par équivalence observationnelle, on peut obtenir des gains de performance significatifs dans la synthèse PBE relationnelle, à condition que l'ordre d'énumération s'aligne sur la structure de la cible.