معنى وأهمية عبارة "لا يوجد تنفيذ إنهاء" في نظرية النوع

Question

في سياق مناقشة هاسكل https://stackoverflow.com/questions/62509788/the-intuition-behind-the-definition-of-the-co-reader-monad, ، قيل لي أن

لا يوجد تنفيذ إنهاء للنوع متعدد الأشكال $(e o a) o a$

وأنه لا يمكن أن يكون لدينا وظيفة من النوع $((e o a) o a) o e$ أو وظيفة من النوع $(ص \إلى س) \إلى س$, ، لأن هذه لن تكون "قابلة للتنفيذ".

تم تشكيل هذه الأنواع بشكل جيد في STLC، بمعنى أنه يمكننا بنائها باستخدام قواعد تكوين النوع.وأنا لا أفهم لماذا لا نستطيع تشكيل مصطلحات لامدا بهذا الشكل، مثل $\lambda c_ {((a o t) o t)}.\، ب_أ$, ، أو $\lambda p_{e o a}.\,b_a$.

إذن ما هي المشكلة؟على وجه التحديد، ما هو "إنهاء التنفيذ" في سياق اتفاقية STLC؟أعتقد أن هذا يرتبط بحقيقة ذلك $(e o \bot) o \bot$ لا يعادل بناءا ل $e$, ، ولكن سأكون ممتنًا لو تمكن شخص ما من توضيح ذلك لي.

Answer 1

أنت تستطيع دائماً تسكن نوعًا ما بواسطة متغير حر:نوع $\تاو$ يسكنها المتغير الحر $x_\تاو$.عندما يتحدث الناس عن "التنفيذ" من نوع ما فإنهم يقصدون أ مصطلح مغلق, ، أي واحد بدون متغيرات حرة.الأمثلة التي قدمتها تحتوي على متغيرات حرة، وهي $ب_ا$.

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

في $\لامدا$- حساب التفاضل والتكامل الممتد مع التعريفات العودية (مثل هاسكل) يمكننا أن نسكن كل نوع $\تاو$ مع مصطلح مغلق، على سبيل المثال في هاسكل النوع t يسكنها a معرف ك

a :: t
a = a

بمجرد أن يكون لدينا تعريفات متكررة، فمن السهل كتابة مصطلحات مغلقة لا تنتهي (أو ليس لها شكل عادي).