सिद्ध करें कि एक कंपाइलर सही है
यह ग्रेजुएशन प्रोजेक्ट है। यह खंड पूरा करने पर आपके पास एक मिनी कंपाइलर होगा, और एक ऐसी प्रमेय जिसे 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 पर आगमन (induction) है। इसमें दो नई चीज़ें हैं:
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, इसके बिना जोड़े हुए निर्देश नहीं टूटते।
आगमन परिकल्पना काम नहीं आती। देखें कि induction e के बाद generalizing s लिखा है या नहीं।
आपने क्या हासिल किया
आपने एक छोटी भाषा का अर्थ परिभाषित किया, एक कंपाइलर लिखा, और सिद्ध किया कि वह अर्थ को अपरिवर्तित रखता है। किसी प्रोग्राम को सत्यापित करने का काम भी यहीं तीन चीज़ें हैं: लिखें कि "सही" का मतलब क्या है, प्रोग्राम लिखें, और सिद्ध करें कि प्रोग्राम उसे पूरा करता है।
आगे खुद आज़माने के लिए:
Exprमें एक और रूप जोड़ें, जैसे घटाव। Lean आपको बताएगा कि किन फ़ंक्शनों और प्रमाणों में नई शाखा जोड़नी होगी।compileमें a और b का क्रम बदलें, फिरcompile_correctको देखें। जोड़ वाली शाखा में एक लक्ष्य बचेगा:eval b + eval a = eval a + eval b। यह कथन सत्य है, और पिछले अध्याय केNat.add_commसे इसे पूरा किया जा सकता है। इसके बजाय घटाव लें तो? बचा हुआ कथन अब भी सत्य है?