ماذا يعني أن يتم كتابة اللغة بشكل ثابت؟

Question

أفهم أنه يعني أنه يمكن للمرء أن يكتب برنامجًا لإثبات أن برنامجًا مكتوبًا بلغة مكتوبة بشكل ثابت سيكون خاليًا من مجموعة فرعية (صغيرة) من العيوب.

مشكلتي في هذا على النحو التالي:

افترض أن لدينا لغتين كاملتين ، يُفترض أن A و B. A "نوع آمن" و "B" يفترض أن يكون. لنفترض أنني مُنحت برنامج L للتحقق من صحة أي برنامج مكتوب في A. ما الذي يمنعني من ترجمة أي برنامج مكتوب في B إلى A ، تطبيق L. إذا كان P يترجم من A إلى B ، فلماذا لا PL مدقق نوع صالح لأي برنامج مكتوب في ب؟

لقد تدربت في الجبر وأنا فقط بدأت في دراسة CS ، لذلك قد يكون هناك سبب واضح لأن هذا لا يعمل ، لكنني أود أن أعرف. هذا الشيء "نوع السلامة" كله قد شم رائحة مريب بالنسبة لي لفترة من الوقت.

Answer 1

اسمحوا لـ A أن تكون لغتك الكاملة التي من المفترض أن تتم كتابتها بشكل ثابت ودع "هي اللغة التي تحصل عليها من A عند إزالة النوع الذي تقوم بفحص النوع (ولكن ليس التعليقات التوضيحية لأنها تخدم أيضًا أغراض أخرى). ستكون البرامج المقبولة لـ A مجموعة فرعية من البرامج المقبولة لـ A '. لذلك على وجه الخصوص ، سيكون "turing-Complete.

بالنظر إلى المترجم الخاص بك من B إلى A (والعكس صحيح). ماذا يفترض ان تفعل؟ يمكن أن تفعل واحدة من شيئين:

1. أولاً ، يمكن أن يترجم كل برنامج y من B إلى برنامج A. في هذه الحالة ، ستعود LPY دائمًا بشكل صحيح لأن برامج A يتم كتابتها بحكم تعريفها بشكل صحيح.

2. ثانياً ، يمكن لـ P ترجمة كل برنامج y من B إلى برنامج من A '. في هذه الحالة ، ستعود LPY بشكل صحيح إذا صادف أن يكون PY برنامجًا من A و False إن لم يكن.

نظرًا لأن الحالة الأولى لا تسفر عن أي شيء مثير للاهتمام ، فلنتمسك بالحالة الثانية ، وهو ما تعنيه على الأرجح. هل تخبرنا الوظيفة LP على برامج B أي شيء مثير للاهتمام حول برامج B؟ أنا أقول لا ، لأنه ليس ثابتًا في ظل تغيير P. لأن A Is A Complete ، حتى في الحالة الثانية يمكن اختيار P بحيث تحدث صورتها في A. ثم ستكون LP صحيحة باستمرار. من ناحية أخرى ، يمكن اختيار P بحيث يتم تعيين بعض البرامج على تكملة A في A '. في هذه الحالة ، كان LP يبصق كاذبًا لبعض البرامج (ربما كل) من برامج B. كما يمكنك أن ترى ، لا تحصل على أي شيء يعتمد فقط على Y.

يمكنني أيضًا وضعه بشكل أكثر رياضيا بالطريقة التالية: هناك فئة C من لغات البرمجة التي تكون أشياءها هي لغات البرمجة والتي تعتبر مورفيسماتها مترجمين من لغة برمجة إلى أخرى. على وجه الخصوص إذا كان هناك مورفسم p: x -> y ، فإن y على الأقل معبرة مثل X. بين كل زوج من اللغات الكاملة turing هناك أشكال في كلا الاتجاهين. لكل كائن x من C (أي لكل لغة برمجة) لدينا مجموعة مرتبطة ، على سبيل المثال {x} (تدوين سيئ ، أعرف) لتلك الوظائف المحددة جزئيًا والتي يمكن حسابها بواسطة برامج X. كل التشكل p: x - > y ثم يحفز التضمين {x} -> {y} من مجموعات. دعنا نؤسس رسميًا كل هذه الأشكال p: x -> y التي تحفز الهوية {x} -> {y}. سأدعو الفئة الناتجة (والتي هي ، من الناحية الرياضية ، توطين C) بواسطة C '. الآن التضمين A -> A "هو التشكل في C". ومع ذلك ، لا يتم الحفاظ عليها تحت الأوتوماتيكية لـ A '، وهذا هو التشكل A -> A "ليس ثابتًا لـ" في C ". بمعنى آخر: من وجهة النظر المجردة هذه ، فإن السمة "المكتوبة بشكل ثابت" غير قابلة للتعريف ويمكن أن تكون مرتبطة بشكل تعسفي باللغة.

لجعل وجهة نظري أكثر وضوحًا ، يمكنك أيضًا التفكير في C 'باعتبارها فئة الأشكال الهندسية ، على سبيل المثال ، في الفضاء ثلاثي الأبعاد مع الاقتراحات الإقليدية مثل التشكل. A 'و B هما شكلان هندسيان و P و Q هما حركات إقليدية تجلب B إلى "والعكس صحيح. على سبيل المثال ، يمكن أن يكون A 'و B كرتين. الآن دعونا نصلح نقطة على "، والتي يجب أن تقف للمجموعة الفرعية A من A. دعنا نسمي هذه النقطة "مطبوعة بشكل ثابت". نريد أن نعرف ما إذا كانت نقطة B قد كتبت بشكل ثابت. لذلك نحن نأخذ مثل هذه النقطة Y ، خريطةها عبر p إلى "واختبار ، سواء كانت نقطة ملحوظة على A '. كما يمكن للمرء أن يرى بسهولة ، فإن هذا يعتمد على الخريطة المختارة P أو ، وبعبارة أخرى: لا يتم الحفاظ على نقطة ملحوظة على المجال من خلال الحركات الإقليدية التي تخطط للمجال على نفسه) من هذا المجال.

Answer 2

لو تستطيع ان تترجم كل B '(برنامج مكتوب في ب) إلى ما يعادل A' (وهو صحيح إذا كان B ') ، فإن اللغة B تتمتع بنفس القدر من "السلامة النوعية" مثل اللغة A (بالمعنى النظري ، بالطبع ؛-) - هذا في الأساس يعني أن B هو أنه يمكنك القيام باستنتاج مثالي من النوع. لكن هذا محدود للغاية بالنسبة للغة الديناميكية - على سبيل المثال ، ضع في اعتبارك:

if userinput() = 'bah':
    thefun(23)
else:
    thefun('gotcha')

أين thefun (دعنا نفترض) هو Typesafe للحجة int ، ولكن ليس لحجة str. الآن - كيف تترجم هذا إلى اللغة A في المقام الأول...؟

Answer 3

هناك طريقة أخرى لجعل نفس النقطة التي تم توضيحها هي أن سؤالك يشكل دليلًا على التناقض على أنه أيضًا:

• لا يمكن تعيين A إلى ب
• نوع السلامة ليست خاصية معجمية للغة

او كلاهما. يقول حدسي أن هذا الأخير هو على الأرجح النقطة الشائكة: هذه السلامة من النوع هي خاصية ألوان فنية.

Answer 4

لا يوجد شيء "مريب" حول هذا الموضوع. ؛)

مجموعة اللغات المكتملة التي تكون آمنة من النوع فيما يتعلق بأي غير تافهة [1] اكتب النظام ر هو حازم مجموعة فرعية من اللغات الكاملة. على هذا النحو ، في الحالة العامة ، لا مترجم ص^-1 من عند ب ل أ موجود ؛ لذلك ، لا أي مترجم-النُطَف المَنَويّة-type-checker LP^-1.

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

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

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

[1] من خلال غير التافعي ، أعني أن كل التعبيرات الممكنة غير محتملة.

Answer 5

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

Answer 6

اسمحوا لي أن أجيب على هذا في الاتجاه الآخر:

هناك نوعان مختلفان من البرمجة "الديناميكية".

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

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