مرجع
آخر الزيارات

نظام هيندلي-ميلنر للأنواع

5٬328 كلمة•0 مشاهدة•🗒️ منذ يومين
باختصار: يُعد نظام هيندلي-ميلنر للأنواع ، يُعرف اختصارًا بـ HM، هو نظام أنواع كلاسيكي لتكامل لامدا مع تعدد الأشكال البارامتري. تتناول المقالة 40 قسماً، منها «نظام هيندلي–ميلنر للأنواع»، «النوع الرئيسي» و«المتغيرات الحرة للأنواع».
المحتويات
  1. نظام هيندلي–ميلنر للأنواع
  2. النوع الرئيسي
  3. المتغيرات الحرة للأنواع
  4. nil : forall a . List a
  5. الأنواع المتعددة
  6. قاعدة التعميم
  7. إثبات صحة الخوارزمية
  8. مؤخرًا، قام دولان ومايكروفت
  9. قاعدة الإسناد النمطي
  10. رتبة النوع
  11. قواعد الكتابة النوعية
  12. درجات الحرية في تفعيل القواعد
  13. خطأ 'الأنواع غير متطابقة'
  14. التزامات الإثبات
  15. نظام قواعد موجه نحويًا
  16. الأُحاديات الشكل مقابل التعدد الشكلي
  17. خوارزمية الاستنتاج
  18. العواقب
  19. let id = λ x . x
  20. وإلا
  21. التعدد الشكلي مع let
  22. الاستبدال في السياقات النوعية
  23. التعددية الشكلية في ليت
  24. نظام الاستنتاج
  25. id ≡ λx . x
  26. الأنواع الأحادية
  27. الخوارزمية J
  28. الخوارزمية W
  29. التصنيف الفرعي
  30. التعريفات العودية
  31. nil' : List Number
  32. add : Number -> Number -> Number
  33. السياق والإسناد
  34. درجات الحرية في اختيار القواعد
  35. المقدمة
  36. الأنواع من المرتبة الأعلى
  37. التحميل الزائد
  38. نظرة عامة
  39. البنية الصرفية
  40. لاحقًا، ادعى بارّو

بدايةً، يُعد نظام هيندلي-ميلنر للأنواع ، يُعرف اختصارًا بـ HM، هو نظام أنواع كلاسيكي لتكامل لامدا مع تعدد الأشكال البارامتري. ويُعرف كذلك باسم داماس–ميلنر أو داماس–هندلي–ميلنر. وقد وُصف لأول مرة من قبل ج. روجر هندلي ثم أعاد اكتشافه روبن ميلنر. وقد قدم لويس داماس تحليلاً شكليًا دقيقًا وإثباتًا للطريقة في أطروحة الدكتوراه الخاصة به. ونتناول فيما يلي مزيدًا من التفاصيل.

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

نظام هيندلي–ميلنر للأنواع

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

النوع الرئيسي

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

المتغيرات الحرة للأنواع

كذلك، وجود كل من المتغيرات المقيدة والحرة في نفس النوع غير شائع في لغات البرمجة. في الغالب، تُعامل جميع المتغيرات النوعية كأنها مُقيدة ضمناً. مثلاً، لا توجد عبارات بمتغيرات حرة في برولوغ. وكذلك في هاسكل، حيث تُعتبر جميع المتغيرات النوعية مُقيدة ضمناً، أي أن النوع a -> a في هاسكل يعني . ومن الأمور غير الشائعة كذلك تأثير التقييد في الجهة اليمنى في الإسنادات.

وفي هذا السياق، عادةً ما ينشأ اختلاط المتغيرات المقيدة والحرة من استخدام متغيرات حرة في تعبير. مثال على ذلك دالة الثابت K = ، التي لها النوع الأحادي . يمكن فرض التعددية في الأنواع عبر التعبير:

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

من جهة ثانية، هنا، لها النوع . المتغير النوعي الحر جاء من النوع المرتبط بالمتغير في السياق المحيط. له النوع . يمكن تخيّل أن المتغير النوعي الحر في نوع تم تقييده عبر في نوع . لكن مثل هذا المجال لا يمكن التعبير عنه في نظام HM. بل يُعبَّر عنه من خلال السياق.

.

nil : forall a . List a

ومن جهة أخرى، يمكن تحويل الأنواع المتعددة الأشكال إلى أُحادية الشكل عبر استبدال متسق لمتغيراتها. أمثلة على نسخ أُحادية الشكل:

id : forall a . a -> a

id' : String -> String

الأنواع المتعددة

ومن ناحية أخرى، كمثال آخر، هو نوع دالة تحوّل كل المجموعات المنتهية إلى أعداد صحيحة. الدالة التي تُعيد حجم مجموعة هي قيمة لهذا النوع.

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

وعلى صعيد آخر، تُقاس مساواة الأنواع المتعددة بترتيب الكمّيات وتغيير أسماء المتغيرات المُقيدة (-تحويل). علاوة على ذلك، يمكن حذف المتغيرات المُقيدة غير الموجودة في النوع الأحادي.

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

ومن ناحية أخرى، الأنواع المتعددة (أو مخططات الأنواع) هي أنواع تحتوي على متغيرات مُقيَّدة بواحد أو أكثر من كمّيات "لكل"، مثل .

قاعدة التعميم

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

إثبات صحة الخوارزمية

كذلك، وبالتالي فإن تنقيح المتغيرات الحرة يعني تنقيح الاستنتاج بأكمله.

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

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

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

مؤخرًا، قام دولان ومايكروفت

من جهة ثانية، وبيّنا أن الطرح الجبري لتأصيل التصنيف الفرعي يسمح بإنتاج مخططات أنواع رئيسية مدمجة للغة شبيهة بـML (سُميت MLsub).

وفي السياق ذاته، بتأصيل العلاقة بين تبسيط مخططات الأنواع وتبسيط الأتمتة المنتهية غير الحتمية (NFA)،

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

قاعدة الإسناد النمطي

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

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

رتبة النوع

من جهة ثانية، تُشير تعددية الأشكال إلى أن تعبيرًا واحدًا نفسه يمكن أن يكون له (وربما عدد لا نهائي) من الأنواع. ولكن في نظام الأنواع هذا، لا تكون هذه الأنواع غير مترابطة تمامًا، بل يتم تنظيمها بواسطة التعدد الشكلي المعلمي.

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

ومن ناحية أخرى، يمكن التعبير عن الاستبدال المتسق رسميًا من خلال تطبيق استبدال على تعبير من نوع ، ويُكتب . كما يُشير المثال، فإن الاستبدال لا يرتبط فقط ارتباطًا وثيقًا بعلاقة ترتيب تُعبّر عن كون نوع ما أكثر أو أقل تخصيصًا، بل يرتبط كذلك بعملية التكميم الكلي التي تسمح بتطبيق الاستبدال.

في مثالنا السابق، فإن تطبيق الاستبدال سينتج عنه:

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

كذلك، العلاقة تُشكّل مجموعة مرتبة جزئيًا، والنوع هو أصغر عنصر فيها.

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

وفي هذا الصدد، كمثال، يمكن أن تكون هوية الدالة من النوع ، وكذلك من النوع أو والكثير من الأنواع الأخرى، ولكن **ليس** من النوع . النوع **الأكثر عمومية** لهذه الدالة هو ، بينما الأنواع الأخرى أكثر تخصيصًا ويمكن اشتقاقها من النوع العام عبر استبدال متسق لنوع آخر مكان **معامل النوع**، أي المتغير المُكمَّم . يفشل المثال المضاد لأن الاستبدال غير متسق.

قواعد الكتابة النوعية

مثال: إثبات أن حيث :

مثال: لإثبات التعميم،

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

وفي السياق ذاته، يعرض الصندوق الجانبي قواعد الاستنتاج الخاصة بنظام الأنواع لهندلي-ميلنر. يمكن تقسيم القواعد على وجه التقريب إلى مجموعتين:

:

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

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

درجات الحرية في تفعيل القواعد

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

إذا كانت كذلك، فلا بأس. يمكن لاحقًا اختيار للنتيجة.

وفي هذا السياق، أما إذا لم تكن كذلك ولا يمكن تعديلها إلى نوع دالي (تابعي)، يفشل التحقق من النوع.

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

وفي السياق ذاته، : قاعدة التطبيق فقط قد تُجبر على تعديل المتغيرات "المفتوحة" حتى الآن، كما تتطلبه المسلّمتان.

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

: هذه القاعدة لا تترك مجالًا للاختيار. انتهى الأمر.

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

  • unify(ta, tb):
  • ta = find(ta)
  • tb = find(tb)
  • إذا كان كلٌّ من ta وtb على شكل D p1..pn بنفس D وn فإننا
  • نقوم بـ unify(ta[i], tb[i]) لكل عنصر مطابق i

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

المسلمة الأولى تُجبر النتيجة على أن تكون من الشكل .

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

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

خطأ 'الأنواع غير متطابقة'

من جهة ثانية، وبما أن لدينا الآن مخططًا عامًّا لخوارزمية استنتاج، فسيُعرض تقديم أكثر رسمية في القسم التالي. وقد وُصِفت هذه الخوارزمية في ملنر ص. 370 وما بعدها باسم الخوارزمية J.

التزامات الإثبات

كذلك، قبل صياغة التزامات الإثبات، لا بد من التنويه إلى الانحراف بين نظامي القواعد D وS وبين الخوارزميات المعروضة.

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

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

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

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

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

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

الامتدادات

نظام قواعد موجه نحويًا

من جانب آخر، مما يعني أنه يمكن اشتقاق النوع الرئيسي للتعبير في مما يسمح لنا بتعميم البرهان في النهاية.

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

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

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

  • لإثبات أن هذا النظام الجديد مكافئ للنظام الأصلي ، يجب إثبات التالي:
  • (اتساق)
  • (اكتمال)

الأُحاديات الشكل مقابل التعدد الشكلي

3 : Number

وفي هذا السياق، في حساب لامبدا البسيط الترتيب، الأنواع إما أن تكون ثوابت نوع ذرية أو أنواع دوال من الشكل . تُعرف هذه الأنواع بأنها أُحادية الشكل (monomorphic). أمثلة شائعة على ذلك هي الأنواع المستعملة في القيم الحسابية:

add 3 4 : Number

خوارزمية الاستنتاج

من جهة ثانية، الآن بعد أن أصبح نظام الاستنتاج في هندلي–ميلنر متاحًا، يمكن تقديم خوارزمية والتحقق من صحتها فيما يتعلق بالقواعد. وبديلًا عن ذلك، قد يكون من الممكن اشتقاقها من خلال إمعان النظر في كيفية تفاعل القواعد وتشكُّل البراهين. يتم ذلك في ما تبقى من هذه المقالة بالتركيز على القرارات الممكن اتخاذها أثناء إثبات النوع.

العواقب

يُمسّ المنطق والاتساق، لأن النمط يصبح مُسكنًا.

وفي هذا السياق، يتم إبطال خاصية التطبيع القوي، لأنه يمكن صياغة عبارات غير منتهية.

رغم أن ما سبق يبدو مباشرًا، إلا أن له ثمنًا.

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

let id = λ x . x

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

in ... (id 3) ... (id "text") ...

وإلا

  • إذا كان على الأقل أحد ta أو tb متغير نوع فإننا
  • نقوم بـ union(ta, tb)
  • وإلا

التعدد الشكلي مع let

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

إضافةً إلى ذلك، عند توسيع استدلال النوع في حساب لامبدا بسيط الترتيب ليشمل التعدد الشكلي، يجب اتخاذ قرار حول ما إذا كان يُسمح بإسناد نوع متعدد الشكل ليس فقط كتعبير، بل كذلك كنوع لمتغير مرتبط بواسطة λ. وهذا من شأنه أن يسمح بإسناد النوع العام لدالة الهوية إلى المتغير 'id' في:

كذلك، بدلًا من ذلك، يميز النظام بين المتغيرات المرتبطة مباشرة بتعبير "let-bound variables"، والمتغيرات العامة المرتبطة بـλ، ويسمح فقط للنوع المتعدد الشكل بأن يُسند إلى الأولى. وهذا يؤدي إلى ما يسمى بـالتعدد الشكلي باستخدام let "let-polymorphism"، حيث تأخذ الحالة السابقة الشكل التالي:

(λ id . ... (id 3) ... (id "text") ... ) (λ x . x)

الاستبدال في السياقات النوعية

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

وعلى صعيد آخر، خلافًا لقاعدة التخصيص، فإن هذه ليست جزءًا من التعريف الرسمي، بل هي — مثل التكميم الكلي الضمني — **نتيجة** لقواعد الأنواع التي سيتم تعريفها لاحقًا.

ومن ناحية أخرى، يمكن توسيع علاقة ترتيب الأنواع المحددة أعلاه لتشمل **السياقات النوعية (typings)**، لأن التكميم الكلي الضمني في السياقات يتيح الاستبدال المتسق:

  • سيناقش هذا المقال أربع مجموعات مختلفة من قواعد الأنواع:
  • النظام الإعلاني (Declarative system)
  • النظام الصياغي (Syntactic system)
  • الخوارزمية J
  • الخوارزمية W

التعددية الشكلية في ليت

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

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

إضافةً إلى ذلك، ونتيجة لهذا التنظيم، لا يمكن إعطاء نوع للتعبير ، لأن المعامل في موضع أحادي النوع، بينما التعبير يحمل النوع ، لأن تم تعريفه داخل تعبير let ويُعامل على أنه متعدد الأشكال نتيجة لذلك.

نظام الاستنتاج

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

كذلك، يُستعمل نحو نظام هندلي-ميلنر (HM) كأساس لبنية قاعدة الاستدلال التي تشكل جسم نظام شكلي، وذلك باستخدام الكتابات النوعية كأحكام. كل قاعدة من القواعد تُحدد ما النتيجة التي يمكن استخلاصها من مقدمات معينة. فضلًا عن الأحكام، يمكن استخدام بعض الشروط الإضافية المُقدمة أعلاه كمقدمات كذلك.

id ≡ λx . x

علاوةً على ذلك، والتي تُرجع ببساطة القيمة التي تُطبّق عليها. وهناك أمثلة أقل بساطة تشمل الأنواع البارامترية مثل القائمة.

cons : forall a . a -> List a -> List a

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

الأنواع الأحادية

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

ومن ناحية أخرى، من أمثلة الأنواع الأحادية أنواع البيانات الأولية مثل أو ، والأنواع المُعلَّمة (البارامترية) مثل . النوع الأخير مثال على تطبيق دوال نوعية مثل تلك الموجودة في المجموعة:

ومن ناحية أخرى، يُعتبر نوعان أحاديان متساويين إذا كانت عباراتهما متطابقة تماماً.

وفي السياق ذاته، الأنواع الأحادية تشير دائماً إلى نوع معين. يُمثّل النوع الأحادي صرفياً كحد.

،

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

الخوارزمية J

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

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

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

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

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

الخوارزمية W

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

ومن جهة أخرى، مع أن الخوارزمية W تُعتبر عادةً "الخوارزمية" الرسمية في نظام هندرسون-ميلنر، وغالبًا ما تُعرض مباشرة بعد نظام القواعد في الأدبيات، إلا أن ميلنر وصف الغرض منها في الصفحة 369 كما يلي:

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

وفي السياق ذاته، كما هي، فإن W ليست خوارزمية فعالة حقًا؛ إذ تُطبق الاستبدالات كثيرًا جدًا. لقد صيغت لتسهيل إثبات الصحة. وسنقدم الآن خوارزمية أبسط (الخوارزمية J) تحاكي W بطريقة دقيقة.

التصنيف الفرعي

من جهة ثانية، لذلك، بُذل جهد كبير لتبسيط مثل هذه المخططات والقيود باستخدام تقنيات مشابهة لتبسيط الأتمتة المنتهية غير الحتمية (NFA)،

وهو أمر مفيد في حال وجود أنواع استنتاجية متكررة.

من جانب آخر، مثلًا: ∀α. (α ≤ T) ⇒ α → α، حيث α ≤ T هو قيد على متغير النوع α.

كذلك، من السهل إلى حد ما تجميع ونشر قيود التصنيف الفرعي (على عكس قيود تساوي الأنواع)، مما يجعل القيود الناتجة جزءًا من مخططات الأنواع المستنتجة،

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

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

التعريفات العودية

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

nil' : List Number

علاوةً على ذلك، بشكل عام، تُعتبر الأنواع متعددة الأشكال إذا احتوت على متغيرات نوع، بينما تكون أُحادية الشكل إذا لم تحتوِ عليها.

كذلك، على عكس أنظمة الأنواع المستعملة في لغات مثل باسكال (1970) وسي (1972)، والتي تدعم فقط الأنواع الأُحادية، فإن نظام هندلي–ميلنر صُمم مع التركيز على التعدد الشكلي البارامتري. أما خلفاء هذه اللغات، مثل سي++ (1985)، فقد ركزوا على أنواع مختلفة من التعدد الشكلي، ولا سيما تعددية الأشكال (علم الحاسوب) المرتبطة بـالبرمجة كائنية التوجه. وعلى الرغم من أن التوريث (subtyping) غير متوافق مع نظام HM، إلا أن نوعًا من التحميل الزائد المنظم متاح في نظام الأنواع المعتمد على HM في لغة هاسكل.

add : Number -> Number -> Number

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

السياق والإسناد

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

درجات الحرية في اختيار القواعد

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

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

المقدمة

في هذا الإطار، يرجع الأصل إلى خوارزمية استدلال النوع لحساب لامبدا البسيط التي صاغها هاسكل كاري وروبرت فايس عام 1958.

علاوةً على ذلك، في سنة 1969، قام ج. روجر هندلي بتوسيع هذا العمل وأثبت أن خوارزميتهم تستنتج دائمًا النوع الأعمّ.

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

في هذا الإطار، وفي عام 1982، أثبت لويس داماس أخيرًا أن خوارزمية ميلنر كاملة، ووسّعها لتدعم الأنظمة التي تحتوي على مراجع متعددة الأشكال .

في هذا الإطار، وفي عام 1978، قدم روبن ميلنر — بشكل مستقل عن عمل هندلي — خوارزمية مكافئة تُعرف بالخوارزمية W.

الأنواع من المرتبة الأعلى

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

وفي السياق ذاته، لكن للأسف، فإن التوحيد لم يعد قابلاً للحسم في وجود الأنواع الفوقية (meta types)، مما يجعل استدلال الأنواع مستحيلًا ضمن هذا القدر من العمومية.

كذلك، وتتوفر امتدادات لغوية تُوسّع من مفهوم الأصناف لمحاكاة ميزات نظام الأنواع المعتمدة على القيم.

تقدم لغة هاسكل مستوى أعلى واحد يُسمى الصنف.

ومن ناحية أخرى، فضلًا عن ذلك، فإن افتراض وجود نوع "لكل الأنواع" يتضمن نفسه كنوع يؤدي إلى مفارقة، كما هو الحال في "مجموعة كل المجموعات"،

علاوةً على ذلك، تُستعمل الأنواع من المرتبة الأعلى لإنشاء نظام أنواع أكثر تعبيرًا ومرونة.

كذلك، تتضمن التعددية الشكلية البارامترية أن تُمرَّر الأنواع نفسها كمعاملات كما لو كانت قيماً حقيقية.

ويُعبَّر عن ذلك رمزيًا بـ .

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

وفي هذا السياق، فمثلًا، يُنظر إلى مُنشئ نوع القوائم كدالة تأخذ نوعًا (نوع عناصر القائمة) وتُنتج نوعًا آخر (نوع القائمة نفسها)؛

لذلك لا بد من التقدم بخطوات عبر مستويات من التجريد.

إضافةً إلى ذلك، ويُمرر النوع كوسيط إلى الدوال العادية، وكذلك إلى "دوال أنواع" كما هو الحال في الثوابت النوعية "البارامترية"، مما يثير التساؤل حول كيفية وضع نظام نوعي أكثر دقة للأنواع نفسها.

التحميل الزائد

وفي السياق ذاته، في هذا المثال، النوع a ليس فقط تعدديًا، بل مقيَّد كذلك بأن يكون مثيلًا للصنف النمطي Ord، الذي يوفر معاملات الترتيب < و>= المستعملة في جسم الدالة. يتم تمرير التطبيقات الصحيحة لهذه المعاملات إلى دالة الترتيب السريع كوسائط إضافية حالما تُستعمل الدالة مع أنواع أكثر تحديدًا توفر تطبيقًا واحدًا للدالة المحملة تحميلًا زائدًا.

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

quickSort :: Ord a => [a] -> [a]

وعلى صعيد آخر، التحميل الزائد يعني إمكانية تعريف دوال مختلفة تُستعمل بنفس الاسم. توفر أغلب لغات البرمجة تحميلًا زائدًا على الأقل للعمليات الحسابية المدمجة (+، <، وغيرها)، لتسمح للمبرمج بكتابة تعبيرات حسابية بنفس الشكل حتى مع اختلاف الأنواع العددية مثل int أو real. وبسبب الحاجة للتحويل الضمني عند خلط هذه الأنواع المختلفة في نفس التعبير، يُدمج التحميل الزائد لهذه العمليات غالبًا في اللغة نفسها. في بعض اللغات مثل C++، تم تعميم هذه الميزة وإتاحتها للمستعمل.

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

ومن ناحية أخرى، يستعمل مثال الترتيب السريع المذكور في المقدمة التحميل الزائد في علاقات الترتيب، مع التعليق النمطي التالي في هاسكل:

نظرة عامة

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

تمضي بقية هذه المقالة على النحو التالي:

من جانب آخر، وبما أن بقاء توافق الخوارزمية J مع نظام الاستنتاج الأصلي غير محسوم، يتم تقديم تنفيذ أقل كفاءة (الخوارزمية W)، ويُلمح إلى استخدامه في إثبات منطقي.

ومن جهة أخرى، يُستعمل نفس الوصف لنظام الاستنتاج في جميع المراحل، بما في ذلك عند عرض الخوارزميتين، لجعل الأشكال المختلفة التي يُقدّم بها منهج HM قابلة للمقارنة المباشرة.

وأخيرًا، تُناقش مواضيع إضافية ذات صلة بالخوارزمية.

ومن جهة أخرى، يُعرّف نظام الأنواع في هندلي–ميلنر (HM). ويتم ذلك من خلال وصف نظام استنتاج يحدد بدقة ما إذا كانت التعبيرات تملك نوعًا معينًا، وإن كانت كذلك، فما هو هذا النوع.

البنية الصرفية

ومن ناحية أخرى، التعبيرات التي تُسند لها الأنواع هي نفسها تعبيرات تكامل لامدا مع توسيع يتضمن تعبير let كما هو موضح في الجدول المجاور. يمكن استخدام الأقواس لإزالة الغموض من تعبير ما. التطبيق يرتبط يسارياً ويرتبط بشكل أقوى من التجريد أو بنية let-in.

في هذا الإطار، تنقسم الأنواع من الناحية الصرفية إلى مجموعتين: الأنواع الأحادية والأنواع المتعددة.

لاحقًا، ادعى بارّو

وفي هذا الصدد، أن هذا الطرح الجبري يعادل خوارزمية بسيطة نسبيًا تُشبه خوارزمية W،

وأن استخدام أنواع الاتحاد والتقاطع لم يكن ضروريًا.

وفي السياق ذاته، نتيجة لذلك، فإن أنظمة الأنواع التي تدعم التصنيف الفرعي والتي تمكّن البرمجة الكائنية، مثل نظام F-Sub الخاص بلوقا كارديلي ،

  • إلا أنه يمتاز بإمكانية دمجه بسهولة مع خوارزميات هندلي-ميليك القياسية.
  • ملاحظات
  • المراجع

من جهة ثانية، يمكن استخدام تعدد الأشكال حسب الصف كبديل للتصنيف الفرعي لدعم ميزات لغوية مثل السجلات البنيوية.

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

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

لا تدعم استدلال الأنواع بأسلوب هندلي-ميليك.

ولوجود ميزات مثل تعدد الأشكال المحدود بـ F.

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

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

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