صورة عامة للتحقق الرسمي في البرامج

Question

أحاول تناول صورة عامة لتعزيز حالة التحقق من البرامج الرسمية، وأواجه قليلا من المتاعب. للسياق، أتيت من خلفية الرياضيات في الغالب. أنا على دراية تماما بحالة مفيدة نظرية آلية ومساعدات إثبات فيما يتعلق باستخدامها لإثبات تصريحات رياضية تشكيلها بشكل جيد (مثل COQ، Isabelle، Slex، إلخ). ما أواجه مشكلة فهم هو ما يحدث مع "الأساليب الرسمية" في تطبيقات CS العملية.

لقد وجدت أن الشركات مثل Microsoft و AWS استخدمت TLA + ك "طريقة رسمية" في تطوير البرامج بشكل كبير إلى حد ما. ولكن عندما بدأت في قراءة كتاب واين العملي TLA + $ مع إدخالات بين 1 و $ n $ للحصول على بعض $ n $ ، أي نحن فقط نتحقق من حالات كثيرة وثيقة القول إنها يجب أن تعمل الخوارزمية بشكل عام. هذا لا يبدو مثيرا للاهتمام بشكل خاص؛ مجرد مثال على اختبار الوحدة الصارم بشكل خاص. لا سيما أنه ليس دليلا رسميا على صحة.

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

هل يمكن لشخص ما يحاول مسح الارتباك الخاص بي؟

Answer 1

برنامج مثبت مسبقا هو برنامج مثبت رسميا بغض النظر عن أي لغة قيد التشغيل. لمجرد أن البرنامج مكتوب في COQ وربما المستخرجة إلى Ocaml أو Haskell، بدلا من المكتوبة في لغة أكثر إشرافا" مثل C ++ أو Java، لا يجعلها أقل من البرنامج.

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

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

ل C، واحدة من المجموعات الفرعية الكبيرة الرئيسية مع نموذج رسمي هو Compruct C، لغة CompCert . CompCert عبارة عن عبارة عن عبارة عن عبارة عن عبارة عن عبارة عن عبارة عن عبارة عن عبارة عن عبارة عن عبارة عن عبارة عن عبارة عن عبارة عن عبارة عن عبارة عن عبارة عن عبارة عن عبارة عن مبرر تم التحقق منه رسميا (مكتوبا في COQ)، لذلك إذا ثبتت خاصية برنامج C، فيمكنك بالإضافة إلى ذلك الحصول على دليل على رمز الجهاز الذي تم إنشاؤه. compruct c مجموعة فرعية كبيرة جدا من C99، ولكن الرسمية تستبعد معظم المعيار مكتبة وبعض عمليات التشويش للغة.

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

من الشائع إلى حد ما أن يكون البرنامج النهائي غير مكتوب يدويا، ولكن استخراج ميكانيكيا من لغة أعلى مستوى. على سبيل المثال، كتابة COQ التي يتم استخراجها إلى Ocaml، أو كتابة f * والتي يتم استخراجها إلى C. ولكن يتعكس النهج المعاكس كذلك، على سبيل المثال، على سبيل المثال كتابة ("Tame") C، قم بتسليمها بممتلكات الوظائف وتقسيمات التعليمات البرمجية الأخرى، واستخدام Frama-C لإثبات تلك الخصائص (والخاصية الضمنية التي لا يوجد بها برنامج C أي سلوك غير محدد).

عندما يكون لديك دلالات رسمية لغة برمجة وسيلة للتعبير عن خصائص البرامج، تثبت هذه الخصائص هي نظرية رياضية. عادة لا تنطوي هذه النظرية على أي رياضيات معقدة مثل حساب التفاضل والتكامل (ما لم يتم إحضارها بواسطة مجال التطبيق، مثل تتبع حركة كائن مادي)، لكن من الصعب إثباتها لأنها تنطوي على صيغ كبيرة جدا، ويحتوي على بيانات حسابية ( $ x ^ n + y ^ n= z ^ n $ ليست معادلة معقدة، ولكن حلها غير أساسي!). إنها من المستحيل نظريا كتابة برنامج يمكن أن يثبت خاصية دلالات غير تافهة لجميع البرامج ، ومن المستحيل عمليا كتابة برنامج يمكن أن يثبت العديد من الخصائص المثيرة للاهتمام للبرامج النموذجية. يتضمن التحقق الرسمي مزيجا من كسر المشكلة في خطوات صغيرة بما فيه الكفاية (كتابة وظائف صغيرة وتقسم خصائص دقيقة كافية لتلك الوظائف)، وجود أداة تثبت تلقائيا بعض تلك الخصائص (مثل

ك SAT Solver منطق الاقتراح)، وبعد أن يكتب البشر البراهين حيث يمكن الكمبيوتر 'T تفعل ذلك (ولكن الكمبيوتر سوف يتحقق من دليل الإنسان). يدخل المساعدين مثل COQ و ISABELLE لهذه الخطوة الأخيرة.

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

إذا كنا فقط تحقق من خوارزمية الفرز في قوائم الطول

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