এই পর্বে যা শিখবেন
- Free variable, capture এড়ানো substitution, α আর β নিয়ম নিজের হাতে লেখা আর চালানো একটি ছোট interpreter দিয়ে
- de Bruijn index দিয়ে নাম ছাড়া term লেখা, আর α-সমতাকে সাধারণ সমতায় নামিয়ে আনা
- Simply typed lambda calculus-এর typing আর evaluation rule, পর্ব ৩৪ আর ৩৮-এর একই ভঙ্গিতে, আর একটি type checker যা Ω বাতিল করে
- Strong normalization কী বলে, fix কেন তা ভাঙে, আর System F কোথায় এর ওপরে বসে
- Curry–Howard correspondence দিয়ে type-কে প্রস্তাব আর program-কে প্রমাণ হিসেবে পড়া, আর compiler-এর IR (CPS, ANF) হিসেবে lambda calculus চেনা
১ · তিনটি গঠনের ভাষা — কেন প্রোগ্রামিং ভাষার গবেষকেরা lambda calculus দিয়ে শুরু করেন
রান্নার একটি রেসিপি ভাবুন: “যেকোনো একটি সবজি নিন, কেটে তেলে ভাজুন, লবণ দিন।” এখানে “সবজি” একটি ফাঁকা ঘর। আলু দিলে আলুভাজি, বেগুন দিলে বেগুনভাজি। রেসিপি লেখা হলো একটি function বানানো; আলু দিয়ে রান্না করা হলো function ডাকা; আর রান্নার সময় রেসিপির প্রতিটি “সবজি” শব্দের জায়গায় “আলু” পড়া হলো substitution. Lambda calculus ঠিক এই তিনটি জিনিস রাখে, আর কিছু নয়।
Lambda calculus Alonzo Church ১৯৩০-এর দশকের শুরুতে তৈরি করেন। গণনার মডেল হিসেবে এর শক্তি, অর্থাৎ শুধু function দিয়ে সংখ্যা (Church numeral), সত্য-মিথ্যা, if আর recursion (Y combinator) বানানো, আর Turing machine-এর সমান ক্ষমতা, Theory of Computation কোর্সের পর্ব ৪৯-এ (গণনার মডেল) বিস্তারিত দেখানো হয়েছে; এখানে তা আর করা হবে না। এই পর্বের চোখ প্রোগ্রামিং ভাষার নকশাকারীর: lambda calculus-কে একটি ছোট core ভাষা হিসেবে নেওয়া, তাতে সংখ্যা, type, recursion যোগ করা, আর দেখা কোন যোগে কোন গুণ পাওয়া যায় বা হারায়।
Untyped lambda calculus-এর পুরো ব্যাকরণ এক লাইনের:
t ::= x (variable, নাম)
| λx. t (abstraction: x নিয়ে t ফেরত দেওয়া function)
| t t (application: function ডাকা)
দুটি লেখার নিয়ম মনে রাখুন। Application বাঁ দিকে জোড়া লাগে: f a b মানে (f a) b. আর λ-এর দেহ যতদূর সম্ভব ডানে যায়: λx. x + 1 মানে λx. (x + 1). এই পর্বে সুবিধার জন্য সংখ্যা আর + - * == সরাসরি রাখা হলো; একে বলে applied lambda calculus. Haat-এর সঙ্গে মিল এক নজরে:
| Haat | Lambda calculus | মন্তব্য |
|---|---|---|
fn(x: Int) -> Int { return x + 1; } | λx:Int. x + 1 | নামহীন function; typed রূপে parameter-এর type লেখা থাকে |
f(a) | f a | বন্ধনী ছাড়া, পাশাপাশি লিখলেই call |
f(a)(b) | f a b | একাধিক argument মানে currying (পর্ব ০৯) |
(Int) -> Int | Int → Int | function type |
top-level fn fact(…)-এর recursion | fix (λf. …) | অংশ ৫-এ |
এই মিল শুধু কাগজে নয়। নিচের Haat program-টি একটি function ফেরত দেয়, যা পরে ডাকা হয়; reference implementation-এ দুই back end-এই সত্যিকারের run (CPython 3.14.4):
// curry.haat — বাজারঘর: ডেলিভারি চার্জ যোগের curried function
fn add_d(d: Int) -> (Int) -> Int {
return fn(total: Int) -> Int { return total + d; };
}
let dhaka = add_d(60);
print(dhaka(936));
print(add_d(0)(1040));
$ python -B haat.py run curry.haat (vm দিলেও একই)
996
1040
Lambda calculus-এ একই জিনিস λd:Int. λtotal:Int. total + d. dhaka হলো λtotal. total + 60, অর্থাৎ d-এর জায়গায় 60 বসানো একটি function; Haat-এর ভেতরে এটি একটি closure (পর্ব ১৭), যার environment-এ d = 60 ধরা আছে। Substitution আর closure একই অর্থের দুই বাস্তবায়ন: একটি কাগজে নাম বদলায়, অন্যটি যন্ত্রে নাম-থেকে-মানের তালিকা রাখে।
ইতিহাস। Church ১৯৩২–৩৬ সালে untyped lambda calculus গড়েন, আর ১৯৪০ সালে “A Formulation of the Simple Theory of Types” প্রবন্ধে তার typed রূপ দেন। প্রোগ্রামিং ভাষার সঙ্গে সেতুটি বাঁধেন Peter Landin: ১৯৬৪ সালে SECD যন্ত্র দিয়ে expression-কে যান্ত্রিকভাবে চালানো, ১৯৬৫ সালে ALGOL 60-কে lambda notation-এ অনুবাদ, আর ১৯৬৬ সালে “The Next 700 Programming Languages” প্রবন্ধে ISWIM নামের একটি কাল্পনিক ভাষা, যা পরে ML আর Haskell-এর মতো ভাষার পূর্বসূরি হিসেবে গণ্য হয়। Landin-এর মূল কথা ছিল: অনেক ভাষার মিল আছে একটি lambda-core-এ, পার্থক্য শুধু তার ওপরের “চিনি” (syntactic sugar)-তে।
নিচের মানচিত্রে এই পর্বের পথ। প্রতিটি তির একটি যোগ, আর পাশে লেখা সেই যোগে কী পাওয়া বা হারানো গেল।
ছবি ৪৩.১ — lambda calculus পরিবারের মানচিত্র
ওপর থেকে নিচে: type যোগ, তারপর দুই দিকে fix (recursion) আর ∀α (generic); শেষে compiler-এর IR হিসেবে ব্যবহার
ছবির প্রতিটি বাক্স এই পর্বের একটি অংশ: অংশ ২–৩ ওপরের বাক্স (substitution আর নাম), অংশ ৪ দ্বিতীয় বাক্স, অংশ ৫ লাল বাক্স, অংশ ৬ দ্বিতীয় বাক্সের “যুক্তি” লাইন, অংশ ৭ সবুজ বাক্স, অংশ ৮ সবার নিচের বাক্স।
২ · Free variable, substitution আর β — নাম “ধরা পড়া” এড়ানো
λx. t-এ x হলো bound variable: তার অর্থ এই λ-ই ঠিক করে। যে নাম কোনো ঘিরে-থাকা λ দিয়ে বাঁধা নয়, সেটি free variable. λtotal. total + d-এ total bound, d free. পর্ব ১৪ আর ১৭-এর ভাষায়, free variable ঠিক সেই নামগুলো, যা closure-কে বাইরে থেকে ধরে রাখতে হয়। গাণিতিক সংজ্ঞা:
FV(x) = {x}
FV(λx. t) = FV(t) − {x}
FV(t₁ t₂) = FV(t₁) ∪ FV(t₂)
হিসাবের একমাত্র আসল ধাপ β-reduction: (λx. t) v-কে [x ↦ v] t দিয়ে বদলানো, অর্থাৎ দেহ t-এর প্রতিটি free x-এর জায়গায় v বসানো (লেখার ধাঁচ পর্ব ৩৮-এর E-CallFn-এর মতোই)। (λx. t) v আকারের অংশকে বলে redex. পুরো কঠিনতা লুকিয়ে আছে “বসানো” কথাটিতে। সংজ্ঞা, case ধরে:
[x ↦ s] x = s
[x ↦ s] y = y (y ≠ x)
[x ↦ s] (t₁ t₂) = ([x ↦ s] t₁) ([x ↦ s] t₂)
[x ↦ s] (λx. t) = λx. t (x এখানে নতুন করে বাঁধা; ভেতরে যাওয়া নয়)
[x ↦ s] (λy. t) = λy. [x ↦ s] t (y ≠ x আর y ∉ FV(s))
অন্যথায় (y ∈ FV(s)): আগে y-কে নতুন নাম z দিন, λz. [y ↦ z] t, তারপর ওপরের নিয়ম
শেষ লাইনটিই capture-avoiding substitution-এর প্রাণ। কেন দরকার, বাজারঘরের একটি উদাহরণে দেখুন। λtotal. total + d হলো “অর্ডারের মোটে ডেলিভারি চার্জ d যোগ করা”। এখন ধরুন d-এর জায়গায় বসাতে হবে বাইরের একটি নাম total, যার মান, বলা যাক, ১০৪০ (আগের একটি অর্ডারের মোট)। সরলভাবে বসালে পাওয়া যায় λtotal. total + total: বাইরের total ভেতরের λ-এর হাতে “ধরা পড়ল”, আর function-টি এখন যেকোনো অর্ডারের মোটকে দ্বিগুণ করে! সঠিক পথ হলো আগে ভেতরের নামটি বদলানো, যাকে বলে α-renaming: λtotal1. total1 + d, তারপর বসানো।
দুটি term-এর পার্থক্য শুধু bound variable-এর নামে হলে তারা α-equivalent: λa. a ≡α λx. x. Lambda calculus-এ এমন term-কে একই ধরা হয়; তাই α-renaming অর্থ বদলায় না, শুধু ধরা পড়া ঠেকায়। নিচের Python block হুবহু ওপরের সংজ্ঞা; প্রতিটি if একটি লাইন।
# λ-term: ("var",x) ("lam",x,τ বা None,দেহ) ("app",f,a) ("num",n) ("op","+",a,b)
def fv(t): # free variable-এর set
if t[0] == "var": return {t[1]}
if t[0] == "lam": return fv(t[3]) - {t[1]}
if t[0] in ("num", "bool"): return set()
return set().union(*(fv(u) for u in t[1:] if type(u) is tuple))
def fresh(x, avoid): # x1, x2, … যেটি এখনো ব্যবহৃত নয়
return next(f"{x}{i}" for i in range(1, 10**6) if f"{x}{i}" not in avoid)
def subst(t, x, s): # [x ↦ s] t, capture এড়িয়ে
k = t[0]
if k == "var": return s if t[1] == x else t
if k in ("num", "bool"): return t
if k == "lam":
y, ty, body = t[1], t[2], t[3]
if y == x or x not in fv(body): return t # ভেতরে x মুক্ত নেই
if y in fv(s): # ধরা পড়ার ভয়: α-renaming
z = fresh(y, fv(s) | fv(body))
print(f" α: {y} → {z}")
body, y = subst(body, y, ("var", z)), z
return ("lam", y, ty, subst(body, x, s))
return (k, *(subst(u, x, s) if type(u) is tuple else u for u in t[1:]))
def show(t):
k, p = t[0], lambda u: show(u) if u[0] in ("var", "num", "bool") else f"({show(u)})"
if k in ("var", "num"): return str(t[1])
if k == "bool": return str(t[1]).lower()
if k == "lam": return f"λ{t[1]}{':' + tshow(t[2], 1) if t[2] else ''}. {show(t[3])}"
if k == "app": return f"{show(t[1]) if t[1][0] in ('var', 'app') else p(t[1])} {p(t[2])}"
if k == "op": return f"{p(t[2])} {t[1]} {p(t[3])}"
return f"if {p(t[1])} then {p(t[2])} else {p(t[3])}" if k == "if" else f"fix {p(t[1])}"
def tshow(ty, p=0): return ty if type(ty) is str else ("({})" if p else "{}").format(f"{tshow(ty[0], 1)} → {tshow(ty[1])}")
V, L, A = (lambda x: ("var", x)), (lambda x, b, ty=None: ("lam", x, ty, b)), (lambda f, a: ("app", f, a))
t = L("total", ("op", "+", V("total"), V("d"))) # λtotal. total + d
print(show(t), " FV =", sorted(fv(t)))
print("[d ↦ 60] :", show(subst(t, "d", ("num", 60))))
print("[d ↦ total]:", show(subst(t, "d", V("total"))))আসল আউটপুট (ব্রাউজারের Python):
λtotal. total + d FV = ['d']
[d ↦ 60] : λtotal. total + 60
α: total → total1
[d ↦ total]: λtotal1. total1 + total
প্রথম লাইনে free variable শুধু d. দ্বিতীয় লাইনে 60 বসানো সহজ: 60-এর ভেতরে কোনো নাম নেই, তাই ধরা পড়ার ভয় নেই, ফল λtotal. total + 60 (ঢাকার ভেতরে ৬০ টাকা চার্জ)। তৃতীয় লাইনে বসাতে হবে নাম total, আর সেটি ভেতরের λ-এর নামের সঙ্গে মেলে; তাই code প্রথমে α: total → total1 ছাপে, তারপর বসায়। ফল λtotal1. total1 + total: parameter-এর নাম বদলেছে, কিন্তু অর্থ ঠিক আছে, আর বাইরের total free রয়ে গেছে। লেখকের lab-এ সরল (renaming ছাড়া) substitution-এর সঙ্গে তুলনা করা হয়েছে: বাইরের total = 1040 ধরে ফল-function-কে 936-এ ডাকলে সরলটি দেয় 1872 (936 + 936), সঠিকটি 1976 (936 + 1040).
একই substitution এবার ধাপে ধাপে, ওপরের নিয়মের কোন লাইন কখন খাটে তা চিহ্নিত করে:
1[x ↦ s] x = s2[x ↦ s] y = y (y ≠ x)3[x ↦ s] (t₁ t₂) = …4[x ↦ s] (λx. t) = λx. t5[x ↦ s] (λy. t) = λy. [x ↦ s] t যদি y ∉ FV(s)6নইলে আগে y → নতুন z (α)
| কাজ | |
| FV(s) | |
| term |
- লক্ষ্য। বসাতে হবে s =
total, একটি free নাম, যা বাইরের কোনো অর্ডারের মোট বোঝায় (ধরুন ১০৪০)। FV(s) = {total}. যে term-এ বসানো হবে, তা একটি λ, তাই λ-এর নিয়মগুলো দেখতে হবে। - λ-এর case. Binder-এর নাম total, যা d নয়, তাই লাইন ৪ খাটে না। দেহে d free, তাই ভেতরে না ঢুকলে চলবে না। প্রশ্ন একটাই: লাইন ৫ সরাসরি খাটানো যায় কি না।
- বিপদ ধরা। লাইন ৫-এর শর্ত y ∉ FV(s), কিন্তু y = total আর total ∈ FV(s). শর্ত ভাঙলে কী হতো? λtotal. total + total, যেখানে বাইরের total ভেতরের λ-এর হাতে ধরা পড়ে, আর function-টি সব অর্ডার দ্বিগুণ করে।
- α-renaming. লাইন ৬: ভেতরের binder-কে এমন নাম দিন, যা FV(s) বা দেহে নেই। {total, d} এড়িয়ে প্রথম খালি নাম total1. λtotal1. total1 + d, যা আগের term-এর α-equivalent, অর্থ একই।
- দেহে বসানো। এবার লাইন ৫ নিরাপদ। দেহ total1 + d-এর দুই পাশে: total1 অন্য নাম, লাইন ২ অনুযায়ী অপরিবর্তিত; d হুবহু x, লাইন ১ অনুযায়ী total দিয়ে বদল। ফল total1 + total.
- ফল। λtotal1. total1 + total: “যেকোনো অর্ডারের মোটের সঙ্গে আগের অর্ডারের মোট যোগ”। 936-এ ডাকলে 936 + 1040 = 1976, লেখকের lab-এর run-এর সঙ্গে মেলে। ওপরের Python block-ও ঠিক এই ফল ছাপে।
এবার substitution-এর ওপর evaluation. Haat-এর মতো call-by-value, বাঁ থেকে ডানে (reference README-এর সিদ্ধান্ত ১২: আগে callee, তারপর argument), আর λ-এর দেহের ভেতরে কোনো হিসাব নয়। নিয়মের নাম পর্ব ৩৮-এর মতো: E-CallFn আসল β-ধাপ, E-Call1 আর E-Call2 বলে কাজটি কোথায়।
# call-by-value small-step: বাঁ থেকে ডানে, λ-এর ভেতরে নয় (Haat-এর মতো)
OPS = {"+": ("Add", lambda a, b: a + b), "-": ("Sub", lambda a, b: a - b),
"*": ("Mul", lambda a, b: a * b), "==": ("Eq", lambda a, b: a == b)}
def is_val(t): return t[0] in ("lam", "num", "bool")
def step(t): # (নতুন term, নিয়মের নাম) বা None
k = t[0]
if k in ("app", "op"):
pre, a, b = t[:-2], t[-2], t[-1] # pre = ("app",) বা ("op", "+")
tag = "E-Call" if k == "app" else "E-" + OPS[t[1]][0]
if not is_val(a): r = step(a); return r and (pre + (r[0], b), f"{tag}1({r[1]})")
if not is_val(b): r = step(b); return r and (pre + (a, r[0]), f"{tag}2({r[1]})")
if k == "app" and a[0] == "lam": return subst(a[3], a[1], b), "E-CallFn"
if k == "op" and a[0] == b[0] == "num":
v = OPS[t[1]][1](a[1], b[1])
return ("bool" if type(v) is bool else "num", v), tag
if k in ("if", "fix") and not is_val(t[1]): # শর্ত বা fix-এর ভেতর আগে
r = step(t[1]); return r and ((k, r[0], *t[2:]), f"E-{k.title()}({r[1]})")
if k == "if" and t[1][0] == "bool": return (t[2], "E-IfTrue") if t[1][1] else (t[3], "E-IfFalse")
if k == "fix" and t[1][0] == "lam": return subst(t[1][3], t[1][1], t), "E-FixBeta"
return None # value, নয়তো stuck
def run(t, limit=60, trace=True): # ⟶* : কত ধাপে value (বা limit)
for n in range(limit):
if trace: print(f" {n}: {show(t)}")
r = step(t)
if r is None: return t, n
t = r[0]
if trace: print(f" ⟶ {r[1]}")
return t, limit
N, op = (lambda n: ("num", n)), (lambda s, a, b: ("op", s, a, b))
run(A(L("x", op("+", V("x"), N(1))), N(2))) # (λx. x + 1) 2
add_d = L("d", L("total", op("+", V("total"), V("d")))) # λd. λtotal. total + d
v, n = run(A(A(add_d, N(60)), N(936)), trace=False); print("ডেলিভারি যোগ:", show(v), "|", n, "ধাপ")
omega = A(L("x", A(V("x"), V("x"))), L("x", A(V("x"), V("x"))))
v, n = run(omega, limit=1000, trace=False); print("Ω:", n, "ধাপ পরেও", show(v))আসল আউটপুট (ব্রাউজারের Python):
0: (λx. x + 1) 2
⟶ E-CallFn
1: 2 + 1
⟶ E-Add
2: 3
ডেলিভারি যোগ: 996 | 3 ধাপ
Ω: 1000 ধাপ পরেও (λx. x x) (λx. x x)
(λx. x + 1) 2 দুই ধাপে 3: প্রথমে β (E-CallFn), তারপর যোগ। add_d 60 936 তিন ধাপে 996, bazar.haat-এর প্রথম লাইনের সেই সংখ্যা (৯৩৬ টাকার পণ্য আর ৬০ টাকা ডেলিভারি)। শেষ লাইনটি গুরুত্বপূর্ণ: Ω = (λx. x x)(λx. x x) একবার β করলে হুবহু নিজেকেই ফেরত দেয়, তাই ১০০০ ধাপের সীমায় থামানোর পরেও term অপরিবর্তিত। এটি lambda calculus-এর অসীম loop; কোনো β-normal form নেই। কোন redex আগে কমানো হবে (normal order না applicative order), তা নিয়ে আলোচনা পর্ব ১৯-এ; আর Church–Rosser theorem বলে normal form থাকলে তা পথ নির্বিশেষে একটিই।
৩ · নাম ছাড়া variable — de Bruijn index
পাড়ার মুদির দোকানে খাতায় লেখা থাকে না “করিম সাহেবের বাকি”, লেখা থাকে “৩ নম্বর খাতা, ২ নম্বর পাতা”। নাম বদলালেও (করিম সাহেব নতুন নামে পরিচিত হলেন) হিসাব বদলায় না। de Bruijn index-এর ভাবনাও তাই: variable-কে নাম দিয়ে না ডেকে বলা হয় “কত স্তর বাইরের λ-টি আমাকে বেঁধেছে”।
ডাচ গণিতবিদ Nicolaas de Bruijn ১৯৭২ সালে AUTOMATH নামের প্রমাণ-যাচাই প্রকল্পের কাজে এই কৌশল প্রস্তাব করেন (পর্ব ১৪-এ এর এক লাইনের উল্লেখ ছিল)। de Bruijn index-এ প্রতিটি bound variable-এর জায়গায় একটি সংখ্যা বসে: ০ মানে সবচেয়ে কাছের λ, ১ মানে তার বাইরেরটি, এভাবে। λ-এর গায়ের নাম মুছে যায়। (de Bruijn নিজে ১ থেকে গুনতেন; Pierce-এর বইসহ আধুনিক বেশিরভাগ লেখা ০ থেকে গোনে, এখানেও তাই।) উদাহরণ: λa. λb. a হয় λ. λ. 1, কারণ a-কে বেঁধেছে এক স্তর বাইরের λ. ফলটি অসাধারণ: α-equivalent দুটি term-এর de Bruijn রূপ হুবহু এক, তাই α-সমতা যাচাই হয়ে যায় সাধারণ সমতা-যাচাই।
# de Bruijn: নামের বদলে সংখ্যা, "কত স্তর বাইরের λ" (০ থেকে গোনা)
def db(t, ctx=()): # ctx: ভেতরের binder আগে
k = t[0]
if k == "var": return ("idx", ctx.index(t[1])) if t[1] in ctx else t # free থাকলে নামেই
if k == "lam": return ("λ", t[2], db(t[3], (t[1],) + ctx)) # নাম মুছে যায়
if k in ("num", "bool"): return t
return (k, *(db(u, ctx) if type(u) is tuple else u for u in t[1:]))
def dshow(d):
k, p = d[0], lambda u: dshow(u) if u[0] in ("idx", "var", "num") else f"({dshow(u)})"
if k == "idx": return str(d[1])
if k in ("var", "num"): return str(d[1])
if k == "λ": return "λ. " + dshow(d[2])
if k == "app": return f"{dshow(d[1]) if d[1][0] in ('idx', 'var', 'app') else p(d[1])} {p(d[2])}"
return f"{p(d[2])} {d[1]} {p(d[3])}" # op
def alpha_eq(s, t): return db(s) == db(t) # α-সমতা = de Bruijn রূপ হুবহু এক
K = L("a", L("b", V("a")))
terms = [K, L("x", L("y", V("x"))), L("a", L("b", V("b"))),
L("d", L("total", op("+", V("total"), V("d")))),
L("total1", op("+", V("total1"), V("total"))), # ওপরের substitution-এর ফল
L("x", A(V("x"), V("x")))]
for t in terms: print(f"{show(t):26} ⇒ {dshow(db(t))}")
print("K ≡α λx. λy. x ?", alpha_eq(K, terms[1]), "| K ≡α λa. λb. b ?", alpha_eq(K, terms[2]))আসল আউটপুট (ব্রাউজারের Python):
λa. λb. a ⇒ λ. λ. 1
λx. λy. x ⇒ λ. λ. 1
λa. λb. b ⇒ λ. λ. 0
λd. λtotal. total + d ⇒ λ. λ. 0 + 1
λtotal1. total1 + total ⇒ λ. 0 + total
λx. x x ⇒ λ. 0 0
K ≡α λx. λy. x ? True | K ≡α λa. λb. b ? False
প্রথম দুই লাইনের নাম আলাদা, de Bruijn রূপ এক: তারা α-equivalent, আর alpha_eq তাই True. তৃতীয়টি দেখতে প্রায় একই, কিন্তু দ্বিতীয় parameter ফেরত দেয় (০), প্রথমটি নয়; তাই False. পঞ্চম লাইনে আগের অংশের substitution-এর ফল: bound total1 হলো ০, আর free total নামেই রয়ে গেছে। নামে থাকায় সে কখনো কোনো λ-এর ০ বা ১-এর সঙ্গে গুলিয়ে যেতে পারে না; ধরা পড়ার সমস্যাটিই আর নেই।
তাহলে সবাই কেন de Bruijn ব্যবহার করে না? দুটি দাম আছে। এক, মানুষের পক্ষে পড়া কঠিন: λ. λ. 0 + 1 দেখে অর্থ বুঝতে সময় লাগে। দুই, λ-এর ভেতরে term বসালে বসানো term-এর free index-গুলো এক ধাপ “সরাতে” (shift) হয়, আর এই হিসাবের off-by-one ভুল কুখ্যাত। তবু যন্ত্রের ভেতরে কৌশলটি জনপ্রিয়: Lean 4 আর Coq/Rocq-এর kernel-এ bound variable এভাবেই রাখা হয় বলে তাদের source আর documentation থেকে জানা যায়, প্রায়ই free variable-এর জন্য নাম রেখে (“locally nameless” ধাঁচ)। Haat-এর resolver-এর (depth, slot) জোড়াও একই চিন্তার আত্মীয়: নামকে একটি ঠিকানায় বদলে দেওয়া, যাতে পরের ধাপে নামের তুলনা লাগে না (পর্ব ৫১-এ symbol table).
৪ · Simply typed lambda calculus — তিনটি typing rule
Untyped জগতে x x লেখা বৈধ, আর সেখান থেকেই আসে Ω-এর মতো অসীম loop, বা 3 (λx. x)-এর মতো অর্থহীন call (একটি সংখ্যাকে function হিসেবে ডাকা), যা stuck term. Church-এর ১৯৪০ সালের প্রস্তাব: প্রতিটি λ-এর parameter-এ type লেখা থাকবে। এর নাম simply typed lambda calculus, সংক্ষেপে STLC. ব্যাকরণ:
τ ::= Int | Bool | τ → τ (type)
t ::= x | λx:τ. t | t t | n | t + t | true | false | if t then t else t
v ::= λx:τ. t | n | true | false (value)
→ ডানে জোড়া লাগে: Int → Int → Int মানে Int → (Int → Int), অর্থাৎ curried দুই-argument function. Haat-এ এটি (Int) -> (Int) -> Int. Typing judgment পর্ব ৩৪-এর মতোই Γ ⊢ t : τ, যেখানে typing context Γ নাম থেকে type-এর তালিকা। নিয়মগুলো পর্ব ৩৪-এর নামে; Pierce-এর বইয়ে T-Fn-কে T-Abs আর T-Call-কে T-App বলা হয়, অর্থ একই:
পড়ার নিয়ম: দাগের ওপরে premise, নিচে conclusion. T-Fn বলে: “x-কে τ1 ধরে নিয়ে দেহের type τ2 পাওয়া গেলে, পুরো function-এর type τ1 → τ2”. T-Call বলে: “function-এর parameter-type আর argument-এর type হুবহু মিললে ফলের type τ2”. সংখ্যা, যোগ, Bool আর if-এর নিয়ম (T-Int, T-Add, T-Bool, T-IfExpr) পর্ব ৩৮-এর মতোই, শুধু সবখানে Γ যোগ হয়। Evaluation-এর নিয়ম call-by-value:
E-CallFn-এ argument-কে value হতে হয় (call-by-value); তার আগে E-Call1 callee-কে, E-Call2 argument-কে value পর্যন্ত চালায়। ছোট্ট একটি উদাহরণে typing আর evaluation দুটিই, ধাপে ধাপে:
1x:Int ⊢ x : Int T-Var2x:Int ⊢ 1 : Int T-Int3x:Int ⊢ x + 1 : Int T-Add4⊢ λx:Int. x + 1 : Int → Int T-Fn5⊢ (λx:Int. x + 1) 2 : Int T-Call6⟶ 2 + 1 E-CallFn7⟶ 3 E-Add
| Γ | |
| term | |
| type |
- পাতা। Derivation ওপর থেকে নয়, পাতা থেকে গড়ে ওঠে। Γ = x : Int ধরে নিয়ে x-এর type T-Var দিয়ে Int (Γ-তে খুঁজে পাওয়া), আর 1-এর type T-Int দিয়ে Int. দুটিই axiom: দাগের ওপরে কোনো type-দাবি নেই।
- দেহ। T-Add দুই পাশ Int চায়; পাওয়া গেছে। তাই x : Int ⊢ x + 1 : Int. এখনো Γ-তে x আছে, কারণ আমরা λ-এর ভেতরে।
- Function. T-Fn: premise ছিল “x : Int ধরে দেহ Int”, conclusion “λx:Int. x + 1 : Int → Int”. x এখন আর Γ-তে নেই; সে type-এর বাঁ অংশে ঢুকে গেছে। Haat-এ এটি
(Int) -> Int. - Call. T-Call: callee-র type Int → Int, argument 2-এর type Int (T-Int); parameter-type আর argument-type মেলে, তাই পুরো term-এর type Int. পূর্ণ derivation তৈরি; checker মেনে নেয়।
- β-ধাপ। 2 একটি value, তাই E-CallFn: দেহ x + 1-এ x-এর জায়গায় 2, ফল 2 + 1. Checker আবার চালালে type Int, আগের মতোই: পর্ব ৩৮-এর preservation, যার প্রমাণে ঠিক এখানে substitution lemma লাগে।
- শেষ। E-Add দিয়ে 3, একটি value, type Int. মোট ২ ধাপ; অংশ ২-এর Python block-এর প্রথম trace-ও হুবহু এই (সেখানে type না লিখে)। লেখকের lab-এ অংশ ৫-এর checker দিয়ে তিনটি term-এর type যাচাই করা হয়েছে: Int, Int, Int.
STLC type sound: progress আর preservation দুটিই সত্য, আর প্রমাণ পর্ব ৩৮-এর অংশ ৬-এর ছকেই চলে; সেখানে এক-parameter function-সহ ভাষার জন্য substitution lemma প্রমাণ করা হয়েছিল, আর STLC সেই ভাষারই পরিচ্ছন্ন রূপ। Typed জগতে 3 (λx:Int. x) লেখাই যায় না: T-Call চায় callee-র type τ1 → τ2, কিন্তু 3-এর type Int.
এবার Ω. λx:τ. x x-এর type পেতে T-Call চায় x-এর type একটি function type, যার parameter-type আবার x-এর type: τ = τ → σ. কোনো সসীম type নিজের একটি অংশের সমান হতে পারে না (পর্ব ৩৫-এর unification-এ এটিই occurs check). তাই Ω, আর Y combinator (fixed-point combinator, যা ভেতরে x x ব্যবহার করে), STLC-তে লেখাই যায় না। Haat-এও একই কথা; reference checker-এ সত্যিকারের run:
// selfapp.haat
fn self_apply(x: (Int) -> Int) -> Int {
return x(x);
}
$ python -B haat.py check selfapp.haat
2:14: error: type mismatch: expected Int, found (Int) -> Int
৫ · সব term শেষ হয় — strong normalization, আর fix দিয়ে recursion ফেরানো
Ω বাদ পড়ল, এটি কাকতালীয় নয়। STLC-এর সবচেয়ে বিখ্যাত ফল:
⊢ t : τ হলে t থেকে যেকোনো ক্রমে β-reduction চালালে সসীম ধাপে একটি normal form-এ পৌঁছানো যায়; কোনো অসীম reduction-শিকল নেই।
“Strong” শব্দটির অর্থ: শুধু কোনো একটি পথ নয়, প্রতিটি পথ শেষ হয় (কোন redex আগে কমানো হলো, তাতে কিছু আসে যায় না)। এই strong normalization-এর আধুনিক প্রমাণ-কৌশলের জন্য সাধারণত William Tait-এর ১৯৬৭ সালের প্রবন্ধকে কৃতিত্ব দেওয়া হয়। প্রমাণের রূপরেখা: সহজ চেষ্টা হলো term-এর আকারের ওপর induction, এই যুক্তিতে যে β-ধাপে term ছোট হয়। কিন্তু তা মিথ্যা: [x ↦ v] t-এ v যতবার x আছে ততবার কপি হয়, তাই term বড়ও হতে পারে (অনুশীলন ২-এ একটি সংখ্যাসহ উদাহরণ)। Tait-এর কৌশল প্রতিটি type-এর জন্য একটি শক্ত শর্ত সংজ্ঞায়িত করে (“reducible”): Int-এর term reducible যদি সে শেষ হয়; τ1 → τ2-এর term reducible যদি সে শেষ হয় আর প্রতিটি reducible argument-এ ডাকলে ফলও reducible হয়। তারপর type-এর গঠনের ওপর induction-এ দেখানো হয় প্রতিটি well-typed term reducible, আর reducible মানেই শেষ হয়। শর্তটি type-এর আকার ধরে ছোট হয়, term-এর আকার ধরে নয়; এখানেই কৌশল।
একটি ফল চোখে পড়ার মতো: প্রতিটি program থামলে ভাষাটি Turing-সমতুল্য হতে পারে না (halting problem অন্যথায় সমাধানযোগ্য হতো; Theory of Computation পর্ব ৫৩)। STLC নিরাপদ, কিন্তু সীমিত। Theorem-টি পরীক্ষা করতে লেখকের lab-এ (CPython 3.14.4) seed 43 দিয়ে ২,০০০টি এলোমেলো well-typed STLC term বানিয়ে (fix ছাড়া, Int আর Bool ফলের, higher-order function-সহ) নিচের evaluator দিয়ে চালানো হয়েছে: মোট ৩৪,৩০৫ ধাপ, সবচেয়ে লম্বাটি ৬৫ ধাপ, শেষ না-হওয়া term ০টি। এটি প্রমাণ নয়, একটি অভিজ্ঞতার পরীক্ষা মাত্র; প্রমাণ ওপরের রূপরেখা।
বাস্তব ভাষার recursion লাগে। সমাধান হলো একটি নতুন গঠন, fix, যার নিয়ম:
E-FixBeta-র অর্থ: দেহে f-এর জায়গায় পুরো fix-term-টিই বসানো, অর্থাৎ “নিজেকে আবার ডাকার উপায়” দেহের হাতে তুলে দেওয়া। Y combinator untyped জগতে যা কৌশলে করে, fix তা একটি নিয়ম হিসেবে করে, আর T-Fix তাকে type দেয়। STLC + fix (সঙ্গে সংখ্যা আর Bool) মোটামুটি Gordon Plotkin-এর ১৯৭৭ সালের PCF ভাষা, যার ভিত্তি Dana Scott-এর ১৯৬৯ সালের দিকের LCF কাজ; PCF আজও ভাষাতত্ত্বের পাঠ্যে “সবচেয়ে ছোট বাস্তবসম্মত functional ভাষা” হিসেবে পড়ানো হয়। নিচের block একটি STLC checker (প্রতিটি শাখা একটি নিয়ম), আর অংশ ২-এর evaluator দিয়ে fix চালায়:
# STLC checker: τ ::= "Int" | "Bool" | (τ1, τ2) যার মানে τ1 → τ2
def typeof(t, G={}): # Γ ⊢ t : τ খোঁজা; না পেলে TypeError
k = t[0]
if k == "num": return "Int" # T-Int
if k == "bool": return "Bool" # T-Bool
if k == "var": # T-Var
if t[1] in G: return G[t[1]]
raise TypeError(f"undefined variable '{t[1]}'")
if k == "lam": return (t[2], typeof(t[3], {**G, t[1]: t[2]})) # T-Fn
if k == "app": # T-Call
f, a = typeof(t[1], G), typeof(t[2], G)
if type(f) is tuple and f[0] == a: return f[1]
raise TypeError(f"cannot call {show(t[1])} : {tshow(f)} with {tshow(a)}")
if k == "op": # T-Add, T-Eq …
if typeof(t[2], G) == typeof(t[3], G) == "Int": return "Bool" if t[1] == "==" else "Int"
raise TypeError(f"operator '{t[1]}' needs Int, Int")
if k == "if": # T-IfExpr
c, a, b = (typeof(u, G) for u in t[1:])
if c == "Bool" and a == b: return a
raise TypeError("if needs Bool and two branches of the same type")
if k == "fix": # T-Fix
f = typeof(t[1], G)
if type(f) is tuple and f[0] == f[1]: return f[0]
raise TypeError(f"fix needs τ → τ, found {tshow(f)}")
I = ("Int", "Int")
typed = L("d", L("total", op("+", V("total"), V("d")), "Int"), "Int")
print(show(typed), ":", tshow(typeof(typed)))
for tau in ["Int", I, (I, "Int")]: # Ω-এর x x
try: typeof(L("x", A(V("x"), V("x")), tau))
except TypeError as e: print("x :", tshow(tau).ljust(20), "→", e)
fact = ("fix", L("f", L("n", ("if", op("==", V("n"), N(0)), N(1),
op("*", V("n"), A(V("f"), op("-", V("n"), N(1))))), "Int"), I))
print("fact :", tshow(typeof(fact)))
v, n = run(A(fact, N(5)), limit=500, trace=False); print("fact 5 =", show(v), "|", n, "ধাপ")
v, n = run(("fix", L("x", V("x"), "Int")), limit=1000, trace=False); print("fix (λx:Int. x):", n, "ধাপ পরেও", show(v))আসল আউটপুট (ব্রাউজারের Python):
λd:Int. λtotal:Int. total + d : Int → Int → Int
x : Int → cannot call x : Int with Int
x : Int → Int → cannot call x : Int → Int with Int → Int
x : (Int → Int) → Int → cannot call x : (Int → Int) → Int with (Int → Int) → Int
fact : Int → Int
fact 5 = 120 | 34 ধাপ
fix (λx:Int. x): 1000 ধাপ পরেও fix (λx:Int. x)
প্রথম লাইনে অংশ ১-এর curried function-এর type, Haat-এর (Int) -> (Int) -> Int. পরের তিন লাইনে Ω-এর অর্ধেক λx:τ. x x তিনটি ভিন্ন τ দিয়ে চেষ্টা: প্রতিবার T-Call ব্যর্থ, কারণ x-এর type আর x-কে যে argument-type চায়, তা কখনো মেলে না (τ বনাম τ-এর parameter অংশ)। তিনটি চেষ্টা প্রমাণ নয়; প্রমাণ ওপরের occurs check-এর যুক্তি। এরপর fix: fact-এর type Int → Int, আর fact 5 ৩৪ ধাপে 120, Haat-এর fact.haat-এর সত্যিকারের run-এর (print(fact(5)); ছাপে 120, run আর vm দুটিতেই) সঙ্গে মেলে। শেষ লাইনটি দাম: fix (λx:Int. x)-এর type Int, checker মেনে নেয়, অথচ E-FixBeta একে হুবহু নিজের কাছে ফেরত পাঠায়; ১০০০ ধাপেও শেষ নয়। fix যোগ করতেই strong normalization ভাঙল, soundness নয়: অসীম চলা stuck অবস্থা নয়।
Haat-এ top-level fn fact নিজের নাম দেহের ভেতর দেখতে পায় (README সিদ্ধান্ত ১৭: top-level function hoist হয়, nested function নিজের দেহে নিজেকে দেখে)। এটিই fix: compiler নামটিকে নিজের closure-এর সঙ্গে বেঁধে দেয়। Agda বা Coq/Rocq-এর মতো ভাষা উল্টো পথে হাঁটে: সাধারণ fix নিষেধ, recursion শুধু ছোট হতে-থাকা argument-এ (structural recursion), যাতে প্রতিটি function থামে। কেন এত কড়াকড়ি, তার উত্তর পরের অংশে।
৬ · Curry–Howard — type মানে প্রস্তাব, program মানে প্রমাণ
বাজারঘরের রান্নাঘরের দেয়ালে লেখা: “চাল থাকলে আর ডাল থাকলে খিচুড়ি হবে।” এটি একটি দাবি। এর প্রমাণ কী? একটি রেসিপি, যা হাতে চাল আর ডাল পেলে খিচুড়ি বানিয়ে দেয়। রেসিপি থাকা মানেই দাবিটি সত্য প্রমাণিত। Type-এর ভাষায়: চাল → ডাল → খিচুড়ি type-এর একটি function লেখা মানে “চাল হলে, ডাল হলে খিচুড়ি” দাবির প্রমাণ দেওয়া।
Haskell Curry ১৯৩০-এর দশকে combinatory logic-এর type আর যুক্তির axiom-এর মিল লক্ষ করেন (১৯৫৮ সালে Feys-এর সঙ্গে লেখা বইয়ে তা স্পষ্ট); William Howard ১৯৬৯ সালে একটি পাণ্ডুলিপিতে মিলটিকে natural deduction আর typed lambda calculus-এর পূর্ণ সম্পর্ক হিসেবে লেখেন, যা ১৯৮০ সালে Curry-কে উৎসর্গ করা একটি সংকলনে প্রকাশিত হয়। এই Curry–Howard correspondence-কে “propositions as types” নামেও ডাকা হয়। মিলটি এক টেবিলে (propositional logic-এর ভিত্তি চাইলে Discrete Mathematics-এর পর্ব ০২ আর পর্ব ০৬ দেখুন):
| যুক্তি (logic) | Type আর program |
|---|---|
| প্রস্তাব A | type A |
| A-এর একটি প্রমাণ | A type-এর একটি বন্ধ term (program) |
| অনুমান “ধরি A সত্য” | Γ-তে একটি variable a : A (T-Var) |
| A ⇒ B (implication), প্রমাণের নিয়ম →-introduction | A → B, λa:A. … (T-Fn) |
| Modus ponens (→-elimination) | function call (T-Call) |
| A ∧ B, A ∨ B | জোড়া (tuple/record), sum type (পর্ব ২৪-এর algebraic data type) |
| ⊥ (মিথ্যা) | যে type-এর কোনো মান নেই |
| প্রমাণ থেকে ঘুরপথ সরানো (proof normalization) | β-reduction |
শেষ সারিটি সুন্দর: প্রমাণে কেউ আগে একটি সাধারণ lemma প্রমাণ করে (λ), তারপর সাথে সাথে একটি নির্দিষ্ট ক্ষেত্রে খাটায় (call); এই ঘুরপথ সরালে সরাসরি প্রমাণ পাওয়া যায়, আর তা হুবহু একটি β-ধাপ। অর্থাৎ program চালানো আর প্রমাণ সরল করা একই কাজ। এবার একটি প্রস্তাবের প্রমাণ খোঁজা, ধাপে ধাপে:
1লক্ষ্য: A → B → A2ধরি a : A (→I, T-Fn)3ধরি b : B (→I, T-Fn)4A আছে: a (অনুমান, T-Var)5λa:A. λb:B. a6A → B: লক্ষ্য B, হাতে শুধু A
| Γ (অনুমান) | |
| লক্ষ্য | |
| program |
- লক্ষ্য। প্রস্তাব A → B → A, অর্থাৎ A ⇒ (B ⇒ A): “A সত্য হলে, তারপর B সত্য হলেও, A সত্য”। Program-এর ভাষায়: এই type-এর একটি বন্ধ term চাই। এখনো হাতে কিছু নেই, Γ ফাঁকা।
- প্রথম অনুমান। লক্ষ্য একটি implication, তাই →-introduction: A-কে অনুমান হিসেবে নিন আর তার নাম দিন a. Program-এ এটি T-Fn: λa:A. ? লেখা, যেখানে ? এর type হতে হবে B → A.
- দ্বিতীয় অনুমান। লক্ষ্য আবার implication: B অনুমান, নাম b. Program এখন λa:A. λb:B. ?, আর ?-এর type হতে হবে A. Γ = a : A, b : B.
- অনুমান ব্যবহার। A তো Γ-তেই আছে, নাম a. যুক্তিতে “অনুমান থেকে”, program-এ T-Var. ? = a. B-এর অনুমানটি ব্যবহারই হলো না; যুক্তিতে এটি বৈধ।
- সম্পূর্ণ প্রমাণ। λa:A. λb:B. a. অংশ ৫-এর checker-এ যাচাই (A আর B-কে base type ধরে): type A → B → A. এই function-টির পরিচিত নাম K combinator, বা Haskell-এর
const: প্রথম argument ফেরত দেয়, দ্বিতীয়টি ফেলে দেয়। - যেখানে প্রমাণ নেই। এবার A → B চেষ্টা করুন। a : A অনুমান করার পর লক্ষ্য B, কিন্তু Γ-তে B type-এর কিছু নেই, আর কোনো function-ও নেই যা B ফেরত দেয়। আটকে গেলাম। যুক্তিতে A → B সত্য নয় (A সত্য, B মিথ্যা হলে)। প্রস্তাব মিথ্যা মানে type-এর কোনো program নেই।
লেখকের lab-এ একটি ছোট প্রমাণ-খোঁজার program (STLC-এর β-normal term খোঁজে, গভীরতা ৮ পর্যন্ত; প্রতিটি পাওয়া term অংশ ৫-এর checker দিয়ে আবার যাচাই) সত্যিকারের run-এ এই ফল দিয়েছে (CPython 3.14.4):
A → B → A : λx0:A. λy1:B. x0
(A → B) → (B → C) → A → C : λx0:(A → B). λy1:(B → C). λz2:A. y1 (x0 z2)
A → B : কোনো মান নেই (গভীরতা ৮ পর্যন্ত)
((A → B) → A) → A (Peirce) : কোনো মান নেই (গভীরতা ৮ পর্যন্ত)
A → A → A : λx0:A. λy1:A. x0
দ্বিতীয় লাইনটি implication-এর transitivity (“A থেকে B, B থেকে C, তাহলে A থেকে C”), আর তার প্রমাণ হলো function composition: আগে x0, তারপর y1. চতুর্থ লাইনটি সূক্ষ্ম। ((A → B) → A) → A, যার নাম Peirce's law, truth table-এ সবসময় সত্য (একটি tautology), অথচ STLC-তে তার কোনো program নেই। কারণ Curry–Howard-এর যুক্তিটি সাধারণ “সত্য-মিথ্যা” যুক্তি নয়; এটি intuitionistic logic, যেখানে প্রমাণ মানে একটি নির্মাণ দেখানো, আর “A অথবা না-A” বিনা প্রমাণে ধরে নেওয়া যায় না। (গভীরতা-সীমার খোঁজ “নেই” প্রমাণ করে না; Peirce's law intuitionistic logic-এ প্রমাণযোগ্য নয়, এটি একটি পরিচিত ফল।) শেষ লাইনটিও শিক্ষণীয়: A → A → A-এর দুটি ভিন্ন program আছে (প্রথম বা দ্বিতীয় argument ফেরত), অর্থাৎ একই প্রস্তাবের দুটি ভিন্ন প্রমাণ।
এখন অংশ ৫-এর কড়াকড়ির কারণ পরিষ্কার। fix থাকলে fix (λx:A. x)-এর type যেকোনো A, তাই প্রতিটি প্রস্তাবের, এমনকি মিথ্যারও, একটি “প্রমাণ” লেখা যায়, যা আসলে কখনো শেষ হয় না। যুক্তি ভেঙে পড়ে। তাই Coq/Rocq, Lean আর Agda-র মতো proof assistant সব function-কে থামতে বাধ্য করে; সেখানে একটি theorem-এর প্রমাণ সত্যিই একটি program, আর type checker-ই প্রমাণ-পরীক্ষক। পর্ব ৪৪-এ (Formal verification — Coq/Lean, verified compiler আর property) এই ধারা আসবে।
৭ · System F এক ঝলক — type-এর ওপর λ
STLC-তে identity function প্রতিটি type-এর জন্য আলাদা লিখতে হয়: λx:Int. x, λx:Bool. x … ৩৬ নম্বর পর্বের parametric polymorphism-এর ভাষায় এটি কোডের পুনরাবৃত্তি। সমাধান: type-কেও parameter বানানো। System F-এ দুটি নতুন গঠন আছে: type abstraction Λα. t (“যেকোনো type α নিন”) আর type application t [τ]. Identity হয় id = Λα. λx:α. x, যার type ∀α. α → α, আর ব্যবহার id [Int] 5 ⟶ 5. নিয়ম দুটি (α Γ-তে free না থাকার শর্তসহ):
System F দুজন আলাদাভাবে আবিষ্কার করেন: যুক্তিবিদ Jean-Yves Girard (১৯৭২, যুক্তির দিক থেকে) আর computer scientist John Reynolds (১৯৭৪, “polymorphic lambda calculus” নামে, প্রোগ্রামিং ভাষার দিক থেকে)। Curry–Howard-এর দিক থেকে এটি second-order propositional logic, যেখানে প্রস্তাবের ওপর ∀ লেখা যায়। আর Girard প্রমাণ করেন System F-ও strongly normalizing, যদিও প্রমাণটি STLC-এর চেয়ে অনেক গভীর।
প্রোগ্রামারের জন্য দুটি কথা জরুরি। প্রথমত, পর্ব ৩৫-এর Hindley–Milner আসলে System F-এর একটি সীমিত টুকরো: ∀ শুধু type-এর সবচেয়ে বাইরে, আর শুধু let-এ বাঁধা নামে। কেন এই সীমা? কারণ J. B. Wells ১৯৯০-এর দশকে (১৯৯৪ সালের সম্মেলন-প্রবন্ধ, ১৯৯৯ সালের পূর্ণ রূপ) প্রমাণ করেন যে পূর্ণ System F-এ annotation ছাড়া type inference undecidable. তাই Haskell-এ উচ্চ-rank type লিখতে programmer-কে annotation দিতে হয়। দ্বিতীয়ত, Java, C# বা Rust-এর generics (পর্ব ৩৬–৩৭) ধারণাগতভাবে System F-এর আত্মীয়: <T> T id(T x) হলো Λα. λx:α. x, আর id<Integer>(5) হলো id [Int] 5. Compiler সেটি erasure, monomorphization বা dictionary passing দিয়ে বাস্তবায়ন করে।
আরও গভীরে। System F-এর একটি বিস্ময়কর গুণ হলো parametricity (Reynolds ১৯৮৩): ∀α. α → α type-এর প্রতিটি থেমে যাওয়া function আসলে identity, কারণ α সম্পর্কে কিছু না জেনে সে argument ছাড়া আর কিছু ফেরত দিতে পারে না। Philip Wadler ১৯৮৯ সালের “Theorems for free!” প্রবন্ধে দেখান, শুধু type দেখেই এমন অনেক সমীকরণ পাওয়া যায় (যেমন ∀α. [α] → [α] type-এর যেকোনো function map-এর সঙ্গে বিনিময়যোগ্য), যা compiler optimization-এর বৈধতা প্রমাণে কাজে লাগে। আর Haskell-এর প্রধান compiler GHC-এর ভেতরের ভাষা Core-কে System F-এর একটি বর্ধিত রূপ (System FC, ২০০৭ সালের প্রবন্ধ) হিসেবে বর্ণনা করা হয়।
৮ · Compiler-এর ভেতরে lambda calculus — CPS আর ANF
Lambda calculus শুধু গবেষণার খাতায় নয়, compiler-এর ভেতরেও থাকে। Source program parse আর check হওয়ার পর compiler তাকে একটি intermediate representation-এ নামায় (পর্ব ৬২-এ বিস্তারিত)। Functional ভাষার compiler-গুলো দীর্ঘদিন ধরে এমন IR ব্যবহার করে, যা আসলে কড়া নিয়মে লেখা lambda term. দুটি প্রধান রূপ:
- Continuation-passing style (CPS): কোনো function ফল return করে না; বরং একটি বাড়তি argument পায়, “বাকি program” (continuation k), আর ফল দিয়ে সেটি ডাকে। পর্ব ৩২-এ হাতে লেখা CPS দেখেছেন; compiler তা যান্ত্রিকভাবে করে।
- A-normal form (ANF): প্রতিটি মধ্যবর্তী ফলের একটি নাম,
let t = … in; প্রতিটি operation-এর argument শুধু নাম বা constant (atom). ক্রম স্পষ্ট, কিন্তু continuation-এর λ নেই।
bazar.haat-এর ১০ নম্বর লাইনের expression price(2, 520) + delivery(price(2, 520)) লেখকের lab-এর একটি ছোট converter-এ (বাঁ থেকে ডানে, README সিদ্ধান্ত ১২) সত্যিকারের run-এ এমন হলো (CPython 3.14.4):
ANF:
let t1 = price(2, 520) in
let t2 = price(2, 520) in
let t3 = delivery(t2) in
let t4 = t1 + t3 in
t4
CPS:
price(2, 520, λt1. price(2, 520, λt2. delivery(t2, λt3. halt(t1 + t3))))
তিনটি জিনিস লক্ষ করুন। এক, ANF-এর let-গুলোর ক্রম হুবহু reference-এর bytecode-এর ক্রম (README-এর dis listing-এ নির্দেশ ৪–১৪: আগে প্রথম price call, তারপর delivery-র ভেতরের price, তারপর delivery, শেষে ADD). Evaluation order-এর সিদ্ধান্ত IR-এ লিখিত হয়ে যায়, পরের optimization তা ভাঙতে পারে না। দুই, ANF দেখতে প্রায় three-address code (t4 = t1 + t3), আর প্রতিটি নাম একবারই বাঁধা: ঠিক SSA form-এর মতো। Richard Kelsey ১৯৯৫ সালে আর Andrew Appel ১৯৯৮ সালের “SSA is Functional Programming” প্রবন্ধে দেখান, SSA আর CPS/ANF-এর মধ্যে প্রায় যান্ত্রিক অনুবাদ সম্ভব; SSA-র φ-function আসলে একটি block-এর parameter, আর block আসলে একটি local function (পর্ব ৬৩-এ)। তিন, CPS-এ প্রতিটি call একটি tail call; “return” বলে কিছু নেই, তাই stack-এর হিসাবও IR-এ স্পষ্ট।
ইতিহাস। Guy Steele ১৯৭৮ সালে MIT-এর একটি thesis-এ Rabbit নামের Scheme compiler বানান, যা program-কে CPS-এ রূপান্তর করে কাজ করত। Andrew Appel-এর ১৯৯২ সালের বই Compiling with Continuations Standard ML of New Jersey compiler-এর CPS-ভিত্তিক নকশা বর্ণনা করে। ১৯৯৩ সালে Cormac Flanagan, Amr Sabry, Bruce Duba আর Matthias Felleisen “The Essence of Compiling with Continuations” প্রবন্ধে দেখান, CPS compiler-এর বেশিরভাগ লাভ ANF-এ, continuation ছাড়াই পাওয়া যায়; ANF নামটি সেখান থেকে। পরে বিতর্ক আবার ঘুরেছে (যেমন Andrew Kennedy-র ২০০৭ সালের “Compiling with Continuations, Continued”), আর LLVM-এর মতো C-ধাঁচের ভাষার compiler SSA-কেই বেছে নিয়েছে।
Haat-এর compiler পর্ব ৬২–৬৩-এ three-address code, CFG আর SSA-র পথে যাবে; আর closure-ওয়ালা function-কে machine-এ নামানোর দুটি lambda-কৌশল, closure conversion আর lambda lifting, পর্ব ১৭-এ দেখা হয়েছে। এই অংশের মূল কথা: প্রতিটি পথের শেষে একটি কড়া-নিয়মের lambda term বা তার সমতুল্য রূপ।
পরীক্ষা ও ইন্টারভিউতে। বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় সাধারণ প্রশ্ন আর এক লাইনের উত্তর:
- “FV(λx. x y (λy. y z)) কী?” {y, z}: প্রথম y বাইরের, ভেতরের y λy-তে বাঁধা।
- “Capture-avoiding substitution কেন?” [x ↦ y](λy. x y)-এ সরলভাবে বসালে λy. y y, অর্থ বদলায়; আগে নাম বদলে λy1. y y1.
- “STLC-তে Ω কেন type পায় না?” x x-এর জন্য τ = τ → σ লাগে, যা কোনো সসীম type মানে না।
- “Strong normalization মানে কী, আর fix তা কী করে?” প্রতিটি well-typed term-এর প্রতিটি reduction শেষ হয়; fix যোগে অসীম loop type পায়, গুণটি হারায়।
- “Curry–Howard এক লাইনে?” Type = প্রস্তাব, program = প্রমাণ, β-reduction = প্রমাণ সরল করা।
৯ · AI-এর যুগে lambda calculus
AI assistant lambda calculus-এর প্রশ্নে দ্রুত, আত্মবিশ্বাসী উত্তর দেয়। বিপদ থাকে ছোট ছোট জায়গায়: একটি নাম ধরা পড়া, একটি ভুল reduction-ক্রম, বা “প্রমাণ” যা আসলে একটি উদাহরণ।
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| Substitution-এ ধরা পড়া উপেক্ষা: [x ↦ y](λy. x y)-কে λy. y y লেখা | অংশ ২-এর subst-এ চালিয়ে দেখা; de Bruijn রূপ তুলনা করা |
| Normal order আর call-by-value গুলিয়ে ফেলা, বা λ-এর ভেতরে reduction করে “Python এভাবে চলে” বলা | কোন কৌশলের কথা হচ্ছে স্পষ্ট করে, একটি evaluator-এ ধাপ গুনে মেলানো |
| “Y combinator STLC-তে লেখা যায়” বা “STLC Turing-complete” | Checker-এ চালানো: x x বাতিল হয়; strong normalization theorem মনে রাখা |
| Curry–Howard-এ classical আর intuitionistic যুক্তি গুলিয়ে Peirce's law-এর program দাবি করা | দাবিকৃত term-কে checker-এ দেওয়া; সাধারণত সেটি fix বা call/cc-জাতীয় কিছু লুকিয়ে ব্যবহার করে |
| “System F-এ type inference সম্ভব” বা ভুল সাল ও নাম | Wells-এর ফল আর Girard/Reynolds-এর প্রবন্ধ প্রাথমিক উৎসে মেলানো |
| de Bruijn index-এ off-by-one, বা ০ আর ১ থেকে গোনার রীতি মিশিয়ে ফেলা | কোন রীতি তা জিজ্ঞেস করা; ছোট term-এ converter চালিয়ে মেলানো |
AI-কে কাজে লাগাতে নিয়মগুলো পুরো দিন, আর প্রতিটি দাবির পাশে যাচাইযোগ্য ধাপ চান:
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Landin ১৯৬০-এর দশকে ALGOL 60-কে lambda calculus-এ অনুবাদ করতে চাইলেন কেন, আর আজকের ভাষায় তার প্রভাব কোথায়?
১৯৬০ সালের ALGOL 60 report ছিল সেই সময়ের সবচেয়ে যত্নে লেখা ভাষা-বিবরণ: syntax লেখা হয়েছিল BNF-এ, নিখুঁতভাবে। কিন্তু semantics লেখা ছিল ইংরেজি গদ্যে, আর call-by-name, block, nested procedure-এর মতো জিনিসের অর্থ নিয়ে পাঠকদের মধ্যে মতভেদ ছিল। Peter Landin চাইলেন অর্থটিকেও গাণিতিক করতে। তাঁর কৌশল: ALGOL-এর প্রতিটি গঠনকে lambda notation-এর একটি রূপে অনুবাদ করা, আর lambda term চালানোর জন্য একটি যন্ত্র দেওয়া। ১৯৬৪ সালের SECD যন্ত্র (Stack, Environment, Control, Dump নামের চারটি অংশ থেকে নাম) এমন একটি যন্ত্র, যা substitution না করে environment রাখে; আজকের প্রায় প্রতিটি interpreter-এর environment আর closure-এর ধারণা এর বংশধর।
১৯৬৬ সালের “The Next 700 Programming Languages” প্রবন্ধে Landin আরও সাহসী দাবি করেন: শত শত ভাষার পার্থক্য আসলে ওপরের সাজসজ্জায়; ভেতরে একটি সাধারণ core, যাকে তিনি ISWIM (“If you See What I Mean”) নাম দেন। ISWIM-এ ছিল let আর where, indentation-ভিত্তিক লেখা, আর first-class function. এটি কখনো পুরোপুরি বাস্তবায়িত হয়নি, কিন্তু ML, Haskell-এর মতো পরের ভাষার নকশাকারীরা এর ধারণা নিয়েছেন বলে সাধারণভাবে স্বীকৃত। Closure শব্দটিও Landin-এর।
আজকের প্রভাব তিন জায়গায় স্পষ্ট। এক, ভাষার নকশায় “ছোট core আর তার ওপর desugaring”-এর চর্চা: Haskell-এর Core, Racket-এর ছোট kernel, আর পর্ব ৫৫-এ Haat-এর desugaring একই ভাবনা। দুই, semantics লেখার রীতি: পর্ব ৪০, পর্ব ৪১ আর পর্ব ৪২-এর operational, denotational আর axiomatic পদ্ধতি সবই lambda calculus-এর ওপর পরীক্ষিত হয়ে বড় হয়েছে। তিন, interpreter বানানোর ধাঁচ: environment-ভিত্তিক evaluator, যা পর্ব ৫৬–৫৭-এ Haat-এর জন্য গড়া হবে, SECD-এর সরাসরি উত্তরসূরি। Landin-এর বড় শিক্ষাটি আজও খাটে: নতুন ভাষা বোঝার দ্রুততম পথ হলো তার core খুঁজে বের করা।
মূল উপলব্ধি: Landin lambda calculus-কে ভাষার অর্থ লেখার মাধ্যম বানালেন; SECD থেকে environment আর closure, ISWIM থেকে functional ভাষার নকশা, আর “ছোট core + চিনি” ধারণাটি আধুনিক compiler-এর desugaring-এ বেঁচে আছে।
প্র ০২Church প্রথমে untyped lambda calculus দিয়ে যুক্তির ভিত্তি গড়তে চেয়েছিলেন। Type এল কেন, আর type দিয়ে কী হারাল?
Church-এর মূল পরিকল্পনা ছিল lambda calculus-এর ওপর গোটা গণিতের যুক্তি দাঁড় করানো। ১৯৩৫ সালে তাঁর দুই ছাত্র Stephen Kleene আর J. Barkley Rosser দেখান, সেই পূর্ণ ব্যবস্থাটি স্ববিরোধী (inconsistent): তাতে যেকোনো দাবি প্রমাণ করা যায়। সমস্যার মূলে ছিল self-application, অর্থাৎ x x ধরনের গঠন, যা দিয়ে “এই বাক্যটি মিথ্যা” ধাঁচের প্যারাডক্স তৈরি করা যায়। Church যুক্তির অংশটি বাদ দিয়ে শুধু গণনার অংশটি রাখলেন, যা আজকের untyped lambda calculus, আর সেটি প্রমাণিতভাবে সুসংগত (Church–Rosser theorem তার একটি চাবি)।
যুক্তির জন্য তিনি ১৯৪০ সালে অন্য পথ নিলেন: Bertrand Russell-এর type তত্ত্বের অনুপ্রেরণায় প্রতিটি term-কে একটি type দেওয়া, যাতে x x লেখাই না যায়। এটিই simply typed lambda calculus. অংশ ৪-এ দেখেছেন, ঠিক occurs check-এর কারণে self-application বাদ পড়ে। লাভ বিশাল: strong normalization, আর Curry–Howard-এর মাধ্যমে একটি সুসংগত যুক্তি, যেখানে মিথ্যা প্রস্তাবের কোনো প্রমাণ নেই।
দাম হলো গণনার ক্ষমতা। প্রতিটি program থামে, তাই STLC Turing-সমতুল্য নয়; আরও নির্দিষ্ট করে, শুধু Church numeral-এ লেখা STLC-এর function দিয়ে খুব সীমিত কিছু সংখ্যা-function প্রকাশ করা যায় বলে গবেষণায় দেখানো হয়েছে। প্রোগ্রামিং ভাষা এই দাম দিতে রাজি নয়, তাই প্রায় প্রতিটি typed ভাষা general recursion ফিরিয়ে আনে: ML-এর let rec, Haskell-এর সাধারণ recursion, Haat-এর top-level function. এটি অংশ ৫-এর fix. Proof assistant রাজি, কারণ সেখানে যুক্তির সুসংগতি সবার আগে; Coq/Rocq বা Agda termination checker দিয়ে fix-এর ব্যবহার সীমিত রাখে, আর অসীম চলতে পারে এমন কাজ আলাদা কৌশলে (যেমন coinduction বা “fuel” নামের গণনা-সীমা) লেখায়।
এখান থেকে একটি নকশা-প্রশ্ন আসে, যা প্রতিটি ভাষার সামনে: type system কতটা শক্তিশালী হলে কতটা নিশ্চয়তা, আর কতটা স্বাধীনতা হারানো? Haat-এর মতো সাধারণ ভাষা soundness রাখে, termination ছাড়ে; proof assistant দুটিই রাখে, কিন্তু programmer-কে প্রতিটি recursion-এর থামা দেখাতে হয়।
মূল উপলব্ধি: type এসেছিল self-application-এর প্যারাডক্স ঠেকাতে; দামে গেল Turing-সম্পূর্ণতা, যা প্রোগ্রামিং ভাষা fix দিয়ে ফেরায়, আর proof assistant সচেতনভাবে ফেরায় না।
প্র ০৩Peirce's law-এর কোনো STLC program নেই। অথচ ১৯৯০ সালে দেখানো হলো, call/cc-এর type ঠিক Peirce's law. এর অর্থ কী?
অংশ ৬-এর খোঁজে ((A → B) → A) → A-এর কোনো program পাওয়া যায়নি, আর এটি কাকতালীয় নয়: Curry–Howard-এর যুক্তি intuitionistic, যেখানে “A অথবা না-A” (excluded middle) বা Peirce's law প্রমাণযোগ্য নয়। Intuitionistic যুক্তিতে কোনো কিছুর অস্তিত্ব প্রমাণ মানে সেটিকে বানিয়ে দেখানো; “না থাকলে স্ববিরোধ হতো, তাই আছে” ধরনের যুক্তি যথেষ্ট নয়। Program-এর ভাষায় এটি স্বাভাবিক: একটি function শুধু হাতে যা আছে তা দিয়েই মান বানাতে পারে।
Scheme ভাষায় একটি অদ্ভুত operator আছে, call/cc (call-with-current-continuation). এটি “বাকি program”-কে (continuation) একটি function হিসেবে হাতে তুলে দেয়, যা পরে ডাকলে program সেই মুহূর্তে ফিরে যায়, ঠিক exception-এর মতো লাফ দিয়ে। ১৯৯০ সালে Timothy Griffin “A Formulae-as-Types Notion of Control” প্রবন্ধে দেখান, typed ভাষায় call/cc-এর স্বাভাবিক type হলো ((A → B) → A) → A, অর্থাৎ Peirce's law, আর control operator যোগ করলে Curry–Howard-এর যুক্তি classical logic হয়ে যায়। অর্থাৎ classical যুক্তির “অতিরিক্ত শক্তি” program-এর ভাষায় হলো সময়ের মধ্যে লাফ দেওয়ার ক্ষমতা।
ব্যাখ্যাটি সুন্দর। Peirce's law-এর প্রমাণ এভাবে কাজ করে: “(A → B) → A একটি function দেওয়া আছে। আমি তাকে একটি নকল A → B দিই; যদি সে কখনো সেটি একটি A দিয়ে ডাকে, আমি সেই A নিয়ে লাফ দিয়ে সোজা উত্তরে চলে যাই।” এটি “আগে একটি দাবি করে পরে দরকার হলে ফিরিয়ে নেওয়া”, যা classical প্রমাণের চেনা কৌশল। এর পর থেকে exception, generator, async/await-এর মতো control feature-এর type আর যুক্তি নিয়ে বড় গবেষণা-ধারা তৈরি হয়েছে।
প্রোগ্রামারের জন্য শিক্ষা: একটি type দেখে বলা যায় সেই type-এর program লেখা কতটা “শক্তি” দাবি করে। ভাষায় নতুন control feature (exception, continuation) এলে type system-এর যুক্তিও বদলায়, তাই soundness আর অর্থ নতুন করে যাচাই করতে হয়, যেমন পর্ব ৩৮-এ দেখেছেন।
মূল উপলব্ধি: intuitionistic যুক্তি = বিশুদ্ধ function; continuation-এর মতো control operator যোগ করলে যুক্তি classical হয়, আর Peirce's law-এর প্রমাণ হয়ে যায় call/cc.
প্র ০৪GHC-এর মতো compiler optimization-এর পরেও ভেতরের প্রতিটি ধাপে typed lambda term রাখে কেন, যখন শেষ machine code-এ type থাকেই না?
Haskell source প্রথমে desugar হয়ে Core নামের একটি ছোট ভাষায় নামে, যা System F-এর একটি বর্ধিত রূপ (System FC). এরপর শত শত optimization pass (inlining, specialization, case-of-case, let-floating) এই Core-এর ওপরেই চলে, আর প্রতিটি pass-এর পরেও ফল একটি well-typed Core program. শেষ ধাপে type মুছে ফেলা হয় (type erasure) আর অন্য IR-এ নামানো হয়। প্রশ্ন হলো, এত ঝামেলা কেন?
প্রথম কারণ ভুল ধরা। Optimization pass লেখা কঠিন, আর একটি ভুল pass নিঃশব্দে ভুল program বানাতে পারে। GHC-এর “Core Lint” নামের একটি checker প্রতিটি pass-এর পর (নির্দিষ্ট flag দিলে) Core program-টি আবার type-check করে। কোনো pass যদি type ভাঙে, তা প্রায় নিশ্চিতভাবে একটি compiler bug, আর তা ঠিক কোন pass-এ ঘটল তা সাথে সাথে ধরা পড়ে। এটি পর্ব ৩৮-এর preservation-এর একটি ব্যবহারিক রূপ: সঠিক রূপান্তর type রক্ষা করে, তাই type ভাঙলে রূপান্তর ভুল।
দ্বিতীয় কারণ তথ্য। Type জানা থাকলে optimizer আরও সাহসী হতে পারে: কোন মান function, কোনটি সংখ্যা, কোন generic call কোন type-এ specialize করলে লাভ, তা type থেকে জানা যায়। ১৯৯০-এর দশকে এই ভাবনা থেকে typed intermediate language নিয়ে বড় গবেষণা হয়, যেমন Greg Morrisett ও সহকর্মীদের TIL compiler আর ১৯৯৮ সালের “From System F to Typed Assembly Language”, যেখানে type একেবারে assembly পর্যন্ত বহন করা হয়, যাতে শেষ machine code-এরও নিরাপত্তা যাচাই করা যায়।
দাম আছে: typed IR বড়, প্রতিটি pass-কে type ঠিক রাখতে হয়, আর কিছু রূপান্তর (যেমন কিছু low-level কৌশল) type-এ প্রকাশ করা কঠিন। তাই অনেক compiler একটি পর্যায় পর্যন্ত typed IR রাখে, তারপর untyped বা দুর্বল-typed IR-এ (যেমন LLVM IR-এর সরল type) নামে। Haat-এর compiler-ও checker-এর পর type-তথ্য ব্যবহার করে bytecode বানায়, কিন্তু bytecode নিজে type বহন করে না।
মূল উপলব্ধি: typed lambda term-কে IR রাখলে প্রতিটি optimization-এর পর একটি সস্তা সঠিকতা-পরীক্ষা পাওয়া যায় আর optimizer-এর হাতে তথ্য থাকে; type মোছা হয় যত দেরিতে সম্ভব।
প্র ০৫Compiler-এর IR হিসেবে CPS, ANF আর SSA: তিনটিই “একই জিনিস” বলে প্রমাণিত হলে বাস্তব compiler-গুলো আলাদা পথ বেছে নিল কেন?
তিনটি রূপের মিল অংশ ৮-এ দেখেছেন: প্রতিটি মধ্যবর্তী মানের একটি নাম, নাম একবারই বাঁধা, আর evaluation order স্পষ্ট। Kelsey (১৯৯৫) আর Appel (১৯৯৮) দেখান CPS আর SSA-র মধ্যে যান্ত্রিক অনুবাদ আছে; Flanagan ও সহকর্মীরা (১৯৯৩) দেখান ANF-এ CPS-এর বেশিরভাগ লাভ থাকে। তবু “সমতুল্য” মানে “সমান সুবিধাজনক” নয়; প্রতিটি রূপে কিছু কাজ সহজ, কিছু কঠিন।
CPS-এ সব control flow, এমনকি return আর exception-ও, একটি function call; তাই call/cc, coroutine বা tail call-এর মতো জটিল control সহজে প্রকাশ হয়। Steele-এর Rabbit আর Appel-এর SML/NJ এই সুবিধা নিয়েছিল। অসুবিধা: প্রতিটি continuation একটি নতুন λ, IR অনেক বড় হয়, আর কিছু সাধারণ optimization (যেমন একটি call-এর ফলকে সাধারণ মান হিসেবে দেখা) জটিল হয়ে যায়। ANF এই সমস্যার অনেকটা সারায়, তাই বেশ কিছু functional compiler ANF-ধাঁচের IR নেয়; Kennedy ২০০৭ সালে আবার যুক্তি দেন যে নির্দিষ্ট ধরনের CPS আসলে optimization সহজ করে, আর বিতর্কটি আজও পুরোপুরি মীমাংসিত নয়।
C, C++, Rust বা Swift-এর মতো ভাষার compiler-এর কাজ ভিন্ন: loop, pointer, memory, register. সেখানে SSA-ভিত্তিক CFG স্বাভাবিক, কারণ dataflow analysis (পর্ব ৬৪), loop optimization (পর্ব ৬৬) আর register allocation (পর্ব ৭০) সবই CFG-তে ভালোভাবে বোঝা আর বাস্তবায়িত। LLVM আর GCC (GIMPLE-এর SSA রূপ) এই পথে। আবার কিছু আধুনিক নকশা দুটিকে মেশায়: MLIR আর Swift-এর SIL-এর মতো IR-এ basic block-এর parameter থাকে, যা φ-function-এর বদলে ঠিক Appel-এর “block = local function” ধারণা।
অর্থাৎ পছন্দটি নির্ভর করে source ভাষার চরিত্র আর compiler কোন optimization-এ জোর দেয় তার ওপর। Haat-এর মতো ভাষা, যার closure আছে কিন্তু call/cc নেই, আর loop-ও আছে, তার জন্য এই কোর্স SSA-র পথ নেবে (পর্ব ৬৩); কিন্তু ভেতরের ভাবনাটি, প্রতিটি মানের একটি নাম আর স্পষ্ট ক্রম, এই পর্বের lambda calculus থেকেই আসে।
মূল উপলব্ধি: CPS, ANF আর SSA গাণিতিকভাবে আত্মীয়, কিন্তু প্রকৌশলে আলাদা; জটিল control-এর ভাষা CPS/ANF-এর দিকে, loop আর memory-প্রধান ভাষা SSA-র দিকে ঝোঁকে, আর block parameter দুই জগৎকে কাছে আনছে।
অনুশীলন
প্রথমে নিজে লিখুন বা হিসাব করুন, তারপর উত্তর খুলুন। প্রতিটি উত্তর চালানো কোড দিয়ে যাচাই করা।
-
নকশা ও বাস্তবায়ন — STLC-তে
let: Haat-এরlet x = e;-এর মতো একটি গঠনlet x = t₁ in t₂যোগ করুন। (ক) typing rule (T-Let) আর evaluation rule লিখুন। (খ) একে (λx:τ₁. t₂) t₁-এ desugar করা যায় দেখান, আর τ₁ কোথা থেকে আসে বলুন। (গ) অংশ ৫-এরtypeof-এর ওপর একটি desugar function লিখেlet p = 2 * 520 in let d = if p == 1040 then 0 else 60 in p + dচালান।(ক) T-Let: Γ ⊢ t1 : τ1 আর Γ, x : τ1 ⊢ t2 : τ2 থেকে Γ ⊢ let x = t1 in t2 : τ2. Evaluation (call-by-value): E-Let (t1 ⟶ t1′ হলে let x = t1 in t2 ⟶ let x = t1′ in t2) আর E-LetV (let x = v in t2 ⟶ [x ↦ v] t2).
(খ) (λx:τ1. t2) t1-এর derivation T-Call আর T-Fn দিয়ে হুবহু T-Let-এর premise দুটিই চায়, আর evaluation-এ E-Call2 তারপর E-CallFn হুবহু E-Let তারপর E-LetV. সমস্যা শুধু একটি: λ-এ τ1 লিখতে হয়, অথচ let-এ লেখা নেই। তাই desugar করতে হয় type checking-এর পরে (বা সময়ে), t1-এর type বের করে; Haat-এর
let-ও initializer থেকে type নেয়। পর্ব ৩৫-এর Hindley–Milner-এ let আরও বিশেষ: সেখানে let-এ generalization (∀) হয়, λ-এ হয় না, তাই সেখানে let নিছক চিনি নয়।(গ) লেখকের lab-এ (CPython 3.14.4) একটি ছোট
desugarfunction (t1-এর typetypeofদিয়ে বের করে λ-এ বসায়), সত্যিকারের run:type Int (λp:Int. (λd:Int. p + d) (if (p == 1040) then 0 else 60)) (2 * 520) typeof Int 1040 6Desugar-এর আগে আর পরে type একই (Int), আর অংশ ২-এর evaluator ৬ ধাপে
1040দেয়: p = 1040, তাই ডেলিভারি ০, মোট ১০৪০। -
ভুল প্রমাণ খুঁজুন: একজন STLC-এর strong normalization এভাবে “প্রমাণ” করলেন: “term-এর আকার (node-এর সংখ্যা) n ধরে induction. প্রতিটি β-ধাপ (λx:τ. t) v ⟶ [x ↦ v] t একটি λ আর একটি call সরায়, তাই আকার কমে। আকার ঋণাত্মক হতে পারে না, তাই reduction-শিকল সসীম। ∎” কোন ধাপ ভুল? একটি সংখ্যাসহ পাল্টা উদাহরণ দিন, আর সঠিক প্রমাণ কী করে বলুন।
ভুল “তাই আকার কমে” কথাটিতে। λ আর call সরে ঠিকই, কিন্তু [x ↦ v] t-এ দেহে x যতবার আছে, v ততবার কপি হয়; v বড় হলে term বড় হয়। পাল্টা উদাহরণ (প্রতিটি variable, সংখ্যা, λ, call আর operator একটি node): t = (λf:(Int → Int). f (f 1)) (λy:Int. (y + y) + y). লেখকের lab-এ গোনা আকার ১৩. এক β-ধাপ পরে (λy:Int. (y + y) + y) ((λy:Int. (y + y) + y) 1), আকার ১৫: বেড়েছে। (term-টি অবশ্য শেষ হয়: ৭ ধাপে
9; theorem সত্য, শুধু এই প্রমাণ ভুল।)সঠিক প্রমাণ (Tait-এর কৌশল, অংশ ৫): term-এর আকার নয়, type-এর আকার ধরে একটি শক্ত শর্ত (reducibility) সংজ্ঞায়িত করা, আর দেখানো যে প্রতিটি well-typed term সেই শর্ত মানে। লক্ষ করুন, ভুল প্রমাণটি type ব্যবহারই করেনি; তাহলে সেটি untyped Ω-এর জন্যও “খাটত”, অথচ Ω শেষ হয় না। Type কোথাও না লাগা প্রমাণ মানেই সন্দেহজনক প্রমাণ।
-
Trace আর আউটপুট অনুমান: call-by-value, বাঁ থেকে ডানে, λ-এর ভেতরে নয়। নিচের term-টির type বের করুন, তারপর প্রতিটি ধাপ নিয়মের নামসহ (congruence-সহ) লিখুন। কত ধাপ, আর শেষ value কী?
(λf:(Int → Int). f (f 1)) (λy:Int. y + y)Type: λf-এর দেহ f (f 1): f 1 : Int (T-Call), তারপর f (…) : Int; তাই বাঁ অংশ (Int → Int) → Int, argument Int → Int, ফল Int. অংশ ২ ও ৫-এর code দিয়ে লেখকের lab-এ চালানো (CPython 3.14.4) আউটপুট:
type Int 0: (λf:(Int → Int). f (f 1)) (λy:Int. y + y) ⟶ E-CallFn 1: (λy:Int. y + y) ((λy:Int. y + y) 1) ⟶ E-Call2(E-CallFn) 2: (λy:Int. y + y) (1 + 1) ⟶ E-Call2(E-Add) 3: (λy:Int. y + y) 2 ⟶ E-CallFn 4: 2 + 2 ⟶ E-Add 5: 4৫ ধাপ, value
4(“দুবার দ্বিগুণ”)। ধাপ ১-এর পরে বাইরের call-এর callee ইতিমধ্যে value (একটি λ), তাই E-Call2 দিয়ে argument-এ ঢুকতে হয়: call-by-value-এ argument আগে value হবে, তারপর β. Normal order হলে ধাপ ১-এর পরে আগে বাইরের β হতো, আর argument(λy:Int. y + y) 1দেহে দুবার কপি হয়ে দুবার হিসাব হতো (পর্ব ১৯-এর পার্থক্য)। -
Curry–Howard-এর হিসাব: (ক) (A → B → C) → (A → B) → A → C-এর একটি program লিখুন আর প্রতিটি অংশের type দেখান। (খ) A → (A → B) → B কি প্রমাণযোগ্য? Program দিন বা কারণ দেখান। (গ) “একই প্রস্তাবের দুটি ভিন্ন প্রমাণ” আছে এমন একটি type দিন।
(ক) λf:(A → B → C). λg:(A → B). λa:A. f a (g a). যাচাই: a : A; g a : B (T-Call); f a : B → C; (f a) (g a) : C. তিনটি T-Fn দিয়ে পুরো type. এটি S combinator; যুক্তিতে “A থেকে B-হলে-C, আর A থেকে B; তাহলে A থেকে C”.
(খ) হ্যাঁ: λa:A. λf:(A → B). f a. এটি modus ponens-এর নিজের প্রমাণ: A আর A ⇒ B থেকে B, program-এ “argument দিয়ে function ডাকো”। লেখকের lab-এর প্রমাণ-খোঁজার program-এ (অংশ ৬) এই দুটি type-এর term পাওয়া যায়, আর অংশ ৫-এর checker দুটিকেই মেনে নেয়।
(গ) A → A → A: λx:A. λy:A. x আর λx:A. λy:A. y. দুটিই সঠিক program, কিন্তু আলাদা আচরণ (de Bruijn-এ λ. λ. 1 আর λ. λ. 0, তাই α-equivalent-ও নয়)। Curry–Howard-এ প্রমাণ শুধু “সত্য কি না” নয়, “কীভাবে” তারও রেকর্ড: দুটি প্রমাণ দুটি ভিন্ন program.
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমCall-by-value-এ (বাঁ থেকে ডানে, λ-এর ভেতরে নয়) (λx:Int. x + 1) ((λy:Int. y * 2) 3) চালালে যে term-গুলো পরপর আসে, সেভাবে সাজান (▲▼ চেপে সরান)
- (λx:Int. x + 1) ((λy:Int. y * 2) 3)
- (λx:Int. x + 1) (3 * 2)
- (λx:Int. x + 1) 6
- 6 + 1
- 7
Lambda term λx. x y (λy. y z)-এর free variable-এর set কোনটি?
- {y, z}
- {z}
- {x, y, z}
- ∅ (কোনো free variable নেই)
Capture-avoiding substitution অনুযায়ী [x ↦ y](λy. x y)-এর ফল কোনটি (α-equivalent রূপ ধরে)?
- λy. y y
- λy. x y
- λy1. y y1
- λy1. x y1
০ থেকে গোনা de Bruijn index-এ λx. λy. y x কীভাবে লেখা হয়?
- λ. λ. 1 0
- λ. λ. 0 1
- λ. λ. 1 2
- λ. λ. 0 0
Simply typed lambda calculus-এ λx:τ. x x কোনো τ দিয়েই type পায় না কেন?
- STLC-তে function argument হিসেবে function দেওয়া যায় না
- একই variable দুবার ব্যবহার নিষেধ
- Type checker অসীম loop-এ পড়ে
- x x-এর জন্য τ = τ → σ লাগে, যা কোনো সসীম type মানে না
শুধু base type A আর B থাকলে (কোনো constant নেই) নিচের কোন type-এর কোনো বন্ধ STLC term নেই?
- A → B
- A → B → A
- (A → B) → A → B
- A → A
Simply typed lambda calculus-এ T-Fix (Γ ⊢ t : τ → τ থেকে Γ ⊢ fix t : τ) আর E-FixBeta যোগ করলে কোন গুণটি হারায়?
- Type soundness
- প্রতিটি term-এর type-এর অনন্যতা
- Strong normalization (প্রতিটি well-typed term থামে)
- বাঁ থেকে ডানে evaluation order
Compiler IR হিসেবে A-normal form (ANF)-এর মূল শর্ত কোনটি?
- প্রতিটি function ফলের বদলে একটি continuation ডাকে
- প্রতিটি operation আর call-এর argument একটি নাম বা constant, মধ্যবর্তী ফল let-এ বাঁধা
- প্রতিটি variable একটি সংখ্যা দিয়ে লেখা
- প্রতিটি term-এর সঙ্গে type লেখা থাকে
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Core: lambda calculus-এর তিন গঠন x, λx. t, t t; Haat-এর নামহীন
fnআর call এর রূপ, আর closure হলো substitution-এর যন্ত্র-রূপ। - Substitution: β-ধাপ (λx. t) v ⟶ [x ↦ v] t; বসানো নাম ভেতরের λ-এ ধরা পড়ার ভয় থাকলে আগে α-renaming. de Bruijn index (০ থেকে গোনা) নাম মুছে α-সমতাকে সাধারণ সমতা বানায়।
- STLC: T-Var, T-Fn, T-Call (Pierce-এ T-Abs, T-App); sound; x x-এর type নেই; strong normalization (Tait ১৯৬৭-এর কৌশল)। ২,০০০ এলোমেলো term, ০টি অসীম।
- fix আর System F: fix recursion ফেরায় কিন্তু থামার নিশ্চয়তা নেয়; System F (Girard ১৯৭২, Reynolds ১৯৭৪) ∀α যোগ করে, আর তার পূর্ণ type inference undecidable (Wells).
- Curry–Howard আর IR: type = প্রস্তাব, program = প্রমাণ, β = প্রমাণ সরল করা; যুক্তিটি intuitionistic (Peirce's law-এর program নেই)। CPS আর ANF compiler-এর ভেতরের lambda term, SSA-র আত্মীয়।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৪৪ · Formal verification — Coq/Lean, verified compiler আর propertyপরবর্তী পর্বপ্রমাণকে program হিসেবে লেখা আর যন্ত্রে যাচাই।
- প্রোগ্রামিং ভাষা ও কম্পাইলার · কোর্স হোম৮৬টি পর্বপুরো কোর্সের মানচিত্র আর Haat প্রজেক্টের পথ।
- পর্ব ৩৮ · Type soundness — progress আর preservationএই কোর্সেsubstitution lemma আর STLC-এর soundness-এর প্রমাণ-ছক।
- পর্ব ৩৫ · Type inference — Hindley–Milner আর unificationএই কোর্সেoccurs check, let-polymorphism আর System F-এর সীমা।
- গণনার তত্ত্ব · পর্ব ৪৯ · গণনার মডেলপাশের ট্র্যাকChurch numeral, Church–Rosser, Y combinator আর Turing-সমতুল্যতা।
- Discrete Mathematics · পর্ব ০৬ · অনুমানের নিয়মপাশের ট্র্যাকmodus ponens আর প্রমাণের নিয়ম, Curry–Howard-এর যুক্তির দিক।