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

Type inference — Hindley–Milner আর unification

Type Inference: Hindley–Milner and Unification

Taught in Bangla, this lesson infers types by naming unknowns with type variables, collecting constraints from the AST and solving them by unification with the occurs check. It runs Algorithm W in in-page Python (Pyodide) to derive principal types for compose and twice, explains let-polymorphism, generalisation, instantiation and the value restriction, discusses decidability and Hindley–Milner's limits, adds parameter inference to an extended Haat, and compares TypeScript's local inference in a real tsc run.

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

  • একটি function-এর AST থেকে type variable আর constraint তৈরি করা, আর unification দিয়ে সেগুলো হাতে সমাধান করা
  • Algorithm W-এর চারটি নিয়ম (variable, function, call, let) পড়া, চালানো, আর compose, twice, S-এর মতো ক্লাসিক function-এর type বের করা
  • Generalisation আর instantiation বোঝা: কেন let-এর id দুই type-এ চলে, অথচ parameter-এর id চলে না, আর value restriction কেন লাগে
  • Principal type, decidability আর HM-এর সীমা (rank-2+, subtyping, overloading) প্রমাণ বা রূপরেখাসহ ব্যাখ্যা করা
  • Haat-এর বর্ধিত রূপে parameter-এ type না লিখে inference চালানো, আর TypeScript-এর আসল tsc output দিয়ে local inference-এর সঙ্গে তুলনা করা

১ · কেন type inference — না-লেখা type খুঁজে বের করা

বাজারঘরের হিসাবরক্ষক মাসের শেষে খাতা মেলাচ্ছেন। কয়েকটি রসিদ হারিয়ে গেছে, তাই কয়েকটি ঘরের অঙ্ক জানা নেই। কিন্তু তিনি জানেন “ক্যাশে আসা টাকা = বিক্রি − ফেরত”, “বিক্রি = চালান ১ + চালান ২”। প্রতিটি অজানা ঘরকে একটি নাম দিয়ে (ক, খ, গ) সম্পর্কগুলো সমীকরণ হিসেবে লেখেন, তারপর সমাধান করেন। কোনো ঘরের দুটি আলাদা মান বেরোলে বোঝেন খাতায় ভুল আছে। Type inference ঠিক এই কাজটি করে, টাকার বদলে type নিয়ে।

পর্ব ৩৩-এ (Type system — static, dynamic, strong আর weak typing) দেখেছেন, type দুভাবে আসতে পারে: programmer নিজে লেখেন (explicit typing), অথবা compiler নিজে বের করে। পর্ব ৩৪-এ (Typing rule আর type judgment — type checking-এর গণিত) typing judgment Γ ⊢ e : τ আর নিয়ম দিয়ে type যাচাই করার কথা। এখানে Γ মানে নাম থেকে type-এর তালিকা (context বা environment), ⊢ পড়া হয় “থেকে প্রমাণ হয়”, আর τ একটি type. Type checking-এ প্রশ্ন: “এই e কি τ type-এর?” Type inference-এ প্রশ্ন বড়: “e-এর type কী হতে পারে, আর সবচেয়ে সাধারণ উত্তর কোনটি?”

Haat v1 ইতিমধ্যেই একটু infer করে

Haat-এর spec-এ let x = e; লিখলে x-এর type e থেকে আসে, লিখতে হয় না। কিন্তু function-এর parameter আর return type লিখতেই হয়। এটি local type inference: type শুধু ভেতর থেকে বাইরে, initializer থেকে নামের দিকে যায়, আর কোনো অজানা পরে সমাধানের জন্য ফেলে রাখা হয় না। Reference বাস্তবায়নের সত্যিকারের run (CPython 3.14.4, python -B haat.py check local.haat):

let total = 2 * 520;          // total : Int (infer)
let free = total >= 1000;     // free : Bool (infer)
let y: Bool = total;          // লেখা type আর infer করা type মেলে না

3:15: error: type mismatch: expected Bool, found Int

(মন্তব্যগুলো এখানে যোগ করা; ফাইলের চতুর্থ লাইনে print(free);.) প্রথম দুই লাইনের type কেউ লেখেননি, checker নিজে বের করেছে; তৃতীয় লাইনে লেখা type Bool আর বের করা type Int মেলেনি, তাই error. তৃতীয় লাইন বাদ দিলে run ছাপে true. Parameter-এ type না লিখলে অবশ্য Haat v1-এর parser-ই আটকায়:

fn twice(f, x) {
    return f(f(x));
}

1:11: error: expected ':' and a type after parameter 'f'

কেন এই নিয়ম? Parameter-এর type জানতে হলে দেখতে হয় function-এর ভেতরে parameter কীভাবে ব্যবহার হলো: f(x) লেখা মানে f একটি function, আর f(f(x)) মানে f-এর ফলও আবার f-এ যায়। তথ্য এখানে উল্টো দিকে, ব্যবহার থেকে ঘোষণার দিকে চলে। এমন inference-এর জন্য দরকার অজানাকে নাম দেওয়া আর সমীকরণ মেলানো। এই পর্বের বাকিটা সেই যন্ত্র: Hindley–Milner (HM) type inference, আর তার হৃদয় unification. Haat v1 এটি নেয়নি (Haat-এর নকশার যুক্তি পর্ব ০৬-এ); অংশ ৭-এ আমরা Haat-এর বর্ধিত রূপে এটি যোগ করে দেখব।

দুই ধরনের গোয়েন্দা: local inference হলো এমন কর্মী, যিনি শুধু সামনে রাখা রসিদ দেখে একটি ঘর পূরণ করেন। HM হলো এমন হিসাবরক্ষক, যিনি পুরো খাতার সব সম্পর্ক একসাথে লিখে তারপর সমাধান করেন; ফলে একটি ঘরের উত্তর আসতে পারে খাতার একেবারে অন্য পাতার একটি লাইন থেকে।

২ · Type variable আর constraint — অজানাকে নাম দেওয়া

প্রথম ধাপ সহজ: যার type জানা নেই, তাকে একটি নতুন type variable দিন। আমরা লিখব t1, t2, …; চূড়ান্ত উত্তরে পড়ার সুবিধার জন্য নাম বদলে a, b, c. Type variable কোনো নির্দিষ্ট type নয়, একটি ফাঁকা ঘর, যা পরে কোনো type দিয়ে পূরণ হতে পারে, বা ফাঁকাই থেকে যেতে পারে।

দ্বিতীয় ধাপ: AST-এর প্রতিটি node দেখে একটি করে নিয়ম খাটিয়ে constraint (type-এর সমীকরণ) লেখা। ≐ চিহ্নের অর্থ “এই দুই type সমান হতেই হবে”। Haat-এর বর্ধিত রূপের জন্য নিয়মগুলো:

AST nodeকী করা হয়নতুন constraint
Num, Booltype জানা: Int, Boolনেই
Var xΓ-তে x খোঁজানেই (∀ থাকলে নতুন কপি, অংশ ৫)
Lambda / FnDeclপ্রতিটি parameter-এ নতুন variable, return-এর জন্যও একটিনেই
Call f(a1, …, an)f আর argument-গুলোর type বের করে, ফলের জন্য নতুন rτf ≐ (τ1, …, τn) → r
Binary + − * / (বর্ধিত রূপে)দুই পাশ Int, ফল Intτl ≐ Int, τr ≐ Int
Return ee-এর type function-এর return typeτe ≐ rfn
If শর্তশর্ত Bool হতে হবেτশর্ত ≐ Bool

ছবিতে fn twice(f, x) { return f(f(x)); }-এর AST, প্রতিটি node-এ তার type variable আর নিচে জমা হওয়া দুটি constraint. Return-এর জন্য আলাদা variable না নিয়ে সরাসরি বাইরের call-এর t4 ধরা হয়েছে, যাতে নম্বরগুলো নিচের Python run-এর সঙ্গে মেলে।

ছবি ৩৫.১ — twice-এর AST, type variable আর constraint

নীল: parameter থেকে আসা variable; সবুজ: call-এর ফলের জন্য নতুন variable; নিচের বাক্সে দুটি call থেকে আসা দুটি সমীকরণ।

AST of twice annotated with type variables and the two constraints Lambda twice(f, x) (t1, t2) → t4 Return Call : t4 f : t1 Call : t3 f : t1 x : t2 ভেতরের call: t1 ≐ (t2) → t3 বাইরের call: t1 ≐ (t3) → t4

এবার একই কাজ ধাপে ধাপে, যেভাবে একটি inference engine AST ঘোরে। লক্ষ করুন, t1 দুবার দুটি আলাদা দাবির মুখে পড়ে; দুটি দাবি একসাথে সত্য করা যায় কি না, সেটি পরের অংশের প্রশ্ন।

1fn twice(f, x) {2    return f(f(x));3}
engine-এর খাতা
Γ
এখন
C
  1. Parameter. f আর x-এর type লেখা নেই, তাই নতুন দুটি type variable: f : t1, x : t2. দুটিই Γ-তে যায়। এখনো কোনো constraint নেই।
  2. বাইরের call শুরু। f(f(x))-এ আগে callee: Γ-তে f খুঁজে t1 পাওয়া গেল। বাম থেকে ডানে (Haat-এর নকশা-সিদ্ধান্ত ১২-এর ক্রম) এবার argument f(x).
  3. ভেতরের call. callee f : t1, argument x : t2, ফলের জন্য নতুন t3. f-কে একটি t2 দিয়ে ডাকা হলো আর ফল t3, তাই প্রথম constraint: t1 ≐ (t2) → t3.
  4. বাইরের call শেষ। argument-এর type t3, ফলের জন্য নতুন t4. একই f-কে এবার t3 দিয়ে ডাকা হলো, তাই দ্বিতীয় constraint: t1 ≐ (t3) → t4.
  5. Return. function-এর ফল বাইরের call-এর ফল, t4. তাই twice : (t1, t2) → t4, সঙ্গে দুটি constraint. t1-এর ওপর দুটি দাবি একসাথে মেলানো যায় কি না, তা বলবে unification.

এক কথায় inference = constraint তৈরি + constraint সমাধান। কিছু বাস্তবায়ন (যেমন Haskell-এর GHC, হেজসহ বলা: তার নথিপত্রে এমনই বর্ণনা) আগে সব constraint জমায়, পরে সমাধান করে; ক্লাসিক Algorithm W প্রতিটি constraint পাওয়ামাত্র সমাধান করে। ফল একই, শুধু ভুলের বার্তা আর গতিতে পার্থক্য।

৩ · Unification — type-এর সমীকরণ সমাধান

পর্ব ১০-এ (Logic programming — Prolog, unification আর backtracking) unification-এর পুরো algorithm, most general unifier (MGU)-এর সংজ্ঞা আর সঠিকতার প্রমাণ দেখেছেন; সেখানে term ছিল ship(X, hub(Y, 60), Y). এখানে একই algorithm, শুধু term-এর জায়গায় type: constant হলো Int, Bool; compound term হলো function type (τ1, …, τn) → τ, যার functor “→” আর arity n + 1; variable হলো type variable. Prolog-এর θ = {X/dhaka}-এর মতো এখানে substitution লেখা হয় [t1 ↦ Int].

নিয়মসমীকরণকী হয়
deleteτ ≐ τবাদ
decompose(σ1…σn) → σ ≐ (τ1…τn) → τσi ≐ τi আর σ ≐ τ
clashInt ≐ Bool, বা Int ≐ (…) → …, বা parameter-সংখ্যা আলাদাtype error
swapτ ≐ t (τ variable নয়)t ≐ τ
bindt ≐ τ, t τ-এর ভেতরে নেইS-এ t ↦ τ যোগ
occurs checkt ≐ τ, t τ-এর ভেতরে আছে (τ ≠ t)type error, যেমন t1 ≐ (t1) → t2

Clash-এর সারিটি লক্ষ করুন: parameter-সংখ্যা আলাদা হলে clash, অর্থাৎ ভুল সংখ্যক argument দিয়ে ডাকাও unification-এর ভাষায় একটি functor-এর অমিল। Prolog-এর সঙ্গে একটি বড় পার্থক্য: Prolog সাধারণত গতির জন্য occurs check বাদ দেয়, কিন্তু type inference-এ বাদ দেওয়া চলে না, কারণ তখন অসীম type তৈরি হয় আর ভুল program গৃহীত হয় (অনুশীলন ২)।

এখন অংশ ২-এর দুটি constraint সমাধান করুন। Engine একটি খাতা S রাখে (বাস্তবায়নে যাকে বলে triangular substitution): t1 ↦ …, আর দরকার হলে শিকল ধরে (walk) শেষ মান খোঁজে।

1bind: t ≐ τ → S-এ t ↦ τ2walk: বাঁধা t → তার মান3decompose: → ≐ →4apply: সব variable বদলানো5occurs check: t ≐ (…t…)
এই ধাপে
এখন
বাকি
S
  1. শুরু। দুটি constraint, খাতা S খালি। ক্রমটি AST ঘোরার ক্রম।
  2. Bind t1. বাম দিকে মুক্ত variable t1, ডান দিকে (t2) → t3; t1 তার ভেতরে নেই, তাই occurs check পার, আর S-এ t1 ↦ (t2) → t3.
  3. Walk আর decompose. দ্বিতীয় সমীকরণে t1 এখন বাঁধা; walk করে পাওয়া গেল (t2) → t3. দুই দিকই এক-parameter-এর function type, তাই ভেঙে দুটি সমীকরণ: parameter-এ t2 ≐ t3, ফলে t3 ≐ t4.
  4. Bind t2. দুই দিকই মুক্ত variable; একটিকে অন্যটিতে বাঁধলেই চলে: t2 ↦ t3. এর মানে “f-এর input আর output একই type”.
  5. Bind t3. t3 এখনো মুক্ত, তাই t3 ↦ t4. সব সমীকরণ শেষ, কোনো clash নেই।
  6. Apply. শিকল ধরে প্রতিটি variable-এর শেষ রূপ: t2 = t4, t3 = t4, t1 = (t4) → t4. তাই twice : ((t4) → t4, t4) → t4; t4 মুক্ত থাকে বলে যেকোনো type বসতে পারে: ∀a. ((a) → a, a) → a.
  7. Occurs check. অন্য একটি function, fn(f) { return f(f); }: f : t1, ফল t2, constraint t1 ≐ (t1) → t2. t1 নিজেই ডান দিকের ভেতরে, তাই কোনো সসীম type সমাধান নয়: ব্যর্থ। f-কে নিজের ওপর ডাকা HM-এ type পায় না।

এবার algorithm-টি নিজে চালিয়ে দেখুন। Type রাখা হয়েছে সাধারণ Python মানে: "Int", "Bool" constant; ছোট হাতের string ("t1") type variable; আর ("->", p1, …, pn, ফল) function type. এক parameter-এর function-কে show() ML-এর ধাঁচে t2 -> t3 লেখে; Haat-এ একই type (t2) -> t3. এই block আর পরের দুটি block একই namespace ভাগ করে (পরেরটি চালালে এটি আগে চলে)।

INT, BOOL = "Int", "Bool"            # constants; type variables are lowercase: "t1", "a"
def isvar(t): return isinstance(t, str) and t[0].islower()
def fn(*ts): return ("->",) + ts     # ("->", p1, ..., pn, result)
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):                      # follow t1 -> t2 -> ... in the table S
    return walk(S[t], S) if isvar(t) and t in S else t
def apply(t, S):                     # replace every bound variable, all the way down
    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):                 # does variable v appear inside t?
    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")), ("t1", fn("t3", "t4"))],   # fn(f, x) { return f(f(x)); }
          [("t1", fn("t1", "t2"))],                          # fn(f) { return f(f); }
          [(fn(INT, "t2"), fn(BOOL, "t3"))]):                # Int -> t2 = Bool -> t3
    S, log = {}, []
    try:  # solve the constraints one by one
        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 -> t3 = t3 -> t4
  bind t2 := t3
  bind t3 := t4
answer: t1 = t4 -> t4, t2 = t4, t3 = t4
solve t1 = t1 -> t2
  error: occurs check: t1 occurs in t1 -> t2
solve Int -> t2 = Bool -> t3
  error: cannot unify Int with Bool

প্রথম ছয় লাইন stepper-এর ধাপ ২ থেকে ৬: দ্বিতীয় solve লাইনে t1 ইতিমধ্যে walk করে t2 -> t3 হয়ে গেছে, তারপর দুটি bind. answer-এ প্রতিটি variable-এর শেষ মান। পরের দুই লাইন occurs check: f(f)-এর constraint ব্যর্থ। শেষ দুই লাইন clash: decompose-এর পর Int ≐ Bool, দুটি আলাদা constant. বাস্তব checker এই বার্তাকে Haat-এর ধাঁচে অবস্থানসহ লিখত, যেমন type mismatch: expected Int, found Bool.

উপপাদ্য ৩৫.১ — type-এর ওপর unification (Robinson ১৯৬৫-এর ফল, type-এ প্রয়োগ)

Type-সমীকরণের যেকোনো সসীম তালিকার জন্য ওপরের নিয়মগুলো থামে। সমাধান থাকলে ফলের S একটি MGU: অন্য যেকোনো সমাধান S′-কে S-এর পরে আরেকটি substitution চাপিয়ে পাওয়া যায়। সমাধান না থাকলে algorithm clash বা occurs check-এ ব্যর্থ হয়।

প্রমাণ term-এর জন্য যা, এখানেও হুবহু তাই, কারণ function type কেবল “→” functor-ওয়ালা একটি term; থামা আর সঠিকতার রূপরেখা পর্ব ১০-এর উপপাদ্য ১০.১-এ. Inference-এর জন্য MGU-র “সবচেয়ে সাধারণ” হওয়াটাই আসল কথা: twice-এর উত্তর ((t4) → t4, t4) → t4, যা ((Int) → Int, Int) → Int-এর চেয়ে বেশি সাধারণ; দ্বিতীয়টি প্রথমটির ওপর [t4 ↦ Int] চাপালে পাওয়া যায়, উল্টোটা যায় না।

৪ · Algorithm W — Hindley–Milner-এর ধাপগুলো

তত্ত্ব পরিষ্কার রাখতে HM সাধারণত একটি ছোট ভাষায় লেখা হয়: lambda calculus-এর সঙ্গে let. Expression মাত্র চার রকম: variable x, function λx. e (Haat-এ fn(x) { return e; }), call e1 e2, আর let x = e1 in e2; সঙ্গে আমরা Int/Bool literal আর if রাখব। Lambda calculus-কে গণনার মডেল হিসেবে দেখেছেন গণনার তত্ত্ব কোর্সের পর্ব ৪৯-এ; এখানে তার typed রূপ।

HM-এ type দুই স্তরের। সাধারণ type τ ::= Int ∣ Bool ∣ α ∣ τ → τ, যেখানে α একটি type variable. আর type scheme σ ::= ∀α1 … αn. τ: সামনে ∀ মানে “এই variable-গুলোর জায়গায় যেকোনো type বসানো যায়”। ∀ শুধু সবচেয়ে বাইরে বসে; (∀a. a → a) → Int-এর মতো ভেতরের ∀ HM-এ নেই (অংশ ৬-এ এর কারণ)। নিয়মগুলো, পর্ব ৩৪-এর নামেই, তবে T-Var আর T-Let এখন scheme নিয়ে কাজ করে:

(x : σ) ∈ Γ    τ হলো σ-এর একটি instance
Γ ⊢ x : τ
(T-Var)
Γ, x : τ1 ⊢ e : τ2
Γ ⊢ λx. e : τ1 → τ2
(T-Fn)
Γ ⊢ e1 : τ1 → τ2    Γ ⊢ e2 : τ1
Γ ⊢ e1 e2 : τ2
(T-Call)
Γ ⊢ e1 : τ1    Γ, x : gen(Γ, τ1) ⊢ e2 : τ2
Γ ⊢ let x = e1 in e2 : τ2
(T-Let)

দুটি নতুন শব্দ। Instantiation: ∀α. τ থেকে α-র জায়গায় কোনো type (inference-এ একটি নতুন variable) বসিয়ে একটি সাধারণ type পাওয়া। Generalisation: gen(Γ, τ) = ∀ᾱ. τ, যেখানে ᾱ হলো τ-এর সেই variable-গুলো যা Γ-তে মুক্ত অবস্থায় নেই। লক্ষ করুন, T-Fn-এ x পায় একটি সাধারণ τ1, scheme নয়; শুধু T-Let generalise করে। এই অসমতাই অংশ ৫-এর বিষয়।

নিয়মগুলো declarative: বলে কোন type বৈধ, কিন্তু T-Fn-এ τ1 কোথা থেকে আসবে তা বলে না। Milner ১৯৭৮ সালে এগুলো থেকে একটি algorithm দেন, Algorithm W: W(Γ, e) ফেরত দেয় একটি substitution S আর একটি type τ.

  1. x: Γ-তে x : ∀ᾱ. τ খুঁজে প্রতিটি α-র জায়গায় নতুন variable বসানো (instantiate); S খালি।
  2. λx. e: নতুন variable α নিয়ে (S1, τ1) = W(Γ ∪ {x : α}, e); ফল (S1, S1α → τ1).
  3. e1 e2: (S1, τ1) = W(Γ, e1); (S2, τ2) = W(S1Γ, e2); নতুন β; S3 = unify(S2τ1, τ2 → β); ফল (S3S2S1, S3β).
  4. let x = e1 in e2: (S1, τ1) = W(Γ, e1); σ = gen(S1Γ, τ1); (S2, τ2) = W(S1Γ ∪ {x : σ}, e2); ফল (S2S1, τ2).

নিচের block হুবহু এই চার নিয়ম (সঙ্গে literal আর if), আগের block-এর unify ব্যবহার করে। একটি বাস্তবায়ন-কৌশল: প্রতিবার substitution জোড়া না দিয়ে একটিই খাতা S সামনে বয়ে নেওয়া হয়েছে। Milner-এর একই প্রবন্ধে এমন একটি কার্যকর রূপ আছে, যাকে বলা হয় Algorithm J; ফলের type একই।

import itertools                       # uses walk, apply, unify, show from the block above
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})   # fresh copies of ∀-variables
def W(env, e, S, log):                  # env: name -> (∀-vars, type); returns (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()))
    vs = sorted(ftv(t) - busy); log.append(f"gen {e[1]} : forall {' '.join(vs)}. {show(t)}")
    return W({**env, e[1]: (vs, 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: t, S = W({}, e, {}, []); return show(nice(apply(t, S)))
    except TypeError as err: return f"error: {err}"
V = lambda x: ("var", x)
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:])
f, g, x, y, z, i = map(V, "fgxyzi")
use = ("if", A(i, ("bool", True)), A(i, ("int", 1)), ("int", 0))   # if i true then i 1 else 0
for name, e in [("id", L("x", body=x)), ("compose", L("f", "g", "x", body=A(f, A(g, x)))),
                ("twice", L("f", "x", body=A(f, A(f, x)))), ("S", L("x", "y", "z", body=A(x, z, A(y, z)))),
                ("let i = id", ("let", "i", L("x", body=x), use)), ("fn(i) use", L("i", body=use)),
                ("x(x)", L("x", body=A(x, x)))]:
    print(f"{name:11}:", infer(e))

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

id         : a -> a
compose    : (a -> b) -> (c -> a) -> c -> b
twice      : (a -> a) -> a -> a
S          : (a -> b -> c) -> (a -> b) -> a -> c
let i = id : Int
fn(i) use  : error: cannot unify Bool with Int
x(x)       : error: occurs check: t1 occurs in t1 -> t2

প্রথম চারটি ক্লাসিক উত্তর, পরীক্ষায় বারবার আসে। compose = λf.λg.λx. f (g x): g আগে x-এ চলে (c → a), f তার ফল নেয় (a → b), শেষ ফল b. twice-এ f-এর input আর output একই, অংশ ৩-এর ফলের এক-parameter রূপ। S combinator (λx.λy.λz. x z (y z)): x দুটি argument নেয় বলে a -> b -> c, যা আসলে a -> (b -> c); তির ডানদিকে জোড়া লাগে। শেষ তিনটি অংশ ৫ আর ৬-এর গল্প: let-এ বাঁধা i Bool আর Int দুটিতেই চলে, parameter i চলে না, আর x(x) occurs check-এ আটকায়।

উপপাদ্য ৩৫.২ — Algorithm W-এর sound আর complete হওয়া (Milner ১৯৭৮; Damas–Milner ১৯৮২)

Soundness: W(Γ, e) = (S, τ) হলে SΓ ⊢ e : τ. Completeness ও principality: কোনো substitution-এর পরে Γ-তে e-এর কোনো type থাকলে W ব্যর্থ হয় না, আর তার দেওয়া τ থেকে generalise করা scheme e-এর principal type: e-এর অন্য যেকোনো type এর একটি instance.

প্রমাণের রূপরেখা।

  1. Soundness: e-এর গঠনের ওপর induction. প্রতিটি ক্ষেত্রে W যে unify করে, তা নিয়মের premise-গুলো মেলায়; unify-এর ফল একটি সত্যিকারের unifier (উপপাদ্য ৩৫.১), তাই S চাপানোর পর T-Call-এর premise দুটি হুবহু সত্য। Let-এর ক্ষেত্রে gen শুধু Γ-তে না থাকা variable-কে ∀ দেয়, তাই T-Let খাটে।
  2. Completeness: আবার induction. মূল যুক্তি unify-এর MGU হওয়া: অন্য কোনো type-নির্ধারণ যে সমীকরণ মেলায়, তা W-এর পাওয়া S-এর পরে আরেকটি substitution, তাই W কোনো সম্ভাবনা হারায় না।
  3. ফলে W-এর উত্তরটিই সবচেয়ে সাধারণ; ব্যর্থ হলে e-এর কোনো type নেই। ∎ (পূর্ণ প্রমাণ Damas আর Milner-এর ১৯৮২ সালের POPL প্রবন্ধে আর Damas-এর ১৯৮৪ সালের thesis-এ।)

ধারণাটি স্বাধীনভাবে দুবার এসেছে। Roger Hindley ১৯৬৯ সালে combinatory logic-এ দেখান প্রতিটি typable term-এর একটি principal type-scheme আছে, আর তা unification দিয়ে বের করা যায়; এর আগে Haskell Curry-র কাজে এর বীজ ছিল বলে অনেক ইতিহাসবিদ মনে করেন। Robin Milner ১৯৭৮ সালে, Edinburgh-এর LCF theorem prover-এর meta language ML-এর জন্য, polymorphic let-সহ Algorithm W দেন আর বিখ্যাত বাক্যটি লেখেন: “well-typed programs cannot go wrong” (পর্ব ০২-এ ML-এর ইতিহাস)। Luis Damas আর Milner ১৯৮২ সালে W-এর completeness প্রমাণ করেন; তাই নামটি প্রায়ই Hindley–Milner বা Damas–Hindley–Milner.

৫ · Let-polymorphism — generalisation আর value restriction

পরিচয়-function id যা পায়, তাই ফেরত দেয়। দোকানের প্রতিটি তাকের জন্য আলাদা “যা দিলে তাই ফেরত” function লেখা হাস্যকর; একটিই function সব type-এ চলা উচিত। এটিই parametric polymorphism, আর HM এটি পায় let-polymorphism দিয়ে: let-এ বাঁধা মানের type generalise হয়, আর প্রতিটি ব্যবহারে নতুন কপি (instance) নেওয়া হয়। Stepper-এ অংশ ৪-এর let i = id উদাহরণের সত্যিকারের trace (একই engine, প্রতিটি ধাপ ছাপার জন্য একটি মোড়ক যোগ করে চালানো):

1let i = λx. x2in if i(true)3   then i(1)4   else 0
engine-এর খাতা
Γ
এখন
S
  1. Initializer. λx. x: x পায় নতুন t1, দেহ x-এর type t1, তাই t1 → t1. কোনো unify লাগেনি।
  2. Generalise. Γ খালি, তাই t1 Γ-এর কোথাও মুক্ত নেই। t1-কে ∀ দিয়ে বাঁধা যায়: i : ∀t1. t1 → t1. এখন i একটি scheme, একটি নির্দিষ্ট type নয়।
  3. প্রথম ব্যবহার। i(true)-তে i-এর নতুন কপি t2 → t2 (instantiate). Call-এর নিয়মে t2 → t2 ≐ Bool → t3: t2 ↦ Bool, তারপর t3 ↦ Bool. ফল Bool, তাই if-এর শর্ত ঠিক।
  4. দ্বিতীয় ব্যবহার। i(1)-এ আবার নতুন কপি, এবার t4 → t4. t4 ↦ Int, t5 ↦ Int. আগের t2-এর Bool এখানে বাধা দেয়নি, কারণ t2 আর t4 আলাদা variable.
  5. শেষ। else-শাখা 0 : Int, দুই শাখা Int ≐ Int. পুরো expression-এর type Int, ঠিক Python block-এর let i = id : Int.
  6. Parameter হলে? (λi. if i(true) then i(1) else 0)-এ i parameter, তাই একটি সাধারণ t1, কোনো ∀ নেই। i(true) t1-কে Bool → t2-তে বাঁধে, t2 ↦ Bool; i(1)-এ একই t1, অর্থাৎ Bool → Bool ≐ Int → t3, আর decompose-এ Bool ≐ Int: clash.

শেষ ধাপটি অদ্ভুত লাগতে পারে: দুটি program-এর অর্থ এক, একটিতে let, অন্যটিতে parameter. কিন্তু parameter-এর ক্ষেত্রে compiler জানে না কোন function আসবে; কেউ fn(n) { return n + 1; } দিলে তা Bool-এ চলবে না। let-এ মানটি চোখের সামনে, তাই তার type দেখে নিশ্চিত হওয়া যায় যে সত্যিই সব type-এ চলে। Parameter-কে polymorphic বানাতে হলে type-এ ভেতরের ∀ লাগে, (∀a. a → a) → Int, যা অংশ ৬-এর rank-2 type.

gen-এ “Γ-তে মুক্ত নয়” শর্ত কেন

ধরুন λx. let y = x in y(1). x পায় t1; y = x, তাই y-এর type t1. এখন যদি t1-কে generalise করে y : ∀t1. t1 বলি, তবে y যেকোনো type-এর ভান করবে, অথচ y আসলে x, আর x-এর type বাইরে থেকে ঠিক হবে। t1 Γ-তে (x : t1) মুক্ত, তাই gen তাকে ছোঁয় না। এই শর্তটিই block-এর busy সেট।

Value restriction — পরিবর্তনযোগ্য ঘর থাকলে

ML-এ পরিবর্তনযোগ্য ঘর আছে (ref). ধরুন let r = ref []: type 'a list ref. সব variable generalise করলে r : ∀a. a list ref; তারপর একবার r-এ Int-এর list লিখে আরেকবার Bool-এর list হিসেবে পড়া যায়। Type checker খুশি, অথচ চলার সময় একটি Int-কে Bool ধরা হলো: soundness ভাঙল। Standard ML-এর সমাধান value restriction (Andrew Wright-এর ১৯৯৫ সালের প্রস্তাব বলে পরিচিত; SML ’97 এটি নেয়): শুধু syntactic value (function expression, literal, variable) হলে generalise; ref []-এর মতো একটি call হলে নয়। OCaml এর একটি শিথিল রূপ ব্যবহার করে (Garrigue, ২০০৪ সালের দিকে, হেজসহ)।

Haat-এর বর্ধিত রূপে একই প্রশ্ন ওঠে var-এ। var f = fn(x) { return x; };-কে ∀ দিলে পরে f = fn(x) { return x + 1; }; বৈধ হবে (একটি instance), তারপর f(true) চলবে আর Bool-এ 1 যোগ হবে। তাই অংশ ৭-এর নিয়ম: শুধু let আর fn ঘোষণা generalise হয়, var কখনো নয়।

৬ · Principal type, decidability আর HM-এর সীমা

HM-এর তিনটি গুণ একসাথে বিরল। এক, decidable: প্রতিটি program-এ algorithm থামে আর হ্যাঁ বা না বলে। দুই, principal type: উত্তর একটিই, সবচেয়ে সাধারণ, তাই কোন উত্তর বাছতে হবে সে প্রশ্ন নেই। তিন, annotation লাগে না: একটি type-ও না লিখে পুরো program চলে। কিন্তু Rice-এর উপপাদ্য (গণনার তত্ত্ব কোর্সের পর্ব ৫৩) মনে করিয়ে দেয়: decidable হওয়ার দাম হলো কিছু ঠিক program-ও বাদ পড়ে।

প্রস্তাব ৩৫.৩ — λx. x x-এর কোনো HM type নেই

খালি Γ-তে λx. x x-এর জন্য কোনো type τ নেই যাতে ⊢ λx. x x : τ.

প্রমাণ।

  1. ধরা যাক আছে। T-Fn ছাড়া λ-র কোনো নিয়ম নেই, তাই কোনো τ1-এর জন্য x : τ1 ⊢ x x : τ2.
  2. x x একটি call, তাই T-Call-এ কোনো σ-এর জন্য x : σ → τ2 আর x : σ.
  3. x λ-তে বাঁধা, তাই তার type scheme নয়, একটিই τ1; T-Var-এ instance মানে τ1 নিজেই। ফলে τ1 = σ → τ2 আর τ1 = σ, অর্থাৎ σ = σ → τ2.
  4. Type-গুলো সসীম গাছ; σ → τ2-এর আকার σ-এর আকারের চেয়ে কঠোরভাবে বড়, তাই দুটি সমান হতে পারে না। স্ববিরোধ। ∎

Block-এর x(x) লাইনের occurs check এই প্রমাণেরই যান্ত্রিক রূপ। অথচ (λx. x x)(λy. y) চালালে কোনো ভুল ঘটে না: ফল λy. y. HM এটিকে বাদ দেয়, কারণ নিরাপদ program-এর সব কিছু ধরতে গেলে decidability হারাতে হয়।

খরচ: তত্ত্বে সূচকীয়, বাস্তবে দ্রুত

১৯৯০ সালে দুটি স্বাধীন কাজ (Mairson; Kfoury, Tiuryn আর Urzyczyn) দেখায় যে ML-এর typability DEXPTIME-complete: সবচেয়ে খারাপ ক্ষেত্রে সময় সূচকীয়। কারণ nested let: let p1 = fn(x) { (x, x) }, let p2 = fn(x) { p1(p1(x)) } … ধরনের শিকলে type-এর আকার প্রতি ধাপে বর্গ হয়। কিন্তু বাস্তব program-এ এমন গঠন প্রায় আসে না, আর উত্তম বাস্তবায়নে inference প্রায় রৈখিক সময়ে চলে বলে সাধারণ অভিজ্ঞতা।

তিনটি দেয়াল

Rank-2 আর তার বেশি

ভেতরের ∀ সহ type, যেমন (∀a. a → a) → Int, System F-এর জগৎ। J. B. Wells (১৯৯৪ সালে ঘোষণা, ১৯৯৯ সালে journal-এ) দেখান System F-এ typability আর type checking দুটিই undecidable. Rank-2-এ inference decidable, rank-3 থেকে নয় (Kfoury–Wells-এর কাজ, হেজসহ)। তাই GHC-এর RankNTypes-এ annotation লিখতে হয়।

Subtyping

t1 ≐ τ-এর বদলে t1 <: τ ধরনের অসমতা আসে। একটি variable-এর ওপরের আর নিচের সীমা জমে, আর সাধারণত একটি principal উত্তর থাকে না বা খুব জটিল হয়। Java, Scala, TypeScript তাই local আর bidirectional inference বেছে নিয়েছে (Pierce–Turner-এর ২০০০ সালের “Local Type Inference” এর পরিচিত ভিত্তি)। Subtyping-এর formal নিয়ম পর্ব ৩৬-এ।

Overloading

Haat-এ + Int আর Str দুটিতেই চলে (নকশা-সিদ্ধান্ত ১১)। fn(a, b) { return a + b; }-এর type কী? (Int, Int) → Int না (Str, Str) → Str? কোনোটিই অন্যটির instance নয়, তাই principal type নেই। OCaml আলাদা operator রাখে (+, +., ^); Haskell type class আনে (Wadler–Blott, ১৯৮৯), যেখানে type হয় Num a ⇒ a → a → a.

আরও গভীরে: বাস্তব compiler W-কে হুবহু চালায় না। OCaml “level”-ভিত্তিক generalisation ব্যবহার করে (Didier Rémy-এর ১৯৯০-এর দশকের শুরুর কাজ থেকে বলে পরিচিত), যাতে gen-এর সময় পুরো Γ ঘুরতে না হয়; আর unification করে mutable reference দিয়ে, union-find-এর মতো। GHC-এর inference একটি constraint-সমাধান কাঠামো, OutsideIn(X) (Vytiniotis ও সহকর্মী, ২০১১), যা type class, GADT আর type family সামলায়। ভুলের বার্তা ভালো করার গবেষণাও বড় একটি ধারা: unification ব্যর্থ হলে আসল দোষী লাইন প্রায়ই অনেক দূরে থাকে।

৭ · Haat-এর বর্ধিত রূপ — parameter-এ type না লিখে

এবার Haat-এ HM যোগ করার একটি প্রস্তাব। এটি Haat-এর বর্ধিত রূপ: reference বাস্তবায়ন এটি করে না, আর Haat v1-এর parser আজও অংশ ১-এর expected ':' error দেয়। প্রস্তাবের নিয়ম:

  • Parameter-এর : T আর return-এর -> T ঐচ্ছিক; না থাকলে নতুন type variable. লেখা থাকলে সেটি একটি বাড়তি constraint.
  • Top-level আর nested fn ঘোষণা এবং let generalise হয়; var কখনো নয় (অংশ ৫)।
  • Function-এর দেহে নিজের নাম একটি সাধারণ type পায় (∀ ছাড়া), তাই recursion চলে কিন্তু নিজের ভেতরে নিজেকে দুই type-এ ডাকা যায় না; HM-এর এই পরিচিত নিয়মকে বলে monomorphic recursion.
  • + - * / এই প্রস্তাবে শুধু Int-এ; Str জোড়ার জন্য আলাদা operator লাগবে (অংশ ৬-এর overloading-সমস্যা এড়াতে)।
// Haat-এর বর্ধিত রূপ (reference-এ নেই)
fn twice(f, x) { return f(f(x)); }
fn price(qty, unit) {
    let p = qty * unit;
    return p - p / 10;
}
let a = twice(fn(k) { return k + 60; }, 100);
let b = twice(fn(ok) { return ok; }, true);
let c = price(2, true);     // ভুল: unit-এ Bool

নিচের block এই program-এর AST (reference-এর node-নাম FnDecl, Let, Return, Call, Lambda, Binary, Var, Num, Bool, এখানে Python tuple হিসেবে) নিয়ে আগের দুই block-এর unify, inst, ftv দিয়ে type বের করে। Reference-এর typechecker.py-এর সঙ্গে তুলনা করুন: সেখানে প্রতিটি node-এ type যাচাই, এখানে সমীকরণ। পুরো type checker-এর বাস্তবায়ন পর্ব ৫২-এ (Type checker বাস্তবায়ন — Haat-এর type নিয়ম কোডে)।

def hs(t): return t if isinstance(t, str) else "(" + ", ".join(map(hs, t[1:-1])) + ") -> " + hs(t[-1])
def expr(env, e, S):                    # Haat AST as tuples; hs() prints (Int, a) -> Int
    k = e[0]
    if k in ("Num", "Bool"): return (INT if k == "Num" else BOOL), S
    if k == "Var": return inst(*env[e[1]]), S
    if k == "Binary":                   # this extension: + - * / >= on Int only
        for side in e[2:]: t, S = expr(env, side, S); S = unify(t, INT, S, [])
        return (BOOL if e[1] == ">=" else INT), S
    if k == "Call":
        tf, S = expr(env, e[1], S); ts = []
        for a in e[2]: t, S = expr(env, a, S); ts.append(t)
        r = fresh(); return r, unify(tf, fn(*ts, r), S, [])
    return func(env, None, e[1], e[2], S)                         # "Lambda"
def func(env, name, params, body, S):  # parameters without types get type variables
    ps, ret = [fresh() for _ in params], fresh()
    env = {**env, **{p: ([], t) for p, t in zip(params, ps)}}
    if name: env[name] = ([], fn(*ps, ret))                       # recursion: one type
    return fn(*ps, ret), block(env, body, ret, S, "  ")
def block(env, stmts, ret, S, indent=""):
    for s in stmts:
        if s[0] == "Return": t, S = expr(env, s[1], S); S = unify(t, ret, S, []); continue
        t, S = func(env, *s[1:], S) if s[0] == "FnDecl" else expr(env, s[2], S)
        t = apply(t, S); busy = set().union(*(ftv(apply(ty, S)) - set(vs) for vs, ty in env.values()))
        env = {**env, s[1]: (sorted(ftv(t) - busy), t)}           # let/fn: generalise
        m = {u: "abcd"[j] for j, u in enumerate(sorted(ftv(t) - busy))}
        print(f"{indent}{s[1]:6}: {hs(apply(t, m))}" + ("   forall " + " ".join(m.values()) if m else ""))
    return S
v, n, call = (lambda x: ("Var", x)), (lambda k: ("Num", k)), (lambda f, *a: ("Call", ("Var", f), list(a)))
try: block({}, [("FnDecl", "twice", ["f", "x"], [("Return", call("f", call("f", v("x"))))]),
    ("FnDecl", "price", ["qty", "unit"], [("Let", "p", ("Binary", "*", v("qty"), v("unit"))),
        ("Return", ("Binary", "-", v("p"), ("Binary", "/", v("p"), n(10))))]),
    ("Let", "a", call("twice", ("Lambda", ["k"], [("Return", ("Binary", "+", v("k"), n(60)))]), n(100))),
    ("Let", "b", call("twice", ("Lambda", ["ok"], [("Return", v("ok"))]), ("Bool", True))),
    ("Let", "c", call("price", n(2), ("Bool", True)))], "Unit", {})
except TypeError as err: print("error:", err)

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

twice : ((a) -> a, a) -> a   forall a
  p     : Int
price : (Int, Int) -> Int
a     : Int
b     : Bool
error: cannot unify Int with Bool

twice generalise হয়ে ∀a; তাই a-তে Int-এর function আর b-তে Bool-এর function দুটিই বৈধ, অংশ ৫-এর মতো। price-এর ভেতরের let p (দুই ঘর সরানো লাইন) নিজেই inference পেয়েছে, আর * থেকে qty, unit দুটিই Int. শেষ লাইনে price(2, true): (Int, Int) → Int ≐ (Int, Bool) → t, decompose-এ Int ≐ Bool. একই program-এ সব type লিখে (annotation-সহ) reference-এ check করলে সত্যিকারের বার্তা আসে 9:18: error: type mismatch: expected Int, found Bool, argument true-এর শুরুতে (নকশা-সিদ্ধান্ত ২৪)। এই খসড়া অবস্থান রাখে না; অবস্থান রাখার কৌশল অনুশীলন ৩-এ।

এই প্রস্তাবের খরচও আছে। Haat v1-এ function-এর ঘোষণা পড়েই তার type জানা যায়, আর ভুলের বার্তা সবসময় ঘোষণার কাছে আসে। HM-এ ভুল ধরা পড়ে যেখানে দুটি দাবি প্রথম সংঘর্ষে পড়ে, যা ভুলের উৎস থেকে অনেক দূরে হতে পারে। এজন্য Haskell-এর রীতিতে top-level function-এ type লেখা ভালো অভ্যাস ধরা হয়, আর Rust function-এর signature-এ type বাধ্যতামূলক রেখে শুধু দেহের ভেতরে infer করে।

৮ · বাস্তব ভাষায় type inference — OCaml থেকে TypeScript

ভাষাকতটা infer করেযা লিখতেই হয়
OCaml, Standard MLপুরো program, HM (value restriction-সহ)প্রায় কিছুই না; module interface ঐচ্ছিক
Haskell (GHC)HM + type class; বহু extensionRank-N, কিছু GADT; top-level signature রীতি হিসেবে
Rustfunction-এর দেহের ভেতরে HM-ধাঁচেরfunction-এর parameter আর return type
Kotlin, Swift, Scalalocal + প্রসঙ্গ থেকে lambda-র parameterfunction parameter (Scala-তে recursive function-এর return-ও)
TypeScriptlocal + contextual typingfunction parameter (প্রসঙ্গ না থাকলে)
C++11 auto, Java 10 var, C# 3 varinitializer থেকে variableparameter (C++20-এ abbreviated template ছাড়া)
Haat v1let/var-এর initializer থেকেparameter, return (Unit হলে বাদ)

OCaml-এ let compose f g x = f (g x) লিখলে toplevel দেখায় ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b (উদাহরণ, এখানে চালানো হয়নি; OCaml variable-এর নামের আগে ' দেয়)। অংশ ৪-এর block-এর উত্তরের সঙ্গে নামসহ হুবহু মিল, কারণ দুটিই প্রথম দেখার ক্রমে নাম দেয়।

TypeScript-এর সত্যিকারের run — local inference কোথায় থামে

TypeScript-এর compiler --declaration দিলে প্রতিটি export-এর infer করা type একটি .d.ts ফাইলে লিখে দেয়; ফলে editor-এর hover ছাড়াই আসল inference দেখা যায়। সত্যিকারের run: TypeScript 5.9.2 (Apache-2.0; tsc কোনো usage data পাঠায় না), tsc --strict --declaration --emitDeclarationOnly --target es2022 --module es2022 infer.ts:

// infer.ts
export function discount(p: number) { return p >= 1000 ? p - Math.trunc(p / 10) : p; }
export const id = <T,>(x: T) => x;
export function twice<T>(f: (x: T) => T, x: T) { return f(f(x)); }
export const totals = [520, 1040].map(p => discount(p));
export const mixed = [discount(2000), id("bkash")];
export let count = 0;
export function compose(f, g) { return (x) => f(g(x)); }
infer.ts(7,25): error TS7006: Parameter 'f' implicitly has an 'any' type.
infer.ts(7,28): error TS7006: Parameter 'g' implicitly has an 'any' type.
infer.ts(7,41): error TS7006: Parameter 'x' implicitly has an 'any' type.

// infer.d.ts (error সত্ত্বেও লেখা হয়)
export declare function discount(p: number): number;
export declare const id: <T>(x: T) => T;
export declare function twice<T>(f: (x: T) => T, x: T): T;
export declare const totals: number[];
export declare const mixed: (string | number)[];
export declare let count: number;
export declare function compose(f: any, g: any): (x: any) => any;

চারটি জিনিস পড়ুন। এক, return type সব জায়গায় infer হয়েছে: discount-এর number, twice-এর T. দুই, .map(p => …)-এ p-এর type কেউ লেখেননি; map-এর ঘোষণা থেকে প্রসঙ্গ দেখে (contextual typing) p পেয়েছে number. তিন, mixed-এ দুই আলাদা type-এর উপাদান; HM হলে clash হতো, কিন্তু TypeScript-এ union type আর subtyping আছে, তাই উত্তর (string | number)[]. চার, সবচেয়ে গুরুত্বপূর্ণ: compose-এর parameter-এর type TypeScript ব্যবহার দেখে বের করে না, any ধরে নেয়, আর --strict-এ তা error TS7006. অংশ ৪-এর block একই function-এর জন্য দিয়েছিল (a → b) → (c → a) → c → b. Generics-এর type parameter <T> TypeScript-এ নিজে লিখতে হয়; HM তা নিজেই খুঁজে পায়। TypeScript-এর মৌলিক পরিচয় JavaScript কোর্সের পর্ব ৪৭-এ, আর Python-এর type hint-এ একই local ধারা Python কোর্সের পর্ব ৪০-এ.

C++-এর auto-এর নিয়ম আসলে template argument deduction-এর নিয়ম (C++ কোর্সের পর্ব ২৮-এ), যা একটি এক-দিকের pattern match: argument-এর type থেকে T বের করা, পরে কোনো সমীকরণ জমিয়ে রাখা নয়। Java-র generics-এ method call-এর type argument-ও infer হয় (Java কোর্সের পর্ব ২৮), কিন্তু Java-র subtyping-এর কারণে সেখানে সমীকরণের বদলে সীমা (bound) নিয়ে কাজ হয়।

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

  • λf.λg.λx. f (g x)-এর principal type? (a → b) → (c → a) → c → b.
  • Type checking আর type inference-এর পার্থক্য? Checking-এ type দেওয়া থাকে, শুধু যাচাই; inference-এ অজানা type variable আর constraint থেকে type বের করা হয়।
  • Occurs check কী, type inference-এ কেন লাগে? t ≐ (…t…) ধরনের সমীকরণ ব্যর্থ করে; না করলে অসীম type তৈরি হয়, যেমন λx. x x-এ।
  • Let-polymorphism কী? let-এ বাঁধা মানের type-এ Γ-তে মুক্ত নয় এমন variable ∀ দিয়ে generalise হয়, আর প্রতি ব্যবহারে নতুন instance; λ-parameter এভাবে generalise হয় না।
  • HM decidable কি, খরচ কত? হ্যাঁ, principal type-সহ; সবচেয়ে খারাপ ক্ষেত্রে DEXPTIME-complete, বাস্তবে দ্রুত।

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

“এই function-এর type কী?” প্রশ্নে AI assistant প্রায়ই সঠিক দেখতে উত্তর দেয়, কিন্তু type inference এমন বিষয় যেখানে একটি variable-এর নাম ভুল হলেই উত্তর ভুল। এই বিষয়ে যে ভুলগুলো বারবার দেখা যায়:

AI-এর ভুলকীভাবে ধরবেন
Principal type-এর বদলে একটি instance বলা, যেমন compose-এর type (Int → Int) → (Int → Int) → Int → Intনিজের ছোট W engine বা OCaml/GHCi-এ চালিয়ে মেলানো
Variable-এর মিল ভুল: compose-এর উত্তরে (a → b) → (b → c) → a → c (এটি আসলে pipe-এর type)প্রতিটি তির কোন parameter-এর, তা AST ধরে মিলিয়ে দেখা
“TypeScript parameter-এর type ব্যবহার দেখে infer করে”: এক ভাষার নিয়ম অন্য ভাষায়tsc --strict --declaration চালিয়ে .d.ts পড়া
λ-parameter-কে polymorphic ধরে নেওয়া, ফলে বলা “এটি compile হবে”let আর parameter দুই রূপ লিখে checker-এ চালানো
Unification-এর কোডে occurs check বাদ দেওয়া, বা walk না করে তুলনাt1 ≐ (t1) → t2 আর শিকলওয়ালা test case দিয়ে চালানো
“HM rank-2 type infer করে” বা “Rust পুরো program infer করে” ধরনের ভুল দাবিভাষার reference বা মূল প্রবন্ধ দেখা; annotation বাদ দিয়ে compiler-এ চালানো

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

আমি Hindley–Milner type inference শিখছি। নিচের expression-গুলোর principal type বের করো: λf.λg.λx. f (g x), λx.λy.λz. x z (y z), আর let i = λx. x in if i true then i 1 else 0. ১. প্রতিটির জন্য আগে type variable আর constraint-এর তালিকা দাও, তারপর unification-এর প্রতিটি ধাপ (bind, decompose, occurs check) আলাদা লাইনে লেখো। ২. কোনো ধাপে নিশ্চিত না হলে "নিশ্চিত নই" বলো; উত্তর অনুমান করে লিখবে না। ৩. একই উত্তর OCaml-এর toplevel-এ কেমন দেখাবে লেখো, আর বলো আমাকে কোন command চালিয়ে যাচাই করতে হবে। ৪. TypeScript 5.9-এ একই function parameter-এ type ছাড়া লিখলে কী হবে, তা অনুমান না করে আমাকে চালিয়ে দেখতে বলো।

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

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

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

প্র ০১Type inference প্রথম একটি theorem prover-এর ভাষায় এল কেন? ML-এর জন্মের গল্প inference-এর নকশায় কী ছাপ রেখেছে?

১৯৭০-এর দশকের শুরুতে Robin Milner Edinburgh-এ LCF নামের একটি interactive theorem prover বানাচ্ছিলেন। ব্যবহারকারী প্রমাণের কৌশল (tactic) লিখতেন একটি ছোট প্রোগ্রামিং ভাষায়, যার নাম দেওয়া হয় ML, অর্থাৎ meta language. এই ভাষার মূল কাজ ছিল theorem নামের একটি type রক্ষা করা: একটি theorem মান শুধু যুক্তিবিদ্যার বৈধ নিয়ম খাটিয়েই তৈরি হতে পারবে। Type system তাই এখানে গৌণ সুবিধা নয়, পুরো ব্যবস্থার নিরাপত্তার ভিত্তি। ভুল type-এর মান theorem হিসেবে ঢুকে গেলে ভুল কথাও “প্রমাণিত” হয়ে যেত।

একই সঙ্গে tactic-গুলো ছিল higher-order function-এর ঘন জাল: tactic নেয়, tactic ফেরত দেয়, অন্য tactic-এর সঙ্গে জোড়া লাগায়। প্রতিটির type হাতে লিখলে প্রায় প্রতিটি লাইনের চেয়ে type বড় হয়ে যেত। আর একই জোড়া লাগানোর function (যেমন “এটা ব্যর্থ হলে ওটা চেষ্টা করা”) বহু ধরনের মানে খাটে, তাই polymorphism অপরিহার্য। এই দুই চাপ, শক্ত নিরাপত্তা আর লেখার হালকা ভার, একসাথে মেলাতে Milner বেছে নেন: type লিখতে হবে না, কিন্তু compiler প্রতিটি মানের সবচেয়ে সাধারণ type বের করবে আর ভুল হলে চালানোর আগেই থামাবে।

Hindley ১৯৬৯ সালে combinatory logic-এর জন্য principal type-scheme-এর ফলটি পেয়েছিলেন, কিন্তু তিনি প্রোগ্রামিং ভাষা নিয়ে কাজ করছিলেন না; Milner স্বাধীনভাবে একই ধারণায় পৌঁছান আর তাতে polymorphic let যোগ করেন, যা প্রোগ্রামিং-এর জন্য জরুরি। ১৯৭৮ সালের প্রবন্ধে তিনি Algorithm W দেন আর semantic soundness প্রমাণ করেন। Damas তাঁর ছাত্র হিসেবে ১৯৮২ সালে completeness প্রমাণ করেন। ML পরে LCF ছাড়িয়ে Standard ML, OCaml আর পরোক্ষে Haskell, F#, Rust, Swift-এর পূর্বপুরুষ হয়।

এই জন্মকথার ছাপ আজও দেখা যায়: ML-পরিবারে type error কখনো সতর্কতা নয়, সবসময় program বাতিল; আর ML-পরিবারের ভাষা আজও proof assistant আর compiler লেখার প্রিয় হাতিয়ার (Coq/Rocq OCaml-এ লেখা)।

মূল উপলব্ধি: Type inference এসেছিল একটি বাস্তব চাহিদা থেকে: theorem prover-এর নিরাপত্তা না হারিয়ে higher-order আর polymorphic কোড হালকাভাবে লেখা।

প্র ০২Compiler যদি সব type বের করতে পারে, তবু Haskell-এ top-level function-এ type লেখার রীতি আর Rust-এ signature বাধ্যতামূলক কেন?

Type-এর দুটি কাজ: compiler-কে তথ্য দেওয়া, আর মানুষকে তথ্য দেওয়া। Inference প্রথম কাজটি সারে, দ্বিতীয়টি নয়। একটি function-এর signature হলো একটি চুক্তি: “আমাকে এই দিন, আমি এই দেব”। ব্যবহারকারী শুধু চুক্তি পড়ে কাজ সারতে পারেন, দেহ পড়তে হয় না। Signature না থাকলে চুক্তি লুকিয়ে থাকে দেহের ভেতরে, আর দেহ বদলালে চুক্তিও চুপচাপ বদলে যায়।

দ্বিতীয় কারণ ভুলের বার্তা। HM-এ ভুল ধরা পড়ে যেখানে দুটি দাবি প্রথম সংঘর্ষে পড়ে। ধরুন একটি function-এর ভেতরে একটি টাইপো তার type বদলে দিল; inference সেই নতুন type-কেই সত্য ধরে নেয়, আর error আসে দূরের কোনো file-এ, যেখানে function-টি ডাকা হয়েছে। বার্তা বলে “Int আর Bool মেলে না”, অথচ আসল ভুল অন্য জায়গায়। Signature লেখা থাকলে সংঘর্ষটি function-এর নিজের সীমানাতেই ঘটে, তাই বার্তা আসে ঠিক জায়গা থেকে। Haskell community-তে তাই top-level-এ signature লেখা ব্যাপক রীতি, আর GHC-এর একটি সতর্কতা (-Wmissing-signatures) এটি মনে করিয়ে দেয়।

Rust এটিকে নিয়ম বানিয়েছে। কারণ আংশিক নকশাগত: Rust-এর compile-এর একক বড়, আর একটি function-এর দেহ বদলালে যদি তার type বদলায় তবে অন্য বহু function আবার check করতে হতো; signature থাকলে প্রতিটি function আলাদাভাবে check করা যায়। আর library-র API স্থির রাখার প্রশ্ন: public function-এর type দুর্ঘটনায় বদলালে downstream কোড ভাঙে। Rust তাই দেহের ভেতরে সমৃদ্ধ inference দেয়, কিন্তু সীমানায় annotation চায়। Haat v1-ও একই কারণে parameter-এ type চায় (পর্ব ০৬), আর অংশ ৭-এর বর্ধিত রূপে annotation ঐচ্ছিক রাখা হয়েছে, বাদ দেওয়া হয়নি।

উল্টো যুক্তিও শক্তিশালী: ছোট helper function, lambda আর local variable-এ type লিখলে কোড ভারী হয়, আর type-এর নাম লম্বা হলে (iterator-এর chain, nested generic) তা প্রায় অপাঠ্য। তাই বাস্তব রীতি দাঁড়িয়েছে মাঝামাঝি: সীমানায় লিখুন, ভেতরে infer করতে দিন।

মূল উপলব্ধি: Inference লেখার ভার কমায়, কিন্তু signature হলো মানুষের জন্য documentation আর error-এর বেড়া; তাই module বা function-এর সীমানায় type লেখা আজও ভালো নকশা।

প্র ০৩HM-এর type error-এর বার্তা প্রায়ই বিভ্রান্তিকর কেন? Unification-এর ক্রম কি ফল বদলায়?

Unification-এর ফল, অর্থাৎ program typable কি না আর principal type কী, constraint-গুলোর ক্রমের ওপর নির্ভর করে না; MGU যেকোনো ক্রমে একই (variable-এর নাম বদল বাদে)। কিন্তু কোথায় ব্যর্থতা ধরা পড়ে, তা ক্রমের ওপর পুরোপুরি নির্ভর করে। ধরুন তিনটি constraint: t ≐ Int (লাইন ৩), t ≐ Bool (লাইন ২০), t ≐ Int (লাইন ৪০)। বাম থেকে ডানে সমাধান করলে লাইন ২০-এ সংঘর্ষ ধরা পড়ে, আর বার্তা আঙুল তোলে লাইন ২০-এর দিকে। কিন্তু দুই-তৃতীয়াংশ ব্যবহার Int চায়, তাই আসল ভুল সম্ভবত লাইন ২০-ই; অথচ অন্য উদাহরণে আসল ভুল প্রথম লাইনে থাকতে পারে, আর W তখনো দোষ দেয় পরের লাইনকে।

Algorithm W-এর এই পক্ষপাত সুপরিচিত: সে AST বাম থেকে ডানে, ভেতর থেকে বাইরে ঘোরে, আর প্রথম যে দাবি পায় তাকেই সত্য ধরে। Milner-এর পরে বহু গবেষণা এই সমস্যা নিয়ে: Algorithm M (ওপর থেকে প্রত্যাশিত type নিচে পাঠানো, যাতে ভুল আগে ধরা পড়ে), type error slicing (সংঘর্ষে জড়িত সব লাইন দেখানো), আর constraint-ভিত্তিক পদ্ধতি যেখানে আগে সব constraint জমিয়ে পরে সবচেয়ে সম্ভাব্য দোষী খোঁজা হয়। কিছু গবেষণা পরিসংখ্যান বা শেখা মডেল দিয়েও দোষী লাইন অনুমান করার চেষ্টা করেছে; এগুলোর বেশিরভাগ গবেষণার স্তরে।

দ্বিতীয় কারণ, বার্তার ভাষা। Unification ব্যর্থ হলে engine জানে শুধু দুটি type, “Int আর Bool মেলে না”, কিন্তু কোন দুটি ব্যবহার এই দুটি দাবি এনেছে, সেই ইতিহাস না রাখলে তা বলতে পারে না। ভালো compiler তাই প্রতিটি constraint-এর সঙ্গে তার উৎস (লাইন, কোন node) রাখে। Elm আর Rust-এর মতো ভাষা বার্তার মান নিয়ে বিশেষ পরিশ্রম করেছে বলে পরিচিত। Haat-এর বার্তার নিয়ম, অবস্থান হলো অপরাধী expression-এর শুরু (নকশা-সিদ্ধান্ত ২৪), inference-এ রক্ষা করা সহজ নয়, কারণ দোষী expression কোনটি তা-ই অস্পষ্ট।

ব্যবহারিক পরামর্শ: inference-এর ভাষায় বিভ্রান্তিকর error পেলে সন্দেহজনক জায়গায় একটি type annotation বসান। Annotation একটি নতুন, আগে-সমাধান-হওয়া constraint, যা সংঘর্ষকে আপনার বেছে নেওয়া জায়গায় টেনে আনে। এটি binary search-এর মতো: অর্ধেক অংশে annotation দিয়ে দেখুন error কোন পাশে যায়।

মূল উপলব্ধি: HM-এর উত্তর ক্রম-নিরপেক্ষ, কিন্তু ব্যর্থতার অবস্থান ক্রম-নির্ভর; ভালো বার্তার জন্য constraint-এর উৎস রাখা আর annotation দিয়ে খোঁজ ছোট করা দুটোই দরকার।

প্র ০৪Haat-এর + Int আর Str দুটিতেই চলে। HM-ভিত্তিক Haat-এ এটি রাখতে চাইলে কী কী পথ আছে, আর প্রতিটির দাম কী?

সমস্যাটি এই: fn add(a, b) { return a + b; }-এর দুটি সম্ভাব্য type, (Int, Int) → Int আর (Str, Str) → Str, কোনোটি অন্যটির instance নয়, আর ∀a. (a, a) → a বললে Bool-এর জন্যও বৈধ হয়ে যায়, অথচ Bool যোগ হয় না। তাই principal type-এর গ্যারান্টি ভেঙে পড়ে। চারটি পরিচিত পথ।

এক, আলাদা operator (OCaml-এর পথ): Int-এ +, float-এ +., string-এ ^. HM অটুট থাকে, ভুলের বার্তা সরল, কিন্তু লেখা একটু অস্বস্তিকর আর নতুন শিক্ষার্থীর জন্য অপরিচিত। অংশ ৭-এর প্রস্তাব এই পথ নিয়েছে।

দুই, default (Standard ML-এর পথ): + overloaded, কিন্তু প্রসঙ্গ থেকে type ঠিক না হলে Int ধরে নেওয়া হয়। ফলে add হয় (Int, Int) → Int, আর পরে Str-এ ডাকলে error, যদিও function-টি আসলে Str-এও কাজ করত। নিয়মটি সরল, কিন্তু function-এর type নির্ভর করে কোথায় সে ঘোষিত, যা অনেককে চমকে দেয়।

তিন, type class (Haskell-এর পথ, Wadler আর Blott ১৯৮৯): type-এ শর্ত যোগ হয়, ∀a. Add a ⇒ (a, a) → a, আর Int ও Str-কে Add class-এর সদস্য ঘোষণা করা হয়। Principal type আবার ফিরে আসে, শর্তসহ। দাম: ভাষায় নতুন একটি স্তর, compiler-কে চলার সময় সঠিক “যোগ” পৌঁছাতে dictionary পাঠাতে হয় (পর্ব ৩৭-এর dictionary passing), আর ambiguity-র নতুন ধরনের error আসে।

চার, local inference আর annotation (TypeScript, Rust-এর সীমানার পথ): parameter-এ type লিখতে হয়, তাই overloading-এর সমাধান সহজ, শুধু operand-এর জানা type দেখে বাছাই। Haat v1 ঠিক এটিই করে: বাম operand ঠিক করে ডান operand কী হবে (নকশা-সিদ্ধান্ত ১১)।

অনুশীলন ৩-এ ==-এর ক্ষেত্রে একই সমস্যার ছোট রূপ দেখবেন: দুই operand একই type, তবে সেই type Int, Bool বা Str হতে হবে। Inference শেষে type এখনো মুক্ত থাকলে উত্তর অস্পষ্ট (ambiguous). এটি type class-এর ভাবনার একটি সরল সংস্করণ।

মূল উপলব্ধি: Overloading আর principal type একসাথে চাইলে type-এ শর্ত (type class) আনতে হয়; নইলে আলাদা operator, default বা annotation, প্রতিটিতে কিছু ছাড় দিতে হয়।

প্র ০৫HM-এর সবচেয়ে খারাপ ক্ষেত্রে সময় সূচকীয়, আবার System F-এ inference undecidable. তবু বাস্তব ভাষাগুলো কীভাবে এগোয়?

প্রথম ফলটির উৎস nested let-এর শক্তি। let p = fn(x) { return (x, x); } ধরনের একটি function type-এর আকার দ্বিগুণ করে; let-polymorphism একে প্রতিবার নতুন কপিতে চালাতে দেয়, তাই n স্তরের শিকলে type-এর আকার 2n-এর মতো, আর আরও চতুর গঠনে আরও দ্রুত বাড়ে। ১৯৯০ সালে Mairson আর স্বাধীনভাবে Kfoury, Tiuryn ও Urzyczyn দেখান যে ML-typability-র জন্য সূচকীয় সময় এড়ানো যায় না (DEXPTIME-complete). আশ্চর্যের বিষয় হলো, এর আগে প্রায় দশ বছর ML ব্যবহারকারীরা বাস্তবে কখনো এই সমস্যায় পড়েননি; বাস্তব program-এ let-এর গভীরতা আর type-এর আকার ছোট থাকে। McAllester ২০০৩ সালের দিকে দেখান, type-এর আকার আর let-এর গভীরতা সীমিত থাকলে inference প্রায় রৈখিক; হেজসহ বলা যায় এটিই বাস্তব অভিজ্ঞতার তাত্ত্বিক ব্যাখ্যা।

দ্বিতীয় ফলটি বেশি মৌলিক। System F (Girard ১৯৭২, Reynolds ১৯৭৪) যেকোনো জায়গায় ∀ বসাতে দেয়: (∀a. a → a) → Int-এর মতো parameter-ও polymorphic. Wells-এর ফল বলে, কোনো annotation ছাড়া System F-এ একটি term-এর type আছে কি না, তা যাচাইয়ের কোনো algorithm নেই। মাঝামাঝি rank-2-এ inference decidable (Kfoury–Wells), কিন্তু principal type-এর সুবিধা দুর্বল হয়, আর rank-3 থেকে আবার undecidable.

বাস্তব ভাষার কৌশল তাই “যেখানে কঠিন, সেখানে annotation চাও”। GHC-তে RankNTypes চালু করে higher-rank type লিখতে দেয়, কিন্তু সেসব জায়গায় signature বাধ্যতামূলক, আর bidirectional type checking দিয়ে লেখা type ভেতরে ছড়িয়ে দেয় (Peyton Jones ও সহকর্মীদের ২০০৭ সালের কাজ, হেজসহ)। Scala, TypeScript, Kotlin আরও এক ধাপ এগিয়ে local inference নেয়: পুরো program-এর বদলে একটি expression বা statement-এর মধ্যে তথ্য প্রবাহ। এর বিনিময়ে principal type-এর গ্যারান্টি নেই, কিন্তু subtyping, overloading আর union type-এর মতো সুবিধা রাখা যায়।

এখানে একটি বড় নকশা-শিক্ষা আছে: type system-এর শক্তি আর inference-এর পূর্ণতা পরস্পরবিরোধী। HM হলো একটি “মধুর বিন্দু”, যেখানে polymorphism যথেষ্ট আর inference পূর্ণ; এর বাইরে প্রতিটি পদক্ষেপে কিছু annotation দিয়ে দাম দিতে হয়।

মূল উপলব্ধি: তাত্ত্বিক সীমা (সূচকীয় খরচ, undecidability) বাস্তব ভাষাকে থামায় না; তারা HM-এর মধুর বিন্দুর কাছাকাছি থাকে, আর তার বাইরে গেলে programmer-এর কাছ থেকে annotation নেয়।

অনুশীলন

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

  1. Type বের করুন (হাতে, তারপর engine-এ): HM-এ নিচের প্রতিটির principal type লিখুন, বা কেন type নেই বলুন। (ক) K = λx.λy. x (খ) flip = λf.λx.λy. f y x (গ) pipe = λf.λg.λx. g (f x) (ঘ) λx.λy. if x then y else 1 (ঙ) λf.λx. f x x (চ) λf. f f 1 (ছ) let k = λx.λy. x in k 1 true

    অংশ ৪-এর engine-এ (CPython 3.14.4-এ একই কোড) চালানো ফল: (ক) a -> b -> a (খ) (a -> b -> c) -> b -> a -> c (গ) (a -> b) -> (b -> c) -> a -> c (ঘ) Bool -> Int -> Int (ঙ) (a -> a -> b) -> a -> b (চ) error: occurs check: t1 occurs in t1 -> t2 (ছ) Int. হাতের পথ: (ঘ)-এ শর্ত থেকে x ≐ Bool, দুই শাখা থেকে y ≐ Int. (ঙ)-এ f দুবার x পায়, তাই f : a → a → b. (চ)-এ f-কে f দিয়ে ডাকা: প্রস্তাব ৩৫.৩-এর মতো। (গ) আর compose-এর পার্থক্য লক্ষ করুন: pipe-এ f আগে চলে, তাই (a → b) → (b → c); AI প্রায়ই এ দুটি গুলিয়ে ফেলে। (ছ)-এ k generalise হয়েছে, তাই 1 আর true দুই আলাদা variable-এ বসে, আর ফল প্রথম argument-এর type.

  2. ভুল খুঁজুন: একজন সহকর্মী অংশ ৩-এর unify-কে “দ্রুত” করতে occurs-কে বদলে লিখলেন def occurs(v, t, S): return False. তাঁর যুক্তি: “বাস্তব program-এ t ≐ (…t…) আসেই না, Prolog-ও তো বাদ দেয়।” unify("t1", fn("t1", "t2"), {}, []) চালালে কী হবে? Type inference-এ এই পরিবর্তন কেন ভুল?

    সত্যিকারের run (CPython 3.14.4): unify সফল হয়ে ফেরত দেয় S = {'t1': ('->', 't1', 't2')}, অর্থাৎ t1 ↦ (t1) → t2, একটি চক্রাকার binding. তারপর apply("t1", S) ডাকলেই RecursionError: maximum recursion depth exceeded, কারণ t1-কে বদলাতে গেলে আবার t1 আসে, শেষ হয় না। দুটি ভুল একসাথে। এক, soundness: λx. x x-এর মতো expression, যাদের কোনো সসীম type নেই (প্রস্তাব ৩৫.৩), এখন checker পার হয়ে যায়; অথচ type-এর অর্থ “সসীম type-এর গাছ”। দুই, engine নিজেই ভাঙে: পরে যে function S চাপায় বা type ছাপে, সে অসীম loop বা recursion-এ পড়ে। Prolog-এর তুলনাটি ভুল জায়গায়: Prolog চক্রাকার term-কে কিছু ক্ষেত্রে বৈধ মান হিসেবে মেনে নেয় (পর্ব ১০), কিন্তু HM-এর type system-এ চক্রাকার type নেই। (কিছু ভাষা, যেমন OCaml-এর -rectypes option, ইচ্ছা করে recursive type অনুমতি দেয়, তবে তা আলাদা, সচেতন নকশা।) Occurs check-এর খরচ কমানোর সঠিক পথ union-find আর level-ভিত্তিক কৌশল, বাদ দেওয়া নয়।

  3. নকশা ও বাস্তবায়ন — if আর ==: অংশ ৭-এর Haat HM block-এ দুটি জিনিস যোগ করুন। (ক) If statement: শর্ত Bool, দুই শাখা একই return type-এ। (খ) ==: দুই operand-এর type এক হতে হবে, আর সেই type Int, Bool বা Str (Haat-এর নকশা-সিদ্ধান্ত ১১)। HM-এর unify শুধু “এক হতে হবে” বলতে পারে, “এই তিনটির একটি” বলতে পারে না; কীভাবে সামলাবেন? চারটি function-এ চালান: fn same(a, b) { return a == b; }, fn free(t) { if t == 0 { return true; } else { return false; } }, fn same_fn(g) { return g == fn(x) { return x + 1; }; }, fn fee(p, big) { if big { return p / 100; } return 50; }.
    # Haat-এর বর্ধিত রূপ (নকশার খসড়া), অংশ ৭-এর block-এর পাশে
    EQ_OK = ("Int", "Bool", "Str")
    pending = []                    # (অবস্থান, operand-এর type): শেষে যাচাই
    # expr()-এ নতুন শাখা:
        if e[0] == "Eq":            # ("Eq", pos, l, r)
            tl, S = expr(env, e[2], S); tr, S = expr(env, e[3], S)
            S = unify(tl, tr, S, []); pending.append((e[1], tl)); return BOOL, S
    # block()-এ নতুন শাখা:
            if s[0] == "If":        # ("If", cond, then_stmts, else_stmts)
                t, S = expr(env, s[1], S); S = unify(t, BOOL, S, [])
                for b in s[2:]: S = block(env, b, ret, S, indent)
    # function শেষে:
    def check_eq(S):
        for pos, t in pending:
            t = apply(t, S)
            if isvar(t): print(f"{pos}: error: cannot decide the type of '==' operands (ambiguous)")
            elif t not in EQ_OK: print(f"{pos}: error: operator '==' cannot compare values of type {hs(t)}")

    মূল কৌশল: unify দিয়ে শুধু “দুই পাশ এক” নিশ্চিত করা, আর “Int/Bool/Str-এর একটি” শর্তটি একটি অপেক্ষমাণ constraint হিসেবে রেখে পুরো function-এর inference শেষে যাচাই, কারণ মাঝপথে type এখনো variable থাকতে পারে যা পরে ঠিক হয়। লেখকের CPython 3.14.4-এ চালানো সত্যিকারের ফল (অবস্থান ==-এর বাম operand-এর শুরু, reference-এর ধাঁচে):

    same: (a, a) -> Bool
    1:24: error: cannot decide the type of '==' operands (ambiguous)
    free: (Int) -> Bool
    same_fn: ((Int) -> Int) -> Bool
    1:24: error: operator '==' cannot compare values of type (Int) -> Int
    fee: (Int, Bool) -> Int

    same-এর type ∀a. (a, a) → Bool হতো, কিন্তু a-তে function type বসলে == অবৈধ; তাই এখানে অস্পষ্টতা error. বিকল্প নকশা: a-কে “তুলনাযোগ্য” শর্তসহ generalise করা, ∀a. Eq a ⇒ (a, a) → Bool, যা Haskell-এর type class-এর পথ (ভাবনার প্রশ্ন ০৪)। same_fn-এর বার্তা reference-এর বার্তার সঙ্গে হুবহু মেলে: reference-এ fn f(g: (Int) -> Int) -> Bool { return g == g; } check করলে আসে 2:12: error: operator '==' cannot compare values of type (Int) -> Int. fee-এ if big থেকে big : Bool, আর p / 100 থেকে p : Int.

  4. আউটপুট অনুমান করুন — TypeScript 5.9: tsc --strict --declaration নিচের প্রতিটি export-এর জন্য .d.ts-এ কোন type লিখবে, আর কোথাও error দেবে কি? (১) export const totals = [520, 1040].map(p => discount(p)); যেখানে discount(p: number) একটি number ফেরত দেয় (২) export const mixed = [discount(2000), id("bkash")]; যেখানে id = <T,>(x: T) => x (৩) export let count = 0; (৪) export function compose(f, g) { return (x) => f(g(x)); }

    সত্যিকারের run (TypeScript 5.9.2, অংশ ৮-এর পূর্ণ আউটপুট): (১) number[]; p-এর type প্রসঙ্গ থেকে (contextual typing). (২) (string | number)[]; HM হলে clash, TypeScript union বানায়। (৩) number; লক্ষ করুন let বলে type “widen” হয়ে number, literal type 0 নয়; export const count = 0; হলে একই run-এ .d.ts-এ আসে export declare const count = 0;, অর্থাৎ type literal 0 (TypeScript-এর literal widening). (৪) তিনটি error TS7006 (Parameter 'f' implicitly has an 'any' type., একইভাবে g আর x), আর .d.ts-এ compose(f: any, g: any): (x: any) => any. শিক্ষা: TypeScript-এর inference local, ব্যবহার থেকে parameter-এর type পেছনে যায় না; HM হলে উত্তর হতো (a → b) → (c → a) → c → b.

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

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

ক্রমType লেখা নেই এমন একটি let f = fn(x) { … };-এর type বের করতে HM যে কাজগুলো করে, সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. প্রতিটি অজানা জায়গায় (parameter, call-এর ফল) নতুন type variable বসানো
  2. AST ঘুরে প্রতিটি call আর operator থেকে constraint তৈরি করা
  3. Unification দিয়ে constraint সমাধান, occurs check-সহ
  4. পাওয়া substitution চাপিয়ে type-এর শেষ রূপ বের করা
  5. Γ-তে মুক্ত নয় এমন variable ∀ দিয়ে generalise করে f-কে Γ-তে রাখা

Hindley–Milner-এ λf.λg.λx. f (g x) (compose)-এর principal type কোনটি?

  • (a → b) → (b → c) → a → c
  • (a → b) → (c → a) → c → b
  • (Int → Int) → (Int → Int) → Int → Int
  • (a → a) → (a → a) → a → a

Type-এর ওপর unification-এ constraint t1 ≐ (t1) → Int এলে কী হয়?

  • t1 ↦ (t1) → Int বসিয়ে এগোনো হয়
  • Clash: Int আর function মেলে না
  • Occurs check-এ ব্যর্থ, type error
  • Delete: সমীকরণ বাদ দেওয়া হয়

HM-এ কোনটি type পায়? (A) let i = λx. x in if i true then i 1 else 0 (B) (λi. if i true then i 1 else 0)(λx. x)

  • শুধু A (type Int)
  • শুধু B
  • দুটিই
  • কোনোটিই না

(t1) → Int ≐ (Bool) → t2-এর most general unifier কোনটি?

  • [t1 ↦ Int, t2 ↦ Bool]
  • [t1 ↦ Bool]
  • [t1 ↦ t3, t2 ↦ t3]
  • [t1 ↦ Bool, t2 ↦ Int]

TypeScript 5.9-এ --strict দিয়ে function compose(f, g) { return (x) => f(g(x)); } compile করলে কী হয়?

  • f আর g-এর generic type infer হয়, কোনো error নেই
  • Parameter-গুলো implicitly any, তাই error TS7006
  • Syntax error: parameter-এ type বাধ্যতামূলক
  • শুধু return type-এ error

ML-এ value restriction কেন লাগে?

  • Inference-কে দ্রুত করতে
  • Function-কে polymorphic হতে না দিতে
  • পরিবর্তনযোগ্য ঘর generalise হয়ে soundness ভাঙা ঠেকাতে
  • Occurs check-এর বদলে

শব্দকোষ

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

মনে রাখুন

  1. Inference = constraint তৈরি + সমাধান: অজানায় type variable, প্রতিটি call থেকে τf ≐ (τ1, …) → r.
  2. Unification (delete, decompose, swap, bind, occurs check) MGU দেয়; t ≐ (…t…) ব্যর্থ, তাই λx. x x-এর type নেই।
  3. Algorithm W sound আর complete: উত্তরটি principal type, যেমন compose : (a → b) → (c → a) → c → b.
  4. Let-polymorphism: let generalise করে (Γ-তে মুক্ত variable বাদে), প্রতি ব্যবহারে নতুন instance; λ-parameter নয়; পরিবর্তনযোগ্য ঘরে value restriction.
  5. সীমা: HM decidable (worst case DEXPTIME); rank-3+ আর System F undecidable; subtyping আর overloading-এ ভাষাগুলো local inference আর annotation নেয় (TypeScript-এ parameter any → TS7006).

পরের পর্বে: পর্ব ৩৬ (Polymorphism — parametric, ad hoc আর subtype). এই পর্বের ∀ হলো parametric polymorphism; পরের পর্বে overloading, type class আর subtyping-এর formal নিয়ম, আর function type কেন argument-এ contravariant.

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

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