Towards Bottom-Up Enumeration in miniKanren via Pruning and Memoization
تقدم هذه الورقة اثنين من أدوات الربط لمكتبة miniKanren، وهما `prune` و `defrel/bank` اللذان يتيحان التعداد من الأسفل إلى الأعلى مع إزالة التكرار الملاحظي والتخزين المؤقت لتحسين أداء التركيب البرمجي العلائقي على الأهداف العميقة بشكل كبير، مع اقتراح متغير مرجح لمعالجة الحالات التي يفشل فيها الترتيب المعياري للبحث بالعمق أولاً في إيجاد ممثلين مدمجين.
البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل
تخيل أنك محقق تحاول حل لغز، ولكن بدلاً من البحث عن أدلة، أنت تحاول بناء آلة يمكنها القيام بمهمة محددة، مثل تحويل الرقم 2 إلى 4، و3 إلى 9، و4 إلى 16. أنت لا تعرف الصيغة الدقيقة التي تستخدمها الآلة؛ كل ما تعرفه هو النتائج. يُسمى هذا "البرمجة من خلال الأمثلة". لإيجاد الإجابة، يمكنك محاولة بناء كل الآلات الممكنة، واحدة تلو الأخرى، بدءاً من أبسط التروس والرافعات، واختبار كل منها لمعرفة ما إذا كانت ستعمل. هذا يشبه تماماً طباخاً يحاول العثور على وصفة سرية عبر خبز كل التشكيلات الممكنة من الدقيق والسكر والبيض حتى يجد واحدة ذات مذاق صحيح.
في عالم علوم الحاسوب، هناك طريقة خاصة للتفكير تسمى "البرمجة العلاقاتية". بدلاً من إخبار الحاسوب بالضبط كيف يجد الإجابة خطوة بخوة، أنت تصف شكل الإجابة، وتترك للحاسوب مهمة اكتشاف المسار. الأمر يشبه إخبار روبوت: "ابحث لي عن مسار عبر المتاهة"، بدلاً من قوله: "استدر يساراً، ثم امشِ ثلاث خطوات، ثم استدر يميناً". الحاسوب بارع في استكشاف العديد من المسارات في وقت واحد، لكن لديه عادة صعبة: فإنه يميل إلى استكشاف نفس النهايات المسدودة مراراً وتكراراً، أو يعلق في نفق طويل ومتعرج بينما يفوت اختصاراً ذكياً قصيراً بجانبه مباشرة. تتناول هذه الورقة هذه المشكلة من خلال تعليم الحاسوب كيف يكون مستكشفاً أكثر ذكاءً وتنظيماً.
المشكلة: الضياع في المتاهة
تخيل أنك تحاول العثور على مفتاح محدد في علية ضخمة وفوضوية مليئة بالملايين من المفاتيح. معظم هذه المفاتيح تبدو مختلفة، لكنها جميعاً تفتح الباب نفسه تماماً. إذا كنت مستكشفاً أخرق، فقد تلتقط مفتاحاً، تجربه، تدرك أنه يعمل، ثم تقضي ساعات في التقاط مفاتيح أخرى تبدو مختلفة ولكنها تعمل أيضاً، فقط لتتأكد. أنت تضيع الوقت في فحص مفاتيح تقوم بنفس الوظيفة تماماً.
في عالم البرامج الحاسوبية، يحدث هذا طوال الوقت. عندما يحاول الحاسوب بناء برنامج لتحويل المدخلات إلى مخرجات، فإنه يولد آلاف من مقتطفات الكود التي تبدو مختلفة. الكثير من هذه المقتطفات هي "توائم" متنكرة—فهي تفعل الشيء نفسه تماماً رغم اختلاف شكلها من الداخل. طريقة البحث القياسية للحاسوب، والتي تعمل مثل مستكشف يغوص في الأعماق، ستفحص توأماً، ثم التالي، ثم التالي، مما يجعلها تتباطأ أكثر فأكثر مع كبر حجم العلية. الأمر يشبه محاولة العثور على إبرة في كومة قش، لكن كومة القش مكونة من ملايين الإبر التي تبدو جميعها مختلفة قليلاً.
الحل: أداة "التقليم" وأداة "البنك"
ابتكر مؤلفو هذه الورقة، نيكولاي كوداسوف، أداتين ذكيتين لإصلاح هذه الفوضى. فكر فيهما كمرشح سحري ومكتبة ذكية.
1. أداة "التقليم" (المرشح)
تخيل أن لديك حزام ناقل للمفاتيح تخرج من آلة. أداة "التقليم" هي حارس يقف بجانب الحزام. مع وصول كل مفتاح، يتحقق الحارس مما يفتحه هذا المفتاح. إذا كان الحارس قد رأى بالفعل مفتاحاً يفتح نفس الباب، فإنه ببساطة يلقي بالمفتاح الجديد في السلة دون حتى اختباره. هو يحتفظ فقط بأول مفتاح يفتح باباً معيناً. بهذه الطريقة، يحمل الحزام الناقل مفاتيح فريدة ومفيدة فقط. يتوقف الحاسوب عن إضاعة الوقت في الفحص المكرر.
2. أداة "البنك" (المكتبة الذكية)
الآن، تخيل أنك بدلاً من بناء المفاتيح من الصفر في كل مرة تحتاج فيها إلى واحد، لديك مكتبة سحرية. عندما تطلب من المكتبة مفتاحاً، فهي لا تعطيك واحداً فحسب؛ بل تبني رفاً كاملاً من المفاتيح الفريدة مرة واحدة، من الأسفل إلى الأعلى، وتحفظها. إذا طلبت مفتاحاً مرة أخرى لاحقاً، فإن المكتبة تمنحك المفتاح الذي بنته بالفعل.
في لغة الورقة، يسمى هذا defrel/bank. إنه يجبر الحاسوب على بناء قائمة البرامج المرشحة بطريقة محددة ومنظمة (بدءاً من الأبسط)، ويحفظ النتائج. إذا احتاج الحاسوب لاستخدام جزء صغير من برنامج لاحقاً، فإنه لا يعيد بناءه؛ بل يأخذ الجزء من "البنك". هذا يوفر وقتاً هائلاً لأن الحاسوب لا يضطر للقيام بنفس العمل مرتين.
التحول: أحياناً "السرعة" ليست هي "الأفضل"
أدرك المؤلفون أيضاً أن مجرد كونك منظماً ليس كافياً دائماً. أحياناً، يبني "البنك" أرففته بترتيب يكون سريعاً للحاسوب ولكنه بطيء للإنسان. على سبيل المثال، قد يبني البنك جميع آلات "الضرب" أولاً، ولا يبني آلات "الجمع" إلا في وقت متأخر جداً. إذا كانت الإجابة التي تبحث عنها هي آلة "جمع"، فقد يضطر الحاسوب لفحص آلاف آلات الضرب قبل أن يجد الآلة التي تحتاجها أخيراً.
لحل هذه المشكلة، أنشأوا أداة ثالثة تسمى defrel/bank-w (البنك الموزون). هذه الأداة تشبه أميناً للمكتبة يعرف أن بعض أنواع المفاتيح هي الأكثر احتمالاً لتكون هي الإجابة. هي تستخدم "درجة" خاصة لتقرر أي المفاتيح تظهر لك أولاً. هي تحاول إظهار المفاتيح الأبسط والأكثر إيجازاً لك أولاً، حتى لو كانت مدفونة عميقاً في المكتبة. هذا رائع إذا كنت تريد الحل الأكثر أناقة، ولكنه قد يكون أبطأ إذا كانت الإجابة في الواقع آلة معقدة وعميقة.
ما وجدوه: السرعة مقابل الاستراتيجية
اختبر المؤلفون هذه الأدوات على مجموعة من الألغاز الرياضية والنصية (مثل تحويل "Hello" إلى "Hello, World!"). إليكم ما اكتشفوه:
- "البنك" هو وحش سرعة: في 6 من أصل 8 مسائل رياضية صعبة، كانت أداة
defrel/bankأسرع بمقدار 9 إلى 99 مرة من طريقة البحث القياسية القديمة. كانت سريعة جداً لدرجة أنها حلت مسائل في جزء من الثانية بينما كانت الطريقة القديمة تستغرق دقائق لإنهائها. - لكنه يمتلك نقطة ضعف: البنك منظم جداً لدرجة أنه قد يخطئ في العثور على الإجابة إذا كانت الإجابة مخبأة في جزء من المكتبة يزوره في وقت متأخر. على سبيل المثال، إذا كانت الإجابة تتضمن جمع الأرقام بطريقة معينة (مثل )، فقد يعلق البنك في فحص آلاف أمثلة الضرب أولاً. في هذه الحالات، الطريقة القديمة الأبطأ هي التي تفوز لأنها تفحص الأشياء بترتيب مختلف.
- "البنك الموزون" هو عملية مقايضة: أداة
defrel/bank-wممتازة في العثور على الإجابات الأكثر إيجازاً وأناقة. لقد وجدت الإجابة الصحيحة للغز نصي معقد في 10.4 مللي ثانية، متفوقة على الطريقة القياسية التي استغرقت 31.5 مللي ثانية. ومع ذلك، بالنسبة للمسائل الرياضية العميقة جداً، فقد تتعثر في محاولة فحص الكثير من الاحتمالات وتتوقف عن العمل (timeout).
الخلاصة
لا تدعي هذه الورقة أنها حلت كل مشكلة في علوم الحاسوب. بدلاً من ذلك، هي توضح أنه من خلال إضافة القليل من "التقليم" (تصفية المكررات) و"التبنك" (حفظ العمل لوقت لاحق)، يمكننا جعل البرامج الحاسوبية التي تبني برامج أخرى أسرع بكثير.
يقترح المؤلفون أنه إذا كنت تبني نظاماً لحل الألغاز، فيجب عليك استخدام أداة البنك (Bank) كخيار افتراضي لأنها عادة ما تكون الأسرع. ومع ذلك، إذا كنت تبحث عن حل محدد وموجز للغاية، أو إذا كانت المشكلة سطحية وبسيطة، فقد ترغب في استخدام البنك الموزون (Weighted Bank) أو حتى الطريقة القديمة. الأمر لا يتعلق بكون أداة واحدة مثالية، بل بامتلاك الأداة المناسبة لشكل اللغز الذي تحاول حله. تنتهي الورقة باقتراح أن العمل المستقبلي سيختبر هذه الأدوات على ألغاز أكثر تعقيداً، مثل بناء برامج تفهم القوائم أو البيانات المحددة النوع، لمعرفة ما إذا كان هذا التسريع سيصمد في العالم الحقيقي.
غارق في أبحاث مجالك؟
تصلك نشرة يومية بأحدث الأبحاث المطابقة لكلماتك البحثية المفتاحية — مع ملخصات تقنية، بلغتك.