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

Typing rule আর type judgment — type checking-এর গণিত

Typing Rules and Type Judgments — the Mathematics of Type Checking

Taught in Bangla, this lesson teaches the notation of type checking: judgments Γ ⊢ e : τ, contexts, inference rules and axioms. It gives the full typing rules for Haat expressions and statements, builds the derivation tree for price(2, 520) + 60 step by step, shows exactly where a derivation gets stuck on an ill-typed program, turns the rules into a syntax-directed checker in in-page Python (Pyodide), and proves uniqueness of types by structural induction, including how an implicit conversion rule breaks it.

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

  • Judgment, context, metavariable, axiom আর inference rule-এর ভাষা পড়া ও লেখা
  • Haat-এর সব expression আর statement-এর typing rule, reference checker-এর কোডের সঙ্গে মিলিয়ে
  • পরীক্ষার ধাঁচে derivation tree আঁকা, আর ভুল program-এ derivation ঠিক কোথায় আটকায় তা দেখানো
  • নিয়মের সেট থেকে syntax-directed checker বানানো, আর কোন নিয়ম এই সরলতা ভাঙে তা চেনা
  • Type-এর অনন্যতা structural induction দিয়ে প্রমাণ করা, আর প্রমাণের প্রতিটি ধাপ কোন নকশা-সিদ্ধান্তের ওপর দাঁড়িয়ে তা বোঝা

১ · Judgment, context আর rule — type checking-এর ভাষা

বাজারঘরের হিসাব-নিরীক্ষক (auditor) মাসের শেষে খাতা দেখছেন। খাতায় লেখা: “অর্ডার ৯৯৬ টাকা”। তিনি এই দাবি এমনি মানবেন না। জানতে চাইবেন: পণ্যের দাম ৯৩৬ টাকার রসিদ কই, ডেলিভারির ৬০ টাকার রসিদ কই? ৯৩৬ টাকার রসিদের পেছনেও আরেকটি কাগজ থাকে: ২টি পণ্য, প্রতিটি ৫২০ টাকা, ১০% ছাড়। শেষে এমন কাগজে পৌঁছান, যা আর কিছুর ওপর নির্ভর করে না: মূল্যতালিকা। পুরো কাগজের গোছাটি হলো দাবির প্রমাণ। গোছার কোনো এক কাগজ না মিললে দাবিটি গৃহীত হয় না, আর নিরীক্ষক ঠিক সেই কাগজটিই দেখিয়ে দেন।

একটি type checker ঠিক এই নিরীক্ষক। পর্ব ৩৩-এ (Type system) দেখেছেন, type system হলো program না চালিয়ে কিছু ভুলের অনুপস্থিতি প্রমাণের পদ্ধতি। এই পর্বে প্রমাণের যন্ত্রটি খুলে দেখব: দাবি কীভাবে লেখা হয়, কোন নিয়মে একটি দাবি থেকে আরেকটি আসে, আর পুরো প্রমাণ দেখতে কেমন। এটিই type checking-এর গণিত, আর পর্ব ৫২-এ (Type checker বাস্তবায়ন) Haat-এর পূর্ণ checker এই নিয়মগুলো থেকেই লেখা হবে।

Judgment — একটি দাবি

Type system-এর মৌলিক দাবিটি হলো typing judgment:

Γ ⊢ e : τ

পড়ুন: “context Γ-তে expression e-এর type τ, এটি প্রমাণ করা যায়”। প্রতিটি চিহ্নের অর্থ:

  • Γ (গামা) হলো typing context: নাম থেকে type-এর একটি তালিকা, যেমন price : (Int, Int) -> Int, free : Bool. এতে কোনো মান নেই, শুধু type. ফাঁকা context লেখা হয় ∅ বা কিছুই না লিখে: ⊢ 2 : Int.
  • ⊢ (turnstile, “টার্নস্টাইল”) মানে “থেকে প্রমাণ করা যায়”। বাঁ পাশে যা ধরে নেওয়া হয়েছে, ডান পাশে যা প্রমাণিত।
  • e একটি expression, আর τ (টাউ) একটি type: Int, Bool, Str, Unit বা (Int, Int) -> Int-এর মতো function type.

Context-এ একই নাম দুবার থাকতে পারে, কারণ Haat-এ ভেতরের block-এ let দিয়ে shadowing চলে। তখন নিয়ম: Γ(x) মানে Γ-তে x-এর সবচেয়ে ডানের (সবশেষে যোগ-করা) ঘোষণা। “Γ, x : τ” লিখলে বোঝায় Γ-এর ডানে x : τ জুড়ে নতুন context. পর্ব ১৫-এর scope chain-এর এটি গাণিতিক রূপ: ভেতরের ঘোষণা আগে খোঁজা হয়।

Inference rule আর axiom

Judgment প্রমাণ হয় inference rule দিয়ে। আপনি পর্ব ০৩, ২০ আর ৩৩-এ কয়েকটি দেখেছেন: দাগের ওপরে premise (শর্ত), নিচে conclusion (সিদ্ধান্ত), ডানে নিয়মের নাম। পড়ার নিয়ম: “ওপরের সবগুলো প্রমাণিত হলে নিচেরটিও প্রমাণিত”। যে নিয়মের দাগের ওপরে কোনো judgment নেই, শুধু হয়তো একটি সাধারণ শর্ত, তাকে বলে axiom: সে নিজে থেকেই প্রমাণ।

n একটি integer literal
Γ ⊢ n : Int
(T-Int)
(x : τ) ∈ Γ
Γ ⊢ x : τ
(T-Var)
Γ ⊢ e1 : Int    Γ ⊢ e2 : Int
Γ ⊢ e1 + e2 : Int
(T-Add)

T-Int আর T-Var axiom: দাগের ওপরে শুধু একটি side condition, অর্থাৎ type-এর দাবি নয় এমন একটি সাধারণ শর্ত (“n একটি literal”, “x : τ আছে Γ-তে”, Γ(x) অর্থে)। T-Add-এর ওপরে দুটি judgment, তাই এটি দুটি ছোট প্রমাণকে জুড়ে একটি বড় প্রমাণ বানায়।

নিয়মে লেখা e1, τ, n, x আসল কোড নয়; এগুলো metavariable, অর্থাৎ “এখানে যেকোনো expression বসান” ধরনের ফাঁকা ঘর। T-Add আসলে অসংখ্য নিয়মের একটি ছাঁচ: e1 = qty, e2 = 60 বসালে পাওয়া যায় “Γ ⊢ qty : Int আর Γ ⊢ 60 : Int হলে Γ ⊢ qty + 60 : Int”. ছাঁচে বসানোকে বলে নিয়মের instance.

সংজ্ঞা ৩৪.১ — well-typed

Context Γ-তে expression e well-typed, যদি কোনো τ-এর জন্য Γ ⊢ e : τ-এর একটি derivation (নিয়ম দিয়ে গড়া প্রমাণ) থাকে। কোনো τ-এর জন্যই derivation না থাকলে e ill-typed, আর checker program বাতিল করে। লক্ষ করুন, সংজ্ঞায় “চালালে কী হয়” নেই: well-typed একটি পুরোপুরি static ধারণা। চালানোর সঙ্গে এর সম্পর্ক (type soundness) পর্ব ৩৮-এর বিষয়।

২ · Haat-এর expression-এর পূর্ণ নিয়ম

এবার Haat v1-এর প্রতিটি expression-এর নিয়ম, একসঙ্গে। আগের পর্বগুলোতে যে নাম পেয়েছেন, সেগুলোই রাখা হলো; যেখানে আগের নিয়মটি একটি বড় নিয়মের একটি রূপ, তা পাশে বলা আছে। Operand-এর নিয়মগুলো reference implementation-এর README-এর spec decision ১১ হুবহু মানে।

Literal আর নাম। Haat-এ Unit-এর কোনো literal নেই (সিদ্ধান্ত ২২), তাই literal-এর নিয়ম তিনটি, আর নামের একটি।

n একটি integer literal
Γ ⊢ n : Int
(T-Int)
b ∈ {true, false}
Γ ⊢ b : Bool
(T-Bool)
s একটি string literal
Γ ⊢ s : Str
(T-Str)
Γ(x) = τ
Γ ⊢ x : τ
(T-Var)

Operator. +-এর দুটি নিয়ম (সংখ্যা যোগ আর লেখা জোড়া)। - * / %-এর একটি সাধারণ নিয়ম T-Arith (পর্ব ৩৩-এর T-Mul এর একটি রূপ), আর < <= > >=-এর T-Cmp (পর্ব ০৩-এর T-Gt আর ৩৩-এর T-Lt এর রূপ)। নিয়মে ⊕ লেখা মানে তালিকার যেকোনো একটি operator.

Γ ⊢ e1 : Int    Γ ⊢ e2 : Int
Γ ⊢ e1 + e2 : Int
(T-Add)
Γ ⊢ e1 : Str    Γ ⊢ e2 : Str
Γ ⊢ e1 + e2 : Str
(T-Concat)
Γ ⊢ e1 : Int    Γ ⊢ e2 : Int    ⊕ ∈ {-, *, /, %}
Γ ⊢ e1 ⊕ e2 : Int
(T-Arith)
Γ ⊢ e1 : Int    Γ ⊢ e2 : Int    ⊕ ∈ {<, <=, >, >=}
Γ ⊢ e1 ⊕ e2 : Bool
(T-Cmp)
Γ ⊢ e1 : τ    Γ ⊢ e2 : τ    τ ∈ {Int, Bool, Str}    ⊕ ∈ {==, !=}
Γ ⊢ e1 ⊕ e2 : Bool
(T-Eq)
Γ ⊢ e1 : Bool    Γ ⊢ e2 : Bool
Γ ⊢ e1 && e2 : Bool
(T-And; ||-এর T-Or একই আকারের)
Γ ⊢ e : Int
Γ ⊢ -e : Int
(T-Neg)
Γ ⊢ e : Bool
Γ ⊢ !e : Bool
(T-Not)

পর্ব ২১-এর T-StrEq হলো T-Eq-এর τ = Str রূপ। T-Eq-এর শর্ত τ ∈ {Int, Bool, Str} বলে দেয় যে function বা Unit তুলনা করা যায় না; reference-এ print(price == price); দিলে সত্যিকারের run-এ আসে operator '==' cannot compare values of type (Int, Int) -> Int. আর T-Cmp-এ Str নেই, তাই "a" < "b" ill-typed.

Function আর call. পর্ব ০৯-এ (Functional programming) দেখা T-Call আর T-Fn, এবার পূর্ণ রূপে। T-Fn-এর premise-এ একটি statement-এর judgment আছে, যার আকার অংশ ৫-এ আসবে; আপাতত পড়ুন “parameter-গুলো Γ-তে যোগ করে দেহ যাচাই করা যায়, আর দরকার হলে প্রতিটি পথ return করে”।

Γ ⊢ f : (τ1, …, τn) -> τ    Γ ⊢ ei : τi (প্রতিটি i = 1…n)
Γ ⊢ f(e1, …, en) : τ
(T-Call)
Γ, x1 : T1, …, xn : Tn ⊢R body ⇒ Γ′    R = Unit অথবা returns(body)
Γ ⊢ fn(x1: T1, …, xn: Tn) -> R { body } : (T1, …, Tn) -> R
(T-Fn)

T-Call-এ argument-এর সংখ্যা n দুই জায়গাতেই এক, তাই half(1, 2)-এর মতো ভুল সংখ্যার call-এর কোনো instance নেই; reference বার্তা দেয় expected 1 argument, found 2. T-Fn-এর ফলের type পুরোটাই লেখা annotation থেকে আসে, দেহ থেকে নয়; অংশ ৬-এ দেখবেন এই ছোট বিষয়টিই অনন্যতার প্রমাণের চাবি।

নিয়মtypechecker.py-এ কোথায়কী করে
T-Int, T-Str, T-Boolexpr()-এর প্রথম তিনটি ifসরাসরি INT, STR, BOOL ফেরত
T-Varexpr(): b.typeresolver যে ঘোষণা খুঁজে দিয়েছে, তার type
T-Neg, T-Notexpr(): Unaryoperand-এর type যাচাই, ফল INT বা BOOL
T-Add … T-Orbinary()দুই পাশের type বের করে operator অনুযায়ী মেলানো
T-Callcall()callee-র FnType, argument-এর সংখ্যা আর প্রতিটির type
T-Fnfunction(), fn_type()parameter যোগ, দেহ যাচাই, missing return

একটি পার্থক্য খেয়াল করুন। নিয়মে Γ একটি তালিকা যা হাতে হাতে ঘোরে; reference-এ এমন কোনো তালিকা নেই। Resolver (পর্ব ৫১-এ বিস্তারিত) আগেই প্রতিটি নাম-ব্যবহারকে তার ঘোষণার Binding-এর সঙ্গে জুড়ে দেয়, আর checker ঘোষণা পার হওয়ার সময় সেই Binding-এ .type লিখে রাখে। ফল একই: “Γ-এর সবচেয়ে ডানের x” খোঁজার কাজটি resolver scope-এর নিয়মে আগেই করে রেখেছে। Use-before-declaration (সিদ্ধান্ত ১৬) বা অজানা নামের ভুলও তাই type-এর নিয়মের আগে resolver-ই ধরে।

৩ · Derivation tree — দাবির পেছনের পুরো প্রমাণ

একটি নিয়মের premise প্রমাণ করতে আরেকটি নিয়ম লাগে, তার premise-এর জন্য আরেকটি, যতক্ষণ না axiom-এ পৌঁছানো যায়। এই প্রয়োগগুলো একসঙ্গে সাজালে পাওয়া যায় একটি গাছ: derivation tree. মূল দাবি গাছের গোড়ায়, নিচে; axiom-গুলো পাতায়, সবার ওপরে। নিরীক্ষকের কাগজের গোছাটি এটাই।

ছবি ৩৪.১ — price(2, 520) + 60-এর derivation tree

Γ = price : τp, যেখানে τp = (Int, Int) -> Int. প্রতিটি বাক্সের আগে “Γ ⊢” ধরে নিন; তির মানে “ওপরের বাক্সগুলো মিলে নিচেরটি প্রমাণ করে”

Derivation tree of price(2, 520) + 60 : Int with T-Add, T-Call, T-Var and T-Int (price : τₚ) ∈ Γ price : τₚ T-Var 2 : Int T-Int 520 : Int T-Int price(2, 520) : Int T-Call 60 : Int T-Int price(2, 520) + 60 : Int T-Add

সবুজ বাক্সগুলো axiom-এর প্রয়োগ (পাতা), নীল আর হলুদ দুটি premise-ওয়ালা নিয়ম। পরীক্ষার খাতায় একই গাছ লেখা হয় দাগ টেনে, premise ওপরে আর সিদ্ধান্ত নিচে; ছবিটি সেই লেখারই বাক্স-রূপ। কিন্তু checker গাছটি কোন ক্রমে গড়ে? নিচের stepper-এ ধাপে ধাপে দেখুন। বাঁ পাশের লেখাটি সম্পূর্ণ গাছ, ওপরে মূল দাবি আর ভেতরের দিকে premise (পরের Python block ঠিক এই আকারেই ছাপে)।

1Γ ⊢ price(2, 520) + 60 : Int2  Γ ⊢ price(2, 520) : Int3    Γ ⊢ price : τₚ4    Γ ⊢ 2 : Int5    Γ ⊢ 520 : Int6  Γ ⊢ 60 : Int
Checker-এর অবস্থা
লক্ষ্য
নিয়ম
প্রমাণিত
  1. গোড়া থেকে শুরু। লক্ষ্য Γ ⊢ price(2, 520) + 60 : ?. গঠন e1 + e2, তাই দুটি নিয়ম সম্ভব: T-Add আর T-Concat. কোনটি, তা ঠিক হবে বাঁ পাশের type দেখে, তাই checker আগে বাঁ দিকে যায়।
  2. Call-এর গঠন। নতুন লক্ষ্য Γ ⊢ price(2, 520) : ?. এই গঠনের নিয়ম একটিই, T-Call. তার premise তিনটি: callee-র type, আর প্রতিটি argument-এর type.
  3. প্রথম পাতা। price একটি নাম, তাই T-Var. Side condition: Γ-তে খুঁজে পাওয়া গেল τp = (Int, Int) -> Int. এটি axiom, ওপরে আর কিছু লাগে না। প্রমাণিত judgment ১টি।
  4. দুটি argument. T-Int দিয়ে 2 : Int আর 520 : Int. T-Call চায় ei-এর type হুবহু parameter-এর τi: দুটিই Int, মিলেছে। আরও দুটি axiom, মোট ৩টি।
  5. T-Call-এর সিদ্ধান্ত। সব premise প্রমাণিত, তাই নিচের সারি: Γ ⊢ price(2, 520) : Int, ফলের type τp-এর শেষ অংশ থেকে। মোট ৪টি।
  6. নিয়ম বাছাই। বাঁ পাশ Int, তাই T-Concat অসম্ভব (সে চায় Str); বাকি থাকে T-Add, যার দ্বিতীয় premise Γ ⊢ 60 : Int. T-Int দিয়ে প্রমাণিত, মোট ৫টি।
  7. গাছ সম্পূর্ণ। T-Add-এর দুটি premise-ই আছে, তাই Γ ⊢ price(2, 520) + 60 : Int. মোট ৬টি judgment, তার ৪টি axiom, আর গাছের উচ্চতা ৩. Reference-এ এই expression ছাপালে সত্যিকারের run-এ আসে 996, bazar.haat-এর প্রথম লাইন।

খেয়াল করুন checker-এর চলার দিক: সে লক্ষ্য নিয়ে নিচ থেকে ওপরে যায় (কোন নিয়ম? তার premise কী?), আর প্রমাণ ফেরে ওপর থেকে নিচে (পাতা থেকে গোড়ায়)। নিচের block একটি ছোট derivation printer: প্রতিটি নিয়ম derive()-এর একটি শাখা, আর ফল একটি গাছ, যা tree() ভেতরের দিকে সরিয়ে ছাপে। দ্বিতীয় উদাহরণে একটি ভুল আছে; দেখুন গাছ কোথায় আটকায়। পূর্ণ রূপ reference-এর typechecker.py-এর expr(), binary() আর call().

# Haat expression-এর derivation tree: প্রতিটি নিয়ম derive()-এর একটি শাখা
# AST: ("int", n) ("bool", b) ("var", x) ("bin", op, l, r) ("call", f, [args])
def show(t): return t if isinstance(t, str) else f"({', '.join(map(show, t[0]))}) -> {show(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"{src(e[1])}({', '.join(map(src, e[2]))})"
    return f'"{e[1]}"' if e[0] == "str" else str(e[1]).lower()
def pick(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 if lt in ("Int", "Bool", "Str") else "Int/Bool/Str", "Bool")
    if op in ("&&", "||"): return ("T-And" if op == "&&" else "T-Or", "Bool", "Bool")
    return ("T-Cmp", "Int", "Bool") if op in ("<", "<=", ">", ">=") else ("T-Arith", "Int", "Int")
LIT = {"int": ("Int", "T-Int"), "bool": ("Bool", "T-Bool"), "str": ("Str", "T-Str")}
def derive(G, e):        # ফেরত: (e, type, নিয়ম, premise-গুলো); আটকালে type = None
    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]]
        for a, want in zip(args, f[1][0]):             # f-এর type: (param-গুলো, ফল)
            if a[1] != want: return (e, None, f"✗ T-Call: expected {want}, found {a[1]}", [f, *args])
        return (e, f[1][1], "T-Call", [f, *args])
    l, r = derive(G, e[2]), derive(G, e[3])
    if None in (l[1], r[1]): return (e, None, "✗ নিচে কোথাও আটকে আছে", [l, r])
    rule, want, out = pick(e[1], l[1])
    bad = [x[1] for x in (l, r) if x[1] != want]
    if bad: return (e, None, f"✗ {rule}: expected {want}, found {show(bad[0])}", [l, r])
    return (e, out, rule, [l, r])
def tree(d, pad=""):
    e, t, rule, kids = d
    print(f"{pad}Γ ⊢ {src(e)} : {show(t) if t else '?'}   [{rule}]")
    for k in kids: tree(k, pad + "   ")
G = {"price": (("Int", "Int"), "Int"), "free": "Bool"}
call = ("call", ("var", "price"), [("int", 2), ("int", 520)])
tree(derive(G, ("bin", "+", call, ("int", 60))))
print("---"); tree(derive(G, ("bin", "+", call, ("var", "free"))))

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

Γ ⊢ price(2, 520) + 60 : Int   [T-Add]
   Γ ⊢ price(2, 520) : Int   [T-Call]
      Γ ⊢ price : (Int, Int) -> Int   [T-Var]
      Γ ⊢ 2 : Int   [T-Int]
      Γ ⊢ 520 : Int   [T-Int]
   Γ ⊢ 60 : Int   [T-Int]
---
Γ ⊢ price(2, 520) + free : ?   [✗ T-Add: expected Int, found Bool]
   Γ ⊢ price(2, 520) : Int   [T-Call]
      Γ ⊢ price : (Int, Int) -> Int   [T-Var]
      Γ ⊢ 2 : Int   [T-Int]
      Γ ⊢ 520 : Int   [T-Int]
   Γ ⊢ free : Bool   [T-Var]

প্রথম গাছটি ছবি ৩৪.১-এর সঙ্গে হুবহু এক: ৬টি judgment, একই নিয়ম। দ্বিতীয় গাছে ডান পাশের পাতা আছে (Γ ⊢ free : Bool), বাঁ পাশের পুরো শাখাও আছে, কিন্তু গোড়ায় কোনো নিয়ম খাটে না: বাঁ পাশ Int বলে T-Add বাছা হলো, আর T-Add-এর দ্বিতীয় premise চায় free : Int. Type-এর জায়গায় ? মানে derivation নেই। একটি ব্যাপার লক্ষ করুন: কোড একটি গাছ ফেরত দেয়, শুধু “ঠিক/ভুল” নয়। Compiler-এর ভেতরে এই গাছটির বাস্তব রূপ হলো type-লেখা AST: প্রতিটি node-এর পাশে তার type, যা পরের ধাপের (bytecode বা IR তৈরির) কাজে লাগে।

৪ · নিয়ম থেকে algorithm — syntax-directed type checking

নিয়মগুলো গণিতের ভাষায় লেখা: কোন judgment সত্য, শুধু তা বলে, কীভাবে খুঁজতে হবে তা বলে না। তবু ওপরের Python block-টি প্রায় সরাসরি নিয়ম থেকে লেখা গেল। কারণ Haat-এর নিয়মের সেটটি syntax-directed: যেকোনো expression-এর বাইরের গঠন (literal, নাম, +, call …) দেখলেই বোঝা যায় কোন নিয়ম খাটবে। তখন নিয়মগুলোকে উল্টো দিক থেকে, নিচ থেকে ওপরে পড়লেই algorithm:

  1. Input আর output ঠিক করা। Γ আর e input, τ output: check(Γ, e) → τ. একে বলে নিয়মের mode.
  2. প্রতিটি নিয়ম একটি শাখা। Conclusion-এর গঠন অনুযায়ী if/match-এর একটি শাখা।
  3. প্রতিটি premise একটি recursive call. Γ ⊢ e1 : Int মানে check(Γ, e1) চালিয়ে ফলটি Int কি না দেখা।
  4. প্রতিটি side condition একটি সাধারণ যাচাই। (x : τ) ∈ Γ মানে dictionary lookup; τ ∈ {Int, Bool, Str} মানে একটি set-এ আছে কি না।
  5. কোনো শাখা না মিললে error. কোনো derivation নেই, তাই program ill-typed; কোন premise ব্যর্থ হলো, সেটিই error message.

দুটি জায়গায় একটু ভাবতে হয়। +-এর নিয়ম দুটি, কিন্তু দুটির প্রথম premise আলাদা type চায়; তাই বাঁ পাশের type বের করলেই একটি বাদ পড়ে (সিদ্ধান্ত ১১: “the left operand decides”). আর T-Eq-এর premise-এ τ আছে কিন্তু conclusion-এ নেই: নিয়মটি পড়ে মনে হয় τ আন্দাজ করতে হবে। Algorithm আন্দাজ করে না; বাঁ পাশের type বের করে সেটিকেই τ ধরে, তারপর ডান পাশকে তার সঙ্গে মেলায়। T-Call-এর τi-ও তেমনি আসে f-এর type থেকে।

সব নিয়মের সেট এত ভদ্র হয় না। পর্ব ৩৬-এ (Polymorphism) subtyping-এর subsumption নিয়ম (T-Sub) দেখবেন: “Γ ⊢ e : S আর S <: T হলে Γ ⊢ e : T”. এর conclusion-এ e যেকোনো গঠনের হতে পারে, তাই গঠন দেখে আর নিয়ম বাছা যায় না, আর checker-কে ঠিক করতে হয় কোথায় T-Sub বসাবে। আবার annotation ছাড়া fn(x) { return x; }-এ x-এর type কোথাও লেখা নেই; তা বের করতে লাগে type inference (পর্ব ৩৫)। Haat v1 এই দুটিই এড়িয়েছে, আর তাতেই checker একটি সরল recursive function.

যেখানে derivation আটকে যায়

ভুল program-এ checker কী করে, এবার ধাপে ধাপে দেখি। নিচের program-এ লেখক ভেবেছিলেন free একটি ডেলিভারি চার্জ, অথচ সেটি আসলে একটি Bool:

6let total = 936;7let free = total >= 1000;8print(price(2, 520) + free);
Checker-এর অবস্থা
Γ-তে
লক্ষ্য
নিয়ম
  1. Γ গড়ে ওঠে। লাইন ৭-এ total >= 1000: T-Cmp দিয়ে Bool, তাই T-Let Γ-তে যোগ করে free : Bool. এখানে কোনো ভুল নেই; নামটিই শুধু বিভ্রান্তিকর।
  2. Print-এর premise. লাইন ৮ একটি print statement. তার নিয়ম (অংশ ৫) চায় ভেতরের expression-এর একটি type, যা Int, Bool বা Str. লক্ষ্য: Γ ⊢ price(2, 520) + free : ?.
  3. বাঁ শাখা ঠিক আছে। আগের stepper-এর মতোই T-Call দিয়ে Γ ⊢ price(2, 520) : Int. এই অংশের derivation সম্পূর্ণ।
  4. নিয়ম একটিই বাকি। বাঁ পাশ Int, তাই T-Concat-এর প্রথম premise (Str) অসম্ভব। বাকি T-Add, যার দ্বিতীয় premise: Γ ⊢ free : Int.
  5. পাতায় অমিল। free একটি নাম, আর নামের নিয়ম একটিই, T-Var, যা দেয় Γ(free) = Bool. Bool থেকে Int বানানোর কোনো নিয়ম Haat-এ নেই (কোনো implicit conversion নেই)। তাই Γ ⊢ free : Int-এর কোনো derivation সম্ভব নয়: গাছ এখানেই আটকে গেল।
  6. Error message = ব্যর্থ premise. Reference checker ঠিক এই premise-টিই জানায়, ভুল expression-এর শুরুতে (সিদ্ধান্ত ২৪): free শুরু হয় লাইন ৮-এর কলাম ২৩-এ। “expected Int” আসে T-Add-এর premise থেকে, “found Bool” আসে T-Var থেকে। এটি reference-এর সত্যিকারের run.

একটি ভুল থেকে একটিই বার্তা কেন, দুটি নয়? +-এর type পাওয়া গেল না, তাহলে print-এর premise-ও তো ব্যর্থ। Reference-এর typechecker.py এখানে একটি কৌশল নেয়: ব্যর্থ sub-expression-এর type হয় None, আর None সবখানে গ্রহণযোগ্য, যেন “এর বিষয়ে আগেই বলা হয়েছে”। বাস্তবে +-এর ফল হিসেবে সে Int ধরে নেয়, তাই print আপত্তি করে না। এতে এক ভুল থেকে বার্তার ঢল (cascade) নামে না। গণিতের নিয়মে এমন কিছু নেই; এটি বাস্তব checker-এর error recovery, পর্ব ৫০-এর parser recovery-র type-জগতের আত্মীয়।

৫ · Statement-এর judgment — Γ বদলায়, return মেলে

Haat-এ if, while, let, print, assignment সবই statement (print আর assignment-এর কথা reference-এর সিদ্ধান্ত ৮ আর ৯ স্পষ্ট বলে; বাকিগুলো grammar-এই statement): এরা কোনো মান দেয় না। তাই এদের জন্য Γ ⊢ e : τ আকারের judgment খাটে না; লাগে নতুন আকার:

Γ ⊢ρ s ⇒ Γ′

পড়ুন: “যে function-এর ফেরত-type ρ (রো), তার ভেতরে context Γ-তে statement s সঠিক, আর s-এর পরে context হয় Γ′”। দুটি নতুন অংশ। Γ′ লাগে কারণ let পরের statement-গুলোর জন্য একটি নাম যোগ করে; Γ শুধু expression-এর জন্য স্থির, statement-এর ক্রম ধরে সে বদলায়। ρ লাগে কারণ return e; সঠিক কি না, তা নির্ভর করে কোন function-এর ভেতরে আছি তার ওপর। Top level-এ ρ নেই (লেখা হয় —), আর সেখানে return resolver-ই বাতিল করে (সিদ্ধান্ত ২০)।

Γ ⊢ e : τ
Γ ⊢ρ let x = e; ⇒ Γ, x : τ
(T-Let)
Γ ⊢ e : T
Γ ⊢ρ let x: T = e; ⇒ Γ, x : T
(T-LetAnn)
Γ(x) = τ    x একটি var    Γ ⊢ e : τ
Γ ⊢ρ x = e; ⇒ Γ
(T-Assign)
Γ ⊢ e : Bool    Γ ⊢ρ B1 ⇒ Γ1    Γ ⊢ρ B2 ⇒ Γ2
Γ ⊢ρ if e B1 else B2 ⇒ Γ
(T-If)
Γ ⊢ e : Bool    Γ ⊢ρ B ⇒ Γ1
Γ ⊢ρ while e B ⇒ Γ
(T-While)
Γ ⊢ e : ρ
Γ ⊢ρ return e; ⇒ Γ
(T-Return; return; চায় ρ = Unit)
Γ ⊢ e : τ    τ ∈ {Int, Bool, Str}
Γ ⊢ρ print(e); ⇒ Γ
(T-Print)
Γ ⊢ρ s1 ⇒ Γ1    Γ1 ⊢ρ s2 ⇒ Γ2   …   Γn−1 ⊢ρ sn ⇒ Γn
Γ ⊢ρ { s1 … sn } ⇒ Γ
(T-Block)

var-এর নিয়ম T-Let-এর মতোই, শুধু Γ-তে নামটির পাশে “var” চিহ্ন থাকে, যা T-Assign-এর side condition দেখে (সিদ্ধান্ত ১৯: শুধু var-এ assignment; parameter আর function-এর নাম অপরিবর্তনীয়)। Expression statement e;-এর নিয়ম শুধু চায় e-এর কোনো একটি type থাকুক; মানটি ফেলে দেওয়া হয় (সিদ্ধান্ত ২২)। আর T-Let-এ τ-এর কোনো বাধা নেই, তাই Unit ফেরত দেওয়া function-এর ফলও let-এ রাখা যায়।

তিনটি নিয়মে Γ′ ফেলে দেওয়া হয়েছে: T-If, T-While আর T-Block-এর conclusion-এ ডানে আবার Γ, ভেতরের Γ1, Γn নয়। এটিই block scope-এর গণিত: if c { let d = 60; } else { let d = 0; }-এর পরে d আর Γ-তে নেই। Reference-এ এর পরে print(d); লিখলে সত্যিকারের run-এ আসে 3:7: error: undefined variable 'd'.

If: statement না expression?

Haat-এর if একটি statement, তাই T-If দুই শাখার type মেলানোর কথা তোলেই না। যে ভাষায় if একটি expression (OCaml, Rust, Kotlin; পর্ব ৩৩-এর ছোট ভাষাটিও), সেখানে নিয়ম আলাদা:

Γ ⊢ e1 : Bool    Γ ⊢ e2 : τ    Γ ⊢ e3 : τ
Γ ⊢ if e1 then e2 else e3 : τ
(T-IfExpr)

একই τ দুই শাখায়, কারণ চালানোর আগে জানা নেই কোন শাখা নেওয়া হবে, অথচ পুরো expression-এর জন্য একটিই type দিতে হবে। Rust-এ else ছাড়া if-এর type তাই () (Rust-এর Unit). Statement-ভিত্তিক নকশার সুবিধা নিয়মের সরলতা; দাম হলো ছোট শর্তসাপেক্ষ মানের জন্যও var আর দুটি assignment লাগে। ভাবনার প্রশ্ন ৪-এ দুই পথের তুলনা আছে।

Function, return আর missing return

Γ′ = Γ, f : (T1, …, Tn) -> R    Γ′, x1 : T1, …, xn : Tn ⊢R body ⇒ Γ″    R = Unit অথবা returns(body)
Γ ⊢ρ fn f(x1: T1, …) -> R { body } ⇒ Γ′
(T-FnDecl)

লক্ষ করুন দেহের judgment-এ নিচের ছোট অক্ষর R: বাইরের ρ নয়, নিজের ফেরত-type. Nested function-এর ভেতরের return তাই নিজের function-এর সঙ্গেই মেলে। Γ′-এ f নিজে আছে বলে দেহের ভেতর থেকে নিজেকে ডাকা যায় (recursion, সিদ্ধান্ত ১৭)। Top-level function-গুলো hoisted, তাই program-এর শুরুর context Γ0-তেই সবগুলো top-level function-এর type থাকে; mutual recursion তাই চলে। আর parameter আর দেহের প্রথম স্তর একই scope ভাগ করে (সিদ্ধান্ত ১৪), তাই দেহের statement-গুলো সরাসরি T-Block দিয়ে নয়, statement-এর ক্রম হিসেবে যাচাই হয়।

তৃতীয় premise returns(body) একটি আলাদা, সম্পূর্ণ syntactic judgment (সিদ্ধান্ত ২১): একটি statement-তালিকা “return করে”, যদি তাতে থাকে একটি return, বা একটি block যা return করে, বা একটি if যার else আছে আর দুই শাখাই return করে। while কখনো গোনা হয় না, এমনকি while true-ও নয়। এটি type-এর নিয়ম নয়, কারণ এখানে কোনো type নেই; কিন্তু এটি না থাকলে fn half(n: Int) -> Int { if n > 0 { return n / 2; } } শূন্য বা ঋণাত্মক n-এ কোনো Int ফেরত না দিয়েই শেষ হতো, অথচ type বলত Int. নিয়মটি রক্ষণশীল: while true { return a; } কখনো return ছাড়া শেষ হয় না, তবু বাতিল; পর্ব ৩৩-এ দেখা “নিরাপদ কিন্তু অসম্পূর্ণ” checker-এর আরেকটি নমুনা।

1fn price(qty: Int, unit: Int) -> Int {2    let p = qty * unit;3    if p >= 1000 { return p - p / 10; }4    return p;5}
Judgment-এর অংশ
Γ-এর শেষে
ρ
নিয়ম
  1. শুরুর context. bazar.haat-এর দুটি top-level function hoisted (সিদ্ধান্ত ১৭), তাই কোনো statement যাচাইয়ের আগেই Γ0 = price : τp, delivery : (Int) -> Int. Top level-এ ρ নেই।
  2. Function-এ ঢোকা। T-FnDecl: দেহের জন্য Γ1 = Γ0, qty : Int, unit : Int, আর ρ = Int, লেখা ফেরত-type থেকে। Parameter-এর type annotation থেকে আসে, আন্দাজ নয়।
  3. Let যোগ করে। qty * unit: T-Arith, দুটি T-Var-এর premise Int, ফল Int. T-Let তাই Γ2 = Γ1, p : Int. এখন থেকে পরের সব statement p দেখে।
  4. শর্ত আর শাখা। p >= 1000: T-Cmp দিয়ে Bool, T-If-এর প্রথম premise পূর্ণ। then-block যাচাই হয় Γ2-তে; else নেই, তাই দ্বিতীয় শাখা ফাঁকা।
  5. ভেতরের return. p - p / 10: দুবার T-Arith, ফল Int, আর ρ = Int: T-Return ✓. Block শেষ; ভেতরে কিছু যোগ হয়নি, আর হলেও বাইরে আসত না।
  6. বাইরের return. return p;: T-Var দেয় Γ2(p) = Int = ρ ✓. Context তখনও Γ2.
  7. Missing return-এর যাচাই। দেহের তালিকায় একটি return আছে, তাই returns(body) সত্য (সিদ্ধান্ত ২১)। T-FnDecl-এর তিনটি premise-ই পূর্ণ। দেহের Γ2 ফেলে দেওয়া হয়; বাইরে ফিরে context আবার Γ0, আর p কোথাও দেখা যায় না।

এবার statement-এর নিয়মগুলো কোডে। এই block আগের block-এর derive() আর show() ব্যবহার করে (দুটি একই namespace-এ চলে; এটি আগে চাপলে আগেরটিও নিজে থেকে চলবে)। stmt() প্রতিটি statement-এর জন্য নতুন Γ′ ফেরত দেয়, block() Γ ধাপে ধাপে বাড়িয়ে নিয়ে যায়, আর returns() সিদ্ধান্ত ২১-এর syntactic নিয়ম। Error message reference-এর বার্তার সঙ্গে হুবহু মিলিয়ে লেখা।

# Statement-এর judgment  Γ ⊢ρ s ⇒ Γ′  (আগের block-এর derive() আর show() কাজে লাগে)
def stmt(G, s, rho, errs):            # ফেরত: পরের statement-এর জন্য Γ′
    k, ty = s[0], (lambda e: derive(G, e)[1]); expect = lambda want, got: got == want or errs.append(f"type mismatch: expected {show(want)}, found {show(got)}")
    if k in ("let", "var"):           # ("let", নাম, annotation বা None, e)    T-Let
        t = ty(s[3])
        if s[2]: expect(s[2], t); t = s[2]
        print(f"   Γ-তে যোগ: {s[1]} : {show(t)}"); return {**G, s[1]: t}
    if k == "assign": expect(G[s[1]], ty(s[2]))                        # T-Assign
    elif k in ("if", "while"):                                         # T-If, T-While
        expect("Bool", ty(s[1]))
        for body in s[2:]: block(G, body, rho, errs)      # ভেতরের Γ′ ফেলে দেওয়া হয়
    elif k == "return": expect(rho, ty(s[1]) if len(s) > 1 else "Unit")    # T-Return
    elif k == "print" and ty(s[1]) not in ("Int", "Bool", "Str"):       # T-Print
        errs.append(f"cannot print a value of type {show(ty(s[1]))}")
    elif k == "fn":                   # ("fn", নাম, [(x, T)…], R, body)       T-FnDecl
        ft = (tuple(t for _, t in s[2]), s[3]); G = {**G, s[1]: ft}
        print(f"   {s[1]}: ρ = {s[3]}, Γ-তে যোগ: " + ", ".join(f"{x} : {t}" for x, t in s[2]))
        block({**G, **dict(s[2])}, s[4], s[3], errs)
        if s[3] != "Unit" and not returns(s[4]): errs.append(f"missing return: not every path of function '{s[1]}' returns {s[3]}")
    return G
def block(G, ss, rho, errs):
    for s in ss: G = stmt(G, s, rho, errs)
def returns(ss):                      # সিদ্ধান্ত ২১-এর syntactic নিয়ম
    return any(s[0] == "return" or (s[0] == "if" and len(s) == 4 and returns(s[2]) and returns(s[3])) for s in ss)
V = lambda x: ("var", x); I = lambda n: ("int", n); B = lambda o, l, r: ("bin", o, l, r)
price = ("fn", "price", [("qty", "Int"), ("unit", "Int")], "Int", [
    ("let", "p", None, B("*", V("qty"), V("unit"))),
    ("if", B(">=", V("p"), I(1000)), [("return", B("-", V("p"), B("/", V("p"), I(10))))]),
    ("return", V("p"))])
half = ("fn", "half", [("n", "Int")], "Int", [("if", B(">", V("n"), I(0)), [("return", B("/", V("n"), I(2)))])])
yes = ("fn", "yes", [("n", "Int")], "Int", [("return", ("bool", True))])
bad = [("var", "total", None, I(0)), ("assign", "total", ("str", "996")),
       ("fn", "log", [("msg", "Str")], "Unit", [("print", V("msg"))]), ("print", ("call", V("log"), [("str", "x")]))]
for name, prog in [("price", [price]), ("half", [half, yes]), ("bad", bad)]:
    print(name); errs = []; block({}, prog, None, errs); print("  ", errs or "ok")

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

price
   price: ρ = Int, Γ-তে যোগ: qty : Int, unit : Int
   Γ-তে যোগ: p : Int
   ok
half
   half: ρ = Int, Γ-তে যোগ: n : Int
   yes: ρ = Int, Γ-তে যোগ: n : Int
   ["missing return: not every path of function 'half' returns Int", 'type mismatch: expected Int, found Bool']
bad
   Γ-তে যোগ: total : Int
   log: ρ = Unit, Γ-তে যোগ: msg : Str
   ['type mismatch: expected Int, found Str', 'cannot print a value of type Unit']

price-এর trace stepper-এর ধাপগুলোর সঙ্গে মেলে: প্রথমে parameter, তারপর p, আর শেষে ok. বাকি চারটি ভুল একই রূপে Haat-এ লিখে (fn half…, fn yes(n: Int) -> Int { return true; }, var total = 0; total = "996";, fn log(msg: Str) { print(msg); } print(log("x"));) reference-এর check চালানো হয়েছে, সত্যিকারের run:

1:4: error: missing return: not every path of function 'half' returns Int
4:32: error: type mismatch: expected Int, found Bool
6:9: error: type mismatch: expected Int, found Str
8:7: error: cannot print a value of type Unit

চারটি বার্তার লেখা হুবহু এক; reference শুধু অবস্থান যোগ করে। log-এর ফল Unit, কারণ -> T না লিখলে ফেরত-type Unit (সিদ্ধান্ত ২৩-এর মতোই declaration-এ), আর T-Print-এর side condition Unit মানে না (সিদ্ধান্ত ৮)। সরলতার জন্য block-টি দুটি জিনিস বাদ দিয়েছে: var চিহ্ন (assignment-এর অনুমতি resolver দেখে) আর returns()-এ ভেতরের plain block.

৬ · Type-এর অনন্যতা — induction দিয়ে প্রথম প্রমাণ

ওপরের checker প্রতিটি expression-এর জন্য একটি type ফেরত দেয়। কিন্তু নিয়মগুলো তো একটি সম্পর্ক, function নয়: কোনো expression-এর জন্য কি দুটি আলাদা derivation দুটি আলাদা type দিতে পারে? Haat-এ পারে না, আর এটিই এই পর্বের প্রথম theorem.

Theorem ৩৪.১ — type-এর অনন্যতা (uniqueness of types)

যেকোনো Γ আর e-এর জন্য: Γ ⊢ e : τ1 আর Γ ⊢ e : τ2 দুটিই derivable হলে τ1 = τ2.

প্রমাণ e-এর গঠনের ওপর structural induction দিয়ে (পূর্ণ সংখ্যার induction-এর গাছ-রূপ; Discrete Mathematics-এর পর্ব ১০-এ induction-এর ভিত্তি)। Induction hypothesis (IH): e-এর প্রতিটি অংশ-expression-এর জন্য, যেকোনো context-এ, theorem সত্য। দুটি derivation D1 আর D2 নিই, যাদের সিদ্ধান্ত যথাক্রমে Γ ⊢ e : τ1 আর Γ ⊢ e : τ2; দুটির শেষ (সবচেয়ে নিচের) নিয়ম দেখি।

  1. e একটি literal. Integer literal-এর conclusion আছে শুধু T-Int-এ, তাই দুটি derivation-ই T-Int দিয়ে শেষ, আর τ1 = τ2 = Int. T-Bool আর T-Str একই রকম।
  2. e = x. নামের নিয়ম শুধু T-Var, যার type Γ(x). Γ(x) মানে “সবচেয়ে ডানের ঘোষণা”, তাই একটি নির্দিষ্ট মান: τ1 = Γ(x) = τ2.
  3. e = -e′ বা !e′. একটিই নিয়ম (T-Neg বা T-Not), যার ফল নির্দিষ্ট: Int বা Bool.
  4. e = e1 + e2. দুটি নিয়ম সম্ভব। দুটি derivation একই নিয়মে শেষ হলে ফল একই (দুটির ফলই নির্দিষ্ট: Int বা Str). ধরুন D1 T-Add আর D2 T-Concat দিয়ে শেষ। তাহলে D1-এর ভেতরে আছে Γ ⊢ e1 : Int, আর D2-এর ভেতরে Γ ⊢ e1 : Str. e1-এ IH খাটালে Int = Str, যা অসম্ভব। তাই এই মিশ্র ক্ষেত্র ঘটতেই পারে না।
  5. e = e1 ⊕ e2, বাকি operator. প্রতিটির একটিই নিয়ম, আর ফলের type operator থেকেই ঠিক: T-Arith-এ Int, T-Cmp, T-Eq, T-And, T-Or-এ Bool.
  6. e = f(e1, …, en). একটিই নিয়ম, T-Call. D1-এ Γ ⊢ f : σ1, D2-এ Γ ⊢ f : σ2, আর τ1, τ2 যথাক্রমে σ1, σ2-এর ফল-অংশ। f-এ IH খাটালে σ1 = σ2, তাই τ1 = τ2.
  7. e = fn(x1: T1, …) -> R { body }. একটিই নিয়ম, T-Fn, আর তার conclusion-এর type (T1, …, Tn) -> R পুরোটাই e-এর লেখা annotation; দেহের derivation যা-ই হোক, type বদলায় না। তাই τ1 = τ2. ∎

প্রমাণটি পড়লে বোঝা যায়, অনন্যতা কোনো প্রাকৃতিক সত্য নয়, তিনটি নকশা-সিদ্ধান্তের ফল। এক, প্রতিটি গঠনের নিয়ম প্রায় একটি, আর যেখানে দুটি (+), সেখানে premise-এর type তাদের আলাদা করে। দুই, ধাপ ৭: anonymous function-এর parameter-এ annotation বাধ্যতামূলক; না থাকলে fn(x) { return x; }-এর type হতে পারত (Int) -> Int, (Bool) -> Bool, যেকোনো (τ) -> τ. তিন, কোনো implicit conversion বা subsumption-এর নিয়ম নেই, যা যেকোনো গঠনে বসে type বদলাতে পারে। পর্ব ৩৫-এ দ্বিতীয়টি আর পর্ব ৩৬-এ তৃতীয়টি ইচ্ছা করে ভাঙা হবে, আর তখন “একটিমাত্র type”-এর বদলে আসবে “সবচেয়ে সাধারণ type” (principal type) বা “সবচেয়ে ছোট type”-এর ধারণা।

তৃতীয় সিদ্ধান্তটি চালিয়ে পরীক্ষা করা যায়। নিচের block নিয়মগুলোকে syntax-directed না ধরে, “প্রতিটি নিয়ম চেষ্টা করো, যত type পাওয়া যায় সব রাখো” ভঙ্গিতে লেখে। তারপর ৬টি পাতা আর ৫টি operator দিয়ে তিন স্তর পর্যন্ত সব expression বানিয়ে গোনে কোনটির কয়টি type. দ্বিতীয়বার একটি C-ধাঁচের বাড়তি নিয়ম যোগ হয়: “যার type Bool, তার type Int-ও”।

# Type-এর অনন্যতা পরীক্ষা: প্রতিটি নিয়ম চেষ্টা করে e-এর সম্ভাব্য সব type বের করা
G3 = {"x": "Int", "b": "Bool", "s": "Str"}
ATOMS = [("int", 1), ("bool", True), ("str", "a"), ("var", "x"), ("var", "b"), ("var", "s")]
OPS = ["+", "-", "<", "==", "&&"]
def types(e, coerce):                 # সব τ, যার জন্য Γ ⊢ e : τ-এর অন্তত একটি derivation আছে
    k, out = e[0], set()
    if k in ("int", "bool", "str"): out.add(LIT[k][0])                 # T-Int, T-Bool, T-Str
    elif k == "var": out.add(G3[e[1]])                                 # T-Var
    else:
        op, L, R = e[1], types(e[2], coerce), types(e[3], coerce)
        if op == "+" and "Int" in L and "Int" in R: out.add("Int")      # T-Add
        if op == "+" and "Str" in L and "Str" in R: out.add("Str")      # T-Concat
        if op == "-" and "Int" in L and "Int" in R: out.add("Int")      # T-Arith
        if op == "<" and "Int" in L and "Int" in R: out.add("Bool")     # T-Cmp
        if op == "==" and L & R & {"Int", "Bool", "Str"}: out.add("Bool")  # T-Eq
        if op == "&&" and "Bool" in L and "Bool" in R: out.add("Bool")  # T-And
    if coerce and "Bool" in out: out.add("Int")      # C-ধাঁচের বাড়তি নিয়ম: Bool মানেই Int-ও
    return out
two = [("bin", op, l, r) for op in OPS for l in ATOMS for r in ATOMS]
three = [("bin", op, l, r) for op in OPS for l in two for r in ATOMS] + \
        [("bin", op, l, r) for op in OPS for l in ATOMS for r in two]
every = ATOMS + two + three
haat = [types(e, False) for e in every]
print("Haat-এর নিয়ম:", len(every), "expression,", sum(map(bool, haat)), "well-typed,",
      sum(len(t) > 1 for t in haat), "টির একাধিক type")
print("syntax-directed derive() সবখানে একই type দেয়:",
      all(derive(G3, e)[1] == (min(t) if t else None) for e, t in zip(every, haat)))
c = [types(e, True) for e in every]
print("coercion সহ:", sum(map(bool, c)), "well-typed,", sum(len(t) > 1 for t in c), "টির একাধিক type")
new = [(e, t) for e, t, h in zip(every, c, haat) if t and not h]
print("   আগে বাতিল, এখন গৃহীত:", len(new), "টি, যেমন", src(new[0][0]), "→", sorted(new[0][1]))

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

Haat-এর নিয়ম: 10986 expression, 358 well-typed, 0 টির একাধিক type
syntax-directed derive() সবখানে একই type দেয়: True
coercion সহ: 2578 well-typed, 1370 টির একাধিক type
   আগে বাতিল, এখন গৃহীত: 2220 টি, যেমন 1 + true → ['Int']

১০,৯৮৬টি expression-এর মধ্যে ৩৫৮টি well-typed, আর একটিরও একাধিক type নেই: theorem-এর একটি ছোট, পূর্ণ গণনা-পরীক্ষা (প্রমাণ নয়; প্রমাণ সব আকারের expression-এর জন্য)। দ্বিতীয় লাইন দেখায়, “সব নিয়ম চেষ্টা” আর অংশ ৩-এর syntax-directed derive() প্রতিটি expression-এ একই উত্তর দেয়, ill-typed-গুলোতেও। লেখকের lab-এ একই ১০,৯৮৬টি expression বন্ধনী দিয়ে Haat source-এ লিখে reference-এর typechecker.py-তে চালানো হয়েছে (সত্যিকারের run, CPython 3.14.4): ৩৫৮টি গৃহীত, type-এ একটিও অমিল নেই। একটি coercion-নিয়ম যোগ করতেই ১,৩৭০টির দুটি type, আর 1 + true-এর মতো ২,২২০টি নতুন expression গৃহীত। C-তে _Bool সত্যিই integer-এ উন্নীত হয়, তাই C-র নিয়ম এই অর্থে Haat-এর মতো সরল নয়।

৭ · Derivation-কে ছবিতে আঁকা, আর পরীক্ষার খাতায়

পরীক্ষার খাতায় derivation লেখা হয় দাগ টেনে: premise ওপরে পাশাপাশি, দাগ, নিচে সিদ্ধান্ত, দাগের ডানে নিয়মের নাম। নিচের JavaScript block সেই রূপটিই আঁকে, নেস্টেড বাক্স দিয়ে: প্রতিটি নিয়ম-প্রয়োগ একটি বাক্স, যার ওপরের সারিতে premise-এর বাক্স, আর নিচে দাগসহ সিদ্ধান্ত। Axiom-এর ওপরে কিছু নেই, শুধু দাগ। চালালে ওপরে গাছটি, নিচে কয়েকটি গণনা দেখবেন।

// derivation-কে Gentzen-ধাঁচের বাক্সে আঁকা: premise ওপরে, দাগ, নিচে সিদ্ধান্ত
const G = { price: { params: ["Int", "Int"], ret: "Int" }, free: "Bool" };
const show = t => typeof t === "string" ? t : `(${t.params.join(", ")}) -> ${t.ret}`;
function derive(e) {                                  // ফেরত: {text, type, rule, kids}
  if ("int" in e) return { text: String(e.int), type: "Int", rule: "T-Int", kids: [] };
  if ("v" in e) return { text: e.v, type: G[e.v], rule: "T-Var", kids: [] };
  if ("call" in e) {
    const f = derive(e.call), args = e.args.map(derive);
    args.forEach((a, i) => { if (a.type !== f.type.params[i])
      throw new Error(`T-Call: expected ${f.type.params[i]}, found ${show(a.type)}`); });
    return { text: `${f.text}(${args.map(a => a.text).join(", ")})`, type: f.type.ret, rule: "T-Call", kids: [f, ...args] };
  }
  const l = derive(e.l), r = derive(e.r);             // এই ছোট উদাহরণে শুধু + (T-Add)
  const bad = [l, r].find(x => x.type !== "Int");
  if (bad) throw new Error(`T-Add: expected Int, found ${show(bad.type)}`);
  return { text: `${l.text} + ${r.text}`, type: "Int", rule: "T-Add", kids: [l, r] };
}
function box(d) {                                     // একটি নিয়ম-প্রয়োগ = একটি বাক্স
  const el = document.createElement("div"), top = document.createElement("div"),
        bottom = document.createElement("div"), name = document.createElement("span");
  el.className = "rule"; top.className = "prem"; bottom.className = "concl"; name.className = "name";
  d.kids.forEach(k => top.appendChild(box(k)));       // premise-গুলো পাশাপাশি, ওপরে
  bottom.textContent = `Γ ⊢ ${d.text} : ${show(d.type)}`; name.textContent = d.rule;
  bottom.appendChild(name); el.append(top, bottom); return el;
}
const e = { l: { call: { v: "price" }, args: [{ int: 2 }, { int: 520 }] }, r: { int: 60 } };
const d = derive(e);
document.getElementById("tree").appendChild(box(d));
const count = d => 1 + d.kids.reduce((s, k) => s + count(k), 0);
const height = d => 1 + Math.max(0, ...d.kids.map(height));
console.log(`সিদ্ধান্ত: Γ ⊢ ${d.text} : ${show(d.type)}`);
console.log(`judgment ${count(d)}টি, axiom ${JSON.stringify(d).split('"kids":[]').length - 1}টি, উচ্চতা ${height(d)}`);
try { derive({ l: e.l, r: { v: "free" } }); } catch (err) { console.log("আটকে গেল →", err.message); }

আসল আউটপুট (ব্রাউজারের JavaScript), গাছের ছবির নিচে:

সিদ্ধান্ত: Γ ⊢ price(2, 520) + 60 : Int
judgment 6টি, axiom 4টি, উচ্চতা 3
আটকে গেল → T-Add: expected Int, found Bool

একই গাছ তৃতীয়বার, তৃতীয় রূপে: Python-এর ভেতরের দিকে সরানো লেখা, SVG-র বাক্স-আর-তির, আর এখানে খাতার দাগ-টানা রূপ; তিনটিতেই ৬টি judgment, ৪টি axiom, উচ্চতা ৩. এখানে ভুল হলে JavaScript একটি Error ছোড়ে, তাই আটকে যাওয়া derivation-এর আংশিক গাছ আঁকা হয় না, শুধু বার্তা আসে; Python block-এর “আটকালে type = None” কৌশলের তুলনায় এটি সরল, কিন্তু প্রথম ভুলেই থামে। বড় expression দিলে ছবির প্রস্থ দ্রুত বাড়ে, তাই compiler-এর বই আর গবেষণাপত্রে বড় derivation প্রায়ই ভাগ করে লেখা হয়: একটি অংশ-গাছকে নাম দিয়ে (যেমন D1) আলাদা জায়গায় আঁকা।

আরও গভীরে। দাগের ওপরে premise আর নিচে সিদ্ধান্ত লেখার রীতি আসে Gerhard Gentzen-এর ১৯৩৪–৩৫ সালে প্রকাশিত natural deduction আর sequent calculus থেকে; ⊢ চিহ্নের শিকড় সাধারণত Frege-এর ১৮৭৯ সালের Begriffsschrift-এ খোঁজা হয়। প্রোগ্রামিং ভাষার পুরো সংজ্ঞা এই রীতিতে লেখার বড় উদাহরণ The Definition of Standard ML (Milner, Tofte, Harper, ১৯৯০; সংশোধিত ১৯৯৭)। আধুনিক checker-এ judgment প্রায়ই দুই mode-এ ভাগ হয়, “type বের করো” (synthesis) আর “এই type-এর সঙ্গে মেলাও” (checking); একে বলে bidirectional type checking, যার একটি প্রভাবশালী সূচনা Pierce আর Turner-এর “Local Type Inference” (১৯৯৮ সালের POPL-এ, পরে ২০০০ সালে TOPLAS-এ), আর ২০২১ সালে Dunfield ও Krishnaswami-র একটি survey এই ধারার সারসংক্ষেপ করেছে।

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

  • “Γ ⊢ e : τ-এর প্রতিটি অংশ ব্যাখ্যা করুন।” Γ নাম থেকে type-এর তালিকা, ⊢ “প্রমাণ করা যায়”, e expression, τ type; সব মিলে একটি দাবি, যার প্রমাণ derivation.
  • “এই expression-এর derivation tree আঁকুন।” গোড়ায় পুরো দাবি, প্রতিটি নিয়মের premise ওপরে, পাতায় axiom; প্রতিটি দাগের পাশে নিয়মের নাম।
  • “Axiom আর inference rule-এর পার্থক্য?” Axiom-এর কোনো judgment-premise নেই (শুধু side condition হতে পারে); বাকি নিয়ম ছোট প্রমাণ জুড়ে বড় প্রমাণ বানায়।
  • “Syntax-directed মানে কী, কেন দরকার?” প্রতিটি গঠনের জন্য একটিই প্রযোজ্য নিয়ম, তাই checker একটি recursive function; subsumption বা annotation-হীন parameter এই গুণ ভাঙে।
  • “Uniqueness of types প্রমাণ করুন।” গঠনের ওপর induction; প্রতিটি গঠনে একটি নিয়ম, +-এর দুই নিয়ম IH দিয়ে আলাদা, function-এর type annotation থেকে।

৮ · AI-এর যুগে typing rule

Typing rule আর derivation নিয়ে AI assistant দ্রুত উত্তর দেয়, আর সেগুলো দেখতে নিখুঁত গণিতের মতো। কিন্তু এখানে ভুল ধরা কঠিন, কারণ একটি ভুল নিয়ম দেখতেও একটি নিয়মের মতোই:

AI-এর সাধারণ ভুলকীভাবে ধরবেন
এক ভাষার নিয়ম সব ভাষায়: “== যেকোনো দুটি মান তুলনা করে” (Haat-এ function তুলনা নিষেধ), বা “if-এর দুই শাখার type এক হতে হবে” (Haat-এ if statement)সেই ভাষার spec বা reference-এর সিদ্ধান্ত পড়া, আর ছোট program-এ checker চালানো
Derivation-এ premise বাদ দেওয়া, বিশেষ করে T-Fn-এর missing-return শর্ত বা T-Eq-এর τ ∈ {Int, Bool, Str}প্রতিটি দাগের ওপরের premise সংখ্যা নিয়মের সঙ্গে গুনে মেলানো
Context ভুলভাবে বয়ে নেওয়া: block-এর ভেতরের let বাইরে দেখা যায় বলে ধরা, বা function-এর দেহে বাইরের ρ ব্যবহারT-Block আর T-FnDecl-এর conclusion-এ কোন Γ আর কোন ρ, তা দেখা; উদাহরণ চালানো
নিজের বানানো নিয়মের নাম বা “সুপরিচিত theorem”-এর ভুল বিবৃতিনামের চেয়ে নিয়মের আকার মেলানো; theorem-এর জন্য প্রাথমিক উৎস (বই, paper) দেখা
হাতে লেখা “checker-এর আউটপুট”, যার message বা অবস্থান আসল checker-এর সঙ্গে মেলে নাreference-এর check বা আসল compiler চালিয়ে পাশাপাশি মেলানো
“অনন্যতা সব ভাষায় সত্য” বা “syntax-directed মানেই সম্পূর্ণ” ধরনের সাধারণীকরণsubtyping, overloading বা inference আছে এমন ভাষায় একটি পাল্টা উদাহরণ খোঁজা

AI-কে কাজে লাগাতে ভাষা, version আর নিয়মের সেট স্পষ্ট বলে দিন, আর প্রতিটি দাবির যাচাইয়ের পথ চান:

আমি Haat নামের একটি ছোট ভাষার type checker লিখছি। নিয়ম: Int, Bool, Str, Unit, function type (T1, T2) -> R; কোনো implicit conversion নেই; + চলে Int+Int বা Str+Str-এ; == চলে একই type-এর Int, Bool বা Str-এ; if আর while statement, expression নয়। ১. Γ = price : (Int, Int) -> Int, free : Bool ধরে price(2, 520) + free-এর derivation লেখার চেষ্টা করো, আর ঠিক কোন premise প্রমাণ করা যায় না, তা বলো। কোনো premise বাদ দেবে না। ২. Statement-এর জন্য Γ ⊢ρ s ⇒ Γ′ আকারের নিয়ম দাও let, if, return আর block-এর জন্য। block-এর পরে Γ কেন আগের মতো থাকে, ব্যাখ্যা করো। ৩. "প্রতিটি expression-এর type অনন্য" theorem-এর প্রমাণের রূপরেখা দাও। কোন নিয়ম যোগ করলে প্রমাণটি ভাঙবে, একটি উদাহরণ দাও। ৪. তোমার প্রতিটি উত্তর আমি নিজে চালিয়ে যাচাই করব; যেখানে তুমি নিশ্চিত নও, স্পষ্ট বলো।

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

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

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

প্র ০১Java-র নিয়ম লেখা আছে ইংরেজি গদ্যে, Standard ML আর WebAssembly-র নিয়ম inference rule-এ। গদ্যে লিখলে সমস্যা কোথায়?

গদ্য পড়তে আরামদায়ক, কিন্তু অস্পষ্টতা লুকিয়ে রাখে। “দুটি operand একই type-এর হলে তুলনা চলবে” বাক্যটিতে প্রশ্ন থেকে যায়: function-ও? Unit-ও? প্রথমটির type জানা না গেলে কী? Inference rule-এ এই প্রশ্নগুলো এড়ানো যায় না, কারণ প্রতিটি premise আর side condition লিখতেই হয়; T-Eq-এ τ ∈ {Int, Bool, Str} না লিখলে নিয়মটি অসম্পূর্ণ দেখায়। Java Language Specification-এর type-এর অধ্যায়গুলো বিস্তারিত গদ্যে লেখা, আর বছরের পর বছর ধরে javac আর Eclipse-এর নিজস্ব compiler-এর মধ্যে কোনো কোনো জটিল generic program নিয়ে মতভেদের খবর পাওয়া গেছে, যেখানে কোন compiler spec ঠিক পড়েছে তা নিয়েও বিতর্ক হয়েছে।

অন্য প্রান্তে The Definition of Standard ML (১৯৯০, সংশোধিত ১৯৯৭): পুরো ভাষার static আর dynamic semantics inference rule-এ, একটি পাতলা বইয়ে। WebAssembly-র আনুষ্ঠানিক spec-ও (প্রথম সংস্করণ ২০১৭ সালের দিকে) প্রতিটি instruction-এর validation একটি typing rule আকারে দেয়। এর একটি বড় ফল দেখা গেছে: Conrad Watt ২০১৮ সালে নিয়মগুলো Isabelle নামের proof assistant-এ যন্ত্র-যাচাইযোগ্য রূপে লিখে soundness প্রমাণ করেন, আর সেই কাজে spec-এর কয়েকটি ত্রুটি ধরা পড়ে বলে জানিয়েছেন। গদ্যের spec-এ এমন যন্ত্র-প্রমাণ শুরুই করা যায় না।

দাম কী? Inference rule পড়তে শিখতে হয়, আর বড় ভাষার পূর্ণ নিয়ম অনেক পাতা। বাস্তবে তাই অনেক ভাষা মিশ্র পথ নেয়: গদ্যের spec, আর একটি ছোট “core” ভাষার আনুষ্ঠানিক নিয়ম, যেমন Java-র জন্য গবেষকদের Featherweight Java (Igarashi, Pierce, Wadler, ১৯৯৯/২০০১)। Haat-এর ক্ষেত্রে reference implementation-এর README-এর “Spec decisions” গদ্যে লেখা, আর এই পর্বের নিয়মগুলো সেগুলোর আনুষ্ঠানিক রূপ; দুটি মিলিয়ে পড়লে বোঝা যায় কোথায় গদ্য একটু ঢিলে ছিল।

মূল উপলব্ধি: inference rule অস্পষ্টতাকে চোখের সামনে আনে আর যন্ত্রে প্রমাণের দরজা খোলে; গদ্য পড়তে সহজ কিন্তু ফাঁক লুকায়, তাই গুরুত্বপূর্ণ ভাষার অন্তত একটি core অংশ আনুষ্ঠানিকভাবে লেখা হয়।

প্র ০২দাগ-টানা নিয়মের রীতি এসেছে যুক্তিবিদ্যা থেকে। Typing derivation আর গাণিতিক প্রমাণ কি আসলে একই জিনিস?

১৯৩০-এর দশকে Gerhard Gentzen দেখাতে চেয়েছিলেন গণিতবিদেরা আসলে কীভাবে যুক্তি দেন, আর লিখলেন natural deduction: প্রতিটি যুক্তি-চিহ্নের (“এবং”, “যদি…তবে”) জন্য দুটি নিয়ম, একটি দিয়ে চিহ্নটি তৈরি করা, আরেকটি দিয়ে ব্যবহার করা। প্রমাণ হলো এই নিয়মগুলোর একটি গাছ, পাতায় অনুমান আর গোড়ায় সিদ্ধান্ত। Typing derivation-এর আকার হুবহু এই।

মিলটি শুধু আকারে নয়। Γ ⊢ e : τ-কে “Γ-এর অনুমানগুলো থেকে τ প্রমাণ করা যায়, আর e সেই প্রমাণ” হিসেবে পড়লে T-Call (function প্রয়োগ) হয়ে যায় modus ponens: “A থেকে B” আর “A” থাকলে “B”. T-Fn হয় “A ধরে নিয়ে B প্রমাণ করা গেলে A থেকে B প্রমাণিত”। এই সাদৃশ্যকে বলে Curry–Howard correspondence: Haskell Curry ১৯৩০-এর দশক থেকে আর William Howard ১৯৬৯ সালের একটি পাণ্ডুলিপিতে (প্রকাশ ১৯৮০) এটি স্পষ্ট করেন। সরল typed lambda calculus-এর type-গুলো তখন propositional logic-এর সূত্র, আর program সেই সূত্রের প্রমাণ।

Haat-এ সাদৃশ্যটি পুরো খাটে না, কারণ Haat-এ recursion আর while আছে: fn loop(n: Int) -> Int { return loop(n); } well-typed, অথচ কোনো Int কখনো দেয় না; যুক্তির ভাষায় এটি “চক্রাকার প্রমাণ”, যা যুক্তিবিদ্যায় চলে না। Coq বা Lean-এর মতো proof assistant ঠিক এই কারণে সাধারণ recursion-এ বাধা দেয় আর termination দাবি করে (পর্ব ৪৪)। তবু typing rule পড়ার অভ্যাস যুক্তিবিদ্যার নিয়ম পড়ার অভ্যাসের মতোই, আর Discrete Mathematics-এর পর্ব ০৬-এর modus ponens যিনি বুঝেছেন, তিনি T-Call-ও বুঝবেন।

মূল উপলব্ধি: derivation tree আর natural deduction-এর প্রমাণ একই আকারের, আর Curry–Howard দৃষ্টিতে type হলো প্রস্তাব, program হলো প্রমাণ; সাধারণ ভাষায় recursion এই সাদৃশ্যকে আংশিক করে, proof assistant তা ফিরিয়ে আনতে termination দাবি করে।

প্র ০৩Haat function-এর parameter-এ type লেখা বাধ্যতামূলক করেছে। এই সিদ্ধান্ত checker আর error message-কে কীভাবে প্রভাবিত করে?

অংশ ৬-এর প্রমাণে T-Fn-এর ধাপটি এক লাইনের, কারণ function-এর type সরাসরি annotation থেকে পড়া যায়। Annotation না থাকলে fn(x) { return x; }-এর জন্য T-Fn-এর premise প্রতিটি τ-এর জন্য খাটত: (Int) -> Int, (Bool) -> Bool, (Str) -> Str. অনন্যতা ভাঙত, আর syntax-directed checker-এর জন্য “x-এর type কী ধরব?” প্রশ্নের কোনো উত্তর থাকত না। সমাধান দুটি: পুরো program দেখে অজানা type-এর জন্য চলক বসিয়ে সমীকরণ সমাধান (Hindley–Milner, পর্ব ৩৫), অথবা যেখানে লেখা আছে সেখান থেকে type “নিচে নামানো”।

দ্বিতীয় পথটি bidirectional checking-এর মূল ভাবনা, আর বাস্তব ভাষায় এটি খুব প্রচলিত। TypeScript-এ const f: (n: number) => number = x => x * 2; লিখলে x-এর type লাগে না, কারণ বাঁ পাশের annotation থেকে checker জানে কী চাওয়া হচ্ছে (TypeScript-এর ভাষায় contextual typing). Kotlin, Swift আর Rust-এর closure-এও একই ধরনের আচরণ দেখা যায়। নিয়মের ভাষায় judgment-টি দুই রূপ পায়: “e-এর type বের করো” আর “e-কে এই type-এর সঙ্গে মেলাও”।

Error message-এর দিকেও লাভ আছে। Annotation থাকলে ভুলের জায়গা স্থানীয়: yes(n: Int) -> Int-এ return true; দিলে বার্তা আসে ঠিক সেই লাইনে (4:32), কারণ checker জানে কী চাওয়া হয়েছিল। পুরো-program inference-এ একটি ভুল প্রায়ই অনেক দূরের কোনো জায়গায় অমিল হিসেবে ধরা পড়ে, আর বার্তায় এমন type আসে যা programmer কখনো লেখেননি। শেখার ভাষা হিসেবে Haat তাই পড়ার সুবিধা আর পরিষ্কার বার্তাকে প্রাধান্য দিয়েছে; পর্ব ০৬-এ এই নকশার যুক্তি আছে।

মূল উপলব্ধি: parameter annotation একটি ছোট দাম দিয়ে তিনটি জিনিস কেনে: অনন্য type, সরল syntax-directed checker আর স্থানীয় error message; inference বা bidirectional checking সেই দাম কমায়, কিন্তু নিয়ম আর বাস্তবায়ন জটিল করে।

প্র ০৪যে ভাষায় if একটি expression আর দুই শাখার type আলাদা, সেখানে কী করা উচিত: বাতিল, না দুই type মিলিয়ে নতুন type?

T-IfExpr-এর কঠোর রূপ বলে দুই শাখার τ হুবহু এক হতে হবে, নইলে বাতিল। OCaml আর Haskell মোটামুটি এই পথে; Rust-এ if আর else-এর type আলাদা হলে compiler mismatched types error দেয়। কিন্তু একটি ব্যতিক্রম সবাইকে সামলাতে হয়: শাখা যদি কখনো শেষই না হয়? Rust-এ return, panic! বা অসীম loop-এর type “never” (!), যা যেকোনো type-এর সঙ্গে মিলে যায়; তাই let fee = if ok { 60 } else { return 0; }; চলে। গাণিতিকভাবে এটি একটি “bottom” type, যার কোনো মান নেই।

দ্বিতীয় পথ: দুই type মিলিয়ে একটি union. TypeScript ঠিক এটি করে। লেখকের lab-এ tsc 5.9.2 দিয়ে const label = total >= 1000 ? 0 : "60"; আর একটি function-এর দুই শাখায় return 0; ও return "free"; লিখে --declaration চালানো হয়েছে (সত্যিকারের run); declaration ফাইলে এল label: string | number আর ফেরত-type 0 | "free". কোনো error নেই; ভুলটি (একই চার্জের জন্য একবার সংখ্যা, একবার লেখা) পরে কোথাও ধরা পড়বে, যেখানে এই মান ব্যবহার হবে। এর পেছনে subtyping আছে: Int আর Str দুটিই union-এর subtype, আর union হলো দুটির “ক্ষুদ্রতম উপরের সীমা”, যা পর্ব ৩৬-এর বিষয়।

তৃতীয় পথ Haat-এর: if-কে statement রাখা, যাতে প্রশ্নটিই না ওঠে। দাম লেখায়: শর্তসাপেক্ষ মানের জন্য var fee = 60; if ok { fee = 0; }. লাভ নিয়মে: T-If-এ কোনো τ নেই, অনন্যতার প্রমাণে কোনো নতুন case নেই, আর error message সবসময় একটি নির্দিষ্ট assignment-এর দিকে আঙুল তোলে। অনুশীলন ১-এ Haat-এর বর্ধিত রূপে কঠোর T-Cond যোগ করে দেখবেন, প্রথম পথটি কত সহজে বসে যায়।

মূল উপলব্ধি: expression-if-এর দুই শাখা মেলানোর তিনটি উত্তর: কঠোর সমতা (সঙ্গে “never” type-এর ছাড়), union-এর মতো সাধারণ উপরের type, অথবা if-কে statement রাখা; প্রতিটি নিয়মের সরলতা, লেখার সুবিধা আর ভুল ধরার সময়ের মধ্যে একটি আলাদা আপস।

প্র ০৫নিয়ম শুধু বলে “derivation আছে কি নেই”। তাহলে একটি ভালো type error message কোথা থেকে আসে?

গণিতের দৃষ্টিতে ill-typed program-এর কোনো derivation নেই, ব্যস; “কোথায় ভুল” প্রশ্নটি নিয়মের বাইরে। কিন্তু syntax-directed checker একটি নির্দিষ্ট ক্রমে লক্ষ্য খোঁজে, তাই সে জানে কোন premise প্রথম ব্যর্থ হলো। অংশ ৪-এর stepper-এ সেটি ছিল T-Add-এর দ্বিতীয় premise, আর বার্তার দুই অংশ সরাসরি সেখান থেকে: “expected” আসে নিয়ম যা চায় তা থেকে, “found” আসে sub-derivation যা দিল তা থেকে। অবস্থান আসে ব্যর্থ premise-এর expression থেকে (সিদ্ধান্ত ২৪)।

কিন্তু “প্রথম ব্যর্থ premise” সবসময় programmer-এর আসল ভুল নয়। price(2, 520) + free-এ হয়তো ভুলটি free নয়, বরং আগের লাইনে free-এর সংজ্ঞা, বা এখানে অন্য নাম লেখার কথা ছিল। Checker তা জানে না; সে শুধু বলতে পারে কোন দুটি জিনিস মেলেনি। তাই ভালো compiler বাড়তি তথ্য দেয়: অন্য জায়গাটি দেখায় (“free এখানে Bool হিসেবে ঘোষিত”), বা কাছাকাছি নামের পরামর্শ দেয়। Elm ভাষার লেখক Evan Czaplicki ২০১৫ সালের দিকে “Compiler Errors for Humans” লেখায় বার্তাকে কথোপকথনের মতো করার পক্ষে যুক্তি দেন, আর পরে Rust-সহ কয়েকটি ভাষার বার্তার ধরন এই ধারায় প্রভাবিত হয়েছে বলে প্রায়ই বলা হয়।

আরেকটি সমস্যা cascade: একটি ভুল থেকে দশটি বার্তা। Reference-এর সমাধান ব্যর্থ sub-expression-কে None type দেওয়া, যা সবখানে মেনে নেওয়া হয়; অনেক বাস্তব compiler একই উদ্দেশ্যে একটি বিশেষ “error type” রাখে। গণিতের ভাষায় এটি নিয়মের সেটে একটি নতুন, অস্থায়ী type যোগ করা, যা শুধু রিপোর্ট লেখার সময় থাকে। Haat-এ এর ফল: চারটি আলাদা ভুল, চারটি বার্তা, বাড়তি একটিও নয় (অংশ ৫-এর সত্যিকারের run).

মূল উপলব্ধি: error message নিয়মের ফল নয়, algorithm-এর: কোন premise প্রথম ব্যর্থ, কোন অবস্থান, কোন বাড়তি প্রসঙ্গ, আর cascade ঠেকানোর error type; একই নিয়মের দুটি checker খুব আলাদা মানের বার্তা দিতে পারে।

অনুশীলন

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

  1. নকশা ও বাস্তবায়ন — Haat-এর বর্ধিত রূপে conditional expression: Haat-এর বর্ধিত রূপে একটি expression c ? a : b যোগ করুন (C-র ternary-র মতো; এটি spec v1-এ নেই)। (ক) এর typing rule T-Cond লিখুন। (খ) অংশ ৩-এর derive()-এ একটি শাখা যোগ করুন, যা ভুল হলে reference-এর ধাঁচে expected …, found … বার্তা দেয়। (গ) Γ = free : Bool, total : Int হলে free ? 0 : "60" আর total ? 0 : 60-এ কী আসবে? (ঘ) অনন্যতার প্রমাণে কোন নতুন case লাগবে?

    (ক) Γ ⊢ c : Bool, Γ ⊢ a : τ, Γ ⊢ b : τ থাকলে Γ ⊢ c ? a : b : τ (T-Cond). (খ) derive()-এর if k == "call":-এর আগে এই শাখা, আর src()-এ ? আর : ছাপানোর একটি লাইন:

        if k == "cond":                      # ("cond", c, a, b): c ? a : b  — বর্ধিত রূপ
            c, a, b = (derive(G, x) for x in e[1:])
            if c[1] != "Bool": return (e, None, f"✗ T-Cond: expected Bool, found {show(c[1])}", [c, a, b])
            if a[1] != b[1]: return (e, None, f"✗ T-Cond: expected {show(a[1])}, found {show(b[1])}", [c, a, b])
            return (e, a[1], "T-Cond", [c, a, b])

    (গ) লেখকের lab-এ চালানো (CPython 3.14.4): free ? 0 : 60 → Int [T-Cond], তিনটি premise T-Var, T-Int, T-Int; free ? 0 : "60" → ? [✗ T-Cond: expected Int, found Str]; total ? 0 : 60 → ? [✗ T-Cond: expected Bool, found Int]; আর total + (free ? 0 : 60) → Int [T-Add]. দ্বিতীয় বার্তায় “expected Int” আসে then-শাখা থেকে, কারণ এই নকশায় then-শাখার type-ই τ ঠিক করে, যেমন +-এ বাঁ পাশ। (ঘ) Case: e = c ? a : b. একটিই নিয়ম; দুটি derivation-এর ফল τ1, τ2 যথাক্রমে a-এর type, তাই a-তে IH খাটালে τ1 = τ2. অনন্যতা টিকে থাকে, কারণ T-Cond দুই শাখার type হুবহু এক চায়; TypeScript-এর মতো union বানালে প্রমাণে নতুন যুক্তি লাগত।

  2. ভুল derivation খুঁজুন: একজন লিখলেন, ফাঁকা context-এ fn(n: Int) -> Int { if n > 0 { return n / 2; } } well-typed: (১) n : Int যোগ করে context Γ1 = n : Int, ρ = Int; (২) T-Cmp দিয়ে Γ1 ⊢ n > 0 : Bool; (৩) T-Arith দিয়ে Γ1 ⊢ n / 2 : Int, আর T-Return দিয়ে return সঠিক; (৪) T-If দিয়ে পুরো if সঠিক; (৫) T-Fn দিয়ে type (Int) -> Int. কোন ধাপ ভুল, আর reference কী বলবে?

    ধাপ ১–৪ ঠিক। ধাপ ৫-এ T-Fn-এর একটি premise বাদ পড়েছে: R = Unit অথবা returns(body). এখানে R = Int, আর দেহে একটিমাত্র statement, একটি else-হীন if; সিদ্ধান্ত ২১-এর নিয়মে এমন if return করে না, আর দেহে আর কোনো return নেই, তাই returns(body) মিথ্যা। T-Fn খাটে না, derivation নেই। let half = fn(n: Int) -> Int { if n > 0 { return n / 2; } }; reference-এ সত্যিকারের run: 1:12: error: missing return: not every path of anonymous function returns Int. কলাম ১২ হলো fn-এর অবস্থান (সিদ্ধান্ত ২১: anonymous function-এর বেলায় fn-এ)। else { return 0; } যোগ করলে check পার হয়, আর print(half(7)); ছাপে 3. শিক্ষা: derivation যাচাইয়ের সময় শুধু judgment-premise নয়, প্রতিটি side condition-ও গুনতে হয়।

  3. হিসাব — derivation আঁকুন: Γ = price : (Int, Int) -> Int, apply : ((Int) -> Int, Int) -> Int ধরে নিচের expression-এর পূর্ণ derivation tree আঁকুন। মোট কয়টি judgment, তার কয়টি axiom, আর গোড়ার type কী? Haat-এ print(…) করলে কী ছাপবে, যদি price bazar.haat-এর মতো হয় আর apply(f, n) ফেরত দেয় f(n)?
    apply(fn(x: Int) -> Int { return x * 2; }, price(1, 300)) > 500
    Γ ⊢ apply(…, price(1, 300)) > 500 : Bool        [T-Cmp]
       Γ ⊢ apply(…, price(1, 300)) : Int             [T-Call]
          Γ ⊢ apply : ((Int) -> Int, Int) -> Int     [T-Var]
          Γ ⊢ fn(x: Int) -> Int {…} : (Int) -> Int   [T-Fn]
             Γ, x : Int ⊢Int return x * 2; ⇒ …    [T-Return]
                Γ, x : Int ⊢ x * 2 : Int            [T-Arith]
                   Γ, x : Int ⊢ x : Int             [T-Var]
                   Γ, x : Int ⊢ 2 : Int             [T-Int]
          Γ ⊢ price(1, 300) : Int                   [T-Call]
             Γ ⊢ price : (Int, Int) -> Int          [T-Var]
             Γ ⊢ 1 : Int                            [T-Int]
             Γ ⊢ 300 : Int                          [T-Int]
       Γ ⊢ 500 : Int                                [T-Int]

    গাছের আকার আর প্রতিটি নিয়ম লেখকের lab-এ চালানো একটি printer-এর আউটপুটের সঙ্গে মেলানো (অংশ ৩-এর printer-এ lambda-র একটি শাখা যোগ করে); লম্বা অংশ “…” দিয়ে ছোট করা, আর lambda-র ভেতরের context পুরো লেখা হয়েছে। মোট ১৩টি judgment: ১২টি expression-এর আর একটি statement-এর (T-Return); axiom ৭টি (তিনটি T-Var, চারটি T-Int). গোড়ার type Bool. লক্ষ করুন lambda-র ভেতরে context Γ, x : Int, আর ρ = Int আসে annotation থেকে, বাইরের কিছু থেকে নয়। T-Fn-এর missing-return premise-ও পূর্ণ, কারণ দেহে return আছে। চালালে: price(1, 300) = 300 (১০০০-এর কম, তাই ছাড় নেই), lambda দেয় 600, আর 600 > 500, তাই ছাপা হয় true. Reference-এ সত্যিকারের run-এ true এসেছে, আর let v: Bool = … লিখে check চালালে কোনো error আসেনি, অর্থাৎ type Bool নিশ্চিত।

  4. প্রমাণ — weakening lemma: প্রমাণ করুন: lambda ছাড়া Haat expression-এর জন্য, যদি Γ ⊢ e : τ আর x নামটি Γ-তে না থাকে, তাহলে যেকোনো σ-এর জন্য Γ, x : σ ⊢ e : τ. “x Γ-তে না থাকে” শর্তটি কেন দরকার, একটি পাল্টা উদাহরণ দিন। Lambda যোগ করলে প্রমাণে কোন বাড়তি যত্ন লাগবে?

    প্রমাণ Γ ⊢ e : τ-এর derivation-এর ওপর induction (শেষ নিয়ম ধরে case). লিখি Γ′ = Γ, x : σ.

    1. T-Int, T-Bool, T-Str: এদের side condition context দেখে না, তাই Γ′ ⊢ e : τ একই নিয়মে।
    2. T-Var, e = y, Γ(y) = τ: y Γ-তে আছে আর x নেই, তাই y ≠ x. Γ′-এর সবচেয়ে ডানের ঘোষণা x : σ, যা y-এর নয়, তাই Γ′(y) = Γ(y) = τ, আর T-Var খাটে।
    3. দুই premise-ওয়ালা নিয়ম (T-Add, T-Concat, T-Arith, T-Cmp, T-Eq, T-And, T-Or) আর T-Neg, T-Not: premise-গুলোর derivation ছোট, তাই IH দিয়ে প্রতিটি premise Γ′-এ সত্য; side condition (যেমন τ ∈ {Int, Bool, Str}) context-নির্ভর নয়; একই নিয়মে Γ′ ⊢ e : τ.
    4. T-Call: f আর প্রতিটি eᵢ-এর premise-এ IH; একই নিয়ম। ∎

    পাল্টা উদাহরণ: Γ = free : Bool, e = free, τ = Bool. x = free আর σ = Int নিলে Γ, free : Int-এ সবচেয়ে ডানের ঘোষণা Int, তাই Γ, free : Int ⊢ free : Bool আর derivable নয়। নতুন ঘোষণা পুরোনোকে ঢেকে দেয় (shadowing), তাই শর্তটি দরকার। Lambda যোগ করলে T-Fn-এর premise-এ context Γ, x1 : T1, …; যদি কোনো parameter-এর নাম x হয়, তাহলে Γ, x : σ, x : T1-এ IH সরাসরি খাটে না। প্রচলিত সমাধান: parameter-গুলোকে আগে নতুন নামে বদলে নেওয়া (α-renaming; নামের বদলে type বা অর্থ বদলায় না), যাতে কোনো parameter x না হয়। এই lemma পর্ব ৩৮-এ (Type soundness) substitution lemma-র প্রমাণে কাজে লাগবে।

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

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

ক্রমএকটি syntax-directed checker Γ = price : (Int, Int) -> Int-এ price(2, 520) + 60 যাচাই করছে; premise বাঁ থেকে ডানে, আগে premise পরে সিদ্ধান্ত। Judgment-গুলো যে ক্রমে প্রমাণিত হয়, সেভাবে সাজান (▲▼ চেপে সরান)

  1. Γ ⊢ price : (Int, Int) -> Int (T-Var)
  2. Γ ⊢ 2 : Int (T-Int)
  3. Γ ⊢ 520 : Int (T-Int)
  4. Γ ⊢ price(2, 520) : Int (T-Call)
  5. Γ ⊢ 60 : Int (T-Int)
  6. Γ ⊢ price(2, 520) + 60 : Int (T-Add)

Typing judgment Γ ⊢ e : τ-এ Γ কী ধারণ করে?

  • প্রতিটি variable-এর বর্তমান মান
  • ভাষার সব typing rule-এর তালিকা
  • দৃশ্যমান নাম থেকে তাদের type-এর তালিকা
  • e-এর evaluation-এর ফল

Haat-এর typing rule-গুলোর মধ্যে কোনটি axiom (দাগের ওপরে কোনো typing judgment নেই)?

  • T-Add
  • T-Int
  • T-Call
  • T-If

Haat-এর নিয়মে Γ = total : Int, free : Bool. নিচের কোন judgment derivable?

  • Γ ⊢ total + free : Int
  • Γ ⊢ total == free : Bool
  • Γ ⊢ total >= 1000 && free : Bool
  • Γ ⊢ "৳" + total : Str

Haat anonymous function-এর parameter-এ type annotation বাধ্যতামূলক। Annotation ছাড়া fn(x) { return x; } অনুমতি পেলে “প্রতিটি well-typed expression-এর type অনন্য” গুণটির কী হতো?

  • ভাঙত: একই expression-এর অনেক type-এর derivation থাকত
  • টিকে থাকত, কারণ return-এর type একটিই
  • Expression-টির কোনো derivation-ই থাকত না
  • শুধু চালানোর সময় ঠিক হতো

Haat-এ statement-এর judgment Γ ⊢ρ s ⇒ Γ′. Γ = c : Bool হলে if c { let d = 60; } else { let d = 0; }-এর পরে context কী?

  • c : Bool, d : Int
  • c : Bool, d : Int, কারণ then-শাখার context জেতে
  • ফাঁকা context
  • c : Bool, অর্থাৎ আগের মতোই

Haat-এর missing-return নিয়মে (return থাকলে, বা return করে এমন block, বা else-সহ if যার দুই শাখাই return করে; while কখনো গোনা হয় না) কোন function গৃহীত?

  • fn f1(n: Int) -> Int { while true { return 1; } }
  • fn f2(n: Int) -> Int { if n > 0 { return 1; } }
  • fn f3(n: Int) -> Int { if n > 0 { return 1; } else { return 0; } }
  • fn f4(n: Int) -> Int { while n > 0 { return n; } }

শব্দকোষ

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

মনে রাখুন

  1. Judgment আর rule: Γ ⊢ e : τ একটি দাবি; Γ নাম থেকে type-এর তালিকা (সবচেয়ে ডানেরটি খাটে)। নিয়মে ওপরে premise, নিচে সিদ্ধান্ত; premise-হীন নিয়ম axiom.
  2. Derivation tree: গোড়ায় দাবি, পাতায় axiom; price(2, 520) + 60 : Int-এর গাছে ৬টি judgment. ভুল program-এ গাছ যে premise-এ আটকায়, সেটিই error message.
  3. Syntax-directed: প্রতিটি গঠনের একটি নিয়ম, তাই checker = recursive function: premise মানে recursive call, side condition মানে তুলনা। Subsumption আর annotation-হীন parameter এই সরলতা ভাঙে।
  4. Statement: Γ ⊢ρ s ⇒ Γ′; let যোগ করে, block/if/while শেষে ভেতরের নাম ফেলে দেয়, return মেলে ρ-এর সঙ্গে, আর returns(body) একটি আলাদা syntactic শর্ত (সিদ্ধান্ত ২১)।
  5. অনন্যতা: Haat-এ প্রতিটি well-typed expression-এর type একটিই; প্রমাণ structural induction, ভিত্তি annotation আর coercion-এর অনুপস্থিতি।

পরের পর্বে: পর্ব ৩৫ (Type inference — Hindley–Milner আর unification). Parameter-এ type না লিখলে কী হয়: অজানা type-এর জন্য চলক, সমীকরণ, unification, আর কীভাবে প্রতিটি function একটি “সবচেয়ে সাধারণ” type পায়।

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

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