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

উন্নত type — gradual, linear, dependent আর refinement type

Advanced Types — Gradual, Linear, Dependent and Refinement Types

Taught in Bangla, this lesson extends ordinary types in four directions. It covers gradual typing with the unknown type, the non-transitive consistency relation, casts and blame, and compares TypeScript any and unknown and mypy Any through real checker output. In-page Python (Pyodide) checkers demonstrate gradual casts, affine use-after-move detection and length-indexed vectors with refinements, alongside Rust ownership, dependent types and Curry–Howard, refinement types solved by SMT, effect systems and typestate.

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

  • Gradual typing-এর ? type, consistency relation, cast বসানো আর blame, আর optional বনাম sound gradual typing-এর পার্থক্য
  • TypeScript 5.9-এর any আর unknown, আর mypy-র Any, সত্যিকারের checker-এর আউটপুটে
  • Linear আর affine type, structural rule কেন বাদ পড়ে, আর use-after-move কীভাবে ধরা হয়
  • Dependent type (Vec n, Curry–Howard) আর refinement type (শর্ত-সহ type, SMT) দিয়ে মানের তথ্য type-এ রাখা
  • Effect system আর typestate: checked exception, async-এর রঙ আর অর্ডারের অবস্থা যে একই পরিবারের ধারণা

১ · সাধারণ type যা বলতে পারে না — চার দিকে বিস্তার

বাজারঘরের গুদামে প্রতিটি বাক্সে একটি লেবেল থাকে: “চাল”, “তেল”, “ডাল”। লেবেল দেখে কর্মী জানেন বাক্সটি কোন তাকে যাবে। এটি সাধারণ type-এর কাজ: Int, Str, (Int, Int) -> Int বলে দেয় মানটি কোন ধরনের। পর্ব ৩৩ থেকে ৩৮ পর্যন্ত আপনি এই লেবেলের নিয়ম, অনুমান, polymorphism আর soundness দেখেছেন।

কিন্তু গুদামের ব্যবস্থাপক আরও কিছু জানতে চান, যা “চাল” লেবেলে লেখা নেই। কিছু বাক্সের লেবেল এখনও লাগানো হয়নি, সেগুলো কি গুদামে ঢুকবে? ঈদের ছাড়ের ভাউচার একবারই ব্যবহার করা যায়, লেবেলে সেটা লেখা যায়? বাক্সে ঠিক কত কেজি আছে, শূন্য কেজি নয় তো? আর এই বাক্স কি এখন পাঠানো যায়, নাকি আগে টাকা পরিশোধ হতে হবে? প্রতিটি প্রশ্নের জন্য গবেষকেরা একটি করে উন্নত type system বানিয়েছেন। এই পর্ব সেগুলোর মানচিত্র।

ছবি ৩৯.১ — সাধারণ type থেকে চার দিকে বিস্তার

মাঝে সাধারণ type-এর প্রশ্ন; চার কোণে চারটি নতুন প্রশ্ন, প্রতিটির type system আর এই পর্বের অংশ

Four directions beyond simple types: gradual, linear and affine, dependent and refinement, effects and typestate সাধারণ type কোন ধরনের মান? Gradual কতটা যাচাই এখনই? অংশ ২, ৩ Linear, affine কতবার ব্যবহার? অংশ ৪ Dependent, refinement মানটি ঠিক কী? অংশ ৫, ৬ Effect, typestate কী ঘটায়, কখন? অংশ ৭

চারটি দিক একে অপরের বিকল্প নয়; একই ভাষায় কয়েকটি একসঙ্গে থাকতে পারে। Rust-এ affine type আর typestate-এর ধাঁচ একসঙ্গে আছে, Idris 2-এ dependent আর linear type একসঙ্গে। তবে প্রতিটি দিকে একটি সাধারণ আপস আছে: type যত বেশি কথা বলে, checker তত বেশি ভুল ধরে, আর লেখককে তত বেশি তথ্য দিতে হয়। ছবির বাঁ-ওপরের কোণ উল্টো দিকে যায়: gradual typing লেখককে কম তথ্য দেওয়ার অনুমতি দেয়।

Haat v1-এ এর কোনোটিই নেই: type চারটি নাম আর function type, কোনো ? নেই, কোনো move নেই। এই পর্বের প্রতিটি Haat উদাহরণ তাই “Haat-এর বর্ধিত রূপ”, শুধু ধারণা দেখানোর খসড়া। Reference implementation-এ let order: ? = 2; লিখলে সত্যিকারের run-এ প্রথম ধাপেই আসে 1:12: error: unexpected character '?', কারণ v1-এর lexer ? চেনেই না।

২ · Gradual typing — ? type আর consistency

পর্ব ১২-এ (Scripting আর dynamic ভাষা) gradual typing-এর ভূমিকা দেখেছেন: একই program-এ type লেখা আর না-লেখা অংশ পাশাপাশি। এবার তার নিয়ম। ধারণাটির তাত্ত্বিক রূপ দেন Jeremy Siek আর Walid Taha, ২০০৬ সালের “Gradual Typing for Functional Languages” গবেষণাপত্রে। তাঁদের মূল উপাদান দুটি।

এক, একটি নতুন type ?, যার নাম dynamic type: “এখানে type জানা নেই, চলার সময় দেখা যাবে”। লেবেল ছাড়া বাক্সের মতো: গুদামে ঢুকতে দেওয়া হয়, কিন্তু তাকে তোলার সময় খুলে দেখতে হয়।

দুই, সমতার বদলে consistency, লেখা হয় S ~ T (পড়ুন “S আর T সংগত”)। পর্ব ৩৪-এর T-Call চায় argument-এর type হুবহু parameter-এর type-এর সমান। Gradual রূপে “সমান”-এর জায়গায় বসে “সংগত”:

 
? ~ T     T ~ ?
(C-Dyn)
B একটি মৌলিক type
B ~ B
(C-Base)
Si ~ Ti (প্রতিটি i)    R ~ R′
(S1, …, Sn) -> R ~ (T1, …, Tn) -> R′
(C-Fn)
Γ ⊢ f : (T1, …, Tn) -> R    Γ ⊢ ei : Si    Si ~ Ti
Γ ⊢ f(e1, …, en) : R
(T-Call~)

Consistency দেখতে সমতার মতো: প্রতিফলী (T ~ T) আর প্রতিসম (S ~ T হলে T ~ S হয়)। কিন্তু একটি গুণ নেই: সে transitive নয়। Int ~ ? আর ? ~ Bool, অথচ Int ≁ Bool. Transitive হলে ?-এর মাধ্যমে যেকোনো type যেকোনো type-এর সঙ্গে মিলে যেত, আর checker কিছুই ধরত না। এই ছোট বিষয়টিই gradual typing-এর প্রাণ: যেখানে দুই পাশের type-ই জানা, সেখানে checker পুরোনো কঠোরতায় কাজ করে; ঢিলেমি শুধু সেখানে, যেখানে কোনো এক পাশে ? আছে। দুই পাশেই ? না থাকলে S ~ T আর S = T একই কথা, তাই পুরোনো সব well-typed program ঠিক আগের মতোই গৃহীত (অনুশীলন ৪-এ এর প্রমাণ)।

Cast আর blame — ঢিলেমির দাম চলার সময় শোধ

Checker যখন ? থেকে Int-এ যাওয়ার অনুমতি দেয়, তখন সে আসলে একটি প্রতিশ্রুতি নেয়: “চলার সময় এটি Int হবে”। Sound gradual typing এই প্রতিশ্রুতি যাচাই করে। Compile-এর সময় checker প্রতিটি এমন জায়গায় একটি runtime cast বসায়, লেখা হয় ⟨Int ⇐ ?⟩e: “e-এর মান চলার সময় পরীক্ষা করা, Int না হলে থামা”। এখানে ব্যর্থ হলে দোষ কার? Philip Wadler আর Robert Bruce Findler ২০০৯ সালের “Well-Typed Programs Can't Be Blamed” গবেষণাপত্রে দেখান, প্রতিটি cast-এ একটি লেবেল রাখলে ভুলের দায় (blame) সবসময় কম-type-লেখা দিকে যায়: type-লেখা অংশের প্রতিশ্রুতি ভাঙে না, ভাঙে ? দিয়ে আসা মান।

1fn price(qty: Int, unit: Int) -> Int {2    return qty * unit;3}4let order: ? = load();5let free = false;6print(price(order, 520));7print(price(free, 520));
Checker-এর অবস্থা
Γ-তে নতুন
প্রশ্ন
Cast
  1. Type-লেখা অংশ। price-এর parameter আর ফেরত-type লেখা আছে, তাই Γ0-তে price : (Int, Int) -> Int. এই function-এর ভেতরটা পুরোনো কঠোর নিয়মেই যাচাই হয়।
  2. অজানা জগৎ। load() ধরুন বাইরের JSON পড়ে, তাই লেখক type দিয়েছেন ?. T-Let শুধু order : ? যোগ করে; এখানে যাচাইয়ের কিছু নেই।
  3. জানা মান। false একটি Bool literal, তাই free : Bool. এটি সাধারণ, পুরো static একটি নাম।
  4. প্রথম argument. T-Call~ চায় order-এর type parameter-এর type-এর সঙ্গে সংগত হোক: ? ~ Int, নিয়ম C-Dyn দিয়ে সত্য। কিন্তু type সমান নয়, তাই checker এখানে একটি cast বসায়: ⟨Int ⇐ ?⟩order.
  5. দ্বিতীয় argument আর ফল। 520 : Int, আর Int ~ Int, সমানও, তাই cast লাগে না। ফল price-এর ফেরত-type Int, আর T-Print Int মানে। লাইন ৬ গৃহীত, cast-সহ।
  6. লাইন ৭: পুরোনো কঠোরতা। free : Bool, আর Bool ~ Int সত্য নয়: দুই পাশেই জানা type, তাই consistency মানে সমতা। ?-এর মাধ্যমে ঘুরিয়ে মেলানো যায় না, কারণ সম্পর্কটি transitive নয়। চালানোর আগেই static error.
  7. চলার সময় (লাইন ৭ বাদ দিয়ে)। load() যদি Int 2 দেয়, cast পার হয় আর ছাপা হয় 1040. যদি লেখা "2" দেয়, cast ঠিক সীমানায় থামে, price-এর ভেতরে ঢোকার আগেই, আর দোষ যায় অজানা দিকের ওপর। বার্তাগুলো নিচের block-এর সত্যিকারের আউটপুট।

নিচের block ঠিক এই checker. cons() হলো consistency-র তিনটি নিয়ম, check() T-Call~ চালিয়ে যেখানে type সমান নয় সেখানে ("cast", …) node বসায়, আর run() cast node-এ মানের আসল type পরীক্ষা করে। এটি Haat-এর বর্ধিত রূপের খসড়া; reference-এর typechecker.py-এর call()-এ এই পরিবর্তন দুই জায়গায় লাগত: সমতার তুলনা আর cast-সহ AST ফেরত দেওয়া।

# Gradual typing: ? type, consistency (~) আর cast বসানো — Haat-এর বর্ধিত রূপ
def show(t): return t if isinstance(t, str) else f"({', '.join(map(show, t[0]))}) -> {show(t[1])}"
def cons(s, t):                       # s ~ t : consistency, সমতার ঢিলে রূপ
    if "?" in (s, t): return True
    if isinstance(s, tuple) and isinstance(t, tuple):
        return len(s[0]) == len(t[0]) and all(map(cons, s[0], t[0])) and cons(s[1], t[1])
    return s == t
def check(G, e):                      # ফেরত: (type, cast বসানো expression)
    if e[0] in ("int", "str"): return ("Int" if e[0] == "int" else "Str"), e
    if e[0] == "var": return G[e[1]], e
    ft, args = G[e[1]], [check(G, a) for a in e[2]]          # ("call", f, [args])
    out = []
    for i, ((t, a), p) in enumerate(zip(args, ft[0]), 1):
        if not cons(t, p): raise TypeError(f"type mismatch: expected {show(p)}, found {show(t)}")
        out.append(a if t == p else ("cast", p, t, a, f"argument {i} of {e[1]}"))
    return ft[1], ("call", e[1], out)
def tyof(v): return "Int" if type(v) is int else "Bool" if type(v) is bool else "Str"
def run(env, e):                      # চালানো: cast-এ মানের আসল type যাচাই
    if e[0] in ("int", "str", "var"): return env[e[1]] if e[0] == "var" else e[1]
    if e[0] == "cast":
        v = run(env, e[3])
        if tyof(v) != e[1]: raise RuntimeError(f"cast failed: expected {e[1]}, found {tyof(v)} (blame: {e[4]})")
        return v
    return env[e[1]](*[run(env, a) for a in e[2]])
def src(e): return (f"⟨{e[1]} ⇐ {e[2]}⟩{src(e[3])}" if e[0] == "cast" else str(e[1]) if e[0] != "call"
                   else f"{e[1]}({', '.join(map(src, e[2]))})")
print("Int ~ ? :", cons("Int", "?"), "| ? ~ Bool :", cons("?", "Bool"), "| Int ~ Bool :", cons("Int", "Bool"),
      "| (?) -> Int ~ (Str) -> Int :", cons((("?",), "Int"), (("Str",), "Int")))
G = {"price": (("Int", "Int"), "Int"), "order": "?", "free": "Bool"}
for e in [("call", "price", [("var", "order"), ("int", 520)]), ("call", "price", [("var", "free"), ("int", 520)])]:
    try: t, elab = check(G, e); print("static ok:", src(elab), ":", t)
    except TypeError as err: print("static error:", err); continue
    for order in (2, "2"):
        try: print(f"   order = {order!r} →", run({"price": lambda q, u: q * u, "order": order}, elab))
        except RuntimeError as err: print(f"   order = {order!r} →", err)

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

Int ~ ? : True | ? ~ Bool : True | Int ~ Bool : False | (?) -> Int ~ (Str) -> Int : True
static ok: price(⟨Int ⇐ ?⟩order, 520) : Int
   order = 2 → 1040
   order = '2' → cast failed: expected Int, found Str (blame: argument 1 of price)
static error: type mismatch: expected Int, found Bool

প্রথম লাইনে consistency-র তিনটি গুণ একসঙ্গে: Int ~ ? আর ? ~ Bool সত্য, অথচ Int ~ Bool মিথ্যা (transitive নয়), আর function type-এর ভেতরে ? থাকলে C-Fn অংশ ধরে মেলায়। দ্বিতীয় লাইনে checker-এর ফল: আসল expression নয়, cast বসানো expression, যাকে বলে elaboration বা cast insertion; compiler পরের ধাপে এটিই চালায়। একই cast-সহ program দুবার চলে: order = 2 হলে 1040, order = '2' হলে cast থামায়, আর blame-এর লেবেল বলে কোন সীমানায়। শেষ লাইন দেখায়, যেখানে ? নেই সেখানে পুরোনো বার্তাটিই আসে, পর্ব ৩৪-এর reference-এর type mismatch: expected Int, found Bool-এর মতোই।

৩ · বাস্তবের gradual typing — any, unknown আর mypy

TypeScript (২০১২) আর Python-এর type hint (PEP 484, Python 3.5, ২০১৫) gradual typing-এর ধারণা নিয়েছে, কিন্তু একটি বড় অংশ বাদ দিয়ে: চলার সময় cast নেই। দুটিতেই type যাচাইয়ের পরে মুছে যায় (type erasure), তাই ?-এর প্রতিশ্রুতি কেউ পরীক্ষা করে না। এই হালকা রূপকে প্রায়ই optional typing বলা হয়। TypeScript-এর নকশা-লক্ষ্যের দলিলে “sound বা প্রমাণযোগ্যভাবে সঠিক type system” স্পষ্টভাবে অ-লক্ষ্য হিসেবে লেখা আছে: সঠিকতা আর কাজের গতির মধ্যে ভারসাম্যই লক্ষ্য। পর্ব ৩৮-এ (Type soundness) এই ফাঁকের আনুষ্ঠানিক দিক দেখবেন।

TypeScript-এ ?-এর দুটি রূপ। any হুবহু Siek–Taha-র ?: সবকিছুর সঙ্গে দুই দিকেই সংগত, আর এর ওপর যেকোনো কাজ চলে। unknown (TypeScript 3.0, ২০১৮) এক দিকে ঢিলে, অন্য দিকে কঠোর: যেকোনো মান তাতে রাখা যায়, কিন্তু যাচাই করে type সরু না করা পর্যন্ত (narrowing) তার ওপর প্রায় কোনো কাজ চলে না। লেখকের lab-এ বাজারঘরের একটি অর্ডার, যার JSON-এ ভুল করে qty লেখা হয়েছে "2":

// বাজারঘর: বাইরের JSON থেকে আসা অর্ডার
const body = '{"qty": "2", "unit": 520}';
function loadAny(): any { return JSON.parse(body); }
function loadUnknown(): unknown { return JSON.parse(body); }

const a = loadAny();
const t1: number = a.qty * a.unit;          // any: কোনো যাচাই নেই
const fee: number = a.delivery.fee;         // any: এটিও পার হয়
const u = loadUnknown();
const t2: number = u.qty * u.unit;          // unknown: আগে যাচাই চাই
if (typeof u === "object" && u !== null && "qty" in u && typeof u.qty === "number") {
  const t3: number = u.qty * 520;           // narrowing-এর পরে ঠিক
}
console.log(t1, fee, t2);

সত্যিকারের run, TypeScript 5.9.2, tsc --strict --noEmit --target es2022 order.ts:

order.ts(10,20): error TS18046: 'u' is of type 'unknown'.
order.ts(10,28): error TS18046: 'u' is of type 'unknown'.

দুটি error-ই লাইন ১০-এ, unknown-এর ওপর। লাইন ৭ আর ৮ পুরো নীরব, যদিও লাইন ৮-এ delivery নামের কোনো ঘরই JSON-এ নেই। আর লাইন ১২-তে typeof u.qty === "number" যাচাইয়ের পরে একই u.qty গৃহীত: narrowing একটি ছোট, স্থানীয় cast-এর মতো কাজ করে, যা লেখক নিজে লেখেন। এবার শুধু any-এর অংশটি compile করে চালানো যাক। tsc যে JavaScript বানায়, তাতে type-এর কোনো চিহ্ন নেই; নিচের block সেই কোড, শুধু ভাঙার লাইনটি try-তে মোড়ানো, আর তার নিচে একটি হাতে-লেখা সীমানা-cast, যা sound gradual typing-এর ভাবনা দেখায়:

// tsc 5.9.2-এর বানানো JavaScript (type মুছে গেছে), শুধু ভাঙার লাইনটি try-তে মোড়ানো
const body = '{"qty": "2", "unit": 520}';
function loadAny() { return JSON.parse(body); }
const a = loadAny();
const t1 = a.qty * a.unit;                 // "2" * 520: JavaScript নিজেই সংখ্যা বানায়
console.log("t1 =", t1, typeof a.qty);
try { const fee = a.delivery.fee; console.log("fee =", fee); }
catch (e) { console.log("গভীরে ভাঙল →", e.constructor.name + ":", e.message); }

// Sound gradual typing-এর ধাঁচ: অজানা জগৎ থেকে type-এর জগতে ঢোকার সীমানায় যাচাই
function cast(v, shape, label) {
  for (const [k, t] of Object.entries(shape))
    if (typeof v?.[k] !== t)
      throw new TypeError(`cast failed at ${label}: ${k} expected ${t}, found ${typeof v?.[k]}`);
  return v;
}
for (const text of ['{"qty": 2, "unit": 520}', body]) {
  try {
    const o = cast(JSON.parse(text), { qty: "number", unit: "number" }, "JSON.parse");
    console.log("সীমানা পার →", o.qty * o.unit);
  } catch (e) { console.log("সীমানায় ধরা পড়ল →", e.message); }
}

আসল আউটপুট (ব্রাউজারের JavaScript; Node 24-এও হুবহু একই):

t1 = 1040 string
গভীরে ভাঙল → TypeError: Cannot read properties of undefined (reading 'fee')
সীমানা পার → 1040
সীমানায় ধরা পড়ল → cast failed at JSON.parse: qty expected number, found string

প্রথম লাইন সবচেয়ে বিপজ্জনক: কোনো ভুল ধরা পড়েনি। JavaScript নিজেই "2" * 520-কে 1040 বানিয়েছে, তাই হিসাব ঠিক দেখায়, যদিও typeof a.qty বলছে string. দ্বিতীয় লাইনে ভুল ধরা পড়ে অনেক গভীরে, ভুলের উৎস থেকে দূরে; বার্তার ভাষা engine-নির্ভর (এখানে V8-এর)। নিচের অংশে সীমানায় যাচাই: সঠিক JSON পার হয়ে একই 1040 দেয়, আর ভুল JSON ঠিক JSON.parse-এর পরে থামে, কোন ঘর কেন, তা বলে। Typed Racket (Tobin-Hochstadt আর Felleisen, ২০০৬–২০০৮) এই কাজটি নিজে থেকে করে: type-লেখা আর type-হীন module-এর সীমানায় contract বসায়। লাভ নিশ্চয়তা, দাম গতি; ২০১৬ সালে Takikawa ও সহলেখকেরা “Is Sound Gradual Typing Dead?” প্রবন্ধে দেখান, কিছু মিশ্র অবস্থায় এই সীমানা-যাচাইয়ের খরচ খুব বড় হতে পারে।

Python-এও একই ছবি। typing.Any (Python কোর্সের পর্ব ৪০) consistency মানে, আর CPython চলার সময় hint যাচাই করে না। লেখকের lab-এ mypy 2.4.1 (MIT লাইসেন্স; কোনো telemetry নেই, চালানোর পর মুছে ফেলা হয়েছে) দিয়ে সত্যিকারের run:

# বাজারঘর: type hint আর Any
import json
from typing import Any

def price(qty: int, unit: int) -> int:
    return qty * unit + 60

def load() -> Any:
    return json.loads('{"qty": "2"}')

order = load()
print(price(order["qty"], 520))   # Any: mypy চুপ
print(price("2", 520))            # str: mypy ধরে
$ mypy order.py
order.py:13: error: Argument 1 to "price" has incompatible type "str"; expected "int"  [arg-type]
Found 1 error in 1 file (checked 1 source file)

$ python order.py        # CPython 3.14.4
Traceback (most recent call last):
  File "order.py", line 12, in <module>
    print(price(order["qty"], 520))   # Any: mypy চুপ
          ~~~~~^^^^^^^^^^^^^^^^^^^
  File "order.py", line 6, in price
    return qty * unit + 60
           ~~~~~~~~~~~^~~~
TypeError: can only concatenate str (not "int") to str

mypy লাইন ১৩-এর স্পষ্ট ভুল ধরেছে, কিন্তু লাইন ১২ নীরবে ছেড়ে দিয়েছে, কারণ order["qty"]-এর type Any, আর Any ~ int. চালালে ভাঙে লাইন ১২-ই, কিন্তু ভুল ধরা পড়ে price-এর ভেতরে (লাইন ৬), সেই জায়গায় যার type পুরোপুরি ঠিক লেখা। Blame থাকলে দোষ যেত লাইন ১২-এর সীমানায়; type মুছে ফেলায় দোষ গিয়ে পড়েছে নির্দোষ function-এর ঘাড়ে। mypy-র কিছু বাড়তি flag Any-কে চোখে আনে: একই ধাঁচের ছোট ফাইলে --warn-return-any দিলে সত্যিকারের run-এ আসে Returning Any from function declared to return "int" [no-any-return].

৪ · Linear আর affine type — ঠিক একবার, নাকি সর্বোচ্চ একবার

ঈদে বাজারঘর প্রতিটি গ্রাহককে একটি ছাড়ের ভাউচার দেয়: "EID-50". ভাউচার একবার ব্যবহার হলে শেষ; দ্বিতীয়বার দেখালে কাউন্টারে আটকানো হয়। সাধারণ type এই নিয়ম জানে না। Haat v1-এ fn redeem(code: Str, total: Int) লিখে একই ভাউচার দুবার পাঠালে reference সত্যিকারের run-এ নির্বিকারে দুবারই ছাপে EID-50 used, কারণ v1-এ Str একটি সাধারণ মান, যত ইচ্ছা কপি করা যায়।

পর্ব ৩৪-এর context Γ-কে নিয়মের ভাষায় দুটি স্বাধীনতা দেওয়া আছে, যা কোথাও আলাদা করে লেখা হয়নি। Weakening: Γ-তে একটি নাম থাকলেও তা ব্যবহার না করা চলে। Contraction: একটি নাম যতবার ইচ্ছা ব্যবহার করা চলে। এগুলোকে বলে structural rule. এদের একটি বা দুটি সরিয়ে দিলে পাওয়া যায় substructural type system:

রূপWeakening (না ব্যবহার)Contraction (বারবার)মানে
সাধারণ (unrestricted)আছেআছেযতবার ইচ্ছা, ০ বারও
Affineআছেনেইসর্বোচ্চ একবার
Relevantনেইআছেঅন্তত একবার
Linearনেইনেইঠিক একবার

ধারণাটির শিকড় যুক্তিবিদ্যায়: Jean-Yves Girard ১৯৮৭ সালে linear logic প্রকাশ করেন, যেখানে অনুমান “খরচ হয়”, যেমন একটি টাকা একবারই খরচ করা যায়। Philip Wadler-এর ১৯৯০ সালের “Linear types can change the world!” দেখায় এই ধারণা দিয়ে program-এ নিরাপদভাবে জায়গায় বদল (in-place update) করা যায়: পুরোনো মানটির আর কেউ নেই, তাই কপি না করে সরাসরি বদলালেও কেউ টের পায় না। Typing rule-এ বদলটি ছোট: context ভাগ হয়ে যায়। T-Call-এ সাধারণ রূপে প্রতিটি premise একই Γ পায়; linear রূপে Γ টুকরো হয়ে প্রতিটি argument-এর কাছে আলাদা অংশ যায়, আর একই linear নাম দুই টুকরোয় থাকতে পারে না।

বাস্তব checker এই ভাগাভাগি সাধারণত অন্যভাবে করে: সে বাঁ থেকে ডানে পড়ে আর একটি তালিকা রাখে, কোন মান এর মধ্যেই “move” হয়ে গেছে, অর্থাৎ অন্য কারও হাতে চলে গেছে। Use-after-move মানে move হওয়া নাম আবার ব্যবহার। Haat-এর বর্ধিত রূপে নিয়ম ধরুন এমন: Str-এর মান function-এর argument হলে বা আরেকটি let-এ গেলে move হয়; print শুধু পড়ে (Rust-এর ভাষায় ধার, borrow); Int আগের মতো কপি হয়।

1let voucher: Str = "EID-50";2let total: Int = 996;3print(voucher);4redeem(voucher, total);5print(total);6print(voucher);7// শেষ
Checker-এর অবস্থা
Γ
Move হয়েছে
ব্যবহার
  1. নতুন affine মান। voucher : Str, আর এই বর্ধিত রূপে Str affine. Move-এর তালিকা ফাঁকা।
  2. সাধারণ মান। total : Int. Int-এ কোনো বাধা নেই (unrestricted), তাই যতবার ইচ্ছা ব্যবহার আর কপি চলে।
  3. পড়া, move নয়। print(voucher) মান দেখায়, কারও হাতে দেয় না। তালিকা বদলায় না; এটি Rust-এর ধারের (borrow) মতো।
  4. Move. redeem ভাউচারটি নিয়ে নেয়: voucher এখন move-এর তালিকায়। total-ও argument, কিন্তু Int বলে কপি যায়, তালিকায় ওঠে না।
  5. Int আবার। print(total): total কখনো move হয় না, কোনো সমস্যা নেই।
  6. Use-after-move. print(voucher) পড়তে চায় এমন একটি মান, যা লাইন ৪-এ হাতছাড়া হয়েছে। Checker program চালায় না, শুধু তালিকা দেখে বলে: 6: error: use of moved value 'voucher'.
  7. Linear-এর বাড়তি দাবি। Linear নিয়মে শেষেও একটি পরীক্ষা: প্রতিটি linear মান ঠিক একবার move হয়েছে কি না। এই program-এ voucher move হয়েছে, তাই linear-এও একই একটি error. লাইন ৪ মুছে দিলে affine খুশি, কিন্তু linear বলে end: error: linear value 'voucher' is never used. দুটি ফলই নিচের checker-এ চালিয়ে মেলানো।

নিচের block এই checker, affine আর linear দুই mode-এ। if হলে দুই শাখা আলাদা করে যাচাই হয়, আর যেকোনো শাখায় move হলে পরে মানটি “হয়তো move হয়েছে”, তাই ব্যবহার নিষেধ; linear mode-এ দুই শাখায় আলাদা move নিজেই ভুল। while-এর দেহ দুবার যাচাই হয়, যাতে দ্বিতীয় round আগের round-এর move দেখতে পায়।

# Affine আর linear: Str মান move হয় — Haat-এর বর্ধিত রূপের ছোট checker
def uses(e, how):                     # ("var", x) → [(how, x)]; call-এর argument সবসময় move
    if e[0] == "var": return [(how, e[1])]
    return [u for a in e[2] for u in uses(a, "move")] if e[0] == "call" else []
def block(ss, ty, moved, errs, mode):
    for s in ss:
        k, line = s[0], s[1]
        if k == "if":                 # ("if", line, then, else): দুই শাখা আলাদা করে
            a, b = (block(br, ty, set(moved), errs, mode) for br in s[2:])
            if mode == "linear" and a != b: errs.append(f"{line}: error: '{min(a ^ b)}' is moved in only one branch")
            moved = a | b             # যেকোনো শাখায় move = হয়তো move, আর ব্যবহার নিষেধ
        elif k == "while":            # দুই round: দ্বিতীয়বার আগের round-এর move দেখা যায়
            moved = block(s[2], ty, block(s[2], ty, set(moved), errs, mode), errs, mode)
        else:                         # ("let", line, x, T, e)  ("print", line, e)  ("expr", line, e)
            for how, x in uses(s[4] if k == "let" else s[2], "move" if k == "let" else "read"):
                if x in moved: errs.append(f"{line}: error: use of moved value '{x}'")
                elif how == "move" and ty[x] == "Str": moved.add(x)
            if k == "let": ty[s[2]] = s[3]
    return moved
def check(prog, mode):
    ty, errs = {}, []
    moved = block(prog, ty, set(), errs, mode)
    if mode == "linear":              # linear: প্রতিটি Str ঠিক একবার move হতেই হবে
        errs += [f"end: error: linear value '{x}' is never used" for x in ty if ty[x] == "Str" and x not in moved]
    return list(dict.fromkeys(errs)) or ["ok"]
V, S = (lambda x: ("var", x)), ("str", "EID-50")
redeem = lambda *a: ("expr", a[0], ("call", "redeem", [V(x) for x in a[1:]]))
P = {"move-then-use": [("let", 1, "voucher", "Str", S), ("let", 2, "total", "Int", ("int", 996)),
                       ("print", 3, V("voucher")), redeem(4, "voucher", "total"),
                       ("print", 5, V("total")), ("print", 6, V("voucher"))],
     "one-branch": [("let", 1, "voucher", "Str", S), ("if", 2, [redeem(2, "voucher")], [("print", 2, V("voucher"))])],
     "loop": [("let", 1, "voucher", "Str", S), ("while", 2, [redeem(3, "voucher")])],
     "unused": [("let", 1, "voucher", "Str", S), ("print", 2, ("str", "done"))]}
for name, prog in P.items():
    print(f"{name:14} affine: {'; '.join(check(prog, 'affine'))}\n{'':14} linear: {'; '.join(check(prog, 'linear'))}")

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

move-then-use  affine: 6: error: use of moved value 'voucher'
               linear: 6: error: use of moved value 'voucher'
one-branch     affine: ok
               linear: 2: error: 'voucher' is moved in only one branch
loop           affine: 3: error: use of moved value 'voucher'
               linear: 3: error: use of moved value 'voucher'
unused         affine: ok
               linear: end: error: linear value 'voucher' is never used

চারটি program, দুই নিয়ম। move-then-use stepper-এর program, দুই নিয়মেই লাইন ৬. one-branch-এ এক শাখা move করে, অন্যটি শুধু পড়ে; পরে কেউ ব্যবহার করে না বলে affine খুশি, কিন্তু linear বলে “এক শাখায় খরচ, অন্য শাখায় নয়”, কারণ একটি পথে ভাউচারটি অব্যবহৃত থেকে যায়। loop-এ ভুলটি একটি লাইনে, কিন্তু শুধু দ্বিতীয় round-এ ধরা পড়ে: প্রথমবার move বৈধ, দ্বিতীয়বার একই মান আর নেই। unused-এ পার্থক্যটি সবচেয়ে পরিষ্কার: affine ভাউচার ফেলে রাখা চলে, linear-এ চলে না।

Rust: affine type বাস্তবে

Rust (১.০, ২০১৫) এই ধারণার সবচেয়ে পরিচিত বাস্তব রূপ। Rust-এর String কপিযোগ্য নয়: let w = v; বা function-এ পাঠালে মান move হয়, আর পরে v ব্যবহার করলে compiler E0382 error দেয় (“use of moved value” বা “borrow of moved value” ধাঁচের বার্তা)। i32-এর মতো type Copy trait-এর, তাই সাধারণ নিয়মে চলে, ঠিক ওপরের Int-এর মতো। মান ব্যবহার না করে ফেলে দেওয়া চলে, তাই Rust affine, linear নয়; ভাবনার প্রশ্ন ২-এ এর কারণ আছে।

fn redeem(code: String) { println!("{code} used"); }

fn main() {
    let voucher = String::from("EID-50");
    redeem(voucher);          // move: voucher-এর মালিকানা redeem-এর কাছে
    redeem(voucher);          // error[E0382]: আগেই move হয়ে গেছে
}

উদাহরণ, এই পর্বের জন্য চালানো হয়নি; error-এর নম্বর E0382 Rust-এর error index-এ “a variable was used after its contents have been moved elsewhere” অর্থে লেখা। Rust-এ এর সঙ্গে আছে ownership (প্রতিটি মানের একজন মালিক, মালিকের scope শেষে memory ফেরত) আর borrow checker (ধার করা reference মালিকের চেয়ে বেশি দিন বাঁচবে না)। এগুলোর পূর্ণ আলোচনা পর্ব ৭৬-এ (Memory safety আর ownership — Rust-এর borrow checker); এখানে শুধু মূল কথা: GC ছাড়া memory safety-র একটি বড় অংশ এই affine নিয়মের ফল। অন্য ভাষাতেও ধারণাটি এসেছে: Clean ভাষার uniqueness type (১৯৯০-এর দশক), আর GHC 9.0 (২০২১) থেকে Haskell-এর LinearTypes extension, যার ভিত্তি ২০১৮ সালের “Linear Haskell” গবেষণাপত্র।

৫ · Dependent type — মান থেকে type

এখন পর্যন্ত type আর মান দুই আলাদা জগৎ: Int একটি type, 3 একটি মান, আর type-এর ভেতরে কোনো মান বসে না। Dependent type এই দেয়াল ভাঙে: type একটি মানের ওপর নির্ভর করতে পারে। সবচেয়ে পরিচিত উদাহরণ Vec n: “ঠিক n-টি উপাদানের তালিকা”, যেখানে n একটি সংখ্যা। বাজারঘরের ডেলিভারি ভ্যানের মতো ভাবুন, যার কাগজে লেখা “ভেতরে ঠিক ৫টি বাক্স”। খালি ভ্যান থেকে বাক্স নামানোর আদেশ কাগজ দেখেই বাতিল করা যায়, দরজা খোলার আগেই।

Function-এর type তখন argument-এর মান উল্লেখ করতে পারে:

  • empty : Vec 0
  • cons : (Int, Vec n) -> Vec (n + 1) — একটি যোগ করলে length এক বাড়ে
  • append : (Vec n, Vec m) -> Vec (n + m) — দুটি জোড়া দিলে length যোগ হয়
  • head : Vec (n + 1) -> Int আর tail : Vec (n + 1) -> Vec n — শুধু অন্তত একটি উপাদান থাকলে

এখানে n আর m type-এর ভেতরের চলক, যারা সংখ্যা ধরে। Checker-কে এখন সংখ্যার হিসাবও করতে হয়: head-এর argument-এর length কি “কিছু + 1” আকারে লেখা যায়? অজানা n-এর ক্ষেত্রে n + 1 যায়, কিন্তু শুধু n যায় না, কারণ n = 0 হতে পারে। নিচের stepper-এ xs : Vec n, যেখানে n অজানা (ধরুন কোনো ফাইল থেকে পড়া তালিকা)।

1xs : Vec n   // n অজানা2five = cons(5, empty)3head(append(xs, five))4head(tail(append(xs, five)))5// xs : Vec 3 হলে?
Checker-এর হিসাব
Sub-expression
Type
শর্ত
  1. প্রতীকী length. xs-এর length জানা নেই, তাই type-এ একটি প্রতীক: Vec n. Checker n-এর মান জানে না, জানে শুধু n ≥ 0.
  2. ধ্রুবক length. empty : Vec 0, আর cons-এর type বলে length এক বাড়ে: five : Vec 1. এখানে সব সংখ্যাই জানা।
  3. Length-এর যোগ। append-এর type Vec (n + m), এখানে m = 1, তাই append(xs, five) : Vec (n + 1). Checker সংখ্যা যোগ করেছে, প্রতীক রেখে দিয়েছে।
  4. প্রমাণ সহজ। head চায় Vec (k + 1) কোনো k-এর জন্য। n + 1 = k + 1, k = n নিলেই হয়। তাই লাইন ৩ গৃহীত, ফল Int. xs খালি হলেও তালিকায় অন্তত five-এর একটি উপাদান আছে।
  5. এক কমল। লাইন ৪-এ আগে tail: Vec (n + 1) থেকে এক বাদ, ফল Vec n.
  6. প্রমাণ অসম্ভব। এবার head পায় Vec n, আর চায় n = k + 1, অর্থাৎ n ≥ 1. n অজানা, 0 হতে পারে, তাই checker প্রমাণ করতে পারে না: head: ✗ cannot prove length n ≥ 1. xs খালি হলে এই program সত্যিই চলার সময় ভাঙত।
  7. Type মানের ওপর নির্ভর করে। একই লাইন ৪, কিন্তু xs : Vec 3 হলে append দেয় Vec 4, tail দেয় Vec 3 = Vec (2 + 1), আর head গৃহীত। একই কোড, শুধু একটি সংখ্যা বদলে type-এর রায় বদলেছে: এটিই “dependent”. সব ধাপ অংশ ৬-এর শেষের block-এ চালিয়ে মেলানো।

বাস্তব dependent ভাষায় Vec লেখা হয় এমনভাবে (Idris-ধাঁচের উদাহরণ, চালানো হয়নি):

data Vect : Nat -> Type -> Type where
  Nil  : Vect 0 a
  (::) : a -> Vect n a -> Vect (S n) a

head : Vect (S n) a -> a       -- Nil-এর ক্ষেত্র লেখারই দরকার নেই
head (x :: xs) = x

লক্ষ করুন head-এ Nil-এর কোনো শাখা নেই, তবু pattern match সম্পূর্ণ: type-ই বলে দেয় খালি তালিকা এখানে আসতে পারে না। পর্ব ২৪-এর (Algebraic data type) exhaustiveness check এখানে length-এর তথ্য কাজে লাগায়।

Curry–Howard: type একটি দাবি, program তার প্রমাণ

Dependent type-এর আসল শক্তি আসে একটি পুরোনো পর্যবেক্ষণ থেকে, যার নাম Curry–Howard correspondence (Haskell Curry-র ১৯৩০–৫০-এর দশকের কাজ, আর William Howard-এর ১৯৬৯ সালের পাণ্ডুলিপি, প্রকাশ ১৯৮০): type-কে একটি গাণিতিক দাবি হিসেবে, আর সেই type-এর মানকে দাবির প্রমাণ হিসেবে পড়া যায়। (A, B) -> C মানে “A আর B থেকে C”, আর এমন একটি function লেখা মানে সেই যুক্তি দেখানো। Dependent type থাকলে দাবিতে মানও আসে: “প্রতিটি n-এর জন্য, n + 0 = n” একটি type, আর তার মান একটি প্রমাণ, যা checker যাচাই করে।

এই ভাবনা থেকে এসেছে proof assistant: Per Martin-Löf-এর ১৯৭০-এর দশকের type theory-র ধারায় Coq (১৯৮৯-এর দিকে প্রথম প্রকাশ; ২০২৫ সালে নাম বদলে Rocq), Agda, Lean (Leonardo de Moura, ২০১৩ থেকে) আর Idris (Edwin Brady). দাম বড়: type checking-এর জন্য checker-কে type-এর ভেতরের expression মূল্যায়ন করতে হয়। সাধারণ recursion থাকলে সেই মূল্যায়ন শেষ না-ও হতে পারে, তাই এই ভাষাগুলো সাধারণত termination দাবি করে, আর অনেক প্রমাণ লেখককে নিজে লিখতে হয়। গণনার তত্ত্ব কোর্সের পর্ব ৫৩-এর Rice-এর theorem এখানেও খাটে: program-এর আকর্ষণীয় গুণ যন্ত্র নিজে থেকে সবসময় প্রমাণ করতে পারে না, তাই লেখককে প্রমাণ জোগাতে হয়। Verified compiler আর proof assistant নিয়ে বিস্তারিত আলোচনা পর্ব ৪৪-এ (Formal verification — Coq/Lean, verified compiler আর property) পাবেন।

৬ · Refinement type — type-এ শর্ত, যাচাই করে solver

Dependent type শক্তিশালী, কিন্তু প্রতিদিনের কোডের জন্য ভারী। মাঝামাঝি একটি পথ refinement type: একটি সাধারণ type, সঙ্গে একটি যৌক্তিক শর্ত। লেখা হয় {v: Int ∣ v ≠ 0}, পড়ুন “এমন Int v, যেখানে v শূন্য নয়”। Haat-এর /-এর type তখন হতে পারত (Int, {v: Int ∣ v ≠ 0}) -> Int. মনে করুন, Haat-এ var stock = 0; print(996 / stock); type-এর দিক থেকে নিখুঁত, আর reference সত্যিকারের run-এ বলে 2:11: runtime error: division by zero. Spec decision ২৬ অনুযায়ী এটি একটি runtime error, type-এর নিশ্চয়তার বাইরে। Refinement type এই ভুলকে চালানোর আগে আনতে পারত।

Refinement-এর মধ্যে সম্পর্কটি subtyping, আর তার নিয়ম একটি যৌক্তিক implication:

∀v. p(v) ⇒ q(v)
{v: Int ∣ p} <: {v: Int ∣ q}
(S-Refine)

অর্থাৎ qty-এর type যদি {v: Int ∣ 1 ≤ v ≤ 100} হয়, তাহলে 996 / qty নিরাপদ, কারণ 1 ≤ v ≤ 100 ⇒ v ≠ 0. এই implication কে প্রমাণ করবে? Refinement-এর শর্তগুলো ইচ্ছা করে একটি সরল যুক্তির ভাষায় সীমিত রাখা হয় (যেমন পূর্ণসংখ্যার রৈখিক সম্পর্ক), যাতে একটি SMT solver (যেমন Z3) নিজে থেকেই উত্তর দিতে পারে। এটিই dependent type থেকে বড় পার্থক্য: লেখক শর্ত লেখেন, প্রমাণ লেখেন না।

ইতিহাস ছোট করে: Tim Freeman আর Frank Pfenning ১৯৯১ সালে ML-এর জন্য “refinement types” নাম দেন; Hongwei Xi আর Pfenning ১৯৯৮ সালে Dependent ML-এ সীমিত dependent type দিয়ে array-র সীমা যাচাই চালানোর আগে সরানোর পথ দেখান; Rondon, Kawaguchi আর Jhala ২০০৮ সালে “Liquid Types” দিয়ে শর্তের বড় অংশ নিজে থেকে অনুমান করার পদ্ধতি দেন, আর তার ওপর Liquid Haskell (২০১৪ সালের দিকে ICFP-তে প্রকাশিত) Haskell-এ এই যাচাই এনেছে:

{-@ type NonZero = {v:Int | v /= 0} @-}

{-@ divide :: Int -> NonZero -> Int @-}
divide :: Int -> Int -> Int
divide total k = total `div` k

{-@ perItem :: {q:Int | 1 <= q && q <= 100} -> Int @-}
perItem q = divide 996 q        -- solver প্রমাণ করে: 1 ≤ q ⇒ q ≠ 0

উদাহরণ, চালানো হয়নি: {-@ … @-}-এর ভেতরের লেখা সাধারণ Haskell compiler-এর কাছে মন্তব্য, Liquid Haskell সেগুলো পড়ে solver-কে প্রশ্ন পাঠায়। নিচের block একটি খুব ছোট সংস্করণ: solver-এর বদলে প্রতিটি expression-এর সম্ভাব্য পরিসর [lo, hi] হিসাব করে, তারপর দেখে 0 সেই পরিসরের বাইরে কি না। একই block-এর প্রথম অংশ অংশ ৫-এর Vec n checker, যা stepper-এর প্রতিটি ধাপ ছাপে।

# মান type-এর ভেতরে: Vec n (dependent) আর {v: Int | lo ≤ v ≤ hi} (refinement)
from collections import Counter
def add(a, b): return (a[0] + b[0], a[1] + b[1])     # length = (ধ্রুবক, প্রতীকী চলক): n + 1 → (1, {n: 1})
def show(n): s = " + ".join([k if v == 1 else f"{v}·{k}" for k, v in n[1].items()] + [str(n[0])] * (n[0] > 0 or not n[1])); return f"({s})" if "+" in s else s
def check(G, e, pad=""):                              # ফেরত: "Int" বা ("Vec", length)
    if e[0] in ("int", "var"):
        t = "Int" if e[0] == "int" else G[e[1]]
    else:
        f, args = e[0], [check(G, a, pad + "  ") for a in e[1:]]
        if f == "empty": t = ("Vec", (0, Counter()))
        elif f == "cons": t = ("Vec", add(args[1][1], (1, Counter())))   # (Int, Vec n) -> Vec (n + 1)
        elif f == "append": t = ("Vec", add(args[0][1], args[1][1]))     # (Vec n, Vec m) -> Vec (n + m)
        else:                                                            # head, tail: Vec (k + 1) চায়
            n = args[0][1]
            if n[0] < 1: print(f"{pad}{f}: ✗ cannot prove length {show(n)} ≥ 1"); raise TypeError(f)
            t = "Int" if f == "head" else ("Vec", (n[0] - 1, n[1]))
    print(f"{pad}{e[0] if e[0] not in ('int', 'var') else e[1]} : {t if t == 'Int' else 'Vec ' + show(t[1])}")
    return t
G = {"xs": ("Vec", (0, Counter(n=1)))}               # xs : Vec n, n অজানা
five = ("cons", ("int", 5), ("empty",))
for e in [("head", ("append", ("var", "xs"), five)), ("head", ("tail", ("append", ("var", "xs"), five)))]:
    try: check(G, e); print("→ গৃহীত\n")
    except TypeError: print("→ বাতিল\n")
def rng(G, e):                                        # refinement: মানের সম্ভাব্য পরিসর [lo, hi]
    if e[0] == "int": return (e[1], e[1])
    if e[0] == "var": return G[e[1]]
    a, b = rng(G, e[1]), rng(G, e[2])
    return (a[0] + b[0], a[1] + b[1]) if e[0] == "+" else (a[0] - b[1], a[1] - b[0])
R = {"qty": (1, 100), "stock": (0, 50)}              # qty : {v: Int | 1 ≤ v ≤ 100}
for d in [("var", "qty"), ("var", "stock"), ("+", ("var", "stock"), ("int", 1)), ("-", ("var", "qty"), ("int", 1))]:
    lo, hi = rng(R, d)                                # / চায় divisor : {v: Int | v ≠ 0}
    print(f"996 / {d[1] if d[0] == 'var' else d[1][1] + ' ' + d[0] + ' ' + str(d[2][1])}: v ∈ [{lo}, {hi}] →",
          "নিরাপদ" if lo > 0 or hi < 0 else "বাতিল: 0 হতে পারে")

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

    xs : Vec n
      5 : Int
      empty : Vec 0
    cons : Vec 1
  append : Vec (n + 1)
head : Int
→ গৃহীত

      xs : Vec n
        5 : Int
        empty : Vec 0
      cons : Vec 1
    append : Vec (n + 1)
  tail : Vec n
head: ✗ cannot prove length n ≥ 1
→ বাতিল

996 / qty: v ∈ [1, 100] → নিরাপদ
996 / stock: v ∈ [0, 50] → বাতিল: 0 হতে পারে
996 / stock + 1: v ∈ [1, 51] → নিরাপদ
996 / qty - 1: v ∈ [0, 99] → বাতিল: 0 হতে পারে

প্রথম দুটি গাছ stepper-এর লাইন ৩ আর ৪: ভেতরের দিকে সরানো লাইনগুলো sub-expression, আর প্রতিটির type-এ length-এর হিসাব। দ্বিতীয় গাছে tail পর্যন্ত সব ঠিক, ব্যর্থতা শুধু শেষ head-এ, ঠিক যেমন পর্ব ৩৪-এর derivation একটি premise-এ আটকায়। নিচের চার লাইন refinement: qty-র পরিসর [1, 100] বলে ভাগ নিরাপদ; stock 0 হতে পারে বলে বাতিল; stock + 1 কখনো 0 নয়; আর qty - 1 বাতিল, কারণ qty = 1 হলে ভাজক 0. পরিসরের হিসাব sound কিন্তু অসম্পূর্ণ: qty - qty-এর পরিসর সে বলবে [-99, 99], যদিও আসলে সবসময় 0; সত্যিকারের SMT solver এমন সম্পর্ক ধরতে পারে, তবু তারও সীমা আছে।

৭ · Effect system আর typestate — কী ঘটায়, আর কখন ডাকা যায়

সাধারণ function type (Int) -> Int বলে কী ঢোকে আর কী বের হয়, কিন্তু মাঝখানে কী ঘটে, তা বলে না: ফাইল লেখে কি না, exception ছোড়ে কি না, নেটওয়ার্কের জন্য থামে কি না। এই side effect-গুলো type-এ লেখার পদ্ধতি effect system. John Lucassen আর David Gifford ১৯৮৮ সালে “Polymorphic effect systems” গবেষণাপত্রে ধারণাটি আনুষ্ঠানিক করেন: judgment-এ type-এর পাশে একটি effect-এর সেট, Γ ⊢ e : τ ! ε, পড়ুন “e-এর type τ, আর চলতে গিয়ে সে ε-এর effect ঘটাতে পারে”। নিয়ম effect-গুলো যোগ করে: কোনো function-এর দেহে যা ঘটে, তার ডাকেও তা ঘটে।

আপনি এর দুটি বাস্তব রূপ আগেই দেখেছেন, হয়তো এই নামে চেনেননি:

  • Java-র checked exception (পর্ব ২৮): throws IOException একটি effect-এর ঘোষণা। যে method এটি ডাকে, তাকে হয় ধরতে হয়, নয়তো নিজেও ঘোষণা করতে হয়: effect ডাকের শিকল ধরে ওপরে ওঠে। দুর্বলতাও এখান থেকে: java.util.function-এর interface-গুলো কোনো checked exception ঘোষণা করে না, তাই lambda-র ভেতর থেকে IOException ছোড়া যায় না; effect-এর ওপর polymorphism নেই।
  • async-এর রঙ (পর্ব ৩১): function coloring আসলে একটি effect: “এই function থামতে পারে”। async শব্দটি effect-এর ঘোষণা, আর রঙ ছড়িয়ে পড়ার নিয়মটি effect যোগ হওয়ার নিয়ম।

গবেষণার ভাষায় এর পরের ধাপ effect polymorphism: “এই map ঠিক সেই effect ঘটায়, যা তার হাতে দেওয়া function ঘটায়”। Daan Leijen-এর Koka ভাষা (২০১৪ সালের গবেষণাপত্র থেকে) প্রতিটি function-এর type-এ effect-এর সারি রাখে আর এমন polymorphism দেয়। Algebraic effect আর handler (Plotkin আর Pretnar, ২০০৯) exception, generator আর async-কে একটি সাধারণ যন্ত্রে বাঁধে; OCaml 5.0 (২০২২) effect handler এনেছে, তবে effect-গুলো type-এ লেখা হয় না। আর Haskell-এ IO type দীর্ঘদিন ধরে একটি মোটা দাগের effect চিহ্ন: Int আর IO Int আলাদা type.

Typestate — অবস্থা type-এর অংশ

বাজারঘরের একটি অর্ডার চার অবস্থার মধ্য দিয়ে যায়: খসড়া → পরিশোধিত → পাঠানো → পৌঁছানো। পাঠানো অর্ডার আর বাতিল করা যায় না, আর পরিশোধের আগে পাঠানো যায় না। Typestate (Robert Strom আর Shaula Yemini, ১৯৮৬) এই অবস্থাকে type-এর অংশ বানায়: Order<Paid>-এর ship() আছে, Order<Draft>-এর নেই। প্রতিটি পরিবর্তন পুরোনো মান খেয়ে নতুন অবস্থার মান দেয়: ship(o: Order<Paid>) -> Order<Shipped>. কিন্তু পুরোনো o হাতে থেকে গেলে কেউ তাকে আবার পাঠাতে পারে! এখানেই অংশ ৪ ফিরে আসে: o affine হলে ship-এর পরে সে move হয়ে যায়, পুরোনো অবস্থার কোনো কপি থাকে না। Rust-এ typestate তাই একটি প্রচলিত নকশা-ধাঁচ: অবস্থাগুলো আলাদা struct বা generic parameter, আর পরিবর্তনের method self নিয়ে নেয়।

ধারণাType-এ যা লেখা হয়বাস্তব উদাহরণ
Checked exceptionকোন ব্যর্থতা বাইরে আসতে পারেJava throws; Swift 6-এর typed throws
async / রঙfunction থামতে পারে কি নাJavaScript, Python, Rust, C#-এর async
সাধারণ effect systemসব effect-এর সারি, polymorphism-সহKoka (গবেষণা ভাষা)
Typestateমানটি এখন কোন অবস্থায়, কোন কাজ বৈধRust-এর typestate ধাঁচ (affine move-এর সাহায্যে)

৮ · গবেষণা থেকে বাস্তবে — কে কতদূর এসেছে

প্রতিটি ধারণা গবেষণাপত্র থেকে বাস্তব ভাষায় আসতে সাধারণত দশক লেগেছে, আর প্রায় সবসময় একটি হালকা রূপে। নিচের সারণি সেই যাত্রার সারসংক্ষেপ; সাল আর নাম যেখানে উৎস ভেদে একটু আলাদা, সেখানে “দিকে” লেখা।

ধারণাগবেষণার শুরুবাস্তব ভাষায়যা ছাড় দেওয়া হয়েছে
GradualSiek–Taha ২০০৬; Typed Racket ২০০৬–০৮TypeScript, Python hint (mypy), Dart-এর পুরোনো সংস্করণচলার সময়ের cast আর blame
Linear / affineGirard ১৯৮৭; Wadler ১৯৯০Rust (affine), Haskell LinearTypes, Idris 2Rust-এ linear নয়, ফেলে দেওয়া চলে
DependentMartin-Löf, ১৯৭০-এর দশকLean, Rocq/Coq, Agda, Idris, F*সাধারণ ভাষায় নয়; লেখককে প্রমাণ লিখতে হয়
RefinementFreeman–Pfenning ১৯৯১; Liquid Types ২০০৮Liquid Haskell, F*শর্তের ভাষা সীমিত, যাতে solver পারে
EffectLucassen–Gifford ১৯৮৮; handler ২০০৯Java checked exception, async, Koka, OCaml 5 (type-হীন)বেশিরভাগ ভাষায় effect polymorphism নেই
TypestateStrom–Yemini ১৯৮৬Rust-এর নকশা-ধাঁচআলাদা বৈশিষ্ট্য নয়, generic আর move দিয়ে অনুকরণ

লক্ষ করুন শেষ কলামটি: যে রূপ বাস্তবে টিকেছে, সে প্রায় সবসময় তত্ত্বের কিছু নিশ্চয়তা ছেড়েছে, বিনিময়ে লেখকের কম পরিশ্রম, কম ধীরগতি বা পুরোনো কোডের সঙ্গে মিল পেয়েছে। কোনো উন্নত type-কে বিচার করার তিনটি প্রশ্ন তাই এক: লেখককে কী লিখতে হয়, checker কী প্রমাণ করে, আর চলার সময় কী খরচ।

আরও গভীরে। Siek, Vitousek, Cimini আর Boyland ২০১৫ সালে “gradual guarantee” নামে একটি মানদণ্ড দেন: কোনো well-typed program থেকে annotation সরিয়ে ? বসালে program তখনও গৃহীত থাকবে আর একই আচরণ করবে, শুধু কম ভুল আগে ধরা পড়বে। Idris 2 দাঁড়িয়ে আছে quantitative type theory-র ওপর (McBride ২০১৬, Atkey ২০১৮), যেখানে প্রতিটি নাম কতবার ব্যবহার হবে (০, ১ বা যতবার ইচ্ছা) type-এর অংশ, ফলে linear আর dependent type এক কাঠামোয় বসে। বাস্তব প্রভাবের একটি উদাহরণ F* ভাষায় লেখা যাচাই-করা cryptography library HACL*, যার অংশ প্রকাশিত তথ্য অনুযায়ী Firefox-এর NSS-এ ব্যবহৃত হয়েছে।

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

  • “Gradual typing-এ consistency আর equality-র পার্থক্য কী?” ? সব type-এর সঙ্গে সংগত; consistency প্রতিফলী আর প্রতিসম, কিন্তু transitive নয়।
  • “TypeScript-এ any আর unknown-এর পার্থক্য?” দুটিতেই যেকোনো মান রাখা যায়; any-র ওপর সব কাজ চলে (যাচাই বন্ধ), unknown-এ narrowing ছাড়া প্রায় কিছুই চলে না।
  • “Linear আর affine type-এর পার্থক্য?” Linear: ঠিক একবার (weakening আর contraction দুটিই নেই); affine: সর্বোচ্চ একবার (contraction নেই)। Rust affine.
  • “Dependent type দিয়ে কী যাচাই করা যায়, উদাহরণ দিন।” head : Vec (n + 1) -> a: খালি তালিকার head compile-এর আগেই বাতিল।
  • “Checked exception কি effect system?” হ্যাঁ, একটি সীমিত রূপ: effect (exception) type-এ ঘোষিত আর ডাকের শিকলে ছড়ায়, কিন্তু effect polymorphism নেই।

৯ · AI-এর যুগে উন্নত type

উন্নত type নিয়ে AI assistant-এর উত্তর প্রায়ই আত্মবিশ্বাসী আর আংশিক সঠিক, কারণ নামগুলো (linear, dependent, sound) বিভিন্ন ভাষায় বিভিন্ন অর্থে ব্যবহার হয়:

AI-এর সাধারণ ভুলকীভাবে ধরবেন
“TypeScript gradual typing, তাই any-র ভুল সীমানায় ধরা পড়ে” — অথচ TypeScript চলার সময় কিছুই যাচাই করে নাtsc-এর বানানো JavaScript পড়া আর চালানো; কোনো cast আছে কি না দেখা
“Rust-এ linear type আছে” বা “Rust মান ব্যবহারে বাধ্য করে”একটি String তৈরি করে ব্যবহার না করে compile করা; বড়জোর unused-এর সতর্কবার্তা আসে
Consistency-কে transitive ধরে যুক্তি, বা ?-কে subtyping-এর top type ভাবাInt ~ ?, ? ~ Bool, Int ~ Bool তিনটি ছোট checker-এ চালিয়ে দেখা
বানানো compiler flag, error code বা ভাষার বৈশিষ্ট্য (যেমন কোনো ভাষায় “refinement type built-in”)ভাষার নিজস্ব documentation আর release note; আসল compiler-এ চালানো
Dependent type-এর উদাহরণ যা আসলে typecheck হয় না, বা proof assistant-এর পুরোনো আর নতুন সংস্করণের syntax মেশানোনির্দিষ্ট version-এর tool-এ চালানো; না চালালে “উদাহরণ” বলে চিহ্নিত রাখা
“এই annotation যোগ করলে program নিরাপদ” — অথচ Any বা any পথে ভুল ঢুকে আছেmypy-র --warn-return-any, TypeScript-এর unknown আর narrowing দিয়ে Any-র পথ খোঁজা

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

আমি TypeScript 5.9 (--strict) আর Python 3.14 + mypy ব্যবহার করি। বাইরের API থেকে আসা JSON নিয়ে কাজ করি। ১. আমার কোডে any আর unknown কোথায় কোনটি বসানো উচিত, একটি ছোট উদাহরণে দেখাও। প্রতিটি দাবির জন্য বলো tsc ঠিক কোন error দেবে; আমি নিজে চালিয়ে মেলাব। ২. TypeScript কি চলার সময় কোনো type যাচাই করে? না করলে সীমানায় যাচাইয়ের একটি ছোট function লিখে দাও, আর বলো কোন ক্ষেত্র সেটি ধরবে না। ৩. Rust-এর move নিয়মকে affine type বলা হয় কেন, linear কেন নয়? এমন একটি উদাহরণ দাও যা compile হয় অথচ linear নিয়মে বাতিল হতো। ৪. যেখানে তুমি নিশ্চিত নও বা ভাষার version-ভেদে উত্তর বদলায়, স্পষ্ট বলো।

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

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

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

প্র ০১TypeScript ইচ্ছা করে unsound, আর চলার সময় কোনো cast বসায় না। এটি কি দুর্বলতা, নাকি সঠিক নকশা-সিদ্ধান্ত?

TypeScript-এর লক্ষ্য ছিল JavaScript-এর বিশাল প্রচলিত কোডে type আনা, কোড না ভেঙে আর গতি না কমিয়ে। Sound gradual typing নিলে প্রতিটি সীমানায়, যেখানে any থেকে type-লেখা জগতে মান ঢোকে, চলার সময় একটি পরীক্ষা বসত। একটি সংখ্যার জন্য পরীক্ষা সস্তা, কিন্তু একটি object বা function-এর জন্য নয়: object-এর প্রতিটি ঘর, আর function-এর প্রতিটি ডাকের argument আর ফল পরীক্ষা করতে হয়, তাই function-কে একটি মোড়কে (wrapper) ঢেকে রাখতে হয়। Takikawa ও সহলেখকেরা ২০১৬ সালে Typed Racket-এ type-লেখা আর type-হীন module-এর নানা মিশ্রণ মেপে দেখান, কিছু মিশ্রণে এই মোড়কের খরচ খুব বড় হয়ে যায়; প্রবন্ধের শিরোনামই ছিল “Is Sound Gradual Typing Dead?”

TypeScript-এর দল তাই অন্য পথ নিল। তাদের নকশা-লক্ষ্যের দলিলে sound type system স্পষ্টভাবে অ-লক্ষ্য, আর type মুছে ফেলা একটি প্রতিশ্রুতি: যা লেখেন, compile-এর পরে প্রায় সেই JavaScript-ই পান। ফলে কোনো runtime খরচ নেই, ছোট library সহজে বানানো যায়, আর দলের লোক ধাপে ধাপে type যোগ করতে পারে। দাম অংশ ৩-এর সত্যিকারের run-এ দেখেছেন: any দিয়ে আসা ভুল নীরবে ঢুকে গভীরে ভাঙে। এছাড়া কিছু ইচ্ছাকৃত ফাঁক আছে, যেমন method parameter-এর bivariance, যা পর্ব ৩৮-এ দেখবেন।

মাঝামাঝি পথও আছে। গবেষকেরা “transient” বা “shallow” যাচাই প্রস্তাব করেছেন, যেখানে শুধু মানের বাইরের আকার (এটি object কি না, সংখ্যা কি না) দেখা হয়, পুরো গঠন নয়; Reticulated Python এর একটি পরীক্ষা ছিল। বাস্তবে TypeScript-এর ব্যবহারকারীরা প্রায়ই নিজেরাই সীমানায় যাচাই বসান: বাইরের JSON-এর জন্য একটি schema-যাচাইয়ের library বা অংশ ৩-এর মতো একটি ছোট cast. অর্থাৎ sound gradual typing-এর কাজটি ভাষা না করে কোডের নির্দিষ্ট জায়গায় হাতে করা হয়, যেখানে ঝুঁকি সবচেয়ে বেশি।

মূল উপলব্ধি: soundness একটি গুণ, যার দাম গতি আর জটিলতায়; TypeScript সেই দাম না দিয়ে ব্যাপক ব্যবহার কিনেছে, আর ফাঁকটি পূরণ করার দায় দিয়েছে প্রোগ্রামারকে, বিশেষ করে বাইরের তথ্য ঢোকার সীমানায়।

প্র ০২Rust affine, linear নয়: একটি মান ব্যবহার না করেও ফেলে দেওয়া যায়। Linear হলে কী লাভ হতো, আর কেন Rust সেই পথে যায়নি?

Linear type একটি শক্ত প্রতিশ্রুতি দেয়: প্রতিটি মান ঠিক একবার “খরচ” হবে। ফাইল handle, database transaction বা একটি অর্ধেক-লেখা অর্ডারের মতো রিসোর্সের জন্য এটি দারুণ: ভুলে বন্ধ না করা বা commit না করা compile-এর সময়েই ধরা পড়ত। অনুশীলনের block-এর unused program ঠিক এটি দেখায়: affine নিয়মে ভাউচার পড়ে থাকা চলে, linear-এ চলে না।

Rust এই কাজটি অন্যভাবে করে: Drop. মালিকের scope শেষ হলে মানের destructor নিজে থেকে চলে, ফাইল বন্ধ হয়, memory ফেরত যায়। তাই “ভুলে ফেলে রাখা” সাধারণত নিরাপদ, আর সব মানকে linear বানালে প্রতিটি error-এর শাখায়, প্রতিটি early return-এ প্রতিটি মান হাতে করে খরচ করতে হতো, যা লেখা কঠিন করত। কিন্তু Drop কোনো প্রতিশ্রুতি নয়। ২০১৫ সালে, Rust ১.০-এর ঠিক আগে, দেখা গেল একটি API-র নিরাপত্তা destructor চলার ওপর নির্ভর করত, অথচ reference-counting-এর চক্র তৈরি করে নিরাপদ কোডেই destructor না চালিয়ে মান “হারিয়ে ফেলা” যায়। সম্প্রদায়ে এই ঘটনা “leakpocalypse” নামে পরিচিত; সমাধান হিসেবে std::mem::forget-কে নিরাপদ (safe) ঘোষণা করা হয়, আর নিয়ম দাঁড়ায়: নিরাপত্তা destructor চলার ওপর নির্ভর করতে পারবে না।

যেখানে “ব্যবহার করতেই হবে” দরকার, Rust সেখানে হালকা সরঞ্জাম দেয়: #[must_use] attribute, যা Result ফেলে দিলে সতর্কবার্তা দেয়, error নয়। গবেষণা আর অন্য ভাষায় পূর্ণ linear type আছে: Haskell-এর LinearTypes, Idris 2-এর quantity, আর Rust-এ linear type যোগের প্রস্তাব বহুবার আলোচিত হয়েছে, পুরোনো কোড আর generic-এর সঙ্গে মেলানোর জটিলতার কারণে এখনও আসেনি।

মূল উপলব্ধি: affine নিয়ম “দুবার নয়” নিশ্চিত করে memory safety দেয়, আর “একবার অবশ্যই” কাজটি ছেড়ে দেয় destructor আর সতর্কবার্তার হাতে; linear নিয়ম বেশি প্রমাণ করে, কিন্তু প্রতিটি পথে হাতে করে খরচের দাম চায়।

প্র ০৩Dependent type দিয়ে যদি “program ঠিক” প্রমাণ করা যায়, তাহলে test লেখার দরকার থাকে কি? প্রমাণিত সফটওয়্যারের বাস্তব অভিজ্ঞতা কী বলে?

সবচেয়ে বিখ্যাত উদাহরণ CompCert, Xavier Leroy আর সহকর্মীদের C compiler, যার optimization আর code generation-এর বড় অংশ Coq-এ প্রমাণিত: compile করা program source-এর মতোই আচরণ করে। ২০১১ সালে Yang, Chen, Eide আর Regehr-এর Csmith গবেষণা লক্ষ লক্ষ এলোমেলো C program দিয়ে GCC আর LLVM-এ বহু ভুল-কোড বানানোর bug খুঁজে পায়; CompCert-এ তারা যে কয়েকটি সমস্যা পায়, সেগুলো ছিল প্রমাণের বাইরের অংশে (যেমন front end), প্রমাণিত অংশে ভুল-কোডের bug তাদের পরীক্ষায় ধরা পড়েনি বলে তারা জানান। এটি প্রমাণের শক্তির একটি জোরালো সাক্ষ্য।

কিন্তু একই গল্প প্রমাণের সীমাও দেখায়। প্রমাণ শুধু ততটুকু বলে, যতটুকু spec বলে: spec-এ ভুল থাকলে প্রমাণিত program সেই ভুলটি নিখুঁতভাবে করে। প্রমাণের বাইরে থাকা অংশ (parser, linker, operating system, hardware) আলাদা ঝুঁকি। আর proof assistant-এর ভেতরের কোড নিজেও একটি program; এটি যত ছোট, তত ভরসা, তাই এই tool-গুলো একটি ছোট “kernel” রাখে, যা শেষ যাচাই করে।

খরচের প্রশ্নও আছে। CompCert বা seL4 (Isabelle-এ প্রমাণিত microkernel, ২০০৯) বানাতে বহু মানুষ-বছর লেগেছে বলে লেখকেরা জানিয়েছেন। তাই বাস্তবে একটি স্তরভেদ দেখা যায়: সবচেয়ে ঝুঁকির ছোট অংশ (cryptography, compiler-এর core, kernel) পূর্ণ প্রমাণে, বাকি কোডে refinement type বা শক্ত type, আর সবখানে test. Test বলে “এই input-গুলোতে ঠিক”, প্রমাণ বলে “সব input-এ, spec অনুযায়ী ঠিক”; spec নিজে ঠিক কি না, তা যাচাই করতে আবার test আর মানুষের চোখ লাগে।

মূল উপলব্ধি: dependent type-এর প্রমাণ test-এর চেয়ে অনেক শক্ত নিশ্চয়তা দেয়, কিন্তু শুধু spec-এর সীমার ভেতরে আর বড় খরচে; বাস্তব প্রকল্প তাই প্রমাণ, শক্ত type আর test মিলিয়ে ঝুঁকি অনুযায়ী খরচ ভাগ করে।

প্র ০৪Java-র checked exception-কে অনেকে ব্যর্থ পরীক্ষা বলেন, অথচ effect system-কে গবেষকেরা ভবিষ্যৎ ভাবেন। দুটি একই ধারণা হলে পার্থক্য কোথায়?

দুটিই একই প্রশ্নের উত্তর দেয়: “এই function কোন ব্যর্থতা বা কাজ ঘটাতে পারে?” Java-র throws সেই উত্তর type-এ লেখে, আর compiler নিশ্চিত করে কোনো checked exception নীরবে হারায় না। পর্ব ২৮-এ দেখেছেন সমস্যাগুলো: নিচের স্তরে নতুন exception যোগ হলে ওপরের সব method-এর ঘোষণা বদলাতে হয়, আর লোকে বিরক্ত হয়ে ধরে ফেলে দেয় বা সব কিছু RuntimeException-এ মুড়ে ফেলে, যা effect-এর তথ্যটাই মুছে দেয়।

সবচেয়ে বড় ফাঁকটি দেখা গেল Java 8-এর lambda আর stream-এ। list.stream().map(f)-এ map-এর type জানে না f কোন exception ছোড়ে; Function interface কোনো checked exception ঘোষণা করে না, তাই ফাইল পড়ার মতো কাজ lambda-য় লিখতে গেলে মোড়ক লাগে। Effect system-এর ভাষায় এখানে দরকার effect polymorphism: “map-এর effect আর f-এর effect একই”। Koka ঠিক এটি দেয়: function-এর type-এ effect-এর একটি সারি, যার মধ্যে একটি চলক থাকতে পারে, ঠিক যেমন generic type-এ type-চলক থাকে। তখন একই map pure function-এর সঙ্গে pure, exception-ছোড়া function-এর সঙ্গে exception-ছোড়া।

নতুন ভাষাগুলোর প্রতিক্রিয়াও শিক্ষণীয়। Rust আর Go exception-এর বদলে ব্যর্থতাকে মান হিসেবে ফেরত দেয় (Result, error মান), ফলে ব্যর্থতা সাধারণ type-এ ঢুকে যায় আর generic-এর polymorphism সেখানে স্বাভাবিকভাবে কাজ করে। Swift 6 (২০২৪) “typed throws” যোগ করেছে, যেখানে throws(MyError) লেখা যায় আর generic code সেই error type-এর ওপর polymorphic হতে পারে বলে প্রস্তাবে বলা হয়েছে। অর্থাৎ ধারণাটি ব্যর্থ নয়; ব্যর্থ ছিল polymorphism-ছাড়া, ভারী রূপটি।

মূল উপলব্ধি: checked exception একটি effect system, কিন্তু effect polymorphism ছাড়া; ঘোষণার বোঝা আর higher-order কোডে অচলতাই তার সমস্যা, আর আধুনিক ভাষা effect-কে হয় সাধারণ type-এ (Result) ঢুকিয়ে, নয় polymorphic effect দিয়ে সেই সমস্যা মেটায়।

প্র ০৫Haat-এর পরের version-এ এই পর্বের কোন উন্নত type যোগ করা সবচেয়ে কাজের হবে, আর কোনটি শেখার ভাষার জন্য ভারী?

প্রথমে দেখা যাক Haat v1-এর কোন ভুলগুলো এখনও চলার সময় আসে। Reference-এর spec decision ২৬ তিনটি runtime error-এর কথা বলে: division by zero, 'k' is not initialized yet (decision ১৮) আর stack overflow. এর মধ্যে প্রথমটি refinement type-এর সবচেয়ে সরল লক্ষ্য: / আর %-এর ভাজককে {v: Int ∣ v ≠ 0} চাইলে অংশ ৬-এর পরিসর-হিসাবই অনেক program-এ যথেষ্ট। দাম: কিছু সঠিক program বাতিল হবে (যেমন qty - qty-এর মতো ক্ষেত্র), তাই একটি “আমি জানি” পালানোর পথ (চলার সময়ের যাচাই) রাখতে হবে।

বাজারঘরের গল্পে affine type-ও স্বাভাবিক: ভাউচার, একবার-ব্যবহার্য OTP, পরিশোধের token. কিন্তু Haat-এর closure “capture by reference”, অর্থাৎ ভেতরের function বাইরের variable-এর একটি ভাগ করা বাক্স ধরে রাখে (পর্ব ১৭)। Affine মান কোনো closure ধরে রাখলে প্রশ্ন ওঠে: closure-টি কতবার ডাকা যাবে? Rust এর উত্তরে closure-কেই তিন ভাগে ভাগ করেছে (Fn, FnMut, FnOnce); শেখার ভাষার জন্য এটি একটি বড় বাড়তি অধ্যায়।

Gradual typing শেখার ভাষায় আকর্ষণীয়: নতুন শিক্ষার্থী type ছাড়া শুরু করে পরে type যোগ করতে পারতেন। কিন্তু Haat-এর দুটি back end (interpreter আর VM) দুটিতেই cast বসাতে হতো, আর blame-এর বার্তা দুই জায়গায় একই রাখতে হতো; reference-এর “interp আর VM একই আউটপুট দেয়” নামের পরীক্ষা তখন আরও কঠিন হতো। Dependent type সবচেয়ে ভারী: checker-এর ভেতরে evaluator লাগে, আর termination-এর প্রশ্ন আসে। Effect system মাঝামাঝি: Haat-এ print একমাত্র effect, তাই “pure function” চিহ্নটি সহজে যোগ করা যায়, আর পর্ব ৬৫-এর optimization (যেমন pure call-এর ফল পুনর্ব্যবহার) তাতে লাভবান হয়।

মূল উপলব্ধি: উন্নত type বাছাইয়ের প্রশ্ন “কোনটি সবচেয়ে শক্তিশালী” নয়, “কোন ভুল সবচেয়ে বেশি হয় আর কত কম দামে ধরা যায়”; Haat-এর জন্য refinement-এর হালকা রূপ আর একটি pure চিহ্ন সবচেয়ে কম দামে সবচেয়ে বেশি লাভ দেয়।

অনুশীলন

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

  1. নকশা ও বাস্তবায়ন — clone যোগ করুন: অংশ ৪-এর affine checker-এ (Haat-এর বর্ধিত রূপ) একটি built-in clone(x) যোগ করুন, যা x-কে move না করে, শুধু পড়ে, আর একটি নতুন Str দেয়। কোন এক লাইন বদলাতে হবে? তারপর তিনটি program-এর ফল affine আর linear নিয়মে বলুন: (ক) let v = "EID-50"; let w: Str = clone(v); redeem(v); redeem(w); (খ) let v = "EID-50"; redeem(v); let w: Str = clone(v); redeem(w); (গ) let v = "EID-50"; let w: Str = clone(v); redeem(v);

    uses()-এর call-এর লাইনটি: argument-এর ব্যবহার “move”-এর বদলে, callee clone হলে “read”:

        return [u for a in e[2] for u in uses(a, "read" if e[1] == "clone" else "move")] if e[0] == "call" else []

    লেখকের lab-এ বদলানো checker চালানো হয়েছে (CPython 3.14.4): (ক) affine ok, linear ok: v আর w দুটিই ঠিক একবার move. (খ) দুই নিয়মেই 3: error: use of moved value 'v': clone-ও একটি ব্যবহার, আর v লাইন ২-এ চলে গেছে। (গ) affine ok, linear end: error: linear value 'w' is never used: কপি বানিয়ে ফেলে রাখা linear-এ নিষেধ। Rust-এর .clone() ঠিক এই ভূমিকা নেয়: মালিকানা না ছেড়ে একটি নতুন মালিকানাধীন কপি, বিনিময়ে memory আর সময়ের খরচ। নকশার শিক্ষা: clone থাকলে affine নিয়ম কখনো “অসম্ভব” নয়, শুধু খরচ দৃশ্যমান হয়।

  2. ভুল যুক্তি খুঁজুন: একজন লিখলেন: “Gradual checker-এ price(free, 520) গ্রহণযোগ্য হওয়া উচিত, যেখানে free : Bool আর price : (Int, Int) -> Int. যুক্তি: (১) Bool ~ ? (C-Dyn); (২) ? ~ Int (C-Dyn); (৩) তাই Bool ~ Int; (৪) T-Call~ খাটে।” কোন ধাপ ভুল? আর লেখক যদি ইচ্ছা করে free-কে আগে ? type দেন (যেমন let f: ? = free;), তখন কী হবে?

    ধাপ ৩ ভুল: consistency transitive নয়, তাই (১) আর (২) থেকে (৩) আসে না। দুই পাশেই জানা মৌলিক type থাকলে একমাত্র নিয়ম C-Base, যা চায় দুটি হুবহু এক; Bool ≠ Int, তাই derivation নেই আর checker বলে type mismatch: expected Int, found Bool (অংশ ২-এর block-এর শেষ লাইন, সত্যিকারের run থেকে)। দ্বিতীয় প্রশ্ন: নামটির type ? করে দিলে, অর্থাৎ Γ-তে f : ? (বা block-এ G-তে free : ?), checker গ্রহণ করে আর cast বসায়। লেখকের lab-এ একই block চালিয়ে: price(⟨Int ⇐ ?⟩free, 520) : Int, আর চালালে মান False হলে cast failed: expected Int, found Bool (blame: argument 1 of price). অর্থাৎ ? দিয়ে ঘুরিয়ে মেলানো সম্ভব, কিন্তু শুধু লেখক নিজে স্পষ্টভাবে লিখলে, আর তখন ভুলটি চলার সময় সীমানায় ধরা পড়ে। Checker নিজে থেকে কখনো এই ঘুরপথ নেয় না: এটিই non-transitivity-র উদ্দেশ্য।

  3. হিসাব — length আর পরিসর: xs : Vec n, ys : Vec m ধরে নিচের তিনটির type বের করুন, অথবা বলুন কোথায় বাতিল: (ক) tail(append(cons(1, xs), ys)) (খ) head(append(xs, ys)) (গ) append(tail(cons(7, ys)), cons(1, cons(2, xs))). তারপর qty : {v ∣ 1 ≤ v ≤ 100}, stock : {v ∣ 0 ≤ v ≤ 50} ধরে পরিসর-হিসাবে stock - qty, qty + stock আর 101 - qty-এর পরিসর বলুন; কোনটি দিয়ে ভাগ করা নিরাপদ?

    অংশ ৬-এর block-এর check() আর rng() দিয়ে লেখকের lab-এ চালিয়ে মেলানো, সত্যিকারের run থেকে। (ক) cons(1, xs) : Vec (n + 1), append-এর পরে Vec (n + m + 1), আর tail-এর শর্ত পূর্ণ (ধ্রুবক অংশ ১), ফল Vec (n + m). (খ) append(xs, ys) : Vec (n + m), ধ্রুবক অংশ ০, তাই head: ✗ cannot prove length (n + m) ≥ 1: দুটি তালিকাই খালি হতে পারে। (গ) cons(7, ys) : Vec (m + 1), tail দেয় Vec m; cons(1, cons(2, xs)) : Vec (n + 2); append দেয় Vec (m + n + 2), গৃহীত (যোগ commutative, তাই প্রতীকের ক্রম গুরুত্বহীন)। পরিসর: stock - qty ∈ [-100, 49], 0 ভেতরে, তাই ভাগ বাতিল; qty + stock ∈ [1, 150], নিরাপদ; 101 - qty ∈ [1, 100], নিরাপদ। লক্ষ করুন বিয়োগে পরিসরের সীমা উল্টো দিক থেকে আসে: নিচের সীমা = 0 - 100, ওপরের = 50 - 1.

  4. প্রমাণ — consistency-র তিনটি গুণ: Haat-এর type (Int, Bool, Str, Unit, function type) আর ?-এর ওপর অংশ ২-এর C-Dyn, C-Base, C-Fn দিয়ে সংজ্ঞায়িত ~-এর জন্য প্রমাণ করুন: (ক) ~ প্রতিফলী আর প্রতিসম; (খ) S আর T-এর কোথাও ? না থাকলে S ~ T যদি এবং কেবল যদি S = T; (গ) ~ transitive নয়।

    প্রমাণ type-এর গঠনের ওপর structural induction দিয়ে (পর্ব ৩৪-এর অনন্যতার প্রমাণের মতো)।

    1. (ক) প্রতিফলী: T = ? হলে C-Dyn; T মৌলিক হলে C-Base; T = (T1, …, Tn) -> R হলে IH দিয়ে প্রতিটি Ti ~ Ti আর R ~ R, তাই C-Fn. প্রতিসম: প্রতিটি নিয়ম নিজেই প্রতিসম (C-Dyn-এ দুই দিকই লেখা, C-Base-এ দুই পাশ এক), আর C-Fn-এ IH দিয়ে প্রতিটি অংশ উল্টানো যায়।
    2. (খ) “যদি” দিক: S = T হলে (ক) থেকে S ~ T. “কেবল যদি” দিক: S ~ T-এর শেষ নিয়ম দেখি। C-Dyn হতে পারে না, কারণ কোথাও ? নেই। C-Base হলে S = T = B. C-Fn হলে দুটি function type-এর argument-সংখ্যা সমান আর প্রতিটি অংশে ? নেই, তাই IH দিয়ে Si = Ti আর R = R′, ফলে S = T.
    3. (গ) পাল্টা উদাহরণ: Int ~ ? আর ? ~ Bool (দুটিই C-Dyn), কিন্তু Int ~ Bool-এর জন্য কোনো নিয়ম খাটে না: C-Dyn-এ ? লাগে, C-Base-এ দুই পাশ সমান লাগে, C-Fn-এ function type লাগে। ∎

    (খ)-এর অর্থ গুরুত্বপূর্ণ: ?-হীন program-এ gradual checker আর পর্ব ৩৪-এর সাধারণ checker হুবহু একই রায় দেয়, তাই gradual typing পুরোনো ভাষার একটি নিরাপদ সম্প্রসারণ, ইংরেজিতে conservative extension. অংশ ২-এর block-এর প্রথম লাইন (গ)-এর পাল্টা উদাহরণটিই চালিয়ে দেখায়: Int ~ ? : True | ? ~ Bool : True | Int ~ Bool : False.

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

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

ক্রমSound gradual typing-এ order : ? দিয়ে price(order, 520) ডাকা হলো, যেখানে price : (Int, Int) -> Int. Compile থেকে চলা পর্যন্ত ঘটনাগুলো ক্রমে সাজান (▲▼ চেপে সরান)

  1. Checker order-এর type ? আর parameter-এর type Int দেখে
  2. Consistency যাচাই: ? ~ Int সত্য, তাই call গৃহীত
  3. Type সমান নয় বলে argument-এ ⟨Int ⇐ ?⟩ cast বসে
  4. চলার সময় order-এর আসল মান তৈরি হয়
  5. Cast মানটির type পরীক্ষা করে
  6. Int না হলে সীমানাতেই থামে, blame যায় অজানা দিকে

Gradual typing-এর consistency relation (~) সম্পর্কে কোন কথাটি সঠিক?

  • এটি একটি equivalence relation: প্রতিফলী, প্রতিসম আর transitive
  • ? সব type-এর সঙ্গে সংগত, কিন্তু সম্পর্কটি transitive নয়
  • ? শুধু এক দিকে মেলে: Int ~ ? সত্য, কিন্তু ? ~ Int নয়
  • ? না থাকলেও Bool ~ Int সত্য, কারণ দুটিই মৌলিক type

TypeScript 5.9-এ --strict দিয়ে নিচের কোডের কোন লাইনে tsc error দেয়? const a: any = JSON.parse(s); (লাইন ১), const u: unknown = JSON.parse(s); (লাইন ২), const x: number = a.qty * 2; (লাইন ৩), const y: number = u.qty * 2; (লাইন ৪)

  • লাইন ১
  • লাইন ২
  • লাইন ৩
  • লাইন ৪

Affine type-এর নিয়মে একটি মান সম্পর্কে কোনটি সঠিক?

  • সর্বোচ্চ একবার ব্যবহার করা যায়, ব্যবহার না করে ফেলে দেওয়াও চলে
  • ঠিক একবার ব্যবহার করতেই হবে
  • অন্তত একবার ব্যবহার করতে হবে, বারবারও চলে
  • যতবার ইচ্ছা ব্যবহার করা যায়

একটি affine checker-এ (Str মান function-এর argument হলে move হয়, print শুধু পড়ে) নিচের program-এর কোন লাইনে error? লাইন ১: let v: Str = "EID-50"; লাইন ২: print(v); লাইন ৩: redeem(v); লাইন ৪: print(v);

  • লাইন ১
  • লাইন ২
  • লাইন ৪
  • লাইন ৩

Dependent type-এ append : (Vec n, Vec m) -> Vec (n + m) আর head : Vec (k + 1) -> Int. xs : Vec n (n অজানা) হলে নিচের কোনটি checker গ্রহণ করে?

  • head(xs)
  • head(append(xs, cons(5, empty)))
  • head(tail(append(xs, cons(5, empty))))
  • head(append(xs, xs))

Java-র checked exception-কে effect system-এর দৃষ্টিতে দেখলে তার প্রধান সীমাবদ্ধতা কোনটি?

  • এটি শুধু চলার সময় যাচাই হয়
  • effect ডাকের শিকলে ছড়ায় না
  • exception type-এ লেখার কোনো উপায় নেই
  • effect polymorphism নেই, তাই higher-order কোডে (যেমন lambda) অচল

শব্দকোষ

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

মনে রাখুন

  1. চার দিক: gradual (কতটা যাচাই এখনই), linear/affine (কতবার), dependent/refinement (মানটি কী), effect/typestate (কী ঘটায়, কখন)। প্রতিটি বেশি প্রমাণ করে, বেশি তথ্য চায়।
  2. Gradual: ? type আর consistency, যা প্রতিসম কিন্তু transitive নয়; sound রূপে সীমানায় cast আর blame. TypeScript-এর any আর mypy-র Any cast ছাড়া, তাই ভুল গভীরে ভাঙে; unknown narrowing চায়।
  3. Linear আর affine: structural rule সরিয়ে “ঠিক একবার” আর “সর্বোচ্চ একবার”; checker move-এর তালিকা রাখে, শাখা আর loop-এর দ্বিতীয় round সাবধানে দেখে। Rust affine.
  4. মান type-এ: Vec n-এ length type-এর অংশ, তাই খালি তালিকার head static ভুল; refinement {v: Int ∣ v ≠ 0} শর্ত রাখে, solver implication প্রমাণ করে। Curry–Howard: type দাবি, program প্রমাণ।
  5. Effect আর typestate: checked exception আর async আসলে effect system-এর আংশিক রূপ; typestate অবস্থাকে type-এ রাখে আর affine move দিয়ে পুরোনো অবস্থা মুছে দেয়।

পরের পর্বে: পর্ব ৪০ (Operational semantics — small-step আর big-step). এবার type-এর জগৎ থেকে অর্থের জগতে: একটি Haat program ঠিক কীভাবে ধাপে ধাপে চলে, তা নিয়মে লেখা, যাতে interpreter আর VM-এর আচরণ আনুষ্ঠানিকভাবে মেলানো যায়।

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

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