اكتب الاستدلال مع التحميل الزائد

Question

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

للحصول على مثال صغير، النظر في التعبير (x + y) + 1 أين x :: N | S, y :: a, + :: (N -> N -> N) | (S -> S -> S), 1 :: N. :: تمثل نوع من, ، و a | b يرمز إلى النوع a أو يكتب b.

الطريقة، كما أفترض، ستعمل الآن على استنتاج النوع، هي اجتياز شجرة بناء الجملة، وإرجاع قيد نوع لكل عقدة:

(x + y) + 1 => ((N & (N[a=N] | S[a=S])), (N & N) -> N) | ((S & (N[a=N] | S[a=S])), (S & N) -> S) => N[a=N]
  1         => N
  +         => (N -> N -> N) | (S -> S -> S)
  x + y     => ((N & (N | S)), (N & a) -> N) | ((S & (N | S)), (S & a) -> S) => N[a=N] | S[a=S]
    x       => N | S
    y       => a
    +       => (N -> N -> N) | (S -> S -> S)

a & b في هذا المثال يرمز إلى توحيد الأنواع a و b, [a=T, b=U] هي مجموعة من قيود المساواة لمتغيرات النوع.

كما هو متوقع، يتم استنتاج نوع الإرجاع للتعبير المعطى N[a=N], ، إنه N حيث متغير النوع a من المتوقع أن يكون N.

لذلك، قدم الاثنان تطبيقات لـ + المشغل أو العامل (N -> N -> N, S -> S -> S), N -> N -> N يجب أن تستخدم.في المثال المعطى، يتم استنتاج النوع الناتج، ولكن ليس نوع المشغل المحمل بشكل زائد.سؤالي هو ما إذا كان هناك نمط شائع يُستخدم لإبلاغ + عقدة في شجرة بناء الجملة للتنفيذ المستخدم.

Answer 1

يمكنك تنظيم استنتاج النوع على النحو التالي.

لنفترض أن بناء جملة الإدخال الخاص بك يحتوي على نوع Input.تحديد بناء جملة الإخراج Output لتكون مثل Input ولكن مع التعليقات التوضيحية الصريحة على كافة المتغيرات.سيكون لاستدلال النوع نوع

infer : Input -> List (Output * Type)

وهذا هو، نظرا لبعض المدخلات e, ، فإنه يقوم بإرجاع قائمة بالإجابات المحتملة.كل إجابة هي زوج (e', t) أين e' يكون e مع المتغيرات المشروحة حسب الأنواع، و t هو النوع المستنتج من e.

يمكنك رؤية هذا على أنه كل ما يحدث في الأحادية غير الحتمية.عندما تحتاج إلى استنتاج نوع المتغير x, ، تبحث عن أنواعها المحتملة S | T | ... وتفرع على كل واحد منهم.بهذه الطريقة لن تضطر إلى "إعادة" أية معلومات إلى التعبيرات الفرعية.بدلاً من ذلك، يأتي كل تعبير فرعي بالفعل مشروحًا بكل الطرق الممكنة.