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

Polymorphism — parametric, ad hoc আর subtype

Polymorphism — Parametric, Ad Hoc and Subtype

Taught in Bangla, this lesson classifies polymorphism into parametric, ad hoc and subtype forms following Strachey and Cardelli–Wegner. It covers ∀-types and parametricity, runs an overload-resolution algorithm and a record subtyping checker in in-page Python (Pyodide), proves why function parameters are contravariant and shows the TypeError when that rule is broken, explains covariant, contravariant and invariant generics, Java's covariant arrays and TypeScript's gaps, and introduces bounded polymorphism.

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

  • Strachey আর Cardelli–Wegner-এর শ্রেণিবিভাগ, আর প্রতিটি রূপ কোন ভাষায় কীভাবে দেখা যায়
  • Parametric polymorphism-এর typing rule (∀α, type application) আর parametricity-র ধারণা
  • Overload resolution-এর algorithm চালিয়ে দেখা, coercion আর type class-এর জায়গা বোঝা
  • Record আর function subtyping-এর নিয়ম formal-ভাবে, contravariance-এর প্রমাণ, আর algorithmic subtyping checker
  • Generic type-এর variance, Java আর TypeScript-এর ফাঁক, আর bounded polymorphism কেন দরকার

১ · এক নাম, অনেক type — polymorphism-এর তিন রূপ

পাড়ার মুদি দোকানের দাঁড়িপাল্লার কথা ভাবুন। চাল, ডাল, আলু, যা-ই রাখুন, পাল্লা একইভাবে ওজন করে; জিনিসটি কী, তা তার জানার দরকার নেই। দোকানের ক্যাশিয়ারের কাজ আলাদা: “দাম নিন” বললে নগদ টাকা হলে গুনে নেন, bKash হলে ফোনে মেসেজ মেলান, কার্ড হলে মেশিনে ঘষেন। একই কথা, কিন্তু প্রতিটি ক্ষেত্রে আলাদা কাজ। আর দোকানের নিয়ম “যেকোনো ক্রেতা বাকিতে নিতে পারবেন না, শুধু নিয়মিত ক্রেতা পারবেন” মানে নিয়মিত ক্রেতা আসলে একজন ক্রেতা, তার ওপর কিছু বাড়তি সুবিধা।

এই তিনটি ছবিই প্রোগ্রামিং ভাষার polymorphism: একই নাম বা একই কোড ভিন্ন ভিন্ন type-এর মানের সঙ্গে কাজ করা। দাঁড়িপাল্লা হলো parametric polymorphism, ক্যাশিয়ার হলো ad hoc polymorphism, আর নিয়মিত ক্রেতা হলো subtype polymorphism. পর্ব ০৮-এ (Object-oriented ভাষার ধারণা) subtype polymorphism, dynamic dispatch আর Liskov নীতি দেখেছেন অনানুষ্ঠানিকভাবে। এই পর্বে তিনটি রূপই নিয়ম, প্রমাণ আর সত্যিকারের checker দিয়ে দেখব।

ইতিহাস: “parametric” আর “ad hoc” শব্দ দুটি সাধারণত Christopher Strachey-র নামে উদ্ধৃত হয়, ১৯৬৭ সালে Copenhagen-এর একটি summer school-এ দেওয়া তাঁর lecture notes “Fundamental Concepts in Programming Languages” থেকে (লেখাটি বহু বছর হাতে হাতে ঘুরেছে, ছাপা হয় ২০০০ সালে)। Luca Cardelli আর Peter Wegner ১৯৮৫ সালে ACM Computing Surveys-এ “On Understanding Types, Data Abstraction, and Polymorphism” প্রবন্ধে ভাগটি বড় করেন: universal (parametric আর inclusion, অর্থাৎ subtype) বনাম ad hoc (overloading আর coercion). আজকের পাঠ্যবই মোটামুটি এই ভাগই মেনে চলে।

ছবি ৩৬.১ — Cardelli–Wegner-এর ভাগ, সঙ্গে type class

ওপরে দুই বড় ভাগ; প্রতিটির নিচে দুটি রূপ আর একটি করে চেনা উদাহরণ। ডটেড বাক্স: type class, parametric আর overloading-এর সেতু।

Polymorphism split into universal (subtype, parametric) and ad hoc (coercion, overloading), with type classes bridging parametric and overloading Polymorphism universal ad hoc subtype extends parametric Java <T> coercion int → double overloading C++ overload type class / trait ∀α. Show α ⇒ α → Str

Universal আর ad hoc-এর মূল পার্থক্য একটি প্রশ্নে: কতগুলো কোড? Universal polymorphism-এ একটিই কোড অসীম সংখ্যক type-এর সঙ্গে কাজ করে, এমনকি এমন type-এর সঙ্গেও যা কোড লেখার সময় ছিলই না। Ad hoc polymorphism-এ প্রতিটি type-এর জন্য আলাদা কোড থাকে, আর type-এর তালিকা সীমিত; নামটি শুধু একই। Haat spec v1 ইচ্ছা করেই প্রায় polymorphism-হীন: generics নেই, subtyping নেই, implicit conversion নেই। তবু একটি জায়গায় ad hoc polymorphism লুকিয়ে আছে, built-in operator-এ। Reference বাস্তবায়নে সত্যিকারের run:

print(520 + 476);          // Int + Int
print("Rina" + " Akter");  // Str + Str
print(996 == 996);
print("Rina" == "Rina");
print(true != false);

~/haat $ python haat.py run p1.haat
996
Rina Akter
true
true
true

+ একটি নামে দুটি আলাদা কাজ: Int-এ যোগ, Str-এ জোড়া। == তিনটি type-এ চলে। এটি operator overloading, ad hoc polymorphism-এর সবচেয়ে পুরোনো রূপ; FORTRAN-এর +-ও integer আর real দুটিতেই চলত। কিন্তু তালিকাটি বন্ধ: reference-এর সিদ্ধান্ত ১১ অনুযায়ী + শুধু Int, Int অথবা Str, Str; == শুধু একই type-এর Int, Bool বা Str. ব্যবহারকারী নতুন type যোগ করতে পারেন না। সত্যিকারের python haat.py check:

fn first(a: Int, b: Int) -> Int { return a; }
print(first(2, 520));
print(first("Rina", "Sumi"));
print(1040 + " taka");
print(price == price);
fn price(q: Int) -> Int { return q * 520; }

3:13: error: type mismatch: expected Int, found Str
3:21: error: type mismatch: expected Int, found Str
4:14: error: type mismatch: expected Int, found Str
5:7: error: operator '==' cannot compare values of type (Int) -> Int

লাইন ৩-এর ভুলটিই polymorphism-এর অভাবের লক্ষণ। first-এর কাজে Int-এর কিছুই লাগে না, দুটি মানের প্রথমটি ফেরত দেওয়া যেকোনো type-এ অর্থবহ। তবু Haat v1-এ Str-এর জন্য আলাদা firstStr লিখতে হয় (সত্যিকারের run-এ দুটি সংস্করণ 2 আর Rina ছাপে)। একই কোড বারবার লেখা, শুধু type বদলে: এই পুনরাবৃত্তি দূর করতেই parametric polymorphism.

২ · Parametric polymorphism — type-কে parameter বানানো

সমাধানের ভাবনাটি সহজ: মান যেমন parameter হয়, type-ও parameter হোক। first-এর type লেখা যায় ∀α. (α, α) -> α, পড়ুন “যেকোনো type α-এর জন্য, দুটি α নিয়ে একটি α ফেরত দেয়”। এখানে α (আলফা) একটি type variable, আর ∀ (“সব”) বলে এটি যেকোনো type দিয়ে বদলানো যায়। ব্যবহারের সময় α-কে একটি আসল type দিয়ে বদলানোকে বলে instantiation; [α ↦ Int] লেখা মানে “α-র জায়গায় Int বসানো”, একে বলে substitution. Java, C# আর TypeScript-এ একে বলে generics, আর α-কে লেখা হয় <T>, একটি type parameter.

Haat v1-এ এটি লেখাই যায় না। সিদ্ধান্ত ৬ অনুযায়ী Int Bool Str Unit keyword নয়, type-এর জায়গায় শুধু এই নামগুলোই চলে; তাই fn first(a: T, b: T) -> T-এ reference বলে 1:13: error: unknown type 'T'. নিচের বাক্যগঠন Haat-এর বর্ধিত রূপ, একটি প্রস্তাব, যা reference বাস্তবায়ন করে না:

fn first[T](a: T, b: T) -> T { return a; }   // Haat-এর বর্ধিত রূপ
print(first[Int](2, 520));         // T := Int
print(first[Str]("Rina", "Sumi"));  // T := Str
print(first(2, 520));              // T বের করা হবে (পর্ব ৩৫-এর inference)

Formal-ভাবে এর জন্য দুটি নতুন typing rule লাগে, যা Jean-Yves Girard (১৯৭২) আর John Reynolds (১৯৭৪) আলাদাভাবে প্রস্তাব করা System F-এর মূল নিয়ম। Γ ⊢ e : τ-এর অর্থ পর্ব ৩৩-এ দেখেছেন, আর নিয়ম ও derivation tree পর্ব ৩৪-এ (Typing rule আর type judgment): “Γ-তে লেখা নাম আর type জানা থাকলে e-এর type τ”। এখন Γ-তে type variable-ও থাকতে পারে:

Γ, α ⊢ e : τ
Γ ⊢ Λα. e : ∀α. τ
(T-TAbs)
Γ ⊢ e : ∀α. τ
Γ ⊢ e[σ] : [α ↦ σ]τ
(T-TApp)

T-TAbs (type abstraction) বলে: α-কে একটি অজানা কিন্তু স্থির type ধরে শরীরটি যাচাই করুন; পারলে পুরো জিনিসটির type ∀α. τ. Λ (বড় হাতের lambda) মানে “type নেয় এমন function”. T-TApp (type application) বলে: ∀α. τ type-এর জিনিসকে type σ দিলে ফল τ-তে α-র জায়গায় σ. তাই first[Int] : (Int, Int) -> Int, আর তারপর পরিচিত T-Call দিয়ে first[Int](2, 520) : Int. যাচাই একবার হয়, শরীরের ভেতরে; প্রতিটি ব্যবহারে শুধু substitution. পরের পর্বে (পর্ব ৩৭, Generics-এর বাস্তবায়ন) দেখবেন compiler চলার সময়ের কোড কীভাবে বানায়: একটি কোড সবার জন্য (erasure) না প্রতিটি type-এর জন্য আলাদা কপি (monomorphization).

Parametricity — type দেখেই আচরণ জানা

T-TAbs-এর একটি গভীর ফল আছে। শরীর যাচাইয়ের সময় checker α সম্পর্কে কিছুই জানে না: যোগ করা যায় না, তুলনা করা যায় না, নতুন α বানানো যায় না। তাহলে ∀α. α -> α type-এর একটি function কী করতে পারে? হাতে আছে শুধু argument-টি, আর ফেরত দিতে হবে একটি α. ফলে, side effect আর exception না থাকলে আর function থামলে, এটি argument-টিই ফেরত দিতে বাধ্য: identity function. এই ধারণার নাম parametricity; John Reynolds ১৯৮৩ সালে এর গাণিতিক ভিত্তি দেন, আর Philip Wadler ১৯৮৯ সালের “Theorems for free!” প্রবন্ধে দেখান কীভাবে শুধু type থেকে উপপাদ্য পাওয়া যায় (যেমন ∀α. [α] -> [α] type-এর যেকোনো function তালিকার উপাদান সাজাতে, বাদ দিতে বা পুনরাবৃত্তি করতে পারে, কিন্তু নতুন উপাদান বানাতে পারে না)।

কিন্তু ভাষা যদি চলার সময় type জিজ্ঞেস করতে দেয়, প্রতিশ্রুতি ভেঙে যায়। সত্যিকারের run (TypeScript 5.9.2, tsc --strict --target es2022, তারপর Node.js 24.15.0):

function sneaky<T>(x: T): T {
  if (typeof x === "number") return (x + 1) as T;
  return x;
}
console.log(sneaky(995), sneaky("Rina"), sneaky(true));

~/haat $ tsc --strict --target es2022 --outDir out param.ts    (কোনো error নেই)
~/haat $ node out/param.js
996 Rina true

Type বলছে <T>(x: T) => T, ঠিক identity-র type; কিন্তু সংখ্যা পেলে function-টি 995-কে 996 বানিয়ে দিল। দুটি ফাঁক একসাথে কাজ করেছে: typeof চলার সময় type দেখতে দেয়, আর as T checker-কে চুপ করায়। Java-র instanceof আর reflection-ও একই কাজ করে। তাই “type দেখেই আচরণ জানা” পুরোপুরি খাটে শুধু pure, reflection-হীন ভাষায় (যেমন Haskell-এর side effect-হীন অংশ, কিছু শর্তসহ)। Haat-এর বর্ধিত রূপে যদি T-এর মান চলার সময় জিজ্ঞেস করার কোনো উপায় না রাখা হয়, parametricity টিকে থাকবে।

৩ · Ad hoc polymorphism — overloading, coercion আর type class

Function overloading-এ একই নামের কয়েকটি function থাকে, parameter-এর type বা সংখ্যা আলাদা; compiler প্রতিটি ডাকের জন্য একটি বাছে। এই বাছাইয়ের নাম overload resolution. এর সঙ্গে প্রায়ই জড়িয়ে থাকে implicit conversion, যাকে Cardelli–Wegner বলেছেন coercion: C-তে 1 + 2.5 লিখলে compiler নিজে 1-কে double বানায় (পর্ব ২০-এর usual arithmetic conversions). দুটি একসাথে থাকলে প্রশ্ন জটিল হয়: একটি ডাক কয়েকটি function-এর সঙ্গে মেলে, কোনোটি হুবহু, কোনোটি রূপান্তরের পর।

প্রতিটি ভাষার নিয়ম আলাদা আর বিস্তারিত; C++-এর নিয়ম মানদণ্ডের কয়েক পৃষ্ঠা জুড়ে (implicit conversion sequence-এর ক্রম, template, reference binding). কিন্তু মূল কাঠামো প্রায় সবখানে এক। নিচে একটি খেলনা ভাষা (Haat নয়): type Int, Float আর Str, আর একটিমাত্র coercion, Int থেকে Float. প্রতিটি argument-এর একটি “খরচ”: হুবহু মিললে 0, রূপান্তর লাগলে 1, অসম্ভব হলে বাদ।

# A toy language (not Haat): types Int, Float, Str; one coercion Int -> Float
COERCE = {("Int", "Float")}               # allowed implicit conversions

def cost(arg, param):
    if arg == param: return 0             # exact match
    if (arg, param) in COERCE: return 1   # needs a coercion
    return None                           # not possible

def resolve(name, args, cands):
    viable = []
    for params in cands[name]:
        if len(params) != len(args): continue
        cs = [cost(a, p) for a, p in zip(args, params)]
        if None not in cs: viable.append((params, cs))
    if not viable: return "error: no matching overload"
    # best = at least as good in every argument as every other viable one
    best = [p for p, c in viable
            if all(all(x <= y for x, y in zip(c, d)) for _, d in viable)]
    if len(best) != 1:
        return "error: ambiguous call, candidates " + " / ".join(
            "(" + ", ".join(p) + ")" for p, _ in viable)
    return "picks (" + ", ".join(best[0]) + ")"

cands = {"total": [("Int", "Int"), ("Float", "Float"), ("Str", "Str")],
         "mix":   [("Int", "Float"), ("Float", "Int")]}
calls = [("total", ("Int", "Int")), ("total", ("Int", "Float")),
         ("total", ("Str", "Str")), ("total", ("Str", "Int")),
         ("mix", ("Int", "Float")), ("mix", ("Int", "Int"))]
for name, args in calls:
    print(f"{name}({', '.join(args)})".ljust(19), resolve(name, args, cands))

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

total(Int, Int)     picks (Int, Int)
total(Int, Float)   picks (Float, Float)
total(Str, Str)     picks (Str, Str)
total(Str, Int)     error: no matching overload
mix(Int, Float)     picks (Int, Float)
mix(Int, Int)       error: ambiguous call, candidates (Int, Float) / (Float, Int)

প্রথম লাইনে দুটি প্রার্থী সম্ভব: (Int, Int) খরচ [0, 0] আর (Float, Float) খরচ [1, 1]; প্রথমটি প্রতিটি argument-এ সমান বা ভালো, তাই বিজয়ী। চতুর্থ লাইনে Str থেকে Int-এর কোনো রূপান্তর নেই। শেষ লাইনটি C++-এর পরিচিত ambiguity-র খেলনা রূপ: দুই প্রার্থীর প্রতিটি একটি করে রূপান্তর চায়, কিন্তু আলাদা argument-এ; কেউ “সব দিকে সমান বা ভালো” নয়। “প্রতিটি argument-এ সমান বা ভালো” নিয়মটি C++-এর best viable function-এর নিয়মের সরল রূপ; আসল নিয়মে খরচ শুধু 0/1 নয়, কয়েক স্তরের।

1total(a: Int, b: Int)2total(a: Float, b: Float)3total(a: Str, b: Str)4mix(a: Int, b: Float)5mix(a: Float, b: Int)6total(1040, 2.5); mix(1040, 60);
এই মুহূর্তে
ডাক
প্রার্থী
খরচ
  1. নাম দিয়ে প্রার্থী। total(1040, 2.5)-এর argument-এর static type (Int, Float). total নামে তিনটি ঘোষণা, তিনটিতেই দুটি parameter, তাই তিনটিই প্রার্থী।
  2. লাইন ১ বাদ। প্রথম argument হুবহু মেলে (খরচ 0), কিন্তু দ্বিতীয়টি Float থেকে Int: খেলনা ভাষায় এমন রূপান্তর নেই (দশমিক হারানো ঠেকাতে)। একটি argument অসম্ভব হলেই পুরো প্রার্থী বাদ।
  3. লাইন ২ সম্ভব, লাইন ৩ নয়। (Float, Float)-এ প্রথম argument-এ Int থেকে Float coercion (খরচ 1), দ্বিতীয়টি হুবহু (0): খরচ [1, 0]. Str-এর প্রার্থীতে কোনো argument-ই মেলে না।
  4. একমাত্র viable, তাই বিজয়ী। Compiler লাইন ২ বেছে নেয় আর ডাকটি নতুন করে লেখে: প্রথম argument-এর আগে একটি রূপান্তর বসায়। Ad hoc polymorphism পুরোটাই compile-এর সময়; চলার সময় কোনো বাছাই নেই।
  5. দ্বিতীয় ডাক: mix(1040, 60). দুটি argument-ই Int. লাইন ৪ চায় দ্বিতীয়টিতে রূপান্তর [0, 1], লাইন ৫ চায় প্রথমটিতে [1, 0]. দুটিই সম্ভব।
  6. Ambiguity. লাইন ৪ প্রথম argument-এ ভালো, লাইন ৫ দ্বিতীয়টিতে। কেউ প্রতিটি argument-এ সমান বা ভালো নয়, তাই compiler আন্দাজ না করে error দেয়। সমাধান programmer-এর হাতে: একটি argument নিজে রূপান্তর করে লিখুন, যেমন mix(1040, 60.0).

TypeScript-এ overloading একটু আলাদা: কয়েকটি signature লেখা যায়, কিন্তু বাস্তবায়ন একটিই, যার ভেতরে চলার সময় typeof দিয়ে শাখা। সত্যিকারের run (TypeScript 5.9.2, Node.js 24.15.0):

function fee(kg: number): number;
function fee(zone: string): number;
function fee(x: number | string): number {
  return typeof x === "number" ? 20 * x : (x === "Dhaka" ? 60 : 120);
}
console.log(fee(3), fee("Dhaka"), fee("Rajshahi"));
fee(true);

ovl.ts(7,5): error TS2769: No overload matches this call.
  Overload 1 of 2, '(kg: number): number', gave the following error.
    Argument of type 'boolean' is not assignable to parameter of type 'number'.
  Overload 2 of 2, '(zone: string): number', gave the following error.
    Argument of type 'boolean' is not assignable to parameter of type 'string'.
(error-এর লাইন বাদ দিয়ে চালালে) 60 60 120

C++ আর Java-তে প্রতিটি overload সত্যিই আলাদা function. Linker যেন এদের আলাদা করতে পারে, C++ compiler parameter-এর type নামের ভেতরে লিখে দেয় (name mangling): Linux-এ GCC আর Clang যে Itanium C++ ABI মানে, তাতে total(int, int) হয় _Z5totalii আর total(double, double) হয় _Z5totaldd. Linking-এর দিক পর্ব ৭৪-এ।

Type class — ad hoc-কে নিয়মে বাঁধা

Overloading-এর একটি বড় সমস্যা: overload করা নাম দিয়ে নতুন generic কোড লেখা যায় না। ধরুন আপনি “যেকোনো দেখানো-যায় এমন জিনিসের তালিকা ছাপানো” লিখতে চান; show-এর কোন overload ডাকা হবে, তা generic কোড লেখার সময় জানা নেই। Philip Wadler আর Stephen Blott ১৯৮৯ সালের “How to make ad-hoc polymorphism less ad hoc” প্রবন্ধে Haskell-এর জন্য এর সমাধান দেন: type class. একটি class একটি operation-এর নাম আর type ঘোষণা করে, প্রতিটি type নিজের instance লেখে, আর generic function একটি শর্ত (constraint) বহন করে। উদাহরণ (Haskell, চালানো হয়নি):

class Show a where            -- operation-এর নাম আর type
  show :: a -> String
instance Show Bool where      -- Bool-এর নিজের কোড
  show True = "true"
  show False = "false"
receipt :: Show a => [a] -> String   -- যেকোনো a, যদি Show a থাকে
receipt xs = concatMap show xs

Show a => অংশটিই ছবি ৩৬.১-এর সেতু: receipt parametric (যেকোনো a), কিন্তু শর্তসাপেক্ষে; আর show-এর আসল কোড ad hoc, প্রতিটি type-এর আলাদা। Rust-এর trait একই ধারণার আরেক রূপ: fn receipt<T: Display>(xs: &[T]). Haskell compiler সাধারণত instance-গুলো একটি “dictionary” হিসেবে লুকানো argument-এ পাঠায়, আর Rust সাধারণত প্রতিটি type-এর জন্য আলাদা কপি বানায়; দুটি কৌশলই পর্ব ৩৭-এ।

৪ · Subtype polymorphism formal-ভাবে — subsumption আর record subtyping

পর্ব ০৮-এ subtyping S <: T (“S হলো T-এর subtype”) আর T-Sub নিয়মটি দেখেছেন। সেখানে S <: T আসত class-এর ঘোষণা থেকে (class C extends D), অর্থাৎ nominal typing. এখানে আমরা structural পথে যাব, যেখানে সম্পর্কটি type-এর আকার থেকে প্রমাণ হয় (পর্ব ২২-এর structural typing; TypeScript এভাবেই কাজ করে)। প্রথমে মূল নিয়মটি, যাকে বলে subsumption:

Γ ⊢ e : S    S <: T
Γ ⊢ e : T
(T-Sub)

নিয়মটি বলে: e-এর type S প্রমাণ হলে, আর S যদি T-এর subtype হয়, e-কে T হিসেবেও ধরা যায়। এখন S <: T নিজেই কীভাবে প্রমাণ হয়, তার নিয়ম লাগবে। Haat-এর বর্ধিত রূপে structural record type ধরুন: {name: Str, points: Int}, যার মান লেখা হয় {name: "Rina", points: 120}, আর field পড়া হয় r.points দিয়ে (পর্ব ২২-এর record ছিল nominal, নাম দিয়ে ঘোষিত; subtyping-এর জন্য এখানে আকার-ভিত্তিক রূপ নিচ্ছি)। বাজারঘরের দুই রকম ক্রেতা: Customer = {name: Str} আর Member = {name: Str, points: Int}. নিয়মগুলো:

 
S <: S
(S-Refl)
S <: U    U <: T
S <: T
(S-Trans)
 
S <: Top
(S-Top)
 
{l1: T1, …, ln+k: Tn+k} <: {l1: T1, …, ln: Tn}
(S-RcdWidth)
Si <: Ti (প্রতিটি i)
{li: Si} <: {li: Ti}
(S-RcdDepth)
{kj: Sj} হলো {li: Ti}-এর ক্রম বদল
{kj: Sj} <: {li: Ti}
(S-RcdPerm)

S-Refl আর S-Trans বলে <: একটি preorder (প্রতিফলী আর সংক্রামী সম্পর্ক; বিচ্ছিন্ন গণিত কোর্সের পর্ব ৫৬-এ এমন সম্পর্কের গণিত আছে)। Top সবার ওপরের type, যার কোনো field নেই; সব মান তার মধ্যে পড়ে। Width subtyping (S-RcdWidth) বলে বেশি field-এর record কম field-এর record-এর subtype: Member <: Customer. শুনতে উল্টো লাগে, কিন্তু মনে রাখুন: subtype মানে বেশি প্রতিশ্রুতি, আর বেশি প্রতিশ্রুতির মানের সংখ্যা কম। যে কোড শুধু .name পড়ে, তাকে একজন Member দিলে কোনো ক্ষতি নেই। Depth subtyping (S-RcdDepth) বলে field-এর type নিজেও subtype হতে পারে: {buyer: Member} <: {buyer: Customer}. আর S-RcdPerm বলে field-এর ক্রম কোনো বিষয় নয়।

নিয়ম থেকে algorithm

এই নিয়মগুলো সংজ্ঞা হিসেবে সুন্দর, কিন্তু checker হিসেবে অচল। S-Trans-এর U কোথা থেকে আসবে? Checker-কে একটি মাঝের type আন্দাজ করতে হবে, যা syntax-directed নয়: পর্ব ৩৪-এ দেখেছেন, ভালো checker প্রতিটি আকারের জন্য ঠিক একটি নিয়ম খোঁজে। (T-Sub-ও একই সমস্যা আনে, কারণ এর conclusion-এ e যেকোনো গঠনের হতে পারে; বাস্তব checker তাই T-Sub-কে আলাদা নিয়ম না রেখে T-Call-এর মতো জায়গায় “argument-এর type parameter-এর type-এর subtype কি না” যাচাইয়ে মিশিয়ে দেয়।) সমাধান হলো algorithmic subtyping: তিনটি record নিয়মকে একটিতে জুড়ে দেওয়া (“T-এর প্রতিটি field S-এ আছে, আর সেই field-এর type subtype”), আর S-Trans পুরো বাদ দেওয়া। Benjamin Pierce-এর Types and Programming Languages (২০০২) বইয়ের subtyping অধ্যায়ে প্রমাণ আছে যে এই দুই পদ্ধতি একই সম্পর্ক দেয় (S-Trans আর S-Refl “admissible”, অর্থাৎ বাকি নিয়ম থেকেই বেরিয়ে আসে)। নিচের checker প্রতিটি ধাপ ছেপে নিজের derivation দেখায়:

# Algorithmic subtyping for records and functions (Haat extension, a proposal)
def show(t):
    if isinstance(t, str): return t
    if t[0] == "rec": return "{" + ", ".join(f"{f}: {show(x)}" for f, x in t[1].items()) + "}"
    return "(" + ", ".join(map(show, t[1])) + ") -> " + show(t[2])

def sub(s, t, d=0):                       # is s <: t ?  prints the derivation
    pad, ok, rule = "  " * d, False, ""
    print(f"{pad}{show(s)} <: {show(t)} ?")
    if s == t and isinstance(s, str): ok, rule = True, "S-Refl"
    elif t == "Top": ok, rule = True, "S-Top"
    elif s[0] == t[0] == "rec":           # width + depth + permutation
        rule, ok = "S-Rcd", True
        for f, ft in t[1].items():
            if f not in s[1]: print(f"{pad}  field '{f}' missing"); ok = False; break
            if not sub(s[1][f], ft, d + 1): ok = False; break
    elif s[0] == t[0] == "fn" and len(s[1]) == len(t[1]):
        rule = "S-Arrow"                  # parameters flip, result keeps direction
        ok = (all(sub(tp, sp, d + 1) for sp, tp in zip(s[1], t[1]))
              and sub(s[2], t[2], d + 1))
    print(f"{pad}{'yes' if ok else 'NO'} {rule}")
    return ok

Customer = ("rec", {"name": "Str"})
Member = ("rec", {"name": "Str", "points": "Int"})
greetC = ("fn", [Customer], "Int")        # works for every Customer
greetM = ("fn", [Member], "Int")          # reads .points
print("A:", sub(greetC, greetM)); print()
print("B:", sub(greetM, greetC))

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

({name: Str}) -> Int <: ({name: Str, points: Int}) -> Int ?
  {name: Str, points: Int} <: {name: Str} ?
    Str <: Str ?
    yes S-Refl
  yes S-Rcd
  Int <: Int ?
  yes S-Refl
yes S-Arrow
A: True

({name: Str, points: Int}) -> Int <: ({name: Str}) -> Int ?
  {name: Str} <: {name: Str, points: Int} ?
    Str <: Str ?
    yes S-Refl
    field 'points' missing
  NO S-Rcd
NO S-Arrow
B: False

Indentation-ই derivation tree: প্রতিটি প্রশ্নের নিচে তার উপ-প্রশ্ন, আর শেষে কোন নিয়মে উত্তর। S-Rcd লাইনটি তিনটি record নিয়মের যোগফল: Customer-এর একমাত্র field name Member-এ আছে (width), তার type Str <: Str (depth), আর ক্রম দেখা হয়নি (permutation). কিন্তু function-এর বেলায় অদ্ভুত কিছু ঘটেছে: A-তে প্রশ্ন ছিল (Customer) -> Int <: (Member) -> Int, অথচ checker parameter-এর জন্য জিজ্ঞেস করল উল্টো প্রশ্ন, Member <: Customer. কেন, সেটিই পরের অংশ।

৫ · Function subtyping — parameter কেন উল্টো দিকে

পর্ব ০৮-এ S-Arrow নিয়মটি দেখেছেন, Liskov-এর পূর্বশর্ত আর প্রতিশ্রুতির নিয়মের type-রূপ হিসেবে। এখানে নিয়মটি আবার লিখে প্রমাণ করব যে অন্য কোনো দিক নিরাপদ নয়:

T1 <: S1    S2 <: T2
(S1) -> S2 <: (T1) -> T2
(S-Arrow)

ফেরত type একই দিকে চলে: এটি covariance. Parameter-এর type উল্টো দিকে: এটি contravariance. বাজারঘরের ভাষায়: যে কাজের জন্য “Member-দের অভিবাদন জানানোর একজন লোক” চাওয়া হয়েছে, সেখানে “যেকোনো ক্রেতাকে অভিবাদন জানাতে পারেন” এমন লোক পাঠানো নিরাপদ; তিনি Member-দেরও পারবেন। উল্টোটা নিরাপদ নয়। এবার এটি সত্যিকারের কোডে দেখুন, যেখানে কোনো type checker পাহারা দিচ্ছে না:

// বাজারঘর: দুই রকম ক্রেতা
const rina = { name: "Rina", points: 120 };   // Member: {name, points}
const karim = { name: "Karim" };              // শুধু Customer: {name}

function greetAny(c) { return "Hello " + c.name; }   // (Customer) -> Str
function greetMember(m) {                            // (Member) -> Str
  return "Hello " + m.name + ", points " + m.points.toFixed(0);
}
// greetAll চায় একটি (Customer) -> Str, আর সব ক্রেতার ওপর ডাকে
function greetAll(f, list) {
  for (const c of list) console.log(f(c));
}

greetAll(greetAny, [rina, karim]);      // ঠিক জায়গায় ঠিক function
try {
  greetAll(greetMember, [rina, karim]); // (Member)->Str যেখানে (Customer)->Str চাওয়া
} catch (e) {
  console.log(e.name + ": " + e.message);
}
const onlyMembers = [rina];
greetAll(greetAny, onlyMembers);        // উল্টো দিক: (Customer)->Str, শুধু Member-দের ওপর

আসল আউটপুট (ব্রাউজারে; লেখকের Node.js 24.15.0-তেও হুবহু এক):

Hello Rina
Hello Karim
Hello Rina, points 120
TypeError: Cannot read properties of undefined (reading 'toFixed')
Hello Rina

দ্বিতীয় ডাকে Rina-র জন্য সব ঠিক, কিন্তু Karim-এর points নেই: undefined.toFixed, আর TypeError. greetMember ধরে নিয়েছিল তার argument-এ points থাকবে; যে জায়গায় তাকে বসানো হয়েছে সেখানে সেই প্রতিশ্রুতি নেই। শেষ ডাকটি উল্টো দিক: সাধারণ function-কে বিশেষ জায়গায় বসানো, আর কোনো সমস্যা নেই। Checker-এর আউটপুটের A (True) আর B (False) ঠিক এই দুই আচরণ।

প্রস্তাব ৩৬.১ — parameter-এ covariance unsound

ধরুন S-Arrow-এর বদলে নিয়ম হতো S-ArrowCo: S1 <: T1 আর S2 <: T2 হলে (S1) -> S2 <: (T1) -> T2. তাহলে record আর function-সহ Haat-এর বর্ধিত রূপে একটি well-typed program আছে, যা চলার সময় আটকে যায় (type soundness ভাঙে)।

প্রমাণ. ১. S-RcdWidth দিয়ে Member <: Customer, আর S-Refl দিয়ে Int <: Int. ২. S-ArrowCo দিয়ে (Member) -> Int <: (Customer) -> Int. ৩. ধরুন Γ = bonus : (Member) -> Int, karim : Customer, যেখানে bonus-এর শরীর return m.points;. ৪. T-Var আর ধাপ ২-এর ওপর T-Sub দিয়ে Γ ⊢ bonus : (Customer) -> Int. ৫. T-Var দিয়ে Γ ⊢ karim : Customer, তাই T-Call দিয়ে Γ ⊢ bonus(karim) : Int; program-টি well-typed. ৬. চলার সময় karim-এর মান {name: "Karim"}, আর শরীরে m.points হিসাব করতে হয়; এই record-এ points নেই, তাই কোনো evaluation নিয়ম খাটে না: program আটকে গেল, যা ঠিক সেই ভুল যা type system-এর বাদ দেওয়ার কথা। ∎

উল্টো দিকে, S-Arrow কেন নিরাপদ তার রূপরেখা: (S1) -> S2 type-এর f-কে (T1) -> T2 হিসেবে ব্যবহার করলে প্রতিটি argument v-এর type T1; শর্ত T1 <: S1, তাই T-Sub দিয়ে v : S1, যা f-এর শরীর ধরে নিয়েছে। ফল S2, আর S2 <: T2, তাই ব্যবহারকারী যা আশা করেন তা-ই পান। পূর্ণ প্রমাণে progress আর preservation লাগে, যা পর্ব ৩৮-এ (Type soundness). Checker-এর A প্রশ্নটি ধাপে ধাপে:

1C = {name: Str}2M = {name: Str, points: Int}3greetC : (C) -> Int4greetM : (M) -> Int5A: greetC, M-এর জায়গায়?6B: greetM, C-এর জায়গায়?
এই মুহূর্তে
লক্ষ্য
প্রশ্ন
  1. প্রশ্ন A. greetAll-এর মতো কোনো জায়গা চায় (M) -> Int, আমরা দিতে চাই greetC : (C) -> Int. যাচাই করতে হবে (C) -> Int <: (M) -> Int. দুই পাশই function type, তাই একমাত্র খাটে এমন নিয়ম S-Arrow.
  2. দুই উপ-প্রশ্ন। S-Arrow-এর দুই premise: parameter-এর জন্য উল্টো দিকে M <: C (জায়গাটি যা দেবে, তা greetC-র চাওয়ার মধ্যে পড়ে কি না), আর ফেরত type-এর জন্য একই দিকে Int <: Int.
  3. M <: C, record নিয়মে। C-র প্রতিটি field M-এ আছে কি না দেখা হয়: C-র একমাত্র field name, M-এ আছে, আর Str <: Str (S-Refl). M-এর বাড়তি points কোনো সমস্যা নয় (width). উত্তর yes, S-Rcd.
  4. A সম্পূর্ণ। Int <: Int, S-Refl. দুটি premise-ই প্রমাণিত, তাই S-Arrow দিয়ে A: True. সাধারণ function বিশেষ জায়গায় বসতে পারে।
  5. প্রশ্ন B, উল্টো দিক। (M) -> Int <: (C) -> Int যাচাই করতে S-Arrow চায় C <: M. M-এর field points C-তে নেই, তাই S-Rcd ব্যর্থ, আর S-Arrow-ও। B: False.
  6. এর অর্থ। B-র “না” ঠিক JavaScript run-এর TypeError-টিকে চালানোর আগেই আটকায়: greetM-কে এমন জায়গায় বসানো যেত না যেখানে Karim-এর মতো শুধু-Customer আসতে পারে। Contravariance কোনো রুচির বিষয় নয়, এটি নিরাপত্তার শর্ত।

TypeScript-এর সিদ্ধান্ত — strict কোথায়, ঢিলা কোথায়

TypeScript ২.৬ (২০১৭) থেকে --strictFunctionTypes flag আছে, যা --strict-এর অংশ। কিন্তু নিয়মটি শুধু function-type property-তে খাটে; method syntax-এ লেখা parameter এখনো দুই দিকেই মেনে নেওয়া হয় (bivariance), যাতে প্রচলিত JavaScript-এর ধাঁচ না ভাঙে। একই ফাইলে দুটি রূপ, সত্যিকারের run (TypeScript 5.9.2, tsc --noEmit --strict --target es2022):

type Customer = { name: string };
type Member = { name: string; points: number };
function bonus(m: Member): number { return m.points.toFixed(0).length; }

type ProcF = { run: (c: Customer) => number };   // property: contravariant
const p1: ProcF = { run: bonus };
type ProcM = { run(c: Customer): number };       // method: bivariant
const p2: ProcM = { run: bonus };
const karim: Customer = { name: "Karim" };
console.log(p2.run(karim));

fnvar.ts(8,21): error TS2322: Type '(m: Member) => number' is not assignable to type '(c: Customer) => number'.
  Types of parameters 'm' and 'c' are incompatible.
    Property 'points' is missing in type 'Customer' but required in type 'Member'.

Error এল শুধু লাইন ৮-এ (property রূপ)। লাইন ১২-র method রূপ নীরবে পাস করল, যদিও দুটির অর্থ হুবহু এক। --strictFunctionTypes false দিলে লাইন ৮-ও পাস করে (সত্যিকারের run, ০টি error). ডিফল্টে tsc error থাকলেও JavaScript লেখে; সেই ফাইল Node.js 24.15.0-তে চালালে শেষ লাইনে: TypeError: Cannot read properties of undefined (reading 'toFixed'). প্রস্তাব ৩৬.১-এর ভুলটি বাস্তবে, একটি জনপ্রিয় ভাষার মেনে নেওয়া program-এ। এটি TypeScript-এর ঘোষিত নকশা-সিদ্ধান্ত, ভুল নয়; ফাঁকটির আলোচনা পর্ব ৩৮-এও আসবে।

৬ · Generic type-এর variance — covariant, contravariant আর invariant

Function type-এর দুটি দিক আলাদা আচরণ করে। একই প্রশ্ন যেকোনো generic type-এ ওঠে: Member <: Customer হলে List<Member> আর List<Customer>-এর সম্পর্ক কী? উত্তরের নাম variance. একটি type constructor F (যেমন List বা Box) হলো

  • covariant, যদি S <: T থেকে F<S> <: F<T> (একই দিকে);
  • contravariant, যদি S <: T থেকে F<T> <: F<S> (উল্টো দিকে);
  • invariant, যদি S আর T সমান না হলে F<S> আর F<T>-এর কোনো সম্পর্ক না থাকে।

কোনটি নিরাপদ, তা ঠিক করে F-এর ভেতরে T কোথায় বসে। S-Arrow থেকেই নিয়মটি আসে: শুধু বাইরে দেওয়া হয় (output, ফেরত মান) → covariant; শুধু ভেতরে নেওয়া হয় (input, parameter) → contravariant; দুটোই → invariant. শুধু পড়া যায় এমন একটি Box(T), যার একটিই method get() -> T, covariant. শুধু লেখা যায় এমন একটি Sink(T), যার method put(x: T), contravariant. আর বদলানো যায় এমন array বা list, যেখানে get আর set দুটিই আছে, তাকে invariant হতেই হবে। পড়া আর লেখা দুটোই থাকলে covariant করলে কী হয়, তার সবচেয়ে বিখ্যাত উদাহরণ Java-র array.

1String[] names = new String[2];2Object[] objs = names;3objs[0] = "Rina";4objs[1] = 1040;5// TypeScript: একই নিয়ম6everyone.push({name: "Karim"});
এই মুহূর্তে
compiler
array-র ভেতর
  1. Array তৈরি। Java-তে প্রতিটি array object নিজের element type মনে রাখে, এখানে String. এই তথ্য চলার সময়ও থাকে (array “reified”).
  2. Covariant নিয়ম। Java Language Specification অনুযায়ী S <: T হলে S[] <: T[], তাই String[] একটি Object[]. objs আর names একই array-র দুটি নাম (aliasing, পর্ব ২৩)। Compiler সন্তুষ্ট।
  3. বৈধ লেখা। "Rina" একটি Object, তাই compile হয়। চলার সময় JVM-এর aastore নির্দেশ দেখে মানটি array-র আসল element type String-এর সঙ্গে খাপ খায় কি না: খায়।
  4. ফাঁক, আর জোড়াতালি। 1040 autobox হয়ে Integer, যা একটি Object: compile পাস। কিন্তু aastore-এর যাচাই দেখে Integer String নয়, আর ছোড়ে ArrayStoreException: java.lang.Integer (Java 21, উদাহরণ, চালানো হয়নি; আচরণটি JLS-এ লেখা)। Static নিয়মের ফাঁক প্রতিটি লেখায় একটি dynamic যাচাই দিয়ে ঢাকা।
  5. TypeScript: একই নিয়ম, যাচাই নেই। TypeScript-এ array-ও covariant: const everyone: Customer[] = members; বৈধ, আর push দিয়ে শুধু-Customer Karim ঢুকে গেল। Type মুছে যায়, তাই চলার সময় কোনো store check নেই।
  6. ভুল ধরা পড়ে অনেক পরে। সত্যিকারের run-এ tsc --strict ০টি error দিল। Node.js 24.15.0-তে loop প্রথমে Rina 120 ছাপল, তারপর Karim-এ m.points.toFixed: TypeError. ভুলের কারণ লাইন ৬, বার্তা অন্য জায়গায়।

Java কেন এই নকশা বেছেছিল? ১৯৯৫ সালে Java-তে generics ছিল না; Arrays.sort(Object[])-এর মতো একটি method সব রকম array-তে চালাতে covariance ছিল সহজ পথ। Java 5-এ (২০০৪) যখন generics এল, তখন List<String> আর List<Object>-কে invariant রাখা হলো: List<Object> xs = new ArrayList<String>(); compile error (Java 21, উদাহরণ, চালানো হয়নি)। নমনীয়তা ফেরানো হলো ব্যবহারের জায়গায় লেখা wildcard দিয়ে, একে বলে use-site variance: List<? extends Customer> থেকে পড়া যায় (covariant ব্যবহার), List<? super Member>-এ লেখা যায় (contravariant ব্যবহার)। Joshua Bloch-এর Effective Java-র “PECS” স্মৃতিসূত্র: producer extends, consumer super. Java-র generics-এর হাতে-কলমে চর্চা আছে Java কোর্সের পর্ব ২৮-এ (generics).

অন্য পথ declaration-site variance: type ঘোষণার সময় একবার লিখে দেওয়া। C# 4.0 (২০১০) interface আর delegate-এ out T ও in T, Kotlin-এ out ও in, Scala-য় +A ও -A. TypeScript ৪.৭ (২০২২) থেকে ঐচ্ছিক in/out annotation আছে, আর compiler সেগুলো যাচাই করে। সত্যিকারের run (TypeScript 5.9.2, --strict):

interface Reader<out T> { get(): T }
interface Writer<in T> { put(x: T): void }
const r: Reader<Customer> = rm;   // rm : Reader<Member>, OK
const w: Writer<Member> = wc;     // wc : Writer<Customer>, OK
const r2: Reader<Member> = rc;    // rc : Reader<Customer>
box.ts(12,7): error TS2322: Type 'Reader<Customer>' is not assignable to type 'Reader<Member>'.
  Property 'points' is missing in type 'Customer' but required in type 'Member'.

interface Bad<out T> { put: (x: T) => void }
box2.ts(3,15): error TS2636: Type 'Bad<sub-T>' is not assignable to type 'Bad<super-T>' as implied by variance annotation.

প্রথম অংশে covariant Reader আর contravariant Writer ঠিক দিকে মেনে নেওয়া হলো, আর উল্টো দিকের Reader বাতিল। দ্বিতীয় অংশে compiler ঘোষণাটিই যাচাই করল: out বলা T একটি parameter-এ বসেছে, তাই TS2636. একটি সূক্ষ্ম বিষয়: পরীক্ষার সময় Bad-এ প্রথমে method syntax লেখা হয়েছিল (put(x: T): void), তাতে কোনো error আসেনি, কারণ অংশ ৫-এর method bivariance এখানেও খাটে। Property syntax-এ লিখলে তবেই TS2636 এল।

৭ · Bounded polymorphism — ∀α <: T

Parametric polymorphism-এ α সম্পর্কে কিছুই জানা নেই, তাই শরীরে α-র কোনো field পড়া যায় না। Subtyping দিয়ে {total: Int} নিলে field পড়া যায়, কিন্তু আরেকটি সমস্যা: ফল ফেরত দিলে বাড়তি field হারিয়ে যায়। ধরুন বাজারঘরে দুটি অর্ডারের মধ্যে বড়টি চাই:

fn biggerA(a: HasTotal, b: HasTotal) -> HasTotal { … }        // subtyping
fn biggerB[T <: HasTotal](a: T, b: T) -> T { … }              // bounded
// HasTotal = {total: Int}; Haat-এর বর্ধিত রূপ

দুটিতেই শরীর একই: if a.total >= b.total { return a; } return b;. কিন্তু biggerA(rina, sumi)-এর type শুধু HasTotal: T-Sub argument-কে HasTotal বানিয়ে ঢুকিয়েছিল, আর ফেরার পথে points আর name-এর খবর হারিয়ে গেছে। biggerB-তে T-কে Member দিয়ে instantiate করলে ফলের type-ও Member. এটিই bounded polymorphism (Cardelli–Wegner ১৯৮৫-এ bounded quantification নামে): type variable-এর ওপর একটি ঊর্ধ্বসীমা। নিয়ম দুটি T-TAbs আর T-TApp-এরই রূপ:

Γ, α <: B ⊢ e : τ
Γ ⊢ Λα <: B. e : ∀α <: B. τ
(T-TAbsB)
Γ ⊢ e : ∀α <: B. τ    Γ ⊢ σ <: B
Γ ⊢ e[σ] : [α ↦ σ]τ
(T-TAppB)

শরীরের ভেতরে Γ-তে α <: B লেখা থাকে, তাই checker a.total দেখলে α-র জায়গায় B-র field খোঁজে। ব্যবহারের সময় একটি বাড়তি premise: দেওয়া type σ সীমা মানে কি না। নিচের checker তিনটি রূপ পাশাপাশি যাচাই করে:

# Bounded polymorphism vs plain subtyping (Haat extension, a proposal)
def show(t):
    if isinstance(t, str): return t
    return "{" + ", ".join(f"{f}: {show(x)}" for f, x in t.items()) + "}"
def sub(s, t):                       # record width + depth subtyping
    if isinstance(s, dict) and isinstance(t, dict):
        return all(f in s and sub(s[f], ft) for f, ft in t.items())
    return s == t
def field(t, f, bounds={}):          # type of e.f ; a type variable has
    b = bounds.get(t, t) if isinstance(t, str) else t   # only its bound
    if isinstance(b, dict) and f in b: return b[f]
    raise TypeError(f"no field '{f}' in type {show(t)}")

HasTotal = {"total": "Int"}
Member = {"name": "Str", "total": "Int", "points": "Int"}
def biggerA(arg):                    # fn biggerA(a: HasTotal, b: HasTotal) -> HasTotal
    if not sub(arg, HasTotal): raise TypeError("argument is not a HasTotal")
    return HasTotal                  # T-Sub forgot the extra fields
def biggerB(arg):                    # fn biggerB[T <: HasTotal](a: T, b: T) -> T
    if not sub(arg, HasTotal):
        raise TypeError(f"{show(arg)} does not satisfy bound {show(HasTotal)}")
    return arg                       # result type T, with T := the argument's type

tests = [
    ("body, T unbounded: a.total", lambda: field("T", "total", {"T": "Top"})),
    ("body, T <: HasTotal: a.total", lambda: field("T", "total", {"T": HasTotal})),
    ("biggerA(rina, sumi).points", lambda: field(biggerA(Member), "points")),
    ("biggerB(rina, sumi).points", lambda: field(biggerB(Member), "points")),
    ('biggerB("Rina", "Sumi")', lambda: biggerB("Str")),
]
for label, run in tests:
    try: print(f"{label:30} : {run()}")
    except TypeError as e: print(f"{label:30} x {e}")

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

body, T unbounded: a.total     x no field 'total' in type T
body, T <: HasTotal: a.total   : Int
biggerA(rina, sumi).points     x no field 'points' in type {total: Int}
biggerB(rina, sumi).points     : Int
biggerB("Rina", "Sumi")        x Str does not satisfy bound {total: Int}

প্রথম দুই লাইন শরীরের যাচাই: সীমাহীন T-তে a.total অচল (parametricity), সীমা থাকলে চলে। তৃতীয় লাইন subtyping-এর দাম: ফলের type HasTotal, তাই .points নেই। চতুর্থ লাইনে bounded রূপ T := Member বসিয়ে পুরো type রাখল। শেষ লাইনে T-TAppB-এর premise σ <: B ব্যর্থ। TypeScript-এ হুবহু একই পরীক্ষা, সত্যিকারের run (tsc --noEmit --strict): biggerA(rina, sumi).points-এ error TS2339: Property 'points' does not exist on type 'HasTotal'., biggerB("Rina", "Sumi")-এ error TS2345: Argument of type 'string' is not assignable to parameter of type 'HasTotal'., আর ভুল লাইন দুটি বাদ দিয়ে চালালে biggerB(rina, sumi).points ছাপল 120.

কখনো সীমাটি নিজেই type variable-এর ওপর নির্ভর করে। “নিজের মতো আরেকটির সঙ্গে তুলনা করা যায়” লিখতে Java-তে <T extends Comparable<T>>: T-এর সীমায় T নিজেই আছে। একে বলে F-bounded polymorphism; Peter Canning, William Cook ও সহলেখকেরা ১৯৮৯ সালে object-oriented ভাষার জন্য ধারণাটি দেন। Rust-এ একই কাজ trait bound দিয়ে, fn biggest<T: PartialOrd>(xs: &[T]) -> &T, আর Haskell-এ constraint দিয়ে, maximum :: Ord a => [a] -> a (দুটিই উদাহরণ, চালানো হয়নি)। লক্ষ করুন, এখানে bound subtyping নয়, type class বা trait: ছবি ৩৬.১-এর সেতু আবার।

৮ · তিন রূপ পাশাপাশি — compiler-এর চোখে আর Haat-এর নকশা

প্রতিটি রূপের দুটি প্রশ্ন compiler-এর জন্য জরুরি: কোন কোড চলবে তা কখন ঠিক হয়, আর চলার সময় কোড কয়টি. বাস্তবায়নের বিস্তারিত পর্ব ৩৭-এ; এখানে মানচিত্রটি:

রূপকোডের সংখ্যাকখন বাছাইচেনা উদাহরণসাধারণ বাস্তবায়ন
Parametricলেখা হয় একবারType যাচাই একবার; instantiation compile-এJava/TS generics, ML-এর 'a listErasure বা monomorphization (পর্ব ৩৭)
Overloadingপ্রতিটি type-এর আলাদাCompile-এর সময়, static type দেখেC++, Java, Haat-এর +আলাদা function, mangled নাম
Coercionএকটি কোড + রূপান্তরCompile-এর সময় রূপান্তর বসানোC-র int থেকে doubleরূপান্তরের নির্দেশ
Type class / traitপ্রতিটি instance আলাদাসাধারণত compile-এHaskell Show, Rust DisplayDictionary passing বা আলাদা কপি
Subtypeএক কোড, অনেক type-এর মানMethod বাছাই চলার সময়Java extends, TS structuralvtable দিয়ে dynamic dispatch (পর্ব ০৮)

রূপগুলো একে অন্যের সঙ্গে সহজে মেশে না। পর্ব ৩৫-এর Hindley–Milner inference parametric polymorphism-এর জন্য তৈরি; subtyping যোগ করলে “x : α আর α <: Customer” ধরনের constraint আসে, আর সাধারণ unification আর যথেষ্ট নয়। Overloading-এর সঙ্গে inference-ও কঠিন: fn(x) { return x + x; }-এ + কোন overload, তা x-এর type না জানলে বলা যায় না, আর x-এর type + না জানলে বের হয় না। Haskell type class এনেছিল ঠিক এই জট খুলতে: অজানা অবস্থায় constraint (Num a =>) জমিয়ে রাখা।

তাই Haat v1-এর বাছাই ইচ্ছাকৃত: কোনো generics, subtyping বা ব্যবহারকারীর overloading নেই, আর built-in operator-এ ছোট, বন্ধ একটি তালিকা (সিদ্ধান্ত ১১)। এতে পর্ব ৫২-এর type checker প্রতিটি expression-এর জন্য ঠিক একটি type বের করে, আর VM-এর ADD জানে দুই পাশ একই ধরনের। কোর্সের বর্ধিত রূপগুলো এক এক করে যোগ হয়: পর্ব ৩৫-এ inference-সহ parametric Haat, এই পর্বে record subtyping আর bound, আর পর্ব ৩৯-এ gradual আর affine type.

আরও গভীরে: Bounded quantification-যুক্ত System F, যাকে F<: বলা হয়, তার পূর্ণ রূপে subtyping যাচাই undecidable: Benjamin Pierce ১৯৯০-এর দশকের শুরুতে এটি প্রমাণ করেন, তাই বাস্তব ভাষা সীমিত রূপ নেয়। Java-র generics আর wildcard-এর subtyping-ও যথেষ্ট শক্তিশালী যে Radu Grigore ২০১৭ সালের একটি প্রবন্ধে দেখান, এর type checking দিয়ে Turing machine-এর হিসাব নকল করা যায়। উল্টো দিকে Stephen Dolan আর Alan Mycroft ২০১৭ সালে MLsub-এ দেখান কীভাবে subtyping-সহ ML-ধাঁচের inference-এ principal type রাখা যায়। Rust compiler trait-এর generic কোডকে সাধারণত প্রতিটি type-এর জন্য আলাদা করে compile করে, আর dyn Trait লিখলে vtable ব্যবহার করে: একই ভাষায় দুই বাস্তবায়ন।

পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই দেখা যায়।
১. Polymorphism-এর প্রকার? Universal (parametric, subtype/inclusion) আর ad hoc (overloading, coercion); Strachey ১৯৬৭, Cardelli–Wegner ১৯৮৫।
২. Overloading আর overriding-এর পার্থক্য? Overloading: একই নাম, আলাদা parameter, compile-এর সময় বাছাই। Overriding: subclass-এ একই signature, চলার সময় dynamic dispatch.
৩. (Animal) -> Int আর (Cat) -> Int-এর কোনটি কোনটির subtype? (Animal) -> Int <: (Cat) -> Int, কারণ parameter contravariant.
৪. Java-তে List<String> কি List<Object>? না, generics invariant; array covariant, আর তার দাম ArrayStoreException.
৫. Bounded generic কেন, শুধু interface parameter কেন নয়? Bound ফেরত type-এ আসল type রাখে, subtyping তা হারায়।

৯ · AI-এর যুগে polymorphism

Variance আর overload-এর প্রশ্নে AI assistant-এর উত্তর প্রায়ই আত্মবিশ্বাসী কিন্তু দিক উল্টো, বা এক ভাষার নিয়ম আরেক ভাষায় চাপানো। এই বিষয়ে বারবার দেখা ভুল আর যাচাইয়ের উপায়:

AI-এর ভুলকীভাবে ধরবেন
Function-এর parameter covariant বলা, বা “subclass-এর method আরও নির্দিষ্ট parameter নিতে পারে”S-Arrow-এর সঙ্গে মেলানো; অংশ ৫-এর মতো একটি argument বানানো, যা উল্টো দিকে crash করায়
“TypeScript-এ --strict দিলে সব function sound”Method syntax আর array covariance নিয়ে ছোট program লিখে tsc আর node-এ চালানো
Java array-র নিয়ম generics-এ চাপানো (List<String> একটি List<Object>)javac-এ compile করে দেখা; JLS-এর generics অধ্যায় পড়া
Overload resolution-এর ফল আন্দাজে বলা, বিশেষত C++-এ ambiguity আর template মিশে গেলেআসল compiler-এ compile করা; সন্দেহ হলে argument-এ নিজে cast লেখা
Generic কোডে type error চুপ করাতে as T, any বা unchecked castDiff-এ এগুলো খোঁজা; parametricity ভাঙছে কি না ভাবা (অংশ ২-এর sneaky)
বানানো error code বা compiler flagআসল tsc, javac বা clang চালিয়ে বার্তা কপি করা; flag-এর নাম documentation-এ খোঁজা

AI-কে ভালোভাবে কাজে লাগাতে ভাষা আর version বলে দিন, আর প্রতিটি দাবির জন্য একটি পরীক্ষাযোগ্য উদাহরণ চান:

আমি polymorphism আর variance শিখছি; ভাষা: TypeScript 5.9 (--strict), Java 21, C++20. ১. নিচের প্রতিটি type জোড়ার জন্য বলো কোনটি কোনটির subtype, কোন নিয়মে (S-Arrow, record width/depth, variance), আর কেন: [আমার type-গুলো] ২. প্রতিটি "না"-এর জন্য একটি ছোট program দাও, যা উল্টো দিক মেনে নিলে চলার সময় ভাঙত। ৩. TypeScript-এ কোন জায়গায় checker ইচ্ছা করে ঢিলা (method bivariance, array covariance), তা আলাদা করে চিহ্নিত করো। ৪. কোনো compiler error বা আউটপুট অনুমান করে লিখবে না; কোনটি আমাকে tsc, javac বা clang-এ চালিয়ে দেখতে হবে, তার তালিকা দাও।

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

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

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

প্র ০১Strachey আর Cardelli–Wegner overloading আর coercion-কে কেন “ad hoc” বললেন? Type class কি এই ভাগ মুছে দিয়েছে?

“Ad hoc” শব্দের অর্থ “একটি নির্দিষ্ট কাজের জন্য, সাধারণ নিয়ম ছাড়া”। Strachey ১৯৬৭ সালের notes-এ লক্ষ করেছিলেন, +-এর integer আর real সংস্করণের মধ্যে কোনো সাধারণ কাঠামো নেই; যন্ত্রের স্তরে দুটি সম্পূর্ণ আলাদা নির্দেশ, শুধু নাম এক। কোন type-এ কী হবে তা আগে থেকে বলার কোনো নিয়ম নেই; প্রতিটি জোড়া আলাদা করে সংজ্ঞায়িত। উল্টো দিকে একটি list-এর দৈর্ঘ্য গোনার function সব type-এ একই কাজ করে, একটি সূত্রে লেখা যায়; তাই তার নাম parametric. Cardelli আর Wegner ১৯৮৫ সালে এই ধারণা বাড়িয়ে বলেন, ad hoc polymorphism আসলে “বাহ্যিক” polymorphism: একটি সীমিত সংখ্যক মনোমরফিক function একটি নামের নিচে জড়ো করা, আর coercion হলো একটি type-কে চুপচাপ আরেক type-এ বদলে একটি function-কে অনেক type-এর মতো দেখানো।

সমস্যাটি ছিল ব্যবহারিক। ML-এর মতো ভাষায় parametric polymorphism আর type inference সুন্দরভাবে চলত, কিন্তু সমতা (==) আর সংখ্যার operator নিয়ে বিশেষ ব্যবস্থা লাগত; Standard ML-এ “equality type” নামে একটি আলাদা ধারণা আনতে হয়েছিল। Wadler আর Blott ১৯৮৯ সালে প্রস্তাব করেন, overload-এর তালিকাকেই একটি নাম দেওয়া হোক (class), প্রতিটি type সদস্যপদ ঘোষণা করুক (instance), আর generic কোড তার প্রয়োজন constraint হিসেবে লিখুক। এতে একটি overload করা নাম ব্যবহার করে নতুন generic কোড লেখা গেল, আর inference-ও টিকে রইল।

তাহলে কি ভাগ মুছে গেছে? পুরোপুরি নয়। show-এর Bool আর Int সংস্করণ এখনো আলাদা কোড, অর্থাৎ ad hoc; কিন্তু তাদের ওপর লেখা receipt parametric, শুধু শর্তসহ। গবেষকেরা একে প্রায়ই “constrained” বা “bounded” parametric polymorphism বলেন। Rust-এর trait, Swift-এর protocol আর C++20-এর concept একই দিকে এগিয়েছে। ভাগটি তাই এখন একটি বর্ণালি: একদিকে বিশুদ্ধ parametric, অন্যদিকে বিশুদ্ধ ad hoc, মাঝখানে type class, যেখানে ad hoc কোড একটি নিয়মের ছাতার নিচে আসে।

মূল উপলব্ধি: ad hoc আর parametric-এর পার্থক্য “একটি সূত্র না অনেক আলাদা সংজ্ঞা”-র প্রশ্ন। Type class দুটিকে জুড়েছে: ad hoc সংজ্ঞাগুলোকে নাম দিয়ে, যাতে তাদের ওপর parametric কোড লেখা যায়।

প্র ০২Java-র covariant array কি একটি নকশা-ভুল? Generics invariant করে আর wildcard এনে Java কী শিখল?

১৯৯৫ সালের Java-তে generics ছিল না। সব রকম array সাজানো, কপি করা বা খোঁজার একটি method লিখতে হলে তার parameter হতে হতো Object[]; array invariant হলে String[] সেখানে দেওয়াই যেত না, আর প্রতিটি element type-এর জন্য আলাদা method লিখতে হতো। Covariance এই সমস্যা সহজে মেটাল, আর দাম হিসেবে প্রতিটি array-তে লেখার সময় JVM-কে একটি যাচাই করতে হয় (aastore-এর store check), যা ব্যর্থ হলে ArrayStoreException. অর্থাৎ type system-এর একটি জানা ফাঁক চলার সময়ের পাহারা দিয়ে ঢাকা: এটি unsound নয় এই অর্থে যে ভুল মেমরি লেখা হয় না, কিন্তু static type-এর প্রতিশ্রুতি ভঙ্গ হয়ে dynamic error আসে।

নকশা-ভুল বলা কঠিন, কারণ বিকল্প ছিল সীমিত; C# প্রায় একই কারণে reference type-এর array-তে একই covariance রেখেছে। কিন্তু Java 5-এর generics-এর নকশাকারেরা (যাঁদের কাজের পূর্বসূরি ছিল ১৯৯৮ সালের GJ প্রস্তাব, Bracha, Odersky, Stoutamire আর Wadler-এর) শিক্ষাটি নিয়েছিলেন: List<String> আর List<Object> invariant. আর generics erasure দিয়ে বাস্তবায়িত (পর্ব ৩৭), তাই চলার সময় list নিজের element type জানে না; array-র মতো store check করা সম্ভবই ছিল না। Invariance তাই ঐচ্ছিক নয়, বাধ্যতামূলক।

নমনীয়তা ফেরাতে wildcard: ? extends T আর ? super T. এটি শক্তিশালী, কিন্তু বহু programmer-এর কাছে কঠিন; Bloch-এর PECS স্মৃতিসূত্রই দেখায় নিয়মটি মনে রাখতে সাহায্য লাগে। পরের ভাষাগুলো (C# 4, Kotlin, Scala, TypeScript 4.7) declaration-site variance বেছে নিয়েছে: type-এর লেখক একবার out বা in লেখেন, আর ব্যবহারকারীর কিছু ভাবতে হয় না। Kotlin দুটিই রেখেছে।

মূল উপলব্ধি: পড়া আর লেখা দুটোই চলে এমন container covariant হলে হয় dynamic যাচাই লাগে (Java array), নয়তো চুপচাপ ভুল (TypeScript array). Invariance আর স্পষ্ট variance annotation সেই দাম এড়ায়, বদলে programmer-কে variance নিয়ে ভাবতে শেখায়।

প্র ০৩TypeScript জেনেশুনে method parameter-এ bivariance আর array-তে covariance রেখেছে। একটি জনপ্রিয় ভাষার জন্য এই সিদ্ধান্ত কতটা যুক্তিসঙ্গত?

TypeScript-এর ঘোষিত নকশা-লক্ষ্যে sound type system চাওয়া হয়নি; লক্ষ্য হলো বিদ্যমান JavaScript-এর ধাঁচ যতটা সম্ভব মেনে নিয়ে বেশিরভাগ ভুল ধরা। Array covariance বাদ দিলে কী হতো ভাবুন: Member[] একটি Customer[]-চাওয়া function-এ দেওয়া যেত না, যদিও বাস্তবের বেশিরভাগ function array শুধু পড়ে। লক্ষ লক্ষ লাইনের কোডে হঠাৎ error আসত। TypeScript-এ readonly Customer[] লেখা যায়, যা সত্যিই নিরাপদভাবে covariant, কিন্তু সাধারণ Customer[]-কেও covariant রাখা হয়েছে সুবিধার জন্য।

Method bivariance-এর পেছনেও একই যুক্তি। DOM-এর event handler, callback-ভিত্তিক library আর class hierarchy-তে method parameter প্রায়ই subclass-এ আরও নির্দিষ্ট লেখা হয় (Eiffel-এর ধাঁচে)। TypeScript ২.৬-এ যখন strictFunctionTypes এল, তখন দলটি একটি সমঝোতা করল: function-type property আর আলাদা function-এ contravariance, কিন্তু method-এ পুরোনো আচরণ। এই পর্বের সত্যিকারের run দেখিয়েছে দাম: হুবহু একই অর্থের দুটি লেখা, একটিতে error, অন্যটিতে চলার সময় TypeError.

যুক্তিসঙ্গত কি না, তা নির্ভর করে আপনি type system-কে কী ভাবছেন তার ওপর। যদি প্রমাণ-যন্ত্র হিসেবে দেখেন, তবে এগুলো গর্ত। যদি ভুল-খোঁজার যন্ত্র হিসেবে দেখেন, যা বেশিরভাগ বাস্তব কোডে খুব কম মিথ্যা alarm দেয়, তবে সমঝোতাটি বোঝা যায়। ব্যবহারিক শিক্ষা হলো ফাঁকগুলো জানা: callback-এর type property রূপে লেখা, শুধু-পড়ার array-কে readonly বলা, আর বাইরে থেকে আসা তথ্যের জন্য চলার সময়ের যাচাই রাখা। পর্ব ৩৮-এ unsound feature-গুলোর একটি তালিকা দেখবেন।

মূল উপলব্ধি: ভাষার নকশায় soundness একটি মূল্য, একমাত্র মূল্য নয়। TypeScript ইচ্ছা করে কয়েকটি জায়গায় তা ছেড়েছে; ভালো programmer সেই জায়গাগুলো চেনেন আর নিজের কোডে সেগুলো এড়িয়ে চলেন।

প্র ০৪“Theorems for free” — একটি function-এর শুধু type দেখে তার আচরণ সম্পর্কে কী জানা যায়, আর এটি বাস্তবে কোথায় কাজে লাগে?

Parametric function তার type variable-এর মান “ভেতর থেকে” দেখতে পারে না; এটি একটি সীমাবদ্ধতা, আর সীমাবদ্ধতা থেকেই তথ্য আসে। John Reynolds ১৯৮৩ সালে এই ধারণাকে গাণিতিক রূপ দেন (relational parametricity): একটি polymorphic function বিভিন্ন type-এর মধ্যে যেকোনো সম্পর্ক রক্ষা করে। Philip Wadler ১৯৮৯ সালে দেখান যে এ থেকে প্রতিটি type-এর জন্য একটি উপপাদ্য স্বয়ংক্রিয়ভাবে বের করা যায়। যেমন ∀α. [α] -> [α] type-এর যেকোনো f আর যেকোনো function g-এর জন্য: আগে প্রতিটি উপাদানে g প্রয়োগ করে তারপর f, আর আগে f তারপর g, একই ফল দেয়। কারণ f শুধু অবস্থান বদলাতে পারে (উল্টানো, বাদ দেওয়া, পুনরাবৃত্তি), উপাদান বদলাতে পারে না।

বাস্তবে এর তিনটি ব্যবহার আছে। এক, compiler optimization: Haskell-এর GHC-তে list fusion-এর মতো রূপান্তরের যুক্তিতে এমন উপপাদ্যের ভূমিকা আছে, যা মাঝের list বানানো এড়ায়। দুই, API পড়া: ∀α. α -> α দেখেই বোঝা যায় function-টি identity, documentation না পড়েই; Haskell প্রোগ্রামারেরা type দিয়ে function খোঁজার tool (Hoogle) ব্যবহার করেন এই ভরসায়। তিন, নিরাপত্তা আর বিমূর্তকরণ: একটি module যদি একটি type লুকিয়ে রাখে, বাইরের parametric কোড তার ভেতরের রূপ ব্যবহার করতে পারে না; Reynolds-এর মূল প্রেরণা ছিল ঠিক এই abstraction.

কিন্তু উপপাদ্যগুলোর শর্ত আছে। Side effect (ছাপা, ফাইল লেখা), exception, অসীম loop, আর চলার সময় type দেখার ক্ষমতা প্রতিশ্রুতি দুর্বল করে। এই পর্বের TypeScript-এর sneaky function-টি typeof দিয়ে সংখ্যাকে আলাদা করে 995-কে 996 বানিয়েছে, যদিও type ছিল identity-র। Java-র instanceof আর reflection-ও তাই। Haskell-এও seq আর অসীম loop-এর কারণে উপপাদ্যগুলো সামান্য শর্তসহ খাটে, এটি গবেষণা-সাহিত্যে আলোচিত।

মূল উপলব্ধি: যত কম জিনিস একটি function করতে পারে, তার type তত বেশি কথা বলে। কোনো ভাষায় generic কোডে type দেখার সুযোগ (typeof, instanceof, cast) রাখা মানে এই বিনামূল্যের উপপাদ্যগুলো হারানো।

প্র ০৫Haat-এর পরের সংস্করণে একটিমাত্র polymorphism যোগ করার সুযোগ থাকলে কোনটি আগে আনবেন, আর কেন?

তিনটি প্রার্থী, আর প্রতিটির খরচ compiler-এর ভিন্ন ভিন্ন অংশে পড়ে। Parametric polymorphism (generics) আনলে সবচেয়ে বড় লাভ: first, list-এর function, Option[T] (পর্ব ২৪-এর ADT-র সঙ্গে) একবার লিখলেই চলে। Type checker-এ লাগে T-TAbs আর T-TApp, আর পর্ব ৩৫-এর unification দিয়ে type argument বের করা যায়, তাই first(2, 520)-এ [Int] লিখতে হয় না। Back end-এ সিদ্ধান্ত নিতে হবে erasure না monomorphization (পর্ব ৩৭); Haat-এর VM-এ সব মান আগে থেকেই একই আকারের slot-এ থাকে, তাই erasure সহজ।

Record subtyping আনলে বাজারঘরের বিভিন্ন ক্রেতা আর অর্ডার এক function-এ চালানো যায়। কিন্তু খরচ বেশি: field-এর offset আর স্থির থাকে না (Member-এ name যেখানে, অন্য record-এ সেখানে নাও থাকতে পারে), তাই field পড়ার কোড ধীর হয় বা বাড়তি কৌশল লাগে; আর inference-এর সঙ্গে মেলানো কঠিন, যা অংশ ৮-এ দেখেছেন। Bounded polymorphism না থাকলে subtyping-এ ফলের type হারায়, তাই আসলে দুটি feature একসাথে লাগে।

ব্যবহারকারীর overloading সবচেয়ে সস্তা মনে হয়, কিন্তু inference আর error বার্তা দুটোকেই জটিল করে, আর ambiguity-র নিয়ম লিখতে হয়। এর চেয়ে ভালো পথ হলো parametric polymorphism আসার পর type class বা trait-এর মতো constrained polymorphism, যা print-কে Int, Bool আর Str-এর বাইরে বাড়াতেও কাজে লাগবে। ML-পরিবারের ইতিহাসও এই ক্রম দেখায়: আগে Hindley–Milner, তারপর type class.

তাই একটি যুক্তিসঙ্গত পরিকল্পনা: v2-তে inference-সহ parametric polymorphism, v3-তে trait-ধাঁচের constraint, আর subtyping শুধু দরকার হলে, bound-সহ। প্রতিটি ধাপে reference বাস্তবায়নের পরীক্ষা বাড়াতে হবে, আর পুরোনো সব program আগের মতো চলছে কি না differential test দিয়ে দেখতে হবে।

মূল উপলব্ধি: polymorphism বাছাই মানে শুধু ব্যবহারকারীর সুবিধা নয়, checker, inference, memory layout আর code generation-এর ওপর প্রভাব হিসাব করা। Parametric polymorphism সবচেয়ে বেশি লাভ দেয় সবচেয়ে কম জটিলতায়।

অনুশীলন

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

  1. Checker বড় করুন (বাস্তবায়ন): অংশ ৪-এর subtyping checker-এ (derivation ছাপা বাদ দিয়ে) দুটি type constructor যোগ করুন: Box(T), যা শুধু পড়া যায় (get() -> T), আর Ref(T), যা পড়া আর লেখা দুটোই যায়। প্রতিটির variance কী হওয়া উচিত? তারপর এগুলো যাচাই করুন: M <: Top, Box(M) <: Box(C), Box(C) <: Box(M), Ref(M) <: Ref(C), (Box(C)) -> Int <: (Box(M)) -> Int, () -> Ref(M) <: () -> Ref(C). এখানে C = {name: Str}, M = {name: Str, points: Int}.

    Box শুধু বাইরে দেয়, তাই covariant; Ref ভেতরে নেয় আর বাইরে দেয়, তাই invariant. নতুন দুই শাখা:

        if s[0] == "Box": return sub(s[1], t[1])                       # covariant
        if s[0] == "Ref": return sub(s[1], t[1]) and sub(t[1], s[1])   # invariant

    সত্যিকারের run-এর ফল:

    M <: Top                             True
    Box(M) <: Box(C)                     True
    Box(C) <: Box(M)                     False
    Ref(M) <: Ref(C)                     False
    Ref(M) <: Ref(M)                     True
    (Box(C)) -> Int <: (Box(M)) -> Int   True
    () -> Ref(M) <: () -> Ref(C)         False

    ষষ্ঠটিতে দুটি নিয়ম মিশেছে: S-Arrow parameter উল্টে Box(M) <: Box(C) চায়, আর Box covariant, তাই True. শেষটিতে ফেরত type একই দিকে, Ref(M) <: Ref(C), কিন্তু Ref invariant, তাই False. Ref covariant হলে কী ভাঙত, তা অংশ ৬-এর Java array-র ধাপগুলোতেই আছে।

  2. ভুল খুঁজুন (derivation আর বাস্তব কোড): (ক) একজন শিক্ষার্থী লিখলেন: “Member <: Customer, তাই S-Arrow দিয়ে (Member) -> Int <: (Customer) -> Int.” কোন ধাপটি ভুল? (খ) নিচের TypeScript কোড tsc --strict-এ ০টি error দেয়। চলার সময় কী হবে, আর কোন typing নিয়মটি এর জন্য দায়ী?
    type Customer = { name: string };
    type Member = { name: string; points: number };
    const members: Member[] = [{ name: "Rina", points: 120 }];
    const everyone: Customer[] = members;
    everyone.push({ name: "Karim" });
    for (const m of members) console.log(m.name, m.points.toFixed(0));

    (ক) S-Arrow-এর parameter-এর premise হলো T1 <: S1, অর্থাৎ এখানে Customer <: Member, Member <: Customer নয়। শিক্ষার্থী premise-এর দিক উল্টে ফেলেছেন। Customer <: Member প্রমাণ করা যায় না (points নেই), তাই সিদ্ধান্তটিই ভুল; সঠিক সম্পর্ক উল্টো, (Customer) -> Int <: (Member) -> Int. অংশ ৪-এর checker-এর B প্রশ্ন ঠিক এটিই False দেখায়।

    (খ) সত্যিকারের run (TypeScript 5.9.2, Node.js 24.15.0): tsc --strict ০টি error; চালালে প্রথমে Rina 120, তারপর TypeError: Cannot read properties of undefined (reading 'toFixed'). দায়ী TypeScript-এর array covariance: Member <: Customer থেকে Member[] <: Customer[] মেনে নেওয়া, যদিও array-তে লেখা যায় (push). নিরাপদ রূপ: const everyone: readonly Customer[] = members;; তখন push নিজেই compile error, কারণ readonly array-তে push method নেই (সত্যিকারের run: error TS2339: Property 'push' does not exist on type 'readonly Customer[]'.)।

  3. আউটপুট অনুমান করুন (overload resolution): অংশ ৩-এর খেলনা ভাষায় (একমাত্র coercion Int থেকে Float) এই overload-গুলো আছে: fee(Int), fee(Float), fee(Str); pay(Int, Int), pay(Float, Float); ship(Float, Int), ship(Int, Float), ship(Float, Float). এই ডাকগুলোর প্রতিটির ফল কী: fee(Int), fee(Float), pay(Float, Int), pay(Str, Int), ship(Int, Int), ship(Float, Float), ship(Int, Float)?

    অংশ ৩-এর resolve function-এ এই তালিকা দিয়ে সত্যিকারের run:

    fee(Int)            picks (Int)
    fee(Float)          picks (Float)
    pay(Float, Int)     picks (Float, Float)
    pay(Str, Int)       error: no matching overload
    ship(Int, Int)      error: ambiguous call, candidates (Float, Int) / (Int, Float) / (Float, Float)
    ship(Float, Float)  picks (Float, Float)
    ship(Int, Float)    picks (Int, Float)

    যুক্তি: pay(Float, Int)-এ (Int, Int) অসম্ভব (Float থেকে Int নেই), তাই (Float, Float), খরচ [0, 1]. ship(Int, Int)-এ তিনটিই সম্ভব: [1, 0], [0, 1], [1, 1]; প্রথম দুটির কেউ অন্যটির চেয়ে সব দিকে ভালো নয়, তাই ambiguous (তৃতীয়টি দুটির কাছেই হারে, কিন্তু তাতে জট খোলে না)। ship(Int, Float)-এ (Float, Int) অসম্ভব, (Int, Float) খরচ [0, 0], (Float, Float) খরচ [1, 0]; প্রথমটি বিজয়ী।

  4. ভাষার feature নকশা (Haat-এর বর্ধিত রূপ): বাজারঘরের কোডে অর্ডার, ফেরত আর বাতিল, তিন রকম record আছে, প্রতিটিতে total: Int আর আরও কিছু field. একটি biggest function চান, যা দুটি একই ধরনের record থেকে বড়টি ফেরত দেয় আর ফলের সব field রাখে। (ক) বাক্যগঠন আর typing rule লিখুন। (খ) biggest(o1, o2)-এ T কীভাবে বের হবে? (গ) কোন কোন error বার্তা লাগবে? (ঘ) VM-এ কোনো বদল লাগবে কি?

    একটি সম্ভাব্য নকশা (একমাত্র সঠিক উত্তর নয়):

    • (ক) fn biggest[T <: {total: Int}](a: T, b: T) -> T { if a.total >= b.total { return a; } return b; }. Type: ∀T <: {total: Int}. (T, T) -> T. শরীর যাচাইয়ে T-TAbsB: Γ-তে T <: {total: Int}, তাই a.total : Int (T-Field, সীমা দিয়ে)। ব্যবহারে T-TAppB: σ <: {total: Int} premise.
    • (খ) সবচেয়ে সরল: প্রথম argument-এর type থেকে T নেওয়া, তারপর দ্বিতীয়টি T-এর subtype কি না দেখা। আরও সাধারণ উপায় দুই type-এর “join” (সবচেয়ে ছোট সাধারণ supertype) নেওয়া, কিন্তু তাতে ফলের field হারাতে পারে, যা লক্ষ্যের বিরুদ্ধে। অস্পষ্ট হলে biggest[Order](o1, o2) লিখতে বলা।
    • (গ) Haat-এর ধাঁচে: Str does not satisfy bound {total: Int}, no field 'points' in type T (সীমাহীন বা ভুল সীমার T-তে field পড়লে), আর দুই argument-এর type না মিললে পরিচিত type mismatch: expected Order, found Refund.
    • (ঘ) Erasure বেছে নিলে না: VM-এ মান আগের মতোই, শুধু field পড়ার নির্দেশ জানতে হবে record-এ total কোথায়। Width subtyping থাকায় offset স্থির নয়, তাই নামে খোঁজা (hash table) বা প্রতিটি instantiation-এর জন্য আলাদা কপি (monomorphization) লাগবে; বিনিময়টি পর্ব ৩৭-এর বিষয়।

    নিজে যাচাই: অংশ ৭-এর checker-এ Order = {"total": "Int", "qty": "Int"} নামে একটি নতুন record যোগ করে biggerB(Order) আর biggerB("Str") চালান; প্রথমটি পুরো Order ফেরত দেবে, দ্বিতীয়টি ওপরের প্রথম বার্তাটি দেবে।

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

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

ক্রমএকটি static compiler overload করা ডাক total(1040, 2.5)-এর জন্য যে কাজগুলো করে, সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. Argument-গুলোর static type বের করে: (Int, Float)
  2. একই নাম আর একই সংখ্যক parameter-এর সব ঘোষণা প্রার্থী হিসেবে নেয়
  3. প্রতিটি argument-এ হুবহু মেলা, রূপান্তর বা অসম্ভব যাচাই করে অসম্ভব প্রার্থী বাদ দেয়
  4. বাকিদের মধ্যে যে প্রতিটি argument-এ সমান বা ভালো, তাকে খোঁজে; না পেলে ambiguous call error
  5. বিজয়ীর জন্য প্রয়োজনীয় রূপান্তর বসিয়ে ডাকটির কোড তৈরি করে

Cardelli–Wegner (১৯৮৫)-এর শ্রেণিবিভাগে কোন জোড়াটি “universal” polymorphism?

  • Overloading আর coercion
  • Parametric আর inclusion (subtype)
  • Parametric আর coercion
  • Overloading আর subtype

Record type Customer = {name: Str} আর Member = {name: Str, points: Int} হলে structural subtyping-এ কোনটি সত্য?

  • Customer <: Member
  • দুটির কোনো subtype সম্পর্ক নেই
  • Member <: Customer
  • দুটি একে অপরের subtype, অর্থাৎ সমান

Cat <: Animal হলে function type-এর জন্য কোনটি সঠিক?

  • (Animal) -> Int <: (Cat) -> Int
  • (Cat) -> Int <: (Animal) -> Int
  • দুটির মধ্যে কোনো সম্পর্ক নেই
  • দুটি একে অপরের subtype

Java 21-এ String[] names = new String[2]; Object[] objs = names; objs[0] = 1040; — কী ঘটে?

  • Compile error, কারণ String[] একটি Object[] নয়
  • Integer নীরবে array-তে ঢোকে, পরে পড়ার সময় ভুল হয়
  • 1040 string-এ রূপান্তরিত হয়ে "1040" জমা হয়
  • Compile হয়, কিন্তু চলার সময় ArrayStoreException

দুটি overload mix(Int, Float) আর mix(Float, Int) আছে, আর একমাত্র implicit conversion Int থেকে Float. ডাক mix(1040, 60)-এ (দুটিই Int) কী হয়?

  • প্রথমে ঘোষিত mix(Int, Float) বেছে নেওয়া হয়
  • Ambiguous call error
  • No matching overload error
  • চলার সময় argument-এর মান দেখে বাছাই হয়

TypeScript-এ function biggerA(a: HasTotal, b: HasTotal): HasTotal আর function biggerB<T extends HasTotal>(a: T, b: T): T (HasTotal = { total: number })। দুটি Member (name, total, points) দিয়ে ডেকে ফলের .points পড়লে tsc --strict কী বলে?

  • দুটিতেই কোনো error নেই
  • biggerB-তে error, biggerA-তে নয়
  • biggerA-তে error, biggerB-তে নয়
  • দুটিতেই error

একটি pure ভাষায় (side effect, exception বা চলার সময় type দেখার সুযোগ নেই) ∀α. α -> α type-এর একটি function, যা সবসময় থামে, কী করতে পারে?

  • শুধু argument-টিই ফেরত দিতে পারে (identity)
  • সংখ্যা হলে 1 যোগ করে ফেরত দিতে পারে
  • একটি ধ্রুবক মান ফেরত দিতে পারে
  • যেকোনো type-এর মান ফেরত দিতে পারে

শব্দকোষ

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

মনে রাখুন

  1. তিন রূপ: parametric (একটি কোড, ∀α), ad hoc (একই নাম, আলাদা কোড: overloading, coercion, type class), subtype (S <: T আর T-Sub). Haat v1-এ শুধু built-in + আর ==-এর ad hoc রূপ।
  2. Overload resolution compile-এর সময়: প্রার্থী, সম্ভাব্যতা, খরচ, আর প্রতিটি argument-এ সমান বা ভালো একমাত্র বিজয়ী; নইলে ambiguous.
  3. Record subtyping: width (বেশি field), depth (field-এর subtype), permutation; checker-এ S-Trans বাদ দিয়ে একটি algorithmic নিয়ম।
  4. S-Arrow: parameter contravariant, ফল covariant; উল্টোটা মানলে well-typed program আটকে যায় (প্রস্তাব ৩৬.১, আর TypeScript-এর method bivariance-এর সত্যিকারের crash).
  5. Variance আর bound: পড়া → covariant, লেখা → contravariant, দুটো → invariant; Java array-র ফাঁক ArrayStoreException দিয়ে ঢাকা। Bounded polymorphism ∀α <: B ফলের পুরো type রাখে।

পরের পর্বে: পর্ব ৩৭ (Generics-এর বাস্তবায়ন — erasure, monomorphization আর dictionary passing). একই generic max Java-র মতো একটি কোডে, C++-এর মতো প্রতিটি type-এর আলাদা কপিতে, আর Haskell-এর মতো লুকানো dictionary-তে: compiler কী বানায় আর কেন।

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

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