Naar Bottom-Up Enumeratie in miniKanren via Pruning en Memoization

Samenvatting

Wij presenteren twee kleine bibliotheekcombinatoren bovenop standaard miniKanren, ontworpen om bottom-up enumeratie met observationele deduplicatie — het standaardinstrument in niet-relationele program-by-example (PBE) synthesizers — naar de relationele setting te brengen.

De eerste combinator, prune, dedupliceert een antwoordstroom aan de hand van een door de gebruiker opgegeven sleutel, gewoonlijk het input/output-gedrag van de kandidaat. De tweede, defrel/bank, memoiseert een relatie tegenover canonieke nieuwe variabelen, zodat één geprunede antwoordstroom bottom-up wordt opgebouwd en bij elke aanroep wordt herhaald.

We bespreken ook een gewogen variant, defrel/bank-w, die toelaatbare bovengrenzen koppelt aan onvoltooide (immature) streams om best-first enumeratie te herstellen in gevallen waarin de natuurlijke depth-first canonieke volgorde compacte representanten mist.

In een voorlopige PBE-benchmark van rekenkundige en string-synthese-doelen presteert defrel/bank aanzienlijk beter dan de baseline met dieptebeperking op de meeste diepe doelen, terwijl het verliest bij een kleine familie waar de canonieke depth-first enumeratievolgorde compacte representanten mist. Wij laten een bredere empirische evaluatie over aan een uitgebreide versie van dit artikel.