إثبات صحة مُصرِّف
هذا مشروع تخرج. بعد إكمال هذا القسم، سيكون بين يديك مُصرِّف مصغّر، ونظرية تحقق منها Lean: لأي تعبير حسابي، فإن النتيجة التي تحسبها التعليمات المُصرَّفة هي نفسها النتيجة المباشرة لحساب هذا التعبير.
ليس "اختبرنا تعابير كثيرة وكلها صحيحة"، بل جميعها.
كل ما يُستخدم هنا هو ما تعلمته سابقًا: تعريف الدوال، والاستقراء على البُنى، والبحث عن مبرهنات عند التعثر.
قبل البدء
- تعلمتالاستقراء على القوائم، وتعرف ما هي المبرهنة
- أنشئ ملفًا جديدًا
Compiler.lean، واكتب الشيفرة التالية فيه بالترتيب
الخطوة 1: تعريف التعابير الحسابية، وما "ينبغي" أن تساوي قيمته
التعبير الحسابي إما أن يكون عددًا، أو جمع تعبيرين، أو ضرب تعبيرين:
inductive Expr where
| num : Nat → Expr
| add : Expr → Expr → Expr
| mul : Expr → Expr → Exprinductive يُعرِّف نوع بيانات جديدًا، مع سرد جميع أشكاله الممكنة.
حساب قيمة تعبير حسابي مباشرةً:
def eval : Expr → Nat
| .num n => n
| .add a b => eval a + eval b
| .mul a b => eval a * eval beval هو تعريف "الإجابة الصحيحة". صحة المُصرِّف لاحقًا تُقاس بالنسبة إليه.
جرّب 2 + 3 × 4:
def demo : Expr := .add (.num 2) (.mul (.num 3) (.num 4))
#eval eval demo14eval demoيحسب 14
الخطوة 2: تعريف آلة لا تتعرف إلا على ثلاث تعليمات
لهذه الآلة مكدس، أي كومة من الأعداد، لا يمكن الوضع فيها أو الأخذ منها إلا من الأعلى. التعليمات ثلاث:
inductive Instr where
| push : Nat → Instr
| add
| mulpush n: ضع n في أعلى المكدس.add: خذ العددين في أعلى المكدس، وضع مجموعهما مكانهما.mul: خذ العددين في أعلى المكدس، وضع حاصل ضربهما مكانهما.
تنفيذ سلسلة من التعليمات:
def run : List Instr → List Nat → List Nat
| [], stack => stack
| .push n :: rest, stack => run rest (n :: stack)
| .add :: rest, b :: a :: stack => run rest ((a + b) :: stack)
| .mul :: rest, b :: a :: stack => run rest ((a * b) :: stack)
| _ :: rest, stack => run rest stackrun 指令 栈 يُرجع المكدس بعد انتهاء التنفيذ. السطر الأخير يعالج حالة عدم وجود عددين كافيين في المكدس: تخطي هذه التعليمة.
Instrوrunبلا أخطاء
الخطوة 3: كتابة المُصرِّف
ترجمة التعبير الحسابي إلى تعليمات. العدد هو ببساطة push؛ والجمع هو حساب الجانب الأيسر أولًا، ثم الأيمن، وأخيرًا add:
def compile : Expr → List Instr
| .num n => [.push n]
| .add a b => compile a ++ compile b ++ [.add]
| .mul a b => compile a ++ compile b ++ [.mul]صرِّف التعبير السابق وشغّله على مكدس فارغ:
#eval run (compile demo) [][14]أعلى المكدس هو 14، وهو نفس eval demo. لكن هذا تعبير واحد فقط.
run (compile demo) []يعطي[14]
الخطوة 4: كتابة العبارة المطلوب إثباتها
"المُصرِّف صحيح" يجب أولًا توضيح معناه:
theorem compile_correct (e : Expr) (s : List Nat) :
run (compile e) s = eval e :: sتُقرأ كالتالي: لأي تعبير حسابي e وأي مكدس ابتدائي s، فإن تنفيذ التعليمات المُصرَّفة من e يُنتج مكدسًا فيه فوق s عدد إضافي واحد، وهذا العدد هو بالضبط eval e.
هذه الخطوة أهم من الإثبات نفسه. قلنا في القسم الأول: ما يتحقق منه Lean هو العبارة التي تكتبها. إذا كُتبت هذه العبارة بشكل صحيح، صار للإثبات معنى.
لاحظ أنها تقول "لأي مكدس ابتدائي s"، ولم تقل المكدس الفارغ فقط. السبب سيظهر بعد قليل.
- أستطيع أن أشرح بكلماتي ما تدّعيه
compile_correct
الخطوة 5: إثبات المُعين أولًا
نتيجة compile هي عدة مقاطع من التعليمات مُسلسلة معًا. للتفكير فيها، يجب أولًا معرفة: تشغيل مقطعين من التعليمات مُسلسلين معًا يساوي تشغيل المقطع الأول، ثم تشغيل المقطع الثاني على المكدس الذي تركه.
theorem run_append (p q : List Instr) (s : List Nat) :
run (p ++ q) s = run q (run p s) := by
induction p generalizing s with
| nil =>
rfl
| cons i rest ih =>
cases i <;> rcases s with _ | ⟨b, _ | ⟨a, s⟩⟩ <;> simp [run, ih]هذا استقراء على قائمة التعليمات p. هناك أمران جديدان:
generalizing s: يجعل فرضية الاستقراء صحيحة لأي مكدس. المكدس يتغير مع كل تعليمة تُنفَّذ، ففرضية تصح لمكدس ثابت واحد لا تُفيد. وهذا أيضًا سبب كتابة "لأي مكدس s" في نظرية الخطوة السابقة.- السطر الأخير: بحسب نوع التعليمة الأولى، ووجود صفر أو واحد أو اثنين على الأقل من الأعداد في المكدس، تُسرد جميع الحالات، وتُسلَّم كل حالة إلى
simp. معنى<;>هو "نفِّذ الخطوة التالية على كل هدف ناتج".
لا يلزم فهم هذا السطر بالكامل الآن. يكفي أن تعرف أنه يقوم بـ"تقسيم الحالات، وتبسيط كل واحدة".
run_appendنجح
الخطوة 6: إثبات صحة المُصرِّف
استقراء على شكل التعبير الحسابي. للتعبير ثلاثة أشكال، فالحالات ثلاث؛ وللجمع والضرب تعبيران فرعيان لكل منهما، فلكل منهما فرضيتا استقراء. مشِ بنفسك عبرها:
theorem compile_correct (e : Expr) (s : List Nat) : run (compile e) s = eval e :: s := by
induction e generalizing s with
| num n =>
rfl
| add a b iha ihb =>
simp [compile, run_append, iha, ihb, run, eval]
| mul a b iha ihb =>
simp [compile, run_append, iha, ihb, run, eval]
اكتب في الملف:
theorem compile_correct (e : Expr) (s : List Nat) :
run (compile e) s = eval e :: s := by
induction e generalizing s with
| num n =>
rfl
| add a b iha ihb =>
simp [compile, run_append, iha, ihb, run, eval]
| mul a b iha ihb =>
simp [compile, run_append, iha, ihb, run, eval]يجب أن ترى: لا أخطاء.
ما يحدث في فرع الجمع: compile يتوسّع إلى ثلاث مقاطع من التعليمات؛ run_append يفكّ "تشغيل ثلاثة مقاطع" إلى تشغيل مقطعًا مقطعًا؛ iha يقول إنه بعد تشغيل المقطع الأول زاد قمة المكدس بمقدار eval a، وihb يقول إنه بعد تشغيل المقطع الثاني زادت بمقدار eval b؛ وأخيرًا add يجمعهما معًا، وهو بالضبط eval (.add a b).
compile_correctنجح
الخطوة 7: اكتب عمدًا مُصرِّفًا خاطئًا
للتحقق من الفائدة، انظر هل يستطيع اكتشاف الخطأ. صرِّف الجمع بشكل خاطئ: التعبير الموجود على اليمين لا يُصرَّف، والتعبير الموجود على اليسار يُصرَّف مرتين.
def badCompile : Expr → List Instr
| .num n => [.push n]
| .add a _ => badCompile a ++ badCompile a ++ [.add]
| .mul a b => badCompile a ++ badCompile b ++ [.mul]
theorem bad_correct (e : Expr) (s : List Nat) :
run (badCompile e) s = eval e :: s := by
induction e generalizing s with
| num n =>
rfl
| add a b iha ihb =>
simp [badCompile, run_append, iha, ihb, run, eval]
| mul a b iha ihb =>
simp [badCompile, run_append, iha, ihb, run, eval]يجب أن ترى: فرع الجمع لا يمرّ في الإثبات، وتبدأ رسالة الخطأ بهذا السطر:
unsolved goalsهذا المُصرِّف الخاطئ يحسب جميع التعبيرات التي يتطابق فيها الطرفان مثل 1 + 1 و2 + 2 بشكل صحيح. إذا اختبرت هذه فقط، فستنجح الاختبارات. أما الإثبات فلا.
- رأيت أن المُصرِّف الخاطئ لا يمرّ في الإثبات
نقطة تحقق
- ملف
Compiler.leanلم يُظهر أي خطأ من البداية إلى النهاية - أستطيع أن أشرح ما هو كل من
evalوrunوcompile - أستطيع أن أقرأ معنى العبارة
compile_correct - أعرف لماذا نحتاج إلى المُبرهنة
run_append - رأيت خطأً تنجح معه الاختبارات لكن يفشل معه الإثبات
لم تنجح؟
compile_correct يُظهر خطأً يقول إنه لا يعرف run_append. يجب كتابة المُبرهنة قبل ذلك.
بقي في فرع الجمع هدف أو أكثر لم يُثبت. قارن بالبنود الستة داخل الأقواس المربعة في simp، لا يجوز أن ينقص أي منها. خصوصًا run_append، فبدونه لا يمكن فك التعليمات المُدمجة.
فرضية الاستقراء غير قابلة للاستخدام. تحقق هل كُتب generalizing s بعد induction e.
ما الذي أنجزته
لقد عرّفتَ معنى لغة صغيرة، وكتبتَ مُصرِّفًا، وأثبتَّ أنه يحافظ على المعنى دون تغيير. التحقق من برنامج هو فعل هذه الأمور الثلاثة: كتابة ما معنى "صحيح"، وكتابة البرنامج، وإثبات أن البرنامج يحقق ذلك.
ما يمكنك تجربته بنفسك تاليًا:
- أضِف شكلًا جديدًا إلى
Expr، مثل الطرح. سيخبرك Lean بالدوال والإثباتات التي تحتاج إلى إضافة فرع جديد لها. - اعكس ترتيب a وb في
compileثم انظر إلىcompile_correct. سيبقى في فرع الجمع هدف واحد:eval b + eval a = eval a + eval b. هذه العبارة صحيحة، ويمكن إكمالها باستخدامNat.add_commمن الفصل السابق. وماذا لو استبدلناها بالطرح؟ هل تبقى العبارة المتبقية صحيحة؟