ما هي الشكليات لإثبات العبارات حول تفرد الوظائف بتوقيعات معينة

Question

لنفترض أنني أريد وظيفة مثل

f: ((A, B) -> C) -> A -> B -> C

العبارة التي رأيتها كثيرًا هي أن f لديها تطبيق واحد فقط، وهو "وظيفة الكاري"، أي. g => a => b => g(a, b)

في ظاهر الأمر، لا يبدو أن هذا صحيحًا في الواقع، يمكنني دائمًا تعريف f على أنه يتصرف بشكل مختلف عن هذا في حالات خاصة، على سبيل المثال.أستطيع أن أقول أنه هو g => a => b => g(a, b) إلا عندما A = B ثم أقوم بتعريفه على أنه g => a => b => g(b, a).

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

أود أن أعرف الشكلية الصحيحة التي يمكن من خلالها إثبات أقوال مثل ما سبق.

أعتقد أنني أظن أنها نظرية الفئة؟ما ورد أعلاه يشبه إلى حد ما فكرة التحول الطبيعي، لكنني لا أرى التفاصيل حقًا.

Answer 1

أنا متأكد من أن هناك صلة بنظرية الفئة، ولكن يمكنك فعل ذلك باستخدام (ما أعتبره) أداة أبسط:البارامترية.

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

وهذا يمنع بالضبط تنفيذ "الحالة الخاصة" الذي تصفه في سؤالك.ومن الجدير بالذكر أيضًا أن هذه التطبيقات كلها تمديديا متساوي:قد تبدو مختلفة ولكنها تنتج نتائج متساوية لمدخلات متساوية.على سبيل المثاليمكنك استبدال أي مصطلح $t$ مع $(\lambda x \ldotp x) t $ والحصول على وظيفة مماثلة.

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

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

يمكنك في الواقع إنشاء نظريات مجانية في http://free-theorems.nomeata.de/, ، على الرغم من أن الأمر قد يستغرق بعض التدليك للحصول على معلومات مفيدة من النظريات التي يقدمونها هناك.

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