এই পর্বে যা শিখবেন
- Hoare triple-এর অর্থ big-step semantics দিয়ে নিখুঁতভাবে লেখা, আর partial ও total correctness আলাদা করা
- Haat-core-এর জন্য Hoare logic-এর নিয়ম ব্যবহার করে প্রমাণ লেখা, আর While নিয়মের soundness প্রমাণ বোঝা
- Weakest precondition হাতে আর কোডে হিসাব করা, শূন্য দিয়ে ভাগ আর short-circuit-সহ
- Loop invariant আর variant বেছে নেওয়া, ভুল invariant counterexample দিয়ে ধরা
- Haat source থেকে verification condition বানিয়ে Z3 দিয়ে যাচাই করা, গণিতের Int আর 64-bit দুই জগতেই
১ · অর্থ মানে চুক্তি — {P} S {Q} কী দাবি করে
বাজারঘর একটি কুরিয়ার কোম্পানির সঙ্গে চুক্তি করেছে। চুক্তিপত্রে লেখা নেই কুরিয়ারের ভ্যান কোন রাস্তায় যাবে, কোথায় চা খেতে থামবে। লেখা আছে শুধু দুটি কথা: “পার্সেল ঠিকমতো প্যাক করা আর ঠিকানা সঠিক থাকলে, পৌঁছানোর সময় পার্সেল অক্ষত থাকবে।” প্রথম অংশ শর্ত, দ্বিতীয় অংশ প্রতিশ্রুতি। ক্রেতার কাছে কুরিয়ারের “অর্থ” এই চুক্তিটুকুই।
Program-এর অর্থও এভাবে লেখা যায়। পর্ব ৪০-এ (Operational semantics) অর্থ ছিল program কীভাবে ধাপে ধাপে চলে। পর্ব ৪১-এ (Denotational semantics) অর্থ ছিল একটি গাণিতিক function, state থেকে state-এ। এই পর্বে তৃতীয় রীতি, axiomatic semantics: program-এর অর্থ হলো তার সম্পর্কে কোন কোন দাবি প্রমাণ করা যায়, তার তালিকা। দাবিগুলোর আকার একটিই, Hoare triple:
পড়ুন: “P সত্য এমন যেকোনো state থেকে S চালালে, S যদি স্বাভাবিকভাবে শেষ হয়, তবে শেষ state-এ Q সত্য।” P হলো precondition (আগের শর্ত), Q postcondition (পরের শর্ত)। P আর Q-কে বলা হয় assertion: state সম্পর্কে একটি যুক্তির বাক্য, যেমন qty >= 0 && unit >= 0. এই পর্বে assertion লেখা হবে Haat-এর expression দিয়েই, সঙ্গে গণিতের ∧ (এবং), ∨ (অথবা), ¬ (না), ⇒ (হলে) আর ∀ (সব)।
Hoare logic-এর প্রথম পরিচয় পেয়েছেন Discrete Mathematics-এর পর্ব ১৩-এ (Program-এর সঠিকতা): triple, নিয়মগুলো, একটি ভাগের loop আর Z3-এর প্রথম স্বাদ। লুপ ইনভেরিয়েন্টের অ্যালগরিদমিক ব্যবহার আছে DSA-র পর্ব ০৩-এ। এখানে ভাষা-নকশাকারীর চোখে আরও গভীরে যাব: Haat-core-এর জন্য পুরো logic, প্রতিটি নিয়ম কেন সঠিক তার প্রমাণ, wp-এর গণিত, 64-bit integer আর runtime error-এর বাস্তবতা, আর Haat source থেকে নিজের হাতে verification condition বানিয়ে Z3-কে দেওয়া।
ইতিহাস। Alan Turing ১৯৪৯ সালে “Checking a large routine” নামের একটি ছোট লেখায় একটি routine-এর বিভিন্ন জায়গায় শর্ত লিখে তার সঠিকতা যাচাইয়ের ধারণা দেখান বলে ধরা হয়। Robert Floyd ১৯৬৭ সালে “Assigning meanings to programs”-এ flowchart-এর প্রতিটি তিরে assertion বসিয়ে প্রমাণের পদ্ধতি দেন। C. A. R. (Tony) Hoare ১৯৬৯ সালে Communications of the ACM-এ “An axiomatic basis for computer programming” প্রকাশ করেন, যেখানে triple আর নিয়মের আকারটি আসে; তাই একে Floyd–Hoare logic-ও বলা হয়। Edsger Dijkstra ১৯৭৫ সালের “Guarded commands, nondeterminacy and formal derivation of programs” লেখায় weakest precondition প্রস্তাব করেন। Floyd ১৯৭৮ আর Hoare ১৯৮০ সালে Turing Award পান।
“S যদি শেষ হয়” কথাটি গুরুত্বপূর্ণ। এটি নিখুঁত করতে পর্ব ৪০-এর big-step semantics লাগে: ⟨S, σ⟩ ⇓ σ′ মানে “state σ থেকে S চালালে শেষে state σ′”, আর ⟨S, σ⟩ ⇓ error মানে runtime error. σ ⊨ P লিখলে বোঝাবে “state σ-তে P সত্য”।
Partial: ⊨ {P} S {Q}, যদি প্রতিটি σ, σ′-এর জন্য σ ⊨ P আর ⟨S, σ⟩ ⇓ σ′ হলে σ′ ⊨ Q. Total: ⊨ [P] S [Q], যদি প্রতিটি σ ⊨ P-এর জন্য এমন σ′ আছে যে ⟨S, σ⟩ ⇓ σ′ (অর্থাৎ S থামে, error ছাড়া), আর সেই σ′ ⊨ Q.
Partial correctness তাই অসীম loop আর runtime error সম্পর্কে কিছু বলে না: যে চলা শেষই হলো না, বা error-এ থামল, তার জন্য দাবির কিছু যায় আসে না। Total correctness দুটোই নিষেধ করে। কুরিয়ারের ভাষায়: partial মানে “পৌঁছালে অক্ষত”, total মানে “পৌঁছাবেই, আর অক্ষত”। নিচের ছবিতে তিনটি শুরুর state আর তাদের পরিণতি।
ছবি ৪২.১ — একটি triple-এর চোখে state-এর জগৎ
বাঁয়ে P সত্য এমন state, ডানে Q সত্য এমন state. প্রতিটি তির S-এর একটি চলা। Partial correctness শুধু শেষ হওয়া তির দেখে; total correctness তিনটিই দেখে
কোন রীতি কখন? Operational semantics interpreter লেখার নকশা, denotational semantics দুটি program-এর সমতা প্রমাণের হাতিয়ার, আর axiomatic semantics program সঠিক কি না প্রমাণের হাতিয়ার। তিনটিই একই ভাষার কথা বলে, তাই একটির নিয়ম অন্যটি দিয়ে যাচাই করা যায়; অংশ ৭-এ ঠিক এটিই করব।
২ · Haat-core-এর জন্য Hoare logic — সাতটি নিয়ম
পর্ব ৪০-এর Haat-core-ই চলবে: expression-এ সংখ্যা, true, false, variable, + - * / %, তুলনা, && আর ||; statement-এ x = e;, print(e);, পরপর দুটি statement, if e { S } else { S }, while e { S } আর সহায়ক skip. সব variable শুরুতে ঘোষিত, ভেতরে নতুন ঘোষণা নেই। একটি কথা এখানে খুব কাজের: Haat-core-এর expression state বদলায় না। কারণ README-র সিদ্ধান্ত ৯ অনুযায়ী assignment একটি statement, expression নয়, আর core-এ function call নেই। তাই একটি expression-এর মান শুধু state-এর ওপর নির্ভর করে, যা নিচের assignment নিয়মকে সম্ভব করে।
Hoare logic একটি প্রমাণ-পদ্ধতি: কিছু inference rule, যা দিয়ে ⊢ {P} S {Q} (“প্রমাণ করা যায়”) গড়া হয়। পর্ব ৩৪-এর typing rule-এর মতো দাগের ওপরে premise, নিচে conclusion:
নামের আগে H- রাখা হলো, যাতে পর্ব ৪০-এর E- আর B- নিয়মের সঙ্গে গুলিয়ে না যায়। Discrete Mathematics-এর পর্বে এদের বলা হয়েছিল assignment axiom, composition rule, conditional rule, while rule আর consequence rule; নিয়ম একই।
H-Assign পেছন থেকে কেন? Q[e/x] মানে “Q-এর ভেতরে x-এর প্রতিটি জায়গায় e বসানো” (একটি substitution). ধরুন চাই, assignment-এর পরে p ≥ 1000. তাহলে আগে কী সত্য থাকা দরকার? p-এর নতুন মান হবে qty * 520, তাই আগে qty * 520 ≥ 1000 সত্য হলেই চলে: {qty * 520 >= 1000} p = qty * 520; {p >= 1000}. সামনের দিকে একই কাজ করতে গেলে পুরোনো মানের নাম হারিয়ে যায়: {x == 5} x = x + 1; {?}-এ P-তে x-এর জায়গায় x + 1 বসালে আসে x + 1 == 5, যা ভুল (আসল উত্তর x == 6). সঠিক সামনের নিয়মটি Floyd-এর, তাতে “পুরোনো মান x₀ বলে কিছু আছে” লিখতে ∃ লাগে; ফলটির নাম strongest postcondition. পেছনের নিয়মে ∃ লাগে না, তাই যন্ত্রে সহজ।
H-Print. Assertion-এ ছাপা লেখার কোনো ঘর নেই, তাই print state-এর variable বদলায় না: যা আগে সত্য, পরেও সত্য। ছাপা লেখা নিয়েও দাবি করতে চাইলে পর্ব ৪০-এর out ঘরটিকে একটি variable হিসেবে assertion-এ আনতে হতো।
H-While. I হলো loop invariant: শর্ত সত্য থাকা অবস্থায় দেহ একবার চালালে যা টিকে থাকে। তাহলে যত বারই ঘুরুক, I টিকে থাকে, আর loop শেষ হলে শর্ত মিথ্যা, তাই I ∧ ¬b. লক্ষ করুন, নিয়মে কোথাও “থামে” নেই; এটি partial correctness-এর নিয়ম। থামার জন্য অংশ ৫-এ আলাদা নিয়ম আসবে।
H-Cons একমাত্র নিয়ম যা program দেখে না, শুধু যুক্তি: শুরুর শর্ত শক্ত করা আর শেষের শর্ত ঢিলে করা সবসময় নিরাপদ। P ⇒ P′ ধরনের বাক্যগুলো গণিতের সত্য, program-এর নয়; এদেরই পরে Z3-কে দেওয়া হবে।
৩ · Weakest precondition — পেছন থেকে হিসাব
Hoare-এর নিয়ম দিয়ে প্রমাণ লিখতে প্রতিটি ধাপে মাঝের assertion R অনুমান করতে হয়। Dijkstra-র পর্যবেক্ষণ: loop না থাকলে অনুমানের দরকার নেই, পেছন থেকে হিসাব করলেই হয়। Weakest precondition wp(S, Q) হলো সবচেয়ে দুর্বল শর্ত, যা শুরুতে সত্য থাকলে S নিশ্চিতভাবে থামে আর শেষে Q সত্য হয়। “সবচেয়ে দুর্বল” মানে অন্য যেকোনো যথেষ্ট শর্ত একে imply করে।
Haat-এ একটি সূক্ষ্মতা আছে: / আর % শূন্য দিয়ে হলে runtime error (README সিদ্ধান্ত ২৬)। তাই প্রতিটি expression-এর জন্য একটি definedness condition def(e) লাগে: def(a / b) = def(a) ∧ def(b) ∧ b ≠ 0. আর short-circuit-এর জন্য def(a && b) = def(a) ∧ (a ⇒ def(b)), কারণ a মিথ্যা হলে b চলেই না (পর্ব ২৬-এর পাহারা-কৌশল)। এবার নিয়মগুলো:
| S | wp(S, Q) |
|---|---|
skip | Q |
x = e; | def(e) ∧ Q[e/x] |
print(e); | def(e) ∧ Q |
| S1 S2 | wp(S1, wp(S2, Q)) |
if b { S1 } else { S2 } | def(b) ∧ (b ⇒ wp(S1, Q)) ∧ (¬b ⇒ wp(S2, Q)) |
while b { S } | সরল সূত্র নেই: invariant লাগে (অংশ ৫–৬) |
def বাদ দিলে যা পাওয়া যায়, তার নাম weakest liberal precondition, wlp: partial correctness-এর জন্য (error হলে দাবি খাটে না)। দুটির মধ্যে সম্পর্কটি সরল: loop-ছাড়া Haat-core-এ wp(S, Q) = wlp(S, Q) ∧ “কোথাও error হয় না”।
(ক) σ ⊨ wp(S, Q) হলে ⟨S, σ⟩ ⇓ σ′ কোনো σ′-এর জন্য, আর σ′ ⊨ Q. (খ) উল্টোটাও: σ থেকে S error ছাড়া থেমে Q-তে পৌঁছালে σ ⊨ wp(S, Q). ফলে ⊨ [P] S [Q] হয় ঠিক তখন, যখন P ⇒ wp(S, Q) সব state-এ সত্য।
প্রমাণের রূপরেখা (S-এর গঠনের ওপর structural induction; induction-এর ভিত্তি Discrete Mathematics-এর পর্ব ১০-এ):
- মূল lemma (substitution): def(e) সত্য হলে σ ⊨ Q[e/x] ঠিক তখন, যখন σ[x ↦ v] ⊨ Q, যেখানে ⟨e, σ⟩ ⇓ v. কারণ Q-তে x যেখানে ছিল, বাঁ পাশে সেখানে e, আর e-এর মান σ-তে v; Q-এর বাকি অংশ দুই state-এ একই, কারণ শুধু x বদলেছে। Expression-এর side effect নেই বলেই এটি খাটে।
- x = e; def(e) মানে B-Assign খাটে, error নয়; তারপর lemma. (ক) আর (খ) দুই দিকই সরাসরি।
- S1 S2: induction hypothesis (IH) S1-এ wp(S2, Q)-কে postcondition ধরে, তারপর S2-এ IH; B-Seq দুটি চলা জোড়ে।
- if: def(b) থাকায় b-এর মান true বা false. true হলে প্রথম implication থেকে σ ⊨ wp(S1, Q), IH আর B-IfT; false হলে B-IfF. ∎
এবার হিসাবটি কোডে। বাজারঘরের বিল: p = qty * unit; d = p / 10; total = p - d + 60;, অর্থাৎ ১০% ছাড়, তারপর ৬০ টাকা ডেলিভারি। দাবি: বিল কখনো ৬০ টাকার কম নয়, Q = total >= 60. নিচের block-এ expression হলো ছোট tuple, যেমন ("*", "qty", "unit"); sub হলো Q[e/x], ok হলো def(e), আর wp সরাসরি ওপরের টেবিল।
# wp ক্যালকুলেটর: Haat-core-এর assignment আর if, পেছন থেকে substitution
PREC = {"=>": 0, "||": 1, "&&": 2, "==": 3, "!=": 3, "<": 4, "<=": 4, ">": 4,
">=": 4, "+": 5, "-": 5, "*": 6, "/": 6, "%": 6}
def show(e, p=0):
if not isinstance(e, tuple): return str(e).lower()
if e[0] == "!": return "!" + show(e[1], 7)
q = PREC[e[0]]; s = f"{show(e[1], q)} {e[0]} {show(e[2], q + 1)}"
return f"({s})" if q < p else s
def sub(e, x, r): # Q[r/x]: x-এর প্রতিটি জায়গায় r
if e == x: return r
return (e[0], *[sub(a, x, r) for a in e[1:]]) if isinstance(e, tuple) else e
def AND(a, b): return b if a is True else a if b is True else ("&&", a, b)
def ok(e): # def(e): runtime error ছাড়া চলবে কখন
if not isinstance(e, tuple): return True
d = True
for a in e[1:]: d = AND(d, ok(a))
if e[0] in "/%" and not (type(e[2]) is int and e[2] != 0): d = AND(d, ("!=", e[2], 0))
return d
def wp(S, Q):
if S[0] == "=": return AND(ok(S[2]), sub(Q, S[1], S[2]))
if S[0] == "if": return AND(ok(S[1]), AND(("=>", S[1], wp(S[2], Q)),
("=>", ("!", S[1]), wp(S[3], Q))))
for s in reversed(S[1:]): Q = wp(s, Q) # ("seq", S1, S2, ...)
return Q
bill = [("=", "p", ("*", "qty", "unit")), ("=", "d", ("/", "p", 10)),
("=", "total", ("+", ("-", "p", "d"), 60))]
Q = (">=", "total", 60); print(f"{'Q':23}:", show(Q))
for s in reversed(bill):
Q = wp(s, Q); print(f"wp({s[1]} = {show(s[2])})".ljust(23), ":", show(Q))
print(show(wp(("=", "each", ("/", "total", "k")), (">=", "each", 0))))
print(show(wp(("if", (">=", "t", 1000), ("=", "t", ("-", "t", ("/", "t", 10))),
("seq",)), (">=", "t", 0))))আসল আউটপুট (ব্রাউজারের Python):
Q : total >= 60
wp(total = p - d + 60) : p - d + 60 >= 60
wp(d = p / 10) : p - p / 10 + 60 >= 60
wp(p = qty * unit) : qty * unit - qty * unit / 10 + 60 >= 60
k != 0 && total / k >= 0
(t >= 1000 => t - t / 10 >= 0) && (!(t >= 1000) => t >= 0)
প্রথম চার লাইন পেছন থেকে হাঁটা: শেষ assignment থেকে শুরু, প্রতি ধাপে একটি substitution. d = p / 10-এর ধাপে def যোগ হয়নি, কারণ ভাজক 10 একটি শূন্য-নয় সংখ্যা, ok তা চিনে বাদ দেয়। পঞ্চম লাইনে ভাজক একটি variable k, তাই wp-তে k != 0 যোগ হলো: ভাগ নিরাপদ না হলে কোনো postcondition-ই নিশ্চিত নয়। শেষ লাইনে if-এর নিয়ম: ছাড়ের শাখা আর else-বিহীন (skip) শাখা, দুই দিকের wp-ই আলাদা implication হয়ে এসেছে। একটি সরলীকরণ: ok short-circuit মানে না, &&-এর দুই পাশের সব ভাগের পাহারা চায়। এটি দরকারের চেয়ে কড়া, তাই নিরাপদ; অংশ ৬-এর vcgen.py ঠিক নিয়মটিই মানে।
একই হিসাব ধাপে ধাপে, প্রতিটি ধাপে কোন লাইনের নিয়ম খাটছে তা দেখে:
0{ P: qty ≥ 0 ∧ unit ≥ 0 }1p = qty * unit;2d = p / 10;3total = p - d + 60;4{ Q: total ≥ 60 }
| শর্ত | |
| নিয়ম |
- শুরু শেষ থেকে। লক্ষ্য Q: total ≥ 60, program-এর একদম শেষে। wp হিসাব পেছন দিকে হাঁটে, তাই প্রথমে দেখা হয় শেষ লাইন ৩।
- লাইন ৩. H-Assign: Q-তে total-এর জায়গায় p − d + 60 বসানো। নতুন শর্ত p − d + 60 ≥ 60, যা লাইন ৩-এর ঠিক আগে সত্য থাকতে হবে। total নামটি আর শর্তে নেই।
- লাইন ২. d-এর জায়গায় p / 10. ভাগ আছে, তাই def যোগ হওয়ার কথা: 10 ≠ 0, যা নিজেই সত্য, তাই বাদ। শর্ত এখন p − p / 10 + 60 ≥ 60.
- লাইন ১. p-এর জায়গায় qty·unit. ফল wp(S, Q) = qty·unit − qty·unit / 10 + 60 ≥ 60, যেখানে শুধু ইনপুট qty আর unit আছে। হিসাব পুরো যান্ত্রিক, কোনো অনুমান লাগেনি।
- P ⇒ wp? গণিতের পূর্ণসংখ্যায় (ℤ): qty ≥ 0 আর unit ≥ 0 হলে p = qty·unit ≥ 0, আর শূন্যের দিকে কাটা ভাগে p / 10 ≤ p, তাই p − p / 10 ≥ 0. H-Cons দিয়ে triple প্রমাণিত। পরের block এটি ৬২৫টি state-এ চালিয়েও মেলায়।
- কিন্তু Haat-এ Int 64-bit. “p ≥ 0” ধাপটি ভুল হতে পারে: দুটি ধনাত্মক সংখ্যার গুণফল wrap হয়ে ঋণাত্মক হয় (সিদ্ধান্ত ১৩)। অংশ ৪-এ Z3 ঠিক এমন qty আর unit খুঁজে দেবে, যেখানে p = −61 আর বিল 5 টাকা।
wp যে আসলেই সঠিক (Theorem ৪২.১), সেটিও চালিয়ে দেখা যায়: প্রতিটি state-এ “wp সত্য” আর “program চালিয়ে শেষে Q সত্য” একই উত্তর দেয় কি না। নিচের block আগের block-এর wp আর bill ব্যবহার করে, সঙ্গে Haat-এর অর্থে একটি ছোট evaluator: 64-bit wrap আর C-র মতো ভাগ।
# Haat-এর অর্থে হিসাব (64-bit wrap, C-র ভাগ), তারপর ছোট পরিসরের সব অবস্থায় যাচাই
def wrap(n): return (n + 2**63) % 2**64 - 2**63 # সিদ্ধান্ত ১৩
def cdiv(a, b): q = abs(a) // abs(b); return q if (a < 0) == (b < 0) else -q
ARITH = {"+": lambda a, b: a + b, "-": lambda a, b: a - b, "*": lambda a, b: a * b,
"/": cdiv, "%": lambda a, b: a - b * cdiv(a, b)}
CMP = {"<": int.__lt__, "<=": int.__le__, ">": int.__gt__, ">=": int.__ge__,
"==": lambda a, b: a == b, "!=": lambda a, b: a != b}
def ev(e, s): # ⟦e⟧σ
if not isinstance(e, tuple): return s[e] if isinstance(e, str) else e
if e[0] == "!": return not ev(e[1], s)
if e[0] == "&&": return ev(e[1], s) and ev(e[2], s) # short-circuit
if e[0] == "=>": return not ev(e[1], s) or ev(e[2], s)
a, b = ev(e[1], s), ev(e[2], s) # বাঁ দিক আগে
if e[0] in CMP: return CMP[e[0]](a, b)
if e[0] in "/%" and b == 0: raise ZeroDivisionError("division by zero")
return wrap(ARITH[e[0]](a, b))
def run(S, s): # ⟨S, σ⟩ ⇓ σ′
for x, e in S: s = {**s, x: ev(e, s)}
return s
W, Q = wp(("seq", *bill), (">=", "total", 60)), (">=", "total", 60)
grid = [{"qty": q, "unit": u} for q in range(-12, 13) for u in range(-12, 13)]
same = sum(ev(W, s) == ev(Q, run([b[1:] for b in bill], s)) for s in grid)
print("wp সত্য ⇔ চালানোর পরে Q সত্য:", same, "/", len(grid), "অবস্থায় মিলেছে")
for name, P in [("qty >= 0 && unit >= 0", ("&&", (">=", "qty", 0), (">=", "unit", 0))),
("true", True)]:
bad = [s for s in grid if ev(P, s) and not ev(W, s)]
print(f"{{{name}}} ⇒ wp:", f"counterexample {bad[0]}" if bad else "সব অবস্থায় সত্য")
z3_model = {"qty": 2689941458634176767, "unit": 8537903022776636733}
end = run([b[1:] for b in bill], z3_model)
print("Z3-এর অবস্থায়: p =", end["p"], "| total =", end["total"], "| wp =", ev(W, z3_model))আসল আউটপুট (ব্রাউজারের Python):
wp সত্য ⇔ চালানোর পরে Q সত্য: 625 / 625 অবস্থায় মিলেছে
{qty >= 0 && unit >= 0} ⇒ wp: সব অবস্থায় সত্য
{true} ⇒ wp: counterexample {'qty': -12, 'unit': 1}
Z3-এর অবস্থায়: p = -61 | total = 5 | wp = False
qty আর unit −12 থেকে 12 পর্যন্ত সব ৬২৫টি জোড়ায় wp আর আসল চলা হুবহু মিলেছে: Theorem ৪২.১-এর দুই দিক এই পরিসরে। {qty ≥ 0 ∧ unit ≥ 0} ⇒ wp এই পরিসরে সব জায়গায় সত্য। কিন্তু precondition true দিলে প্রথম counterexample qty = −12, unit = 1: p = −12, d = −1, বিল −12 + 1 + 60 = 49. শেষ লাইনে অংশ ৪-এর Z3-এর পাওয়া বিশাল দুটি সংখ্যা, browser-এ: p = −61, বিল 5, আর wp মিথ্যা। ছোট পরিসরের brute force এটি কখনো খুঁজে পেত না।
৪ · Haat-এর বাস্তবতা — 64-bit wrap আর সত্যিকারের Z3
অংশ ৩-এর প্রমাণে একটি নীরব অনুমান ছিল: “qty ≥ 0 আর unit ≥ 0 হলে qty·unit ≥ 0”. গণিতের পূর্ণসংখ্যায় সত্য, Haat-এ নয়। Haat-এর Int 64-bit, আর প্রতিটি ফল wrap করে (README সিদ্ধান্ত ১৩; wrapping arithmetic). Hoare নিজেই ১৯৬৯-এর paper-এ লিখেছিলেন যে যন্ত্রের পূর্ণসংখ্যা সসীম, আর integer overflow-এর কয়েকটি সম্ভাব্য ব্যাখ্যা (overflow নিষিদ্ধ, সীমায় আটকে যাওয়া, modulo হিসাব) আলাদা axiom দিয়ে ধরতে হবে।
এই প্রশ্ন হাতে নয়, একটি SMT solver দিয়ে নিষ্পত্তি করা যায়। দাবিটিকে একটি গাণিতিক বাক্যে পরিণত করা হয়, যার নাম verification condition (VC): এখানে P ⇒ wp(S, Q). VC সব state-এ সত্য কি না জানতে solver-কে দেওয়া হয় তার অস্বীকার ¬VC: solver যদি বলে “এর কোনো সমাধান নেই” (unsat), তবে VC সর্বত্র সত্য; সমাধান পেলে সেটিই একটি counterexample. Z3-এ variable দুই রকমে ঘোষণা করা যায়: Int (গণিতের অসীম পূর্ণসংখ্যা) আর BitVec(x, 64), একটি 64-বিটের bit-vector, যার যোগ-গুণ ঠিক Haat-এর মতো wrap করে আর signed ভাগ শূন্যের দিকে কাটে।
লেখকের lab-এ একটি ছোট VC generator লেখা হলো, vcgen.py (অংশ ৬-এ ভেতরটা দেখবেন)। সেটি Haat-এর reference implementation-এর lexer আর parser দিয়ে একটি সত্যিকারের .haat ফাইল পড়ে, wp হিসাব করে, আর Z3-কে জিজ্ঞেস করে। Haat ফাইলে let দিয়ে ঘোষণা আছে, কারণ reference চালাতে তা লাগে; generator ইনপুট হিসেবে চিহ্নিত নামগুলোর (এখানে qty, unit) let বাদ দিয়ে সেগুলোকে “যেকোনো মান” ধরে, আর বাকি let-কে Haat-core-এর assignment হিসেবে পড়ে।
// বাজারঘর: একটি পণ্যের বিল, ১০% ছাড় আর ৬০ টাকা ডেলিভারি
let qty = 2;
let unit = 520;
let p = qty * unit;
let d = p / 10;
let total = p - d + 60;
print(total);
# ---- verify_bill.py ----
from vcgen import verify
IN = {"qty", "unit"}
S, Q = "bill.haat", "total >= 60"
for pre, mode in [("qty >= 0 && unit >= 0", "int"), ("true", "int"),
("qty >= 0 && unit >= 0", "bv"),
("qty >= 0 && qty <= 1000 && unit >= 0 && unit <= 1000000", "bv")]:
print(f"[{mode}] {{{pre}}} bill {{{Q}}}")
verify(S, pre, Q, [], IN, mode)সত্যিকারের run, লেখকের Windows lab-এ: Python 3.12.13, z3-solver 5.4.1.0 (PyPI, MIT লাইসেন্স; প্যাকেজটিতে কোনো network বা usage-reporting কোড নেই, লেখক খুঁজে দেখেছেন), কাজ শেষে পুরো venv মুছে ফেলা হয়েছে:
~/haat-verify $ uv add z3-solver
~/haat-verify $ uv run python verify_bill.py
[int] {qty >= 0 && unit >= 0} bill {total >= 60}
init valid
[int] {true} bill {total >= 60}
init FAILS {'unit': -1, 'qty': 1}
[bv] {qty >= 0 && unit >= 0} bill {total >= 60}
init FAILS {'unit': 8537903022776636733, 'qty': 2689941458634176767}
[bv] {qty >= 0 && qty <= 1000 && unit >= 0 && unit <= 1000000} bill {total >= 60}
init valid
~/haat-verify $ python haat.py run bill.haat
996
~/haat-verify $ python haat.py run bill_cex.haat # qty, unit = Z3-এর দুটি মান
5
চারটি লাইন, চারটি শিক্ষা। (১) গণিতের Int-এ triple প্রমাণিত, অংশ ৩-এর হাতের প্রমাণের মতোই। (২) precondition true হলে Z3-এর counterexample qty = 1, unit = −1: ঋণাত্মক দাম। (৩) 64-bit-এ একই precondition ভাঙে: qty = 2689941458634176767 আর unit = 8537903022776636733 দুটিই ধনাত্মক, কিন্তু গুণফল wrap হয়ে −61. Reference interpreter-এ ঠিক এই দুটি মান বসিয়ে চালালে বিল আসে 5, আর vm back end-ও 5 দেয়। (৪) বাস্তবসম্মত সীমা যোগ করলে (qty ≤ 1000, unit ≤ 1000000) 64-bit-এও প্রমাণিত, কারণ গুণফল সর্বোচ্চ 109, 64 বিটের সীমার অনেক নিচে।
ভাষাভেদে নিয়ম আলাদা। Haat আর Java-র long wrap করে; তাই প্রমাণে bit-vector লাগে, বা overflow হয় না তা আলাদা করে দেখাতে হয়। C-তে signed overflow undefined behavior; Frama-C-এর মতো C verifier তাই প্রতিটি গাণিতিক কাজের জন্য “overflow হয় না” একটি বাড়তি VC বানায়। Python 3-এর int অসীম, তাই সেখানে গণিতের Int-ই সঠিক model. এক ভাষার প্রমাণ আরেক ভাষার জন্য খাটে না।
৫ · Loop invariant আর variant — ছাড়ের loop
বাজারঘরের অর্ডারে n টি একই পণ্য, প্রতিটির দাম unit টাকা। দাম যোগ হয় একটি loop-এ, তারপর মোট ১০০০ বা তার বেশি হলে ১০% ছাড়:
// বাজারঘর: n টি পণ্য, প্রতিটির দাম unit; মোট ১০০০ বা তার বেশি হলে ১০% ছাড়
let n = 2;
let unit = 520;
var i = 0;
var total = 0;
while i < n {
total = total + unit;
i = i + 1;
}
if total >= 1000 {
total = total - total / 10;
}
print(total);Reference-এ সত্যিকারের run: python haat.py run discount.haat ছাপে 936 (দুটি ৫২০ টাকার পণ্য, ১০৪০, তাতে ১০৪ টাকা ছাড়; bazar.haat-এর price(2, 520)-এর সমান)। দাবি: n ≥ 0 আর unit ≥ 0 হলে বিল কখনো ঋণাত্মক নয়, আর ছাড়ের আগের মোটের বেশি নয়, অর্থাৎ Q = 0 ≤ total ≤ n · unit. আর loop অবশ্যই থামে।
Invariant কীভাবে খুঁজবেন? বাজারের ফর্দের কথা ভাবুন। প্রতিটি পণ্য ব্যাগে তোলার পর দোকানি হিসাব মেলান: “এ পর্যন্ত যতগুলো তুলেছি, ততগুলোর দাম যোগ হয়েছে।” এই কথাটিই invariant: total == i · unit. সঙ্গে আরও দুটি সত্য লাগে, যা loop-এর শেষ অবস্থা বোঝাতে দরকার: 0 ≤ i ≤ n (তোলা পণ্য কখনো ফর্দের বেশি নয়) আর unit ≥ 0 (দাম ঋণাত্মক নয়; loop unit বদলায় না, কিন্তু loop-এর ভেতরের যুক্তি precondition মনে রাখে না, তাই কথাটি invariant-এ বয়ে নিতে হয়)।
থামার প্রমাণে লাগে একটি variant function V: একটি পূর্ণসংখ্যা, যা invariant আর শর্ত সত্য থাকলে ঋণাত্মক নয়, আর প্রতি ঘোরায় কঠোরভাবে কমে। পূর্ণসংখ্যা অসীমভাবে নিচে নামতে পারে না, তাই loop থামে। এখানে V = n − i, “ফর্দে বাকি পণ্যের সংখ্যা”। Total correctness-এর নিয়মটি:
এখানে v0 একটি নতুন নাম, “এই ঘোরার শুরুতে V-এর মান”। I ⇒ def(b) নিশ্চিত করে যে শর্ত হিসাব করতেই error হবে না। পুরো loop-এর প্রমাণ এখন চারটি দায় (VC): শুরুতে I সত্য (init), এক ঘোরায় I টিকে থাকে (preserve), শেষে I ∧ ¬b থেকে বাকি program-এর পরে Q (exit), আর V কমে কিন্তু শূন্যের নিচে যায় না (variant).
0{ n ≥ 0 ∧ unit ≥ 0 }1i = 0; total = 0;2while i < n { // I, V3 total = total + unit;4 i = i + 1; }5if total ≥ 1000 { ছাড় }6{ 0 ≤ total ≤ n·unit }
| দায় | |
| যুক্তি | |
| উদাহরণে |
- Invariant বেছে নেওয়া। I = total == i·unit ∧ 0 ≤ i ≤ n ∧ unit ≥ 0, আর variant V = n − i. এগুলো programmer-এর দেওয়া annotation; wp এদের নিজে খুঁজে পায় না। উদাহরণের জন্য n = 2, unit = 520.
- Init. P ⇒ wp(i = 0; total = 0;, I). Substitution-এর পরে: 0 == 0·unit ∧ 0 ≤ 0 ≤ n ∧ unit ≥ 0. প্রথমটি সবসময় সত্য, বাকি দুটি P থেকে। উদাহরণে i = 0, total = 0, I সত্য।
- Preserve. I ∧ i < n ⇒ wp(দেহ, I). দেহের দুই assignment পেছন থেকে বসালে: total + unit == (i + 1)·unit, যা total == i·unit থেকে সরাসরি; আর i < n থেকে i + 1 ≤ n. উদাহরণে (i, total) জোড়া (0, 0) থেকে (1, 520), তারপর (2, 1040); প্রতিবার I সত্য।
- Exit. I ∧ ¬(i < n): i ≥ n আর i ≤ n, তাই i = n, ফলে total = n·unit, আর unit ≥ 0 থেকে total ≥ 0. তারপর if-এর wp: ছাড় হলে t − t/10, যা 0 আর t-এর মাঝে; না হলে t নিজেই। দুই শাখাতেই Q. উদাহরণে 1040 ≥ 1000, তাই 936.
- Variant. I-তে i ≤ n, তাই V = n − i ≥ 0. দেহে i বাড়ে ১, তাই V কমে ঠিক ১: wp(দেহ, V < v0) = n − (i + 1) < n − i, সবসময় সত্য। উদাহরণে V: 2, 1, 0, তারপর শর্ত মিথ্যা।
- ফল। চারটি দায় পূর্ণ, তাই H-WhileT, H-Seq আর H-If জুড়ে [n ≥ 0 ∧ unit ≥ 0] program [0 ≤ total ≤ n·unit]: থামে, আর বিল ঠিক সীমার ভেতরে। Reference-এর ছাপা 936 এর একটি উদাহরণ মাত্র; প্রমাণটি সব n আর unit-এর জন্য, গণিতের Int-এ।
প্রমাণের আগে চালিয়ে দেখা সস্তা আর কাজের: প্রতি ঘোরার শুরুতে invariant assert করা। কিন্তু চালানো শুধু যে state-গুলো আসলে আসে সেগুলো দেখে। VC আরও কড়া: invariant সত্য এমন যেকোনো state-এ দায়গুলো খাটতে হবে। নিচের block দুটিই করে, আর দুটি “প্রায় ঠিক” invariant-ও পরীক্ষা করে।
# ছাড়ের loop: invariant চালিয়ে দেখা, তারপর চারটি VC ছোট পরিসরের সব অবস্থায়
from itertools import product
def body(s): return {**s, "total": s["total"] + s["unit"], "i": s["i"] + 1}
def tail(s): # loop-এর পরের if: ১০% ছাড়
t = s["total"]; return {**s, "total": t - cdiv(t, 10) if t >= 1000 else t}
P = lambda s: s["n"] >= 0 and s["unit"] >= 0
POST = lambda s: 0 <= s["total"] <= s["n"] * s["unit"]
B = lambda s: s["i"] < s["n"]
V = lambda s: s["n"] - s["i"] # variant: বাকি পণ্যের সংখ্যা
INV = {"total == i*unit && 0 <= i && i <= n && unit >= 0":
lambda s: s["total"] == s["i"] * s["unit"] and 0 <= s["i"] <= s["n"] and s["unit"] >= 0,
"unit >= 0 বাদ": lambda s: s["total"] == s["i"] * s["unit"] and 0 <= s["i"] <= s["n"],
"i <= n বাদ": lambda s: s["total"] == s["i"] * s["unit"] and 0 <= s["i"] and s["unit"] >= 0}
I = INV["total == i*unit && 0 <= i && i <= n && unit >= 0"]
checks = 0
for n, unit in product(range(0, 40), range(0, 300, 7)): # চালিয়ে: প্রতি ঘোরার শুরুতে assert
s = {"n": n, "unit": unit, "i": 0, "total": 0}
while True:
assert I(s), s; checks += 1
if not B(s): break
v = V(s); s = body(s); assert 0 <= V(s) < v
assert POST(tail(s)), s
print("চালিয়ে দেখা: invariant আর variant", checks, "বার যাচাই, একটিও ভাঙেনি")
VC = {"init": lambda s: not P(s) or I({**s, "i": 0, "total": 0}),
"preserve": lambda s: not (I(s) and B(s)) or I(body(s)),
"exit": lambda s: not (I(s) and not B(s)) or POST(tail(s)),
"variant": lambda s: not (I(s) and B(s)) or 0 <= V(body(s)) < V(s)}
R = range(-3, 10)
states = [dict(n=n, unit=u, i=i, total=t) for n, u, i in product(R, R, R) for t in range(-30, 31)]
for name, I in INV.items():
print("I:", name)
for vc, f in VC.items():
bad = next((s for s in states if not f(s)), None)
print(f" {vc:9}", "সত্য" if bad is None else f"ভাঙল: {bad}")আসল আউটপুট (ব্রাউজারের Python):
চালিয়ে দেখা: invariant আর variant 35260 বার যাচাই, একটিও ভাঙেনি
I: total == i*unit && 0 <= i && i <= n && unit >= 0
init সত্য
preserve সত্য
exit সত্য
variant সত্য
I: unit >= 0 বাদ
init সত্য
preserve সত্য
exit ভাঙল: {'n': 1, 'unit': -3, 'i': 1, 'total': -3}
variant সত্য
I: i <= n বাদ
init সত্য
preserve সত্য
exit ভাঙল: {'n': -3, 'unit': 1, 'i': 0, 'total': 0}
variant সত্য
৪০টি n আর ৪৩টি unit-এর সব জোড়ায় loop চালিয়ে ৩৫,২৬০ বার invariant আর variant যাচাই হয়েছে, আর প্রতিটি শেষে Q; কিছুই ভাঙেনি। তারপর −3 থেকে 9 পর্যন্ত n, unit, i আর −30 থেকে 30 পর্যন্ত total-এর সব state-এ চারটি VC: পূর্ণ invariant-এ চারটিই সত্য। unit >= 0 বাদ দিলে exit ভাঙে: n = 1, unit = −3, i = 1, total = −3. i <= n বাদ দিলেও exit ভাঙে, যদিও লেখকের lab-এ একই চালানোয় loop-এর মাথার ৩৫,২৬০টি যাচাইয়ে এই দুর্বল invariant-ও একবারও মিথ্যা হয়নি। অর্থাৎ চালিয়ে দেখা ভুলটি ধরতে পারত না; VC পেরেছে।
৬ · Verification condition আর Z3 — Haat source থেকে প্রমাণ
অংশ ৫-এর চারটি দায় হাতে লেখা হয়েছিল। Dafny, Why3 বা Frama-C-এর মতো verifier এগুলো নিজে বানায়: annotation-সহ program থেকে VC, তারপর SMT solver. Haat-এর জন্য সেই কাজটি করে লেখকের vcgen.py; নিচে তার মূল function, হুবহু। expr একটি Haat expression-কে Z3-এর term আর তার def-এ বদলায়; substitute হলো Z3-এর নিজের Q[e/x]. Loop পেলে generator চারটি VC জমা রাখে (সঙ্গে “guard ok”, অর্থাৎ I ⇒ def(b)), আর loop-এর জায়গায় wp হিসেবে ফেরত দেয় I.
# vcgen.py-এর মূল অংশ: একটি Haat statement-এর wp, Z3-এর term হিসেবে
def wp1(s, Q, ann, inputs):
if isinstance(s, Let) and s.name in inputs: return Q # symbolic input
if isinstance(s, (Let, Assign)):
e, d = expr(s.init if isinstance(s, Let) else s.value)
return And(d, substitute(Q, (var(s.name), e)))
if isinstance(s, Print): return And(expr(s.value)[1], Q)
if isinstance(s, Block): return wp(s.stmts, Q, ann, inputs)
if isinstance(s, If):
b, d = expr(s.cond)
S2 = Q if s.else_ is None else wp1(s.else_, Q, ann, inputs)
return And(d, Implies(b, wp1(s.then, Q, ann, inputs)), Implies(Not(b), S2))
if isinstance(s, While):
I, V = (cond(x) for x in ann.pop()) # loops from the end
b, d = expr(s.cond)
v0 = var("V0")
VCS.append(("preserve", Implies(And(I, b), wp1(s.body, I, [], inputs))))
VCS.append(("exit ", Implies(And(I, Not(b)), Q)))
VCS.append(("guard ok", Implies(I, d)))
VCS.append(("variant ", Implies(And(I, b), And(V >= num(0),
substitute(wp1(s.body, V < v0, [], inputs), (v0, V))))))
return I
raise ValueError(f"not Haat-core: {type(s).__name__}")এবার ছাড়ের loop, পাঁচ রকম চেষ্টায়। প্রতিটি চেষ্টায় postcondition একই, শুধু invariant বা সংখ্যার জগৎ আলাদা। সত্যিকারের run (একই lab, একই version):
~/haat-verify $ uv run python verify_discount.py
(1) [int] I = total == i * unit && 0 <= i && i <= n
init valid
preserve valid
exit FAILS {'unit': -1, 'n': 10, 'i': 10, 'total': -10}
guard ok valid
variant valid
(2) [int] I = total == i * unit && 0 <= i && i <= n && unit >= 0
init valid
preserve valid
exit valid
guard ok valid
variant valid
(3) [int] I = total == i * unit && 0 <= i && unit >= 0
init valid
preserve valid
exit FAILS {'unit': 1, 'n': 908, 'i': 1009, 'total': 1009}
guard ok valid
variant valid
(4) [bv64] I = total == i * unit && 0 <= i && i <= n && unit >= 0
init valid
preserve valid
exit FAILS {'unit': 7917505528869928069, 'n': 3568109576614234620, 'i': 3568109576614234620, 'total': -3072290497149272084}
guard ok valid
variant valid
(5) [bv64] P and I also get: n <= 1000 && unit <= 1000000
init valid
preserve valid
exit valid
guard ok valid
variant valid
(১) প্রথম চেষ্টায় invariant-এ unit ≥ 0 নেই, আর Z3 সঙ্গে সঙ্গে exit-এ counterexample দেয়: unit = −1, n = i = 10, total = −10. (২) unit ≥ 0 যোগ করলে পাঁচটি VC-ই valid: গণিতের Int-এ total correctness প্রমাণিত, অংশ ৫-এর হাতের প্রমাণের যন্ত্র-রূপ। (৩) i ≤ n বাদ দিলে exit ভাঙে, নিচের stepper-এ বিস্তারিত। (৪) একই সঠিক invariant 64-bit-এ: init, preserve আর variant টিকে থাকে, কারণ total == i·unit wrap-সহ গুণেও সত্য থাকে (দুই দিকই একই modulo হিসাব)। কিন্তু exit ভাঙে: n·unit wrap হয়ে ঋণাত্মক, ছাড়ের শর্ত মিথ্যা, বিল ঋণাত্মক। Python-এ হিসাব মিলিয়ে দেখা হয়েছে: 3568109576614234620 × 7917505528869928069 wrap করলে ঠিক −3072290497149272084. (৫) precondition আর invariant-এ বাস্তব সীমা যোগ করতেই 64-bit-এও সব valid.
1I′ = total == i·unit2 ∧ 0 ≤ i ∧ unit ≥ 03 (∧ i ≤ n বাদ পড়েছে)4init, preserve5exit: I′ ∧ i ≥ n ⇒ wp(if, Q)
| ধাপ | |
| state | |
| ফল |
- প্রস্তাব। I′ দেখতে যুক্তিসঙ্গত, আর লেখকের lab-এ আসল চালানোয় loop-এর মাথার ৩৫,২৬০টি যাচাইয়ের প্রতিটিতে সত্য ছিল। Testing-এর চোখে কোনো সমস্যা নেই।
- Init. শুরুতে i = 0, total = 0: 0 == 0·unit, 0 ≤ 0, আর P থেকে unit ≥ 0. দায় পূর্ণ।
- Preserve. total + unit == (i + 1)·unit আর 0 ≤ i + 1, I′ থেকেই। দায় পূর্ণ; i ≤ n না থাকায় এখানে কিছু হারায়নি।
- Exit, ছোট পরিসরে। VC বলে: I′ সত্য আর i < n মিথ্যা এমন যেকোনো state-এ ছাড়ের পরে Q. Block-এর brute force পায় n = −3, unit = 1, i = 0, total = 0: I′ সত্য, শর্ত মিথ্যা, কিন্তু Q চায় 0 ≤ n·unit = −3. “এমন state তো কখনো আসে না!” ঠিক, কিন্তু VC সেটি জানে না: loop-এর পরে যা জানা, তা শুধু I′ ∧ ¬b.
- Exit, Z3-এ। সব পূর্ণসংখ্যায় খুঁজে Z3 দেয় n = 908, i = 1009, unit = 1, total = 1009: i, n-কে ছাড়িয়ে গেছে। ১০০৯ ≥ ১০০০, তাই ছাড়ের পরে 1009 − 100 = 909, যা n·unit = 908-এর বেশি। এখানে কারণটি স্পষ্ট: i ≤ n ছাড়া i ≥ n থেকে i = n পাওয়া যায় না।
- সংশোধন। i ≤ n ফিরিয়ে দিলে exit-এ i ≥ n ∧ i ≤ n ⇒ i = n, আর ওপরের run-এর (২) নম্বরে পাঁচটি VC-ই valid. শিক্ষা: invariant শুধু “সত্য” হলে চলে না, loop-এর পরের যুক্তির জন্য যথেষ্ট শক্ত হতে হয়।
এখানে একটি সীমাও দেখা দরকার। লেখকের lab-এ অনুশীলন ৪-এর যোগফলের loop (2·s == i·(i + 1)) গণিতের Int-এ সঙ্গে সঙ্গে প্রমাণিত, কিন্তু 64-bit-এ preserve আর exit-এর VC-তে Z3 ৬০ সেকেন্ডের সময়সীমায় উত্তর দেয়নি: ফল unknown. Bit-vector-এ গুণ আর ভাগ (nonlinear) solver-এর পক্ষে কঠিন; “unknown” প্রমাণও নয়, counterexample-ও নয়। বাস্তব verifier-গুলো তাই সাহায্যকারী lemma, সীমা বা অন্যভাবে লেখা VC নিয়ে কাজ করে।
৭ · Soundness, completeness আর সীমা
নিয়মগুলো আমরা বিশ্বাস করেছি। কিন্তু একটি ভুল নিয়ম (যেমন H-While-এ ¬b বাদ পড়া বা H-Assign সামনের দিকে) মিথ্যা দাবি “প্রমাণ” করে ফেলবে। তাই প্রথম প্রশ্ন: প্রমাণযোগ্য সবকিছু কি সত্য?
⊢ {P} S {Q} হলে ⊨ {P} S {Q}: নিয়ম দিয়ে প্রমাণ করা প্রতিটি triple big-step semantics-এ সত্য।
প্রমাণ ⊢ {P} S {Q}-এর derivation-এর ওপর induction (পর্ব ৩৮-এর induction on derivations-এর মতো), শেষ নিয়ম ধরে case. H-Skip, H-Print আর H-Assign সরাসরি: B-Skip state বদলায় না, B-Print variable বদলায় না, আর H-Assign-এর জন্য Theorem ৪২.১-এর substitution lemma. H-Seq আর H-If-এ দুই premise-এ IH, তারপর B-Seq, B-IfT বা B-IfF. H-Cons-এ দুটি implication দুই প্রান্তে বসে। কঠিন case H-While:
- Premise থেকে IH: ⊨ {I ∧ b} S {I}. দেখাতে হবে: σ ⊨ I আর ⟨while b { S }, σ⟩ ⇓ σ″ হলে σ″ ⊨ I ∧ ¬b.
- এবার ⟨while b { S }, σ⟩ ⇓ σ″-এর big-step derivation-এর ওপর দ্বিতীয় একটি induction. Loop থেমেছে বলেই এই derivation সসীম, তাই induction চলে।
- শেষ নিয়ম B-WhileF হলে ⟨b, σ⟩ ⇓ false আর σ″ = σ. তাই σ″ ⊨ I (ধরে নেওয়া) আর σ″ ⊨ ¬b.
- শেষ নিয়ম B-WhileT হলে ⟨b, σ⟩ ⇓ true, ⟨S, σ⟩ ⇓ σ′ আর ⟨while b { S }, σ′⟩ ⇓ σ″. প্রথম দুটি থেকে σ ⊨ I ∧ b, তাই বাইরের IH বলে σ′ ⊨ I.
- তৃতীয় premise একটি ছোট derivation, আর σ′ ⊨ I; ভেতরের IH দিয়ে σ″ ⊨ I ∧ ¬b. ∎
লক্ষ করুন ধাপ ২: যুক্তি loop-এর সসীম চলার ওপর। Loop না থামলে কোনো ⇓ derivation নেই, দাবির কিছু যায় আসে না, ঠিক partial correctness-এর সংজ্ঞা। একই ছকে H-WhileT-এর soundness প্রমাণে V-এর ওপর well-founded induction লাগে, কারণ সেখানে থামা নিজেই প্রমাণের বিষয়।
উল্টো দিক, completeness: প্রতিটি সত্য triple কি প্রমাণযোগ্য? পুরোপুরি নয়, আর বাধাটি program-এ নয়, গণিতে। H-Cons-এর P ⇒ P′ পূর্ণসংখ্যার গাণিতিক বাক্য, আর Gödel-এর incompleteness theorem বলে পূর্ণসংখ্যার সব সত্য বাক্য কোনো সসীম axiom-তালিকা থেকে আসে না। Stephen Cook ১৯৭৮ সালে দেখান, এই অংশটুকু একটি “oracle”-এর হাতে দিলে বাকি নিয়মগুলো সম্পূর্ণ: এর নাম relative completeness, আর শর্ত হলো assertion-এর ভাষা যথেষ্ট প্রকাশক্ষম, যাতে প্রতিটি loop-এর দরকারি invariant লেখা যায়। Edmund Clarke ১৯৭৯ সালে দেখান, কিছু ভাষা-বৈশিষ্ট্যের মিলন (যেমন parameter হিসেবে procedure পাঠানো, recursion, static scope আর global variable একসঙ্গে) থাকলে এমন sound আর relatively complete Hoare logic থাকতেই পারে না।
আর বাস্তবের সীমা: wp loop পেরোতে পারে না, invariant লাগে, আর একটি loop-এর যথেষ্ট invariant খুঁজে বের করা সাধারণভাবে undecidable. এটি Rice-এর theorem-এর আরেক চেহারা (Theory of Computation-এর পর্ব ৫৩)। তাই tool-গুলো আংশিক কৌশলে invariant খোঁজে, যেমন abstract interpretation (Theory of Computation-এর পর্ব ৭৮), আর না পারলে programmer-এর কাছে চায়।
আরও গভীরে। Pointer আর heap এলে H-Assign ভেঙে পড়ে: *p = 5 কোন নামের মান বদলাল, তা aliasing-এর ওপর নির্ভর করে। John Reynolds, Peter O'Hearn আর Hongseok Yang ২০০১–২০০২ সালের কাজে separation logic দেন, যার “frame rule” প্রমাণকে heap-এর ছোট অংশে সীমিত রাখে; এর ওপর ভিত্তি করে Infer-এর মতো open-source analyzer লাখো লাইনের কোডে চলে বলে জানা যায়। আজকের verifier-গুলো (Dafny, Why3, Frama-C-এর WP plugin, SPARK) মূলত এই পর্বের wp-VC-SMT পাইপলাইন, সঙ্গে function-এর জন্য requires/ensures চুক্তি। পর্ব ৪৪-এ (Formal verification) proof assistant আর verified compiler আসবে।
পরীক্ষা ও ইন্টারভিউতে। বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রচলিত:
- “wp(x = x + 1; y = 2 * x;, y > 10) কত?” পেছন থেকে: 2 * x > 10, তারপর 2 * (x + 1) > 10, অর্থাৎ ℤ-এ x > 4.
- “Partial আর total correctness-এর পার্থক্য?” Partial: থামলে Q; total: থামবে আর Q. দ্বিতীয়টিতে variant লাগে।
- “Loop invariant-এর তিনটি দায় কী?” শুরুতে সত্য, এক ঘোরায় টিকে থাকে, শেষে ¬b-সহ postcondition দেয়; সঙ্গে থামার জন্য variant.
- “Assignment নিয়ম পেছন থেকে কেন?” Q[e/x]-এ substitution-ই যথেষ্ট; সামনের দিকে পুরোনো মানের জন্য ∃ লাগে।
- “Soundness আর completeness?” Sound: প্রমাণযোগ্য সব সত্য। Complete শুধু আপেক্ষিকভাবে (Cook ১৯৭৮), কারণ পূর্ণসংখ্যার গণিত নিজেই incomplete.
৮ · AI-এর যুগে axiomatic semantics
আজ AI assistant-কে কোড দিলে সে প্রায়ই “invariant” আর “প্রমাণ” লিখে দেয়। ভাষা ঝরঝরে, কিন্তু Hoare logic-এ ছোট একটি ফাঁকই পুরো প্রমাণ বাতিল করে। সুখবর হলো, এই বিষয়ে AI-এর দাবি যন্ত্রে যাচাই করা সহজ: invariant-টি VC-তে বসিয়ে Z3 চালালেই হয়।
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| Invariant “সত্য” কিন্তু যথেষ্ট শক্ত নয় (যেমন i ≤ n বা unit ≥ 0 বাদ) | চারটি VC আলাদা করে Z3-এ; exit-এর counterexample দেখা |
| গণিতের পূর্ণসংখ্যা ধরে প্রমাণ, অথচ ভাষায় 64-bit wrap বা C-র UB | ভাষা আর version উল্লেখ করে BitVec দিয়ে আবার চালানো |
| Assignment নিয়ম সামনের দিকে খাটানো, বা substitution-এ একটি জায়গা বাদ | ছোট wp calculator-এ একই হিসাব, আর state-এর grid-এ চালিয়ে মেলানো |
| শূন্য দিয়ে ভাগ বা short-circuit-এর def(e) ভুলে যাওয়া | প্রতিটি / আর %-এর জন্য ভাজক ≠ 0 আছে কি না খোঁজা |
| “Test পাস, তাই প্রমাণিত” বা partial-কে total বলে দাবি | Variant আছে কি না দেখা; অসীম loop-এর উদাহরণ খোঁজা |
Z3-এর unknown-কে “প্রমাণিত” পড়া | শুধু unsat (valid) মানেই প্রমাণ; সময়সীমা আর ফল দুটোই লিখে রাখা |
AI-কে কাজে লাগাতে ভাষার semantics আর চাওয়া রূপ পরিষ্কার দিন:
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Hoare ১৯৬৯ সালের paper-এর শিরোনামে “axiomatic basis” বলেছিলেন। তিনি কি শুধু প্রমাণের কৌশল চেয়েছিলেন, নাকি ভাষার সংজ্ঞাই?
Hoare-এর paper পড়লে বোঝা যায়, তাঁর লক্ষ্য দুটি ছিল। প্রথমটি পরিচিত: program সঠিক কি না, তা গণিতের মতো প্রমাণ করা। দ্বিতীয়টি আজ কম আলোচিত: ভাষার সংজ্ঞা axiom আর নিয়ম দিয়ে দেওয়া। তাঁর যুক্তি ছিল, একটি ভাষার বাস্তবায়ন যন্ত্রভেদে আলাদা হতে পারে, কিন্তু programmer-এর যা জানা দরকার তা হলো কোন দাবি নিরাপদে করা যায়। নিয়মের তালিকায় যা নেই, সে বিষয়ে বাস্তবায়নকারী স্বাধীন। তাই paper-টি integer overflow-এর মতো প্রশ্নে কয়েকটি বিকল্প axiom রেখেছিল: কোনটি বাছা হবে, তা ভাষা-নকশার সিদ্ধান্ত।
এই ভাবনার একটি বাস্তব প্রয়োগ হয়েছিল। ১৯৭৩ সালে Hoare আর Niklaus Wirth “An axiomatic definition of the programming language PASCAL” প্রকাশ করেন, যেখানে Pascal-এর বড় অংশের অর্থ Hoare-ধাঁচের নিয়মে দেওয়া হয়। কিন্তু পূর্ণ ভাষার জন্য এই পথ কঠিন প্রমাণিত হয়: goto, procedure-এর parameter, aliasing আর side effect-ওয়ালা expression-এর নিয়ম জটিল, আর কিছু ক্ষেত্রে অসম্ভব (অংশ ৭-এর Clarke-এর ফল)। আজ ভাষার মূল সংজ্ঞা সাধারণত operational semantics-এ লেখা হয়, যেমন WebAssembly-র spec বা Standard ML-এর সংজ্ঞা।
তবু Hoare-এর দ্বিতীয় লক্ষ্যটি অন্য চেহারায় বেঁচে আছে। Haat-এর README-র “Spec decisions”-এর অনেকগুলো আসলে একটি axiomatic প্রশ্নের উত্তর: কোন দাবি সত্য বলে programmer ধরতে পারেন? সিদ্ধান্ত ৯ (assignment statement) না থাকলে এই পর্বের H-Assign খাটত না, কারণ expression-এর ভেতরে state বদলাত। সিদ্ধান্ত ১৩ (wrap) ঠিক করে দিল কোন সংখ্যার model দিয়ে প্রমাণ করতে হবে। এক অর্থে ভাষা-নকশাকারী প্রতিটি সিদ্ধান্তে ঠিক করছেন, কোন Hoare নিয়ম সরল থাকবে।
মূল উপলব্ধি: Hoare axiom দিয়ে ভাষা সংজ্ঞায়িত করতে চেয়েছিলেন; পূর্ণ ভাষার সংজ্ঞায় সেই পথ জেতেনি, কিন্তু “কোন দাবি সরল নিয়মে প্রমাণ করা যায়” প্রশ্নটি আজও ভালো ভাষা-নকশার একটি মাপকাঠি।
প্র ০২Dijkstra শুধু প্রমাণ নয়, wp দিয়ে program “বের করা” (derivation) প্রস্তাব করেছিলেন। পেছন থেকে ভাবা program লেখায় কীভাবে সাহায্য করে?
Dijkstra-র ১৯৭৫ সালের লেখা আর ১৯৭৬ সালের বই A Discipline of Programming-এর মূল দাবি ছিল: আগে program লিখে পরে প্রমাণ খোঁজা উল্টো ক্রম। ভালো ক্রম হলো আগে postcondition, তারপর wp দেখে ঠিক করা কোন statement সেখানে পৌঁছায়। তিনি wp-কে একটি predicate transformer বলেছিলেন: প্রতিটি statement একটি শর্তকে আরেকটি শর্তে বদলায়, আর program-এর অর্থ এই বদলের function. এই চোখে দেখলে program-এর অংশ বেছে নেওয়া একটি হিসাবের কাজ।
একটি ছোট উদাহরণ। চাই total ≥ 60, আর জানি total শেষে p − d + 60 হবে। তাহলে দরকার p − d ≥ 0, অর্থাৎ ছাড় d কখনো দামের বেশি নয়। এই দাবি থেকে সরাসরি বোঝা যায় d-এর জন্য কোন সূত্র নিরাপদ (p / 10 ঋণাত্মক-নয় p-তে), কোনটি নয় (যেমন একটি নির্দিষ্ট ১০০ টাকা ছাড়, যা ৫০ টাকার পণ্যে বিল ঋণাত্মক করে)। Loop-এর ক্ষেত্রে কৌশলটি আরও শক্তিশালী: postcondition থেকে একটি অংশ “ঢিলে” করে invariant বানানো (যেমন total == n·unit থেকে n-এর জায়গায় i বসিয়ে total == i·unit), তারপর loop-এর দেহ এমনভাবে লেখা যাতে invariant টিকে থাকে আর variant কমে। Dijkstra-র ভাষায়, program আর তার প্রমাণ একসঙ্গে বড় হয়।
এই ধারার আরেকটি বৈশিষ্ট্য ছিল guarded command: কয়েকটি শর্ত-কাজের জোড়া, যেখানে একাধিক শর্ত সত্য হলে যেকোনোটি চলতে পারে (nondeterminism). লক্ষ্য ছিল programmer-কে অপ্রয়োজনীয় ক্রম বেঁধে দেওয়া থেকে মুক্ত রাখা। পরে David Gries-এর The Science of Programming (১৯৮১) এই পদ্ধতিকে পাঠ্যবইয়ের রূপ দেয়। আজ পুরো program এভাবে খুব কম লেখা হয়, কিন্তু loop লেখার আগে invariant ভাবার অভ্যাস binary search-এর মতো জায়গায় off-by-one ভুল প্রায় দূর করে।
মূল উপলব্ধি: wp প্রমাণের পাশাপাশি নকশার যন্ত্র: postcondition থেকে পেছনে হাঁটলে বোঝা যায় কোন statement দরকার, আর postcondition ঢিলে করে invariant পাওয়া loop লেখার একটি নির্ভরযোগ্য কৌশল।
প্র ০৩Binary search-এ mid = (low + high) / 2 বহু বছর পাঠ্যবই আর library-তে ছিল। Overflow-এর গল্প Hoare logic সম্পর্কে কী শেখায়?
Binary search-এর সঠিকতার প্রমাণ পাঠ্যবইয়ের প্রিয় উদাহরণ: invariant “খোঁজা মান থাকলে low আর high-এর মাঝে আছে”, variant high − low. প্রমাণটি গণিতের পূর্ণসংখ্যায় নিখুঁত। কিন্তু Joshua Bloch ২০০৬ সালে একটি লেখায় দেখান যে Java-র standard library-র Arrays.binarySearch-এ প্রায় নয় বছর ধরে একটি bug ছিল: array-তে প্রায় 230-এর বেশি উপাদান হলে low + high 32-bit int-এ overflow করে ঋণাত্মক হয়, আর mid ঋণাত্মক index হয়ে exception দেয়। একই ধাঁচ বহু পুরোনো বই আর বাস্তবায়নেও ছিল বলে তিনি উল্লেখ করেন। সমাধান সরল: low + (high - low) / 2, বা Java-তে (low + high) >>> 1.
শিক্ষাটি অংশ ৪-এর মতোই: প্রমাণ যে সংখ্যার model ধরে, সেটি ভাষার model না হলে প্রমাণ যন্ত্রের জন্য মিথ্যা নিশ্চয়তা দেয়। প্রমাণে ভুল ছিল না; ভুল ছিল অনুমানে, যে ধাপটি “নিশ্চয়ই সত্য” মনে হয়েছিল। এই পর্বের বিলের উদাহরণেও p ≥ 0 ধাপটি ছিল এমন। বড় array তখন বিরল ছিল, তাই test-এ কখনো ধরা পড়েনি; ভুলটি দেখা দিল যখন memory সস্তা হয়ে বড় array সাধারণ হলো।
আজকের verifier এই শিক্ষা মেনে নকশা করা। SPARK (Ada-র যাচাইযোগ্য উপভাষা) প্রতিটি গাণিতিক কাজের জন্য “overflow হয় না” প্রমাণ দাবি করে। Frama-C আর C-র জন্য একই কাজ করে, কারণ C-তে signed overflow UB. Dafny-র int গণিতের অসীম পূর্ণসংখ্যা, আর সীমাবদ্ধ type ব্যবহার করলে আলাদা দায় আসে। Haat-এর মতো wrap-করা ভাষায় দুটি পথ: bit-vector-এ প্রমাণ (অংশ ৬-এর run (৫)), বা প্রতিটি কাজে “ফল সীমার ভেতরে” দেখানো, যাতে গণিতের Int-এর প্রমাণই খাটে।
মূল উপলব্ধি: Hoare logic-এর প্রমাণ শুধু ততটা সঠিক, যতটা তার assertion-এর গণিত ভাষার আসল অর্থের সঙ্গে মেলে; 64-bit আর 32-bit জগতে “স্পষ্টতই সত্য” ধাপগুলোই সবচেয়ে বিপজ্জনক।
প্র ০৪Invariant খোঁজা সাধারণভাবে undecidable. তাহলে Dafny-র মতো tool বাস্তবে কাজ করে কীভাবে, আর AI এখানে কী ভূমিকা নিতে পারে?
অংশ ৭-এর কথা আবার: কোনো algorithm প্রতিটি loop-এর জন্য যথেষ্ট invariant খুঁজে দিতে পারে না, কারণ তা করতে পারলে program-এর আচরণ সম্পর্কে Rice-এর theorem-এ নিষিদ্ধ প্রশ্নের উত্তর মিলত। কিন্তু undecidable মানে “কখনো পারা যায় না” নয়; মানে “সবসময় পারা যায় না”। বাস্তব tool-গুলো তাই একটি শ্রমবিভাগ মেনে চলে: যা যান্ত্রিক (wp, VC, SMT), তা যন্ত্র করে; যা সৃজনশীল (invariant, variant, সাহায্যকারী lemma), তা programmer দেন, আর যন্ত্র তা যাচাই করে।
Dafny এর ভালো উদাহরণ। K. Rustan M. Leino ২০০৯ সালের দিকে ভাষাটি শুরু করেন; programmer requires, ensures আর invariant লেখেন, আর Dafny ভেতরে Boogie নামের একটি মধ্যবর্তী ভাষার মাধ্যমে VC বানিয়ে Z3-কে দেয়। কিছু সহজ invariant (যেমন loop variable-এর সীমা) tool নিজে অনুমান করার চেষ্টা করে; গবেষণায় Houdini (Flanagan আর Leino, ২০০১) নামের একটি কৌশল আছে, যা অনেক প্রার্থী invariant থেকে যেগুলো টেকে না সেগুলো বাদ দিয়ে বাকিগুলো রাখে। Abstract interpretation (ToC পর্ব ৭৮) interval-এর মতো সরল invariant স্বয়ংক্রিয়ভাবে দেয়।
এখানে AI-এর ভূমিকা স্বাভাবিকভাবে আসে: প্রার্থী invariant প্রস্তাব করা। ভুল প্রস্তাব নিরাপদ, কারণ VC যাচাই করে প্রত্যাখ্যান করবে, আর counterexample ফিরিয়ে দিয়ে আবার চেষ্টা করানো যায়, ঠিক অংশ ৬-এর (১) থেকে (২)-এ যাওয়ার মতো। সাম্প্রতিক কয়েক বছরে বড় language model দিয়ে invariant আর Dafny annotation প্রস্তাবের গবেষণা বেড়েছে বলে জানা যায়; সফলতার হার নিয়ে নির্দিষ্ট সংখ্যা এখানে দাবি করছি না। মূল কথা হলো নকশাটি: অনুমানকারী যত অনির্ভরযোগ্যই হোক, শেষ রায় দেয় sound যাচাইকারী।
মূল উপলব্ধি: verifier-এ সৃজনশীল অংশ (invariant) আর যান্ত্রিক অংশ (VC, SMT) আলাদা; প্রথমটি মানুষ, heuristic বা AI প্রস্তাব করতে পারে, কারণ দ্বিতীয়টি প্রতিটি প্রস্তাব নির্মমভাবে যাচাই করে।
প্র ০৫Array বা pointer এলে H-Assign কেন ভাঙে, আর McCarthy-র array theory ও separation logic কীভাবে সমাধান দেয়?
H-Assign-এর সাফল্যের গোপন কথা: assignment-এর পরে কোন নাম বদলাল, তা লেখা দেখেই জানা যায়, শুধু x. Array-তে তা আর সত্য নয়। ধরুন Haat-এর বর্ধিত রূপে array আছে, আর দাবি {a[j] == 5} a[i] = 7; {a[j] == 5}. সরল substitution বলবে “Q-তে a[i] নেই, তাই Q অপরিবর্তিত”, যা ভুল: i == j হলে a[j]-ও বদলেছে। দুটি নাম একই ঘর দেখাতে পারে, এটিই aliasing, আর পর্ব ১৭-এ closure-এর ভাগ করা variable-এও এর রূপ দেখেছেন।
Array-র জন্য পুরোনো সমাধান: পুরো array-কে একটি মান ভাবা। John McCarthy ১৯৬২ সালের দিকে দুটি কাজের theory দেন, select(a, i) (পড়া) আর store(a, i, v) (লেখার পরের নতুন array), আর একটি মূল নিয়ম: select(store(a, i, v), j) হলো v যদি i == j, নইলে select(a, j). তাহলে a[i] = 7 মানে a ↦ store(a, i, 7), আর H-Assign আবার খাটে: wp = (i == j ? 7 : a[j]) == 5, অর্থাৎ i ≠ j ∧ a[j] == 5. Z3-সহ আধুনিক SMT solver এই array theory সরাসরি বোঝে।
Pointer-ভরা heap-এ (linked list, tree) এই পদ্ধতি ভারী হয়ে যায়: প্রতিটি লেখার পরে প্রমাণে বলতে হয় বাকি সব ঘর অপরিবর্তিত। Reynolds, O'Hearn আর Yang-এর separation logic নতুন সংযোজক ∗ আনে: P ∗ Q মানে heap দুই আলাদা অংশে ভাগ করা যায়, একটিতে P, অন্যটিতে Q. Frame rule বলে, {P} S {Q} প্রমাণিত হলে {P ∗ R} S {Q ∗ R}, যদি S শুধু P-এর অংশ ছোঁয়। ফলে একটি function-এর প্রমাণ শুধু তার ছোঁয়া heap নিয়ে, বাকি পৃথিবী নিয়ে নয়। এই local reasoning-ই বড় কোডে প্রমাণকে সম্ভব করেছে, আর Rust-এর ownership-এর যাচাই নিয়ে গবেষণাতেও (পর্ব ৭৬) এর প্রভাব আছে।
মূল উপলব্ধি: H-Assign সরল কারণ নাম আর ঘর এক-এক; aliasing এলে হয় array-কে মান বানিয়ে select/store-এর theory, নয় separation logic-এর ∗ আর frame rule দিয়ে “কে কোন ঘরের মালিক” প্রমাণে আনতে হয়।
অনুশীলন
প্রথমে নিজে লিখুন বা হিসাব করুন, তারপর উত্তর খুলুন। প্রতিটি উত্তর চালানো কোড দিয়ে যাচাই করা।
-
নকশা ও বাস্তবায়ন — wp calculator-এ while: অংশ ৩-এর wp calculator loop বোঝে না।
("while", b, দেহ, I, V)আকারের annotation-সহ loop যোগ করুন: wp হিসেবে I ফেরত দিন, আর preserve, exit ও variant VC একটি তালিকায় জমা রাখুন। তারপর ছাড়ের পুরো program-এর init VC-সহ চারটি VC অংশ ৫-এর state-এর grid-এ চালান।পুরোনো
wp-কে মুড়ে নতুন নাম দেওয়া হলো; global নামটি বদলানোয় seq আর if-এর ভেতরের ডাকও নতুনটিতে আসে। Variant-এর জন্য দেহের wp হিসাব করা হয়V < v0-এর ওপর, তারপর v0-এর জায়গায় V বসানো হয় (দেহের আগের মান)।base_wp, VCS = wp, [] def wp(S, Q): # global নামটি বদলাল, তাই seq/if-এর ভেতরের ডাকও এখানে আসে if S[0] != "while": return base_wp(S, Q) _, b, body, I, V = S # ("while", শর্ত, দেহ, invariant, variant) VCS.append(("preserve", ("=>", ("&&", I, b), wp(body, I)))) VCS.append(("exit", ("=>", ("&&", I, ("!", b)), Q))) VCS.append(("variant", ("=>", ("&&", I, b), ("&&", (">=", V, 0), sub(wp(body, ("<", V, "v0")), "v0", V))))) return AND(ok(b), I) I = ("&&", ("==", "total", ("*", "i", "unit")), ("&&", ("<=", 0, "i"), ("&&", ("<=", "i", "n"), (">=", "unit", 0))))লেখকের lab-এ (CPython 3.14.4) অংশ ৩ আর ৫-এর block-এর সঙ্গে চালিয়ে আউটপুট (প্রতিটি VC-র সূত্রের প্রথম অংশসহ):
init সত্য | n >= 0 && unit >= 0 => 0 == 0 * unit && (0 <= 0 && (0 <= n && unit >= preserve সত্য | total == i * unit && (0 <= i && (i <= n && unit >= 0)) && i < n => tot exit সত্য | total == i * unit && (0 <= i && (i <= n && unit >= 0)) && !(i < n) => variant সত্য | total == i * unit && (0 <= i && (i <= n && unit >= 0)) && i < n => n -চারটিই সত্য, অংশ ৫-এর হাতে লেখা lambda-র ফলের সঙ্গে মিলে গেল। লক্ষ করুন init-এর সূত্রে ছাড়ের if-সহ পুরো program-এর wp আছে, যা loop-এর জায়গায় I পেয়েছে।
vcgen.pyএকই কাজ Z3-এর term দিয়ে করে। -
ভুল প্রমাণ খুঁজুন: একজন লিখলেন: “দাবি {true}
if x < 0 { y = -x; }{y ≥ 0}. Then-শাখা: H-Assign দিয়ে {−x ≥ 0} y = -x; {y ≥ 0}, আর x < 0 ⇒ −x ≥ 0, তাই H-Cons দিয়ে {true ∧ x < 0} y = -x; {y ≥ 0}. তাই H-If দিয়ে দাবি প্রমাণিত। ∎” (এখানে Haat-core-এর সঙ্গে পর্ব ৪০-এর unary-.) প্রমাণে কয়টি ভুল? প্রতিটির counterexample দিন, আর Haat-এ সঠিক দাবিটি লিখুন।ভুল ১, H-If-এর দ্বিতীয় premise নেই। else নেই মানে else-শাখা skip, আর H-If চায় {true ∧ ¬(x < 0)} skip {y ≥ 0}, অর্থাৎ x ≥ 0 ⇒ y ≥ 0, যা মিথ্যা: y-এর আগের মান যা খুশি। Z3 (গণিতের Int):
{'y': -1, 'x': 1}.ভুল ২, 64-bit wrap. y আগে 0 করে দিলেও (
var y = 0;) then-শাখার “x < 0 ⇒ −x ≥ 0” Haat-এ মিথ্যা: x = −9223372036854775808 হলে −x wrap হয়ে একই সংখ্যা (সিদ্ধান্ত ১৩)। লেখকের lab-এ সত্যিকারের run:[int] y = 0 first: {true} absval {y >= 0} init valid [bv] y = 0 first: {true} absval {y >= 0} init FAILS {'x': -9223372036854775808} ~/haat-verify $ python haat.py run absval.haat # x = -9223372036854775807 - 1 -9223372036854775808সঠিক দাবি: {x != -9223372036854775807 - 1}
y = 0; if x < 0 { y = -x; }{y ≥ 0}. দুটি শাখাই এখন প্রমাণ হয়: else-শাখায় y = 0, then-শাখায় x > INT_MIN থেকে −x ধনাত্মক। Java-রMath.abs(Integer.MIN_VALUE)-ও একই কারণে ঋণাত্মক ফেরত দেয়, আর তাদের documentation-এ তা লেখা আছে। -
হিসাব — wp বের করুন: (ক) wp(
if x > y { m = x; } else { m = y; }, m ≥ x ∧ m ≥ y). (খ) wp(r = n % k; q = n / k;, n == q * k + r), def-সহ। কোনটি কোন precondition-এ valid? (গ) (খ)-এর দাবি কি 64-bit wrap-এও সত্য, এমনকি n = INT_MIN, k = −1-এ?(ক) H-If-এর wp: (x > y ⇒ x ≥ x ∧ x ≥ y) ∧ (¬(x > y) ⇒ y ≥ x ∧ y ≥ y). প্রথম অংশে x ≥ x সত্য আর x > y থেকে x ≥ y; দ্বিতীয়তে ¬(x > y) মানে y ≥ x. তাই wp = true: max সবসময় সঠিক, কোনো শর্ত ছাড়া, wrap-এও (কোনো গাণিতিক কাজ নেই)।
(খ) পেছন থেকে: q-এর জায়গায় n / k, ভাগ আছে তাই k ≠ 0; তারপর r-এর জায়গায় n % k, আবার k ≠ 0. ফল: k ≠ 0 ∧ k ≠ 0 ∧ n == n / k * k + n % k. লেখকের lab-এ
vcgen.pyদিয়ে সত্যিকারের run: precondition true হলে গণিতের Int-এ counterexample{'k': 0}(def ভাঙে), আর precondition k != 0 হলেvalid. অর্থাৎ শূন্য দিয়ে ভাগ না হলে C-ধাঁচের / আর % সবসময় এই সমীকরণ মানে।(গ) n = INT_MIN, k = −1: Haat-এ n / k = INT_MIN আর n % k = 0 (সিদ্ধান্ত ১৩), আর INT_MIN × −1 wrap হয়ে INT_MIN, যোগ 0: সমীকরণ টিকে যায়। অংশ ৩-এর Haat evaluator (
ev)-এ এই state চালিয়েও সত্য আসে। তবে সব 64-bit মানের জন্য Z3-এর bit-vector চেষ্টা ৬০ সেকেন্ডেunknownদিয়েছে (অংশ ৬-এর শেষের সীমা), তাই এখানে দাবিটি যন্ত্র-প্রমাণিত বলছি না; গাণিতিক যুক্তিটি হলো, modulo 264-এ q·k + r == n যেকোনো সঠিক ভাগফল-ভাগশেষ জোড়ায় সত্য থাকে। ব্যবহারিকভাবে reference-এn = -7, k = 2চালালেprint(q * k + r)ছাপে-7. -
প্রমাণ — যোগফলের loop: Haat-core-এ
i = 0; s = 0; while i < n { i = i + 1; s = s + i; }. গণিতের Int-এ [n ≥ 0] program [2·s == n·(n + 1)] প্রমাণ করুন: invariant আর variant দিন, চারটি দায় হাতে দেখান। 64-bit-এ কী বদলায়?I = 2·s == i·(i + 1) ∧ 0 ≤ i ≤ n, V = n − i.
- Init: i = 0, s = 0: 2·0 == 0·1, আর 0 ≤ 0 ≤ n, P থেকে।
- Preserve: দেহের wp পেছন থেকে: s-এর জায়গায় s + i, তারপর i-এর জায়গায় i + 1, ফল 2·(s + i + 1) == (i + 1)(i + 2) ∧ 0 ≤ i + 1 ≤ n. বাঁ পাশ 2s + 2i + 2 = i(i + 1) + 2(i + 1) = (i + 1)(i + 2), I থেকে। আর i < n ⇒ i + 1 ≤ n.
- Exit: i ≥ n ∧ i ≤ n ⇒ i = n, তাই 2·s == n·(n + 1).
- Variant: I থেকে n − i ≥ 0, আর দেহে i ঠিক ১ বাড়ে, তাই V ঠিক ১ কমে। ∎
লেখকের lab-এ
vcgen.py-এর সত্যিকারের run: গণিতের Int-এ init, preserve, exit, guard ok আর variant পাঁচটিইvalid. 64-bit-এ init, guard ok আর variant valid, কিন্তু preserve আর exit-এ ৬০ সেকেন্ডেunknown. অর্থে বদলায়ও: n বড় হলে n·(n + 1) আর s দুটিই wrap করে; সমীকরণটি modulo 264-এ টিকে থাকে, কিন্তু s তখন আর আসল যোগফল নয়। আসল যোগফল চাইলে precondition-এ n-এর সীমা লাগে (যেমন n ≤ 3000000000, যাতে n(n + 1)/2 < 263). Reference-এn = 4চালালে ছাপে10, আর 2·10 == 4·5.
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমHaat-core program a = b + 1; c = a * 2; আর postcondition c > 10-এর জন্য weakest precondition হিসাবের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- শুরু postcondition থেকে: c > 10
- শেষ statement c = a * 2: c-এর জায়গায় a * 2, পাওয়া গেল a * 2 > 10
- আগের statement a = b + 1: a-এর জায়গায় b + 1, পাওয়া গেল (b + 1) * 2 > 10
- Precondition P দিয়ে যাচাই: P ⇒ (b + 1) * 2 > 10 সব state-এ সত্য কি না
Haat-core-এ wp(x = y + 1;, x > 5) কী? (Haat-core-এ expression state বদলায় না।)
- x > 5
- y > 5
- y + 1 > 5
- x == y + 1 ∧ x > 5
Partial correctness ⊨ {P} S {Q} আর total correctness ⊨ [P] S [Q]-এর পার্থক্য কোনটি?
- Total-এ P বেশি শক্ত হতে হয়
- Total-এ S-কে P সত্য প্রতিটি state থেকে error ছাড়া থামতে হয়
- Partial শুধু loop-ছাড়া program-এ খাটে
- Total-এ Q প্রতিটি মাঝের state-এও সত্য হতে হয়
Loop while i < n { total = total + unit; i = i + 1; }, precondition n ≥ 0 ∧ unit ≥ 0 আর loop-এর আগে i = 0, total = 0, loop-এর পরে দাবি total == n * unit ∧ total ≥ 0. নিচের কোন invariant দিয়ে প্রমাণ পূর্ণ হয়?
- total == i * unit ∧ 0 ≤ i ∧ unit ≥ 0
- total == i * unit ∧ 0 ≤ i ≤ n
- total == i * unit ∧ i < n ∧ unit ≥ 0
- total == i * unit ∧ 0 ≤ i ≤ n ∧ unit ≥ 0
Triple {qty ≥ 0 ∧ unit ≥ 0} p = qty * unit; {p ≥ 0} গণিতের পূর্ণসংখ্যায় valid. Haat-এ (64-bit Int, overflow wrap করে) কী হয়?
- Invalid; বড় qty আর unit-এ গুণফল wrap হয়ে ঋণাত্মক হয়
- Valid, কারণ overflow হলে runtime error হয় আর partial correctness তা মাফ করে
- ফল undefined behavior, তাই প্রশ্নটি অর্থহীন
- Valid, কারণ ধনাত্মক সংখ্যার গুণফল সবসময় ধনাত্মক
একটি loop-এর verification condition Z3-কে দেওয়া হলো: solver-এর কাছে ¬VC যোগ করে check() চালানো হলো। কোন ফলের মানে VC সব state-এ সত্য?
- sat
- unknown
- unsat
- timeout হলে VC সত্য ধরা হয়
Hoare logic-এর soundness theorem কী বলে, আর Cook ১৯৭৮-এর ফল কোন দিকের?
- Soundness: প্রতিটি সত্য triple প্রমাণযোগ্য; Cook দেখান কিছু প্রমাণযোগ্য triple মিথ্যা
- Soundness: প্রমাণযোগ্য প্রতিটি triple সত্য; Cook-এর ফল আপেক্ষিক completeness
- Soundness: প্রতিটি program থামে; Cook দেখান invariant সবসময় খোঁজা যায়
- Soundness: wp সবসময় হিসাব করা যায়; Cook loop-এর wp-এর সূত্র দেন
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Triple: {P} S {Q} = P থেকে শুরু করে S থামলে Q (partial); [P] S [Q] = থামবেই, error ছাড়া, আর Q (total). সংজ্ঞা big-step semantics ⟨S, σ⟩ ⇓ σ′ দিয়ে।
- নিয়ম: H-Assign পেছন থেকে substitution {Q[e/x]} x = e; {Q}; H-Seq, H-If, H-Cons; H-While invariant দিয়ে, আর H-WhileT-এ variant লাগে।
- wp: loop-ছাড়া কোডে যান্ত্রিক; def(e) শূন্য দিয়ে ভাগ আর short-circuit ধরে; ⊨ [P] S [Q] ঠিক তখন, যখন P ⇒ wp(S, Q).
- Invariant আর VC: init, preserve, exit, variant; invariant-এ precondition-এর দরকারি তথ্যও বইতে হয়। Z3-এ ¬VC unsat মানে valid; unknown প্রমাণ নয়।
- বাস্তবতা: Haat-এর Int 64-bit wrap করে, তাই গণিতের Int-এর প্রমাণ ভাঙতে পারে (বিল 5 টাকা)। Soundness প্রমাণিত; completeness শুধু আপেক্ষিক (Cook ১৯৭৮)।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৪৩ · Lambda calculus প্রোগ্রামিং ভাষার ভিত্তি হিসেবে — typed lambda calculusপরবর্তী পর্বFunction-ই ভাষার core, আর type-ই প্রমাণ।
- প্রোগ্রামিং ভাষা ও কম্পাইলার · কোর্স হোম৮৬টি পর্বপুরো কোর্সের মানচিত্র আর Haat প্রজেক্টের পথ।
- পর্ব ৪০ · Operational semantics — small-step আর big-stepএই কোর্সেএই পর্বের সংজ্ঞার ভিত্তি ⇓ নিয়মগুলো।
- Program-এর সঠিকতা — loop invariant আর Hoare logic-এর ধারণাপাশের ট্র্যাকDiscrete Mathematics-এর পর্ব ১৩: প্রথম পরিচয় আর ভাগের loop.
- Program analysis-এর সীমা — dataflow, abstract interpretation আর SMTপাশের ট্র্যাকInvariant স্বয়ংক্রিয়ভাবে খোঁজার কৌশল আর সীমা।
- Property-based testing — Hypothesis আর shrinkingপাশের ট্র্যাকপ্রমাণের আগে সস্তায় counterexample খোঁজা।