💻 computer science

A formalization of System I with type Top in Agda

تقدم هذه الورقة صياغة صورية كاملة في لغة Agda لمتغير من النظام I ممتد بالنوع Top، بما في ذلك براهين صورية على التقدم والتقارب القوي.

المؤلفون الأصليون: Agustín Séttimo, Cristian Sottile, Cecilia Manzino

نُشر 2026-03-26

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

CC BY 4.0

المؤلفون الأصليون: Agustín Séttimo, Cristian Sottile, Cecilia Manzino

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

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

النظام I هو نوع جديد من كتب القواعد التي تقول: "انتظر لحظة! الدقيق والسكر هما الشيء نفسه مثل السكر والدقيق. إنهما متماثلان بنيوياً (isomorphic) في المعنى".

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

إليك تفصيل ما فعله المؤلفون، باستخدام تشبيهات من الحياة اليومية:

1. المشكلة: المطبخ الذي "لا يهم فيه الترتيب"

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

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

2. الحل: إضافة "القمة" و"الإيصالات"

أضاف المؤلفون مكوناً جديداً يسمى القمة (Top) (فكر فيه كـ "بطاقة عالمية" يمكن أن تمثل أي مكون).

اللمسة المبتكرة: لجعل هذا يعمل في نظام إثبات حاسوبي (Agda)، لم يكن بإمكانهم مجرد قول "إنهما متساويان". كان عليهم جعل الكمبيوتر يحمل إيصالاً (شاهداً/witness) في كل مرة يقوم فيها بتبديل المكونات.
التشبيه: بدلاً من مجرد تحويل "اللحم" إلى "جبن" بشكل سحري، يجب على الكمبيوتر أن يحمل ملاحظة صغيرة تقول: "أنا أحول هذا اللحم إلى جبن بناءً على القاعدة رقم 4". هذا الإيصال يثبت لماذا حدث التبديل، مما يضمن توقف العملية في النهاية.

3. الهدف: إثبات أنك لن تتعثر

الهدف الرئيسي من الورقة كان إثبات شيئين حول هذا المطبخ الجديد:

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

لماذا هذا صعب؟
تخيل وصفة تقول: "خذ هذه الشطيرة، بدل المكونات، ثم أعد تبديلها، ثم بدلهم مرة أخرى..." إذا لم تكن القواعد مثالية، فقد تظل الشطيرة تُبدل للأبد. لقد أثبت المؤلفون أنه مع نظام "الإيصالات" هذا، يجب أن تُؤكل الشطيرة في النهاية.

4. الأداة: Agda (مساعد الطاهي فائق الصرامة)

لم يكتفِ المؤلفون بكتابة هذا على الورق؛ بل بنوا هذا داخل Agda.

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

5. مثال "أوميجا": فخ الحلقة اللانهائية

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

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

ملخص

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

يمكنك دائماً الاستمرار في الطبخ.
لن تطبخ للأبد.
النظام آمن وموثوق.

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

إليك ملخص تقني مفصل لورقة "صياغة رسمية لنظام I مع النوع Top في Agda" من تأليف أغوستين سيتيمو، كريستيان سوتيلي، وسيسيليا مانزينو.

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

تتناول الورقة تحديات الصياغة الرسمية لـ نظام I (System I)، وهو حساب لامدا بسيط النوع (simply-typed lambda calculus) ممتد بالأزواج حيث تُعتبر الأنواع المتماثلة (isomorphic types) متساوية. وبينما يسمح نظام I ببرمجة مرنة (على سبيل المثال، إعادة ترتيب الوسائط بسبب تماثل الأنواع) وعدم الاكتراث بالبرهان (proof-irrelevance)، فإن دلالاته التشغيلية معقدة بسبب التفاعل بين تماثل الأنواع واختزال المصطلحات (term reduction).

تشمل التحديات المحددة ما يلي:

اللا حتمية (Non-determinism): قواعد الاختزال القياسية (مثل الإسقاط $\pi_1$ ) تصبح غير حتمية عندما تسمح تماثلات الأنواع (مثل تبديل الأزواج) بإعادة ترتيب المصطلحات.
الإنهاء (Termination): ضمان النمطية القوية (Strong Normalization - SN) أمر صعب لأن إضافة التماثلات يمكن أن تؤدي إلى حلقات اختزال لانهائية (مثل التوسع عبر $\eta$ أو إعادة الكتابة المتناظرة).
تعقيد الصياغة الرسمية: تفتقر التنفيذات الحالية (مثل تلك الموجودة في Haskell) غالبًا إلى البراهين الصارمة على الإنهاء والتقدم (progress). إن إضافة أنواع أساسية جديدة (مثل Top) إلى حساب يعتمد على التكافؤ يتطلب توسيع علاقات التكافؤ بعناية للحفاظ على النمطية.

2. المنهجية

يستخدم المؤلفون نظرية الأنواع المعتمدة (Dependent Type Theory) باستخدام مساعد الإثبات Agda لبناء صياغة رسمية كاملة ومحققة. تتضمن منهجيتهم ما يلي:

النوع الداخلي (Intrinsic Typing): بدلاً من النوع الخارجي (حيث تكون المصطلحات والأنواع منفصلة)، يستخدمون مصطلحات ذات نوع داخلي. كل مصطلح في كود Agda هو برهان على اشتقاق نوعه الخاص. يضمن هذا أن حفظ النوع (type preservation) يتم تلقائيًا ويلغي الحاجة إلى إثبات حفظ الموضوع (subject reduction) بشكل منفصل للعديد من العمليات.
مؤشرات دي بروين (De Bruijn Indices): يتم تمثيل المتغيرات كأعداد طبيعية (مؤشرات) بدلاً من الأسماء لتجنب مشكلات التحويل $\alpha$ (alpha-conversion) والتعويض المتجنب لالتقاط الأسماء.
الشهود الصريحون (Explicit Witnesses): للتعامل مع قاعدة التحويل ( $A \equiv B \implies t:A \to t:B$ )، يقدم الحساب منشئًا نحويًا يسمى [ρ]≡t. هنا، ρ هو شاهد صريح (مصطلح برهان) للتماثل النوعي. يجعل هذا تطبيق التماثلات صريحًا في بنية المصطلح، مما يسمح لعلاقة الاختزال باستهداف وإزالة هذه الشهود.
إعادة الكتابة الموجهة (Directed Rewriting): على عكس نظام I، الذي يستخدم علاقة تكافؤ ( $\Leftrightarrow$ )، تُعرف هذه الصياغة علاقة إعادة كتابة موجهة ( $\rightsquigarrow$ ). يتم توجيه التماثلات لتفكيك الشهود، مما يمنع حلقات الاختزال اللانهائية حيث يُعاد كتابة المصطلح ذهابًا وإيابًا بين أشكال متماثلة.

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

أ. توسيع نظام I باستخدام `Top`

يوسع المؤلفون نظام I بإضافة النوع Top (الذي يمثل الحقيقة المنطقية). هذا يقدم تماثلات جديدة:

$A \times \top \equiv A$ (محايد الضرب)
$\top \to A \equiv A$ (محايد الاستلزام)
$A \to \top \equiv \top$ (الطبيعة الامتصاصية)
يقومون بتكييف تماثلات المصطلحات للتعامل مع هذه القواعد الجديدة، مما يضمن اختزال المصطلحات التي تتضمن Top بشكل صحيح.

ب. الصياغة في Agda

تقدم الورقة تطويرًا كاملاً في Agda يشمل:

البنية (Syntax): تعريفات للأنواع، السياقات، والمصطلحات (بما في ذلك منشئ الشاهد).
الدلالات (Semantics): تعريفات التعويض، اختزال $\beta$ (beta-reduction)، وقواعد تكافؤ المصطلحات المحددة (مثل COMM و ASSO و DIST و CURRY والقواعد الجديدة لـ Top).
علاقة الاختزال (Reduction Relation): مُعرفة كunion لـ الاختزال القياسي ( $\to$ ) وتكافؤ المصطلحات ( $\Leftrightarrow$ )، وهي مصممة خصيصًا لإزالة شهود التماثل.

ج. براهين التقدم والنمطية القوية (Progress and Strong Normalization)

التقدم (Progress): يثبت المؤلفون أن كل مصطلح مغلق وذو نوع معين هو إما قيمة أو يمكنه اتخاذ خطوة اختزال. يتعاملون مع تعقيد شهود التماثل من خلال تحليل "الشكل الطبيعي" للمصطلح الفرعي وتطبيق قاعدة التماثل المناسبة لإزالة الشاهد.
النمطية القوية (Strong Normalization - SN): يثبتون أن كل تسلسل اختزال يبدأ من مصطلح ذي نوع معين هو تسلسل منتهٍ.
- التقنية: يستخدمون نهج شايفر (Schäfer's approach) للقدرة على الاختزال (المقتبس من صياغات Coq لحساب System F)، والمُعمم لـ Agda.
- التفسير: يعرفون دالة تفسير $[[t]]$ تربط المصطلحات بمجموعات من المصطلحات ذات النمطية القوية.
- الكفاية (Adequacy): جوهر البرهان هو مبرهنة الكفاية، والتي تنص على أنه إذا كان التعويض "كافيًا" (يربط المتغيرات بمصطلحات ذات نمطية قوية)، فإن المصطلح الناتج عن تطبيق ذلك التعويض هو أيضًا ذو نمطية قوية. هذا يعالج التفاعلات المعقدة لـ $\beta$ -reduction، والإسقاطات، وشهود التماثل.

د. دالة التقييم (Evaluation Function)

بما أن SN مثبت بطريقة بنائية، يعرّف المؤلفون دالة تقييم كلية (eval) في Agda. تأخذ هذه الدالة مصطلحًا مغلقًا ودليل النمطية القوية الخاص به، وتعيد تسلسل الاختزال إلى قيمة. هذا يثبت القدرة الحسابية العملية للصياغة.

4. النتائج

إنهاء $\Omega$ : توضح الورقة أن المصطلح الكلاسيكي غير المنتهي $\Omega = (\lambda x. xx)(\lambda x. xx)$ ، عند استخدامه مع Top واستخدام شهود التماثل المحددة، ينتهي بالفعل في هذا النظام. تجبر الشهود الصريحة مسار اختزال محدد يؤدي في النهاية إلى إزالة حلقة التطبيق الذاتي، مما يختزل $\Omega$ إلى القيمة الوحدة ⋆.
صياغة كاملة: الصياغة الكاملة للحساب، بما في ذلك براهين التقدم والنمطية القوية، مُنفذة بالكامل في Agda ومتاحة للجمهور على GitHub.
التعامل مع اللا حتمية: نجحت الصياغة في حل مشكلات اللا حتمية في نظام I القياسي من خلال جعل تطبيق التماثل موجهاً نحو بناء الجمل (syntax-directed) ومدفوعاً بالشهود.

5. الأهمية

الصرامة التأسيسية: هذه هي أول صياغة معروفة لبرهان النمطية لحساب لامدا مع تماثلات الأنواع في سياق بنائي (Agda). إنها تتحقق من السلامة النظرية لنظام I مع Top.
عدم الاكتراث بالبرهان (Proof Irrelevance): يساهم العمل في فهم عدم الاكتراث بالبرهان في نظرية الأنواع، حيث يوضح كيف يمكن معاملة البراهين المختلفة للقضايا المتماثلة كأنها متطابقة دون كسر النمطية.
التقدم المنهجي: يوفر استخدام الشهود الصريحة والنوع الداخلي نموذجًا قويًا لصياغة حسابات أخرى ذات علاقات تكافؤ معقدة. كما يوضح أن "توجيه" علاقات التكافؤ إلى قواعد إعادة كتابة هو استراتيجية قابلة للتطبيق لضمان الإنهاء.
التطبيقات المستقبلية: تضع هذه الصياغة الأساس لتوسيع هذه الأنظمة لتشمل تعدد الأشكال (System F مع التماثلات) والمتغيرات غير المحددة النوع، وكذلك استكشاف العلاقة مع الأنظمة الامتدادية مثل System I $\eta$ .

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