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

Type derivation আর semantics-এর অনুশীলন — typing rule, inference আর Hoare logic

Practice: Type Derivations and Semantics — Typing Rules, Type Inference, Soundness Proofs, Operational and Denotational Semantics, Hoare Logic and Lambda Calculus

Taught in Bangla, this practice page sets 33 questions in seven groups on Haat typing derivations, finding which rule rejects an ill-typed program, Hindley-Milner inference and polymorphism, type soundness with progress and preservation, small-step and big-step semantics, denotational semantics and Hoare logic, and lambda calculus reduction. Each has marks, difficulty and common mark losses, and six flawed derivations or proofs must be corrected. Ten in-page Python (Pyodide) blocks check the answers.

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

  • পর্ব ৩৪-এর নিয়মের নাম দিয়ে Haat expression আর statement-এর derivation tree লেখা, আর ill-typed program-এ ব্যর্থ premise চিহ্নিত করা
  • Unification আর Algorithm W হাতে চালানো: bind, decompose, occurs check, let-এ generalisation
  • Progress আর preservation-এর case-ভিত্তিক প্রমাণ নতুন নিয়ম যোগ হলে বাড়ানো, আর কোন নিয়ম soundness ভাঙে তা দেখানো
  • Small-step ধাপ আর big-step গাছ, denotation আর Kleene approximant, wp আর loop invariant হাতে বের করা
  • β-reduction, α-renaming আর normal বনাম applicative order-এর ধাপ গোনা, আর ভুল derivation-এর ঠিক ভুল লাইনটি খুঁজে পাওয়া

১ · খাতা-কাঠামো — judgment চেনা, নিয়ম বাছা, গাছ লেখা, কোডে মেলানো

জমির রেজিস্ট্রি অফিসে দলিল জমা দিলে কর্মকর্তা প্রতিটি দাগ নম্বর আর খতিয়ান আলাদা করে মেলান; একটি দাগ না মিললে পুরো দলিল আটকে যায়, আর তিনি ঠিক সেই দাগটিই দেখিয়ে দেন। Type আর semantics-এর প্রমাণও এভাবে পড়া হয়: প্রতিটি লাইন কোনো একটি নিয়মের instance কি না, আর premise-গুলো ওপরে প্রমাণিত কি না। নিয়মগুলো শেখানো হয়েছে মডিউল ৬ (পর্ব ৩৩–৩৯) আর মডিউল ৭-এ (পর্ব ৪০–৪৩); এখানে সেগুলো খাতায় লেখার অনুশীলন, নিয়মের নাম হুবহু সেই পর্বগুলোর মতো।

চার ধাপের কাঠামো
judgment-এর আকার চেনা → নিয়মের পরিবার বাছা → নিয়মের নামসহ গাছ বা ধাপ → ছোট উদাহরণে কোডে মেলানো
  1. আকার চেনা: প্রশ্নটি কোন judgment চায়? Γ ⊢ e : τ (typing), τ ≐ τ′ (unification), ⟨S, σ⟩ ⟶ ⟨S′, σ′⟩ বা ⟨S, σ⟩ ⇓ σ′ (operational), ⟦S⟧σ (denotation), {P} S {Q} (Hoare), নাকি “কখনো stuck হয় না”-র মতো সব term-এর ওপর একটি theorem?
  2. পরিবার বাছা: T-… নিয়ম, E-… বা B-… নিয়ম, H-… নিয়ম, নাকি unification-এর bind/decompose. Theorem হলে প্রথম লাইনেই লিখুন কিসের ওপর induction.
  3. লেখা: গাছ হলে গোড়া ওপরে আর premise ভেতরে সরিয়ে (এই পাতার Python block যেভাবে ছাপে), প্রতিটি লাইনের ডানে নিয়মের নাম। প্রমাণ হলে প্রতিটি case আলাদা লাইনে, শেষে ∎.
  4. মেলানো: Haat হলে reference-এর check বা run; বাকি সব ছোট পরিসরে Python দিয়ে। মিলে গেলেও তা প্রমাণ নয়; না মিললে দাবি বা যুক্তি ভুল।

ছবি ৮৫.১ — প্রশ্নের আকার থেকে নিয়মের পরিবার

বাঁয়ে প্রশ্নে যা দেখবেন, ডানে প্রথমে যে নিয়ম বা কৌশল ধরবেন, বন্ধনীতে মূল পর্ব

From the shape of a question to a family of rules Γ ⊢ e : τ ? programবাতিল type লেখানেই ∀α বাS <: T “কখনো stuckনয়” ⟨S, σ⟩ ⟶ ?⟨S, σ⟩ ⇓ ? ⟦S⟧σ ?{P} S {Q} ? (λx. t) s T-… নিয়মে গাছ,পাতায় axiom (৩৪) ব্যর্থ premise আরcheck-এর বার্তা (৫২) constraint, unify,occurs check (৩৫) T-TApp, S-Arrow,S-RcdWidth (৩৬) progress আরpreservation (৩৮) E-… ধাপ বাB-… গাছ (৪০) fix F (৪১); wp আরinvariant (৪২) β, α, normal বনামapplicative (৪৩, ১৯) নিয়মের নাম লিখুন; কোডে মেলান — কোড প্রমাণ নয়

ছবির নীল সারিগুলো type-এর প্রশ্ন, বেগুনি সারিগুলো semantics-এর। নিচের stepper-এ একটি ১০ নম্বরের derivation (প্রশ্ন ২.২) শুরু থেকে শেষ পর্যন্ত গড়া হয়েছে, প্রতিটি ধাপে জমা নম্বরসহ। লক্ষ্য ঠিক হয় নিচ থেকে ওপরে (কোন নিয়ম? তার premise কী?), আর প্রমাণ ফেরে পাতা থেকে গোড়ায়।

Γ = price : (Int, Int) -> Int, name : Str
ধাপ
খাতায় যা লিখলেন
প্রমাণিত judgment
জমা নম্বর
  1. বাইরের গঠন — ১ নম্বর। Haat-এর precedence-এ (পর্ব ৪৮) &&-এর binding power ২০, >=-এর ৪০, !=-এর ৩০, তাই গাছের গোড়ায় &&. ভুল গোড়া বাছলে পুরো গাছই ভুল, তাই নম্বরটি এখানে।
  2. বাঁ শাখা — আরও ১। >=-এর নিয়ম একটিই, T-Cmp; তার দুই premise Int চায়। বাঁ পাশ একটি call, তাই পরের ধাপে T-Call.
  3. T-Call-এর তিন পাতা — আরও ৩। Callee-র type T-Var থেকে, argument দুটি T-Int থেকে; parameter-type আর argument-type হুবহু মেলে (Int, Int), তাই ফলের type Int. প্রমাণিত ৪টি judgment.
  4. বাঁ শাখা শেষ — আরও ১। 1000 : Int T-Int দিয়ে, তারপর T-Cmp-এর সিদ্ধান্ত Bool. এখন ৬টি judgment.
  5. ডান শাখা — আরও ২। T-Eq-এর premise-এ τ আছে, conclusion-এ নেই। τ আন্দাজ করবেন না: বাঁ পাশ name-এর type Str থেকে τ = Str, তারপর ডান পাশ ""-কে Str-এর সঙ্গে মেলান; Str তালিকা {Int, Bool, Str}-এ আছে। মোট ৯টি।
  6. গোড়া — শেষ ২। T-And: ১০টি judgment, ৬টি axiom, উচ্চতা ৪. অংশ ২-এর Python block হুবহু এই গাছ ছাপে, আর reference-এ একই expression ছাপালে সত্যিকারের run-এ আসে true.
প্রশ্নের ধরনআকার ও নিয়ম চেনাগাছ বা মূল ধাপside condition, সব caseউপসংহার
৫ নম্বর১২১১
১০ নম্বর১–২৪৩–৪১
অংশপ্রশ্নের ধরনমূল পর্বপ্রশ্ন
২Haat-এর typing derivation, statement judgment, অনন্যতা৩৪, ৫২২.১–২.৫
৩Ill-typed program: কোন নিয়ম, কোন premise, কোন বার্তা৩৪, ৫১, ৫২৩.১–৩.৫
৪Unification, Algorithm W, let-polymorphism, subtyping৩৫, ৩৬৪.১–৪.৫
৫Stuck term, progress আর preservation বাড়ানো৩৮৫.১–৫.৫
৬Small-step ধাপ, big-step গাছ, determinism৪০৬.১–৬.৫
৭Denotation, Kleene approximant, wp, loop invariant৪১, ৪২৭.১–৭.৪
৮Substitution, β-reduction, reduction-এর ক্রম, STLC৪৩, ১৯৮.১–৮.৪
৯ভুল derivation আর প্রমাণ ধরা৩৪–৪৩৯.১–৯.৬

এই পাতার কোনো প্রশ্ন কোনো নির্দিষ্ট পরীক্ষা, বিশ্ববিদ্যালয় বা প্রতিষ্ঠান থেকে নেওয়া নয়; এ ধরনের derivation আর প্রমাণ Programming Languages আর Compiler Design কোর্সে, চাকরির লিখিত পরীক্ষায় আর গবেষণামুখী ইন্টারভিউতে প্রায়ই আসে। নম্বর-ভাগ শুধু অনুশীলনের জন্য। প্রতিটি প্রশ্ন আগে নিজে লিখুন, তারপর খুলে মেলান। এই মডিউলের অন্য পর্বগুলো: পর্ব ৮২ (compiler-এর সমস্যা: three-address code, SSA, register allocation), পর্ব ৮৩ (MCQ), পর্ব ৮৪ (লিখিত ও ভাইভা) আর পর্ব ৮৬ (ইন্টারভিউ)।

২ · অংশ ক — Haat-এর typing derivation

ঝালিয়ে নিন: পর্ব ৩৪ · Typing rule আর type judgment (T-Int থেকে T-FnDecl পর্যন্ত সব নিয়ম, typing judgment Γ ⊢ e : τ আর statement-এর Γ ⊢ρ s ⇒ Γ′), পর্ব ৫২ · Type checker বাস্তবায়ন. এই দলের উত্তরে গাছ লেখা হয়েছে গোড়া ওপরে, premise দুই ঘর ভেতরে, প্রতিটি লাইনের ডানে নিয়ম; দাগ-টানা রূপে লিখলেও একই নম্বর।

২.১Γ = qty : Int, unit : Int. Γ ⊢ qty * unit >= 1000 : Bool-এর derivation tree লিখুন; judgment, axiom আর গাছের উচ্চতা গুনুন। — ৫ নম্বর (সহজ)
Γ ⊢ qty * unit >= 1000 : Bool     [T-Cmp, ⊕ = >=]
  Γ ⊢ qty * unit : Int            [T-Arith, ⊕ = *]
    Γ ⊢ qty : Int                 [T-Var]
    Γ ⊢ unit : Int                [T-Var]
  Γ ⊢ 1000 : Int                  [T-Int]

৫টি judgment, তার ৩টি axiom (দুটি T-Var, একটি T-Int), উচ্চতা ৩. নম্বর-ভাগ: গোড়ায় T-Cmp (১), T-Arith আর তার ⊕ (১), পাতা (১), side condition “(qty : Int) ∈ Γ” (১), গোনা (১)। যেখানে নম্বর কাটে: গাছ qty * (unit >= 1000) ধরে আঁকা; *-এর binding power ৬০, >=-এর ৪০, তাই গুণ আগে বাঁধে।

২.২Γ = price : (Int, Int) -> Int, name : Str. Γ ⊢ price(2, 520) >= 1000 && name != "" : Bool-এর derivation লিখুন। T-Eq-এর τ কোথা থেকে আসে, ব্যাখ্যা করুন। — ১০ নম্বর (মাঝারি)
Γ ⊢ price(2, 520) >= 1000 && name != "" : Bool   [T-And]
  Γ ⊢ price(2, 520) >= 1000 : Bool               [T-Cmp]
    Γ ⊢ price(2, 520) : Int                      [T-Call]
      Γ ⊢ price : (Int, Int) -> Int              [T-Var]
      Γ ⊢ 2 : Int                                [T-Int]
      Γ ⊢ 520 : Int                              [T-Int]
    Γ ⊢ 1000 : Int                               [T-Int]
  Γ ⊢ name != "" : Bool                          [T-Eq, τ = Str]
    Γ ⊢ name : Str                               [T-Var]
    Γ ⊢ "" : Str                                 [T-Str]

১০টি judgment, ৬টি axiom, উচ্চতা ৪ (ধাপগুলো অংশ ১-এর stepper-এ)। T-Eq-এর premise-এ τ আছে কিন্তু conclusion-এ নেই, তাই নিয়ম পড়ে মনে হয় τ আন্দাজ করতে হবে। Checker আন্দাজ করে না: বাঁ পাশের type বের করে সেটিকেই τ ধরে, আর side condition τ ∈ {Int, Bool, Str} দেখে (syntax-directed পড়া, পর্ব ৩৪-এর অংশ ৪)। সত্যিকারের run: এই expression print করা একটি ছোট program reference-এ check-এ ok, আর run-এ true. যেখানে নম্বর কাটে: T-Call-এ argument-এর সংখ্যা মেলানোর কথা না লেখা; T-Eq-এ τ-এর তালিকার শর্ত বাদ দেওয়া।

২.৩fn delivery(total: Int) -> Int { if total >= 1000 { return 0; } else { return 60; } }. Statement judgment Γ ⊢ρ s ⇒ Γ′ দিয়ে দেখান যে ঘোষণাটি well-typed; প্রতিটি ধাপে Γ আর ρ লিখুন। else অংশটি মুছে দিলে কোন premise ব্যর্থ হয়? — ১০ নম্বর (মাঝারি)
  1. Top-level function hoisted (সিদ্ধান্ত ১৭), তাই শুরুর context Γ0 = delivery : (Int) -> Int; top level-এ ρ নেই। — hoisting
  2. T-FnDecl: দেহ যাচাই হয় Γ1 = Γ0, total : Int-এ, ρ = Int (লেখা ফেরত-type থেকে)। — T-FnDecl-এর দ্বিতীয় premise
  3. শর্ত: Γ1 ⊢ total >= 1000 : Bool (T-Cmp, তার নিচে T-Var আর T-Int). — T-If-এর প্রথম premise
  4. দুই শাখা: Γ1 ⊢ 0 : Int আর Γ1 ⊢ 60 : Int, দুটিই = ρ, তাই দুটি T-Return; block-এর ভেতরে কিছু যোগ হয়নি, আর T-If ফেরত দেয় Γ1. — T-Return, T-If
  5. তৃতীয় premise returns(body): দেহে একটি if আছে যার else আছে আর দুই শাখাই return করে, তাই সত্য (সিদ্ধান্ত ২১)। T-FnDecl-এর সব premise পূর্ণ; বাইরে context আবার Γ0. ∎

else মুছলে: T-If তখনও খাটে (else ঐচ্ছিক), type-এর কোনো নিয়ম ব্যর্থ হয় না; ব্যর্থ হয় শুধু returns(body), কারণ else-ছাড়া if গোনা হয় না। Reference-এর সত্যিকারের run, অবস্থান function-এর নামে (সিদ্ধান্ত ২১):

1:4: error: missing return: not every path of function 'delivery' returns Int

নম্বর-ভাগ: Γ0 আর hoisting (২), Γ1 আর ρ (২), শর্ত আর দুই T-Return (৩), returns(body) (২), উপসংহার (১)। যেখানে নম্বর কাটে: ρ-কে Γ-এর অংশ ভাবা, বা returns(body)-কে একটি typing rule বলা; এটি type ছাড়া একটি syntactic শর্ত।

২.৪fn add_d(d: Int) -> (Int) -> Int { return fn(t: Int) -> Int { return t + d; }; }. দেখান add_d : (Int) -> (Int) -> Int, আর Γ ⊢ add_d(60)(936) : Int-এর গাছ লিখুন। — ১০ নম্বর (কঠিন)
  1. T-FnDecl: Γ′ = add_d : (Int) -> (Int) -> Int; দেহ যাচাই Γ′, d : Int-এ, ρ = (Int) -> Int. — লেখা annotation থেকে
  2. return fn(t: Int) -> Int {…};: T-Return চায় ভেতরের function-এর type = ρ. T-Fn: তার দেহ যাচাই হয় Γ′, d : Int, t : Int-এ, R = Int. — T-Return, T-Fn
  3. ভেতরের দেহ return t + d;: T-Add, দুই premise T-Var (t : Int, d : Int), ফল Int = R; returns সত্য। তাই T-Fn দেয় (Int) -> Int = ρ ✓. d এখানে free, তাই চলার সময় এটি একটি closure (পর্ব ১৭)। — T-Add, T-Var
  4. Call: f(1)(2) মানে (f(1))(2), call বাঁ দিকে জোড়া লাগে (binding power ৮০)।
Γ ⊢ add_d(60)(936) : Int                  [T-Call]
  Γ ⊢ add_d(60) : (Int) -> Int            [T-Call]
    Γ ⊢ add_d : (Int) -> (Int) -> Int     [T-Var]
    Γ ⊢ 60 : Int                          [T-Int]
  Γ ⊢ 936 : Int                           [T-Int]

সত্যিকারের run (reference, CPython 3.14.4): run-এ 996. Type-টি সরাসরি যাচাই করতে একই file-এ let ok: (Int) -> (Int) -> Int = add_d; লেখা হলো (গৃহীত), সঙ্গে দুটি ভুল annotation; check-এর বার্তা:

5:23: error: type mismatch: expected (Int) -> Int, found (Int) -> (Int) -> Int
6:14: error: type mismatch: expected Int, found (Int) -> Int

যেখানে নম্বর কাটে: ভেতরের function-এর দেহ বাইরের ρ দিয়ে যাচাই করা; দেহের judgment-এ সবসময় নিজের R.

২.৫প্রমাণ করুন: Haat-এ Γ ⊢ e : τ1 আর Γ ⊢ e : τ2 হলে τ1 = τ2; শুধু e = e1 + e2 আর e = f(e1, …, en) case দুটি লিখুন। তারপর দেখান “Γ ⊢ e : Bool হলে Γ ⊢ e : Int” নিয়ম যোগ করলে theorem ভাঙে। — ১০ নম্বর (কঠিন)

e-এর গঠনের ওপর structural induction; IH: প্রতিটি অংশ-expression-এর জন্য যেকোনো context-এ theorem সত্য। দুটি derivation D1, D2-এর শেষ নিয়ম দেখি।

  1. e = e1 + e2. দুটিই T-Add হলে τ1 = τ2 = Int; দুটিই T-Concat হলে Str. মিশ্র হলে D1-এ Γ ⊢ e1 : Int আর D2-এ Γ ⊢ e1 : Str; e1-এ IH দেয় Int = Str, অসম্ভব। — IH on e1
  2. e = f(e1, …, en). নিয়ম একটিই, T-Call. D1-এ Γ ⊢ f : σ1, D2-এ Γ ⊢ f : σ2; f-এ IH দেয় σ1 = σ2, আর τi হলো σi-এর ফল-অংশ, তাই τ1 = τ2. ∎ (বাকি case পর্ব ৩৪-এর Theorem ৩৪.১-এ)

Coercion-নিয়মে: true-এর T-Bool দিয়ে Bool, আর নতুন নিয়মে Int: একটি expression, দুটি type. প্রমাণের যে জায়গা ভাঙে: “প্রতিটি গঠনের একটিই নিয়ম” আর নেই, কারণ নতুন নিয়মের conclusion-এ e যেকোনো গঠনের। পর্ব ৩৪-এর গণনা-পরীক্ষায় তিন স্তর পর্যন্ত ১০,৯৮৬টি expression-এ নিয়মটি যোগ করতেই ১,৩৭০টির দুটি type পাওয়া গিয়েছিল। যেখানে নম্বর কাটে: মিশ্র case বাদ দেওয়া; IH কোন অংশে খাটানো হলো তা না লেখা।

LIT = {"int": ("Int", "T-Int"), "str": ("Str", "T-Str"), "bool": ("Bool", "T-Bool")}
def show(t): return t if isinstance(t, str) else f"({', '.join(t[0])}) -> {t[1]}"
def src(e):
    if e[0] == "bin": return f"{src(e[2])} {e[1]} {src(e[3])}"
    if e[0] == "call": return f"{e[1][1]}({', '.join(map(src, e[2]))})"
    return f'"{e[1]}"' if e[0] == "str" else str(e[1]).lower()
def rule(op, lt):                 # (নিয়ম, operand-এর চাওয়া type, ফলের type)
    if op == "+": return ("T-Concat", "Str", "Str") if lt == "Str" else ("T-Add", "Int", "Int")
    if op in ("==", "!="): return ("T-Eq", lt, "Bool")        # বাঁ পাশই τ ঠিক করে
    if op in ("&&", "||"): return ("T-And" if op == "&&" else "T-Or", "Bool", "Bool")
    return ("T-Cmp", "Int", "Bool") if op in "< <= > >=".split() else ("T-Arith", "Int", "Int")
def derive(G, e):                 # ফেরত (e, type বা None, নিয়ম, premise-গুলো)
    if e[0] in LIT: return (e, *LIT[e[0]], [])
    if e[0] == "var": return (e, G[e[1]], "T-Var", [])
    if e[0] == "call":
        f, args = derive(G, e[1]), [derive(G, a) for a in e[2]]
        bad = [f"expected {w}, found {a[1]}" for a, w in zip(args, f[1][0]) if a[1] != w]
        return (e, None if bad else f[1][1], "✗ T-Call: " + bad[0] if bad else "T-Call", [f, *args])
    l, r = derive(G, e[2]), derive(G, e[3]); name, want, out = rule(e[1], l[1])
    bad = [show(x[1]) for x in (l, r) if x[1] != want]
    return (e, None if bad else out, f"✗ {name}: expected {want}, found {bad[0]}" if bad else name, [l, r])
def tree(d, pad=""):              # ছাপে, আর ফেরত দেয় (judgment, axiom, উচ্চতা)
    e, t, r, kids = d; print(f"{pad}Γ ⊢ {src(e)} : {show(t) if t else '?'}   [{r}]")
    s = [tree(k, pad + "  ") for k in kids]
    return 1 + sum(x[0] for x in s), (not kids) + sum(x[1] for x in s), 1 + max([x[2] for x in s], default=0)
V, I, B = (lambda x: ("var", x)), (lambda n: ("int", n)), (lambda o, l, r: ("bin", o, l, r))
G = {"qty": "Int", "unit": "Int", "name": "Str", "price": (("Int", "Int"), "Int")}
for e in [B(">=", B("*", V("qty"), V("unit")), I(1000)), B("==", I(1), ("bool", True)),
          B("&&", B(">=", ("call", V("price"), [I(2), I(520)]), I(1000)), B("!=", V("name"), ("str", "")))]:
    print("judgment, axiom, উচ্চতা =", tree(derive(G, e)))

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

Γ ⊢ qty * unit >= 1000 : Bool   [T-Cmp]
  Γ ⊢ qty * unit : Int   [T-Arith]
    Γ ⊢ qty : Int   [T-Var]
    Γ ⊢ unit : Int   [T-Var]
  Γ ⊢ 1000 : Int   [T-Int]
judgment, axiom, উচ্চতা = (5, 3, 3)
Γ ⊢ 1 == true : ?   [✗ T-Eq: expected Int, found Bool]
  Γ ⊢ 1 : Int   [T-Int]
  Γ ⊢ true : Bool   [T-Bool]
judgment, axiom, উচ্চতা = (3, 2, 2)
Γ ⊢ price(2, 520) >= 1000 && name != "" : Bool   [T-And]
  Γ ⊢ price(2, 520) >= 1000 : Bool   [T-Cmp]
    Γ ⊢ price(2, 520) : Int   [T-Call]
      Γ ⊢ price : (Int, Int) -> Int   [T-Var]
      Γ ⊢ 2 : Int   [T-Int]
      Γ ⊢ 520 : Int   [T-Int]
    Γ ⊢ 1000 : Int   [T-Int]
  Γ ⊢ name != "" : Bool   [T-Eq]
    Γ ⊢ name : Str   [T-Var]
    Γ ⊢ "" : Str   [T-Str]
judgment, axiom, উচ্চতা = (10, 6, 4)

প্রথম গাছ ২.১-এর উত্তর (৫, ৩, ৩), তৃতীয়টি ২.২-এর (১০, ৬, ৪)। মাঝের গাছ 1 == true: বাঁ পাশ Int বলে τ = Int, আর ডান পাশ Bool মেলে না; গোড়ায় type নেই (?)। এই ভুলটি প্রশ্ন ৩.৪ আর ৯.১-এ আবার আসবে। derive()-এর প্রতিটি শাখা একটি নিয়ম, পর্ব ৩৪-এর block-এর সংক্ষিপ্ত রূপ; পূর্ণ রূপ reference-এর typechecker.py.

৩ · অংশ খ — Ill-typed program: কোন নিয়মে, কোন premise-এ আটকায়

ঝালিয়ে নিন: পর্ব ৩৪-এর “যেখানে derivation আটকে যায়”, পর্ব ৫১ · Symbol table আর name resolution (নামের ভুল type-এর আগেই ধরা পড়ে), পর্ব ৫২. প্রতিটি উত্তরে তিনটি জিনিস: কোন নিয়ম বাছা হলো, তার কোন premise বা side condition ব্যর্থ, আর reference-এর বার্তা ও অবস্থান। সব বার্তা reference implementation-এর python -B haat.py check-এর সত্যিকারের run (CPython 3.14.4).

৩.১লাইন ১: let d = 60; লাইন ২: print(d + " টাকা");. কোন নিয়ম বাছা হয়, কোন premise ব্যর্থ, আর বার্তা কোন অবস্থানে আসে? — ৫ নম্বর (সহজ)
  1. +-এর নিয়ম দুটি, T-Add আর T-Concat; বাঁ পাশ ঠিক করে কোনটি (সিদ্ধান্ত ১১)। Γ(d) = Int, তাই T-Add.
  2. T-Add-এর দ্বিতীয় premise Γ ⊢ " টাকা" : Int; কিন্তু T-Str দেয় Str, আর Str থেকে Int-এর কোনো নিয়ম নেই (implicit conversion নেই)।
  3. বার্তা ব্যর্থ expression-এর শুরুতে, অর্থাৎ string-এর উদ্ধৃতিচিহ্নে (সিদ্ধান্ত ২৪): 2:11: error: type mismatch: expected Int, found Str.

উল্টোটি, print(name + 1); যেখানে name : Str: এবার T-Concat বাছা হয়, বার্তা expected Str, found Int. যেখানে নম্বর কাটে: “T-Add আর T-Concat দুটিই ব্যর্থ” লেখা; checker একটিই বাছে, তাই বার্তাও একটি।

৩.২লাইন ১: var total = 936; লাইন ২: if total { print(total); }. ব্যর্থ নিয়ম আর বার্তা লিখুন। C-তে একই গঠন কেন চলে? — ৫ নম্বর (সহজ)

T-If-এর প্রথম premise Γ ⊢ total : Bool; T-Var দেয় Γ(total) = Int. বার্তা শর্তের শুরুতে: 2:4: error: type mismatch: expected Bool, found Int. C-তে (C17) if-এর শর্ত যেকোনো scalar হতে পারে আর অশূন্য মানেই সত্য; অর্থাৎ C-র নিয়মে শর্তের premise “scalar type”, Haat-এর মতো “Bool” নয়। একই গঠন, আলাদা নিয়ম, তাই ভাষার নাম না বলে “if-এ int চলে” লেখা ভুল। যেখানে নম্বর কাটে: ব্যর্থতাকে T-Print-এ দেখানো; ভেতরের print(total) নিজে ঠিক আছে।

৩.৩লাইন ১: fn apply(f: (Int) -> Int, x: Int) -> Int { return f(x); } লাইন ২: print(apply(fn(x: Int) -> Bool { return x > 0; }, 5));. আর আলাদা একটি program-এ fn total(qty: Int) -> Int { return qty * 520; } তারপর print(total(2, 60)); print(-true); print(!total(1));. প্রতিটি ভুলের নিয়ম আর বার্তা লিখুন। — ১০ নম্বর (মাঝারি)
  1. apply: T-Call চায় প্রতিটি argument-এর type হুবহু parameter-এর τi. প্রথম argument-এর type, T-Fn দিয়ে, (Int) -> Bool; চাওয়া (Int) -> Int. Haat v1-এ subtyping নেই, তাই function type-এর মিল পুরোপুরি সমতা। বার্তা argument-এর শুরুতে, fn-এ: 2:13: error: type mismatch: expected (Int) -> Int, found (Int) -> Bool.
  2. total(2, 60): T-Call-এর conclusion-এ argument-সংখ্যা n আর callee-র parameter-সংখ্যা একই n; দুইয়ের সঙ্গে মেলে এমন কোনো instance নেই। বার্তা callee-র শুরুতে (সিদ্ধান্ত ২৪)।
  3. -true: T-Neg-এর premise Γ ⊢ e : Int, পাওয়া Bool. !total(1): T-Not চায় Bool, পাওয়া Int.

Type checker সব ভুল জানায়, অবস্থান অনুযায়ী সাজিয়ে (সিদ্ধান্ত ২); দ্বিতীয় program-এর সত্যিকারের run:

2:7: error: expected 1 argument, found 2
3:8: error: type mismatch: expected Int, found Bool
4:8: error: type mismatch: expected Bool, found Int

যেখানে নম্বর কাটে: apply-এর ভুলকে “ফেরত type ভুল” বলা; ভুলটি argument-এর premise-এ, ফেরত type-এ নয়।

৩.৪তিনটি আলাদা program: (ক) print("a" < "b"); (খ) let paid = 1 == true; (গ) fn log() { print("ok"); } let u = log(); print(u == u);. প্রতিটিতে কয়টি বার্তা, কোন নিয়মের কোন অংশ ব্যর্থ? — ১০ নম্বর (মাঝারি)
  1. (ক) T-Cmp-এর দুই premise-ই Int চায়, দুটিই Str. সিদ্ধান্ত ১১: প্রতিটি ভুল operand আলাদা জানানো হয়, তাই দুটি বার্তা: 1:7: … expected Int, found Str আর 1:13: … expected Int, found Str. Haat-এ Str-এর ক্রম-তুলনা নেই।
  2. (খ) T-Eq: বাঁ পাশ 1 থেকে τ = Int; ডান পাশ Bool ≠ τ. একটি বার্তা, ডান operand-এ: 1:17: error: type mismatch: expected Int, found Bool.
  3. (গ) let u = log(); বৈধ, কারণ T-Let-এ τ-এর কোনো বাধা নেই (সিদ্ধান্ত ২২)। T-Eq-এর দুই premise মেলে (Unit, Unit), কিন্তু side condition τ ∈ {Int, Bool, Str} ভাঙে: 3:7: error: operator '==' cannot compare values of type Unit.

নম্বর-ভাগ: প্রতিটি অংশে নিয়ম (১), ব্যর্থ অংশ (১), বার্তার সংখ্যা ও অবস্থান (১), আর premise বনাম side condition-এর পার্থক্য বলা (১)। যেখানে নম্বর কাটে: (গ)-তে let লাইনকে ভুল বলা।

৩.৫এই দুটি program বাতিল হয়, কিন্তু কোনো typing rule ব্যর্থ হয় না। কোন যাচাই এগুলো ধরে, আর কেন? (ক) fn half(n: Int) -> Int { while n > 0 { return n / 2; } } (খ) let k = 5; k = 6; — ৫ নম্বর (মাঝারি)

(ক) দেহের প্রতিটি expression আর return-এর type ঠিক (T-Cmp, T-Arith, T-Return সব খাটে)। ব্যর্থ হয় T-FnDecl-এর তৃতীয় premise returns(body): সিদ্ধান্ত ২১-এ while কখনো গোনা হয় না, কারণ শর্ত প্রথমবারেই মিথ্যা হতে পারে (n = 0). বার্তা: 1:4: error: missing return: not every path of function 'half' returns Int. (খ) T-Assign-এর side condition “x একটি var”; বাস্তবে এটি resolver ধরে (সিদ্ধান্ত ১৯), type checker চলার আগেই: 2:1: error: cannot assign to 'k': it is declared with 'let'. দুটিই সত্যিকারের run. যেখানে নম্বর কাটে: (ক)-কে “type mismatch” বলা।

৪ · অংশ গ — Hindley–Milner আর polymorphism

ঝালিয়ে নিন: পর্ব ৩৫ · Type inference (unification-এর delete, decompose, clash, swap, bind আর occurs check; Algorithm W; let-polymorphism), পর্ব ৩৬ · Polymorphism (T-TAbs, T-TApp, subsumption, S-Arrow), পর্ব ১০ (term-এর unification). চিহ্ন: t1, t2 … type variable; চূড়ান্ত উত্তরে নাম বদলে a, b, c. পাতার block দুটি পর্ব ৩৫-এর unify আর W, অপরিবর্তিত।

৪.১হাতে unify করুন, প্রতিটি bind লিখে: (ক) {t1 ≐ (t2) → t3, t2 ≐ Int, t1 ≐ (Int) → t4} (খ) {(t1) → t1 ≐ (Int) → Bool} (গ) {t2 ≐ (t1) → t2}. — ৫ নম্বর (সহজ)
  1. (ক) bind t1 := (t2) → t3 (occurs check পার)। bind t2 := Int. তৃতীয়টিতে t1 walk করে (Int) → t3; decompose: Int ≐ Int (delete), t3 ≐ t4, bind t3 := t4. MGU: t1 = (Int) → t4, t2 = Int, t3 = t4.
  2. (খ) decompose: t1 ≐ Int, bind; তারপর t1 ≐ Bool, walk করে Int ≐ Bool: clash.
  3. (গ) t2 নিজেই ডান পাশের ভেতরে: occurs check ব্যর্থ; কোনো সসীম type সমাধান নয়।

যেখানে নম্বর কাটে: (ক)-তে t4-কে Int ধরে ফেলা; MGU-তে t4 মুক্ত থাকে, আর সেটিই “সবচেয়ে সাধারণ”। (খ)-তে বাঁ পাশের দুই t1-কে আলাদা variable ভাবা।

৪.২Algorithm W হাতে চালান: λf. λg. λx. g (f x) x. প্রতিটি নতুন variable, constraint আর bind লিখে principal type বের করুন। — ১০ নম্বর (মাঝারি)

নিচের stepper-এ ধাপগুলো; লেখার রূপ:

  1. f : t1, g : t2, x : t3 (তিনটি λ, প্রতিটিতে নতুন variable). — W-এর λ নিয়ম
  2. f x: ফলের জন্য t4; unify t1 ≐ (t3) → t4 ⇒ bind t1 := (t3) → t4.
  3. g (f x): ফল t5; unify t2 ≐ (t4) → t5 ⇒ bind t2 := (t4) → t5.
  4. (g (f x)) x: application বাঁ দিকে জোড়া লাগে; ফল t6; unify t5 ≐ (t3) → t6 ⇒ bind t5 := (t3) → t6.
  5. Apply: (t3 → t4) → (t4 → t3 → t6) → t3 → t6; নাম বদলে (a → b) → (b → a → c) → a → c. মোট ৩টি bind, কোনো clash নেই। ∎

নম্বর-ভাগ: variable বরাদ্দ (১), তিনটি constraint (৩), bind আর walk (৩), apply ও নাম বদল (২), উপসংহার (১)। যেখানে নম্বর কাটে: g (f x) x-কে g ((f x) x) পড়া; তাহলে f দুই argument নিত, উত্তরও আলাদা।

engine-এর খাতা
এখন
constraint
S
type
  1. Parameter. তিনটি λ, তাই f : t1, g : t2, x : t3, সবাই Γ-তে, কোনো ∀ নেই (λ-তে বাঁধা নাম generalise হয় না)। দেহ g (f x) x = (g (f x)) x.
  2. ভেতরের call. W আগে বাঁ দিক দেখে, তাই প্রথমে g, তারপর argument f x: callee t1, argument t3, নতুন ফল t4. Constraint t1 ≐ (t3) → t4; t1 মুক্ত, occurs check পার, bind.
  3. g-এর call. Callee t2, argument-এর type t4, নতুন ফল t5: t2 ≐ (t4) → t5, আবার সরাসরি bind.
  4. বাইরের call. এবার callee g (f x), যার type t5, argument x : t3, ফল t6. t5 এখনো মুক্ত, তাই bind t5 := (t3) → t6. পুরো W-তে একবারও decompose লাগেনি।
  5. Apply. শিকল ধরে: t1 = t3 → t4, t2 = t4 → t5 = t4 → t3 → t6. Function-এর type t1 → t2 → t3 → t6-তে বসালে ডানের type. → ডান দিকে জোড়া লাগে, তাই t4 → (t3 → t6) বন্ধনী ছাড়া লেখা যায়।
  6. নাম বদল. প্রথম দেখা ক্রমে t3 = a, t4 = b, t6 = c: (a → b) → (b → a → c) → a → c. পাতার Python block-ও ঠিক এই উত্তর আর ৩টি bind ছাপে।
৪.৩let i = λx. x in i i 1-এর type বের করুন। তারপর দেখান λi. i i 1 কেন type পায় না, যদিও “let x = e1 in e2 মানে (λx. e2) e1”. — ১০ নম্বর (মাঝারি)
  1. W(λx. x) = t1 → t1. Γ খালি, তাই gen দেয় i : ∀t1. t1 → t1 (generalisation). — T-Let
  2. i i: দুই ব্যবহারে দুটি নতুন instance, t2 → t2 আর t3 → t3; ফল t4. unify (t2 → t2) ≐ ((t3 → t3) → t4): bind t2 := t3 → t3, তারপর bind t4 := t3 → t3.
  3. (i i) 1: ফল t5; unify t4 ≐ (Int → t5), walk করে (t3 → t3) ≐ (Int → t5): bind t3 := Int, t5 := Int. Type Int, মোট ৪টি bind. ∎
  4. λi. i i 1: i : t1, একটিই type, ∀ নেই। i i চায় t1 ≐ (t1) → t2: occurs check ব্যর্থ।

দুটি program-এর অর্থ এক, কিন্তু HM শুধু let-এ generalise করে, কারণ let-এ e1 জানা, আর λ-এর parameter-এ কোন function আসবে তা জানা নেই। যেখানে নম্বর কাটে: দুই ব্যবহারে একই instance নেওয়া; তাহলে let-এও occurs check হতো।

৪.৪কোনটির type আছে? থাকলে principal type দিন, না থাকলে কোন নিয়মে ব্যর্থ: (ক) λx. if x then x else 1 (খ) λx. λf. f (f x). — ৫ নম্বর (মাঝারি)

(ক) x : t1; শর্ত বলে t1 ≐ Bool (bind); দুই শাখা একই type চায়: t1 ≐ Int, walk করে Bool ≐ Int: clash, type নেই। (খ) x : t1, f : t2; f x: t2 ≐ (t1) → t3; f (f x): t2 ≐ (t3) → t4, walk করে decompose: t1 ≐ t3, t3 ≐ t4. উত্তর a → (a → a) → a, অর্থাৎ a -> (a -> a) -> a, ৩টি bind. যেখানে নম্বর কাটে: (খ)-তে f-কে (a → b) ধরে থামা; দুবার প্রয়োগই input আর output-কে এক করে।

৪.৫(ক) first : ∀α. (α, α) -> α. T-TApp দিয়ে first[Str] আর first[(Int) -> Int]-এর type দিন। (খ) Member = {name: Str, points: Int}, Customer = {name: Str} (Haat-এর বর্ধিত রূপ)। (Customer) -> Int <: (Member) -> Int কি সত্য? উল্টোটি? দুটির derivation বা ব্যর্থতা লিখুন। — ১০ নম্বর (কঠিন)
  1. (ক) T-TApp: [α ↦ σ]τ. first[Str] : (Str, Str) -> Str. first[(Int) -> Int] : ((Int) -> Int, (Int) -> Int) -> (Int) -> Int; α-র প্রতিটি জায়গায় পুরো function type বসে।
  2. (খ) S-Arrow: (S1) -> S2 <: (T1) -> T2 যদি T1 <: S1 (parameter উল্টো দিকে, contravariance) আর S2 <: T2. এখানে লাগে Member <: Customer: S-RcdWidth দিয়ে সত্য (বাড়তি field points বাদ দেওয়া যায়); আর Int <: Int, S-Refl. তাই সত্য: যে function যেকোনো Customer নেয়, সে Member-ও নিতে পারে।
  3. উল্টোটি চায় Customer <: Member; Customer-এ points নেই, কোনো নিয়ম খাটে না: মিথ্যা. ∎

লেখকের lab-এ একটি ছোট subtype checker (S-Refl, record width/depth, S-Arrow) আর একটি substitution function দিয়ে চালানো (CPython 3.14.4): প্রথমটি True, দ্বিতীয়টি False, আর দুটি instance ওপরের মতোই। যেখানে নম্বর কাটে: parameter-এর দিক covariant ধরা।

INT, BOOL, isvar, fn = "Int", "Bool", (lambda t: isinstance(t, str) and t[0].islower()), (lambda *ts: ("->",) + ts)
def show(t):
    if isinstance(t, str): return t
    *ps, r = t[1:]
    if len(ps) > 1: return "(" + ", ".join(map(show, ps)) + ") -> " + show(r)
    return (f"({show(ps[0])})" if isinstance(ps[0], tuple) else ps[0]) + " -> " + show(r)
def walk(t, S): return walk(S[t], S) if isvar(t) and t in S else t
def apply(t, S):
    t = walk(t, S); return (t[0],) + tuple(apply(x, S) for x in t[1:]) if isinstance(t, tuple) else t
def occurs(v, t, S):
    t = walk(t, S); return t == v if isinstance(t, str) else any(occurs(v, x, S) for x in t[1:])
def unify(a, b, S, log):
    a, b = walk(a, S), walk(b, S)
    if a == b: return S                                        # delete
    if isvar(b) and not isvar(a): a, b = b, a                  # swap
    if isvar(a):
        if occurs(a, b, S): raise TypeError(f"occurs check: {a} occurs in {show(apply(b, S))}")
        log.append(f"  bind {a} := {show(apply(b, S))}"); return {**S, a: b}      # bind
    if isinstance(a, str) or isinstance(b, str) or len(a) != len(b):    # clash
        raise TypeError(f"cannot unify {show(apply(a, S))} with {show(apply(b, S))}")
    for x, y in zip(a[1:], b[1:]): S = unify(x, y, S, log)     # decompose
    return S
for C in ([("t1", fn("t2", "t3")), ("t2", INT), ("t1", fn(INT, "t4"))],      # ৪.১ (ক)
          [(fn("t1", "t1"), fn(INT, BOOL))], [("t2", fn("t1", "t2"))]):      # ৪.১ (খ), (গ)
    S, log = {}, []
    try:
        for l, r in C: log.append(f"solve {show(apply(l, S))} = {show(apply(r, S))}"); S = unify(l, r, S, log)
        log.append("answer: " + ", ".join(f"{v} = {show(apply(v, S))}" for v in sorted(S)))
    except TypeError as e: log.append(f"  error: {e}")
    print("\n".join(log))

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

solve t1 = t2 -> t3
  bind t1 := t2 -> t3
solve t2 = Int
  bind t2 := Int
solve Int -> t3 = Int -> t4
  bind t3 := t4
answer: t1 = Int -> t4, t2 = Int, t3 = t4
solve t1 -> t1 = Int -> Bool
  bind t1 := Int
  error: cannot unify Int with Bool
solve t2 = t1 -> t2
  error: occurs check: t2 occurs in t1 -> t2

প্রথম সাত লাইন ৪.১ (ক): তিনটি bind আর MGU. তারপর (খ): একটি bind-এর পরে clash, আর (গ): occurs check. এক parameter-এর function type এখানে ML-এর ধাঁচে t2 -> t3 ছাপা হয়; Haat-এ একই type (t2) -> t3.

import itertools                  # আগের block-এর walk, apply, unify, show কাজে লাগে
def fresh(): return f"t{next(ctr)}"
def ftv(t): return {t} if isvar(t) else set() if isinstance(t, str) else set().union(*map(ftv, t[1:]))
def inst(vs, t): return apply(t, {v: fresh() for v in vs})      # ∀-variable-এর নতুন কপি
def W(env, e, S, log):            # env: নাম -> (∀-variable, type); ফেরত (type, S)
    k = e[0]
    if k in ("int", "bool"): return (INT if k == "int" else BOOL), S
    if k == "var": return inst(*env[e[1]]), S
    if k == "lam": a = fresh(); t, S = W({**env, e[1]: ([], a)}, e[2], S, log); return fn(a, t), S
    if k == "app":
        tf, S = W(env, e[1], S, log); ta, S = W(env, e[2], S, log); r = fresh()
        return r, unify(tf, fn(ta, r), S, log)
    if k == "if":
        tc, S = W(env, e[1], S, log); S = unify(tc, BOOL, S, log)
        t1, S = W(env, e[2], S, log); t2, S = W(env, e[3], S, log); return t1, unify(t1, t2, S, log)
    t, S = W(env, e[2], S, log); t = apply(t, S)                 # "let": generalise
    busy = set().union(*(ftv(apply(ty, S)) - set(vs) for vs, ty in env.values()))
    return W({**env, e[1]: (sorted(ftv(t) - busy), t)}, e[3], S, log)
def infer(e):
    global ctr; ctr = itertools.count(1); m = {}
    def nice(t): return m.setdefault(t, "abcdef"[len(m)]) if isvar(t) else t if isinstance(t, str) else (t[0],) + tuple(map(nice, t[1:]))
    try: log = []; t, S = W({}, e, {}, log); return show(nice(apply(t, S))) + f"   ({len(log)}টি bind)"
    except TypeError as err: return f"error: {err}"
def L(*xs, body): return body if not xs else ("lam", xs[0], L(*xs[1:], body=body))
def A(f, *args): return f if not args else A(("app", f, args[0]), *args[1:])
V = lambda x: ("var", x); f, g, x, i = map(V, "fgxi"); ii1 = A(A(i, i), ("int", 1))
for name, e in [("4.2  λf.λg.λx. g (f x) x", L("f", "g", "x", body=A(g, A(f, x), x))),
                ("4.3  let i = λx.x in i i 1", ("let", "i", L("x", body=x), ii1)), ("4.3  λi. i i 1", L("i", body=ii1)),
                ("4.4  λx. if x then x else 1", L("x", body=("if", x, x, ("int", 1)))), ("4.4  λx. λf. f (f x)", L("x", "f", body=A(f, A(f, x))))]:
    print(f"{name:29}:", infer(e))

আসল আউটপুট (ব্রাউজারের Python; আগে চলা block-এর আউটপুট এখানে বাদ):

4.2  λf.λg.λx. g (f x) x     : (a -> b) -> (b -> a -> c) -> a -> c   (3টি bind)
4.3  let i = λx.x in i i 1   : Int   (4টি bind)
4.3  λi. i i 1               : error: occurs check: t1 occurs in t1 -> t2
4.4  λx. if x then x else 1  : error: cannot unify Bool with Int
4.4  λx. λf. f (f x)         : a -> (a -> a) -> a   (3টি bind)

৪.২-এর উত্তর আর ৩টি bind stepper-এর সঙ্গে মেলে; let-এর i Int দেয় (৪টি bind), λ-এর i occurs check-এ আটকায়, ৪.৪ (ক) clash আর (খ) a -> (a -> a) -> a. Clash-এর বার্তায় “Bool with Int”, কারণ t1 আগেই Bool-এ বাঁধা হয়ে গেছে।

৫ · অংশ ঘ — Type soundness: progress আর preservation

ঝালিয়ে নিন: পর্ব ৩৮ · Type soundness-এর হিসাব-ভাষা (t ::= n ∣ true ∣ false ∣ t + t ∣ t < t ∣ if t then t else t), তার T-IfExpr আর E-… নিয়ম, inversion lemma, canonical forms lemma, আর derivation-এর ওপর induction; induction-এর ভিত্তি Discrete Mathematics-এর পর্ব ১০-এ। এই অংশের term-গুলো হিসাব-ভাষার, Haat-এর নয়: এখানে if একটি expression.

৫.১প্রতিটি term well-typed কি না, আর চালালে value-তে পৌঁছায় নাকি stuck হয়: (ক) if 5 then 1 else 2 (খ) 1 + true (গ) (if true then 1 else 2) + 3 (ঘ) if true then 1 else false. — ৫ নম্বর (সহজ)

(ক) ill-typed (শর্ত Int); শর্ত value কিন্তু true/false নয়, তাই কোনো নিয়ম খাটে না: শুরুতেই stuck. (খ) ill-typed, শুরুতেই stuck. (গ) well-typed, Int; E-Add1(E-IfTrue) দিয়ে 1 + 3, তারপর E-Add দিয়ে 4. (ঘ) ill-typed (T-IfExpr দুই শাখার এক type চায়), অথচ এক ধাপে E-IfTrue দিয়ে value 1: type system রক্ষণশীল, কিছু নিরীহ term-ও বাতিল করে। লেখকের lab-এ পাতার soundness block-এর check আর step দিয়ে চারটিই মেলানো (CPython 3.14.4). যেখানে নম্বর কাটে: (ঘ)-কে stuck বলা; soundness শুধু well-typed term-এর কথা বলে।

৫.২হিসাব-ভাষায় t && t যোগ করুন: typing rule আর তিনটি evaluation rule লিখুন (পর্ব ৪০-এর নামে), আর progress theorem-এর নতুন case প্রমাণ করুন। — ১০ নম্বর (মাঝারি)

নিয়ম: T-And: ⊢ t1 : Bool আর ⊢ t2 : Bool হলে ⊢ t1 && t2 : Bool. E-And1: t1 ⟶ t1′ হলে t1 && t2 ⟶ t1′ && t2. E-AndTrue: true && t2 ⟶ t2. E-AndFalse: false && t2 ⟶ false (short-circuit: t2 ফেলে দেওয়া)।

  1. Case T-And, t = t1 && t2; premise ⊢ t1 : Bool. t1-এর derivation ছোট, তাই IH: t1 value, নয়তো চলে। — IH
  2. t1 ⟶ t1′ হলে E-And1 দিয়ে t ⟶ t1′ && t2.
  3. t1 value হলে canonical forms (১): ⊢ t1 : Bool, তাই t1 = true বা false; প্রথমটিতে E-AndTrue, দ্বিতীয়টিতে E-AndFalse. ∎

লক্ষ করুন, t2-এ IH লাগেইনি: নিয়মগুলো t2-কে আগে হিসাব করে না। যেখানে নম্বর কাটে: canonical forms-এর উল্লেখ বাদ দেওয়া; “t1 value, তাই true বা false” লাইনটিই type-এর একমাত্র ব্যবহার।

৫.৩একই বর্ধিত ভাষায় preservation-এর T-And case প্রমাণ করুন। Inversion lemma-য় কী যোগ করতে হয়? — ১০ নম্বর (মাঝারি)

Inversion-এ নতুন অংশ: ⊢ t1 && t2 : τ হলে τ = Bool, ⊢ t1 : Bool আর ⊢ t2 : Bool (এই গঠনের নিয়ম একটিই)।

  1. ধরি ⊢ t1 && t2 : τ আর t ⟶ t′; inversion দিয়ে τ = Bool আর দুই premise. ধাপটি কোন নিয়মে এল, তিন case.
  2. E-And1: t′ = t1′ && t2; IH দিয়ে ⊢ t1′ : Bool; সঙ্গে ⊢ t2 : Bool, তাই T-And দিয়ে ⊢ t′ : Bool.
  3. E-AndTrue: t′ = t2, আর ⊢ t2 : Bool সরাসরি premise থেকে।
  4. E-AndFalse: t′ = false, T-Bool দিয়ে Bool. ∎

পাতার soundness block ২০,০০০টি এলোমেলো term-এ (seed 85) এই বর্ধিত ভাষায় progress আর preservation দুটিই মেলায়। যেখানে নম্বর কাটে: E-AndTrue case-এ “t2 well-typed” লিখে থামা; দাবি হলো একই type Bool.

৫.৪T-IfExpr-এর বদলে একজন “ঢিলা” নিয়ম দিলেন: ⊢ t1 : Bool, ⊢ t2 : τ, ⊢ t3 : τ′ হলে ⊢ if t1 then t2 else t3 : τ. Progress আর preservation-এর কোনটি ভাঙে? ছোট counterexample দিন, আর দেখান soundness নিজেও ভাঙে। — ১০ নম্বর (কঠিন)
  1. Progress টেকে: তার if-case শুধু শর্তের type (Bool) আর canonical forms ব্যবহার করে, শাখার type নয়।
  2. Preservation ভাঙে: if false then 3 else true-এর type ঢিলা নিয়মে Int, কিন্তু E-IfFalse দিয়ে এক ধাপে true, যার type Bool.
  3. Soundness ভাঙে: (if false then 3 else true) + 1-এর type Int (T-Add), কিন্তু ⟶ true + 1, যা stuck. Well-typed term আটকে গেল। ∎

প্রমাণের কোন লাইনটি অচল: preservation-এর E-IfFalse case-এ দরকার ছিল ⊢ t3 : τ, কিন্তু নতুন নিয়ম দেয় শুধু τ′. পাতার block এলোমেলো term-এ এমন ১৮টি preservation-ভঙ্গ আর ৩টি শেষে-stuck term খুঁজে পায়। যেখানে নম্বর কাটে: “progress-ও ভাঙে” লেখা।

৫.৫Haat-এ var n = 4; তারপর print(1000 / (n - n)); well-typed, অথচ চালালে runtime error. এটি কি type soundness-এর counterexample? — ৫ নম্বর (মাঝারি)

না। পর্ব ৪০-এ E-DivZero নিয়ম আছে: ⟨v1 / 0, σ⟩ ⟶ error, আর error একটি ঘোষিত শেষ অবস্থা, stuck নয় (stuck মানে কোনো নিয়মই খাটে না)। Soundness দাবি করে well-typed program stuck হয় না; সে ভাগশেষ শূন্য না হওয়ার মতো মানের দাবি করে না (পর্ব ৩৮-এর অংশ ৭)। ভাজক শূন্য কি না, তা সাধারণভাবে চালানোর আগে জানা যায় না। যেখানে নম্বর কাটে: “type system ভুল” লেখা; সঠিক উত্তর: ভুলটি soundness-এর আওতার বাইরে, ঘোষিত runtime error.

import random                     # হিসাব-ভাষা (পর্ব ৩৮) + && : progress আর preservation পরীক্ষা
def is_val(t): return t[0] in ("num", "bool")
def check(t, loose=False):        # T-Int T-Bool T-Add T-Cmp T-IfExpr T-And; loose = ভুল if-নিয়ম
    if is_val(t): return "Int" if t[0] == "num" else "Bool"
    ts = [check(x, loose) for x in t[1:]]
    if t[0] == "if": return ts[1] if ts[0] == "Bool" and None not in ts and (loose or ts[1] == ts[2]) else None
    if t[0] == "&&": return "Bool" if ts == ["Bool", "Bool"] else None
    return ("Int" if t[0] == "+" else "Bool") if ts == ["Int", "Int"] else None
def step(t):                      # এক ধাপ ⟶ ; কোনো নিয়ম না খাটলে None (stuck)
    if is_val(t): return None
    k, a, b = t[0], t[1], t[2]
    if not is_val(a): r = step(a); return r and (k, r, *t[2:])            # E-Add1, E-Lt1, E-If, E-And1
    if k == "if": return (t[2] if a[1] else t[3]) if a[0] == "bool" else None   # E-IfTrue/False
    if k == "&&": return (t[2] if a[1] else a) if a[0] == "bool" else None    # E-AndTrue/False
    if not is_val(b): r = step(b); return r and (k, a, r)                  # E-Add2, E-Lt2
    if a[0] != "num" or b[0] != "num": return None
    return ("num", a[1] + b[1]) if k == "+" else ("bool", a[1] < b[1])     # E-Add, E-Lt
def sh(t): return str(t[1]).lower() if is_val(t) else f"({t[0]} " + " ".join(map(sh, t[1:])) + ")"
def final(t): r = step(t); return t if r is None else final(r)        # ⟶* যতদূর যায়
def gen(d):
    if d == 0 or random.random() < 0.3: return random.choice([("num", random.randint(0, 3)), ("bool", random.random() < 0.5)])
    k = random.choice(["+", "<", "&&", "if"]); return (k, *[gen(d - 1) for _ in range(3 if k == "if" else 2)])
random.seed(85); terms = [gen(4) for _ in range(20000)]
for loose in (False, True):
    typed = [t for t in terms if check(t, loose)]
    prog = sum(is_val(t) or step(t) is not None for t in typed)
    pres = [t for t in typed if not is_val(t) and check(step(t), loose) != check(t, loose)]
    stuck = sum(not is_val(final(t)) for t in typed)
    print("loose" if loose else "strict", "| well-typed:", len(typed), "| progress:", prog, "| preservation ভাঙে:", len(pres), "| শেষে stuck:", stuck)
    if pres: t = min(pres, key=lambda t: len(str(t))); print("   ছোট উদাহরণ:", sh(t), "⟶", sh(step(t)), "| type", check(t, True), "→", check(step(t), True))

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

strict | well-typed: 6270 | progress: 6270 | preservation ভাঙে: 0 | শেষে stuck: 0
loose | well-typed: 6304 | progress: 6304 | preservation ভাঙে: 18 | শেষে stuck: 3
   ছোট উদাহরণ: (if false 3 true) ⟶ true | type Int → Bool

পর্ব ৩৮-এর নিয়মের সঙ্গে T-And আর তিনটি E-And নিয়ম। “strict” লাইনে ৬,২৭০টি well-typed term-এর সবগুলোতে progress, একটিতেও preservation ভাঙেনি, শেষে কেউ stuck নয়। “loose” লাইন ৫.৪-এর ঢিলা নিয়ম: progress সবখানে টেকে, কিন্তু ১৮টি term-এ type বদলায় আর ৩টি শেষে stuck হয়; সবচেয়ে ছোটটি হুবহু ৫.৪-এর counterexample. এলোমেলো পরীক্ষা প্রমাণ নয়; ভুল নিয়ম ধরতে এটি সস্তা আর দ্রুত।

৬ · অংশ ঙ — Operational semantics: small-step আর big-step

ঝালিয়ে নিন: পর্ব ৪০ · Operational semantics-এর Haat-core, তার small-step নিয়ম (E-Var, E-Op1, E-Op2, E-Op, E-And1, E-AndTrue, E-AndFalse, E-Assign1, E-Assign, E-Print1, E-Print, E-Seq1, E-SeqSkip, E-If, E-IfTrue, E-IfFalse, E-While, E-DivZero) আর big-step নিয়ম (B-Val, B-Var, B-Op, B-Assign, B-Seq, B-IfT, B-IfF, B-WhileT, B-WhileF). ধাপের নাম বাইরে থেকে ভেতরে লেখা হয়, যেমন E-Assign1(E-Op2(E-Op)); congruence rule মোড়ক, ভেতরে আসল কাজ।

৬.১⟨x = (1 + 2) * 4;, {x ↦ 0}⟩ থেকে ⟨skip, σ′⟩ পর্যন্ত প্রতিটি small-step ধাপ নিয়মের নামসহ লিখুন। — ৫ নম্বর (সহজ)
  1. E-Assign1(E-Op1(E-Op)): ভেতরে 1 + 2-এর দুই পাশ value, E-Op দেয় 3; বাঁ operand ধাপ নিচ্ছে বলে E-Op1. ⟶ ⟨x = 3 * 4;, {x ↦ 0}⟩
  2. E-Assign1(E-Op) ⟶ ⟨x = 12;, {x ↦ 0}⟩
  3. E-Assign ⟶ ⟨skip, {x ↦ 12}⟩. মোট ৩টি ধাপ। ∎

Reference-এ var x = 0; x = (1 + 2) * 4; print(x); চালালে সত্যিকারের run-এ আসে 12. যেখানে নম্বর কাটে: প্রথম ধাপকে E-Op2 বলা; বন্ধনীর যোগটি *-এর বাঁ operand.

৬.২দুটি statement-এর small-step চালান, σ = { }: (ক) print(false && 10 / 0 > 1); (খ) print(10 / 0 > 1 && false);. কোনটি কী ছাপে? — ১০ নম্বর (মাঝারি)
  1. (ক) E-Print1(E-AndFalse): বাঁ পাশ ইতিমধ্যে value false, তাই ডান পাশ ফেলে দিয়ে ⟨print(false);⟩; তারপর E-Print, out = [false]. মোট ২ ধাপ; ভাগটি কখনো হয় না।
  2. (খ) বাঁ পাশ আগে (সিদ্ধান্ত ১২): একদম ভেতরে 10 / 0, দুই পাশ value, ভাজক 0: E-DivZero, আর error ভেতর থেকে বাইরে ছড়ায় congruence-এর সঙ্গী নিয়মে (E-Op1-Err, E-And1-Err, E-Print1-Err). প্রথম ধাপেই error, out ফাঁকা।

দুটি লাইন এক file-এ রেখে reference-এর সত্যিকারের run: প্রথমটি false ছাপে, দ্বিতীয়টিতে 5:10: runtime error: division by zero (অবস্থান /-এ, সিদ্ধান্ত ২৪)। && commutative নয়: E-AndFalse শুধু বাঁ পাশ দেখে। যেখানে নম্বর কাটে: (খ)-তে আগে false দেখে short-circuit করা।

৬.৩⟨while i < 2 { i = i + 1; }, {i ↦ 0}⟩ থামতে কয়টি small-step লাগে? প্রতি ঘোরার ধাপ ভাগ করে দেখান, আর while i < n-এর জন্য (n একটি literal, শুরুতে i = 0) সাধারণ সূত্র দিন। — ১০ নম্বর (মাঝারি)
  1. প্রতি ঘোরা: E-While (১), শর্তে E-If(E-Op1(E-Var)) আর E-If(E-Op) (২), E-IfTrue (১), দেহে E-Seq1(E-Assign1(E-Op1(E-Var))), E-Seq1(E-Assign1(E-Op)), E-Seq1(E-Assign) (৩), E-SeqSkip (১): মোট ৮.
  2. শেষ বার: E-While, শর্তের দুই ধাপ, E-IfFalse: ৪.
  3. মোট 8 · 2 + 4 = ২০; সাধারণভাবে 8n + 4. ∎

পাতার block ২০ গোনে; লেখকের lab-এ একই function দিয়ে n = 0 থেকে 5 পর্যন্ত 4, 12, 20, 28, 36, 44 পাওয়া গেছে (CPython 3.14.4), সূত্রের সঙ্গে হুবহু মেলে। যেখানে নম্বর কাটে: E-SeqSkip বা E-Var-এর ধাপ বাদ দিয়ে গোনা।

৬.৪σ = {x ↦ −3, y ↦ 0}. ⟨if x > 0 { y = x; } else { y = 0 - x; }, σ⟩ ⇓ σ′-এর big-step derivation লিখুন; judgment গুনুন। — ১০ নম্বর (মাঝারি)
⟨if x > 0 {…} else {…}, σ⟩ ⇓ σ[y ↦ 3]   [B-IfF]
  ⟨x > 0, σ⟩ ⇓ false                     [B-Op]
    ⟨x, σ⟩ ⇓ −3                          [B-Var]
    ⟨0, σ⟩ ⇓ 0                           [B-Val]
  ⟨y = 0 - x;, σ⟩ ⇓ σ[y ↦ 3]             [B-Assign]
    ⟨0 - x, σ⟩ ⇓ 3                       [B-Op]
      ⟨0, σ⟩ ⇓ 0                         [B-Val]
      ⟨x, σ⟩ ⇓ −3                        [B-Var]

৮টি judgment, উচ্চতা ৪; σ′ = {x ↦ −3, y ↦ 3}. B-IfF-এর premise দুটি: শর্ত false আর else-শাখার চলা; then-শাখা গাছে আসেই না। লেখকের lab-এর একটি ছোট big-step evaluator একই ৮টি judgment ছাপে, আর reference-এ var x = 0 - 3; দিয়ে একই program-এর সত্যিকারের run ছাপে 3. ৬.৩-এর loop-এর big-step গাছে ২০টি judgment (একই evaluator). যেখানে নম্বর কাটে: গাছে then-শাখা আঁকা, বা B-IfT লেখা।

৬.৫প্রমাণের রূপরেখা দিন: Haat-core-এর expression-এর small-step deterministic, অর্থাৎ ⟨e, σ⟩ ⟶ ⟨e′, σ⟩ আর ⟨e, σ⟩ ⟶ ⟨e″, σ⟩ হলে e′ = e″. — ১০ নম্বর (কঠিন)

প্রথম ধাপের derivation-এর ওপর induction; শেষ নিয়ম ধরে case.

  1. Value কোনো নিয়মের বাঁ পাশে নেই, তাই value-এর ধাপ নেই। E-Var: σ(x) একটি নির্দিষ্ট মান।
  2. e = e1 ⊕ e2: তিনটি নিয়মের শর্ত পরস্পর-বর্জিত: E-Op1-এ e1 value নয়; E-Op2-এ e1 value আর e2 নয়; E-Op-এ দুটিই value. তাই দুই derivation একই নিয়মে শেষ।
  3. দুটিই E-Op1 হলে ভেতরের ধাপ দুটির ওপর IH: e1′ এক, তাই e′ = e″. E-Op2 একইভাবে; E-Op-এ v = v1 ⊕̂ v2 একটি function, ফল এক।
  4. &&: E-And1 চায় e1 value নয়, E-AndTrue/False চায় e1 ঠিক true/false; আবার বর্জিত, আর E-And1-এ IH. ∎

মূল কথা: E-Op2-এর বাঁ পাশে v1 লেখাটিই (সিদ্ধান্ত ১২) নিয়মগুলোকে বর্জিত রাখে। এটি সরালে (1 + 2) + (3 + 4)-এ দুটি আলাদা প্রথম ধাপ সম্ভব হতো। যেখানে নম্বর কাটে: বর্জনের যুক্তি না দিয়ে “প্রতিটি গঠনের একটি নিয়ম” বলা; +-এর নিয়ম তিনটি।

import operator as O              # Haat-core: পর্ব ৪০-এর small-step (⟶) আর big-step (⇓)
OPS = {"+": O.add, "-": O.sub, "*": O.mul, "/": lambda a, b: int(a / b), "<": O.lt, ">": O.gt}
def isv(t): return isinstance(t, (bool, int))
def sub(t, i, s, name): x, s2, r = step(t[i], s); return t[:i] + (x,) + t[i + 1:], s2, f"{name}({r})"
def step(t, s):                   # ⟨t, σ⟩ ⟶ ⟨t′, σ′⟩ ; ফেরত (t′, σ′, নিয়মের নাম)
    if isinstance(t, str): return s[t], s, "E-Var"
    k = t[0]
    if k in OPS:
        if not isv(t[1]): return sub(t, 1, s, "E-Op1")
        if not isv(t[2]): return sub(t, 2, s, "E-Op2")
        if k == "/" and t[2] == 0: raise ZeroDivisionError("E-DivZero: division by zero")
        return OPS[k](t[1], t[2]), s, "E-Op"
    if k == "&&":
        if not isv(t[1]): return sub(t, 1, s, "E-And1")
        return (t[2], s, "E-AndTrue") if t[1] else (False, s, "E-AndFalse")
    if k in ("=", "print") and not isv(t[-1]): return sub(t, len(t) - 1, s, "E-Assign1" if k == "=" else "E-Print1")
    if k == "=": return "skip", {**s, t[1]: t[2]}, "E-Assign"
    if k == "print": return "skip", {**s, "out": s["out"] + [str(t[1]).lower()]}, "E-Print"
    if k == "seq": return (t[2], s, "E-SeqSkip") if t[1] == "skip" else sub(t, 1, s, "E-Seq1")
    if k == "if": return sub(t, 1, s, "E-If") if not isv(t[1]) else (t[2], s, "E-IfTrue") if t[1] else (t[3], s, "E-IfFalse")
    return ("if", t[1], ("seq", t[2], t), "skip"), s, "E-While"
def trace(t, s, show=True, n=0):
    while t != "skip":
        try: t, s, r = step(t, s); n += 1
        except ZeroDivisionError as e: return print(f"   {n + 1}: error ({e}), out = {s['out']}")
        if show: print(f"   {n}: {r}")
    print(f"   মোট {n} ধাপ, σ′ = {s}")
for name, t, s in [("6.1", ("=", "x", ("*", ("+", 1, 2), 4)), {"x": 0}), ("6.2 ক", ("print", ("&&", False, (">", ("/", 10, 0), 1))), {}),
                   ("6.2 খ", ("print", ("&&", (">", ("/", 10, 0), 1), False)), {}), ("6.3", ("while", ("<", "i", 2), ("=", "i", ("+", "i", 1))), {"i": 0})]:
    print(name); trace(t, {**s, "out": []}, show=name != "6.3")

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

6.1
   1: E-Assign1(E-Op1(E-Op))
   2: E-Assign1(E-Op)
   3: E-Assign
   মোট 3 ধাপ, σ′ = {'x': 12, 'out': []}
6.2 ক
   1: E-Print1(E-AndFalse)
   2: E-Print
   মোট 2 ধাপ, σ′ = {'out': ['false']}
6.2 খ
   1: error (E-DivZero: division by zero), out = []
6.3
   মোট 20 ধাপ, σ′ = {'i': 2, 'out': []}

৬.১-এর তিনটি নাম, ৬.২ (ক)-এর দুই ধাপ আর (খ)-এর প্রথম ধাপেই error, আর ৬.৩-এর ২০টি ধাপ। step() পর্ব ৪০-এর block-এর সংক্ষিপ্ত রূপ: ভাগ শুধু ছোট সংখ্যার জন্য শূন্যের দিকে কাটা হয়েছে, আর 64-bit wrap বাদ (এখানকার সংখ্যা ছোট)। Error-এর মোড়ক-নামগুলো block ছাপে না, শুধু ভেতরের E-DivZero.

৭ · অংশ চ — Denotational semantics আর Hoare logic

ঝালিয়ে নিন: পর্ব ৪১ · Denotational semantics (⟦S⟧ : Σ → Σ⊥, f†, loop-এর functional F, Kleene iteration আর least fixpoint), পর্ব ৪২ · Axiomatic semantics (H-Skip, H-Assign, H-Seq, H-If, H-While, H-Cons, H-WhileT; wp আর def(e)), Discrete Mathematics-এর পর্ব ১৩ আর পর্ব ৫৬. এই অংশের হিসাব গণিতের পূর্ণসংখ্যায়; 64-bit-এর প্রভাব যেখানে আছে, আলাদা বলা হয়েছে।

৭.১σ = {x ↦ 5, y ↦ 0}. সমীকরণ দিয়ে ⟦x = x * 2; y = x + 1;⟧σ বের করুন। — ৫ নম্বর (সহজ)
  1. ⟦S1 S2⟧σ = ⟦S2⟧†(⟦S1⟧σ). — sequencing-এর সমীকরণ
  2. ⟦x = x * 2;⟧σ = σ[x ↦ ⟦x * 2⟧σ] = σ[x ↦ 10] = {x ↦ 10, y ↦ 0}; ⊥ বা err নয়, তাই † সরাসরি খাটে।
  3. ⟦y = x + 1;⟧{x ↦ 10, y ↦ 0} = {x ↦ 10, y ↦ 11}. ∎

যেখানে নম্বর কাটে: দ্বিতীয় assignment-এ পুরোনো σ-এর x = 5 নেওয়া (তাহলে y = 6); compositionality মানে ঠিক এই ক্রমে ফল জোড়া।

৭.২W = ⟦while n > 0 { n = n - 2; }⟧. শুরুর n ∈ {−1, 0, 1, 2, 3, 4}-এ f0 = ⊥ থেকে f4 পর্যন্ত Kleene approximant লিখুন, W-এর সাধারণ রূপ দিন। while t != 7 { t = t + 2; } শুরুর t = 0-এ কী অর্থ পায়, প্রমাণসহ? — ১০ নম্বর (মাঝারি)
  1. F(w) = λσ. σ(n) > 0 হলে w†(σ[n ↦ n − 2]), নইলে σ. fk জানে k-এর কম ঘোরায় থামা state.
  2. f1: শুধু n ≤ 0 (−1 → −1, 0 → 0); বাকি ⊥. f2: যোগ হয় 1 → −1, 2 → 0. f3: 3 → −1, 4 → 0. f4 = f3 এই ছয়টি state-এ।
  3. সাধারণ রূপ: n ≤ 0 হলে n অপরিবর্তিত; n > 0 বিজোড় হলে শেষে −1, জোড় হলে 0. প্রতিটি state-এ কোনো সসীম k-তে মান আসে, তাই কোথাও ⊥ নেই।
  4. t != 7-এর loop: t = 0 থেকে t সবসময় জোড় (জোড় + 2 = জোড়; 64-bit wrap-এও, কারণ 264 জোড়), তাই কখনো 7 নয়; সব fk(σ) = ⊥, আর ⟦·⟧σ = ⊥. ∎

সাবধান: কয়েকটি state-এ দুটি পরপর approximant মিলে গেলেই fixpoint প্রমাণ হয় না; প্রমাণ এখানে parity-র যুক্তি। যেখানে নম্বর কাটে: f1-এ 2 → 0 লেখা; f1 = F(⊥), এক ঘোরা লাগে এমন state-এ এখনো ⊥.

৭.৩S = d = total / k; total = total - d;, Q = total ≥ 0. wp(S, Q) বের করুন (def(e) সহ)। {total ≥ 0 ∧ k ≠ 0} S {Q} প্রমাণ করুন। total ≥ 0 শর্তটি বাদ দিলে কী হয়? Haat-এর 64-bit Int-এ দাবিটি কি টেকে? — ১০ নম্বর (মাঝারি)
  1. পেছন থেকে: wp(total = total - d;, Q) = total − d ≥ 0 (H-Assign; ভাগ নেই, def সত্য)।
  2. wp(d = total / k;, …) = def(total / k) ∧ total − total / k ≥ 0 = k ≠ 0 ∧ total − total / k ≥ 0. — H-Assign, ভাগে def
  3. P ⇒ wp (ℤ-এ): k > 0 হলে শূন্যের দিকে কাটা ভাগে 0 ≤ total / k ≤ total; k < 0 হলে total / k ≤ 0, তাই total − total / k ≥ total ≥ 0. H-Cons দিয়ে triple প্রমাণিত। ∎
  4. total ≥ 0 বাদ দিলে: total = −1, k = −1 হলে d = 1, শেষে total = −2. Reference-এর সত্যিকারের run-ও −2 ছাপে।

64-bit-এ: না, পুরোপুরি টেকে না। total = 4611686018427387904 (262), k = −1 হলে d = −262, আর total − d = 263, যা wrap করে −9223372036854775808 (সিদ্ধান্ত ১৩)। Reference-এর run আর vm দুটিই এই সংখ্যা ছাপে। তাই 64-bit-এ P-তে total ≤ 262 − 1-এর মতো আরেকটি শর্ত লাগে, বা k > 0. যেখানে নম্বর কাটে: def(e) বাদ দেওয়া; তাহলে k = 0-এ program error-এ থামে অথচ “প্রমাণ” বলে Q সত্য।

৭.৪i = 0; s = 0; while i < n { i = i + 1; s = s + i; }, P = n ≥ 0, Q = 2 · s = n · (n + 1). Total correctness প্রমাণ করুন: loop invariant, variant আর চারটি verification condition লিখুন। Invariant থেকে i ≤ n বাদ দিলে কোন VC ভাঙে? — ১০ নম্বর (কঠিন)

I = 2 · s = i · (i + 1) ∧ 0 ≤ i ≤ n; V = n − i.

  1. Init: wp(i = 0; s = 0;, I) = 0 = 0 ∧ 0 ≤ 0 ≤ n, যা P থেকে আসে।
  2. Preserve: I ∧ i < n ⇒ wp(দেহ, I) = 2(s + i + 1) = (i + 1)(i + 2) ∧ 0 ≤ i + 1 ≤ n. প্রথমটি: 2s + 2i + 2 = i² + i + 2i + 2 = (i + 1)(i + 2). দ্বিতীয়টি i < n থেকে।
  3. Exit: I ∧ ¬(i < n): i ≥ n আর i ≤ n, তাই i = n, ফলে 2s = n(n + 1) = Q.
  4. Variant: I ∧ i < n ⇒ V ≥ 0, আর এক ঘোরায় V ঠিক ১ কমে। H-WhileT, H-Seq আর H-Cons জুড়ে [P] program [Q]. ∎

i ≤ n বাদ দিলে: init, preserve, variant টেকে, কিন্তু exit ভাঙে: (i, s, n) = (1, 1, 0)-তে নতুন I সত্য আর i < n মিথ্যা, অথচ 2s = 2 ≠ 0. n = 4-এ reference ছাপে 10 = 4 · 5 / 2. যেখানে নম্বর কাটে: শুধু “চালিয়ে দেখলাম ঠিক” লেখা; VC প্রতিটি I-সত্য state-এ খাটতে হয়, শুধু পৌঁছানো state-এ নয়।

import operator as O              # Haat-core-এর denotation (পর্ব ৪১): ⟦e⟧ আর ⟦S⟧ function, ⊥ = None
OPS = {"+": O.add, "-": O.sub, "*": O.mul, ">": O.gt, "<": O.lt, "!=": O.ne}
def E(e):                         # ⟦e⟧ : Σ → V, শুধু অংশের অর্থ থেকে গড়া
    if isinstance(e, int): return lambda s: e
    if isinstance(e, str): return lambda s: s[e]
    f, a, b = OPS[e[0]], E(e[1]), E(e[2]); return lambda s: f(a(s), b(s))
def lift(r, w): return None if r is None else w(r)           # w† : ⊥ হলে ⊥ই থাকে
def F(b, c):                      # loop-এর functional: F(w) = λσ. ⟦b⟧σ হলে w†(⟦S⟧σ), নইলে σ
    return lambda w: (lambda s: lift(c(s), w) if b(s) else s)
def C(S):                         # ⟦S⟧ : Σ → Σ⊥
    if S[0] == "=": x, d = S[1], E(S[2]); return lambda s: {**s, x: d(s)}
    if S[0] == "seq": c1, c2 = C(S[1]), C(S[2]); return lambda s: lift(c1(s), c2)
    b, c = E(S[1]), C(S[2]); fk = lambda s: None               # while: f0 = ⊥ থেকে Kleene
    def run(s, limit=100):
        f = fk
        for _ in range(limit):
            if f(s) is not None: return f(s)
            f = F(b, c)(f)
        return None                                               # limit পর্যন্ত ⊥
    return run
print("7.1:", C(("seq", ("=", "x", ("*", "x", 2)), ("=", "y", ("+", "x", 1))))({"x": 5, "y": 0}))
b, c, starts = E((">", "n", 0)), C(("=", "n", ("-", "n", 2))), [-1, 0, 1, 2, 3, 4]
f = lambda s: None
for k in range(5):                # f_k = F^k(⊥) : শুরুর n → শেষের n বা ⊥
    print(f"7.2 f{k}:", "  ".join(f"{n}→{'⊥' if f({'n': n}) is None else f({'n': n})['n']}" for n in starts))
    f = F(b, c)(f)
print("7.2 total != 7, +2:", C(("while", ("!=", "t", 7), ("=", "t", ("+", "t", 2))))({"t": 0}))

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

7.1: {'x': 10, 'y': 11}
7.2 f0: -1→⊥  0→⊥  1→⊥  2→⊥  3→⊥  4→⊥
7.2 f1: -1→-1  0→0  1→⊥  2→⊥  3→⊥  4→⊥
7.2 f2: -1→-1  0→0  1→-1  2→0  3→⊥  4→⊥
7.2 f3: -1→-1  0→0  1→-1  2→0  3→-1  4→0
7.2 f4: -1→-1  0→0  1→-1  2→0  3→-1  4→0
7.2 total != 7, +2: None

প্রথম লাইন ৭.১. তারপর f0 থেকে f4: প্রতি ধাপে নতুন state যোগ হয়, পুরোনো কোনো ফল বদলায় না (fk ⊑ fk+1), আর f3 = f4 এই ছয়টি state-এ। শেষ লাইন None মানে ১০০টি approximant পর্যন্ত ⊥; এটি পর্যবেক্ষণ, প্রমাণ ৭.২-এর parity-যুক্তি।

from itertools import product     # Hoare logic (পর্ব ৪২): wp আর loop invariant, ছোট পরিসরে সব অবস্থা
def cdiv(a, b): q = abs(a) // abs(b); return q if (a < 0) == (b < 0) else -q
def run73(t, k):                  # d = total / k; total = total - d;   (k = 0 হলে runtime error)
    if k == 0: return None
    return t - cdiv(t, k)
wp73 = lambda t, k: k != 0 and t - cdiv(t, k) >= 0                  # হাতে বের করা wp
grid = list(product(range(-30, 31), range(-6, 7)))
same = sum(wp73(t, k) == (run73(t, k) is not None and run73(t, k) >= 0) for t, k in grid)
print("7.3 wp সত্য ⇔ error ছাড়া শেষে total >= 0:", same, "/", len(grid))
print("7.3 {total >= 0 && k != 0} ⇒ wp:", all(wp73(t, k) for t, k in grid if t >= 0 and k != 0))
bad = [(t, k) for t, k in grid if k != 0 and not wp73(t, k)]
print("7.3 total >= 0 বাদ দিলে counterexample (total, k):", min(bad, key=lambda p: (abs(p[0]), abs(p[1]))), "| মোট", len(bad))
# 7.4: i = 0; s = 0; while i < n { i = i + 1; s = s + i; }   Q: 2*s == n*(n+1)
body = lambda i, s, n: (i + 1, s + i + 1)
INV = {"2*s == i*(i+1) && 0 <= i <= n": lambda i, s, n: 2 * s == i * (i + 1) and 0 <= i <= n,
       "2*s == i*(i+1) && 0 <= i":      lambda i, s, n: 2 * s == i * (i + 1) and 0 <= i,
       "2*s == i*(i+1)":                lambda i, s, n: 2 * s == i * (i + 1)}
for name, I in INV.items():
    st = list(product(range(-8, 12), range(-10, 80), range(0, 10)))      # (i, s, n), শুরুতে n >= 0
    vc = {"init": all(I(0, 0, n) for n in range(10)),
          "preserve": all(I(*body(i, s, n), n) for i, s, n in st if I(i, s, n) and i < n),
          "exit": all(2 * s == n * (n + 1) for i, s, n in st if I(i, s, n) and not i < n),
          "variant": all(n - i >= 0 and n - body(i, s, n)[0] < n - i for i, s, n in st if I(i, s, n) and i < n)}
    fails = [k for k, ok in vc.items() if not ok]
    print(f"7.4 I = {name:30}:", "চারটি VC সত্য" if not fails else "ভাঙে: " + ", ".join(fails))
cex = next((i, s, n) for i, s, n in product(range(12), range(80), range(10)) if 2 * s == i * (i + 1) and 0 <= i and not i < n and 2 * s != n * (n + 1))
print("   i <= n বাদ দিলে exit-এর counterexample (i, s, n):", cex)

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

7.3 wp সত্য ⇔ error ছাড়া শেষে total >= 0: 793 / 793
7.3 {total >= 0 && k != 0} ⇒ wp: True
7.3 total >= 0 বাদ দিলে counterexample (total, k): (-1, -1) | মোট 330
7.4 I = 2*s == i*(i+1) && 0 <= i <= n : চারটি VC সত্য
7.4 I = 2*s == i*(i+1) && 0 <= i      : ভাঙে: exit
7.4 I = 2*s == i*(i+1)                : ভাঙে: exit
   i <= n বাদ দিলে exit-এর counterexample (i, s, n): (1, 1, 0)

৭.৩-এর হাতে বের করা wp ৭৯৩টি state-এর সবগুলোতে “চালিয়ে error ছাড়া শেষে Q” -এর সঙ্গে মেলে (k = 0-এর state-গুলো সহ), আর P ⇒ wp সব ছোট state-এ সত্য। ৭.৪-এর সঠিক invariant চারটি VC-ই পূরণ করে; i ≤ n বাদ দিলে শুধু exit ভাঙে, ঠিক উত্তরে বলা counterexample-সহ। এখানে হিসাব Python-এর বড় পূর্ণসংখ্যায়, তাই ৭.৩-এর 64-bit wrap এই block ধরে না; সেটি reference-এর run দেখিয়েছে।

৮ · অংশ ছ — Lambda calculus: substitution, β আর reduction-এর ক্রম

ঝালিয়ে নিন: পর্ব ৪৩ · Lambda calculus (FV, capture-avoiding substitution, α-renaming, β-reduction, STLC-এর T-Var, T-Fn, T-Call), পর্ব ১৯ · Evaluation strategy (normal order বনাম applicative order), আর তত্ত্বের দিক গণনার তত্ত্ব · পর্ব ৪৯. লেখার নিয়ম: application বাঁ দিকে জোড়া লাগে, λ-এর দেহ যতদূর সম্ভব ডানে যায়। এখানে normal আর applicative order পুরো normal form চায়, λ-এর ভেতরেও কমায়।

৮.১FV(λx. x y) কী? [y ↦ x](λx. x y) হিসাব করুন, আর সরল substitution কেন ভুল তা বলুন। — ৫ নম্বর (সহজ)

FV(λx. x y) = FV(x y) − {x} = {y}. Substitution-এ binder x ≠ y, আর দেহে y free, তাই ভেতরে ঢুকতে হবে; কিন্তু বসানো term s = x-এ x free (x ∈ FV(s)), তাই আগে α-renaming: λx1. x1 y. তারপর দেহে বসানো: λx1. x1 x. সরলভাবে বসালে λx. x x: বাইরের x ভেতরের λ-এর হাতে ধরা পড়ে, অর্থ বদলে যায় (প্রশ্ন ৯.৫)। যেখানে নম্বর কাটে: নতুন নামটি FV(s) বা দেহের কোনো নামের সঙ্গে মিলিয়ে ফেলা।

৮.২(λx. λy. y x) a (λz. z)-কে normal form পর্যন্ত কমান, প্রতিটি β আলাদা লাইনে। — ৫ নম্বর (সহজ)
  1. ((λx. λy. y x) a) (λz. z) ⟶ (λy. y a) (λz. z) — β, x ↦ a
  2. ⟶ (λz. z) a — β, y ↦ λz. z
  3. ⟶ a. মোট ৩টি β; normal আর applicative দুই ক্রমেই একই ৩ ধাপ, কারণ কোনো argument-এর ভেতরে redex নেই। ∎
৮.৩Ω = (λw. w w)(λw. w w). Normal আর applicative order-এ ধাপ গুনুন: (ক) (λx. z) Ω (খ) (λx. x x x) ((λy. y) z). কোন theorem বলে normal order “নিরাপদ”? — ১০ নম্বর (মাঝারি)
  1. (ক) normal: বাইরের redex আগে, argument বসে কিন্তু দেহে x নেই: ১ ধাপে z. applicative: আগে Ω কমাতে হয়, যা এক ধাপে নিজেকেই ফেরত দেয়: কখনো শেষ হয় না।
  2. (খ) normal: প্রথম β argument-টি তিনবার কপি করে, তারপর তিনটি আলাদা (λy. y) z কমে: ৪ ধাপ। applicative: আগে argument একবার z, তারপর একটি β: ২ ধাপ। দুই পথে একই normal form z z z.

Standardization theorem (Curry আর Feys, ১৯৫৮): normal form থাকলে normal order সেখানে পৌঁছায়ই। Church–Rosser নিশ্চিত করে দুই পথ শেষ হলে একই normal form. (খ) দেখায় দাম: কপি করা argument বারবার কমে, call-by-name-এর মতো। যেখানে নম্বর কাটে: (ক)-তে applicative-কে “Ω দেয়” বলা; সে কোনো ফলই দেয় না।

৮.৪STLC-তে ⊢ λf:Int → Int. λx:Int. f (f x) : (Int → Int) → Int → Int-এর derivation লিখুন। তারপর দেখান কোনো τ-এর জন্য λx:τ. x x-এর type নেই। — ১০ নম্বর (মাঝারি)
⊢ λf:Int → Int. λx:Int. f (f x) : (Int → Int) → Int → Int   [T-Fn]
  f : Int → Int ⊢ λx:Int. f (f x) : Int → Int              [T-Fn]
    Γ ⊢ f (f x) : Int                                     [T-Call]
      Γ ⊢ f : Int → Int                                   [T-Var]
      Γ ⊢ f x : Int                                       [T-Call]
        Γ ⊢ f : Int → Int                                 [T-Var]
        Γ ⊢ x : Int                                       [T-Var]

এখানে Γ = f : Int → Int, x : Int; ৭টি judgment. x x: T-Call চায় x-এর type একটি function type τ1 → τ2 আর argument-এর type τ1; কিন্তু argument-ও x, তাই τ = τ → τ2, যা কোনো সসীম type মানে না (পর্ব ৩৫-এর occurs check-এর একই যুক্তি)। লেখকের lab-এর একটি ছোট STLC checker (CPython 3.14.4) প্রথম term-এ এই ৭টি judgment ছাপে, আর τ = Int ও τ = Int → Int দুটিতেই T-Call-এ বাতিল করে। ∎

def fv(t):                        # λ-term: ("v", x) ("l", x, দেহ) ("a", f, arg); পর্ব ৪৩-এর FV
    return {t[1]} if t[0] == "v" else fv(t[2]) - {t[1]} if t[0] == "l" else fv(t[1]) | fv(t[2])
def subst(t, x, s):               # [x ↦ s] t, capture এড়িয়ে (দরকারে α-renaming)
    if t[0] == "v": return s if t[1] == x else t
    if t[0] == "a": return ("a", subst(t[1], x, s), subst(t[2], x, s))
    y, body = t[1], t[2]
    if y == x or x not in fv(body): return t
    if y in fv(s):
        z = next(f"{y}{i}" for i in range(1, 99) if f"{y}{i}" not in fv(s) | fv(body))
        body, y = subst(body, y, ("v", z)), z
    return ("l", y, subst(body, x, s))
def lshow(t):
    if t[0] == "v": return t[1]
    if t[0] == "l": return f"λ{t[1]}. {lshow(t[2])}"
    f = lshow(t[1]) if t[1][0] != "l" else f"({lshow(t[1])})"
    return f + " " + (lshow(t[2]) if t[2][0] == "v" else f"({lshow(t[2])})")
def red(t, normal):               # এক β-ধাপ; normal: বাঁয়ের বাইরের redex আগে, নইলে বাঁয়ের ভেতরের
    if t[0] == "v": return None
    if t[0] == "l": r = red(t[2], normal); return r and ("l", t[1], r)
    if normal and t[1][0] == "l": return subst(t[1][2], t[1][1], t[2])
    if (r := red(t[1], normal)): return ("a", r, t[2])
    if (r := red(t[2], normal)): return ("a", t[1], r)
    return subst(t[1][2], t[1][1], t[2]) if t[1][0] == "l" else None
def run(t, normal, limit=12):
    for n in range(limit + 1):
        if (r := red(t, normal)) is None: return f"{n} ধাপে normal form: {lshow(t)}"
        t = r
    return f"{limit} ধাপ পরেও শেষ হয়নি: {lshow(t)}"
print("8.1 FV(λx. x y) =", fv(("l", "x", ("a", ("v", "x"), ("v", "y")))))

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

8.1 FV(λx. x y) = {'y'}

এই block মূলত সংজ্ঞা: fv, capture এড়ানো subst, এক β-ধাপের red আর ধাপ গোনার run; শেষ লাইন ৮.১-এর FV = {y} ছাপে। পরের block এগুলো ব্যবহার করে (দুটি একই namespace-এ চলে; পরেরটি আগে চাপলে এটিও নিজে থেকে চলবে)।

Var = lambda x: ("v", x)          # আগের block-এর fv, subst, lshow, run কাজে লাগে
def Lam(x, b): return ("l", x, b)
def App(f, *xs):
    for x in xs: f = ("a", f, x)
    return f
x, y, z, a, I = Var("x"), Var("y"), Var("z"), Var("a"), Lam("w", Var("w"))
print("8.1 [y ↦ x](λx. x y) =", lshow(subst(Lam("x", App(x, y)), "y", x)))
omega = App(Lam("w", App(Var("w"), Var("w"))), Lam("w", App(Var("w"), Var("w"))))
for name, t in [("8.2", App(Lam("x", Lam("y", App(y, x))), a, Lam("z", z))),
                ("8.3 ক", App(Lam("x", z), omega)),
                ("8.3 খ", App(Lam("x", App(x, x, x)), App(Lam("y", y), z))),
                ("9.5 সঠিক", App(subst(Lam("x", App(x, y)), "y", x), I)), ("9.5 naive", App(Lam("x", App(x, x)), I))]:
    print(name, lshow(t))
    for normal in (True, False):
        print("   ", "normal     " if normal else "applicative", run(t, normal))

আসল আউটপুট (ব্রাউজারের Python; আগের shared block-গুলোর আউটপুট এখানে বাদ):

8.1 [y ↦ x](λx. x y) = λx1. x1 x
8.2 (λx. λy. y x) a (λz. z)
    normal      3 ধাপে normal form: a
    applicative 3 ধাপে normal form: a
8.3 ক (λx. z) ((λw. w w) (λw. w w))
    normal      1 ধাপে normal form: z
    applicative 12 ধাপ পরেও শেষ হয়নি: (λx. z) ((λw. w w) (λw. w w))
8.3 খ (λx. x x x) ((λy. y) z)
    normal      4 ধাপে normal form: z z z
    applicative 2 ধাপে normal form: z z z
9.5 সঠিক (λx1. x1 x) (λw. w)
    normal      2 ধাপে normal form: x
    applicative 2 ধাপে normal form: x
9.5 naive (λx. x x) (λw. w)
    normal      2 ধাপে normal form: λw. w
    applicative 2 ধাপে normal form: λw. w

৮.১-এর α-renaming, ৮.২-এর ৩ ধাপ, ৮.৩-এর ১ বনাম “শেষ হয়নি” আর ৪ বনাম ২. শেষ দুই উদাহরণ প্রশ্ন ৯.৫-এর: সঠিক substitution-এর ফলকে λw. w দিয়ে ডাকলে মুক্ত x ফেরে, সরল substitution-এর ফল ফেরত দেয় λw. w নিজেকে; দুটি আলাদা অর্থ। red()-এর normal শাখা আগে বাইরের redex ধরে, applicative শাখা আগে ভেতরে ঢোকে।

৯ · ভুল ধরুন — ছয়টি ভুল derivation আর প্রমাণ, আর সাধারণ ভুলের ছক

প্রতিটি “উত্তর” পরিষ্কার ভাষায় লেখা আর প্রথম দেখায় বিশ্বাসযোগ্য। ভুল লাইনটি খুঁজুন, কেন ভুল তা নিয়মের নামে বলুন, তারপর সংশোধন লিখুন।

৯.১“Γ ⊢ 1 : Int (T-Int), Γ ⊢ true : Bool (T-Bool); দুই পাশেরই type আছে আর == সবসময় Bool দেয়, তাই T-Eq দিয়ে Γ ⊢ 1 == true : Bool.” — ৫ নম্বর

ভুল: T-Eq-এর দুই premise-এ একই τ: Γ ⊢ e1 : τ আর Γ ⊢ e2 : τ. Int ≠ Bool, তাই কোনো instance নেই, আর কোনো derivation-ও নেই। সংশোধন: program ill-typed; reference বলে 1:17: error: type mismatch: expected Int, found Bool (let paid = 1 == true;-এ)। পাতার প্রথম Python block-এর মাঝের গাছটি এই ব্যর্থতা দেখায়।

৯.২“let i = λx. x in i i 1-এর type Int. let x = e1 in e2 আর (λx. e2) e1 একই অর্থ, তাই HM-এ λi. i i 1-কে λx. x দিয়ে ডাকলে তারও type আছে।” — ৫ নম্বর

ভুল: একই অর্থ মানে একই type নয়। HM-এ শুধু T-Let generalise করে; λ-এর i একটি সাধারণ t1, তাই i i-এ t1 ≐ (t1) → t2 আর occurs check ব্যর্থ (অংশ ৪-এর দ্বিতীয় block). সংশোধন: “let-এর রূপে type Int, λ-এর রূপে type নেই; HM-এ এই দুটি সমার্থক রূপ আলাদা আচরণ করে।”

৯.৩“৫.৪-এর ঢিলা if-নিয়মে preservation: E-IfFalse case-এ t′ = t3, আর premise ⊢ t3 : τ′ বলে t′ well-typed. তাই preservation সত্য।” — ১০ নম্বর

ভুল: preservation দাবি করে ⊢ t′ : τ, মূল term-এর একই type; “কোনো type আছে” যথেষ্ট নয়। τ′ ≠ τ হলে পরের ধাপে মিশ্র term stuck হতে পারে: (if false then 3 else true) + 1 ⟶ true + 1. সংশোধন: ঢিলা নিয়মে preservation মিথ্যা; T-IfExpr-এর τ = τ′ শর্তই এই case বাঁচায়। পাতার soundness block-এর “loose” লাইন।

৯.৪“Assignment-এর নিয়ম: {P} x = e; {P[e/x]}. তাই {x == 5} x = x + 1; {x + 1 == 5}.” — ৫ নম্বর

ভুল: substitution উল্টো দিকে। H-Assign হলো {Q[e/x]} x = e; {Q}: postcondition থেকে পেছনে। দাবিকৃত triple মিথ্যা: শুরুতে x = 5, পরে x = 6, আর x + 1 = 7 ≠ 5. সংশোধন: Q = x == 6 নিলে wp = (x + 1 == 6), যা ঠিক x = 5-এ সত্য; তাই {x == 5} x = x + 1; {x == 6}. নিচের block দুটি triple-ই −20 থেকে 20-এ যাচাই করে।

৯.৫“(λy. λx. x y) x ⟶ λx. x x, কারণ β মানে দেহে y-এর জায়গায় x বসানো।” — ৫ নম্বর

ভুল: বসানো x ভেতরের λx-এর হাতে ধরা পড়েছে (capture). সংশোধন: আগে α-renaming, ফল λx1. x1 x (৮.১)। পার্থক্য শুধু নামের নয়: λw. w দিয়ে ডাকলে সঠিক রূপ দেয় মুক্ত x, ভুল রূপ দেয় λw. w (অংশ ৮-এর block).

৯.৬“⟦while true { }⟧ = identity, কারণ F(w) = w, আর identity-ও W = F(W) মেলায়।” — ৫ নম্বর

ভুল: F(w) = w হলে প্রতিটি function fixpoint; “সব জায়গায় x = 5000”-ও মেলায়। Loop-এর অর্থ যেকোনো fixpoint নয়, least fixpoint ⊔ Fn(⊥), আর এখানে Fn(⊥) = ⊥ সবসময়। সংশোধন: ⟦while true { }⟧ = ⊥ সব state-এ: চিরকাল চলে, কোনো ফল নেই (পর্ব ৪১-এর Kleene theorem).

# ৯.৪: সামনের দিকে substitution — দাবি {x == 5} x = x + 1; {x + 1 == 5}
xs = range(-20, 21)
claimed = all(x + 1 + 1 == 5 for x in xs if x == 5)          # assignment-এর পরে নতুন x = পুরোনো x + 1
right = all(x + 1 == 6 for x in xs if x == 5)                # H-Assign: {(x == 6)[x+1/x]} = {x + 1 == 6}
print("9.4 {x == 5} x = x + 1; {x + 1 == 5} সত্য?", claimed, "| {x == 5} x = x + 1; {x == 6} সত্য?", right)
print("9.4 wp(x = x + 1, x == 6) = (x + 1 == 6), যা সত্য ঠিক x =", [x for x in xs if x + 1 == 6])
# ৯.৬: while true { } — F(w) = w, তাই প্রতিটি w fixpoint; least fixpoint কোনটি?
F = lambda w: (lambda s: w(s))                               # শর্ত সবসময় true, দেহ skip
ident, five = (lambda s: s), (lambda s: {**s, "x": 5000})
states = [{"x": v} for v in range(-3, 4)]
for name, w in [("identity", ident), ("সব জায়গায় x = 5000", five)]:
    print(f"9.6 F({name}) = {name}?", all(F(w)(s) == w(s) for s in states))
f = lambda s: None                                           # f0 = ⊥
for k in range(50): f = F(f)
print("9.6 Kleene: f50 কোনো state-এ সংজ্ঞায়িত?", any(f(s) is not None for s in states))

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

9.4 {x == 5} x = x + 1; {x + 1 == 5} সত্য? False | {x == 5} x = x + 1; {x == 6} সত্য? True
9.4 wp(x = x + 1, x == 6) = (x + 1 == 6), যা সত্য ঠিক x = [5]
9.6 F(identity) = identity? True
9.6 F(সব জায়গায় x = 5000) = সব জায়গায় x = 5000? True
9.6 Kleene: f50 কোনো state-এ সংজ্ঞায়িত? False

৯.৪-এর দাবিকৃত triple মিথ্যা, সংশোধিতটি সত্য, আর wp ঠিক x = 5-এ সত্য। ৯.৬-এ identity আর “x = 5000” দুটিই F-এর fixpoint, কিন্তু ⊥ থেকে ৫০ বার F খাটিয়েও কোনো state সংজ্ঞায়িত হয় না: least fixpoint ⊥.

ভুলকেমন দেখায়ঠিক কাজপ্রশ্ন
নিয়মের নাম না লেখাশুধু “Int, তাই Bool”প্রতিটি লাইনে T-…, E-…, B-… বা H-…২.১, ৬.১
Precedence ভুল গোড়াqty * (unit >= 1000)binding power দেখে গোড়া বাছুন২.১, ২.২
Side condition বাদT-Eq-এ τ ∈ {Int, Bool, Str} ভুলে যাওয়াpremise আর side condition আলাদা লিখুন৩.৪, ৯.১
Syntactic শর্তকে type ভাবাmissing return-কে “type mismatch”returns(body) আর resolver-এর কাজ আলাদা২.৩, ৩.৫
Occurs check বা walk বাদt1 := (t1) → t2 মেনে নেওয়াপ্রতিটি bind-এর আগে occurs check৪.১, ৪.৩
λ-তে generaliseparameter-কে ∀ দেওয়াশুধু let-এ, Γ-তে মুক্ত নয় এমন variable৪.৩, ৯.২
Subtyping-এর দিকparameter covariant ধরাS-Arrow: parameter উল্টো, ফল একই দিকে৪.৫
Preservation-এ “কোনো type”“t′ well-typed, তাই শেষ”একই τ দেখান, প্রতিটি E-নিয়মের case৫.৩, ৯.৩
Stuck আর runtime error গুলানোভাগে শূন্যকে soundness-ভঙ্গ বলাE-DivZero ঘোষিত শেষ অবস্থা৫.৫
Evaluation orderডান পাশ আগে, বা &&-কে commutativeসিদ্ধান্ত ১২: বাঁ থেকে ডানে৬.২, ৬.৫
Assignment সামনের দিকে{P} x = e; {P[e/x]}{Q[e/x]} x = e; {Q}, ভাগে def(e)৭.৩, ৯.৪
দুর্বল invarianti ≤ n বাদexit VC-তে i = n বের করা যায় কি না দেখুন৭.৪
যেকোনো fixpointwhile-এর অর্থ identityleast fixpoint, ⊥ থেকে Kleene৭.২, ৯.৬
Captureλx-এর ভেতরে মুক্ত x বসানোআগে α-renaming৮.১, ৯.৫

খাতায় সময়: মোট মিনিট ÷ মোট নম্বর দিয়ে প্রতিটি প্রশ্নের সময় ঠিক করুন। আটকে গেলে নিয়মের তালিকা, Γ বা constraint-এর তালিকা লিখে এগিয়ে যান; নম্বর-ভাগে এগুলোরই আলাদা নম্বর। বড় গাছে পাশে লিখে রাখুন কোন premise এখনো বাকি।

আরও গভীরে: এই পাতার হাতে-লেখা প্রমাণগুলো আজ proof assistant-এ যন্ত্র দিয়েও যাচাই হয়। Pierce আর সহলেখকদের “Software Foundations” সিরিজে STLC-এর progress, preservation আর Hoare logic Coq-এ (এখন Rocq নামে) ধাপে ধাপে প্রমাণ করা আছে, আর POPLmark challenge (২০০৫) এমন mechanized metatheory-র মানদণ্ড ঠিক করেছিল। Binder আর α-equivalence সেখানেও সবচেয়ে ঝামেলার অংশ, যে কারণে de Bruijn index (পর্ব ৪৩) জনপ্রিয়। যন্ত্রে যাচাইয়ের বাস্তব রূপ পর্ব ৪৪-এ।

পরীক্ষা ও ইন্টারভিউতে: “Γ ⊢ e : τ-এ Γ কী?” — নাম থেকে type-এর তালিকা, সবচেয়ে ডানেরটি খাটে। “HM-এ λx. x x কেন type পায় না?” — t ≐ t → t′, occurs check. “Progress আর preservation এক লাইনে?” — well-typed term value বা এক ধাপ চলে; চললে type একই থাকে। “Small-step আর big-step-এর পার্থক্য?” — একটি ধাপ বনাম পুরো ফলের গাছ; অসীম loop small-step-এ অসীম ধাপ, big-step-এ derivation-ই নেই। “wp(x = e;, Q)?” — def(e) ∧ Q[e/x].

১০ · AI-এর যুগে — AI-এর লেখা derivation আর প্রমাণ যাচাই

AI সহকারী derivation আর প্রমাণ গুছিয়ে লেখে, আর প্রায়ই এই পাতার ফাঁদগুলোতেই পড়ে: নিয়মের নাম বানিয়ে নেয় বা এক পর্বের নাম অন্য পর্বের নিয়মে বসায়, T-Eq-এর মতো side condition বাদ দেয়, এক ভাষার নিয়ম (C-র int শর্ত, Python-এর dynamic +) সব ভাষায় চাপায়, unification-এ occurs check ভুলে যায়, preservation-এ “কোনো type” লিখে থামে, evaluation order ভুল বলে, আর Hoare logic-এ assignment সামনের দিকে চালায়। প্রতিকার একটাই: প্রতিটি লাইন নিয়মের সঙ্গে মেলানো, আর ছোট উদাহরণ চালিয়ে দেখা: Haat হলে reference-এর check ও run, unification হলে পর্ব ৩৫-এর engine, semantics হলে এই পাতার block, অন্য ভাষা হলে সেই ভাষার আসল compiler আর version.

নিজের লেখা উত্তর AI-কে দিয়ে পরীক্ষা করানোর একটি কাঠামো:

তুমি প্রোগ্রামিং ভাষার type system আর semantics-এর একজন কড়া পরীক্ষক। নিচে একটি প্রশ্ন, প্রশ্নে দেওয়া নিয়মের তালিকা (নামসহ) আর আমার উত্তর দিলাম। [প্রশ্ন] [নিয়মের তালিকা: T-…, E-…, B-…, H-…] [আমার উত্তর — প্রতিটি লাইন নম্বর দিয়ে] ১. প্রতিটি লাইন কোন নিয়মের instance, শুধু আমার দেওয়া তালিকা থেকে বলো; তালিকার বাইরের কোনো নিয়মের নাম বানাবে না। ২. প্রতিটি নিয়মের premise আর side condition আলাদা করে মিলিয়ে দেখো; কোনটি বাদ পড়েছে, লাইন নম্বর ধরে বলো। ৩. Unification থাকলে প্রতিটি bind-এর আগে occurs check আর walk হয়েছে কি না দেখো। ৪. Induction-এর প্রমাণ হলে কিসের ওপর induction, সব case আছে কি না, আর IH কোথায় খাটানো হয়েছে, বলো। ৫. Semantics হলে evaluation order আর short-circuit প্রশ্নের নিয়ম মেনেছে কি না দেখো; অন্য ভাষার নিয়ম চাপিয়ো না। ৬. আমার যুক্তি কোনো মিথ্যা দাবিও "প্রমাণ" করে কি না, একটি ছোট counterexample দিয়ে দেখাও। ৭. নম্বর-ভাগ বানিয়ে নম্বর দাও; পুরো সঠিক উত্তর নিজে লিখে দিও না। নিশ্চিত না হলে "নিশ্চিত নই" লেখো।

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

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

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

ক্রমএকটি while loop-এর total correctness প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. Invariant I আর variant V বেছে নেওয়া
  2. Init: P থেকে loop-এর আগের অংশ পার হয়ে I সত্য
  3. Preserve: I ∧ শর্ত থেকে দেহের পরে আবার I
  4. Exit: I ∧ ¬শর্ত থেকে Q (দরকারে পরের অংশের wp)
  5. Variant: I ∧ শর্তে V ≥ 0, আর প্রতি ঘোরায় V কমে

(সহজ) Haat-এ Γ = name : Str. print(name + 1); লিখলে type checker কোন নিয়মের কোন premise-এ আটকায়?

  • T-Add-এর প্রথম premise
  • T-Concat-এর দ্বিতীয় premise
  • T-Var-এর side condition
  • T-Print-এর side condition

(মাঝারি) {(t1) → t1 ≐ (Int) → t2}-এর most general unifier কোনটি?

  • t1 = Int, t2 মুক্ত
  • কোনো unifier নেই (clash)
  • t1 = Int, t2 = Int
  • t1 = t2, দুটিই মুক্ত

(মাঝারি) Hindley–Milner-এ let i = λx. x in i i 1 আর λi. i i 1 সম্পর্কে কোনটি ঠিক?

  • প্রথমটির type Int, দ্বিতীয়টি occurs check-এ ব্যর্থ
  • দুটিরই type Int
  • দুটিই occurs check-এ ব্যর্থ
  • প্রথমটি ব্যর্থ, দ্বিতীয়টির type Int

(মাঝারি) ছোট ভাষার progress প্রমাণে T-IfExpr case: t = if t1 then t2 else t3, আর t1 একটি value. পরের লাইনে কোন lemma লাগে?

  • Substitution lemma
  • Inversion lemma
  • Preservation theorem
  • Canonical forms lemma

(মাঝারি) Haat-core-এর small-step-এ ⟨x = (1 + 2) * 4;, {x ↦ 0}⟩ থেকে ⟨skip, {x ↦ 12}⟩ পর্যন্ত কয়টি ধাপ?

  • ২
  • ৩
  • ৪
  • ৬

(কঠিন) Haat-core-এ ভাগ শূন্য দিয়ে হলে runtime error. wp(d = t / k;, d ≥ 0) কোনটি?

  • t / k ≥ 0
  • t ≥ 0 ∧ k > 0
  • k ≠ 0 ∧ t / k ≥ 0
  • d ≥ 0 ∧ k ≠ 0

শব্দকোষ

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

মনে রাখুন

  1. আগে আকার, তারপর নিয়ম: judgment-এর আকার দেখে নিয়মের পরিবার বাছুন, আর প্রতিটি লাইনের পাশে নিয়মের নাম লিখুন।
  2. Premise আর side condition আলাদা: T-Eq-এর τ-তালিকা, T-Assign-এর var, returns(body): বাতিলের কারণ প্রায়ই এগুলোর একটি।
  3. Unification যান্ত্রিক: walk, decompose, bind-এর আগে occurs check; generalise শুধু let-এ।
  4. Soundness দুই পায়ে: progress-এ canonical forms, preservation-এ একই τ; নতুন নিয়ম এলে দুটির নতুন case লিখুন।
  5. অর্থ তিন ভাষায়: ধাপ (⟶), গাছ (⇓), function (⟦·⟧); loop-এর অর্থ least fixpoint, আর Hoare-এ পেছনের দিকে substitution আর চারটি VC. ছোট পরিসরে কোড চালানো ভুল ধরে, প্রমাণ নয়।

পরের পর্বে: পর্ব ৮৬ “ইন্টারভিউ আর প্রতিযোগিতায় ভাষা ও কম্পাইলার — interpreter, parser আর ভাষার খুঁটিনাটি”: এখানকার নিয়ম আর semantics কাজে লাগবে tokenizer, expression evaluator, environment-সহ ছোট interpreter আর stack VM হাতে লেখায়, আর ভাষার খুঁটিনাটির প্রশ্নে।

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

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