تخيل أنك محقق يحاول حل لغز، ولكن بدلاً من البحث عن الأدلة في زقاق مظلم، أنت تبحث داخل برنامج كمبيوتر. تحديداً، أنت تبحث في البرامج التي تتخذ خيارات عشوائية، مثل رمي قطعة نقد لتحديد المسار الذي ستسلكه. في عالم علوم الحاسوب، يسمى هذا "برنامجاً احتمالياً". هذه البرامج تشبه حجر النرد السحري؛ فهي لا تفعل شيئاً واحداً فقط، بل تفعل أشياء كثيرة باحتمالات مختلفة للحدوث. ولأنها عشوائية، لا يمكننا ببساطة أن نسأل، "هل نجحت؟" بل يجب أن نسأل، "ما مدى جودة أدائها في المتوسط؟" و"كم من الطاقة أو الوقت أهدرت أثناء المحاولة؟"

لفترة طويلة، كان فحص هذه البرامج العشوائية يشبه محاولة الإمساك بسمكة زلقة بيديك العاريتين. يمكنك رؤية السمكة (الكود)، وتعرف الرياضيات (نظرية الاحتمالات)، ولكن إثبات مقدار "التكلفة" (مثل الوقت أو البطارية) التي ستستهلكها بدقة هو أمر صعب للغاية. عادةً، عليك كتابة قصتين منفصلتين: واحدة عن ما يفعله البرنامج، وأخرى عن دليل طويل وممل حول تكلفته. ثم يتعين عليك دمج القصتين يدوياً، سطراً بسطر، للتأكد من تطابقهما. إنها عملية مرهقة، وعرضة للخطأ البشري، وغالباً ما تمنع الناس من التحقق مما إذا كانت خوارزمياتهم العشوائية آمنة وفعالة حقاً.

هنا يأتي دور فريق من الباحثين من النمسا وألمانيا مع أداة جديدة. لقد بنوا "موناداً (Monad) مدركاً للتكلفة" خاصاً للغة برمجة تسمى Liquid Haskell. فكر في "الموناد" كحقيبة ظهر سحرية يحملها البرنامج. عادةً، تحمل حقيبة الظهر هذه نتيجة اختيار عشوائي فقط. لكن حقيبة الظهر التي ابتكرها الباحثون خاصة: فهي تحتوي على آلة حاسبة ونظام تحديد مواقع (GPS) مدمجين. في كل مرة يتخذ فيها البرنامج خطوة، تقوم حقيبة الظهر تلقائياً بتحديث التكلفة الإجمالية واحتمالية حدوث هذه الخطوة. هي لا تحمل البيانات فحسب؛ بل "تعرف" الرياضيات. باستخدام حقيبة الظهر الذكية هذه، أظهر الباحثون أن أجهزة الكمبيوتر يمكنها تلقائياً فحص تكلفة البرامج العشوائية، محولةً لغزاً يدوياً صعباً إلى عملية شبه تلقائية. لقد اختبروا ذلك على مشكلات كلاسيكية مثل فرز القوائم وإدارة البيانات، مثبتين أن طريقتهم الجديدة ليست دقيقة فحسب، بل هي أيضاً أسرع وأسهل بكثير في الاستخدام من الطرق السابقة.

الحقيبة السحرية للبرامج العشوائية

تخيل أنك تلعب لعبة فيديو حيث يتعين على شخصيتك القفز فوق العقبات. أحياناً تكون اللعبة سهلة، وأحياناً تكون صعبة، اعتماداً على كيفية رمي الكمبيوتر لنرد افتراضي. في علوم الحاسوب، نسمي هذه "الخوارزميات الاحتمالية". إنها مفيدة جداً لأنها يمكن أن تكون أسرع وأذكى من التعليمات الجامدة خطوة بخطوة. ولكن هناك عقبة: نظرًا لاعتمادها على الصدفة، فمن الصعب التنبؤ بالضبط بمقدار "الوقود" (الوقت، المال، أو قوة الحوسبة) الذي ستستهلكه.

لسنوات، واجه علماء الحاسوب مشكلة. لإثبات أن برنامجاً عشوائياً فعال، كان عليهم القيام بشيئين منفصلين: أولاً، إثبات أن البرنامج يعمل بشكل صحيح، وثانياً، كتابة دليل جديد تماماً لحساب التكلفة المتوسطة. كان الأمر يشبه خبز كعكة ثم الاضطرار لكتابة مقال منفصل لإثبات أنك استخدمت الكمية الصحيحة من السكر، رغم أن الوصفة موجودة أمامك مباشرة. هذا جعل العملية بطيئة وعرضة للأخطاء.

قرر مؤلفو هذه الورقة، ماتياس هيتزنبرغر، وجورج موزر، وفلوريان زوليجر، إصلاح ذلك عبر إنشاء نوع جديد من "الحقائب" للبرامج. في عالم البرمجة، "الموناد" هو طريقة لتغليف عملية حسابية لتسهيل التعامل معها. صمم الفريق "موناد احتمالي مدرك للتكلفة". يمكنك التفكير في هذا كحقيبة ظهر سحرية لا تحمل فقط نتيجة رمية عملة عشوائية، بل تحمل أيضاً حصيلة جارية للتكلفة والاحتمالية.

إليك كيف يعمل ذلك بتبسيط:

1. الحقيبة تعرف الرياضيات: عندما يرمي البرنامج عملة (اختيار عشوائي)، تقوم حقيبة الظهر تلقائياً بحساب متوسط تكلفة تلك الرمية. لا يحتاج الإنسان لكتابة الرياضيات؛ الحقيبة تفعل ذلك نيابة عنك.
2. تتبع كل شيء: بينما يعمل البرنامج، تحتفظ حقيبة الظهر بسجل. إذا اتخذ البرنامج خطوة تكلف وحدة زمنية واحدة، تضيف الحقيبة 1 إلى الإجمالي. إذا انقسم البرنامج إلى مسارين، تحسب الحقيبة متوسط تكلفة كلا المسارين معاً.
3. تتحدث مع الكمبيوتر: استخدم الباحثون أداقة تسمى Liquid Haskell، وهي تشبه روبوتاً فائق الذكاء يتحقق من الأخطاء في الكود الخاص بك. من خلال وضع "حقيبة الظهر المدركة للتكلفة" داخل Liquid Haskell، سمحوا للروبوت بالتحقق من الرياضيات تلقائياً. يمكن للروبوت النظر إلى الكود والقول: "نعم، خوارزمية الفرز العشوائي هذه ستستغرق حوالي 2(n+1) مضروبة في العدد التوافقي ناقص 4n خطوة في المتوسط"، دون أن يضطر الإنسان لكتابة الإثبات بنفسه.

اختبار الحقيبة: من "الهيبس" إلى "التوظيف"

لرؤية ما إذا كانت حقيبة الظهر الجديدة تعمل حقاً، جرب الفريق استخدامها في عدة مشكلات شهيرة في علوم الحاسوب. أرادوا معرف أن ما إذا كان بإمكان الروبوت حل الألغاز الرياضية تلقائياً أم أنه سيظل بحاجة للمساعدة.

1. الهيبس القابلة للدمج (الفوز السهل)
أولاً، نظروا في بنية بيانات تسمى "الميلدابل هيب" (Meldable Heap). تخيل مجموعتين من أوراق اللعب تريد دمجهما في مجموعة واحدة كبيرة. يقوم البرنامج بذلك عن طريق رمي عملة لتحديد مكان ذهاب كل ورقة. وجد الباحثون أن حقيبة الظهر جعلت هذا الأمر تلقائياً بالكامل تقريباً. تحقق الروبوت من الكود وأكد فوراً أن التكلفة ستكون لوغاريتمية (مما يعني أنها تنمو ببطء شديد حتى مع كبر حجم المجموعة). المساعدة الوحيدة التي قدمها الإنسان كانت تلميحاً بسيطاً حول كيفية عمل اللوغاريتمات. أظهر هذا أنه بالنسبة لبعض المشكلات، فإن الطريقة الجديدة مثالية تقرياً ولا تتطلب أي عمل يدوي تقريباً.

2. الكويك سورت العشوائي (اللغز الأصعب)
بعد ذلك، واجهوا "الراندومايزد كويك سورت" (Randomised Quicksort)، وهي طريقة شهيرة لفرز القوائم. هذا الجزء أكثر تعقيداً. يختار البرنامج رقماً عشوائياً لتقسيم القائمة، ثم يرتب الأجزاء الصغيرة والكبيرة. الرياضيات هنا أكثر تعقيداً، وتتضمن مجموعات وأنماطاً يصعب تخمينها.
استطاع الروبوت التعامل مع الأجزاء الأساسية، ولكن للحصول على الإجابة النهائية (صيغة محددة تتضمن الأعداد التوافقية)، كان على الإنسان التدخل وتوجيه الروبوت عبر بعض الخطوات الرياضية الأكثر صعوبة. كان الأمر يشبه قدرة الروبوت على الجري في السباق، لكنه احتاج إلى مدرب ليشرح له استراتيجية اللفة الأخيرة. ومع ذلك، حتى مع هذه المساعدة الإضافية، وجد الفريق أن طريقتهم أقصر وأنظف بكثير من الطرق الأخرى لإثبات الشيء نفسه.

3. أشجار سبلاي ومشكلة التوظيف (المنطقة الوسطى)
اختبروا أيضاً "أشجار سبلاي العشوائية" (Randomised Splay Trees) - وهي طريقة لتنظيم البيانات التي تنقل العناصر المستخدمة بكثرة إلى الأعلى - و"مشكلة التوظيف" (Hiring Problem) - وهي سيناريو تقوم فيه بمقابلة مرشحين وتوظيف الأفضل بينهم حتى الآن.

• بالنسبة لـ أشجار سبلاي، ساعدت حقيبة الظهر في تتبع "الجهد" (كلمة منمقة لكيفية العمل المتبقي) وتكلفة الدورات. تطلب الأمر بعض التلميحات البشرية حول اللوغاريتمات، لكن الروبوت قام بالعمل الشاق.
• بالنسبة لـ مشكلة التوظيف، استخدموا حقيبة الظهر لإثبات أنه إذا قمت بمقابلة المرشحين بترتيب عشوائي، فإن متوسط عدد المرات التي توظف فيها شخصاً ما يتبع نمطاً معيناً. نجح الروبوت في إثبات ذلك عن طريق تقسيم المشكلة إلى مجموعات أصغر، مما أظهر أن الطريقة تعمل جيداً مع أنواع مختلفة من الخوارزميات العشوائية.

ماذا يعني هذا للمستقبل؟

الخلاصة الكبرى من هذه الورقة هي أننا لم نعد مضطرين للاختيار بين "التلقائية" و"الدقة". قبل هذا، إذا كنت تريد من الكمبيوتر فحص تكلفة برنامج عشوائي، كان عليك غالباً القيام بالكثير من العمل اليدوي. وإذا أردت أن يكون الأمر تلقائياً بالكامل، فغالباً ما كان عليك تبسيط المشكلة لدرجة تجعل الإجابة غير مفيدة.

أظهر المؤلفون أنه من خلال بناء تتبع التكلفة مباشرة داخل هيكل البرنامج (حقيبة الظهر)، يمكنك الحصول على أفضل ما في العالمين. يمكن للكمبيوتر القيام بمعظم العمل تلقائياً، ولكن عندما تصبح الرياضيات صعبة حقاً، يمكن للإنسان التدخل لتوجيه الروبوت دون الحاجة إلى إعادة كتابة الإثبات بالكامل من البداية.

لقد أثبتوا أيضاً أن طريقتهم "سليمة" (Sound)، وهي طريقة منمقة لقول "إنها صحيحة رياضياً". هم لم يتكهنوا فحسب؛ بل أظهروا أنه إذا قال الروبوت إن التكلفة هي (X)، فإن التكلفة هي بالفعل (X).

ومع ذلك، هناك بعض الحدود. تشير الورقة إلى أن حقيبة الظهر الخاصة بهم تعمل حالياً فقط مع البرامج التي تنتهي في وقت محدد مع عدد محدود من النتائج. لا يمكنها بعد التعامل مع البرامج التي قد تعمل للأبد أو التي لديها عدد لا نهائي من الاحتمالات. ولكن بالنسبة للغالبية العظمى من الخوارمايات العشوائية المفيدة التي نستخدمها اليوم، فإن هذه الأداة تمثل تغييراً جذرياً. إنها تحول مهمة مملة وعرضة للخطأ إلى عملية سلسة وشبه تلقائية، مما يجعل من السهل بناء برمجيات أسرع، وأرخص، وأكثر موثوقية.

باختصار، صنع الباحثون حقيبة ظهر أذكى لمستكشفينا الرقميين. الآن، عندما تنطلق برامجنا في مغامراتها العشوائية، فهي تحمل خريطتها وآلتها الحاسبة الخاصة، مما يضمن لنا معرفة التكلفة الدقيقة للوصول إلى الكنز.