💻 computer science

Compositional Program Verification with Polynomial Functors in Dependent Type Theory

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

المؤلفون الأصليون: C. B. Aberlé

نُشر 2026-04-03

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: C. B. Aberlé

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

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

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

إليك تفصيل أفكار الورقة باستخدام تشبيهات بسيطة:

1. صندوق "الواجهة" (الدوال متعددة الحدود - Polynomial Functors)

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

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

في الورقة، تُسمى هذه الصناديق "الدوال متعددة الحدود" (Polynomial Functors). وهي مجرد طريقة رياضية متطورة لقول: "هذا هو شكل نقاط اتصال هذا الصندوق".

2. "مخطط التوصيل" (التركيب - Composition)

الآن، تخيل أن لديك صندوقاً يقوم بفرز البريد، وصندوقاً آخر يقوم بختم الأظرف.

لصنع "نظام معالجة بريد"، لا تحتاج لإعادة كتابة الكود الخاص بالفرز أو الختم.
ببساطة، تقوم بتوصيل مخرج صندوق "الفرز" بمدخل صندوق "الختم".

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

3. "كتاب القواعد" (المواصفات والدوال متعددة الحدود المعتمدة - Specifications & Dependent Polynomials)

مجرد القدرة على توصيل الصناديق لا يعني أنها ستؤدي الوظيفة الصحيحة. فربما يكون صندوق الفرز معطلاً ويقوم برمي الرسائل.

لإصلاح ذلك، يضيف المؤلفون "كتاب قواعد" (مواصفة) لكل صندوق.

الوعد: "إذا أعطيتني رسالة (إدخال)، أعدك بأن أعطيك رسالة مختومة (إخراج)".
الشرط: كتاب القواعد ذكي؛ فهو يقول: "إذا كانت الرسالة موجهة لـ 'بوب'، فأعدك بختمها باللون الأحمر. وإذا كانت لـ 'أليس'، فأعدك بختمها باللون الأزرق".

في الورقة، تُسمى هذه "الدوال متعددة الحدود المعتمدة" (Dependent Polynomials). وهي بمثابة عقد ديناميكي يتغير بناءً على ما يدخل إلى الصندوق.

4. "المفتش" (التحقق - Verification)

إليك القوة الخارقة لهذا الإطار: التحقق التركيبي (Compositional Verification).

عادةً، لإثبات أن نظاماً كاملاً آمن، يتعين عليك فحص كل سطر كود في النظام بأك//ل. هذا يشبه فحص كل طوبة في ناطحة سحاب لتثبت أن المبنى لن ينهار.

تقول هذه الورقة: لا، لست بحاجة للقيام بذلك.

افحص صندوق "الفرز" مقابل كتاب القواعد الخاص به. (ناجح!)
افحص صندوق "الختم" مقابل كتاب القواعد الخاص به. (ناجح!)
افحص مخطط التوصيل للتأكد من أن مخرجات أحدهما تتوافق مع مدخلات الآخر. (ناجح!)

النتيجة: بما أن القطع تم فحصها والوصلات صحيحة، فإن النظام بأكمله مضمون الصواب. إن "البرهان" يترابط ويتكون تماماً كما تتكون الصناديق.

5. "الروبوت" (آلات ميلي - Mealy Machines)

كيف نشغل هذه الصنواع فعلياً؟ تستخدم الورقة "آلات ميلي" (Mealy Machines).
تخيل "آلة ميلي" كأنها روبوت يمتلك ذاكرة.

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

6. "شرطي المرور" (التزامن - Concurrency)

تنظر الورقة أيضاً فيما يحدث عندما تعمل الصناديق في نفس الوقت (مثل شخصين يحاولان استخدام نفس الطابعة).

قدموا مفهوم "الجمع المتوازي" الذي يعمل مثل شرطي المرور.
هو يضمن عدم محاولة صندوقين الاستحواذ على نفس المورد في اللحظة ذاتها، مما يمنع "الاختناقات المرورية" (حالات السباق/Race Conditions) في البرمجيات.

الصورة الكبيرة

لقد بنى المؤلف، سي. بي. أبيرلي (C.B. Aberlé)، "مجموعة ليغو" رياضية لمهندسي البرمجيات.

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

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

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

إليك ملخص تقني مفصل لورقة البحث بعنوان "التحقق التكويني من البرامج باستخدام الدوال متعددة الحدود في نظرية النوع التابع" للكاتب س. ب. أبيرلي (C.B. Aberlé).

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

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

تعالج الورقة الحاجة إلى إطار عمل تكويني للتحقق من البرامج يهدف إلى:

تفكيك البرامج المعقدة إلى وحدات أبسط يمكن التحقق منها بشكل مستقل.
السماح بتركيب هذه الوحدات (ربطها معاً) مع الحفاظ على ضمانات صحتها.
توحيد تمثيل الواجهات (interfaces)، والتنفيذات (implementations)، والمواصفات (specifications) (الشروط المسبقة/اللاحقة)، والدلالات التشغيلية (operational semantics) ضمن بنية رياضية واحدة.
العمل ضمن نظرية النوع التابع (Dependent Type Theory)، مما يسمح للمواصفات بالاعتماد على القيم وهياكل البيانات أثناء وقت التشغيل.

2. المنهجية

يستخدم المؤلف الدوال متعددة الحدود (Polynomial Functors) ضمن سياق نظرية النوع التابع (المصاغة تحديداً في لغة Agda) لنمذجة الأنظمة البرمجية. تعتمد المنهجية على ثلاثة تجريدات أساسية:

أ. الدوال متعددة الحدود كواجهات

تمثل الدالة متعددة الحدود $P(y) = \sum_{a:A} y^{B(a)}$ واجهة البرنامج:

$A$ : نوع المواقع (المدخلات).
$B(a)$ : نوع الاتجاهات (المخرجات/الاستجابات) لمدخل معين.
يمثل المورفيزم (العدسة/lens) بين الدوال متعددة الحدود برنامجاً ينفذ واجهة ما عبر استدعاء واجهة أخرى.

ب. الموناد الحر (Free Monads) كتنفيذات

لنمذجة التركيب المتسلسل حيث يتم استدعاء الواجهة صفر أو مرة واحدة أو عدة مرات، يستخدم إطار العمل الموناد الحر على دالة متعددة الحدود ( $Free\ P$ ).

تنفيذ لواجهة $p$ يعتمد على واجهة $q$ هو مورفيزم $p \Rightarrow Free\ q$ .
ينمذج هذا الهيكل بشكل طبيعي منطق "الافتراض-الضمان" (assume-guarantee): بافتراض وجود تنفيذ لـ $q$ ، فإننا نضمن وجود تنفيذ لـ $p$ .

ج. الدوال متعددة الحدود التابعة كمواصفات

للانتقال من التنفيذ إلى التحقق، تقدم الورقة الدوال متعددة الحدود التابعة (Dependent Polynomials).

تتكون الدالة متعددة الحدود التابعة فوق $P=(A, B)$ $P = (A, B)$ من:
- الشروط المسبقة (Preconditions): عائلة $C: A \to Set$ على المدخلات.
- الشروط اللاحقة (Postconditions): عائلة $D: (a:A) \to C(a) \to B(a) \to Set$ على المخرجات.
يقوم هذا بتشفير عقد مشابه لثلاثية هوار (Hoare triple): إذا كان المدخل $a$ يحقق الشرط $C(a)$ ، فيجب أن يحقق المخرج $D(a, \dots)$ .
تُستخدم المونادات الحرة التابعة ($FreeDep$) لرفع هذه المواصفات إلى مستوى الحسابات، مما يسمح بإثبات أن الحساب يحترم مواصفاته بافتراض أن تبعاته تحترم مواصفاتها.

د. الدلالات التشغيلية عبر آلات ميلي (Mealy Machines)

تُعرف الورقة الدلالات التشغيلية باستخدام آلات ميلي (وهي أوتوماتا ذات حالة/stateful automata).

تأخذ آلة ميلي لواجهة $P$ مدخلاً، وتنتج مخرجاً، وتنتقل إلى حالة جديدة.
من الأهمية بمكان أن آلات ميلي تعمل كـ مشغلات (runners) للتأثيرات (effects). فإذا كان البرنامج يستخدم واجهة $q$ (مثل تأثير الحالة)، فإن آلة ميلي لـ $q$ توفر التنفيذ الملموس لهذا التأثير.
يثبت إطار العمل أن تركيب وحدة برمجية مع آلة ميلي ينتج آلة ميلي جديدة لواجهة الوحدة.

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

1. التحقق التكويني عبر مخططات التوصيل (Wiring Diagrams)

توضح الورقة أن التنفيذات وتحققاتها تتراكب عبر مخططات التوصيل.

مبرهنة: بالنظر إلى مخطط توصيل للوحدات وتنفيذات مُحققة لكل صندوق، فإن النظام المركب يمتلك تنفيذاً مُحققاً للواجهة الخارجية.
يتم تحقيق ذلك عبر تركيب كليسلي (Kleisli composition) للموناد الحر ونظيره التابع. يعتمد الإثبات على حقيقة أن الدوال متعددة الحدود التابعة مغلقة تحت الجمع (coproducts)، مما يسمح بدمج مواصفات الوحدات الفرعية في مواصفة واحدة للكل.

2. البنية الفئوية الموحدة

حدد المؤلف البنية الفئوية المجردة التي يقوم عليها هذا الإطار:

الواجهات ($Int$): فئة مونويدية (Monoidal Category) (فئة كليسلي للموناد الحر على Poly).
المواصفات ($Spec$): فئة مونويدية من الأزواج (دالة متعددة الحدود، دالة متعددة حدود تابعة).
المجموعات المسبقة (Presheaves): تعيين آلات ميلي للواجهات يشكل مجموعاً مسبقاً مونويدياً ضعيفاً (lax monoidal presheaf).
التحويل الطبيعي (Natural Transformation): يوجد تحويل طبيعي مونويدي من المجموع المسبق للأنظمة المُحققة ($DepMealy $) إلى المجموع المسبق للأنظمة ($ Mealy$) عبر الدالة الناسيّة (forgetful functor).
يسمح هذا التجريد بتعميم إطار العمل على فئات أخرى ونواتج مونويدية مختلفة (مثل التزامن).

3. الدلالات التشغيلية للتحقق

تربط الورقة بين التحقق الساكن والتنفيذ الديناميكي. فهي تبين أن آلات ميلي التابعة (آلات ميلي مزودة بأدلة التحقق) مغلقة تحت التركيب. وهذا يعني أن برنامجاً مُحققاً يعمل على آلة حالة مُحققة ينتج آلة حالة مُحققة للنظام المركب.

4. التوسع نحو التزامن والتحقق العلاقاتي

في الملحق، يتم توسيع إطار العمل ليشمل الوحدات المتزامنة باستخدام الجمع المتوازي ( $\|$ ) بدلاً من الجمع القياسي ( $\oplus$ ).

يسمح الجمع المتوازي باستدعاء واجهات متعددة في آن واحد.
يدعم هذا الهيكل التحقق العلاقاتي (مثل عدم التداخل/non-interference، والرتابة/monotonicity) عبر تفكيك المواصفات إلى أجزاء أحادية وأجزاء علاقاتية تربط مدخلات ومخرجات المكونات المتزامنة.
ثبت أن الجمع المتوازي هو "أفيني" (affine) (مما يمنع حدوث سباق البيانات/race conditions بالتصميم، حيث لا يمكن استخدام السلك في مكانين في وقت واحد).

4. النتائج

الصياغة الرسمية: تمت صياغة إطار العمل بالكامل، بما في ذلك التعريفات والمبرهنات والأمثلة، في لغة Agda.
دراسات الحالة:
- عمليات القوائم (List Operations): نجح إطار العمل في نمذجة والتحقق من عمليات مثل fold و append و concat. وقد أظهر كيفية التحقق من append عبر تركيب حالات الأساس والخطوة المُحققة.
- متتالية فيبوناتشي مع الحالة (Fibonacci with State): تم تنفيذ مولد فيبوناتشي باستخدام تأثير الحالة. وثقت الورقة أن الآلة تحسب أرقام فيبوناتشي بشكل صحيح وتحافظ على ثابت الحالة (أن الحالة تمثل أرقام فيبوناتشي المتتالية).
التكوينية (Compositionality): تؤكد البراهين أن جهد التحقق يتناسب خطياً مع عدد المكونات، وليس مع تعقيد النظام ككل، طالما تم التحقق من المكونات بشكل مستقل.

5. الأهمية

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

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