Skip to content

إثبات صحة مُصرِّف ​

هذا مشروع تخرج. بعد إكمال هذا القسم، سيكون بين يديك مُصرِّف مصغّر، ونظرية تحقق منها Lean: لأي تعبير حسابي، فإن النتيجة التي تحسبها التعليمات المُصرَّفة هي نفسها النتيجة المباشرة لحساب هذا التعبير.

ليس "اختبرنا تعابير كثيرة وكلها صحيحة"، بل جميعها.

كل ما يُستخدم هنا هو ما تعلمته سابقًا: تعريف الدوال، والاستقراء على البُنى، والبحث عن مبرهنات عند التعثر.

قبل البدء ​

  • تعلمتالاستقراء على القوائم، وتعرف ما هي المبرهنة
  • أنشئ ملفًا جديدًا Compiler.lean، واكتب الشيفرة التالية فيه بالترتيب

الخطوة 1: تعريف التعابير الحسابية، وما "ينبغي" أن تساوي قيمته ​

التعبير الحسابي إما أن يكون عددًا، أو جمع تعبيرين، أو ضرب تعبيرين:

lean
inductive Expr where
  | num : Nat → Expr
  | add : Expr → Expr → Expr
  | mul : Expr → Expr → Expr

inductive يُعرِّف نوع بيانات جديدًا، مع سرد جميع أشكاله الممكنة.

حساب قيمة تعبير حسابي مباشرةً:

lean
def eval : Expr → Nat
  | .num n => n
  | .add a b => eval a + eval b
  | .mul a b => eval a * eval b

eval هو تعريف "الإجابة الصحيحة". صحة المُصرِّف لاحقًا تُقاس بالنسبة إليه.

جرّب 2 + 3 × 4:

lean
def demo : Expr := .add (.num 2) (.mul (.num 3) (.num 4))

#eval eval demo
text
14
  • eval demo يحسب 14

الخطوة 2: تعريف آلة لا تتعرف إلا على ثلاث تعليمات ​

لهذه الآلة مكدس، أي كومة من الأعداد، لا يمكن الوضع فيها أو الأخذ منها إلا من الأعلى. التعليمات ثلاث:

lean
inductive Instr where
  | push : Nat → Instr
  | add
  | mul
  • push n: ضع n في أعلى المكدس.
  • add: خذ العددين في أعلى المكدس، وضع مجموعهما مكانهما.
  • mul: خذ العددين في أعلى المكدس، وضع حاصل ضربهما مكانهما.

تنفيذ سلسلة من التعليمات:

lean
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 stack

run 指令 栈 يُرجع المكدس بعد انتهاء التنفيذ. السطر الأخير يعالج حالة عدم وجود عددين كافيين في المكدس: تخطي هذه التعليمة.

  • Instr و run بلا أخطاء

الخطوة 3: كتابة المُصرِّف ​

ترجمة التعبير الحسابي إلى تعليمات. العدد هو ببساطة push؛ والجمع هو حساب الجانب الأيسر أولًا، ثم الأيمن، وأخيرًا add:

lean
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]

صرِّف التعبير السابق وشغّله على مكدس فارغ:

lean
#eval run (compile demo) []
text
[14]

أعلى المكدس هو 14، وهو نفس eval demo. لكن هذا تعبير واحد فقط.

  • run (compile demo) [] يعطي [14]

الخطوة 4: كتابة العبارة المطلوب إثباتها ​

"المُصرِّف صحيح" يجب أولًا توضيح معناه:

text
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 هي عدة مقاطع من التعليمات مُسلسلة معًا. للتفكير فيها، يجب أولًا معرفة: تشغيل مقطعين من التعليمات مُسلسلين معًا يساوي تشغيل المقطع الأول، ثم تشغيل المقطع الثاني على المكدس الذي تركه.

lean
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: إثبات صحة المُصرِّف ​

استقراء على شكل التعبير الحسابي. للتعبير ثلاثة أشكال، فالحالات ثلاث؛ وللجمع والضرب تعبيران فرعيان لكل منهما، فلكل منهما فرضيتا استقراء. مشِ بنفسك عبرها:

البرهنة بنفسكإثبات أن المترجم صحيحالحالة والأخطاء من Lean 4.35.0 توليد
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]

اكتب في الملف:

lean
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: اكتب عمدًا مُصرِّفًا خاطئًا ​

للتحقق من الفائدة، انظر هل يستطيع اكتشاف الخطأ. صرِّف الجمع بشكل خاطئ: التعبير الموجود على اليمين لا يُصرَّف، والتعبير الموجود على اليسار يُصرَّف مرتين.

lean
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]

يجب أن ترى: فرع الجمع لا يمرّ في الإثبات، وتبدأ رسالة الخطأ بهذا السطر:

text
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 من الفصل السابق. وماذا لو استبدلناها بالطرح؟ هل تبقى العبارة المتبقية صحيحة؟
gaodong.aiAboutPrivacyContact

Independent tutorials, not affiliated with any product mentioned. Product names and trademarks belong to their owners. Check official pages for prices and policies.