💻 computer science

Towards Bottom-Up Enumeration in miniKanren via Pruning and Memoization

यह शोध पत्र दो miniKanren लाइब्रेरी कॉम्बिनेटर्स, `prute` और `defrel/bank` को प्रस्तुत करता है, जो गहरे लक्ष्यों (deep targets) पर रिलेशनल प्रोग्राम सिंथेसिस के प्रदर्शन को महत्वपूर्ण रूप से सुधारने के लिए ऑब्जर्वेशनल डिडुप्लिकेशन (observational deduplication) और मेमोइज़ेशन (memoization) के साथ बॉटम-अप एन्यूमरेशन को सक्षम करते हैं, साथ ही उन मामलों को संबोधित करने के लिए एक वेटेड वेरिएंट का भी प्रस्ताव देते हैं जहाँ कैनोनिकल डेप्थ-फर्स्ट ऑर्डरिंग कॉम्पैक्ट रिप्रेजेंटेटिव्स खोजने में विफल रहती है।

मूल लेखक: Nikolai Kudasov

प्रकाशित 2026-07-29

📖 8 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Nikolai Kudasov

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक जासूस हैं जो एक रहस्य सुलझाने की कोशिश कर रहे हैं, लेकिन सुराग खोजने के बजाय, आप एक ऐसी मशीन बनाने की कोशिश कर रहे हैं जो एक विशिष्ट काम कर सके, जैसे संख्या 2 को 4 में, 3 को 9 में और 4 को 16 में बदलना। आप सटीक फॉर्मूला नहीं जानते कि मशीन क्या उपयोग करती है; आप केवल परिणाम जानते हैं। इसे "प्रोग्रामिंग बाय एग्जांपल" (उदाहरण द्वारा प्रोग्रामिंग) कहा जाता है। उत्तर खोजने के लिए, आप हर संभव मशीन को एक-एक करके, सबसे सरल गियर और लीवरों से शुरू करते हुए बनाने की कोशिश कर सकते हैं और प्रत्येक का परीक्षण कर सकते हैं कि क्या वह काम करती है। यह एक शेफ की तरह है जो आटे, चीनी और अंडों के हर संभावित संयोजन को तब तक बेक करके गुप्त रेसिपी खोजने की कोशिश करता है जब तक कि एक सही स्वाद न मिल जाए।

कंप्यूटर विज्ञान की दुनिया में, सोचने का एक विशेष तरीका है जिसे "रिलेशनल प्रोग्रामिंग" कहा जाता है। यह बताने के बजाय कि कंप्यूटर को चरण-दर-चरण उत्तर कैसे खोजना है, आप वर्णन करते हैं कि उत्तर कैसा दिखता है, और कंप्यूटर को रास्ता खोजने देते हैं। यह एक रोबोट को बताने जैसा है, "मेरे लिए भूलभुलैया के माध्यम से एक रास्ता खोजो," बजाय इसके कि "बाएं मुड़ें, फिर तीन कदम चलें, फिर दाएं मुड़ें।" कंप्यूटर एक साथ कई रास्तों को खोजने में बहुत अच्छा है, लेकिन इसकी एक अजीब आदत है: यह बार-बार एक ही डेड एंड (बंद रास्ते) को खोजने या एक लंबे, घुमावदार टनल में फंस जाने की प्रवृत्ति रखता है, जबकि उसके ठीक बगल में एक छोटा, चतुर शॉर्टकट मौजूद हो सकता है। यह पेपर इसी समस्या को हल करता है, यह सिखाकर कि कंप्यूटर को एक स्मार्ट और अधिक व्यवस्थित खोजकर्ता कैसे बनाया जाए।

समस्या: भूलभुलैया में खो जाना

कल्पना कीजिए कि आप लाखों चाबियों से भरी एक विशाल, अस्त-व्यस्त अटारी में एक विशिष्ट चाबी खोजने की कोशिश कर रहे हैं। इनमें से अधिकांश चाबियाँ अलग दिखती हैं, लेकिन वे सभी एक ही दरवाजे को खोलती हैं। यदि आप एक अनाड़ी खोजकर्ता हैं, तो आप एक चाबी उठा सकते हैं, उसे आजमा सकते हैं, एहसास कर सकते हैं कि यह काम करती है, और फिर यह सुनिश्चित करने के लिए अन्य चाबियाँ उठाने में घंटों बिता सकते हैं जो अलग दिखती हैं लेकिन फिर भी काम करती हैं। आप उन चाबियों की जांच करने में समय बर्बाद कर रहे हैं जो बिल्कुल एक ही काम करती हैं।

कंप्यूटर प्रोग्रामों की दुनिया में, यह हमेशा होता है। जब एक कंप्यूटर इनपुट को आउटपुट में बदलने के लिए एक प्रोग्राम बनाने की कोशिश करता है, तो वह हजारों अलग-अलग दिखने वाले कोड स्निपेट्स (कोड के टुकड़े) बनाता है। इनमें से कई स्निपेट्स "जुड़वां" होते हैं—वे अंदर से अलग दिखने के बावजूद बिल्कुल एक ही काम करते हैं। एक मानक कंप्यूटर खोज विधि, जो एक गहरे गोता लगाने वाले खोजकर्ता की तरह काम करती है, एक जुड़वां को चेक करेगी, फिर दूसरे को, फिर अगले को, जिससे वह धीरे-धीरे धीमी होती जाएगी। यह घास के ढेर में सुई खोजने जैसा है, लेकिन घास का ढेर लाखों सुइयों से बना है जो सभी थोड़ी अलग दिखती हैं।

समाधान: "प्रून" (छंटनी) और "बैंक"

इस पेपर के लेखक, निकोलाई कुडासोव ने इस गड़बड़ी को ठीक करने के लिए दो चतुर उपकरण दिए हैं। इन्हें एक जादुई फिल्टर और एक स्मार्ट लाइब्रेरी के रूप में सोचें।

1. "प्रून" टूल (द फिल्टर)
कल्पना कीजिए कि एक मशीन से बाहर आती चाबियों का एक कन्वेयर बेल्ट है। "प्रून" टूल उस बेल्ट के पास खड़ा एक गार्ड है। जैसे ही प्रत्येक चाबी आती है, गार्ड यह जांचता है कि वह कौन सा दरवाजा खोलती है। यदि गार्ड ने पहले ही एक ऐसी चाबी देख ली है जो वही दरवाजा खोलती है, तो वह उस नई चाबी को बिना टेस्ट किए ही कचरे में फेंक देता है। वे केवल उस विशिष्ट दरवाजे को खोलने वाली पहली चाबी को रखते हैं। इस तरह, कन्वेयर बेल्ट केवल अद्वितीय, उपयोगी चाबियाँ ले जाता है। कंप्यूटर डुप्लिकेट्स पर समय बर्बाद करना बंद कर देता है।

2. "बैंक" टूल (द स्मार्ट लाइब्रेरी)
अब, कल्पना कीजिए कि हर बार जब आपको एक चाबी की आवश्यकता होती है, तो उसे शून्य से बनाने के बजाय, आपके पास एक जादुई लाइब्रेरी है। जब आप लाइब्रेरी से एक चाबी मांगते हैं, तो वह केवल एक नहीं देती; बल्कि वह एक बार, नीचे से ऊपर की ओर बढ़ते हुए, अद्वितीय चाबियों की एक पूरी शेल्फ बनाती है और उन्हें सहेज लेती है। यदि आप बाद में फिर से किसी चाबी के लिए पूछते हैं, तो लाइब्रेरी बस वही चाबी आपको थमा देती है जो उसने पहले ही बना ली थी।

पेपर की भाषा में, इसे defrel/bank कहा जाता है। यह कंप्यूटर को अपने उम्मीदवार प्रोग्रामों की सूची एक विशिष्ट, व्यवस्थित तरीके से बनाने (सबसे सरल से शुरू करते हुए) और परिणामों को सहेजने के लिए मजबूर करता है। यदि कंप्यूटर को बाद में एक प्रोग्राम के छोटे हिस्से का उपयोग करने की आवश्यकता होती है, तो वह उसे फिर से नहीं बनाता है; वह बस उस हिस्से को "बैंक" से उठा लेता है। यह बहुत सारा समय बचाता है क्योंकि कंप्यूटर को कभी भी एक ही काम दोबारा नहीं करना पड़ता।

ट्विस्ट: कभी-कभी "तेज़" होना "सर्वश्रेष्ठ" नहीं होता

लेखकों ने यह भी महसूस किया कि केवल व्यवस्थित होना हमेशा पर्याप्त नहीं होता है। कभी-कभी, "बैंक" अपनी शेल्फ को ऐसे क्रम में बनाता है जो कंप्यूटर के लिए तेज़ है लेकिन इंसान के लिए धीमा है। उदाहरण के लिए, बैंक पहले सभी "गुणा" (multiplication) वाली मशीनें बना सकता है, और बहुत बाद में "जोड़" (addition) वाली मशीनें बना सकता है। यदि आप जिस उत्तर की तलाश कर रहे हैं वह एक "जोड़" वाली मशीन है, तो कंप्यूटर को उस एक को खोजने से पहले हजारों गुणा मशीनों को चेक करने में समय लग सकता है।

इसे ठीक करने के लिए, उन्होंने तीसरा उपकरण बनाया जिसे defrel/bank-w ("वेटेड" बैंक) कहा जाता है। यह टूल एक ऐसे लाइब्रेरियन की तरह है जो जानता है कि कुछ प्रकार की चाबियाँ उत्तर होने की अधिक संभावना रखती हैं। यह यह तय करने के लिए एक विशेष "स्कोर" का उपयोग करता है कि कौन सी चाबियाँ आपको पहले दिखानी हैं। यह आपको सबसे सरल, सबसे संक्षिप्त चाबियाँ पहले दिखाने की कोशिश करता है, भले ही वे लाइब्रेरी में गहराई में दबी हों। यह बहुत अच्छा है यदि आप सबसे सुंदर समाधान चाहते हैं, लेकिन यह धीमा हो सकता है यदि उत्तर वास्तव में एक जटिल, गहरी मशीन है।

उन्होंने क्या पाया: गति बनाम रणनीति

लेखकों ने गणित और स्ट्रिंग पहेलियों (जैसे "Hello" को "Hello, World!" में बदलना) के एक सेट पर इन उपकरणों का परीक्षण किया। यहाँ उन्होंने क्या खोजा:

"बैंक" एक स्पीड डेमन (गति का दैत्य) है: 8 कठिन गणितीय समस्याओं में से 6 पर, defrel/bank टूल पुराने, मानक खोज तरीके की तुलना में 9 से 99 गुना तेज़ था। यह इतना तेज़ था कि इसने उन समस्याओं को सेकंड के एक अंश में हल कर दिया जिन्हें पुराने तरीके को पूरा करने में मिनटों लग जाते थे।
लेकिन इसकी एक कमजोरी है: बैंक इतना व्यवस्थित है कि यह कभी-कभी उत्तर को मिस कर देता है यदि वह उत्तर लाइब्रेरी के उस हिस्से में छिपा है जिसे वह देर से देखता है। उदाहरण के लिए, यदि उत्तर में संख्याओं को एक विशिष्ट तरीके से जोड़ना शामिल है (जैसे $(1+x)^5$ ), तो बैंक हजारों गुणा उदाहरणों को चेक करने में फंस सकता है। इन मामलों में, पुराना, धीमा तरीका वास्तव में जीत जाता है क्योंकि वह एक अलग क्रम में चीजें चेक करता है।
"वेटेड" बैंक एक समझौता है: defrel/bank-w टूल सबसे संक्षिप्त, सुंदर उत्तर खोजने में उत्कृष्ट है। इसने एक पेचीदा स्ट्रिंग पहेली के लिए सही उत्तर 10.4 मिलीसेकंड में खोज लिया, जो मानक पद्धति के 31.5 मिलीसेकंड को हरा देता है। हालाँकि, बहुत गहरी गणितीय समस्याओं के लिए, यह बहुत सारी संभावनाओं को चेक करने की कोशिश में फंस गया और टाइम आउट हो गया।

निष्कर्ष

यह पेपर यह दावा नहीं करता कि इसने कंप्यूटर विज्ञान की हर समस्या को हल कर लिया है। इसके बजाय, यह दिखाता है कि थोड़ा सा "प्रूनिंग" (डुप्लिकेट्स को फ़िल्टर करना) और "बैंकिंग" (काम को बाद के लिए सहेजना) जोड़कर, हम अन्य प्रोग्राम बनाने वाले कंप्यूटर प्रोग्रामों को बहुत, बहुत तेज़ बना सकते हैं।

लेखक सुझाव देते हैं कि यदि आप पहेलियाँ सुलझाने के लिए एक सिस्टम बना रहे हैं, तो आपको Bank टूल को अपना डिफ़ॉल्ट बनाना चाहिए क्योंकि यह आमतौर पर सबसे तेज़ होता है। हालाँकि, यदि आप एक बहुत ही विशिष्ट, संक्षिप्त समाधान की तलाश में हैं, या यदि समस्या उथली और सरल है, तो आप Weighted Bank या पुराने तरीके का उपयोग करना चाह सकते हैं। यह केवल एक उपकरण के पूर्ण होने के बारे में नहीं है; यह इस बारे में है कि आपके द्वारा हल की जाने वाली पहेली के आकार के लिए सही उपकरण कौन सा है। पेपर इस सुझाव के साथ समाप्त होता है कि भविष्य के कार्य इन उपकरणों का और भी अधिक जटिल पहेलियों, जैसे कि लिस्ट या टाइप किए गए डेटा को समझने वाले प्रोग्राम बनाने पर परीक्षण करेंगे, ताकि यह देखा जा सके कि क्या यह गति-वृद्धि वास्तविक दुनिया में भी बनी रहती है।

तकनीकी सारांश: प्रूनिंग और मेमोइज़ेशन के माध्यम से miniKanren में बॉटम-अप एन्यूमरेशन की ओर

समस्या विवरण

आधुनिक प्रोग्राम-बाय-एग्जांपल (PBE) सिंथेसाइज़र आमतौर पर ऑब्जर्वेशनल डीडुप्लीकेशन के साथ बॉटम-अप एन्यूमरेशन पर निर्भर करते हैं। यह दृष्टिकोण उम्मीदवार अभिव्यक्तियों (candidate expressions) का एक वर्कलिस्ट बनाए रखता है, उन्हें उदाहरण इनपुट पर उनके व्यवहार के आधार पर डीडुप्लिकेट करता है, और एक मिलान मिलने तक उन्हें स्तर-दर-स्तर (level-by-level) विस्तारित करता है। हालांकि यह अपैरेटिव और फंक्शनल सेटिंग्स में अत्यधिक प्रभावी है, यह रणनीति रिलेशनल प्रोग्रामिंग (विशेष रूप से miniKanren) में अजीब तरह से बैठती है, जहाँ स्वाभाविक खोज अनुशासन (search discipline) उम्मीदवारों के एक फेयर स्ट्रीम के विरुद्ध टॉप-डाउन रेजोल्यूशन है।

मौजूदा miniKanren रेसिपीज़, जैसे कि एक रिलेशनल इंटरप्रेटर लिखना और उसे "बैकवर्ड्स" चलाना या डेप्थ बाउंड्स के साथ "एन्यूमेरेट-एंड-टेस्ट" दृष्टिकोण का उपयोग करना, वास्तविक खोज गहराई पर महत्वपूर्ण अक्षमताओं से ग्रस्त हैं। प्राथमिक मुद्दा यह है कि सर्च ट्री में कई व्यवहारिक रूप से समान (behaviorally equivalent) अभिव्यक्तियाँ होती हैं। एक नाईव डेप्थ-बाउंडेड एन्यूमेटर प्रत्येक रिकर्सिव लेवल पर एक फ्रेश डीडुप्लीकेशन टेबल बनाता है, जिससे पिछले स्तरों पर किए गए कार्य का पुन: उपयोग करने में विफलता होती है। इससे खोज स्थान (search space) में एक्सपोनेंशियल ब्लोअप होता है जहाँ व्यवहारिक रूप से समान उम्मीदवारों का बार-बार मूल्यांकन किया जाता है।

कार्यप्रणाली

लेखक एक अपरिवर्तित $\mu$ Kanren कोर के ऊपर निर्मित दो छोटे लाइब्रेरी कॉम्बिनेटर्स का प्रस्ताव करते हैं जो बॉटम-अप PBE सिंथेसिस और रिलेशनल प्रोग्रामिंग के बीच के अंतर को पाटते हैं। ये कॉम्बिनेटर्स होस्ट सर्च डिसिप्लिन को बदले बिना बॉटम-अप एन्यूमरेशन और ऑब्जर्वेशनल डीडुप्लीकेशन पेश करते हैं।

1. `prune` कॉम्बिनेटर

पहला कॉम्बिनेटर, prune, एक उपयोगकर्ता-प्रदान किए गए की-फंक्शन के आधार पर उत्तर स्ट्रीम (answer stream) को फ़िल्टर करता है।

तंत्र: यह एक गोल (goal) को रैप करता है और की-फंक्शन (जैसे, उम्मीदवार अभिव्यक्ति का इनपुट/आउटपुट व्यवहार) के विशिष्ट मान के लिए अधिकतम एक स्टेट उत्सर्जित करता है।
लॉजिक वेरिएबल्स को संभालना: उन मामलों को संभालने के लिए जहाँ की (key) अनबाउंड लॉजिक वेरिएबल्स पर निर्भर है, prune एक सेंटिनल वैल्यू (skip-prune) का उपयोग करता है। यदि कोई टर्म ग्राउंड न होने के कारण की (key) कंप्यूट नहीं की जा सकती है, तो स्टेट को डीडुप्लीकेशन टेबल में रिकॉर्ड किए बिना उत्सर्जित किया जाता है। यह केवल तभी डीडुप्लीकेशन के अधीन होता है जब वेरिएबल बाउंड हो जाता है और टर्म ग्राउंड हो जाता है।
स्कोप: डीडुप्लीकेशन सख्ती से प्रति-कॉल (per-call) होता है। प्रत्येक इन्वोकेशन के लिए एक फ्रेश हैश टेबल बनाया जाता है ताकि "बाहरी वेरिएबल के रूप में देखा गया" बनाम "आंतरिक वेरिएबल के रूप में देखा गया" के बीच भ्रम न हो, जो अन्यथा रिकर्सिव डेफिनिशन में पूर्णता (completeness) को तोड़ सकता है।

2. `defrel/bank` कॉम्बिनेटर

दूसरा कॉम्बिनेटर, defrel/bank, एक रिलेशन के सभी कॉल साइट्स में साझा डीडुप्लीकेशन के साथ वास्तविक बॉटम-अप एन्यूमरेशन प्राप्त करने के लिए prune का विस्तार करता है।

कैनोनिकल वेरिएबल्स: यह रिलेशन को कैनोनिकल फ्रेश वेरिएबल्स (एक खाली स्टेट के पहले $N$ फ्रेश वेरिएबल्स) के विरुद्ध मेमोइज़ करता है, जो रिलेशन के सबसे सामान्य कॉल का प्रतिनिधित्व करते हैं।
"बैंक" (The Bank): रिलेशन बॉडी को इन कैनोनिकल वेरिएबल्स के विरुद्ध एक बार निष्पादित किया जाता है ताकि एक कैनोनिकल स्ट्रीम (जिसे "बैंक" कहा जाता है) बनाई जा सके। यह स्ट्रीम बॉटम-अप बनाई जाती है और इसमें प्रत्येक इक्विवेलेंस क्लास का ठीक एक प्रतिनिधि होता है (जो #:prune की द्वारा निर्धारित होता है)।
रीप्ले (Replay): बाद के कॉल रिलेशन को दोबारा निष्पादित नहीं करते हैं। इसके बजाय, वे कॉलर के विशिष्ट आर्गुमेंट्स के विरुद्ध कैनोनिकल स्ट्रीम को रीप्ले करते हैं। इसमें कैनोनिकल सब्स्टीट्यूशन पर चलना, आंतरिक वेरिएबल्स को कॉलर के नेमस्पेस में बदलना और परिणामों को कॉलर के आर्गुमेंट्स के साथ यूनिफाई करना शामिल है।
दक्षता: यह दृष्टिकोण सुनिश्चित करता है कि डीडुप्लीकेशन कार्य एक ही (run ...) क्वेरी के लिए केवल एक बार किया जाए, चाहे रिलेशन कितनी भी बार रिकर्सिवली कॉल किया जाए।

3. `defrel/bank-w` वेरिएंट (बेस्ट-फर्स्ट)

मानक defrel/bank डेप्थ-फर्स्ट रिकर्सन का उपयोग करता है, जो एन्यूमरेशन ऑर्डर के प्रति पक्षपाती होता है (उदाहरण के लिए, एडिशन के ऊपर मल्टीप्लिकेशन के राइट-स्पाइन चेन्स को प्राथमिकता देना)। उन मामलों को संबोधित करने के लिए जहाँ लक्ष्य समाधान कैनोनिकल ऑर्डर में गहरा स्थित है, लेखक defrel/bank-w पेश करते हैं।

वेटेड स्ट्रीम्स (Weighted Streams): यह वेरिएंट इमच्योर (immature) स्ट्रीम सेल्स को एडमिसेबल अपर बाउंड्स (वेट्स) से जोड़ता है।
डेप्थ-डिके (Depth-Decay): रिकर्सिव कॉल साइट्स पर वेट्स पर एक डिके फैक्टर लागू किया जाता है। यह सुनिश्चित करता है कि उथले (shallower) प्रतिनिधियों का भार कम हो और उन्हें mplus-w द्वारा सॉर्टेड मर्ज लॉजिक द्वारा पहले उत्सर्जित किया जाए।
लेजी ह्यूरिस्टिक्स (Lazy Heuristics): सिस्टम एक "लेजी-सीलिंग" अनुशासन का उपयोग करता है जहाँ अंडरलाइंग थंक (thunk) को फोर्स किए बिना वेट्स को पीक किया जाता है, जो अंडरलाइंग थंक को मजबूर किए बिना वेट्स को पीक करता है, जो यह सुनिश्चित करता है कि अनंत लूप से बचा जा सके। यह एक A*-स्टाइल सर्च को लागू करता है जहाँ वेट सीलिंग एक एडमिसेबल ह्यूरिस्टिक के रूप में कार्य करती है।

मुख्य योगदान

prune: एक जेनेरिक आंसर-स्ट्रीम डीडुप्लीकेशन कॉम्बिनेटर जो यूजर-सप्लाइड फंक्शन्स द्वारा की (key) किया जाता है, जिसे प्रून कीज़ में उठाने के लिए हेल्पर्स (ground-key, when-ground) द्वारा समर्थित किया जाता है।
defrel/memo और defrel/bank: कैनोनिकल फ्रेश वेरिएबल्स के विरुद्ध रिलेशन मेमोइज़ेशन के लिए कॉम्बिनेटर्स। defrel/bank विशेष रूप से साझा डीडुप्लीकेशन के साथ बॉटम-अप एन्यूमरेशन प्रदान करता है, जो प्रभावी रूप से रिलेशनल सेटिंग में मानक PBE "वर्कलिस्ट" पैटर्न को ट्रांसप्लांट करता है।
defrel/bank-w: एक डेप्थ-डिेकेड बेस्ट-फर्स्ट वेरिएंट जो इमच्योर स्ट्रीम्स पर वेट्स का उपयोग करके बेस्ट-फर्स्ट एन्यूमरेशन को रिकवर करता है, जिससे सिस्टम को कैनोनिकल ऑर्डर में मौजूद होने के बावजूद कॉम्पैक्ट रिप्रेजेंटेटिव्स खोजने की अनुमति मिलती है।
इम्प्लीमेंटेशन ट्रिक्स: पेपर इंजीनियरिंग ऑप्टिमाइजेशन का विवरण देता है, जैसे कि सॉर्टेड मर्ज के लिए पेयरिंग हीप्स का उपयोग करना और "थंक-कोलैप्स" तकनीकें, यह सुनिश्चित करने के लिए कि मेमोइज़्ड अप्रोच डेप्थ-बाउंडेड बेसलाइन्स के साथ प्रतिस्पर्धी प्रदर्शन करे।

परिणाम

लेखक अंकगणितीय (arithmetic) और स्ट्रिंग PBE बेंचमार्क्स (डेप्थ 0–6) पर एक प्रारंभिक अनुभवजन्य मूल्यांकन प्रस्तुत करते हैं।

प्रदर्शन लाभ: 8 गहरे अंकगणितीय लक्ष्यों में से 6 पर, defrel/bank, डेप्थ-बाउंडेड बेसलाइन (bounded) की तुलना में 9–99× तेज़ है। ऐसा इसलिए है क्योंकि bank हर रिकर्सिव लेवल पर सब-एक्सप्रेशन को फिर से प्रून करने से बचता है।
एन्यूमरेशन ऑर्डर बायस: defrel/bank का प्रदर्शन उसके एन्यूमरेशन ऑर्डर पर अत्यधिक निर्भर है। यह तब उत्कृष्ट होता है जब लक्ष्य समाधान कैनोनिकल डेप्थ-फर्स्ट ऑर्डर में जल्दी आता है (जैसे $x^k$ या $x^k + c$ )। हालाँकि, यह $(1+x)^k$ जैसे लक्ष्यों के लिए संघर्ष करता है या टाइमआउट हो जाता है, जो कैनोनिकल स्ट्रीम में बहुत देर से आते हैं (जैसे डेप्थ 4 के लिए स्थिति 243,158)।
बेस्ट-फर्स्ट ट्रेड-ऑफ्स: defrel/bank-w $(1+x)^k$ जैसे लक्ष्यों के लिए जल्दी कॉम्पैक्ट रिप्रेजेंटेटिव्स खोजने में सफल होता है। हालाँकि, यह एक "ब्रैडथ-फर्स्ट कॉस्ट" लाता है: एक डेप्थ- $K$ सेल उत्सर्जित करने के लिए डेप्थ $<K$ के सभी सेल्स को उत्सर्जित करना आवश्यक है। वाइड बिहेवियर स्पेस (डेप्थ 3 पर हजारों विशिष्ट व्यवहार) में, यह उन गहरे अंकगणितीय लक्ष्यों पर टाइमआउट की ओर ले जाता है जहाँ defrel/bank सफल होता है।
होस्ट बेसलाइन के साथ तुलना: एक नॉन-रिलेशनल होस्ट-लैंग्वेज बेसलाइन (host-bank) उथले लक्ष्यों और $(1+x)^k$ परिवारों पर अच्छा प्रदर्शन करता है, लेकिन रिलेशनल इंजन के बाहर बैंक बनाने की लागत के कारण गहरे राइट-स्पाइन लक्ष्यों पर बुरी तरह विफल हो जाता है। defrel/bank रिलेशनल इंटरफेस को बनाए रखता है और वहां अधिकांश host-bank के स्पीडअप को रिकवर करता है जहाँ एन्यूमरेशन बायस अनुकूल होता है।

महत्व और दावे

पेपर दावा करता है कि ये कॉम्बिनेटर्स सफलतापूर्वक बॉटम-अप एन्यूमरेशन के साथ ऑब्जर्वेशनल डीडुप्लीकेशन को रिलेशनल सेटिंग में लाते हैं बिना रिलेशनल पैराडाइम छोड़े या होस्ट सर्च डिसिप्लिन को बदले।

ऑप्ट-इन सिमेंटिक्स: यह दृष्टिकोण पूरी तरह से ऑप्ट-इन है। यह मानक miniKanren रिलेशन की सेमेंटिक्स को नहीं बदलता है; डीडुप्लीकेशन केवल उन रिलेशन पर लागू होता है जिन्हें prune के माध्यम से या defrel/bank के माध्यम से स्पष्ट रूप से रैप किया गया है।
पूर्णता (Completeness): लेखक तर्क देते हैं कि प्रूनिंग उपयोगकर्ता-प्रदान की गई इक्विवेलेंस के संबंध में पूर्णता बनाए रखती है। प्रत्येक व्यवहार के लिए, कम से कम एक प्रतिनिधि पाया जाता है।
सीमाएँ: वे अपने दायरे के बारे में विनम्र हैं, यह नोट करते हुए कि मूल्यांकन प्रारंभिक है, दो डोमेन (अंकगणित और स्ट्रिंग) तक सीमित है, और एक विशिष्ट व्याकरण पर निर्भर है। वे स्वीकार करते हैं कि defrel/bank एक सार्वभौमिक समाधान नहीं है; इसकी सफलता लक्ष्य के आकार और एन्यूमरेशन ऑर्डर के बीच परस्पर क्रिया पर निर्भर करती है। वे स्पष्ट रूप से कहते हैं कि फेयर कंजंक्शन defrel/bank के एन्यूमरेशन बायस को हल नहीं कर सकता क्योंकि बायस इस बात में है कि बैंक में कौन से सेल्स मौजूद हैं, न कि इस बात में कि उन्हें कैसे इंटरलीव किया गया है।
भविष्य का कार्य: पेपर भविष्य के कार्य के लिए कई दिशाओं की पहचान करता है, जिसमें ब्रैडथ-फर्स्ट कॉस्ट के बिना $(1+x)^k$ बायस को ठीक करने के लिए कैनोनिकल बॉडी पर इटरेटिव डीपनिंग, सैचुरेशन डिटेक्शन, और समृद्ध कंस्ट्रेंट स्टोर्स और अन्य PBE डोमेन (जैसे बिट-वेक्टर्स, लिस्ट्स) तक विस्तार करना शामिल है।

संक्षेप में, पेपर प्रदर्शित करता है कि कैनोनिकल वेरिएबल्स के विरुद्ध रिलेशन को मेमोइज़ करके और ऑब्जर्वेशनल इक्विवेलेंस द्वारा प्रून करके, एक रिलेशनल PBE सिंथेसिस में महत्वपूर्ण प्रदर्शन लाभ प्राप्त किया जा सकता है, बशर्ते कि एन्यूमरेशन ऑर्डर लक्ष्य की संरचना के साथ संरेखित हो।