সরাসরি পর্বে যান
পর্ব ৩৮ · ৮৬-এর মধ্যে · মডিউল ৬

Type soundness — progress আর preservation

Type Soundness — Progress and Preservation

Taught in Bangla, this lesson states type soundness precisely using small-step evaluation, values and stuck terms, then proves progress and preservation case by case for a small arithmetic language, with the canonical forms and substitution lemmas. In-page Python (Pyodide) runs property-based tests over thousands of random well-typed terms and catches deliberately broken rules. It lists what soundness does not promise, such as division by zero, and shows real tsc --strict code that passes yet fails at runtime.

এই পর্বে যা শিখবেন

  • Small-step evaluation, value আর stuck term দিয়ে “program ভুল পথে যায়” কথাটিকে গাণিতিকভাবে লেখা
  • একটি ছোট ভাষার জন্য progress আর preservation-এর পূর্ণ প্রমাণ, সব case দেখিয়ে, পরীক্ষার খাতার ধাঁচে
  • Canonical forms আর substitution lemma কোথায় আর কেন লাগে, তা বোঝা
  • Property-based test দিয়ে theorem-এর দাবি হাজারো term-এ চালিয়ে দেখা, আর ভুল নকশা ধরা
  • Soundness কী প্রতিশ্রুতি দেয় না, আর TypeScript, Java-র মতো বাস্তব ভাষার ফাঁক কোথায়, তা চেনা

১ · “Well-typed programs cannot go wrong” — soundness আসলে কী দাবি করে

বাজারঘরের গুদামে ঢোকার মুখে একটি চেকপোস্ট আছে। চেকপোস্টের কর্মী প্রতিটি বস্তার গায়ের লেবেল দেখেন: “চাল, ৫০ কেজি”। লেবেল ঠিক না থাকলে বস্তা ঢুকতে দেন না। ভেতরের কর্মীরা তাই আর প্রতিটি বস্তা খুলে দেখেন না; লেবেলে ভরসা করেন। এই ব্যবস্থা তখনই নিরাপদ, যখন দুটি কথা সত্য। এক, ভেতরে কোনো বস্তা এমন অবস্থায় পড়ে থাকে না যে কেউ জানে না তা দিয়ে কী করতে হবে। দুই, বস্তা এক তাক থেকে আরেক তাকে গেলেও লেবেলের সঙ্গে ভেতরের মাল মেলে। প্রথমটির নাম progress, দ্বিতীয়টির preservation.

পর্ব ৩৩-এ (Type system) দেখেছেন, type checker একটি রক্ষণশীল চেকপোস্ট: কিছু ঠিক program-ও বাতিল করে (incompleteness), কিন্তু যা মেনে নেয় তা নিরাপদ হওয়ার কথা। সেখানে এই “নিরাপদ” দাবিটি একটি ছোট গণনা দিয়ে দেখানো হয়েছিল: গভীরতা ২ পর্যন্ত মেনে নেওয়া একটি expression-ও চলার সময় আটকায়নি। আর পর্ব ৩৪-এ (Typing rule) typing rule আর derivation লেখা শিখেছেন। এই পর্বে দুটিকে জুড়ে সব আকারের program-এর জন্য দাবিটি প্রমাণ করা হবে। এটিই type soundness.

ইতিহাস। Robin Milner ১৯৭৮ সালে ML-এর type system নিয়ে তাঁর বিখ্যাত paper-এ (“A Theory of Type Polymorphism in Programming”) একটি theorem প্রমাণ করেন, যার সারকথা আজ স্লোগান হয়ে আছে: well-typed programs cannot “go wrong”. সেখানে “wrong” ছিল denotational semantics-এর একটি বিশেষ মান। ১৯৯৪ সালে Andrew Wright আর Matthias Felleisen “A Syntactic Approach to Type Soundness” paper-এ দেখান, একই কথা অনেক সহজে প্রমাণ করা যায় program-কে ধাপে ধাপে চালানোর নিয়ম দিয়ে। আজ যে progress-preservation রূপটি পাঠ্যবইয়ে পড়ানো হয় (যেমন Benjamin Pierce-এর Types and Programming Languages, ২০০২), সেটি এই ধারার একটি পরিচ্ছন্ন রূপ।

দাবিটি গাণিতিক করতে তিনটি শব্দ ঠিক করতে হয়। Value হলো হিসাবের শেষ ফল, যার আর কিছু করার নেই: 996, true. এক ধাপ চলা লেখা হয় t ⟶ t′ (“t এক ধাপে t′ হয়”), আর কোন অবস্থায় কোন ধাপ, তা বলে evaluation-এর নিয়ম। এই ধরনের সংজ্ঞাকে বলে small-step semantics, যা operational semantics-এর একটি রূপ; পর্ব ৪০-এ (Operational semantics — small-step আর big-step) এটি বিস্তারিত আসবে, এখানে শুধু যতটুকু লাগে। আর stuck term হলো এমন term, যা value নয়, অথচ কোনো নিয়মে এক ধাপও চলতে পারে না। true + 1 এর উদাহরণ: যোগের নিয়ম দুটি সংখ্যা চায়, true সংখ্যা নয়। বাস্তব যন্ত্রে stuck অবস্থা মানে কোনো অর্থহীন কাজ: Bool-এর বিটকে সংখ্যা ভেবে যোগ, বা function না এমন কিছুকে call. C-তে এর ফল undefined behavior, Python-এ চলার সময় TypeError.

সংজ্ঞা ৩৮.১ — type soundness (type safety)

একটি ভাষা sound, যদি প্রতিটি well-typed বন্ধ term t-এর জন্য (⊢ t : τ), t থেকে যত ধাপই চলা হোক (t ⟶* t′), t′ কখনো stuck নয়। Pierce-এর বইসহ অনেক পাঠ্যে এটিকে type safety নামেও ডাকা হয়, আর প্রমাণের ছকটি একটি স্লোগানে বলা হয়: safety = progress + preservation.

এখানে “বন্ধ” (closed) মানে term-এ কোনো মুক্ত variable নেই, তাই context ফাঁকা, আর judgment লেখা হয় শুধু ⊢ t : τ. ⟶* মানে “শূন্য বা তার বেশি ধাপ”। নিচের ছবিটি পুরো theorem-এর মানচিত্র।

ছবি ৩৮.১ — soundness-এর ছবি: progress আর preservation

নীল জগতে সব term-এর type Int. প্রতিটি তির এক ধাপ (⟶); preservation বলে তির নীল জগতের বাইরে যায় না, progress বলে value না হলে একটি তির আছেই

Progress and preservation: evaluation stays inside the well-typed region and never reaches a stuck term well-typed (⊢ t : Int) t₀ : Int t₁ : Int t₂ : Int 996 : Int value, কাজ শেষ progress progress progress stuck true + 1 ✗ এখানে কোনো well-typed term পৌঁছায় না

ছবির প্রতিটি নীল বাক্সের type একই, Int: এটি preservation. প্রতিটি নীল বাক্স থেকে পরের বাক্সে একটি তির আছে, যতক্ষণ না সবুজ value-তে পৌঁছায়: এটি progress. লাল বাক্সে যাওয়ার কাটা তিরটি কখনো ঘটে না; সেটিই soundness.

২ · হিসাব-ভাষা — typing rule আর এক-ধাপের evaluation

পুরো Haat-এর জন্য প্রমাণ অনেক লম্বা (variable, closure, var, while, return সব লাগবে; অংশ ৬-এ দেখবেন কী কী)। তাই প্রমাণের কৌশল শিখতে বেছে নেওয়া হলো একটি ছোট ভাষা, যার নাম দিচ্ছি হিসাব-ভাষা। পর্ব ৩৩-এর ছোট checker-এর ভাষার মতোই, শুধু একটি তুলনা যোগ:

t ::= n | true | false | t + t | t < t | if t then t else t      (term)
v ::= n | true | false                                           (value)
τ ::= Int | Bool                                                 (type)

n মানে যেকোনো 64-bit integer (ঋণাত্মকও; Haat-এর মতো যোগ wrap করে, সিদ্ধান্ত ১৩)। একটি পার্থক্য খেয়াল রাখুন: এখানে if একটি expression, যার মান আছে, অথচ Haat spec-এ if একটি statement. তাই নিয়মটি পর্ব ৩৪-এর T-IfExpr, Haat-এর T-If নয়। Typing rule-গুলো পর্ব ৩৪-এর নামেই:

n একটি integer
⊢ n : Int
(T-Int)
b ∈ {true, false}
⊢ b : Bool
(T-Bool)
⊢ t1 : Int    ⊢ t2 : Int
⊢ t1 + t2 : Int
(T-Add)
⊢ t1 : Int    ⊢ t2 : Int
⊢ t1 < t2 : Bool
(T-Cmp)
⊢ t1 : Bool    ⊢ t2 : τ    ⊢ t3 : τ
⊢ if t1 then t2 else t3 : τ
(T-IfExpr)

এবার evaluation-এর নিয়ম, একই দাগ-টানা ভঙ্গিতে, শুধু judgment-টি এখন t ⟶ t′. নিয়মগুলো দুই রকম। Computation rule আসল কাজ করে (যোগ, তুলনা, শাখা বাছাই)। Congruence rule বলে কাজটি term-এর ভেতরে কোথায় হবে: আগে বাঁ দিক, তারপর ডান দিক (Haat-এর বাঁ থেকে ডানে evaluation, সিদ্ধান্ত ১২), আর if-এ আগে শর্ত।

n = n1 + n2 (64-bit wrap)
n1 + n2 ⟶ n
(E-Add)
t1 ⟶ t1′
t1 + t2 ⟶ t1′ + t2
(E-Add1)
t2 ⟶ t2′
v1 + t2 ⟶ v1 + t2′
(E-Add2)
b = true যদি n1 < n2, নইলে false
n1 < n2 ⟶ b
(E-Lt; E-Lt1, E-Lt2 যোগের মতোই)
 
if true then t2 else t3 ⟶ t2
(E-IfTrue)
 
if false then t2 else t3 ⟶ t3
(E-IfFalse)
t1 ⟶ t1′
if t1 then t2 else t3 ⟶ if t1′ then t2 else t3
(E-If)

লক্ষ করুন E-Add-এ দুই পাশে n লেখা: নিয়মটি খাটে শুধু তখন, যখন দুই পাশই সংখ্যার value. true + 1-এর বাঁ পাশ value, কিন্তু সংখ্যা নয়; E-Add1 খাটে না (true আর চলে না), E-Add2 খাটে না (1 আর চলে না), E-Add খাটে না। কোনো নিয়ম নেই, তাই term-টি stuck. নিচের Python block হুবহু এই নিয়মগুলো: check()-এর প্রতিটি লাইন একটি typing rule, step()-এর প্রতিটি শাখা একটি evaluation rule, আর None মানে “কোনো নিয়ম খাটেনি”।

# ছোট ভাষা: ("num", n) ("bool", b) ("+", a, b) ("<", a, b) ("if", c, a, b)
def wrap(n): return (n + 2**63) % 2**64 - 2**63       # Haat-এর মতো 64-bit wrap
def is_val(t): return t[0] in ("num", "bool")
def check(t):                       # T-Int T-Bool T-Add T-Cmp T-IfExpr; None = বাতিল
    if is_val(t): return "Int" if t[0] == "num" else "Bool"
    ts = [check(x) for x in t[1:]]
    if t[0] == "if": return ts[1] if ts[0] == "Bool" and ts[1] == ts[2] else None
    return ("Int" if t[0] == "+" else "Bool") if ts == ["Int", "Int"] else None
CONG = {"+": "E-Add", "<": "E-Lt"}
def step(t):                        # এক ধাপ ⟶ : (নতুন term, নিয়ম); না পারলে None
    if is_val(t): return None                        # value: কাজ শেষ
    k, a, b = t[0], t[1], t[2]
    if k == "if":
        if not is_val(a):                            # E-If: আগে শর্ত
            r = step(a); return r and (("if", r[0], *t[2:]), f"E-If({r[1]})")
        if a[0] != "bool": return None               # আটকে গেছে (stuck)
        return (t[2], "E-IfTrue") if a[1] else (t[3], "E-IfFalse")
    if not is_val(a):                                # বাঁ দিক আগে (সিদ্ধান্ত ১২)
        r = step(a); return r and ((k, r[0], b), f"{CONG[k]}1({r[1]})")
    if not is_val(b):
        r = step(b); return r and ((k, a, r[0]), f"{CONG[k]}2({r[1]})")
    if a[0] != "num" or b[0] != "num": return None   # আটকে গেছে (stuck)
    if k == "+": return ("num", wrap(a[1] + b[1])), "E-Add"
    return ("bool", a[1] < b[1]), "E-Lt"
def show(t):
    if is_val(t): return str(t[1]).lower()
    p = lambda x: show(x) if is_val(x) else f"({show(x)})"
    if t[0] == "if": return f"if {p(t[1])} then {p(t[2])} else {p(t[3])}"
    return f"{p(t[1])} {t[0]} {p(t[2])}"
N = lambda n: ("num", n)
t = ("+", ("if", ("<", N(936), N(1000)), N(936), N(900)), N(60))
while t:
    print(f"{show(t):38} : {check(t)}"); r = step(t); t = r and r[0]
    if r: print("   ⟶", r[1])
bad = ("+", N(1), ("bool", True)); print(show(bad), ": type", check(bad), "| step", step(bad))

আসল আউটপুট (ব্রাউজারের Python):

(if (936 < 1000) then 936 else 900) + 60 : Int
   ⟶ E-Add1(E-If(E-Lt))
(if true then 936 else 900) + 60       : Int
   ⟶ E-Add1(E-IfTrue)
936 + 60                               : Int
   ⟶ E-Add
996                                    : Int
1 + true : type None | step None

তিন ধাপে 996, bazar.haat-এর প্রথম লাইনের সেই সংখ্যা (৯৩৬ টাকার পণ্য, ১০০০-এর কম, তাই ৬০ টাকা ডেলিভারি)। প্রতিটি লাইনের ডানে type: শুরুতে Int, প্রতিটি ধাপের পরেও Int, শেষেও Int. নিয়মের নামগুলো বাসার ঠিকানার মতো পড়ুন: E-Add1(E-If(E-Lt)) মানে “যোগের বাঁ পাশে গিয়ে, সেখানে if-এর শর্তে গিয়ে, তুলনাটি করা হলো”। শেষ লাইনে 1 + true: type None (checker বাতিল করে), আর step-ও None: stuck. Soundness বলে, এই দুই None একসঙ্গে থাকে; checker যা মানে, তার step কখনো None নয়, যতক্ষণ না value.

একই trace এবার ধাপে ধাপে, প্রতিটি ধাপে type-টি আবার যাচাই করে:

0(if 936 < 1000   then 936   else 900) + 601(if true then 936   else 900) + 602936 + 603996
যাচাই
ধাপ
নিয়ম
type
  1. শুরু। t₀ = (if 936 < 1000 then 936 else 900) + 60. Checker-এর derivation: T-Add, তার বাঁ premise T-IfExpr, তার শর্তে T-Cmp. তাই ⊢ t₀ : Int. t₀ value নয়, তাই progress বলে একটি ধাপ থাকতেই হবে।
  2. কাজটি কোথায়? বাইরে +, বাঁ পাশ value নয়, তাই E-Add1 দিয়ে ভেতরে যেতে হয়। সেখানে if, শর্ত value নয়: E-If, আরও ভেতরে। সেখানে 936 < 1000, দুই পাশই সংখ্যা: E-Lt খাটে, ফল true. তিনটি নিয়ম মিলে একটি ধাপ।
  3. Preservation-এর প্রথম পরীক্ষা। t₁ = (if true then 936 else 900) + 60. Checker আবার চালালে type Int, আগের মতোই। শর্তের type Bool ছিল, value-টিও Bool (true): ভেতরেও type বদলায়নি।
  4. শাখা বাছাই। এবারও বাঁ পাশে যেতে হয় (E-Add1), কিন্তু শর্ত এখন value true, তাই E-IfTrue: পুরো if-এর জায়গায় then-শাখা 936. t₂ = 936 + 60, type Int. else-শাখার 900 ফেলে দেওয়া হলো; T-IfExpr দুই শাখার type এক চেয়েছিল বলেই এখানে type বদলায় না।
  5. শেষ ধাপ। দুই পাশই সংখ্যা: E-Add দেয় 996, একটি value, type Int. মোট ৩ ধাপ, প্রতিটিতে type Int, কোথাও আটকায়নি। ওপরের Python block-এর আউটপুটও হুবহু এই।

একটি term-এ কাজ করল বলে theorem প্রমাণ হয় না। প্রতিটি সম্ভাব্য term-এর জন্য দেখাতে হবে, আর term অসীম। সেখানেই লাগে induction.

৩ · Progress — well-typed term কখনো আটকে থাকে না

প্রমাণ চলবে induction on derivations দিয়ে: ⊢ t : τ-এর derivation tree-র শেষ (সবচেয়ে নিচের) নিয়ম ধরে case ভাগ, আর ভেতরের premise-গুলোর জন্য theorem আগেই সত্য ধরে নেওয়া (induction hypothesis, IH). এটি পর্ব ৩৪-এ দেখা structural induction-এরই আত্মীয়; সেখানে গাছ ছিল term-এর, এখানে গাছ derivation-এর। Induction-এর ভিত্তি চাইলে Discrete Mathematics-এর পর্ব ১০ দেখুন। প্রথমে দুটি ছোট সহায়ক কথা।

Lemma ৩৮.১ — inversion (নিয়ম উল্টো পড়া)

(১) ⊢ t1 + t2 : τ হলে τ = Int, ⊢ t1 : Int আর ⊢ t2 : Int. (২) ⊢ t1 < t2 : τ হলে τ = Bool আর দুটিই Int. (৩) ⊢ if t1 then t2 else t3 : τ হলে ⊢ t1 : Bool, ⊢ t2 : τ আর ⊢ t3 : τ. (৪) ⊢ true : τ বা ⊢ false : τ হলে τ = Bool; ⊢ n : τ হলে τ = Int.

এর প্রমাণ এক লাইনের: প্রতিটি গঠনের conclusion আছে ঠিক একটি নিয়মে (পর্ব ৩৪-এর syntax-directed গুণ), তাই derivation-এর শেষ নিয়মটি সেটিই, আর তার premise-গুলোই উত্তর। এই উল্টো-পড়াকে বলে inversion lemma.

Lemma ৩৮.২ — canonical forms

(১) v একটি value আর ⊢ v : Bool হলে v = true অথবা v = false. (২) v একটি value আর ⊢ v : Int হলে v একটি integer n.

প্রমাণ। Value মাত্র তিন রকম: n, true, false. (১)-এর জন্য: v = n হলে inversion (৪) অনুযায়ী তার type Int, Bool নয়; তাই v = true বা false. (২)-এর জন্য: v = true বা false হলে type Bool, Int নয়; তাই v = n. ∎

নামটির মানে: প্রতিটি type-এর value-এর একটি “স্বাভাবিক আকার” আছে। কথাটি তুচ্ছ শোনায়, কিন্তু progress-এর প্রমাণে এটিই সেই জায়গা, যেখানে type থেকে মানের আকার সম্পর্কে কিছু জানা যায়। এই canonical forms lemma ছাড়া প্রমাণ এগোয় না।

Theorem ৩৮.১ — progress

⊢ t : τ হলে t একটি value, অথবা এমন t′ আছে যে t ⟶ t′.

প্রমাণ ⊢ t : τ-এর derivation-এর ওপর induction, শেষ নিয়ম ধরে সব case:

  1. T-Int বা T-Bool. t = n, true বা false: সংজ্ঞা অনুযায়ী value. শেষ।
  2. T-Add, t = t1 + t2. Premise: ⊢ t1 : Int আর ⊢ t2 : Int. t1-এর derivation ছোট, তাই IH: t1 value, নয়তো এক ধাপ চলে।
    1. t1 ⟶ t1′ হলে E-Add1 দিয়ে t ⟶ t1′ + t2.
    2. t1 value হলে t2-তে IH. t2 ⟶ t2′ হলে E-Add2 দিয়ে t ⟶ t1 + t2′ (E-Add2 বাঁ পাশে value-ই চায়, আর t1 value).
    3. দুটিই value হলে canonical forms (২): দুটিই integer, t = n1 + n2. E-Add খাটে, t ⟶ n.
  3. T-Cmp, t = t1 < t2. ধাপ ২-এর হুবহু একই যুক্তি, E-Lt1, E-Lt2 আর শেষে canonical forms (২) দিয়ে E-Lt.
  4. T-IfExpr, t = if t1 then t2 else t3. Premise ⊢ t1 : Bool; IH দিয়ে t1 value, নয়তো চলে।
    1. t1 ⟶ t1′ হলে E-If দিয়ে t ⟶ if t1′ then t2 else t3.
    2. t1 value হলে canonical forms (১): t1 = true বা false. প্রথমটিতে E-IfTrue, দ্বিতীয়টিতে E-IfFalse. ∎

প্রমাণে কোথায় type কাজে লাগল, খেয়াল করুন: শুধু canonical forms-এর দুটি জায়গায়। true + 1-এ ধাপ ২.৩ পর্যন্ত সব ঠিক চলে (দুই পাশই value), কিন্তু canonical forms খাটানো যায় না, কারণ ⊢ true : Int নেই। ওই term-টি well-typed নয় বলেই theorem-এর আওতায় পড়ে না। if-এর case-টি ধাপে ধাপে:

1লক্ষ্য: t value, নয়তো চলে2IH on t₁: value, নাকি চলে?3ক: t₁ ⟶ t₁′ ⇒ E-If4খ: t₁ value, ⊢ t₁ : Bool5Lemma ৩৮.২: true/false6E-IfTrue বা E-IfFalse ∎
উদাহরণে
t
t₁
case
  1. লক্ষ্য। t-এর derivation-এর শেষ নিয়ম T-IfExpr, তার premise ⊢ t1 : Bool, ⊢ 936 : Int আর ⊢ 900 : Int. দেখাতে হবে t value, অথবা চলতে পারে। t স্পষ্টতই value নয়।
  2. IH. t1 = 936 < 1000-এর derivation t-এর derivation-এর ভেতরের একটি ছোট গাছ, তাই IH খাটে: t1 value, নয়তো এক ধাপ চলে। দুটি case, দুটিই সামলাতে হবে।
  3. Case ক। এখানে t1 value নয়, আর IH (আসলে T-Cmp case) বলে সে চলে: E-Lt দিয়ে true. তাহলে E-If দিয়ে পুরো t এক ধাপ চলে। এই case-এ type-এর আর কোনো তথ্য লাগল না।
  4. Case খ। ধরুন এক ধাপ পরের term: t1 = true, যা value. এবার congruence-এর পথ বন্ধ; computation rule (E-IfTrue বা E-IfFalse) লাগবে। কিন্তু সেই নিয়ম শর্তে ঠিক true বা false চায়।
  5. Canonical forms. t1 value আর ⊢ t1 : Bool, তাই Lemma ৩৮.২ (১) বলে t1 = true বা false. এটি type-এর তথ্যের একমাত্র ব্যবহার: শর্তে 5 বা অন্য কোনো value থাকতে পারে না, কারণ তাদের type Bool নয়।
  6. শেষ। t1 = true, তাই E-IfTrue: t ⟶ 936. false হলে E-IfFalse. সব case-এ একটি ধাপ পাওয়া গেল, T-IfExpr case শেষ। ill-typed if 5 then 1 else 2-এ ধাপ ৫-টি ব্যর্থ হতো, আর term-টি stuck.

৪ · Preservation — এক ধাপ চললে type বদলায় না

Progress একা যথেষ্ট নয়। সে শুধু বলে well-typed term এক ধাপ চলতে পারে; কিন্তু চলার পরের term যদি ill-typed হয়ে যায়, তাহলে পরের ধাপে progress আর খাটে না, আর সেখানে আটকে যেতে পারে। ঠিক এই ফাঁক বন্ধ করে preservation; পুরোনো বইয়ে একে subject reduction নামেও পাবেন।

Theorem ৩৮.২ — preservation

⊢ t : τ আর t ⟶ t′ হলে ⊢ t′ : τ.

প্রমাণ ⊢ t : τ-এর derivation-এর ওপর induction. প্রতিটি case-এ আবার ভাগ: t ⟶ t′ কোন evaluation rule দিয়ে এল।

  1. T-Int বা T-Bool. t একটি value. কোনো evaluation rule-এর বাঁ পাশে value নেই, তাই t ⟶ t′ অসম্ভব; দেখানোর কিছু নেই।
  2. T-Add, t = t1 + t2, τ = Int. তিনটি নিয়ম দিয়ে t চলতে পারে:
    1. E-Add: t′ = n, একটি integer (64-bit wrap-এর পরেও integer). T-Int দিয়ে ⊢ t′ : Int.
    2. E-Add1: t1 ⟶ t1′ আর t′ = t1′ + t2. ⊢ t1 : Int আর t1 ⟶ t1′, তাই IH দিয়ে ⊢ t1′ : Int. সঙ্গে ⊢ t2 : Int, তাই T-Add দিয়ে ⊢ t′ : Int.
    3. E-Add2: একইভাবে t2-তে IH, তারপর T-Add.
  3. T-Cmp, τ = Bool. E-Lt দিলে t′ = true বা false, T-Bool দিয়ে Bool. E-Lt1, E-Lt2 দিলে ধাপ ২.২-এর মতো IH আর T-Cmp.
  4. T-IfExpr, t = if t1 then t2 else t3. Premise: ⊢ t1 : Bool, ⊢ t2 : τ, ⊢ t3 : τ.
    1. E-IfTrue: t′ = t2, আর ⊢ t2 : τ সরাসরি premise থেকে।
    2. E-IfFalse: t′ = t3, ⊢ t3 : τ premise থেকে।
    3. E-If: t1 ⟶ t1′; IH দিয়ে ⊢ t1′ : Bool; তারপর T-IfExpr দিয়ে ⊢ if t1′ then t2 else t3 : τ. ∎

ধাপ ৪.২-টি ভালো করে দেখুন। E-IfFalse-এ ফল else-শাখা, আর তার type যে τ, তা জানা গেল কারণ T-IfExpr দুই শাখারই type τ দাবি করেছিল। পর্ব ৩৩-এ এই দাবিটিকে মনে হয়েছিল অতিরিক্ত কড়াকড়ি, কারণ 1 + (if true then 1 else true)-এর মতো চলতে-পারা program বাতিল হয়। এখানে দেখা গেল তার কারণ: else-শাখা কখনো চলতে পারে, আর তখনও type রক্ষা করতে হবে। Checker চলার আগে জানে না কোন শাখা নেওয়া হবে, তাই দুটিকেই একই type দিতে হয়।

Corollary ৩৮.৩ — soundness

⊢ t : τ আর t ⟶* t′ হলে t′ stuck নয়: t′ একটি value (যার type τ), অথবা আরেক ধাপ চলে।

প্রমাণ ধাপের সংখ্যা k-এর ওপর সাধারণ induction. k = 0 হলে t′ = t, আর ⊢ t : τ. k + 1 ধাপ হলে প্রথম k ধাপে পৌঁছানো term-এর type IH দিয়ে τ, আর শেষ ধাপে preservation দিয়ে ⊢ t′ : τ. সবশেষে ⊢ t′ : τ-এর ওপর progress খাটালে t′ value, নয়তো চলে। ∎

একটি বাড়তি পর্যবেক্ষণ: হিসাব-ভাষায় প্রতিটি ধাপ term-কে ছোট করে (যেমন E-Add তিনটি node থেকে একটি বানায়), তাই কোনো evaluation অসীম চলতে পারে না, আর প্রতিটি well-typed term শেষে একটি value দেয়। এটি soundness-এর অংশ নয়, আলাদা একটি গুণ (termination). Haat-এ while আর recursion আছে, তাই সেখানে এটি সত্য নয়; অংশ ৭-এ দেখবেন soundness তখনও কী বলে।

৫ · Property-based test — হাজারো term-এ theorem যাচাই

প্রমাণ হাতে লেখা, আর হাতে লেখা প্রমাণে case বাদ পড়ে। বাস্তবে ভাষা-নকশাকারীরা তাই প্রমাণের আগে-পরে একটি সস্তা পরীক্ষা চালান: theorem-এর দাবিটিকেই একটি test বানানো, আর হাজারো এলোমেলো input-এ চালানো। একে বলে property-based testing; Hypothesis আর shrinking-সহ পুরো কৌশল Software Testing & QA-এর পর্ব ৫৮-এ। এখানে property দুটি: (১) well-typed term value না হলে step কখনো None নয় (progress), (২) প্রতিটি ধাপের পরে check একই type দেয় (preservation).

Generator দুটি। gen(ty, d) চাওয়া type অনুযায়ী term বানায়, তাই সবসময় well-typed (এটি T-নিয়মগুলোকে উল্টো দিক থেকে চালানো)। gen_any(d) যেকোনো term বানায়, ill-typed-ও। মাঝে মাঝে 9223372036854775807 বসানো হয়, যাতে যোগে wrap ঘটে। Seed 38, তাই প্রতিবার একই term আর একই সংখ্যা।

# Property-based test: হাজারো এলোমেলো term-এ progress আর preservation
import random
rng = random.Random(38)                          # seed: প্রতিবার একই term
BIG, INT_OPS = 2**63 - 1, ("+",)                # BIG: মাঝে মাঝে wrap ঘটাতে
def leaf(ty): return ("bool", rng.random() < 0.5) if ty == "Bool" else                     N(BIG if rng.random() < 0.05 else rng.randint(-5, 5))
def gen(ty, d):                                  # type-directed: সবসময় well-typed
    if d == 0 or rng.random() < 0.2: return leaf(ty)
    if rng.random() < 0.4: return ("if", gen("Bool", d - 1), gen(ty, d - 1), gen(ty, d - 1))
    op = rng.choice(INT_OPS) if ty == "Int" else "<"
    return (op, gen("Int", d - 1), gen("Int", d - 1))
def gen_any(d, ops=("+", "<", "if")):            # যেকোনো term, ill-typed-ও
    if d == 0 or rng.random() < 0.25: return leaf(rng.choice(["Int", "Bool"]))
    op = rng.choice(ops)
    return (op, *[gen_any(d - 1, ops) for _ in range(3 if op == "if" else 2)])
def trial(t):                                    # value পর্যন্ত চালিয়ে প্রতিটি ধাপ যাচাই
    ty, n = check(t), 0
    while not is_val(t):
        try: r = step(t)
        except ZeroDivisionError: return "error", n
        if r is None: return "progress ভাঙল", t
        if ty and check(r[0]) != ty: return "preservation ভাঙল", (t, r[0])
        t, n = r[0], n + 1
    return "ok", n
def size(t): return 1 if is_val(t) else 1 + sum(size(x) for x in t[1:])
res = [trial(gen(rng.choice(["Int", "Bool"]), 6)) for _ in range(3000)]
ok = [n for k, n in res if k == "ok"]
print("well-typed term:", len(res), "| সফল:", len(ok), "| মোট ধাপ যাচাই:", sum(ok),
      "| সবচেয়ে লম্বা:", max(ok), "ধাপ")
print("ব্যর্থ:", [k for k, _ in res if k != "ok"][:3] or "কোনোটিই নয়")
anyt = [gen_any(5) for _ in range(3000)]
stuck = [t for t in anyt if trial(t)[0] == "progress ভাঙল"]
print("এলোমেলো term:", len(anyt), "| checker মানল:", sum(1 for t in anyt if check(t)), "| আটকে গেল:", len(stuck),
      "| মানা আর আটকানো দুটোই:", sum(1 for t in stuck if check(t)))
s = min(stuck, key=size); print("সবচেয়ে ছোট আটকে-যাওয়া:", show(s), ":", check(s))

আসল আউটপুট (ব্রাউজারের Python):

well-typed term: 3000 | সফল: 3000 | মোট ধাপ যাচাই: 64739 | সবচেয়ে লম্বা: 56 ধাপ
ব্যর্থ: কোনোটিই নয়
এলোমেলো term: 3000 | checker মানল: 773 | আটকে গেল: 2206 | মানা আর আটকানো দুটোই: 0
সবচেয়ে ছোট আটকে-যাওয়া: false < 0 : None

৩,০০০টি well-typed term, প্রতিটি value পর্যন্ত চালানো, মোট ৬৪,৭৩৯টি ধাপ, আর প্রতিটি ধাপে দুটি theorem-ই যাচাই হয়েছে: একটিও ব্যর্থ নয়। সবচেয়ে লম্বাটির ৫৬ ধাপ লেগেছে। লেখকের lab-এ wrap গুনে দেখা হয়েছে: এই block-এর দুই ভাগ মিলে ১,৫৭০ বার যোগ 64-bit সীমা পেরিয়েছে, তাই wrap-এর case-ও পরীক্ষিত। দ্বিতীয় অংশে এলোমেলো ৩,০০০টির মধ্যে checker মেনেছে ৭৭৩টি, আটকে গেছে ২,২০৬টি, আর “মানা আর আটকানো দুটোই” ঠিক ০: soundness-এর সাক্ষ্য। হিসাব মেলালে আরও একটি জিনিস বেরোয়: ৩,০০০ − ৭৭৩ − ২,২০৬ = ২১টি term checker বাতিল করেছে, অথচ সেগুলো আটকায়নি, value পর্যন্ত চলেছে। এটি পর্ব ৩৩-এর incompleteness, আবার দেখা দিল।

কিন্তু test কাজের কি না, তা বোঝা যায় শুধু তখন, যখন সে ভুল ধরে। নিচের block নিয়মের সেটে দুটি ভুল ঢোকায়। (ক) ঢিলে T-IfExpr: else-শাখা যাচাই না করে then-শাখার type নেওয়া। (খ) ভাগ যোগ করা: T-Div (দুটি Int থেকে Int) আছে, আর C-র মতো শূন্যের দিকে কাটা ভাগের নিয়ম E-Div আছে, কিন্তু ভাজক 0 হলে কোনো নিয়ম নেই। তারপর (গ) একটি সংশোধন: E-DivZero, যা program থামিয়ে runtime error দেয়, ঠিক Haat-এর মতো।

# Theorem ভাঙা: একই test কি দুটি ভুল নকশা ধরে?
good_check, good_step = check, step
def report(name, make):
    out = {}
    for _ in range(3000):
        t = make()
        if check(t): k, why = trial(t); out.setdefault(k, []).append(why)
    print(name, {k: len(v) for k, v in out.items()})
    return out
# (ক) ঢিলে T-IfExpr: else-শাখা না দেখে then-শাখার type নেওয়া
def check(t):              # নামটি global, তাই good_check-এর ভেতরের ডাকও এখানে আসে
    if t[0] == "if": return check(t[2]) if check(t[1]) == "Bool" else None
    return good_check(t)
b = report("ঢিলে if:", lambda: gen_any(5))
a, a2 = min(b["preservation ভাঙল"], key=lambda p: size(p[0]))
print("   ", show(a), ":", check(a), " ⟶ ", show(a2), ":", check(a2))
# (খ) ভাগ যোগ: T-Div আছে, কিন্তু n / 0-এর কোনো evaluation নিয়ম নেই
def check(t):
    if t[0] == "/": return "Int" if [check(t[1]), check(t[2])] == ["Int"] * 2 else None
    return good_check(t)
CONG["/"], DIV_ERROR, INT_OPS = "E-Div", False, ("+", "/")
wt = lambda: gen(rng.choice(["Int", "Bool"]), 5)
def step(t):
    if t[0] != "/" or not (is_val(t[1]) and is_val(t[2])): return good_step(t)
    x, y = t[1][1], t[2][1]
    if y == 0:
        if DIV_ERROR: raise ZeroDivisionError        # (গ) E-DivZero: থেমে যাওয়া
        return None
    q = abs(x) // abs(y)                             # C-র মতো শূন্যের দিকে কাটা
    return N(wrap(q if (x < 0) == (y < 0) else -q)), "E-Div"
b = report("n / 0-এর নিয়ম নেই:", wt)
print("    সবচেয়ে ছোট আটকে-যাওয়া:", show(min(b["progress ভাঙল"], key=size)))
DIV_ERROR = True
report("E-DivZero সহ:", wt)
check, step = good_check, good_step

আসল আউটপুট (ব্রাউজারের Python):

ঢিলে if: {'ok': 820, 'preservation ভাঙল': 16}
    if false then 1 else false : Int  ⟶  false : Bool
n / 0-এর নিয়ম নেই: {'ok': 2104, 'progress ভাঙল': 896}
    সবচেয়ে ছোট আটকে-যাওয়া: 10 / 0
E-DivZero সহ: {'error': 852, 'ok': 2148}

(ক) ঢিলে নিয়মে ১৬টি term preservation ভেঙেছে। সবচেয়ে ছোটটি একটি shrinking-এর সরল রূপে বেছে নেওয়া (সবচেয়ে কম node-এর): if false then 1 else false. ঢিলে checker বলে Int, কারণ then-শাখা 1; কিন্তু শর্ত false, তাই E-IfFalse দিয়ে ফল false, যার type Bool. প্রমাণের ধাপ ৪.২ (“⊢ t3 : τ premise থেকে”) ঠিক এখানেই ভাঙে, কারণ এই premise আর নেই। (খ) ৮৯৬টি term progress ভেঙেছে: ভাগের নিয়ম well-typed, কিন্তু চলতে চলতে 10 / 0-এর মতো অবস্থায় পৌঁছায় (যেমন (5 + 5) / 0 থেকে), যেখানে কোনো নিয়ম নেই। (গ) E-DivZero যোগ করতেই ৮৫২টি term runtime error-এ থামে, বাকিগুলো value দেয়, আর কোনো stuck নেই। কিন্তু খেয়াল করুন, theorem-টিকেই বদলাতে হলো: “value, নয়তো চলে, নয়তো ঘোষিত runtime error”. অংশ ৭-এ Haat-এ ঠিক এটিই দেখবেন।

একটি সতর্কতা: হাজারো test পাস করা প্রমাণ নয়। (ক)-এর ভুলটি ৩,০০০টির মধ্যে মাত্র ১৬টিতে ধরা পড়েছে; কম test চালালে হয়তো ধরাই পড়ত না। প্রমাণ সব term-এর জন্য, test শুধু যেগুলো চালানো হলো সেগুলোর জন্য। তবে উল্টো দিকটিও সত্য: একটি ব্যর্থ test একটি নিশ্চিত পাল্টা উদাহরণ, আর তা খুঁজে পাওয়া প্রমাণ লেখার চেয়ে অনেক সস্তা।

৬ · Variable আর function — substitution lemma

হিসাব-ভাষায় variable বা function নেই। এবার যোগ করি, Haat-এর লেখার ধাঁচে, এক parameter-এর জন্য: t ::= … | x | fn(x: σ) -> τ { return t; } | t(t), আর value-এর তালিকায় যোগ হয় fn. Typing rule তিনটি পর্ব ৩৪-এর T-Var, T-Fn আর T-Call (সেখানকার রূপের এক-parameter সংস্করণ), এখন context Γ-সহ। Call-এর evaluation:

v একটি value
(fn(x: σ) -> τ { return t; })(v) ⟶ [x ↦ v] t
(E-CallFn)

[x ↦ v] t মানে “t-এর ভেতরে মুক্ত x-এর প্রতিটি জায়গায় v বসানো” (পর্ব ৩৫-এর [α ↦ Int]-এর মতো লেখা, তবে এবার type নয়, term বসছে)। সঙ্গে দুটি congruence rule, E-Call1 (আগে callee) আর E-Call2 (তারপর argument), সিদ্ধান্ত ১২-এর ক্রমে। উদাহরণ: (fn(x: Int) -> Int { return x + 60; })(936) ⟶ 936 + 60 ⟶ 996, প্রতিটি ধাপে type Int.

Progress-এ নতুন case T-Call আসে, আর যুক্তি T-Add-এর মতো; শুধু canonical forms-এ একটি তৃতীয় অংশ লাগে: ⊢ v : (σ) -> τ হলে v একটি fn. Preservation-এ নতুন কঠিন case E-CallFn: ফলের term [x ↦ v] t, যার type আগে কখনো হিসাব হয়নি। এর জন্য লাগে:

Lemma ৩৮.৪ — substitution

Γ, x : σ ⊢ t : τ আর Γ ⊢ v : σ হলে Γ ⊢ [x ↦ v] t : τ.

সহজ ভাষায়: যে জায়গায় x : σ ধরে নিয়ে t-এর type পাওয়া গিয়েছিল, সেখানে x-এর বদলে একই type-এর একটি আসল মান বসালে type বদলায় না। বাজারঘরের ভাষায়: ফর্দে “৫০ কেজির একটি চালের বস্তা” লেখা ছিল, আর গুদাম থেকে আসা আসল বস্তাটিও ৫০ কেজির চাল; হিসাবের বাকি সব আগের মতোই মেলে।

প্রমাণের রূপরেখা Γ, x : σ ⊢ t : τ-এর derivation-এর ওপর induction:

  1. T-Var, t = x. তাহলে τ = σ, আর [x ↦ v] x = v; ⊢ v : σ দেওয়া আছে।
  2. T-Var, t = y ≠ x. বসানোর পরেও y; Γ(y) = τ আগের মতো।
  3. T-Int, T-Bool. Literal-এ কিছু বসে না।
  4. T-Add, T-Cmp, T-IfExpr, T-Call. প্রতিটি premise-এ IH, তারপর একই নিয়ম।
  5. T-Fn, t = fn(y: ρ) -> τ′ { return t′; }. সবচেয়ে সূক্ষ্ম case. প্রথমে parameter-এর নাম বদলে (α-renaming) নিশ্চিত করা হয় যে y ≠ x আর v-তে y মুক্ত নয়। তারপর IH খাটাতে হয় বড় context Γ, y : ρ-তে, আর সেজন্য লাগে Γ, y : ρ ⊢ v : σ: এটি পর্ব ৩৪-এর অনুশীলনের weakening lemma. ∎

এখন E-CallFn-এর preservation সহজ: inversion দিয়ে Γ, x : σ ⊢ t : τ আর ⊢ v : σ, তারপর Lemma ৩৮.৪. একটি ব্যাপার লক্ষ করুন: Haat-এর reference interpreter (পর্ব ৫৬ আর ৫৭-এ বিস্তারিত) আসলে substitution করে না; সে environment রাখে, আর closure capture করে by reference (Haat spec). তখন প্রমাণে “term-এর type” ছাড়াও লাগে “environment-এর প্রতিটি মানের type Γ-এর সঙ্গে মেলে” ধরনের একটি invariant. var-এর জন্য যোগ হয় memory-র প্রতিটি ঘরের type-তালিকা (store typing), return-এর জন্য function-এর ফেরত-type ρ, আর while-এর জন্য অসীম চলার সম্ভাবনা। প্রতিটি যোগে প্রমাণ লম্বা হয়, কিন্তু ছক একই থাকে: progress আর preservation. Haat v1-এর পূর্ণ আনুষ্ঠানিক প্রমাণ এই কোর্সে করা হয়নি।

আরও গভীরে। Function-ওয়ালা typed lambda calculus-এ “সব term শেষ হয়” কথাটিও সত্য (strong normalization), কিন্তু তার প্রমাণ progress-preservation দিয়ে হয় না; লাগে William Tait-এর ১৯৬৭ সালের logical relations কৌশল, যা আজও উন্নত type system-এর গবেষণায় প্রধান হাতিয়ার। আরেকটি দিক: বড় ভাষার soundness প্রমাণে হাতে-লেখা ভুল এত সাধারণ যে ২০০৫ সালে POPLmark challenge নামে একটি আহ্বান এসেছিল, এমন প্রমাণ proof assistant-এ যন্ত্র-যাচাই করার জন্য; পর্ব ৪৪-এ (Formal verification) এই ধারা আসবে।

৭ · Soundness যা প্রতিশ্রুতি দেয় না — Haat-এর runtime error

“Well-typed program ভুল করে না” কথাটি সবচেয়ে বেশি ভুল বোঝা হয়। Soundness শুধু একটি জিনিস বাদ দেয়: stuck অবস্থা, অর্থাৎ semantics-এ যে অবস্থার কোনো নিয়ম লেখা নেই। Semantics যা স্পষ্ট লিখে রেখেছে (যেমন “শূন্য দিয়ে ভাগ = runtime error”), তা ঘটা theorem-এর বিরুদ্ধে নয়। Haat-এর reference README-র সিদ্ধান্ত ২৬ ঠিক এমন তিনটি runtime error-এর তালিকা দেয়। নিচের তিনটি program reference checker-এ পাস করে (check বলে ok), তবু চলার সময় থামে:

// divzero.haat
fn share(total: Int, n: Int) -> Int { return total / n; }
print(share(996, 2));
print(share(996, 0));

// uninit.haat  (সিদ্ধান্ত ১৮)
print(fee());
let k = 936;
fn fee() -> Int { return k + 60; }

// deep.haat
fn deep(n: Int) -> Int { return deep(n + 1); }
print(deep(0));

সত্যিকারের run (reference implementation, CPython 3.14.4; run আর vm দুই back end-এ হুবহু একই আউটপুট):

~/haat $ python -B haat.py check divzero.haat
ok
~/haat $ python -B haat.py run divzero.haat
498
1:52: runtime error: division by zero
~/haat $ python -B haat.py check uninit.haat
ok
~/haat $ python -B haat.py run uninit.haat
3:26: runtime error: 'k' is not initialized yet
~/haat $ python -B haat.py check deep.haat
ok
~/haat $ python -B haat.py run deep.haat
1:33: runtime error: stack overflow
ঘটনাHaat-এSoundness-এর সঙ্গে সম্পর্ক
শূন্য দিয়ে ভাগdivision by zero, /-এর অবস্থানে (সিদ্ধান্ত ২৪)ঘোষিত runtime error, E-DivZero-এর মতো; theorem-এর বাইরে নয়
Hoisted function আগে চলে variable পড়ল'k' is not initialized yet (সিদ্ধান্ত ১৮)Type ঠিক, কিন্তু মান তখনো তৈরি হয়নি; Haat এটি static ভাবে ধরে না, চলার সময় যাচাই করে
১,০০০-এর বেশি nested callstack overflowসম্পদের সীমা; semantics-এ মেমরি অসীম ধরা হয়, তাই theorem এ নিয়ে কিছু বলে না
অসীম loop, যেমন while total < 5000 { total = total + 0; }check বলে ok; চালালে কখনো শেষ হয় নাProgress প্রতিটি ধাপে সত্য, চিরকাল; soundness শেষ হওয়ার প্রতিশ্রুতি দেয় না
Integer overflow9223372036854775807 + 1 ছাপে -9223372036854775808 (সত্যিকারের run)ভুলই নয়: wrap সংজ্ঞায়িত (সিদ্ধান্ত ১৩); C-তে signed overflow UB, তাই C-তে এমন নিশ্চয়তা নেই
ভুল ছাড়ের হিসাবType Int, মান ভুলযুক্তির ভুল; type এর কিছুই জানে না

অর্থাৎ soundness একটি আপেক্ষিক প্রতিশ্রুতি: সে যে semantics-এর ওপর প্রমাণিত, শুধু তার সাপেক্ষে। আর একটি গুরুত্বপূর্ণ ব্যবহারিক ফল আছে। Reference-এর runtime.py-তে যোগ-বিয়োগের function arith-এর বিবরণে লেখা “operand types were checked statically”: interpreter আর VM কোনো মানের type-চিহ্ন (tag) যাচাই করে না, checker-এর ওপর ভরসা করে। এই ভরসার যুক্তিই soundness. Checker unsound হলে কী হতো? Interpreter Python-এ লেখা, আর Python-এ True + 1 হলো 2; ভুল program কোনো বার্তা ছাড়াই ভুল সংখ্যা ছাপত। Compiler-এর জগতে এটি আরও গুরুতর: Haat-এর RISC-V back end (পর্ব ৭২) Bool-কে একটি register-এ 0 বা 1 হিসেবে রাখলে, unsound checker-এর ফল হতো যন্ত্রের স্তরে অর্থহীন কাজ, C-র UB-এর মতো।

৮ · বাস্তব ভাষার ফাঁক — TypeScript, Java আর অন্যরা

বাস্তব ভাষাগুলো soundness-এর সঙ্গে আলাদা আলাদা সম্পর্ক রাখে। TypeScript-এর নিজের প্রকাশিত design goals-এ “sound বা provably correct type system” স্পষ্টভাবে লক্ষ্যের বাইরে রাখা হয়েছে; লক্ষ্য হলো সঠিকতা আর কাজের সুবিধার ভারসাম্য। পর্ব ৩৬-এ method parameter-এর bivariance দেখেছেন। এবার আরও দুটি ফাঁক, একটি ফাইলে: any আর array-র covariance.

1o: Order = parse(j)2bill = o.total + 603log("bill:", bill)4items: Item[] = fishes5items.push(dal)6for (f of fishes)7  log(f.kg.toFixed(1))
দুই চোখে
tsc ভাবে
চলার সময়
  1. Checker সন্তুষ্ট। tsc --strict ০টি error দেয়, exit code 0. তারপর সে type মুছে দিয়ে JavaScript লেখে (type erasure); চলার সময় কোনো type-যাচাই থাকে না।
  2. ফাঁক ১: any. parse ফেরত দেয় any, যা কোনো যাচাই ছাড়াই Order-এ বসে যায়। কিন্তু JSON-এ total লেখা ছিল "936", একটি string. Checker-এর বিশ্বাসে number, বাস্তবে string. এখানেই soundness ভাঙল, যদিও কিছু চোখে পড়েনি।
  3. নীরব ভুল। o.total + 60: checker ভাবে সংখ্যা যোগ। JavaScript-এ string + number মানে জোড়া লাগানো: "93660". কোনো error নেই, শুধু ভুল বিল। Preservation-এর ভাষায়: “number” type-এর expression থেকে string মান এল।
  4. ফাঁক ২: covariant array. Fish[]-কে Item[] হিসেবে নেওয়া TypeScript মেনে নেয়। দুটি নাম, একটিই array. পড়ার জন্য এটি নিরাপদ, লেখার জন্য নয় (পর্ব ৩৬-এর variance-এর নিয়ম)।
  5. ভুল জিনিস ঢুকল। items-এর type Item[], তাই একটি সাধারণ Item (ডাল) ঢোকানো বৈধ। কিন্তু সেটি fishes-এরও ভেতরে, যার প্রতিটি জিনিসের kg থাকার কথা।
  6. দূরে গিয়ে crash. loop প্রথমে ilish 1.5 ছাপে, তারপর ডালে f.kg = undefined, আর toFixed-এ TypeError. ভুলের কারণ লাইন ৪ আর ৫, crash লাইন ৭-এ। Java হলে লাইন ৫-এর মতো জায়গাতেই ArrayStoreException আসত।

পুরো ফাইলটি লেখকের lab-এ সত্যিকারের run-এ যাচাই করা (TypeScript 5.9.2, Node.js 24.15.0):

// বাজারঘর: tsc --strict পাস করে, তবু চলার সময় ভুল
type Order = { id: number; total: number };
function parse(json: string): any { return JSON.parse(json); }

// ফাঁক ১: any — কোনো যাচাই ছাড়াই যেকোনো type-এ বসে যায়
const o: Order = parse('{"id": 7, "total": "936"}');
const bill: number = o.total + 60;          // tsc ভাবে number + number
console.log("bill:", bill);

// ফাঁক ২: array covariance — Fish[] কে Item[] হিসেবে নেওয়া যায়
class Item { constructor(public name: string) {} }
class Fish extends Item {
  constructor(name: string, public kg: number) { super(name); }
}
const fishes: Fish[] = [new Fish("ilish", 1.5)];
const items: Item[] = fishes;               // মেনে নেয়
items.push(new Item("dal"));                // একই array-তে ডাল ঢুকল
for (const f of fishes) {
  console.log(f.name, f.kg.toFixed(1));     // tsc ভাবে kg সবসময় আছে
}
~/tsound $ tsc --strict --target es2022 --outDir out unsound.ts
~/tsound $ echo $?
0
~/tsound $ node out/unsound.js
bill: 93660
ilish 1.5
~/tsound/out/unsound.js:25
    console.log(f.name, f.kg.toFixed(1)); // tsc ভাবে kg সবসময় আছে
                             ^

TypeError: Cannot read properties of undefined (reading 'toFixed')

tsc-এর লেখা JavaScript নিচে, হুবহু; শুধু শেষ loop-টি একটি try/catch-এ মোড়ানো, যাতে browser-এ error-এর বার্তা ছাপা হয়। চালিয়ে দেখুন:

"use strict";
// tsc --strict-এর লেখা JavaScript: সব type মুছে গেছে
function parse(json) { return JSON.parse(json); }
// ফাঁক ১: any — কোনো যাচাই ছাড়াই যেকোনো type-এ বসে যায়
const o = parse('{"id": 7, "total": "936"}');
const bill = o.total + 60; // tsc ভাবে number + number
console.log("bill:", bill);
// ফাঁক ২: array covariance — Fish[] কে Item[] হিসেবে নেওয়া যায়
class Item {
    name;
    constructor(name) {
        this.name = name;
    }
}
class Fish extends Item {
    kg;
    constructor(name, kg) {
        super(name);
        this.kg = kg;
    }
}
const fishes = [new Fish("ilish", 1.5)];
const items = fishes; // মেনে নেয়
items.push(new Item("dal")); // একই array-তে ডাল ঢুকল
try { // শুধু এই try/catch লেখকের যোগ করা
    for (const f of fishes) {
        console.log(f.name, f.kg.toFixed(1)); // tsc ভাবে kg সবসময় আছে
    }
} catch (e) { console.log(e.name + ": " + e.message); }

আসল আউটপুট (ব্রাউজারে; লেখকের Node.js 24.15.0-তেও একই বার্তা):

bill: 93660
ilish 1.5
TypeError: Cannot read properties of undefined (reading 'toFixed')

তুলনার জন্য, একই lab-এ সরাসরি const o2: Order = { id: 7, total: "936" }; লিখলে tsc ধরে: error TS2322: Type 'string' is not assignable to type 'number'. আর parse-এর ফেরত-type unknown করলে: error TS2322: Type 'unknown' is not assignable to type 'Order'. অর্থাৎ ফাঁকটি any-তে, checker-এর বাকি অংশে নয়। ব্যবহারিক শিক্ষা: বাইরে থেকে আসা তথ্য (JSON, API) unknown হিসেবে নিন আর চলার সময় যাচাই করুন; any আর type assertion (as) প্রতিটিই checker-এর কাছে একটি অপ্রমাণিত দাবি।

ভাষাঅবস্থা (সংক্ষেপে, সতর্ক ভাষায়)
Standard MLপুরো ভাষার আনুষ্ঠানিক সংজ্ঞা আছে (১৯৯০, সংশোধিত ১৯৯৭); ২০০৭ সালে Lee, Crary আর Harper একটি অভ্যন্তরীণ ভাষার মাধ্যমে soundness-এর যন্ত্র-যাচাই প্রমাণ জানান
WebAssemblySpec-এ typing rule আর soundness theorem; Conrad Watt ২০১৮ সালে Isabelle-এ যন্ত্র-যাচাই করেন (পর্ব ৩৪-এ উল্লেখ)
JavaCore অংশ (Featherweight Java, ১৯৯৯/২০০১) sound প্রমাণিত; covariant array-র ফাঁক চলার সময়ের যাচাইয়ে ধরা পড়ে (ArrayStoreException, পর্ব ৩৬)। Amin আর Tate ২০১৬ সালে দেখান যে null আর wildcard-এর মিশ্রণে Java আর Scala-র type system unsound
TypeScriptইচ্ছা করে unsound: any, as, covariant array, method bivariance; চলার সময় type মুছে যায়
CType-safe নয়: cast, union আর সীমার বাইরে লেখা UB; checker-এর type চলার সময় কিছু নিশ্চিত করে না
RustSafe অংশটি sound হওয়ার লক্ষ্যে নকশা; RustBelt (২০১৮) একটি core ভাষা আর কিছু library-র জন্য প্রমাণ দেয়; unsafe block প্রমাণের দায় programmer-এর ওপর দেয় (পর্ব ৭৬)

লক্ষ করুন Java-র ক্ষেত্রে একটি সূক্ষ্ম পার্থক্য। Static type কখনো কখনো মিথ্যা বলে (array covariance), কিন্তু JVM প্রতিটি array-লেখায় যাচাই করে exception ছোড়ে, তাই program কখনো stuck অবস্থায় যায় না। এমন ভাষাকে বলা যায় “চলার সময়ের যাচাইসহ safe”: theorem-টি তখন “value, নয়তো চলে, নয়তো একটি ঘোষিত exception”, ঠিক অংশ ৫-এর E-DivZero-এর মতো। TypeScript-এ সেই যাচাইও নেই; ভুল মান চুপচাপ এগিয়ে যায়, যেমন 93660.

পরীক্ষা ও ইন্টারভিউতে। বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রচলিত:

  • “Progress আর preservation বিবৃত করুন।” Progress: ⊢ t : τ হলে t value বা t ⟶ t′. Preservation: ⊢ t : τ আর t ⟶ t′ হলে ⊢ t′ : τ.
  • “Canonical forms lemma কেন দরকার?” Progress-এ operand value হলে তার আকার (true/false, n) জানতে, যাতে computation rule খাটানো যায়।
  • “Preservation-এর উল্টো (subject expansion) কি সত্য?” না: if true then 1 else false ⟶ 1; ফল well-typed, শুরুটি নয়।
  • “Sound language-এ runtime error হয় কেন?” Semantics-এ ঘোষিত error (শূন্য দিয়ে ভাগ, exception) stuck নয়; soundness শুধু stuck অবস্থা বাদ দেয়।
  • “TypeScript কি sound?” না, ইচ্ছা করেই: any, as, covariant array, method bivariance; চলার সময় type মুছে যায়।

৯ · AI-এর যুগে type soundness

AI assistant এই বিষয়ে ঝরঝরে প্রমাণ লেখে, আর সেখানেই বিপদ: প্রমাণ দেখতে পূর্ণ, অথচ একটি case বাদ, বা একটি lemma নিঃশব্দে ধরে নেওয়া।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
“Sound মানে runtime error নেই” বা “well-typed program সঠিক ফল দেয়”Semantics-এ ঘোষিত error আর stuck-এর পার্থক্য খোঁজা; Haat-এ division by zero চালিয়ে দেখা
Progress-এর প্রমাণে canonical forms ছাড়া সরাসরি “তাই E-IfTrue খাটে” লেখাপ্রতিটি computation rule-এর আগে value-এর আকার কোথা থেকে জানা গেল, খোঁজা
Congruence case (E-Add1, E-If) বাদ দিয়ে শুধু computation rule-এর case দেখানোপ্রতিটি evaluation rule-এর একটি case আছে কি না গুনে মেলানো
এক ভাষার দাবি সবখানে: “Java sound”, “TypeScript sound strict mode-এ”ভাষা আর version উল্লেখ করে আসল compiler-এ পাল্টা উদাহরণ চালানো (যেমন tsc --strict, তারপর node)
“Test-এ পাস, তাই প্রমাণিত”Test পাল্টা উদাহরণ খোঁজে, প্রমাণ সব term-এর জন্য; দুটিকে আলাদা রাখা
বানানো paper, বছর বা theorem-এর নামPaper-এর শিরোনাম আর প্রকাশস্থান প্রাথমিক উৎসে মেলানো

AI-কে কাজে লাগাতে ভাষার নিয়মগুলো পুরো দিন, আর প্রতিটি case আলাদা করে চান:

আমার ছোট ভাষা: t ::= n | true | false | t + t | t < t | if t then t else t. Typing rule: T-Int, T-Bool, T-Add, T-Cmp, T-IfExpr (দুই শাখার type এক)। Small-step rule: E-Add, E-Add1, E-Add2, E-Lt, E-Lt1, E-Lt2, E-IfTrue, E-IfFalse, E-If; বাঁ থেকে ডানে। ১. Progress আর preservation-এর প্রমাণ দাও, derivation-এর ওপর induction-এ, প্রতিটি typing rule আর প্রতিটি evaluation rule-এর case আলাদা করে। কোনো case "একইভাবে" বলে বাদ দেবে না। ২. কোথায় canonical forms lemma লাগে, ঠিক সেই লাইনটি চিহ্নিত করো। ৩. আমি t / t আর T-Div যোগ করলে কোন theorem ভাঙে, একটি পাল্টা উদাহরণ দাও, আর দুটি সমাধান বলো। ৪. যেখানে নিশ্চিত নও, স্পষ্ট বলো; আমি প্রতিটি দাবি একটি Python property test-এ চালিয়ে যাচাই করব।

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।

প্র ০১Milner ১৯৭৮ সালেই soundness প্রমাণ করেছিলেন। তাহলে ১৯৯৪ সালের Wright–Felleisen-এর “syntactic” পদ্ধতি এত জনপ্রিয় হলো কেন?

Milner-এর প্রমাণ ছিল denotational: প্রতিটি program-এর অর্থ একটি গাণিতিক বস্তু, আর মানের জগতে একটি বিশেষ উপাদান “wrong” রাখা হয়, যা আসে যখন কোনো operation ভুল ধরনের মান পায়। Theorem বলে, well-typed program-এর অর্থ কখনো wrong নয়। পদ্ধতিটি সুন্দর, কিন্তু তার জন্য দরকার ভাষার পুরো denotational model, যা recursion, mutable memory বা exception থাকলে বেশ জটিল গণিত (domain theory) দাবি করে। নতুন একটি feature যোগ করলে model-টাই নতুন করে গড়তে হতে পারে।

Wright আর Felleisen দেখালেন, program-কে ধাপে ধাপে term থেকে term-এ বদলানোর নিয়ম দিয়েই কাজ চলে। “Wrong” তখন আর একটি বিশেষ মান নয়; এটি শুধু stuck term, যার জন্য কোনো নিয়ম নেই। প্রমাণ ভাঙে দুটি ছোট lemma-তে, আর প্রতিটির প্রমাণ নিয়মের ওপর সাধারণ induction, ঠিক এই পর্বের মতো। নতুন feature যোগ করলে নতুন নিয়ম আসে, আর প্রমাণে নতুন case যোগ হয়; পুরোনো case-গুলো প্রায় অপরিবর্তিত থাকে। Mutable reference, exception, continuation-এর মতো কঠিন feature-ও এই ছকে সামলানো যায় বলে তাঁরা দেখান।

এর একটি বড় ব্যবহারিক ফল: পদ্ধতিটি একজন স্নাতক ছাত্রের নাগালে এল। Pierce-এর পাঠ্যবই (২০০২) প্রায় প্রতিটি নতুন type feature-এর জন্য একই ছক ব্যবহার করে, আর আজ নতুন ভাষা-নকশার paper-এ “progress আর preservation প্রমাণিত” একটি প্রায় আবশ্যিক বাক্য। Proof assistant-এ যন্ত্র-যাচাইও এই ধাঁচে সহজ, কারণ নিয়মগুলো সরাসরি inductive সংজ্ঞা হিসেবে লেখা যায়। তবে denotational পদ্ধতি হারিয়ে যায়নি; program-এর সমতা প্রমাণে (দুটি program কি একই কাজ করে) তার শক্তি এখনো বেশি, যা পর্ব ৪১-এ (Denotational semantics) আসবে।

মূল উপলব্ধি: একই theorem দুই পথে প্রমাণ করা যায়; syntactic পথটি জিতেছে কারণ সেটি ভাষার সঙ্গে ধাপে ধাপে বাড়ে, সাধারণ induction-এই চলে, আর যন্ত্রে যাচাই করা সহজ।

প্র ০২ML-এ polymorphism আর mutable reference একসঙ্গে আসতেই soundness ভেঙে গিয়েছিল। কীভাবে, আর সমাধান কী ছিল?

পর্ব ৩৫-এ let-polymorphism দেখেছেন: let id = fn x => x-এর type ∀α. α → α, তাই একে Int-এও, Bool-এও ব্যবহার করা যায়। এবার ML-এর ref ধরুন, যা একটি পরিবর্তনযোগ্য ঘর বানায়। let r = ref [] (একটি খালি list-এর ঘর) সাধারণ নিয়মে type পায় ∀α. α list ref, অর্থাৎ “যেকোনো type-এর list-এর ঘর”। এক জায়গায় r := [1] লিখে ঘরে Int-এর list রাখা হলো, অন্য জায়গায় r-কে Bool list ref হিসেবে পড়ে মাথার উপাদানকে Bool হিসেবে ব্যবহার করা হলো। দুটি ব্যবহারই type-check হয়, অথচ চলার সময় 1-কে Bool ভাবা হয়: ঠিক stuck অবস্থা।

প্রমাণের ভাষায় ভুলটি preservation-এ। ঘরটি একটিই, কিন্তু type system তাকে অনেক type-এর বলে দাবি করেছে; একটি লেখার পরে memory-র অবস্থা আর type-এর দাবি মেলে না। ১৯৮০-এর দশক থেকে এই সমস্যার নানা সমাধান প্রস্তাবিত হয়, যেমন Mads Tofte-এর ১৯৯০ সালের “imperative type variable” ধারণা, যেগুলো নিয়মকে জটিল করত। শেষে ১৯৯৫ সালের দিকে Andrew Wright একটি খুব সরল নিয়ম প্রস্তাব করেন, value restriction: শুধু syntactic value (যেমন function বা literal) সাধারণীকৃত হবে, ref []-এর মতো কাজ-করা expression নয়। কিছু সঠিক program হারানোর দাম তুলনায় ছোট দেখা গেল, আর Standard ML-এর ১৯৯৭ সংশোধনে এই ধাঁচের নিয়ম গৃহীত হয়; OCaml পরে আরেকটু ঢিলে রূপ (relaxed value restriction) নেয়।

শিক্ষাটি বড়: দুটি feature আলাদাভাবে sound হলেও একসঙ্গে unsound হতে পারে। প্রতিটি নতুন feature-এর পর progress-preservation আবার চালানোর অভ্যাস ঠিক এই কারণেই। Haat v1 এই বিপদ থেকে মুক্ত, কারণ তার type monomorphic: var-এর type একবার ঠিক হয়, আর কখনো ∀ পায় না। Haat-এর বর্ধিত রূপে generics (পর্ব ৩৬–৩৭) আর var একসঙ্গে এলে এই প্রশ্ন আবার উঠবে।

মূল উপলব্ধি: polymorphism আর mutation-এর মিলনে preservation ভেঙেছিল; value restriction একটি সরল syntactic শর্ত দিয়ে তা সারায়, আর দেখায় যে feature-গুলোর soundness একসঙ্গেই যাচাই করতে হয়।

প্র ০৩একটি ভাষা কেন ইচ্ছা করে unsound হতে চাইবে? TypeScript আর Dart-এর পথ তুলনা করুন।

TypeScript-এর লক্ষ্য ছিল বিদ্যমান JavaScript-এর ওপর type বসানো, যাতে লাখো লাইনের পুরোনো কোড ধীরে ধীরে, ফাইল ধরে ধরে type পায়। JavaScript-এর প্রচলিত ধাঁচগুলো (callback-এ বেশি বা কম argument, method-কে ঢিলেভাবে override করা, array-কে বিভিন্ন জায়গায় পাঠানো) কঠোর sound নিয়মে অনেক error দিত। TypeScript-এর design goals তাই স্পষ্ট বলে, sound type system লক্ষ্য নয়; লক্ষ্য হলো বেশিরভাগ বাস্তব bug ধরা আর খুব কম মিথ্যা alarm. any পুরোনো, type-হীন কোডের সঙ্গে সেতু; method bivariance আর covariant array প্রচলিত ধাঁচ টিকিয়ে রাখে। সময়ের সঙ্গে কিছু ফাঁক বন্ধও হয়েছে, যেমন ২.৬ সংস্করণে (২০১৭) --strictFunctionTypes আর ৩.০ সংস্করণে (২০১৮) unknown type.

Dart উল্টো পথে হেঁটেছে। Dart 1-এর type ছিল মূলত ঐচ্ছিক সতর্কবাণী, আর ভাষাটি জেনেশুনে unsound ছিল। ২০১৮ সালের দিকে Dart 2-তে sound type system আনা হয়, আর যেখানে static যাচাই সম্ভব নয় (যেমন covariant generic-এর কিছু ক্ষেত্রে), সেখানে চলার সময়ের যাচাই বসানো হয়, Java-র array-র মতো। Google-এর Dart দল এর পক্ষে দুটি যুক্তি দিয়েছিল বলে জানা যায়: ভুল আগে ধরা, আর compiler-এর পক্ষে type-এ ভরসা করে দ্রুত কোড বানানো। দ্বিতীয়টি অংশ ৭-এর কথা: unsound checker-এর ওপর optimizer ভরসা করতে পারে না।

দুটি পথই যুক্তিসঙ্গত, শুধু লক্ষ্য আলাদা। TypeScript compiler-এর output হলো সাধারণ JavaScript, তাই type ভুল হলেও engine মেমরি-নিরাপদভাবে TypeError দেয়; ক্ষতি “ভুল ফল বা পরে crash”, যন্ত্রের স্তরের বিপর্যয় নয়। যে ভাষা type দেখে native code বানায়, তার জন্য unsoundness অনেক বেশি বিপজ্জনক। তাই প্রশ্নটি সবসময় এমন: type-এর ওপর কে ভরসা করছে, আর ভরসা ভাঙলে কী হয়?

মূল উপলব্ধি: soundness একটি নকশা-সিদ্ধান্ত; পুরোনো কোডের সঙ্গে মানিয়ে নেওয়ার জন্য TypeScript তা ছেড়েছে, আর optimizer ও আগে ভুল ধরার জন্য Dart তা গ্রহণ করেছে, বাকি ফাঁক চলার সময়ের যাচাইয়ে ঢেকে।

প্র ০৪Java-র type system নিয়ে বছরের পর বছর গবেষণা হয়েছে। তবু ২০১৬ সালে কীভাবে একটি unsoundness ধরা পড়ল, আর এ থেকে কী শেখার আছে?

১৯৯৯ সালের দিকে Igarashi, Pierce আর Wadler Featherweight Java প্রস্তাব করেন: Java-র একটি ক্ষুদ্র core, যেখানে class, field, method, cast আর inheritance আছে, কিন্তু প্রায় আর কিছু নেই। এই core-এর জন্য progress আর preservation প্রমাণ করা হয়, আর পরে generics-সহ রূপের জন্যও। এমন core-ভাষা গবেষণায় খুব কাজের, কিন্তু একটি ঝুঁকি থাকে: আসল ভাষার যে feature-গুলো core-এ নেই, সেগুলোর মিলন থেকে নতুন সমস্যা আসতে পারে।

২০১৬ সালে Nada Amin আর Ross Tate ঠিক এমন একটি মিলন দেখান। Java-র wildcard (? extends T, ? super T) আসলে একটি অস্তিত্বসূচক type, আর type-এর সম্পর্ক নিয়ে কিছু যুক্তি checker ধরে নেয় যে সংশ্লিষ্ট মানটি আছে। কিন্তু Java-তে যেকোনো reference-এর মান null হতে পারে, আর null সেই যুক্তির “প্রমাণ” হিসেবে কাজ করে, অথচ কোনো প্রমাণ বহন করে না। ফল: তাঁরা এমন একটি ছোট program দেখান, যা compiler মেনে নেয়, অথচ চালালে একটি Integer-কে String হিসেবে ব্যবহারের চেষ্টা হয় আর ClassCastException আসে, যেখানে কোডে কোনো cast লেখা নেই। Scala-র জন্যও তাঁরা অনুরূপ উদাহরণ দেন। তাঁদের paper-এর শিরোনামেই দাবিটি আছে: Java আর Scala-র type system unsound.

তিনটি শিক্ষা। এক, core ভাষার প্রমাণ মূল্যবান, কিন্তু পুরো ভাষার নিশ্চয়তা নয়; feature-এর মিলনই বিপদের জায়গা (প্রশ্ন ২-এর মতো)। দুই, JVM-এর চলার সময়ের যাচাই এখানে শেষ রক্ষা করেছে: ClassCastException একটি ঘোষিত exception, মেমরি নষ্ট নয়। তিন, বাস্তবে এমন ফাঁক খুব কৃত্রিম কোডেই দেখা দেয়, তাই ভাষা-রক্ষকেরা প্রায়ই ঠিক করেন সারাতে গিয়ে পুরোনো কোড ভাঙবে কি না; এখানে সঠিকতা আর সামঞ্জস্যের টানাপোড়েন আবার দেখা যায়।

মূল উপলব্ধি: ছোট core-এর প্রমাণ পুরো ভাষার প্রমাণ নয়; null-এর মতো একটি নিরীহ feature-ও প্রমাণের ধরে-নেওয়া কথা ভাঙতে পারে, আর চলার সময়ের যাচাই তখন “unsound কিন্তু safe” অবস্থা রক্ষা করে।

প্র ০৫হাতে লেখা প্রমাণ, property-based test আর proof assistant-এ যন্ত্র-যাচাই: একটি নতুন ভাষার soundness-এর জন্য কোনটি কতটা ভরসার?

হাতে লেখা প্রমাণ এই পর্বের মতো ছোট ভাষায় ভালো কাজ করে। কিন্তু বাস্তব ভাষার নিয়ম শত শত, আর প্রমাণে “বাকি case একইভাবে” লেখার প্রলোভন প্রবল। অংশ ৫-এর ঢিলে T-IfExpr ঠিক এমন একটি ভুল, যা পড়ার সময় চোখ এড়িয়ে যেতে পারে। Casey Klein, Robert Bruce Findler আর সহকর্মীরা ২০১২ সালের একটি paper-এ (“Run Your Research”) একটি সম্মেলনের প্রকাশিত বেশ কয়েকটি ভাষা-model PLT Redex নামের tool-এ লিখে এলোমেলো test চালান, আর তাঁরা জানান যে পরীক্ষিত প্রতিটি model-এই কোনো না কোনো ভুল পেয়েছেন, যার কয়েকটি প্রকাশিত দাবিকে প্রভাবিত করে। কাজটি দেখায়, অংশ ৫-এর ধাঁচের test কত সস্তায় কত ভুল ধরে।

কিন্তু test সব term দেখে না। পূর্ণ নিশ্চয়তার জন্য প্রমাণটিকে Coq (এখন Rocq), Isabelle, Lean বা Agda-র মতো proof assistant-এ লেখা হয়, যেখানে যন্ত্র প্রতিটি ধাপ যাচাই করে। ২০০৫ সালের POPLmark challenge এমন যন্ত্র-যাচাইকে নিয়মিত চর্চা বানানোর আহ্বান জানায়। এর ফল চোখে পড়ার মতো: WebAssembly-র spec যন্ত্রে প্রমাণ করতে গিয়ে Conrad Watt ২০১৮ সালে spec-এর ত্রুটি পেয়েছেন বলে জানান; CakeML প্রকল্প একটি ML-ধাঁচের ভাষার যন্ত্র-যাচাইকৃত compiler বানিয়েছে; RustBelt Rust-এর একটি core-এর জন্য এমন প্রমাণ দিয়েছে। দাম হলো সময়: যন্ত্র-প্রমাণ সাধারণত হাতের প্রমাণের চেয়ে বহুগুণ লম্বা।

বাস্তবের ভালো চর্চা তাই তিন স্তরের। নকশার শুরুতে property test, প্রতিটি নিয়ম বদলের পর সেকেন্ডের মধ্যে ফল। তারপর হাতে প্রমাণ, যা কেন সত্য তা বোঝায়। আর গুরুত্বপূর্ণ ভাষা বা core-এর জন্য যন্ত্র-প্রমাণ, যা নিশ্চয়তা দেয়। Haat-এর মতো শেখার ভাষায় প্রথম দুটিই যথেষ্ট; পর্ব ৪৪-এ যন্ত্র-যাচাইয়ের ধারণা আরও বিস্তারে আসবে।

মূল উপলব্ধি: test সস্তায় ভুল খোঁজে, হাতের প্রমাণ কারণ বোঝায়, যন্ত্র-প্রমাণ নিশ্চয়তা দেয়; গুরুত্বপূর্ণ ভাষায় তিনটিই লাগে, আর ক্রমটি সাধারণত এই।

অনুশীলন

প্রথমে নিজে লিখুন বা হিসাব করুন, তারপর উত্তর খুলুন। প্রতিটি উত্তর চালানো কোড দিয়ে যাচাই করা।

  1. নকশা ও বাস্তবায়ন — ! আর short-circuit &&: হিসাব-ভাষায় !t আর t && t যোগ করুন; && Haat-এর মতো short-circuit, অর্থাৎ বাঁ পাশ false হলে ডান পাশ চলে না। (ক) typing rule আর evaluation rule লিখুন। (খ) progress আর preservation-এ কোন নতুন case আসে, প্রমাণ করুন। (গ) অংশ ২-এর check আর step-এ যোগ করে অংশ ৫-এর test চালান। (ঘ) (1 < 0) && ((1 + true) < 0) চলে, অথচ checker বাতিল করে কেন?

    (ক) T-Not: ⊢ t : Bool থেকে ⊢ !t : Bool. T-And: ⊢ t1 : Bool আর ⊢ t2 : Bool থেকে ⊢ t1 && t2 : Bool. Evaluation: E-Not (!true ⟶ false, !false ⟶ true), E-Not1 (t ⟶ t′ হলে !t ⟶ !t′), E-AndTrue (true && t2 ⟶ t2), E-AndFalse (false && t2 ⟶ false), E-And1 (t1 ⟶ t1′ হলে t1 && t2 ⟶ t1′ && t2). লক্ষ করুন E-And2 নেই: ডান পাশ আলাদা করে কখনো চলে না, এটিই short-circuit.

    (খ) Progress, T-And: IH দিয়ে t1 চললে E-And1; value হলে canonical forms (১) দিয়ে true বা false, তারপর E-AndTrue বা E-AndFalse. T-Not একই রকম। Preservation, T-And: E-AndTrue-তে t′ = t2, premise থেকে Bool; E-AndFalse-এ t′ = false, T-Bool; E-And1-এ IH আর T-And. ∎ (গ) লেখকের lab-এ (CPython 3.14.4), wrapper-এর একই কৌশলে নতুন শাখা যোগ করা হলো:

    def check(t):
        if t[0] == "!": return "Bool" if check(t[1]) == "Bool" else None
        if t[0] == "&&": return "Bool" if [check(t[1]), check(t[2])] == ["Bool"] * 2 else None
        return good_check(t)
    def step(t):
        if t[0] == "&&":
            a = t[1]
            if not is_val(a): r = step(a); return r and (("&&", r[0], t[2]), f"E-And1({r[1]})")
            if a[0] != "bool": return None
            return (t[2], "E-AndTrue") if a[1] else (("bool", False), "E-AndFalse")
        ...   # "!"-এর শাখা একই ধাঁচে, তারপর return good_step(t)

    নতুন generator (! আর &&-সহ, seed 38) দিয়ে ৩,০০০টি well-typed term, ৪৭,২৬৭টি ধাপ, সবচেয়ে লম্বা ৫৮ ধাপ, ব্যর্থ ০টি। (ঘ) Trace: (1 < 0) && ((1 + true) < 0) ⟶ E-And1(E-Lt) ⟶ false && ((1 + true) < 0) ⟶ E-AndFalse ⟶ false. ডান পাশের 1 + true কখনো চলেনি, তাই আটকায়নি; কিন্তু T-And দুই পাশেরই type চায়, তাই checker বাতিল করে (type None). আবার সেই incompleteness: checker চলার পথ জানে না।

  2. ভুল প্রমাণ খুঁজুন: একজন হিসাব-ভাষায় t / t যোগ করলেন, নিয়ম T-Div (দুটি Int থেকে Int) আর E-Div (n2 ≠ 0 হলে n1 / n2 ⟶ শূন্যের দিকে কাটা ভাগফল), সঙ্গে E-Div1, E-Div2. তাঁর progress-এর নতুন case: “(১) T-Div-এর premise ⊢ t1 : Int, ⊢ t2 : Int. (২) IH দিয়ে কেউ চললে E-Div1 বা E-Div2. (৩) দুটিই value হলে canonical forms দিয়ে n1, n2. (৪) তাই E-Div খাটে। ∎” কোন ধাপ ভুল? পাল্টা উদাহরণ আর দুটি সংশোধন দিন।

    ধাপ (৪) ভুল। E-Div-এর একটি side condition আছে, n2 ≠ 0, আর ধাপ (৩) শুধু জানায় n2 একটি integer, শূন্য নয় এমন কিছু নয়। পাল্টা উদাহরণ: 10 / 0. ⊢ 10 / 0 : Int (T-Div, দুটি T-Int), value নয়, অথচ কোনো নিয়ম খাটে না: stuck. অংশ ৫-এর property test ঠিক এটিই খুঁজে পেয়েছে (৮৯৬টি term, সবচেয়ে ছোট আটকে-যাওয়া অবস্থা 10 / 0).

    সংশোধন ১ (semantics বদলানো): E-DivZero যোগ করা, যা n / 0 থেকে একটি বিশেষ error অবস্থায় যায় আর program থামায়; theorem হয় “value, নয়তো চলে, নয়তো error”. Haat (সিদ্ধান্ত ২৬), Java (ArithmeticException) আর Python (ZeroDivisionError) মোটামুটি এই পথে। সংশোধন ২ (type বদলানো): ভাজকের জন্য একটি আলাদা type, যেমন NonZeroInt, যার value শূন্য হতে পারে না; তখন canonical forms নিজেই বলে n2 ≠ 0. এটি refinement type-এর ধারণা, পর্ব ৩৯-এ (উন্নত type) আসবে। দাম: programmer-কে দেখাতে হয় যে ভাজক শূন্য নয়, যা সবসময় সহজ নয়। C-র পথটি তৃতীয়: integer-কে শূন্য দিয়ে ভাগ undefined behavior; অর্থাৎ semantics-এ “stuck”-কেই বৈধ রেখে দেওয়া, যা soundness-এর ঠিক উল্টো।

  3. Trace আর আউটপুট অনুমান: হিসাব-ভাষায় নিচের term-টি ধাপে ধাপে চালান। প্রতিটি ধাপে নিয়মের নাম (congruence-সহ) আর type লিখুন। শেষ value কী? if (2 + -2 < 1) then (9223372036854775807 + 1 < 0) else false

    অংশ ২-এর step আর check দিয়ে লেখকের lab-এ চালানো (CPython 3.14.4) আউটপুট, প্রতিটি লাইনে term : type:

    if ((2 + -2) < 1) then ((9223372036854775807 + 1) < 0) else false : Bool
       ⟶ E-If(E-Lt1(E-Add))
    if (0 < 1) then ((9223372036854775807 + 1) < 0) else false : Bool
       ⟶ E-If(E-Lt)
    if true then ((9223372036854775807 + 1) < 0) else false : Bool
       ⟶ E-IfTrue
    (9223372036854775807 + 1) < 0 : Bool
       ⟶ E-Lt1(E-Add)
    -9223372036854775808 < 0 : Bool
       ⟶ E-Lt
    true : Bool

    ৫ ধাপ, প্রতিটিতে type Bool (preservation). শেষ value true: সবচেয়ে বড় Int-এ ১ যোগ করলে 64-bit wrap-এ সবচেয়ে ছোট Int, যা ঋণাত্মক। Haat-এর reference-এ print(9223372036854775807 + 1); চালালেও সত্যিকারের run-এ -9223372036854775808 আসে। লক্ষ করুন, overflow এখানে ভুল নয়, একটি সংজ্ঞায়িত ধাপ (সিদ্ধান্ত ১৩); C-র signed int-এ একই হিসাব UB হতো।

  4. প্রমাণ — preservation-এর উল্টো দিক: “Subject expansion” দাবি করে: t ⟶ t′ আর ⊢ t′ : τ হলে ⊢ t : τ. হিসাব-ভাষায় এটি সত্য কি না প্রমাণ বা খণ্ডন করুন। পর্ব ৩৩-এর incompleteness-এর সঙ্গে এর সম্পর্ক কী?

    মিথ্যা। পাল্টা উদাহরণ: t = if true then 1 else false. E-IfTrue দিয়ে t ⟶ 1, আর ⊢ 1 : Int. কিন্তু t-এর কোনো type নেই: T-IfExpr দুই শাখার type এক চায়, Int আর Bool মেলে না। লেখকের lab-এ অংশ ২-এর কোড দিয়ে যাচাই: check(t) দেয় None, আর step(t) দেয় (("num", 1), "E-IfTrue").

    সম্পর্কটি সরাসরি। পর্ব ৩৩-এর ২৭৫টি “বাতিল, তবু চলে” expression-এর প্রতিটি এমন একটি term, যা কিছু ধাপ পরে well-typed হয়ে যায় (শেষ value তো সবসময় well-typed). Subject expansion সত্য হলে, value-তে পৌঁছানো প্রতিটি term-কে well-typed হতে হতো, অর্থাৎ checker complete হতো। Rice-এর theorem (Theory of Computation, পর্ব ৫৩) বলে, যথেষ্ট শক্তিশালী ভাষায় এমন checker অসম্ভব। হিসাব-ভাষা ছোট বলে এখানে হয়তো একটি complete checker বানানো যেত (চালিয়ে দেখলেই হয়, কারণ সব term শেষ হয়), কিন্তু T-IfExpr-এর মতো syntax-directed নিয়ম তা করে না, আর সেটিই ইচ্ছাকৃত: checker program চালায় না।

    এক লাইনে: preservation সামনের দিকে type রক্ষা করে, পেছনের দিকে নয়; আর এই অসমতাই রক্ষণশীল checker-এর চিহ্ন।

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।

ক্রমSmall-step নিয়মে (বাঁ থেকে ডানে, if-এ আগে শর্ত) if (1 + 2 < 4) then 10 else 20 চালালে যে term-গুলো পরপর আসে, সেভাবে সাজান (▲▼ চেপে সরান)

  1. if (1 + 2 < 4) then 10 else 20
  2. if (3 < 4) then 10 else 20
  3. if true then 10 else 20
  4. 10

Type soundness-এর progress theorem কী বলে?

  • ⊢ t : τ আর t ⟶ t′ হলে ⊢ t′ : τ
  • ⊢ t : τ হলে t একটি value, অথবা কোনো t′-এর জন্য t ⟶ t′
  • ⊢ t : τ হলে t সসীম ধাপে একটি value-তে পৌঁছায়
  • t ⟶ t′ আর ⊢ t′ : τ হলে ⊢ t : τ

হিসাব-ভাষায় (n, true, false, +, <, if-then-else; বাঁ থেকে ডানে small-step) নিচের কোন term stuck, অর্থাৎ value নয় অথচ কোনো নিয়মে চলতে পারে না?

  • true + 1
  • if true then 1 else 2
  • 5
  • 1 + 2 < 4

Progress-এর প্রমাণে T-IfExpr case-এ শর্ত t₁ একটি value আর ⊢ t₁ : Bool. E-IfTrue বা E-IfFalse খাটানোর আগে কোন lemma লাগে?

  • Substitution lemma
  • Weakening lemma
  • Canonical forms lemma
  • Type-এর অনন্যতা

একটি checker T-IfExpr-কে ঢিলে করে: শর্ত Bool হলে then-শাখার type-ই পুরো if-এর type, else-শাখা যাচাই হয় না। কোন theorem ভাঙে, আর কোন term তা দেখায়?

  • Progress, if false then 1 else false দিয়ে
  • Canonical forms, true দিয়ে
  • Preservation, if true then 1 else 2 দিয়ে
  • Preservation, if false then 1 else false দিয়ে

Haat-এর reference checker নিচের program মেনে নেয়, কিন্তু চালালে 498 ছাপার পর 1:52: runtime error: division by zero আসে। এটি কি soundness-এর বিরোধী? fn share(total: Int, n: Int) -> Int { return total / n; } print(share(996, 2)); print(share(996, 0));

  • হ্যাঁ, checker-এর উচিত ছিল বাতিল করা
  • না, এটি semantics-এ ঘোষিত runtime error, stuck অবস্থা নয়
  • না, কারণ Haat dynamically typed
  • হ্যাঁ, এটি interpreter-এর bug

TypeScript 5.9-এ function parse(j: string): any { return JSON.parse(j); } আর const o: Order = parse('{"total": "936"}'); (যেখানে Order-এর total : number) লিখে o.total + 60 ছাপলে tsc --strict কোনো error দেয় না, আর Node.js ছাপে 93660. কেন?

  • --strict mode কাজ করছে না
  • JSON.parse string-কে সংখ্যায় বদলে দেয়
  • any যাচাই বন্ধ করে, আর চলার সময় কোনো type-যাচাই নেই
  • Node.js TypeScript-এর type ভুল পড়ে

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

  1. Soundness: well-typed বন্ধ term যত ধাপই চলুক, কখনো stuck নয় (value নয় অথচ কোনো নিয়ম খাটে না)। Milner ১৯৭৮-এর স্লোগান, Wright–Felleisen ১৯৯৪-এর syntactic প্রমাণ-ছক।
  2. Progress: ⊢ t : τ হলে t value বা t ⟶ t′; প্রমাণে derivation-এর ওপর induction আর canonical forms (Bool-এর value মানেই true/false).
  3. Preservation: ⊢ t : τ আর t ⟶ t′ হলে ⊢ t′ : τ; প্রতিটি typing rule আর evaluation rule-এর case; function call-এ substitution lemma লাগে।
  4. Test আর প্রমাণ: seeded property test (৩,০০০ term, ৬৪,৭৩৯ ধাপ, ০ ব্যর্থ) ভুল নিয়ম দ্রুত ধরে, কিন্তু প্রমাণের বিকল্প নয়।
  5. সীমা: ঘোষিত runtime error (শূন্য দিয়ে ভাগ), অসীম loop, stack overflow, যুক্তির ভুল soundness-এর বাইরে; TypeScript ইচ্ছা করে unsound, Java চলার সময়ের যাচাইয়ে safe.

পরের পর্বে: পর্ব ৩৯ (উন্নত type — gradual, linear, dependent আর refinement type). Type-হীন আর type-ওয়ালা কোড পাশাপাশি, একবারই ব্যবহারযোগ্য মান, আর type-এর ভেতরে সংখ্যা: যেমন “শূন্য নয় এমন Int”, যা অনুশীলন ২-এর ভাগের সমস্যা type দিয়েই সারায়।

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান