هل هناك أي لغات حقيقية يمكن إثباتها؟ (سكالا؟)

Question

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

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

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

لقد سمعت أشياء مثيرة للاهتمام حول قابلية اختبار اللغات الوظيفية مثل سكالا.

كبرنامج المهندسون ما هي الخيارات التي لدينا؟

Answer 1

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

---

انطباعي وتجربتي هو أن هناك تقنيتان لكتابة البرامج الصحيحة:

• التقنية 1: اكتب البرنامج بلغة تشعر بالراحة معها (C ، C ++ أو Java على سبيل المثال). خذ مواصفات رسمية لهذه اللغة ، وأثبت برنامجك الصحيح.

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

• التقنية 2: اكتب البرنامج بلغة أكثر حرجًا قليلاً (بعض مجموعة فرعية من ADA أو إصدار تعديل من OCAML على سبيل المثال) واكتب دليل الصواب على طول الطريق. هنا البرمجة وإثبات يسير جنبا إلى جنب. البرمجة في COQ حتى تعادلهم تماما! (انظر المراسلات الكاري هارد)

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

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

فيما يلي بعض الأمثلة الأخرى عن الأساليب الرسمية. إذا كان "العالم الحقيقي" أم لا ، يعتمد على من تسأل :-)

• PROVER نظرية COQ: البرمجة مع COQ (تقنية 2)
• ESC/Java (التقنية 1 ، لا صوت ولا اكتمال رغم ذلك)
• المواصفات# (التقنية 1 ، لا صوت ولا اكتمال رغم ذلك)
• لماذا / كراكاتو (التقنية 2 ، على أساس جافا)

أنا أعرف فقط "واحد صحيح" لغة تطبيق الويب: أور. يضمن برنامج Ur-Program الذي "يمر عبر المترجم":

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

Answer 2

للإجابة على هذا السؤال ، تحتاج حقًا إلى تحديد ما تعنيه بـ "Diviber". كما أشار ريكي ، فإن أي لغة ذات نظام نوع هي لغة ذات نظام إثبات مدمج يتم تشغيله في كل مرة تقوم فيها بتجميع البرنامج. إن أنظمة الإثبات هذه دائمًا ما تكون عاجزًا للأسف - الإجابة على أسئلة مثل String ضد Int وتجنب أسئلة مثل "هل يتم فرز القائمة؟" -لكنها أنظمة دليل لا شيء.

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

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

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

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

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

Answer 3

تثبت اللغات المكتوبة عدم وجود فئات معينة من الخطأ. كلما زاد نظام النوع ، زادت الأخطاء التي يمكن أن تثبت عدم وجود.

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

Answer 4

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

• هناك لغات مفهومة جيدًا مع إمكانية إثبات استخدامها اليوم ؛ LISP عبر ACL2 هو واحد ، وبالطبع مخطط لديه تعريف رسمي فهم جيد كذلك.

• حاول عدد من الأنظمة استخدام اللغات الوظيفية النقية ، أو اللغات النقية تقريبًا ، مثل Haskell. هناك القليل من الأساليب الرسمية التي تعمل في هاسكل.

• بالعودة إلى أكثر من 20 عامًا ، كان هناك شيء قصير الأجل لاستخدام لغة رسمية تم ترجمتها بدقة إلى لغة مجمعة. كانت بعض الأمثلة هي أن غرفة نظافة برمجيات IBM و ACL و Gypsy و Res Out of Compual Logic و John McHugh's وعملي في مجموعة جديرة بالثقة من C ، وعملي الخاص ببرمجة أنظمة C. كل هذا يحظى ببعض الاهتمام ، ولكن لم يجعل أي منهم الكثير موضع التنفيذ.

أعتقد أن السؤال المثير للاهتمام لطرحه هو ما هو الظروف الكافية للحصول على مقاربات رسمية موضع التنفيذ؟ أحب أن أسمع بعض الاقتراحات.

Answer 5

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

هذه هي قراءة ممتعة إذا كنت مهتمًا بلغات البرمجة الوظيفية ولغات البرمجة الوظيفية الخالصة.

Answer 6

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

لا تتوسع لغات "Problable" فقط لكتابة/قراءة قاعدة رمز المشروع الكبير ويبدو أنها تعمل فقط في حالات الاستخدام الصغيرة والمعزولة.

Answer 7

أنا متورط في لغتين يمكن أن يكونا. الأول هو اللغة المدعومة من قبل Perfect Developer ، نظام لتحديد SOTFware ، تحسينه وتوليد التعليمات البرمجية. تم استخدامه لبعض الأنظمة الكبيرة ، بما في ذلك PD نفسه ، ويتم تدريسه في عدد من الجامعات. اللغة الثانية التي يمكن أن أشارك فيها هي مجموعة فرعية يمكن إثباتها من MISRA-C ، انظر مدونة التحقق C/C ++ للمزيد من.

Answer 8

الدفع أوميغا.

هذه المقدمة يحتوي على تنفيذ غير مؤلم نسبيا لأشجار AVL مع دليل صواب شمل.

Answer 9

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

تحرير ===== أزال أفكاري غير الصحيحة حول ML "يمكن إثباتها".

Answer 10

تعريفي (المثير للجدل) لـ "العالم الحقيقي" في سياق التعليمات البرمجية التي تم تصحيحها على ما يرام هو:

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

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

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

Answer 11

ماذا عن إدريس و agda؟ العالم الحقيقي بما فيه الكفاية؟

كمثال جيد للحياة ، هناك مشروع يهدف إلى توفير مكتبة HTTP REST التي تم التحقق منها مكتوبة في AGDA ، تسمى Lemmachine: https://github.com/larrytheliquid/lemmachine