🔢 mathematics

Bidirectional Interpolation for the Lambda-Calculus -- Revisiting and Formalising Craig-Čubrić Interpolation

تقدم هذه الورقة برهاناً جديداً لمبرهنة تشوبريتش (Čubrić) الخاصة بالاستكمال ذي الصلة بالبرهان (proof-relevant interpolation theorem) لحساب لامدا بسيط النوع (simply-typed lambda-calculus) باستخدام مبادئ النوع ثنائي الاتجاه (bidirectional typing principles)، وتوفر صياغتها الرسمية في مساعد الإثبات روك (Rocq).

المؤلفون الأصليون: Meven Lennon Bertrand, Alexis Saurin

نُشر 2026-03-04

📖 4 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Meven Lennon Bertrand, Alexis Saurin

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

إليك شرح لورقة بحثية بعنوان "الاستكمال ثنائي الاتجاه لحساب لامدا" (Bidirectional Interpolation for the Lambda-Calculus)، مترجمة إلى لغة يومية باستخدام تشبيهات إبداعية.

الصورة الكبيرة: مشكلة "المترجم"

تخيل أن لديك شخصين، أليس وبوب، يحتاجان للتواصل.

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

مبرهنة كرايج للاستكمال (الفكرة القديمة) تقول: "لا تقلقا! هناك مترجم (المستكمل - Interpolant) لا يتحدث إلا الكلمات التي يعرفها كل من أليس وبوب معاً (مثل 'شيء' أو 'كائن'). يمكن لأليس شرح رسالتها للمترجم، والمترجم يمكنه شرحها لبوب."

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

المشكلة في الطريقة القديمة

كانت الطريقة السابقة لإيجاد هذا المترجم (التي طورها عالم رياضيات يدعى تشوبريتش) تشبه محاولة حل متاهة عن طريق التخمين.

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

الحل الجديد: "النمذجة ثنائية الاتجاه" (Bidirectional Typing)

وجد المؤلفون طريقة جديدة لبناء المترجم باستخدام مفهوم يسمى النمذجة ثنائية الاتجاه.

التشبيه: خط التجميع مقابل محطة التفتيش
تخيل مصنعاً يصنع الألعاب.

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

في علوم الحاسوب (تحديداً في حساب لامدا، وهو الرياضيات التي تقوم عليها لغات البرمجة)، تعني "النمذجة ثنائية الاتجاه" التبديل بين هذين الوضعين اعتماداً على ما تفعله.

عندما تقوم ببناء هيكل معقد (مثل دالة)، فإنك تتحقق منه مقابل مخطط معروف.
عندما تقوم باستخدام هيكل (مثل تطبيق دالة على وسيط)، فإنك تستنتج ما يفعله.

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

مشكلة "المجموع" (الجزء الصعب)

تتعامل الورقة مع نوع محدد من الرياضيات يسمى STLC+ (حساب لامدا بسيط النوع مع المجموع/Sums).

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

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

الجزء "الرسمي": المحامي الآلي

لم يكتفِ المؤلفون بكتابة هذا على الورق؛ بل بنوا محامياً آلياً (باستخدام أداة تسمى Rocq، وهي مساعد برهان).

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

لقلق أثبتوا أيضاً أن طريقتهم تعمل من أجل التطبيع (Normalization).

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

لماذا يجب أن تهتم؟

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

ملخص في جملة واحدة

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

إليك ملخص تقني مفصل لورقة البحث "الاستيفاء ثنائي الاتجاه في حساب لامدا: إعادة النظر في وتأطير استيفاء كرايج-تشوبريتش" (Bidirectional Interpolation for the Lambda-Calculus: Revisiting and Formalising Craig-Čubrić Interpolation) بقلم ميفين لينون-بيرتراند وألكسيس سورين.

1. بيان المشكلة

تتناول الورقة مشكلة الاستيفاء ذي الصلة بالبرهان (Proof-Relevant Interpolation) في حساب لامدا بسيط النوع مع المجموعات والأنواع الفارغة (STLC+).

الخلفية: ينص مبرهنة كرايج للاستيفاء على أنه إذا كان $A \vdash B$ ، فإنه يوجد مستوفٍ (interpolant) $I$ يستخدم فقط المفردات المشتركة بين $A$ و $B$ بحيث يكون $A \vdash I$ و $I \vdash B$ .
الصلة بالبرهان: النسخة الأقوى تتطلب أن يمكن تحليل البراهين (الحدود/terms) التي تشكل الاستلزام من خلال المستوفي. وتحديداً، إذا كان $x:A \vdash t:B$ ، فيجب أن يوجد نوع $C$ (المستوفي) وحدود $u: A \to C$ و $v: C \to B$ بحيث يؤدي التركيب $(\lambda y. v) u$ إلى الحد الأصلي $t$ .
الفجوة: بينما أثبت تشوبريتش هذه النتيجة لـ STLC+، فإن برهانه الأصلي كان:
1. معقداً: اعتمد على استقراء قائم على الحجم للحدود، حيث يتم استبدال الحدود الفرعية بمتغيرات، مما أخفى البنية الأساسية.
2. معيباً: احتوى على حالة محددة (الحالة الفرعية 6.3.2) تم تجاهلها باعتبارها "مشابهة" لحالة سابقة، بينما كانت في الواقع متميزة وتتطلب معالجة مختلفة.
3. غير مؤطر: جعل التعقيد من الصعب التحقق من البرهان آلياً.
التحدي: في STLC+، لا تحقق الأشكال الطبيعية $\beta$ ( $\beta$ -normal forms) القياسية خاصية الصيغة الجزئية (subformula property) (وهي متطلب رئيسي للاستيفاء) عند وجود المجموعات والأنواع الفارغة. يجب إجراء التطبيع بالنسبة لـ التحويلات التبادلية (commuting conversions) (دفع عمليات الإزالة عبر عمليات إزالة أخرى) لاستعادة فئة من الأشكال الطبيعية ذات الخصائص البنيوية اللازمة.

2. المنهجية

يقترح المؤلفون استراتيجية برهنة جديدة تستفيد من النوعية ثنائية الاتجاه (Bidirectional Typing) لتوصيف الأشكال الطبيعية، مستبدلين بذلك الاستقراء القائم على الحجم في البرهان الأصلي.

أ. التوصيف ثنائي الاتجاه للأشكال الطبيعية

يعرف المؤلفون نظام نوع ثنائي الاتجاه (يقسم الأحكام إلى استنتاج $\Gamma \vdash t \triangleright A$ و تحقق $\Gamma \vdash t \triangleleft A$ ) يجسد تماماً الأشكال الطبيعية لـ STLC+ تحت اختزال $\beta$ والتحويلات التبادلية.

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

ب. التطبيع عبر العلاقات المنطقية

لتطبيق مبرهنة الاستيفاء على الحدود جيدة النوع (well-typed) لأي حدود (ليس فقط تلك الموجودة بالفعل في شكل طبيعي)، يثبت المؤلفون التطبيع (Normalization) لـ STLC+ مع التحويلات التبادلية.

يستخدمون حجة العلاقات المنطقية (Logical Relations) (مستوحاة من أبيل وساتلر).
يقدمون مفهوم "التغطية" (Covering) للتعامل مع الأنواع الموجبة ( $+$ و $\bot$ ). بما أن عمليات الإزالة على هذه الأنواع (مثل if أو raise) ليست محايدة، فقد عرفوا محدد "تغطية" يلتقط الحدود التي تأخذ شكل أشجار الحالة (case trees)، مما يضمن أن أوراق الشجرة تحقق شروط القابلية للاختزال.
يؤدي هذا إلى برهان مفاده أن كل حد جيد النوع يؤول إلى شكل طبيعي يحقق خاصية الصيغة الجزئية.

ج. برهان الاستيفاء

باستخدام التوصيف ثنائي الاتجاه، يقوم المؤلفون بإجراء استقراء متبادل على بنية الأشكال الطبيعية والمحايدات:

يحافظون على تقسيم السياق ( $\Gamma = \Gamma_s \cup \Gamma_t$ ) لتتبع المتغيرات التي تنتمي إلى مفردات المصدر ( $A$ ) والهدف ( $B$ ).
لكل قاعدة في النظام ثنائي الاتجاه، يبنون نوع المستوفي $M$ والحدود $l$ (من المصدر إلى $M$ ) و $r$ ( $M$ إلى الهدف) بحيث يعيد التركيب بناء الحد الأصلي.
التعامل مع الانعكاسات: جانب مبتكر في برهانهم هو التعامل مع الحالات التي تتبدل فيها أدوار "المصدر" و "الهدف" في السياق (على سبيل المثال، في قاعدة Demote)، وهو ما عانى منه البرهان الأصلي.

3. المساهمات الرئيسية

برهان جديد لمبرهنة تشوبريتش: يقدم المؤلفون برهاناً مصححاً وأكثر وضوحاً من الناحية البنيوية للاستيفاء ذي الصلة بالبرهان لـ STLC+. من خلال استخدام النوعية ثنائية الاتجاه، يتجنبون عثرات الاستقراء الأصلي القائم على الحجم ويصححون معالجة الحالات الخاطئة.
التأطير في Rocq: تم تأطير الميتا-نظرية بالكامل في مساعد البرهان Rocq (المعروف سابقاً بـ Coq). يشمل ذلك:
- أول برهان مؤطر رسمياً للتطبيع لـ STLC+ مع التحويلات التبادلية.
- تأطير كامل لبرهان الاستيفاء ذي الصلة بالبرهان.
- يبلغ حجم الكود حوالي 4,000 سطر من الكود (LoC)، وهو أكثر إيجازاً بكثير من التأطيرات السابقة لخصائص منطقية مماثلة.
الربط بين النوعية ثنائية الاتجاه وخاصية الصيغة الجزئية: تثبت الورقة صراحةً أن أنظمة النوعية ثنائية الاتجاه توصف طبيعياً الأشكال الطبيعية ذات خاصية الصيغة الجزئية، وهو ارتباط كان مشتبهاً به ولكن لم يتم استغلاله بصرامة سابقاً في وجود المجموعات.
التعامل مع الثوابت والمعادلات: تم تعميم المبرهنة لتشمل أي ثوابت ونظريات معادلات، مما يظهر متانة النهج.

4. النتائج

مبرهنة (الاستيفاء): لأي حد جيد النوع $x:A \vdash t:B$ في STLC+، يوجد نوع $C$ مبني من المفردات المشتركة لـ $A$ و $B$ ، وحدود $u: A \to C$ و $v: C \to B$ ، بحيث يكون $(\lambda y. v) u \twoheadrightarrow^* t$ .
التطبيع: كل حد جيد النوع في STLC+ يؤول إلى شكل طبيعي (تحت اختزال $\beta$ والتحويلات التبادلية).
التحقق الآلي: البرهانات تم التحقق منها آلياً في Rocq. يستخدم التأطير أدوات الأتمتة مثل AutoSubst2 لحساب الاستبدال و setoid rewriting لخطوات الاختزال، رغم أن المؤلفين أشاروا إلى تحديات في الأداء مع المحركات الحالية.

5. الأهمية

الصحة والموثوقية: من خلال تأطير البرهان، يكشف المؤلفون ويصححون الأخطاء الدقيقة في عمل تشوبريتش الأصلي في التسعينيات، مما يوفر أساساً موثقاً للاستيفاء ذي الصلة بالبرهان.
التحول المنهجي: تدعو الورقة إلى استخدام النوعية ثنائية الاتجاه كأداة أساسية لإثبات الخصائص البنيوية (مثل الاستيفاء) في نظرية النوع، والابتعاد عن الاستقراءات التقليدية التي غالباً ما تكون فوضوية والقائمة على الحجم.
الآثار الفئوية (Categorical Implications): بما أن STLC+ هي اللغة الداخلية للفئات المغلقة ثنائية كارتيزي (biCCCs)، فإن النتيجة تقدم استنتاجات فئوية، مما يوفر "تصنيفاً" (categorification) لنتائج الاستيفاء في جبر هيتينج.
الاتجاهات المستقبلية: يحدد المؤلفون مسارات لتوسيع هذا العمل ليشمل:
- الحدود غير الطبيعية: استيفاء الحدود التي تحتوي على redexes (cuts) من خلال تقييد مفردات صيغ القطع.
- الاستيفاء الموحد (Uniform Interpolation): توليد مستوفي واحد للغة فرعية كاملة.
- الأنواع التابعة (Dependent Types): توسيع المبرهنة إلى نظرية النوع التابعة، رغم أن هذا يواجه تحديات تتعلق بصحة النوع تحت التحويلات التبادلية (مثل نمط الـ convoy).

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