এই পর্বে যা শিখবেন
- Formal verification ঠিক কী নিশ্চয়তা দেয়, আর specification, trusted computing base ও খরচের প্রশ্ন
- একটি optimization (constant folding) ⟦·⟧ রক্ষা করে, তা হাতে প্রমাণ করা, আর একটি ভুল নিয়ম চালানো checker দিয়ে ধরা
- Proof assistant-এ (Lean 4) একই প্রমাণ tactic দিয়ে লেখা আর goal ধাপে ধাপে পড়া
- Z3 দিয়ে ৬৪-বিট bit-vector-এ optimization-এর নিয়ম প্রমাণ বা খণ্ডন, আর C-র undefined behavior-এর সঙ্গে তুলনা
- CompCert-এর semantic preservation, simulation diagram, translation validation আর random compiler testing-এর জায়গা
১ · পরীক্ষা আর প্রমাণ — formal verification কী দেয়, কী দাম চায়
বাজারঘরের গুদামে একটি দাঁড়িপাল্লা আছে। কেউ কয়েকটি বাটখারা চাপিয়ে দেখলেন, ১ কেজি, ২ কেজি, ৫ কেজি ঠিক আসে। এতে কি প্রমাণ হলো, ৩.৭ কেজির চালও ঠিক মাপবে? না, শুধু জানা গেল যে পরীক্ষা করা ওজনগুলোতে ভুল ধরা পড়েনি। আরেকজন পাল্লার নকশা খুলে দেখালেন: দুই বাহু সমান দৈর্ঘ্যের, কাঁটা মাঝখানে, তাই যেকোনো ওজনে দুই পাশ সমান হলে কাঁটা সোজা থাকবে। দ্বিতীয়টি যুক্তি দিয়ে সব ওজনের জন্য একসঙ্গে কথা বলে। কিন্তু তাতেও কিছু ধরে নিতে হয়েছে: বাহুর মাপ যিনি নিয়েছেন তাঁর ফিতা ঠিক ছিল, আর “সঠিক মাপ” বলতে যা বোঝানো হয়েছে, সেটিই আসলে দরকার ছিল।
Software-এ প্রথমটি testing, দ্বিতীয়টি formal verification: একটি program বা নকশা তার specification মানে, তা গাণিতিক যুক্তি দিয়ে প্রমাণ করা, আর সেই প্রমাণ কম্পিউটার দিয়ে যাচাই করানো। এই মডিউলের আগের পর্বগুলো এর ভিত্তি দিয়েছে: পর্ব ৪০ আর পর্ব ৪১ program-এর অর্থকে গাণিতিক বস্তু বানিয়েছে, পর্ব ৪২ (Axiomatic semantics) Hoare triple আর verification condition দিয়ে একটি program-এর দাবি প্রমাণ করে, আর পর্ব ৪৩ (Lambda calculus) দেখায় type আর প্রমাণের সম্পর্ক। এই পর্ব প্রশ্নটিকে ভাষা আর compiler-এর দিকে ঘোরায়: optimization-এর নিয়ম কি অর্থ বদলায়? পুরো compiler কি সঠিক? আর সেই দাবি কে, কীভাবে যাচাই করে?
যেকোনো verification-এর তিনটি অংশ থাকে। (১) মডেল: যা যাচাই হচ্ছে তার গাণিতিক রূপ, যেমন Haat-core-এর ⟦·⟧. (২) দাবি: specification, যেমন “fold করার আগে আর পরে প্রতিটি state-এ অর্থ এক”। (৩) প্রমাণ আর তার যাচাই: হাতে লেখা, SMT solver-এর স্বয়ংক্রিয় খোঁজ, বা proof assistant-এর ধাপে ধাপে যাচাই করা প্রমাণ। ফল সবসময় শর্তসাপেক্ষ: “মডেল বাস্তবের মতো, আর spec যা চাই তাই বলে, এই দুটি সত্য হলে program সঠিক”।
ইতিহাস। Edsger Dijkstra-র একটি বহুল উদ্ধৃত কথা, যা সাধারণত ১৯৬৯–৭০ সালের লেখা ও বক্তৃতার বলে উল্লেখ করা হয়: program testing দিয়ে bug-এর উপস্থিতি দেখানো যায়, অনুপস্থিতি কখনো নয়। একই সময়ে Tony Hoare-এর ১৯৬৯ সালের axiomatic পদ্ধতি program-এর প্রমাণের ভাষা দেয়। তবে বাস্তব আকারের software-এর যন্ত্র-যাচাই করা প্রমাণ এসেছে অনেক পরে, ২০০০-এর দশকে, proof assistant আর SMT solver যথেষ্ট শক্তিশালী হওয়ার পরে।
নিশ্চয়তার কয়েকটি স্তর আছে, আর প্রতিটির দাম আলাদা। এই পর্বের প্রতিটি অংশ নিচের টেবিলের একটি সারি:
| পদ্ধতি | কী নিশ্চিত করে | দাম | এই পর্বে |
|---|---|---|---|
| Unit test, random আর property-based testing | পরীক্ষিত input-গুলোতে ভুল ধরা পড়েনি | কম | অংশ ৭ |
| Bounded check (ছোট পরিসরের সব মান) | সেই পরিসরে সমান; বাইরে কিছু বলে না | কম | অংশ ২ |
| SMT solver (Z3) | একটি সূত্র সব মানে সত্য, বা একটি পাল্টা উদাহরণ | মাঝারি; বড় সূত্রে সময় লাগতে পারে | অংশ ৪, ৬ |
| Proof assistant (Lean, Rocq, Isabelle) | যন্ত্রে যাচাই করা প্রমাণ, যেকোনো আকারের theorem | বেশি; মানুষকে প্রমাণ লিখতে হয় | অংশ ৩, ৫ |
সবচেয়ে উঁচু স্তরেও কিছু বিশ্বাস করতে হয়: proof checker-এর ছোট কেন্দ্র, specification নিজে, যে মডেলে প্রমাণ হলো সেটি বাস্তব যন্ত্রের সঙ্গে মেলে কি না, আর hardware. এই বিশ্বাসযোগ্য অংশের নাম trusted computing base (TCB). ভালো verification-এর একটি লক্ষ্য TCB যত সম্ভব ছোট আর সরল রাখা, যাতে মানুষ চোখে দেখে তা বিশ্বাস করতে পারে। পর্ব ০৪-এ Thompson-এর “Trusting Trust” প্রশ্নটি দেখেছেন: compiler-কেও বিশ্বাস করতে হয়; verified compiler সেই বিশ্বাসের একটি বড় অংশকে প্রমাণে বদলে দেয়।
২ · Optimization-এর সঠিকতা — constant folding অর্থ রাখে
Constant folding সবচেয়ে সরল optimization: 2 * 520 + x দেখে compiler আগেই 1040 + x লিখে দেয়। এটি “ঠিক” বলতে কী বোঝায়, পর্ব ৪১-এর ভাষায় তা একটি সমীকরণ। Haat-core-এর expression-এর অর্থ ⟦e⟧σ: state σ-তে একটি মান, বা শূন্য দিয়ে ভাগ হলে err. Fold-এর নিয়ম: একটি binary node-এর দুই অংশ fold করার পরে দুটিই সংখ্যা হলে হিসাবটি এখনই করে ফল বসানো, তবে / বা %-এর ডান পাশ 0 হলে নয়, কারণ তখন হিসাবটির অর্থ err, কোনো সংখ্যা নয়।
প্রতিটি Haat-core expression e আর প্রতিটি state σ-এর জন্য: ⟦fold(e)⟧σ = ⟦e⟧σ. সমতাটি err-কেও ধরে: একটি পাশ err হলে অন্যটিও err.
প্রমাণ (e-এর গঠনের ওপর structural induction; দাবিটিকে P(e) বলি):
- সংখ্যা আর নাম। fold(n) = n আর fold(x) = x, তাই দুই পাশ হুবহু এক।
- Binary node e = e1 ⊕ e2. Induction hypothesis (IH): P(e1) আর P(e2) সত্য। লিখি f1 = fold(e1), f2 = fold(e2).
- Case ক: f1 = c1, f2 = c2 দুটিই সংখ্যা, আর ভাগে c2 ≠ 0. তখন fold(e) = c, যেখানে c = wrap(c1 ⊕ c2) (Haat-এর C-ধাঁচের ভাগসহ)। IH থেকে ⟦e1⟧σ = ⟦c1⟧σ = c1 আর ⟦e2⟧σ = c2, তাই পর্ব ৪১-এর সমীকরণে ⟦e⟧σ = wrap(c1 ⊕ c2) = c = ⟦fold(e)⟧σ. লক্ষ করুন, folder আর ⟦·⟧ একই wrap ব্যবহার করে (সিদ্ধান্ত ১৩); folder সাধারণ গণিতের যোগ ব্যবহার করলে এখানে প্রমাণ ভেঙে যেত।
- Case খ: অন্য সব ক্ষেত্র. fold(e) = f1 ⊕ f2. Compositionality-র কারণে ⟦f1 ⊕ f2⟧σ শুধু ⟦f1⟧σ আর ⟦f2⟧σ-এর ওপর নির্ভর করে, আর IH বলে সেগুলো ⟦e1⟧σ আর ⟦e2⟧σ-এর সমান (err হলে err). তাই ⟦fold(e)⟧σ = ⟦e⟧σ.
- ভাগে c2 = 0. এটি case খ-তে পড়ে: node যেমন ছিল থাকে, তাই দুই পাশই err. সব case-এ P(e) সত্য। ∎
প্রমাণটি ছোট, কিন্তু প্রতিটি শর্ত কাজে লেগেছে। “ডান পাশ 0 হলে fold নয়” নিয়মটি বাদ দিলে folder হয় crash করত, নয় err-কে একটি সংখ্যা বানিয়ে ফেলত। আরেকটি পরিচিত “optimization” দেখুন: e * 0 → 0. সাধারণ গণিতে ঠিক, কিন্তু e-এর ভেতরে ভাগ থাকলে ⟦e⟧σ = err হতে পারে, আর তখন ⟦e * 0⟧σ = err ≠ 0. নিচের block-এ সঠিক folder, একটি ভুল নিয়মসহ folder, আর একটি bounded checker আছে, যা সীমার মান (INT_MIN, −1, 0, 1, INT_MAX …) আর ২০০০টি seeded এলোমেলো state-এ দুই পাশ মেলায়। পূর্ণ Haat-এ wrap আর ভাগের একই হিসাব reference-এর runtime.py-তে।
# Constant folding আর তার bounded যাচাই (Haat-core expression, ৬৪-বিট wrap)
import random, itertools
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
OPS = {"+": lambda a, b: a + b, "-": lambda a, b: a - b, "*": lambda a, b: a * b,
"/": cdiv, "%": lambda a, b: a - b * cdiv(a, b)}
def ev(e, s): # ⟦e⟧σ ; শূন্য দিয়ে ভাগ হলে "err"
if isinstance(e, int): return e
if isinstance(e, str): return s[e]
a, b = ev(e[1], s), ev(e[2], s)
if "err" in (a, b) or (e[0] in "/%" and b == 0): return "err"
return wrap(OPS[e[0]](a, b))
def fold(e, bad=False): # bad=True হলে একটি ভুল নিয়মও চলে
if not isinstance(e, tuple): return e
op, a, b = e[0], fold(e[1], bad), fold(e[2], bad)
if isinstance(a, int) and isinstance(b, int) and not (op in "/%" and b == 0):
return wrap(OPS[op](a, b)) # দুই পাশই জানা: এখনই হিসাব
if bad and op == "*" and b == 0: return 0 # ভুল নিয়ম: e * 0 → 0
return (op, a, b)
def sh(e): return str(e) if not isinstance(e, tuple) else f"({sh(e[1])} {e[0]} {sh(e[2])})"
EDGE = [-2**63, -2**63 + 1, -2, -1, 0, 1, 2, 2**63 - 1]
def check(e, f): # সীমার সব জোড়া + ২০০০টি seeded এলোমেলো state
rnd = random.Random(44)
st = [{"x": x, "y": y} for x, y in itertools.product(EDGE, repeat=2)]
st += [{"x": rnd.randint(-2**63, 2**63 - 1), "y": rnd.randint(-9, 9)} for _ in range(2000)]
for s in st:
if ev(e, s) != ev(f, s): return f"আলাদা! x={s['x']} y={s['y']}: {ev(e, s)} বনাম {ev(f, s)}"
return f"সমান, {len(st)}টি state-এ"
progs = [("+", ("*", 2, 520), "x"), ("+", ("-", "x", ("*", 3, 4)), ("/", 10, 0)),
("*", ("/", 100, "y"), ("-", 5, 5))]
for e in progs: print(f"ঠিক: {sh(e)} ⇒ {sh(fold(e))} → {check(e, fold(e))}")
e = progs[2]; print(f"ভুল: {sh(e)} ⇒ {sh(fold(e, True))} → {check(e, fold(e, True))}")আসল আউটপুট (ব্রাউজারের Python):
ঠিক: ((2 * 520) + x) ⇒ (1040 + x) → সমান, 2064টি state-এ
ঠিক: ((x - (3 * 4)) + (10 / 0)) ⇒ ((x - 12) + (10 / 0)) → সমান, 2064টি state-এ
ঠিক: ((100 / y) * (5 - 5)) ⇒ ((100 / y) * 0) → সমান, 2064টি state-এ
ভুল: ((100 / y) * (5 - 5)) ⇒ 0 → আলাদা! x=-9223372036854775808 y=0: err বনাম 0
প্রথম লাইনে 2 * 520 হয়ে গেল 1040. দ্বিতীয় লাইনে 3 * 4 fold হয়েছে, কিন্তু 10 / 0 ছোঁয়া হয়নি: Theorem ৪৪.১-এর শর্ত মেনে ভাগটি run time-এর জন্য রেখে দেওয়া হয়েছে, তাই program চালালে ঠিক আগের মতোই runtime error আসবে। তৃতীয় লাইনে 5 - 5 হলো 0, কিন্তু সঠিক folder সেখানে থামে। শেষ লাইনে ভুল নিয়ম e * 0 → 0 পুরো expression-কে 0 বানিয়ে দিল, আর checker প্রথম state-গুলোর একটিতেই (y = 0) পাল্টা উদাহরণ পেল: আসল অর্থ err, fold-এর পরে 0. লেখকের lab-এ reference-এ সত্যিকারের run (CPython 3.14): let y = 0; print((100 / y) * (5 - 5)); দেয় 2:12: runtime error: division by zero, তাই এই নিয়ম Haat-এর optimizer-এ চলবে না। একই lab-এ এই block-এর ev ৫৪টি এলোমেলো Haat program-এ reference-এর haat.py run-এর সঙ্গে হুবহু মিলেছে।
“সমান, 2064টি state-এ” প্রমাণ নয়। Checker শুধু পরীক্ষিত state-গুলোর কথা বলে। ভুল ধরতে এটি দারুণ, কিন্তু 2128টি সম্ভাব্য (x, y) জোড়ার তুলনায় ২০৬৪ প্রায় শূন্য। সব state-এর নিশ্চয়তা আসে Theorem ৪৪.১-এর প্রমাণ থেকে, আর পরের দুই অংশে সেই প্রমাণ যন্ত্রকে দিয়ে যাচাই করানো হবে।
৩ · Proof assistant — যন্ত্র যখন প্রমাণের প্রতিটি ধাপ যাচাই করে
হাতে লেখা প্রমাণে ভুল থাকতেই পারে: একটি case বাদ পড়ে, একটি “স্পষ্ট” ধাপ আসলে মিথ্যা হয়। Proof assistant এই সমস্যার সমাধান: প্রমাণটি একটি formal ভাষায় লিখতে হয়, আর যন্ত্র প্রতিটি ধাপ নিয়ম মেনে যাচাই করে। সবচেয়ে পরিচিত কয়েকটি: Rocq (আগের নাম Coq, ১৯৮০-এর দশকের শেষ থেকে Inria-তে; ২০২৫ সালে নাম বদলায়), Isabelle (Lawrence Paulson, ১৯৮০-এর দশক থেকে; বিশেষ করে Isabelle/HOL), আর Lean (Leonardo de Moura, ২০১৩ থেকে; এখনকার Lean 4 একই সঙ্গে একটি সাধারণ প্রোগ্রামিং ভাষাও)।
এরা কীভাবে কাজ করে, তার মূল ধারণা পর্ব ৩৯-এর dependent type আর পর্ব ৪৩-এর Curry–Howard correspondence: একটি theorem হলো একটি type, আর তার প্রমাণ সেই type-এর একটি মান (একটি program). “প্রমাণ সঠিক কি না” প্রশ্নটি তাই হয়ে যায় “এই program কি type check পার হয়?”। এই type checker-এর ছোট কেন্দ্রটির নাম kernel; বাকি সব (প্রমাণ খোঁজার স্বয়ংক্রিয় কৌশল, সুবিধার লেখা) kernel-কে একটি প্রমাণ-term দেয়, আর kernel সেটি আলাদা করে যাচাই করে। একে প্রায়ই de Bruijn criterion বলা হয় (Automath-এর স্রষ্টা N. G. de Bruijn-এর নামে): বড় আর জটিল যন্ত্রপাতি ভুল করলেও ছোট kernel সেই ভুল ধরবে, তাই বিশ্বাস করতে হয় শুধু kernel-কে।
মানুষ সাধারণত প্রমাণ-term সরাসরি লেখে না; লেখে tactic: “e-এর ওপর induction”, “এই সংজ্ঞা খোলা”, “বাকিটা সরল করা”-র মতো নির্দেশ। প্রতিটি tactic বাকি থাকা লক্ষ্য (goal) বদলায়, আর সব goal শেষ হলে প্রমাণ শেষ। নিচে Theorem ৪৪.১-এর একটি ছোট রূপ Lean 4-এ, যোগ আর গুণ নিয়ে। Int64 Lean-এর ৬৪-বিট signed integer, যার যোগ-গুণ Haat-এর মতোই wrap করে।
-- Haat-core-এর ছোট expression: সংখ্যা, নাম, যোগ, গুণ (Int64 = ৬৪-বিট, wrap করে)
inductive Expr where
| num : Int64 → Expr
| var : String → Expr
| add : Expr → Expr → Expr
| mul : Expr → Expr → Expr
deriving Repr
def eval (σ : String → Int64) : Expr → Int64 -- ⟦e⟧σ
| .num n => n
| .var x => σ x
| .add a b => eval σ a + eval σ b
| .mul a b => eval σ a * eval σ b
def fold : Expr → Expr -- constant folding
| .num n => .num n
| .var x => .var x
| .add a b =>
match fold a, fold b with
| .num m, .num n => .num (m + n)
| a', b' => .add a' b'
| .mul a b =>
match fold a, fold b with
| .num m, .num n => .num (m * n)
| a', b' => .mul a' b'
theorem fold_correct (σ : String → Int64) (e : Expr) :
eval σ (fold e) = eval σ e := by
induction e with
| num n => rfl
| var x => rfl
| add a b iha ihb =>
simp only [fold]
split <;> simp_all [eval]
| mul a b iha ihb =>
simp only [fold]
split <;> simp_all [eval]File-এর শেষে তিনটি নির্দেশ যোগ করে লেখকের lab-এ চালানো হয়েছে (সত্যিকারের run, Lean 4.36.0, Apache-2.0 licence; Lean-এ কোনো usage reporting নেই, binary-তে telemetry-র কোনো উল্লেখও পাওয়া যায়নি)। Error ছাড়া শেষ হওয়া মানে theorem-টি kernel যাচাই করেছে:
$ lean Fold.lean # শেষে: #eval fold (.add (.mul (.num 2) (.num 520)) (.var "x"))
# #eval (4611686018427387904 : Int64) * 2 / 2
# #print axioms fold_correct
Expr.add (Expr.num 1040) (Expr.var "x")
-4611686018427387904
'fold_correct' depends on axioms: [propext]
প্রথম লাইন Lean-এর folder-এর ফল, অংশ ২-এর Python-এর মতোই 1040 + x. দ্বিতীয় লাইন একটি সতর্কবার্তা, অংশ ৪-এ কাজে লাগবে: Lean-এর Int64-এ 262 × 2 ÷ 2 = −262. তৃতীয় লাইন TCB-র একটি স্পষ্ট হিসাব: প্রমাণটি kernel-এর নিয়মের বাইরে শুধু একটি স্বতঃসিদ্ধ (axiom) ব্যবহার করেছে, propext (দুটি proposition একে অপরকে বোঝালে তারা সমান)। প্রমাণে কোনো ফাঁকি (sorry) থাকলে এখানে sorryAx দেখা যেত। নিচের stepper add case-এর প্রতিটি tactic-এর আগে-পরের goal দেখায়; লেখাগুলো একই lab-এ trace_state বসিয়ে Lean থেকে নেওয়া (একটু ছোট করা)।
1eval σ (fold e) = eval σ e := by2 induction e with3 | num n => rfl4 | add a b iha ihb =>5 simp only [fold]6 split <;> simp_all [eval]7 | mul a b iha ihb => …
| হাতে আছে | |
| প্রমাণ করতে হবে (⊢) |
- লক্ষ্য। শুরুতে একটি goal: সব σ আর e-এর জন্য eval σ (fold e) = eval σ e.
⊢চিহ্নের ডানে যা, তা প্রমাণ করতে হবে। - Induction.
induction egoal-টিকে Expr-এর চারটি গঠনে ভাঙে।numcase-এ fold (num n) সংজ্ঞা অনুযায়ী num n, তাই দুই পাশ হিসাব করলে হুবহু এক;rfl(reflexivity) এটুকুই বলে।varএকই রকম। - add case. এখন a আর b-এর জন্য দাবিটি জানা:
ihaআরihb, ঠিক হাতে লেখা প্রমাণের IH. লক্ষ্য: যোগের node-এর জন্য একই সমতা। - সংজ্ঞা খোলা।
simp only [fold]fold-এর add-লাইনটি বসায়। goal-এ এখন একটিmatch: fold a আর fold b দুটিই সংখ্যা কি না, তার ওপর ফল নির্ভর করে। - Case ভাগ।
splitmatch-এর দুই শাখায় দুটি goal বানায়। প্রথমটিতে (h_1) নতুন তথ্য: fold a = num m আর fold b = num n. এটি হাতে লেখা প্রমাণের case ক। - Case ক বন্ধ।
simp_all [eval]iha-তে fold a = num m বসিয়ে পায় m = eval σ a, ihb থেকে n = eval σ b, আর eval-এর সংজ্ঞা খুলে goal হয় m + n = eval σ a + eval σ b, যা এখন সরাসরি সত্য। - Case খ বন্ধ। দ্বিতীয় শাখায় fold কোনো হিসাব করেনি, শুধু (fold a).add (fold b). eval খুললে বাকি থাকে eval σ (fold a) + eval σ (fold b) = eval σ a + eval σ b; iha আর ihb দিয়ে মিলে যায়।
- শেষ। mul case হুবহু একই কৌশলে বন্ধ হয়। Tactic-গুলো মিলে একটি প্রমাণ-term বানায়, আর kernel সেটি স্বাধীনভাবে যাচাই করে; Lean কোনো error দেয়নি, তাই theorem প্রমাণিত। ∎
দুটি জিনিস লক্ষ করার মতো। প্রথম, প্রমাণটি Int64-এর wrap নিয়ে কিছুই বলেনি, কারণ folder আর eval একই + ব্যবহার করে; হাতে লেখা প্রমাণের case ক-এর শর্তটি এখানে স্বয়ংক্রিয়ভাবে মেনে চলা হয়েছে। দ্বিতীয়, এই theorem শুধু এই eval সম্পর্কে। eval যদি Haat-এর আসল অর্থের সঙ্গে না মেলে (ধরুন কেউ ভুল করে গুণের জায়গায় যোগ লিখল), প্রমাণ তবুও পাস করবে। Spec আর মডেল TCB-র অংশ: যন্ত্র এগুলোর সঠিকতা যাচাই করে না, মানুষকে পড়ে দেখতে হয়।
৪ · SMT solver দিয়ে স্বয়ংক্রিয় যাচাই — ৬৪-বিটের সব মান একসঙ্গে
Proof assistant-এ মানুষকে প্রমাণের পথ দেখাতে হয়। অনেক ছোট দাবির জন্য তা দরকার নেই: “x * 2 আর x + x কি সব ৬৪-বিট x-এ সমান?” এমন প্রশ্নের উত্তর যন্ত্র নিজেই খুঁজতে পারে। এর যন্ত্র SMT solver, আর সবচেয়ে পরিচিতদের একটি Z3 (Leonardo de Moura আর Nikolaj Bjørner, Microsoft Research; প্রথম প্রকাশ ২০০৮ সালের দিকে, এখন MIT licence). Z3-এর bit-vector theory হুবহু Haat-এর Int: ৬৪-বিট, যোগ-গুণ mod 264-এ ঘোরে। SAT আর SMT-এর ভেতরের কাজ Discrete Mathematics-এর পর্ব ৭৭-এ (SAT, SMT আর verification) আছে; পর্ব ৪২ Z3 দিয়ে Hoare logic-এর verification condition যাচাই করে। এখানে প্রশ্ন শুধু optimizer-এর নিয়ম।
কৌশলটি সবসময় এক: “আগে” আর “পরে” সমান, এই দাবির উল্টোটা solver-কে দেওয়া। Solver যদি বলে unsat (উল্টোটা কখনো সত্য হয় না), তাহলে দাবিটি সব মানে প্রমাণিত। যদি বলে sat, সঙ্গে দেয় একটি model, অর্থাৎ একটি নির্দিষ্ট counterexample. লেখকের lab-এর script (সত্যিকারের run: PyPI z3-solver 5.4.1, MIT licence, CPython 3.12-এর একটি uv venv-এ; package-এ কোনো network বা usage reporting-এর code নেই):
# Haat-এর Int = 64-বিট bit-vector; প্রতিটি "আগে → পরে" নিয়ম সব মানে যাচাই
from z3 import BitVec, BitVecVal, Solver, Optimize, Not, unsat, simplify
x, c1, c2 = BitVec("x", 64), BitVec("c1", 64), BitVec("c2", 64)
def check(name, before, after):
s = Solver()
s.add(Not(before == after)) # এমন মান আছে কি, যেখানে দুই পাশ আলাদা?
if s.check() == unsat:
print(f"{name:<26} proved for all values")
else:
m = s.model()
v = lambda t: m.eval(t, model_completion=True).as_signed_long()
print(f"{name:<26} counterexample x = {v(x)}: {v(before)} vs {v(after)}")
check("(x + c1) + c2 -> x + (c1+c2)", (x + c1) + c2, x + (c1 + c2))
check("x * 2 -> x + x", x * 2, x + x)
check("(x*x + x) * 2^63 -> 0", (x * x + x) * BitVecVal(-2**63, 64), BitVecVal(0, 64))
check("x * 2 / 2 -> x", (x * 2) / 2, x) # BitVec-এ / মানে signed ভাগ (bvsdiv)
check("x / 2 -> x >> 1", x / 2, x >> 1) # >> মানে arithmetic shift
s = Solver(); s.add(Not(x + 1 > x)) # > মানে signed তুলনা
print(f"{'x + 1 > x -> true':<26} counterexample x = {s.model()[x].as_signed_long()}"
if s.check() != unsat else "proved")
o = Optimize(); o.add((x * 2) / 2 != x, x > 0); o.minimize(x)
o.check(); print("smallest x > 0 with x * 2 / 2 != x:", o.model()[x].as_signed_long())
print("INT_MIN / -1 =", simplify(BitVecVal(-2**63, 64) / -1).as_signed_long())
print("7 / 0 in SMT-LIB =", simplify(BitVecVal(7, 64) / 0).as_signed_long())(x + c1) + c2 -> x + (c1+c2) proved for all values
x * 2 -> x + x proved for all values
(x*x + x) * 2^63 -> 0 proved for all values
x * 2 / 2 -> x counterexample x = -7701385326548541167: 1521986710306234641 vs -7701385326548541167
x / 2 -> x >> 1 counterexample x = -50179819698126849: -25089909849063424 vs -25089909849063425
x + 1 > x -> true counterexample x = 9223372036854775807
smallest x > 0 with x * 2 / 2 != x: 4611686018427387904
INT_MIN / -1 = -9223372036854775808
7 / 0 in SMT-LIB = -1
প্রথম লাইন শুধু একটি উদাহরণ নয়, পুরো একটি নিয়ম প্রমাণ করেছে: c1, c2 নিজেরাও যেকোনো মান, তাই “(x + c1) + c2 → x + (c1 + c2)” সব x, c1, c2-এ ঠিক, wrap থাকা সত্ত্বেও। তৃতীয় লাইনটি চমকপ্রদ: x(x + 1) সবসময় জোড়, তাই 263 দিয়ে গুণ করলে mod 264-এ 0. সাধারণ বীজগণিতে এটি মোটেই “স্পষ্ট” নয়, অথচ Z3 সব 264 মানের জন্য এক মুহূর্তে প্রমাণ দিল। চতুর্থ থেকে ষষ্ঠ লাইন তিনটি জনপ্রিয় “optimization”-এর পাল্টা উদাহরণ। লেখকের lab-এ তিনটিই reference-এ মিলিয়ে দেখা হয়েছে: a * 2 / 2 (a = −7701385326548541167) ছাপে 1521986710306234641, c / 2 (c = −50179819698126849) ছাপে -25089909849063424 (শূন্যের দিকে কাটা), আর INT_MAX-এ m + 1 > m ছাপে false. নিচের stepper একটি পাল্টা উদাহরণ ধাপে ধাপে পড়ে।
1দাবি: ∀x. x * 2 / 2 = x2solver-কে: ∃x. x * 2 / 2 ≠ x ?3bit-blast → SAT সূত্র4sat, model: x = …5x * 2 (wrap)6÷ 2 (শূন্যের দিকে)7সবচেয়ে ছোট ধনাত্মক x
| x | |
| মধ্যবর্তী মান | |
| ফল বনাম x |
- দাবি। অসীম পূর্ণসংখ্যায় 2x ÷ 2 = x সবসময় সত্য। প্রশ্ন: Haat-এর ৬৪-বিট Int-এও কি তাই? তাহলে optimizer
x * 2 / 2-কেxবানাতে পারত। - উল্টো প্রশ্ন। Solver-কে জিজ্ঞাসা: এমন কোনো x আছে কি, যেখানে দুই পাশ আলাদা? “নেই” (unsat) হলে দাবি প্রমাণিত, “আছে” (sat) হলে solver একটি x দেখাবে।
- ভেতরে কী হয়। Bit-vector সূত্র সাধারণত bit-blasting নামের কৌশলে Boolean circuit-এ বদলায়: x হয় ৬৪টি সত্য/মিথ্যা চলক, গুণ আর ভাগ হয় যুক্তি-গেটের জাল, তারপর SAT solver খোঁজে। (এটি ধারণা; Z3 আগে সূত্র সরল করাসহ আরও কৌশল চালায়।)
- Model. Z3 বলল sat, আর x = −7701385326548541167 দিল। কেন এই সংখ্যা, তা গুরুত্বপূর্ণ নয়; গুরুত্বপূর্ণ হলো এটি হাতে যাচাই করা যায়।
- গুণ। সাধারণ গণিতে 2x = −15402770653097082334, যা −263-এর চেয়ে ছোট। 264 যোগ করে wrap করলে পাই 3043973420612469282, একটি ধনাত্মক সংখ্যা (সিদ্ধান্ত ১৩)।
- ভাগ। 3043973420612469282 ÷ 2 = 1521986710306234641, যা x নয়। তাই নিয়মটি Haat-এ ভুল। Reference-এ
print(a * 2 / 2);ঠিক এই সংখ্যা ছাপে। - সবচেয়ে ছোট।
Optimizeদিয়ে সবচেয়ে ছোট ধনাত্মক পাল্টা উদাহরণ চাওয়া হলে Z3 দেয় 262 = 4611686018427387904: তার দ্বিগুণ ঠিক 263, যা wrap হয়ে INT_MIN, আর অর্ধেক −262. অংশ ৩-এ Lean-এরInt64-ও ঠিক এই ফল দিয়েছে।
Haat-এ নিষেধ, C-তে বৈধ: একই নিয়ম, দুই ভাষা
Optimizer-এর নিয়ম সঠিক কি না, তা ভাষার semantics-এর ওপর নির্ভর করে, সাধারণ গণিতের ওপর নয়। C-তে signed integer overflow undefined behavior: যে program-এ overflow হয়, তার কোনো নির্দিষ্ট অর্থই নেই, তাই compiler ধরে নিতে পারে overflow কখনো ঘটে না। তখন x * 2 / 2 → x বৈধ। নিচের C ফাইলটি লেখকের lab-এ compile করা হয়েছে (সত্যিকারের run: PyPI ziglang 0.17.1, MIT, যার সঙ্গের Clang 22.1.8; zig cc -O2 -S -g0 -fomit-frame-pointer -fno-sanitize=undefined --target=x86_64-linux-musl -masm=intel), আউটপুট থেকে directive বাদ দেওয়া:
long half_double(long x) { return x * 2 / 2; }
unsigned long uhalf_double(unsigned long x) { return x * 2 / 2; }
int plus_one_bigger(long x) { return x + 1 > x; }half_double:
mov rax, rdi
ret
uhalf_double:
movabs rax, 9223372036854775807
and rax, rdi
ret
plus_one_bigger:
mov eax, 1
ret
তিনটি function, তিনটি শিক্ষা। half_double-এ Clang পুরো হিসাব মুছে x ফেরত দেয়: signed long-এ overflow UB, তাই Z3-এর পাল্টা উদাহরণটি C-র দৃষ্টিতে “ঘটতেই পারে না”। plus_one_bigger সরাসরি 1 (true) ফেরত দেয়, একই কারণে। কিন্তু unsigned long-এ C নিজেই wrap সংজ্ঞায়িত করে, তাই Clang সেখানে x লেখে না, লেখে x & 0x7FFF…, অর্থাৎ সর্বোচ্চ বিটটি মুছে দেওয়া: ঠিক wrap-এর পরে যা থাকে। Compiler একই, নিয়ম আলাদা, কারণ semantics আলাদা। Haat-এর optimizer-এর জন্য Haat-এর semantics-ই spec, আর সেখানে x * 2 / 2 → x নিষিদ্ধ।
সাবধান: solver-এর ভাগ আর Haat-এর ভাগ এক নয়। উপরের শেষ লাইন: SMT-LIB মানে অনুযায়ী 7 / 0-এর ফল −1, কোনো error নয় (সংজ্ঞাটি total রাখার জন্য)। Haat-এ একই হিসাব runtime error. তাই ভাগ আছে এমন নিয়ম Z3-এ যাচাই করার সময় “ভাজক 0 হলে err” আলাদা শর্ত হিসেবে লিখতে হয়, নইলে solver ভুল প্রশ্নের সঠিক উত্তর দেবে। অন্যদিকে INT_MIN / −1 Z3-এ INT_MIN, যা Haat-এর সিদ্ধান্ত ১৩-এর সঙ্গে হুবহু মেলে (C-তে এটিও UB).
SMT solver-এর ওপর গোটা ভাষাও দাঁড়িয়ে আছে। Dafny (K. Rustan M. Leino, Microsoft Research, ২০০৯–১০ সালের দিকে) আর Why3 (Inria, ২০১০ সালের দিকে) এমন ভাষা, যেখানে programmer function-এর সঙ্গে precondition, postcondition আর loop invariant লেখেন, আর verifier সেগুলো থেকে সূত্র বানিয়ে SMT solver-কে দেয়। পর্ব ৪২-এর verification condition-এর ধারণাই এখানে শিল্প-মানে। সুবিধা: বেশিরভাগ ছোট প্রমাণ স্বয়ংক্রিয়। অসুবিধা: solver কখনো কখনো উত্তর না দিয়ে সময় শেষ করে, আর তখন কেন আটকাল তা বোঝা কঠিন।
৫ · Verified compiler — CompCert, CakeML আর simulation
একটি optimization-এর নিয়ম প্রমাণ করা গেল। পুরো compiler? পর্ব ০৫-এ compiler-এর সঠিকতার দাবিটি প্রথম দেখেছেন, আর পর্ব ০১-এ CompCert-এর নাম। এখন দাবিটি নির্দিষ্ট করি। Verified compiler এমন compiler, যার জন্য নিচের ধরনের theorem একটি proof assistant-এ প্রমাণিত:
যদি compile(S) = C সফল হয়, আর source program S-এর আচরণ সংজ্ঞায়িত (কোনো undefined behavior নেই), তাহলে target program C-এর প্রতিটি পর্যবেক্ষণযোগ্য আচরণ S-এরও একটি আচরণ: একই আউটপুটের ক্রম, একই থামা বা না-থামা।
এই দাবির নাম semantic preservation. “পর্যবেক্ষণযোগ্য আচরণ” মানে বাইরে থেকে যা দেখা যায়: Haat-এ print-এর ধারা আর শেষ ফল, register বা stack-এর ভেতরের অবস্থা নয়। শর্ত “আচরণ সংজ্ঞায়িত” খুব জরুরি: C program-এ UB থাকলে CompCert কোনো প্রতিশ্রুতি দেয় না, ঠিক অংশ ৪-এর Clang-এর মতো। নিচের ছবিতে পুরো কাঠামো:
ছবি ৪৪.১ — semantic preservation আর trusted computing base
ওপরে compiler source থেকে target বানায়; দুই পাশের semantics দুটি আচরণ দেয়; প্রমাণিত theorem বলে নিচের দুটি সমান। সবচেয়ে নিচের ধূসর বাক্সের অংশগুলো প্রমাণের বাইরে, বিশ্বাস করতে হয়
এমন theorem কীভাবে প্রমাণ হয়? Source আর target দুটিরই small-step semantics আছে (পর্ব ৪০-এর ⟶)। প্রমাণের মূল যন্ত্র একটি forward simulation: source-এর অবস্থা আর target-এর অবস্থার মধ্যে একটি সম্পর্ক ~ খুঁজে বের করা, যেটি শুরুতে সত্য, আর যার একটি গুণ আছে: source এক ধাপ এগোলে target শূন্য বা বেশি ধাপে এমন অবস্থায় যায়, যেখানে ~ আবার সত্য, আর পথে বাইরের আউটপুট একই। এটি প্রতিটি ধাপের একটি ছোট বর্গক্ষেত্র; বর্গগুলো জুড়ে পুরো চলার সমতা আসে। নিচের stepper Haat-এর reference compiler-এর আসল bytecode দিয়ে একটি ছোট উদাহরণ দেখায়: let x = 4; print(2 + 3 * x);, যার haat.py dis-এর main অংশে instruction 2–7: CONST 2, CONST 3, LOAD_GLOBAL x, MUL, ADD, PRINT.
2CONST 23CONST 34LOAD_GLOBAL x5MUL6ADD7PRINT
| source | |
| source নিয়ম | |
| VM stack |
- শুরু। Source configuration
print(2 + 3 * x), σ = {x ↦ 4}; VM-এর stack ফাঁকা, পরের instruction CONST 2. সম্পর্ক ~: “stack-এ যা আছে আর বাকি instruction মিলে ঠিক source-এর বাকি expression হিসাব করবে”। শুরুতে এটি সত্য। - Stutter. VM
CONST 2চালায়, stack [2]. Source-এ কোনো ধাপ নেই, কারণ 2 আগে থেকেই মান। Simulation এটি অনুমতি দেয়: target বেশি ধাপ নিতে পারে, ~ বজায় থাকলেই হলো। - আবার stutter.
CONST 3, stack [2, 3]. Source এখনোprint(2 + 3 * x); ~ সত্য, কারণ stack-এর 2, 3 আর বাকি LOAD, MUL, ADD মিলে ঠিক 2 + 3 * x হিসাব করবে। - E-Var. Source-এর প্রথম আসল ধাপ: বাঁ-থেকে-ডানে প্রথম অ-মান অংশ x, যা E-Var নিয়মে 4 হয় (পর্ব ৪০)। VM-এর মিলে যাওয়া ধাপ
LOAD_GLOBAL x, stack [2, 3, 4]. - E-Op (গুণ)। Source: 3 * 4 ⟶ 12. VM:
MULওপরের দুটি মান নিয়ে 12 রাখে, stack [2, 12]. ~ এখনো সত্য: stack-এর 2 আর 12, বাকি ADD মিলে 2 + 12. - E-Op (যোগ)। Source: 2 + 12 ⟶ 14. VM:
ADD, stack [14]. - E-Print. Source
print(14)ছাপে 14; VMPRINTছাপে 14. এটিই একমাত্র পর্যবেক্ষণযোগ্য ঘটনা, আর দুই পাশে এক। Reference-এরhaat.py runআরvmদুটিই ছাপে14. - সিদ্ধান্ত। প্রতিটি source ধাপের জন্য VM-এর শূন্য বা বেশি ধাপ পাওয়া গেল, আর আউটপুট সব সময় এক। Compiler-এর প্রতিটি নিয়মের (CONST, LOAD, MUL …) জন্য এই বর্গ সাধারণভাবে প্রমাণ করলে সব program-এর জন্য semantic preservation আসে। CompCert ঠিক এভাবে, প্রতিটি pass-এর জন্য আলাদা simulation প্রমাণ করে।
বাস্তবে সাধারণত forward simulation (source থেকে target) প্রমাণ করা সহজ, কিন্তু দরকার উল্টো দিকের নিশ্চয়তা: target যা করে, source-ও তা করে। Target ভাষা deterministic হলে forward simulation থেকেই উল্টোটা পাওয়া যায়, আর এই কৌশল verified compiler-এর প্রমাণে কেন্দ্রীয়। আরেকটি কারিগরি সুবিধা: compiler অনেক pass-এ ভাগ, আর simulation জোড়া দেওয়া যায় (pass ১-এর simulation আর pass ২-এর simulation মিলে দুটির একসঙ্গের simulation), তাই প্রতিটি pass আলাদা প্রমাণ করা চলে।
CompCert আর CakeML. Xavier Leroy আর সহকর্মীরা ২০০৫–০৬ সাল থেকে Coq-এ CompCert বানান: C-র একটি বড় অংশ থেকে কয়েকটি CPU-র assembly পর্যন্ত, optimization-সহ; মূল প্রবন্ধগুলোর মধ্যে আছে POPL ২০০৬ আর Communications of the ACM ২০০৯ (পর্ব ০৫-এর উল্লেখের সঙ্গে মিলিয়ে)। ২০১১ সালে Csmith প্রকল্প GCC আর LLVM-এ বহু ভুল-কোড bug পায়, কিন্তু CompCert-এর প্রমাণিত অংশে ভুল-কোড bug পায়নি বলে জানায়; যে কয়েকটি সমস্যা পায়, সেগুলো ছিল প্রমাণের বাইরের অংশে। CakeML (Kumar, Myreen, Norrish, Owens, POPL ২০১৪; HOL4-এ) Standard ML-এর একটি রূপের verified compiler, যা নিজেকেই compile করে (bootstrapping) এমনভাবে, যাতে compiler-এর machine code-এর সঠিকতাও প্রমাণে ধরা থাকে।
৬ · Translation validation — compiler নয়, প্রতিবারের ফল যাচাই
পুরো compiler প্রমাণ করা বিশাল কাজ, আর GCC বা LLVM-এর মতো বড় compiler-এ তা আজও বাস্তবসম্মত নয়। একটি মাঝামাঝি পথ: compiler-কে বিশ্বাস না করে, প্রতিবার compile করার পরে একটি আলাদা ছোট program দিয়ে যাচাই করা, “এই নির্দিষ্ট input-এর এই নির্দিষ্ট output কি সমতুল্য?”। এর নাম translation validation; ধারণাটি সাধারণত Amir Pnueli, Michael Siegel আর Eli Singerman-এর ১৯৯৮ সালের কাজের সঙ্গে যুক্ত, আর George Necula ২০০০ সালে একটি optimizing C compiler-এর জন্য এটি দেখান।
পরীক্ষার হলের উপমা ধরা যায়: প্রতিটি পরীক্ষার্থী (compiler) কীভাবে ভাবে, তা প্রমাণ করা কঠিন, কিন্তু প্রতিটি খাতা (output) একটি উত্তরমালা দিয়ে মিলিয়ে দেখা সহজ। Validator নিজে ছোট, তাই তাকে প্রমাণ করা বা বিশ্বাস করা সহজ। শর্ত একটিই: validator sound হতে হবে, অর্থাৎ “গ্রহণ” বললে সত্যিই সমতুল্য। সে complete না হলেও চলে: কখনো কখনো সঠিক output-কেও “প্রমাণ করা গেল না” বলতে পারে; তখন compiler optimization ছাড়া পুরোনো code রাখে।
নিচের block-এ একটি ছোট validator. Optimizer stack code-এ peephole folding করে; validator দুই code-কে মানের বদলে polynomial (mod 264) দিয়ে চালায়, প্রতিটি পদকে একটি স্বাভাবিক রূপে এনে মেলায়। দুটি polynomial হুবহু এক হলে সব input-এ মান এক, তাই এই “গ্রহণ” একটি প্রমাণ।
# Translation validation: প্রতিটি optimize-এর পরে আগে-পরের stack code মিলিয়ে দেখা
from math import prod; M, OPC = 2**64, {"+": "ADD", "-": "SUB", "*": "MUL"}
def gen(e): # expression → stack code
if not isinstance(e, tuple): return [("CONST" if isinstance(e, int) else "LOAD", e)]
return gen(e[1]) + gen(e[2]) + [(OPC[e[0]], None)]
def peephole(code): # অবিশ্বস্ত optimizer
out = []
for ins in code:
out.append(ins)
a, b, c = ([(None, None)] * 3 + out)[-3:]
if a[0] == b[0] == "CONST" and c[0] in ("ADD", "MUL"):
out[-3:] = [("CONST", wrap(a[1] + b[1] if c[0] == "ADD" else a[1] * b[1]))]
return out
def poly(code): # মানের বদলে polynomial (mod 2^64) দিয়ে stack চালানো
st = []
for op, arg in code:
if op in ("CONST", "LOAD"):
st.append({(arg,): 1} if op == "LOAD" else {(): arg % M} if arg % M else {}); continue
q, p, r = st.pop(), st.pop(), {}
terms = [(m1 + m2, c1 * c2) for m1, c1 in p.items() for m2, c2 in q.items()] if op == "MUL" \
else list(p.items()) + [(m, -c if op == "SUB" else c) for m, c in q.items()]
for m, c in terms: m = tuple(sorted(m)); r[m] = (r.get(m, 0) + c) % M
st.append({m: c for m, c in r.items() if c})
return st[0]
def validate(before, after):
if (P := poly(before)) == (Q := poly(after)): return "গ্রহণ: সব input-এ সমান, প্রমাণিত"
val = lambda p, s: sum(c * prod(s[v] for v in m) for m, c in p.items()) % M
bad = [x for x in (0, 1, 2, 7, -1) if val(P, {"x": x, "y": x + 5}) != val(Q, {"x": x, "y": x + 5})]
return f"বাতিল: x={bad[0]}, y={bad[0] + 5}-তে আলাদা" if bad else "বাতিল: সমতা প্রমাণ হলো না"
show = lambda code: " ".join(op if a is None else f"{op} {a}" for op, a in code)
def report(b, a): print(show(b), "⇒", show(a), "\n ", validate(b, a))
b = gen(("+", ("*", 2, 520), "x")); report(b, peephole(b))
b = gen(("-", "x", "y")); report(b, [b[1], b[0], b[2]]) # ভুল optimizer: SUB অদলবদল
report(gen(("*", ("+", ("*", "x", "x"), "x"), -2**63)), [("CONST", 0)]) # x(x+1)·2^63 = 0আসল আউটপুট (ব্রাউজারের Python):
CONST 2 CONST 520 MUL LOAD x ADD ⇒ CONST 1040 LOAD x ADD
গ্রহণ: সব input-এ সমান, প্রমাণিত
LOAD x LOAD y SUB ⇒ LOAD y LOAD x SUB
বাতিল: x=0, y=5-তে আলাদা
LOAD x LOAD x MUL LOAD x ADD CONST -9223372036854775808 MUL ⇒ CONST 0
বাতিল: সমতা প্রমাণ হলো না
প্রথম জোড়ায় optimizer CONST 2 CONST 520 MUL-কে CONST 1040 বানিয়েছে; দুই পাশের polynomial 1040 + x, তাই validator গ্রহণ করল, আর এই গ্রহণ সব 264 মানের জন্য সত্য। দ্বিতীয় জোড়ায় একটি ভুল optimizer x - y-কে y - x বানিয়েছে (বিয়োগকে অদলবদলযোগ্য ভেবে); polynomial আলাদা, আর validator একটি নির্দিষ্ট পাল্টা উদাহরণও দিল। তৃতীয় জোড়া সবচেয়ে শিক্ষণীয়: অংশ ৪-এ Z3 প্রমাণ করেছে (x·x + x)·263 সব মানে 0, তাই এই রূপান্তর আসলে সঠিক. কিন্তু polynomial-এর তুলনা তা দেখতে পায় না (সহগ 263 শূন্য নয়), আর কোনো পাল্টা উদাহরণও পায় না। Validator sound কিন্তু complete নয়: সে সঠিক কাজটিও বাতিল করল, আর তাতে ক্ষতি শুধু একটি হারানো optimization, ভুল program নয়।
এই ধারণার সবচেয়ে প্রভাবশালী আধুনিক রূপ Alive (Nuno Lopes, David Menendez, Santosh Nagarakatte, John Regehr; PLDI ২০১৫): LLVM-এর peephole নিয়মগুলো একটি ছোট ভাষায় লিখে Z3 দিয়ে প্রতিটি নিয়ম যাচাই করা, যা LLVM-এর InstCombine অংশে বাস্তব ভুল খুঁজে পায় বলে জানানো হয়। পরের Alive2 (PLDI ২০২১) পুরো function-এর আগে-পরে LLVM IR মিলিয়ে দেখে, অর্থাৎ প্রকৃত translation validation. এগুলো আবার undefined behavior-এর প্রশ্নে ফিরে আসে: LLVM IR-এ poison আর undef-এর মতো মানের সূক্ষ্ম semantics ঠিকমতো লিখে না নিলে যাচাই অর্থহীন। LLVM IR-এর বিস্তারিত পর্ব ৬৮-এ।
৭ · পরীক্ষা, প্রমাণ আর বাস্তব — property, random testing, seL4 আর WebAssembly
প্রমাণ দামি, তাই বাস্তবে testing আর verification পাশাপাশি চলে। সবচেয়ে কাছের সেতু property-based testing: নির্দিষ্ট উদাহরণের বদলে একটি property লেখা (যেমন “সব e আর σ-তে ⟦fold(e)⟧σ = ⟦e⟧σ”, Theorem ৪৪.১-এর হুবহু বাক্য), আর tool এলোমেলো input বানিয়ে খোঁজে। Haskell-এর QuickCheck (Koen Claessen আর John Hughes, ICFP ২০০০) এই ধারার শুরু; Python-এ Hypothesis একই ধারণার একটি জনপ্রিয় রূপ। ব্যর্থ input পেলে tool তাকে ছোট করে (shrinking), যাতে সবচেয়ে সরল পাল্টা উদাহরণ মেলে। পুরো পদ্ধতি Software Testing & QA-এর পর্ব ৫৮-এ (Property-based testing). লক্ষ করুন, property আর theorem একই বাক্য; পার্থক্য শুধু নিশ্চয়তার উৎসে।
Compiler testing-এর সবচেয়ে বিখ্যাত উদাহরণ Csmith (Xuejun Yang, Yang Chen, Eric Eide, John Regehr; PLDI ২০১১): undefined behavior ছাড়া এলোমেলো C program বানিয়ে কয়েকটি compiler-এ চালানো, আর আউটপুট মেলানো, অর্থাৎ differential testing. নিচের block একই ধারণা ছোট আকারে: এলোমেলো Haat-core expression, একটি compiler + stack VM, আর oracle হিসেবে অংশ ২-এর ⟦e⟧σ. একটি VM-এ ইচ্ছা করে একটি বাস্তবসম্মত bug রাখা হয়েছে: Python-এর // (নিচের দিকে কাটা) দিয়ে ভাগ, Haat-এর শূন্যের দিকে কাটার বদলে।
# Csmith-এর ধারণা ছোট করে: এলোমেলো expression, compiler + VM বনাম ⟦e⟧σ
import random
CODE = {"+": "ADD", "-": "SUB", "*": "MUL", "/": "DIV", "%": "MOD"}
def comp(e): # expression → stack code (সব operator)
if isinstance(e, int): return [("CONST", e)]
if isinstance(e, str): return [("LOAD", e)]
return comp(e[1]) + comp(e[2]) + [(CODE[e[0]], None)]
def vm(code, s, floor_bug=False): # stack VM
st = []
for op, arg in code:
if op == "CONST": st.append(arg)
elif op == "LOAD": st.append(s[arg])
else:
b, a = st.pop(), st.pop()
if op in ("DIV", "MOD") and b == 0: return "err"
if floor_bug and op == "DIV": st.append(wrap(a // b)); continue # Python-ধাঁচের ভাগ
st.append(wrap(OPS[{v: k for k, v in CODE.items()}[op]](a, b)))
return st[0]
def rand_expr(r, depth): # ছোট এলোমেলো expression
if depth == 0 or r.random() < 0.3:
return r.choice(["x", "y", r.randint(-9, 9)])
return (r.choice("+-*/%"), rand_expr(r, depth - 1), rand_expr(r, depth - 1))
def campaign(floor_bug, n=3000):
r, worst, bad = random.Random(2011), None, 0
for _ in range(n):
e, s = rand_expr(r, 3), {"x": r.randint(-50, 50), "y": r.randint(-50, 50)}
if ev(e, s) != vm(comp(e), s, floor_bug):
bad += 1
if worst is None or len(sh(e)) < len(sh(worst[0])): worst = (e, s)
if worst is None: return f"{n}টি program-এ কোনো অমিল নেই"
e, s = worst
return f"{bad}টি অমিল! ছোটটি: {sh(e)}, x={s['x']} y={s['y']}: ⟦e⟧ = {ev(e, s)}, VM = {vm(comp(e), s, True)}"
print("ঠিক VM: ", campaign(False))
print("ভুল VM: ", campaign(True))আসল আউটপুট (ব্রাউজারের Python):
ঠিক VM: 3000টি program-এ কোনো অমিল নেই
ভুল VM: 354টি অমিল! ছোটটি: (x / y), x=-27 y=29: ⟦e⟧ = 0, VM = -1
সঠিক VM ৩০০০টি এলোমেলো program-এ (শূন্য দিয়ে ভাগের err-সহ) ⟦e⟧σ-এর সঙ্গে মিলেছে। ভুল VM-এ ৩৫৪টি অমিল, আর সবচেয়ে ছোটটি একেবারে মূল কারণ দেখায়: −27 / 29 Haat-এ (C-র মতো) 0, কিন্তু নিচের দিকে কাটলে −1. এটি এলোমেলো testing-এর শক্তি: কোনো মানুষ এই test case হাতে লেখেননি। আর তার সীমাও: ঠিক VM-এর “কোনো অমিল নেই” একটি প্রমাণ নয়, শুধু ৩০০০টি নমুনার ফল। লক্ষ করুন, ভুলটি শুধু ঋণাত্মক আর ধনাত্মক মিশে থাকলে দেখা দেয়; যদি generator শুধু ধনাত্মক সংখ্যা বানাত, এই bug কখনো ধরা পড়ত না। Random testing-এর মান তাই generator-এর মানের ওপর নির্ভর করে, যা Csmith-এর গবেষকদেরও মূল চিন্তা ছিল।
বড় মাপের verification: kernel আর ভাষার spec
Compiler-এর বাইরেও formal verification বাস্তবে পৌঁছেছে। seL4 (Gerwin Klein ও সহকর্মীরা, SOSP ২০০৯) একটি microkernel, যার C বাস্তবায়ন তার abstract specification মানে, এমন প্রমাণ Isabelle/HOL-এ; লেখকেরা জানান কয়েক হাজার লাইন C-র জন্য প্রমাণ লাগে তার বহুগুণ, আর কাজে বহু মানুষ-বছর লাগে (পর্ব ৩৯-এ এর উল্লেখ)। ভাষার দিকে, WebAssembly-র মানদণ্ড শুরু থেকেই formal semantics-এ লেখা হয়েছে (Haas ও সহকর্মীরা, PLDI ২০১৭), আর Conrad Watt ২০১৮ সালে তার type soundness Isabelle-এ যন্ত্র-যাচাই করেন (পর্ব ৩৮-এ উল্লেখিত)। এমন mechanized semantics থাকলে একটি ভাষার নিয়ম নিয়ে তর্ক হয় না: proof assistant-এর সংজ্ঞাই উত্তর, আর বাস্তবায়নগুলোকে সেই সংজ্ঞার সঙ্গে মিলিয়ে test করা যায়।
আরও গভীরে। প্রমাণের দাম কমাতে গবেষণা দুই দিকে চলছে। এক, স্বয়ংক্রিয়তা: SMT solver-এর সঙ্গে proof assistant জোড়া (Isabelle-এর Sledgehammer বাইরের solver দিয়ে প্রমাণ খোঁজে, আর পাওয়া প্রমাণ আবার kernel-এ যাচাই হয়), আর Lean-এর bv_decide-এর মতো tactic, যা SAT solver-এর উত্তরের সঙ্গে একটি প্রমাণ-সনদ এনে kernel-কে দেয়। দুই, বিশ্বাসের কেন্দ্র ছোট করা: লেখকের lab-এ Lean 4.36.0-এর Windows বিতরণে মূল lean-এর পাশে leanchecker, lean4lean আর nanoda_bin নামের আলাদা checker-এর executable-ও দেখা গেছে, যা একই প্রমাণ স্বাধীনভাবে আবার যাচাই করার ধারণার সঙ্গে মেলে।
পরীক্ষা ও ইন্টারভিউতে। বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন সাধারণ:
- “Testing আর formal verification-এর পার্থক্য?” Testing কিছু input-এ ভুল খোঁজে; verification spec-এর সাপেক্ষে সব input-এর জন্য গাণিতিক প্রমাণ দেয়, কিছু অংশ (TCB) বিশ্বাস করে।
- “Verified compiler কী প্রমাণ করে?” Semantic preservation: সংজ্ঞায়িত আচরণের source থেকে বানানো target-এর পর্যবেক্ষণযোগ্য আচরণ source-এর মতো; উদাহরণ CompCert (Coq).
- “Constant folding যে ঠিক, প্রমাণ করুন।” Expression-এর গঠনের ওপর structural induction; folder আর semantics একই wrap ব্যবহার করে; ভাজক 0 হলে fold নয়।
- “Translation validation আর verified compiler-এর পার্থক্য?” প্রথমটি প্রতিটি compile-এর ফল আলাদা যাচাই করে (validator sound, complete না-ও হতে পারে); দ্বিতীয়টি compiler-কে একবারে সব input-এর জন্য প্রমাণ করে।
- “
x * 2 / 2-কেxবানানো কি ঠিক?” ভাষার ওপর নির্ভর করে: wrap-এর ভাষায় (Haat, C-র unsigned) ভুল, পাল্টা উদাহরণ 262; C-র signed-এ overflow UB, তাই compiler করতে পারে।
৮ · AI-এর যুগে formal verification
AI assistant প্রমাণ, Lean code আর SMT query দ্রুত লেখে। এখানে একটি বড় সুবিধা আছে: proof assistant নিজেই যাচাইকারী, তাই AI-এর লেখা প্রমাণ kernel পাস করলে তা মানুষের লেখা প্রমাণের মতোই নির্ভরযোগ্য। কিন্তু kernel শুধু প্রমাণ দেখে, দাবি নয়। এই বিষয়ে AI-এর সাধারণ ভুল:
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| সাধারণ পূর্ণসংখ্যার গণিতে নিয়ম “প্রমাণ” করা, wrap বা ভাষার ভাগের নিয়ম ভুলে যাওয়া | Z3-এ ৬৪-বিট bit-vector দিয়ে নিয়মটি যাচাই, আর পাল্টা উদাহরণ reference-এ চালানো |
এক ভাষার নিয়ম সব ভাষায়: “compiler x + 1 > x-কে true বানায়, তাই এটি সবসময় ঠিক” | ভাষা আর version উল্লেখ চাওয়া; C-র signed UB, C-র unsigned, Haat-এর wrap আলাদা করে দেখা |
প্রমাণে sorry, বাড়তি axiom বা দাবি দুর্বল করে দেওয়া | Lean-এ #print axioms; Rocq-এ Print Assumptions; theorem-এর বাক্য নিজে পড়ে মেলানো |
| Spec ভুল লেখা (যেমন eval-এ err বাদ), তারপর সঠিক প্রমাণ দেখানো | Spec-এর সংজ্ঞা reference implementation-এর সঙ্গে random testing-এ মেলানো |
| অস্তিত্বহীন tactic, lemma বা solver option বানিয়ে লেখা | সত্যিকারের tool-এ চালানো; error এলে নাম documentation-এ খোঁজা |
SMT-এর x / 0 বা bounded test-এর “সমান”-কে ভাষার আচরণ বা প্রমাণ বলে চালানো | Solver-এর semantics আলাদা করে পড়া; bounded ফলকে শুধু পাল্টা উদাহরণ খোঁজার যন্ত্র ধরা |
AI-কে কাজে লাগাতে semantics স্পষ্ট বলুন, আর প্রতিটি দাবির যাচাইযোগ্য রূপ চান:
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Dijkstra বলেছিলেন testing bug-এর অনুপস্থিতি দেখাতে পারে না। তাহলে আজও প্রায় সব software শুধু test করেই কেন ছাড়া হয়?
Dijkstra-র কথাটি যুক্তিতে নিখুঁত: ৬৪-বিটের দুটি input-এর জোড়া 2128টি, আর কোনো test suite তার নগণ্য অংশও ছুঁতে পারে না। কিন্তু প্রকৌশল শুধু যুক্তি নয়, খরচ আর ঝুঁকির হিসাবও। Formal verification-এর প্রথম দাম specification: “এই program ঠিক কী করবে” গাণিতিক ভাষায় লেখা, যা অনেক software-এর জন্য নিজেই কঠিন (একটি ওয়েবসাইটের “সুন্দর দেখানো”-র spec কেমন হবে?)। দ্বিতীয় দাম প্রমাণ: seL4-এর লেখকেরা জানান, কয়েক হাজার লাইন C-র জন্য বহুগুণ বেশি প্রমাণের লাইন আর বহু মানুষ-বছর লেগেছে। তৃতীয় দাম রক্ষণাবেক্ষণ: code বদলালে প্রমাণও বদলাতে হয়।
অন্যদিকে testing-এর ফলাফলও দুর্বল নয়। Csmith ২০১১ সালে GCC আর LLVM-এ কয়েকশো আগে-অজানা bug পায়, যে compiler দুটি তখনই কোটি মানুষ ব্যবহার করতেন। এই পর্বের random test-এ শুধু ৩০০০টি এলোমেলো expression দিয়ে VM-এর ভাগের ভুল ধরা পড়েছে। ভুলের বড় অংশ সাধারণ জায়গায় থাকে, আর সেখানে testing সস্তায় পৌঁছায়।
তাই বাস্তবের উত্তর “দুটির একটি” নয়, ঝুঁকি অনুযায়ী মিশ্রণ। যেখানে একটি ভুলের দাম বিপুল (বিমান, রেল সংকেত, চিকিৎসা যন্ত্র, cryptography-র library, OS kernel, compiler), সেখানে formal পদ্ধতি বাড়ছে। বড় cloud আর hardware প্রকল্পেও TLA+-এর মতো specification ভাষা আর SMT-ভিত্তিক যাচাই ব্যবহারের অভিজ্ঞতা প্রকাশিত হয়েছে। সাধারণ app-এ testing, type system আর code review সাধারণত যথেষ্ট। মাঝের পথও আছে: property-based testing একটি property লেখায়, যা পরে theorem হতে পারে; SMT একটি নির্দিষ্ট নিয়ম প্রমাণ করে, পুরো program নয়। এই পর্বের constant folding-ই উদাহরণ: bounded checker দ্রুত ভুল নিয়ম ধরল, Z3 নিয়মগুলো সব মানে প্রমাণ করল, আর Lean পুরো folder-এর theorem যাচাই করল।
মূল উপলব্ধি: testing আর proof প্রতিদ্বন্দ্বী নয়, একই সিঁড়ির ধাপ; কোন ধাপ পর্যন্ত উঠবেন, তা ঠিক করে ভুলের দাম আর spec লেখার সম্ভাবনা।
প্র ০২“প্রমাণ যাচাই করে যে checker, তাকে কে যাচাই করে?” Verified software-এ শেষ পর্যন্ত কী বিশ্বাস করতে হয়?
প্রশ্নটি পুরোনো আর ন্যায্য। একটি proof assistant-ও software, তারও bug থাকতে পারে। এর উত্তর তিন স্তরে। প্রথম, ছোট kernel: de Bruijn criterion অনুযায়ী প্রমাণের সব জটিল যন্ত্র (tactic, স্বয়ংক্রিয় খোঁজ, elaborator) শেষে একটি সরল প্রমাণ-বস্তু বানায়, আর একটি ছোট kernel সেটি যাচাই করে। Tactic ভুল করলে kernel প্রমাণ বাতিল করবে; তাই বিশ্বাস করতে হয় শুধু kernel-কে, যা মানুষ পড়ে দেখতে পারে। দ্বিতীয়, স্বাধীন পুনর্যাচাই: একই প্রমাণ আলাদা লোকের লেখা আলাদা checker দিয়ে আবার যাচাই করা। লেখকের lab-এ Lean 4.36.0-এর বিতরণে মূল lean ছাড়াও leanchecker, lean4lean আর nanoda_bin নামের checker দেখা গেছে; দুটি স্বাধীন checker-এ একই ভুল থাকার সম্ভাবনা অনেক কম। তৃতীয়, স্বতঃসিদ্ধের হিসাব: #print axioms ঠিক কোন axiom-এর ওপর প্রমাণ দাঁড়িয়ে আছে তা দেখায়; এই পর্বের fold_correct শুধু propext-এর ওপর।
তবু যা থেকে যায়, তা প্রায়ই kernel-এর চেয়ে বড় ঝুঁকি: specification. CompCert-এর ক্ষেত্রে Csmith-এর গবেষকেরা প্রমাণিত অংশে ভুল-কোড bug পাননি, কিন্তু প্রমাণের বাইরের অংশে কয়েকটি সমস্যা পান বলে জানান। অর্থাৎ ভুল থাকে সীমানায়: যেখানে প্রমাণ শেষ, যেখানে মডেল বাস্তবকে ধরে নেয়। একটি verified compiler-এর প্রমাণ “target-এর semantics” নামের একটি সংজ্ঞার সাপেক্ষে; CPU সত্যিই সেই সংজ্ঞা মানে কি না, তা আরেক প্রশ্ন। আর পর্ব ০৪-এর Thompson-এর “Trusting Trust” মনে করায়, proof checker-কে compile করেছে যে compiler, সেটিও শৃঙ্খলের অংশ। CakeML-এর মতো কাজ এই শৃঙ্খলকেও প্রমাণের ভেতরে আনার চেষ্টা করে।
এই পর্বের Lean উদাহরণেও শিক্ষাটি স্পষ্ট: theorem পাস করেছে, কিন্তু eval Haat-এর আসল semantics-এর সঙ্গে মেলে কি না, Lean জানে না। লেখক তাই random testing-এ reference-এর সঙ্গে মিলিয়ে দেখেছেন। Spec-এর ভুল ধরার কাজ এখনো মূলত মানুষের, আর testing সেখানে প্রমাণের সঙ্গী।
মূল উপলব্ধি: verification বিশ্বাস দূর করে না, বিশ্বাসকে ছোট, স্পষ্ট আর পড়ার মতো কয়েকটি অংশে নিয়ে আসে; spec সেই অংশগুলোর মধ্যে সবচেয়ে গুরুত্বপূর্ণ।
প্র ০৩Clang C-র long-এ x * 2 / 2-কে x বানায়, Haat-এর optimizer পারে না। Undefined behavior কি optimizer-এর সুবিধা, না ভাষার দুর্বলতা?
দুটিই, আর এটি ভাষা নকশার একটি গভীর আপস। C মানদণ্ড signed overflow-কে undefined বলে, ইতিহাসের একটি কারণে: ১৯৭০–৮০-এর দশকে সব যন্ত্র two's complement ছিল না, তাই overflow-এর একটি নির্দিষ্ট ফল বেঁধে দেওয়া কঠিন ছিল। পরে compiler-লেখকেরা এর একটি শক্তিশালী ব্যবহার পান: “overflow হয় না” ধরে নিলে অনেক রূপান্তর বৈধ হয়। x * 2 / 2 → x, x + 1 > x → true, আর loop-এর counter নিয়ে বহু অনুমান (যেমন for (int i = 0; i < n; i++) কখনো ঘুরে আসে না, তাই loop ঠিক n বার চলে)। এই পর্বের Clang 22.1.8-এর সত্যিকারের run-এ half_double শুধু mov rax, rdi.
দাম দেন programmer. যে program-এ overflow সত্যিই ঘটে, তার কোনো নির্দিষ্ট অর্থ থাকে না, আর optimizer-এর রূপান্তর এমন আচরণ আনতে পারে যা source পড়ে অনুমান করা যায় না। নিরাপত্তার বহু সমস্যা এমন জায়গা থেকে এসেছে বলে বর্ণনা পাওয়া যায়: একটি overflow-check (if (x + 1 < x)) optimizer মুছে দিল, কারণ C-র নিয়মে তা কখনো সত্য হতে পারে না। Verification-এর দৃষ্টিতে ব্যাপারটি স্পষ্ট: CompCert-এর theorem-ও শুধু UB ছাড়া program-এর জন্য, কারণ UB-এর program-এর কোনো “source আচরণ” নেই যা রক্ষা করা যায়।
অন্য ভাষাগুলো অন্য পথ নিয়েছে। Java-তে int overflow সংজ্ঞা অনুযায়ী wrap করে। Rust-এ debug build-এ overflow panic, release build-এ (ডিফল্টে) wrap, আর wrapping_add, checked_add-এর মতো স্পষ্ট বিকল্প আছে। Haat-এর সিদ্ধান্ত ১৩ Java-র পথ নিয়েছে: সব হিসাব wrap. ফলে Haat-এর optimizer কিছু নিয়ম হারায় (এই পর্বে Z3 দেখিয়েছে কোনগুলো), কিন্তু প্রতিটি program-এর একটি নির্দিষ্ট অর্থ থাকে, আর সেই অর্থ রক্ষার প্রমাণ সরল। পর্ব ০৬-এর ভাষা নকশার আপস এখানে সরাসরি optimizer-এর নিয়মের তালিকায় দেখা যায়।
মূল উপলব্ধি: optimization-এর সঠিকতা ভাষার semantics-এর সাপেক্ষে; UB optimizer-কে বেশি স্বাধীনতা দেয়, programmer-এর কাছ থেকে নিশ্চয়তা কেড়ে নেয়, আর verification সেই চুক্তিটি স্পষ্ট করে দেখায়।
প্র ০৪Verified compiler, translation validation আর ব্যাপক testing — একটি নতুন compiler-এর জন্য কোনটি বেছে নেবেন?
তিনটি পথের খরচ আর নিশ্চয়তা আলাদা। Verified compiler (CompCert, CakeML) সবচেয়ে বড় নিশ্চয়তা দেয়: সব input-এর জন্য একবারে প্রমাণ। কিন্তু compiler-কে proof assistant-এর ভাষায় লিখতে হয়, প্রতিটি নতুন optimization-এর সঙ্গে simulation প্রমাণ লাগে, আর optimization-এর বৈচিত্র্য সাধারণত GCC বা LLVM-এর চেয়ে কম রাখতে হয়। CompCert-এর তৈরি code-এর গতি নিয়ে প্রকাশিত তুলনাগুলোতে সাধারণত বলা হয়, তা GCC-র মাঝারি optimization স্তরের কাছাকাছি; নির্দিষ্ট সংখ্যা যন্ত্র আর program-ভেদে আলাদা।
Translation validation বিদ্যমান, অবিশ্বস্ত compiler রাখে, আর প্রতিটি ফলের জন্য একটি ছোট validator চালায়। সুবিধা: compiler-লেখকেরা স্বাধীনভাবে নতুন optimization যোগ করতে পারেন, আর validator-এর সঠিকতা প্রমাণ করা তুলনায় সহজ। অসুবিধা: প্রতি compile-এ বাড়তি সময়, আর validator complete না হলে কিছু সঠিক optimization বাতিল হয় (এই পর্বের polynomial validator ঠিক এটিই করেছে)। Alive-এর অভিজ্ঞতা দেখায়, নিয়মগুলো একবার যাচাই করা (প্রতিটি compile নয়) একটি সস্তা মাঝামাঝি পথ: LLVM-এর peephole নিয়মের বাস্তব ভুল এভাবে ধরা পড়েছে বলে জানানো হয়।
ব্যাপক testing (Csmith-ধাঁচের random program, differential testing, fuzzing) সবচেয়ে সস্তা আর সবচেয়ে ব্যাপকভাবে ব্যবহৃত। কোনো নিশ্চয়তা দেয় না, কিন্তু বড় compiler-এ বিপুল সংখ্যক bug ধরেছে। তার একটি সমস্যা oracle: “সঠিক উত্তর কী?” জানতে হয়; এ জন্য দুটি compiler-এর তুলনা বা একটি reference interpreter (এই পর্বে ⟦e⟧σ) লাগে।
Haat-এর মতো একটি নতুন ভাষার জন্য একটি বাস্তবসম্মত পরিকল্পনা: reference interpreter-কে oracle ধরে শুরু থেকেই differential আর random testing (reference implementation ঠিক এটি করে, ৪০০টি seeded এলোমেলো expression দিয়ে interpreter আর VM মিলিয়ে); প্রতিটি algebraic rewrite নিয়ম Z3-এ যাচাই; আর সবচেয়ে ঝুঁকিপূর্ণ pass (যেমন register allocation) পরে translation validation দিয়ে পাহারা। পুরো verified compiler তখনই, যখন ব্যবহারের ক্ষেত্র (নিরাপত্তা-সংবেদনশীল embedded code) সেই দাম ন্যায্য করে।
মূল উপলব্ধি: নিশ্চয়তা কেনা যায় ধাপে ধাপে; testing সব জায়গায়, নিয়ম-স্তরের SMT যাচাই যেখানে সস্তা, আর পূর্ণ প্রমাণ সেখানে, যেখানে ভুলের দাম তাকে ন্যায্য করে।
প্র ০৫একটি ভাষার মানদণ্ড নিজেই যদি proof assistant-এ লেখা থাকে, কী লাভ হয়? Haat-এর জন্য এটি করতে কী লাগবে?
বেশিরভাগ ভাষার মানদণ্ড ইংরেজি গদ্যে লেখা, আর গদ্যে অস্পষ্টতা থেকেই যায়। পর্ব ০৩ আর পর্ব ৪০-এ এমন উদাহরণ দেখেছেন: একই লেখা দুই ভাষায় দুই অর্থ, আর একই ভাষার দুটি compiler একটি কোণার ক্ষেত্রে দুই রকম আচরণ। Mechanized semantics মানে ভাষার নিয়মগুলো proof assistant-এর সংজ্ঞা হিসেবে লেখা। লাভ চারটি। এক, অস্পষ্টতা থাকে না: সংজ্ঞাই উত্তর। দুই, মানদণ্ডের গুণ প্রমাণ করা যায়, যেমন type soundness (পর্ব ৩৮); WebAssembly-র ক্ষেত্রে Conrad Watt-এর ২০১৮ সালের Isabelle-এর কাজ মানদণ্ডে কিছু সমস্যা চিহ্নিত করে বলে জানানো হয়, যা পরে ঠিক করা হয়। তিন, সংজ্ঞা থেকে চালানো যায় এমন reference interpreter বের করা যায়, আর বাস্তব engine-গুলোকে তার সঙ্গে test করা যায়। চার, compiler-এর প্রমাণের জন্য একটি নির্দিষ্ট “source semantics” তৈরি থাকে।
WebAssembly-র সুবিধা ছিল যে ভাষাটি নতুন, ছোট, আর শুরু থেকেই formal নিয়মে লেখা (Haas ও সহকর্মীদের PLDI ২০১৭ প্রবন্ধ)। JavaScript বা C-র মতো পুরোনো, বড় ভাষার জন্যও গবেষকেরা mechanized semantics বানিয়েছেন (যেমন JavaScript-এর জন্য JSCert, C-র একটি অংশের জন্য CompCert নিজেই), কিন্তু সেগুলো মানদণ্ডের সরকারি রূপ নয়, আর মানদণ্ড বদলালে তাল রাখা কঠিন।
Haat-এর জন্য পথটি এই মডিউল থেকেই দেখা যায়। পর্ব ৪০-এর small-step নিয়ম, পর্ব ৪১-এর ⟦·⟧, আর reference README-র ২৮টি “Spec decisions” একসঙ্গে প্রায় একটি formal spec. কাজ হবে: Haat-core-এর AST Lean-এ inductive হিসেবে লেখা (এই পর্বের Expr-এর মতো, Bool, while আর print যোগ করে); small-step নিয়মগুলো একটি inductive সম্পর্ক হিসেবে; wrap-এর জন্য Int64, ভাগের জন্য শূন্যের দিকে কাটা আর err; তারপর determinism (পর্ব ৪০), adequacy (পর্ব ৪১) আর type soundness (পর্ব ৩৮) প্রমাণ। সংজ্ঞা থেকে একটি interpreter বের করে reference-এর ৩২টি test আর এলোমেলো program-এ মিলিয়ে দেখলে spec-এর ভুলও ধরা পড়বে।
মূল উপলব্ধি: mechanized semantics একটি ভাষার নিয়মকে তর্কের বিষয় থেকে যাচাইযোগ্য বস্তুতে বদলায়; ছোট আর নতুন ভাষায় এটি শুরু থেকে করা সবচেয়ে সস্তা।
অনুশীলন
প্রথমে নিজে লিখুন বা হিসাব করুন, তারপর উত্তর খুলুন। প্রতিটি উত্তর চালানো code বা সত্যিকারের tool দিয়ে যাচাই করা।
-
নকশা ও বাস্তবায়ন — নিরাপদ algebraic নিয়ম: অংশ ২-এর folder-এ এই নিয়মগুলো যোগ করুন:
e + 0 → e,0 + e → e,e * 1 → e, আরe * 0 → 0, শেষটি শুধু তখন, যখন e কখনো err দিতে পারে না। (ক) “কখনো err দেয় না”-র একটি সরল, sound পরীক্ষা লিখুন। (খ) একইcheckদিয়ে চারটি expression যাচাই করুন:(100 / y) * (5 - 5),(x + y) * (5 - 5),x * 1 + 0 * 7,(x % y) * 1.(ক) Haat-core expression-এ err শুধু
/আর%থেকে আসে, তাই “ভেতরে কোনো ভাগ নেই” একটি sound পরীক্ষা (complete নয়:x / 2কখনো err দেয় না, তবু বাদ পড়ে)। (খ) কোড:def safe(e): # / বা % নেই, তাই কখনো err দেয় না return not isinstance(e, tuple) or (e[0] not in "/%" and safe(e[1]) and safe(e[2])) def fold2(e): if not isinstance(e, tuple): return e op, a, b = e[0], fold2(e[1]), fold2(e[2]) if isinstance(a, int) and isinstance(b, int) and not (op in "/%" and b == 0): return wrap(OPS[op](a, b)) if op == "+" and b == 0: return a # e + 0 → e if op == "+" and a == 0: return b # 0 + e → e if op == "*" and b == 1: return a # e * 1 → e if op == "*" and b == 0 and safe(a): return 0 # e * 0 → 0, e নিরাপদ হলে return (op, a, b)লেখকের lab-এ চালানো (CPython 3.14):
((100 / y) * (5 - 5)) ⇒ ((100 / y) * 0) → সমান, 2064টি state-এ ((x + y) * (5 - 5)) ⇒ 0 → সমান, 2064টি state-এ ((x * 1) + (0 * 7)) ⇒ x → সমান, 2064টি state-এ ((x % y) * 1) ⇒ (x % y) → সমান, 2064টি state-এপ্রথমটিতে ভাগ আছে, তাই
* 0মোছা হয়নি, আর y = 0-তে err থেকে গেছে। দ্বিতীয়টিতে ভাগ নেই, তাই পুরোটা 0.e + 0 → eআরe * 1 → eerr থাকলেও ঠিক, কারণ দুই পাশে একই e থাকে: e err দিলে দুই পাশই err (চতুর্থ লাইন)। প্রতিটি নিয়ম Z3-এ যাচাইও করা যায়:x + 0 → xআরx * 1 → xbit-vector-এ সরাসরি প্রমাণিত হয়। -
ভুল খুঁজুন: একজন লিখলেন: “Optimizer
x / 2-কে arithmetic shiftx >> 1বানাতে পারে। প্রমাণ: (১) x = 2q + r, যেখানে r ∈ {0, 1}; (২) ডানে এক ঘর shift মানে শেষ বিট ফেলে দেওয়া, তাই x >> 1 = q; (৩) x / 2 = q, কারণ r দুইয়ের চেয়ে ছোট। ∎” Haat-এর ভাগ (শূন্যের দিকে কাটা) ধরে কোন ধাপ ভুল? একটি ছোট পাল্টা উদাহরণ দিন আর সঠিক রূপান্তরটি লিখুন।ধাপ ৩ ভুল। ধাপ ১ আর ২ floor division-এর কথা: x = 2q + r, r ∈ {0, 1} হলে q = ⌊x / 2⌋, আর arithmetic shift ঠিক এটিই দেয়। কিন্তু Haat (আর C) ভাগে শূন্যের দিকে কাটে: ঋণাত্মক বিজোড় x-এ ফল floor-এর চেয়ে এক বেশি। সবচেয়ে ছোট পাল্টা উদাহরণ x = −1: Haat-এ
-1 / 2= 0, কিন্তু −1 >> 1 = −1 (সব বিট 1 থাকে)। আরেকটি x = −3: Haat-এ −1, shift-এ −2. Reference-এ সত্যিকারের run:print(-1 / 2); print(-3 / 2);ছাপে0আর-1. অংশ ৪-এর Z3 run-ও পাল্টা উদাহরণ দিয়েছিল (x = −50179819698126849).সঠিক রূপান্তর: আগে ঋণাত্মক হলে 1 যোগ, তারপর shift:
(x + ((x >> 63) & 1)) >> 1. লেখকের lab-এ Z3 5.4.1 এটি সব ৬৪-বিট x-এ প্রমাণ করেছে (proved), আর শর্ত x ≥ 0 দিলে সরলx >> 1-ও প্রমাণিত। C compiler-রা signed ভাগকে shift-এ বদলানোর সময় ঠিক এমন সংশোধনের instruction যোগ করে। -
হিসাব — simulation trace: Haat program
let x = 6; let y = 4; print(x * (y + 1));-এর main-এর bytecode (reference-এরdis, instruction 4–9):LOAD_GLOBAL x, LOAD_GLOBAL y, CONST 1, ADD, MUL, PRINT. প্রতিটি instruction-এর পরে VM-এর stack, আর source-এর মিলে যাওয়া small-step configuration ও নিয়ম (E-Var, E-Op, E-Print, বা stutter) লিখুন। আউটপুট কী?instruction VM stack source নিয়ম (শুরু) [ ] print(x * (y + 1)) — LOAD_GLOBAL x [6] print(6 * (y + 1)) E-Var LOAD_GLOBAL y [6, 4] print(6 * (4 + 1)) E-Var CONST 1 [6, 4, 1] print(6 * (4 + 1)) stutter ADD [6, 5] print(6 * 5) E-Op MUL [30] print(30) E-Op PRINT [ ] out = 30 E-Printএখানে stutter একবার, CONST 1-এ: 1 আগে থেকেই মান, source-এ কোনো ধাপ নেই। বাঁ-থেকে-ডানে নিয়ম (সিদ্ধান্ত ১২) মেনে x আগে, তারপর y. আউটপুট
30; reference-এরhaat.py disঠিক এই instruction দেখায়, আরrunছাপে30(লেখকের lab, সত্যিকারের run). -
প্রমাণ — ভাগের case: অংশ ২-এর Theorem ৪৪.১-এর প্রমাণে
/-এর case আলাদা করে লিখুন। Folder-এর নিয়ম: f1 = c1, f2 = c2 সংখ্যা আর c2 ≠ 0 হলে fold(e1 / e2) = wrap(c1 ÷0 c2) (÷0 = শূন্যের দিকে কাটা); নইলে f1 / f2. তিনটি উপ-case-ই দেখান, err-সহ। কেন c2 = 0-তে fold করলে প্রমাণ ভাঙে?IH: ⟦f1⟧σ = ⟦e1⟧σ আর ⟦f2⟧σ = ⟦e2⟧σ (দুটি পাশ err হলে দুটিই err), সব σ-তে।
- দুটিই সংখ্যা, c2 ≠ 0. IH থেকে ⟦e1⟧σ = c1, ⟦e2⟧σ = c2 ≠ 0. ⟦e1 / e2⟧σ-এর সমীকরণ (পর্ব ৪১) তখন wrap(c1 ÷0 c2), যা fold(e)-এর মান, আর একটি সংখ্যার অর্থ সে নিজেই। সমান।
- দুটিই সংখ্যা, c2 = 0. Folder কিছু করে না: fold(e) = c1 / 0. ⟦c1 / 0⟧σ = err, আর IH থেকে ⟦e2⟧σ = 0, তাই ⟦e⟧σ = err (অথবা ⟦e1⟧σ নিজেই err হলে তাও err). দুই পাশ err.
- অন্তত একটি সংখ্যা নয়. fold(e) = f1 / f2. ⟦f1 / f2⟧σ শুধু ⟦f1⟧σ আর ⟦f2⟧σ-এর ওপর নির্ভর করে (compositionality), যা IH-এ ⟦e1⟧σ আর ⟦e2⟧σ-এর সমান; তাই ফল সমান, err-সহ। ∎
c2 = 0-তে fold করলে folder-কে একটি সংখ্যা বসাতে হতো (অথবা compile time-এই crash করত), কিন্তু ⟦e⟧σ = err, আর কোনো সংখ্যা err-এর সমান নয়: উপ-case ২ মিথ্যা হয়ে যেত। Python-এ
fold(("/", 10, 0))ঠিক এজন্যই নিয়মটি এড়ায়, আর অংশ ২-এর block-এ(10 / 0)fold-এর পরেও অপরিবর্তিত ছিল। আরেকটি সূক্ষ্মতা: c1 = INT_MIN, c2 = −1 হলে Haat-এ ফল INT_MIN (সিদ্ধান্ত ১৩), তাই folder-কেও একই wrap ব্যবহার করতে হবে; Z3-এর রানেওINT_MIN / -1 = -9223372036854775808.
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমProof assistant-এ একটি compiler pass verify করার ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- Source আর target ভাষার semantics formal সংজ্ঞা হিসেবে লেখা
- Pass-টি proof assistant-এর ভাষায় একটি function হিসেবে লেখা
- Semantic preservation-এর theorem বলা: compile-এর পরে আচরণ একই
- দুই পাশের অবস্থার মধ্যে simulation সম্পর্ক বানিয়ে tactic দিয়ে প্রমাণ
- Kernel প্রমাণটি যাচাই করে; তারপর সব pass-এর প্রমাণ জুড়ে পুরো compiler-এর theorem
CompCert-ধাঁচের verified compiler-এর মূল theorem (semantic preservation) কী নিশ্চিত করে?
- Compile করা program যেকোনো CPU-তে, hardware-এর ভুল থাকলেও, ঠিক চলবে
- Source program-এ undefined behavior থাকলেও target একটি নির্দিষ্ট, নিরাপদ আচরণ করবে
- সংজ্ঞায়িত আচরণের source থেকে বানানো target-এর পর্যবেক্ষণযোগ্য আচরণ source-এর মতো
- তৈরি code সম্ভাব্য সবচেয়ে দ্রুত
৬৪-বিট wrap-এর Int-এ (যেমন Haat, Java-র long) optimizer-এর নিয়ম x * 2 / 2 → x সম্পর্কে কোনটি সঠিক? (/ শূন্যের দিকে কাটে)
- সঠিক, কারণ 2x ÷ 2 = x সবসময় সত্য
- ভুল; x = 4611686018427387904-এ ফল -4611686018427387904
- শুধু ঋণাত্মক x-এ ভুল, সব ধনাত্মক x-এ সঠিক
- ভুল, কারণ x = 0-তে শূন্য দিয়ে ভাগ হয়
Clang-এ long f(long x) { return x * 2 / 2; } -O2-তে শুধু x ফেরত দেয়, কিন্তু unsigned long-এর একই function-এ একটি and instruction রাখে। কেন?
- Unsigned type-এর জন্য Clang-এর optimizer দুর্বল
- Signed-এ C wrap সংজ্ঞায়িত করে, unsigned-এ করে না
- Unsigned function-এ debug তথ্য থেকে যায়
- C-তে signed overflow undefined behavior, unsigned-এ wrap সংজ্ঞায়িত
Translation validation সম্পর্কে কোনটি সঠিক?
- প্রতিবার compile-এর ফল আলাদা যাচাই হয়; validator sound হলেই চলে, complete না হলেও
- এটি compiler-এর source code প্রমাণ করে, একবারে সব input-এর জন্য
- Validator মাঝে মাঝে ভুল ফল গ্রহণ করলেও সমস্যা নেই, কারণ test পরে ধরবে
- শুধু ছোট, আগে থেকে verified compiler-এ এটি ব্যবহার করা যায়
Haat-এ (শূন্য দিয়ে ভাগ runtime error) একটি folder e * 0-কে সবসময় 0 বানায়। (100 / y) * (5 - 5)-এ y = 0 হলে কী হয়?
- কিছুই না; দুই রূপেই ফল 0
- Compile time-এ শূন্য দিয়ে ভাগের error
- আসল program runtime error দেয়, fold করাটি 0 দেয়: নিয়মটি অর্থ বদলায়
- দুই রূপই runtime error দেয়
Lean 4-এ একটি constant folder-এর সঠিকতার theorem error ছাড়া পাস করেছে, আর #print axioms দেখায় শুধু [propext]. এর পরেও কী বিশ্বাস করতে হয়?
- প্রতিটি tactic (simp, split) নিজে ভুলহীন
- Lean-এর kernel, আর eval-এর সংজ্ঞাটি ভাষার আসল semantics-এর মতো কি না
- প্রমাণে কোথাও sorry নেই, এটি আলাদা করে খুঁজতে হবে
- কয়েকটি input-এ test না করলে theorem অর্থহীন
একটি compiler-কে ৩০০০টি এলোমেলো program দিয়ে একটি reference interpreter-এর সঙ্গে মেলানো হলো, একটিও অমিল নেই। এ থেকে কোনটি বলা যায়?
- Compiler প্রমাণিতভাবে সঠিক
- Reference interpreter-এ নিশ্চয়ই bug আছে
- এমন testing অর্থহীন, কারণ এটি প্রমাণ নয়
- এই নমুনায় কোনো ভুল ধরা পড়েনি; সব program-এর নিশ্চয়তা নেই
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Verification = মডেল + spec + যাচাই করা প্রমাণ: ফল সব input-এর জন্য, তবে spec আর TCB (kernel, semantics, hardware)-এর সাপেক্ষে।
- Optimization-এর সঠিকতা: ⟦fold(e)⟧σ = ⟦e⟧σ, structural induction-এ প্রমাণ; folder আর semantics-এ একই wrap, ভাজক 0 হলে fold নয়,
e * 0 → 0শুধু ভাগহীন e-তে। - SMT: দাবির উল্টোটা দিন; unsat মানে প্রমাণিত, sat মানে পাল্টা উদাহরণ। ৬৪-বিটে
x * 2 / 2 → xভুল (262), C-র signed-এ UB-এর জোরে বৈধ; SMT-LIB-এরx / 0Haat-এর মতো নয়। - Verified compiler: semantic preservation, প্রমাণ হয় প্রতিটি pass-এর simulation দিয়ে (target বেশি ধাপ নিতে পারে, আউটপুট একই); CompCert (Coq), CakeML (HOL4).
- Translation validation আর testing: validator প্রতিটি ফল যাচাই করে (sound, complete না-ও হতে পারে); property-based আর random testing সস্তায় ভুল ধরে, কিন্তু প্রমাণ নয়।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৪৫ · Compiler-এর front end — Haat ভাষার পরিচয় আর নকশাপরবর্তী পর্বমডিউল ৮: Haat-এর front end বানানো শুরু।
- প্রোগ্রামিং ভাষা ও কম্পাইলার · কোর্স হোম৮৬টি পর্বপুরো কোর্সের মানচিত্র আর Haat প্রজেক্টের পথ।
- পর্ব ৪১ · Denotational semantics — program-এর গাণিতিক অর্থএই কোর্সে⟦·⟧, compositionality আর program equivalence, যার ওপর এই পর্বের theorem দাঁড়িয়ে।
- পর্ব ০৫ · Compiler-এর ধাপগুলোএই কোর্সেCompiler-এর সঠিকতার প্রথম দাবি আর সত্যিকারের Clang-এর ধাপ।
- Property-based testingপাশের ট্র্যাকProperty লিখে এলোমেলো input আর shrinking দিয়ে যাচাই।
- SAT, SMT আর verificationপাশের ট্র্যাকSAT আর SMT solver-এর ভেতরের যুক্তি আর bit-vector.
- Fuzz testingপাশের ট্র্যাকএলোমেলো input দিয়ে crash আর ভুল খোঁজার পদ্ধতি।