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

Generics-এর বাস্তবায়ন — erasure, monomorphization আর dictionary passing

Implementing Generics — Erasure, Monomorphization and Dictionary Passing

Taught in Bangla, this lesson explains why generic code needs special handling and implements four strategies in in-page Python (Pyodide): monomorphization, dictionary passing, uniform representation with boxing, and type erasure. Real runs show Clang emitting one LLVM IR function per type, javap revealing the checkcast javac inserts, and tsc output with types erased. It covers heap pollution, bridge methods, polymorphic recursion and code bloat, then weighs code size, speed and separate compilation.

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

  • Parametric polymorphism-কে machine code-এ নামাতে কেন বিশেষ কৌশল লাগে, আর type instantiation-এর নিয়ম (∀ থেকে নির্দিষ্ট type)
  • Monomorphization, dictionary passing, uniform representation আর erasure — প্রতিটির কাজের ধাপ, Python-এ ছোট বাস্তবায়নসহ
  • সত্যিকারের Clang-এর LLVM IR, Java-র javap bytecode আর tsc-এর JavaScript পড়ে কোন ভাষা কোন পথ নিয়েছে তা নিজে চেনা
  • Heap pollution, bridge method, polymorphic recursion আর code bloat-এর মতো পার্শ্বফল বোঝা
  • কোডের আকার, গতি আর separate compilation-এর আপস বিচার করে একটি ভাষার জন্য কৌশল বেছে নেওয়া

১ · এক নকশা, অনেক type — সমস্যাটি কোথায়

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

পর্ব ৩৬-এ (Polymorphism — parametric, ad hoc আর subtype) দেখেছেন parametric polymorphism-এর তত্ত্ব: একটি function যেকোনো type-এ একইভাবে কাজ করে। এই পর্বের প্রশ্ন অন্য: compiler এমন function-কে machine code-এ কীভাবে নামায়? Haat spec v1-এ generics নেই। Reference বাস্তবায়নে দুটি সত্যিকারের run তা দেখায়। fn bigger<T>(a: T, b: T) -> T লিখলে parser থামে 1:10: error: expected '(' after function name বার্তায়। আর Str-এর জন্য আলাদা function লিখে তার ভেতরে a > b দিলে type checker বলে 6:8: error: type mismatch: expected Int, found Str, কারণ reference-এর সিদ্ধান্ত ১১ অনুযায়ী < <= > >= শুধু Int-এ চলে। তাই এই পর্বে আমরা Haat-এর বর্ধিত রূপ কল্পনা করব:

// Haat-এর বর্ধিত রূপ (spec v1-এ নেই): generic function আর Ord শর্ত
fn bigger<T: Ord>(a: T, b: T) -> T {
    if a > b { return a; }
    return b;
}
print(bigger(2, 5));            // T = Int  → 5
print(bigger("chal", "dal"));   // T = Str  → dal  (অক্ষরের code point ক্রমে)
print(bigger(1040, 996));       // T = Int  → 1040

এখানে T হলো একটি type parameter, আর T: Ord শর্ত বলে “T-এর মানগুলো তুলনা করা যায়”। বর্ধিত রূপে Int আর Str দুটিই Ord, কিন্তু তুলনার নিয়ম আলাদা: Int-এ একটি সংখ্যা-তুলনা, Str-এ অক্ষর ধরে ধরে তুলনা। Type checker-এর কাজ সহজ। পর্ব ৩৫-এর (Type inference — Hindley–Milner আর unification) ভাষায় bigger-এর type হলো একটি type scheme, ∀T. (T, T) -> T, আর প্রতিটি ডাকে T-কে একটি নির্দিষ্ট type দিয়ে বদলানো হয়। পর্ব ৩৬-এর System F-এর দুটি নিয়ম আবার দেখুন (α একটি type variable, Λα. e মানে “type নেয় এমন e”, Γ নাম থেকে type-এর তালিকা, আর [α ↦ σ]τ মানে “τ-তে α-র জায়গায় σ বসানো”):

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

T-TApp দিয়ে bigger : ∀T. (T, T) -> T থেকে পাই bigger : (Int, Int) -> Int (প্রথম ডাক) আর (Str, Str) -> Str (দ্বিতীয় ডাক)। Type-এর দিক থেকে কাজ শেষ। কিন্তু code generation-এর ধাপে (পর্ব ৬৯–৭২) তিনটি প্রশ্নের উত্তর লাগে, যা type scheme দেয় না:

  1. মাপ: a আর b কত byte? Register-এ রাখা যাবে, না memory-তে? (Haat-এর RISC-V back end-এ Int ৮ byte-এর একটি সংখ্যা, Str একটি pointer; C++-এ একটি struct ১০০ byte-ও হতে পারে।)
  2. কাজ: a > b কোন নির্দেশ? Int-এ একটি সংখ্যা-তুলনার নির্দেশ, double-এ floating-point তুলনা, Str-এ একটি loop.
  3. নকল আর মুক্তি: মানটি ফেরত দিতে কপি করতে হবে কীভাবে, আর garbage collector-কে বলতে হবে কি যে এটি pointer?

এই তিন প্রশ্নের উত্তর কখন আর কোথা থেকে আসে, তাই দিয়েই বাস্তবায়নের কৌশল আলাদা হয়। নিচের ছবিতে একই উৎস থেকে তিনটি প্রধান পথ:

ছবি ৩৭.১ — একটি generic function, তিনটি বাস্তবায়ন

ওপরে একই উৎস; নিচে compiler যা তৈরি করে। চতুর্থ পথ uniform representation অংশ ৪-এ, আর সেটি গ-এর ভিত্তি।

One generic source compiled three ways: monomorphization (two copies), dictionary passing (one copy plus per-type tables), erasure (one copy on Object plus casts at call sites) bigger<T> · একটি উৎস ক · Monomorphization bigger__Int bigger__Str ২টি কপি · সরাসরি ডাক খ · Dictionary passing bigger(d, a, b) ORD_INT ORD_STR ১টি কপি · type-প্রতি একটি খাতা গ · Erasure (+ boxing) bigger(Object, Object) checkcast ১টি কপি · ডাকের জায়গায় cast

২ · Monomorphization — প্রতিটি type-এর আলাদা কপি

Monomorphization শব্দের মানে “এক-রূপ করা”: compiler পুরো program ঘুরে দেখে generic function কোন কোন type-এ ডাকা হয়েছে, তারপর প্রতিটি type-এর জন্য T-এর জায়গায় সেই type বসিয়ে একটি সাধারণ, non-generic কপি বানায়। এরপর বাকি compiler (optimizer, code generator) জানেই না যে কখনো generics ছিল। C++-এ এর নাম template instantiation; Rust-এর generics-ও (trait object বাদে) এভাবেই compile হয়। সত্যিকারের run: Zig 0.17.1-এর সঙ্গে আসা Clang 22.1.8 (Apache-2.0 with LLVM exception; Zig MIT), target x86_64-linux-gnu, debug তথ্য ছাড়া:

// bigger.cpp — একটি template, তিনটি type
struct Taka { long paisa; };
bool operator>(Taka a, Taka b) { return a.paisa > b.paisa; }

template <typename T>
T bigger(T a, T b) { return a > b ? a : b; }

long   best_qty(long x, long y)      { return bigger(x, y); }
double best_rate(double x, double y) { return bigger(x, y); }
Taka   best_bill(Taka x, Taka y)     { return bigger(x, y); }
long   best_qty2(long x, long y)     { return bigger<long>(y, x); }
~/haat $ zig c++ --target=x86_64-linux-gnu -g0 -O0 -S -emit-llvm bigger.cpp
~/haat $ grep -E "^define|icmp|fcmp" bigger.ll
define noundef zeroext i1 @_Zgt4TakaS_(i64 %0, i64 %1) #0 {
  %11 = icmp sgt i64 %8, %10
define noundef i64 @_Z8best_qtyll(i64 noundef %0, i64 noundef %1) #1 {
define linkonce_odr noundef i64 @_Z6biggerIlET_S0_S0_(i64 noundef %0, i64 noundef %1) #0 comdat {
  %7 = icmp sgt i64 %5, %6
define noundef double @_Z9best_ratedd(double noundef %0, double noundef %1) #1 {
define linkonce_odr noundef double @_Z6biggerIdET_S0_S0_(double noundef %0, double noundef %1) #0 comdat {
  %7 = fcmp ogt double %5, %6
define i64 @_Z9best_bill4TakaS_(i64 %0, i64 %1) #1 {
define linkonce_odr i64 @_Z6biggerI4TakaET_S1_S1_(i64 %0, i64 %1) #0 comdat {
define noundef i64 @_Z9best_qty2ll(i64 noundef %0, i64 noundef %1) #1 {

পড়ার কৌশল: প্রতিটি define একটি আসল function. Template bigger নিজে কোথাও নেই; আছে তিনটি কপি, প্রতিটির নামে type লেখা। এটি name mangling (পর্ব ১৮-এ C++-এর namespace আর name mangling): _Z6biggerIlET_S0_S0_-এর IlE মানে template argument long, IdE মানে double, I4TakaE মানে Taka. চারটি ডাক, কিন্তু কপি তিনটি: best_qty2-এর bigger<long> আগের কপিটিই আবার ব্যবহার করেছে। আর প্রতিটি কপিতে > হয়েছে সেই type-এর নিজস্ব নির্দেশ: long-এ icmp sgt (signed integer তুলনা), double-এ fcmp ogt (floating-point তুলনা), Taka-য় operator>-এর একটি ডাক। এই কারণেই monomorphization দ্রুত: প্রতিটি কপি নিজের type-এর জন্য বিশেষভাবে তৈরি, কোনো পরোক্ষ ডাক নেই।

linkonce_odr আর comdat শব্দ দুটিও গুরুত্বপূর্ণ। দশটি .cpp ফাইল যদি একই header থেকে bigger<long> ব্যবহার করে, প্রতিটি object file-এ একটি করে কপি থাকে; linker (পর্ব ৭৪) একই নামের কপিগুলো থেকে একটি রেখে বাকিগুলো ফেলে দেয়। এবার -O2-এ একই ফাইল:

~/haat $ zig c++ --target=x86_64-linux-gnu -g0 -O2 -S -emit-llvm bigger.cpp
define noundef i64 @_Z8best_qtyll(i64 noundef %0, i64 noundef %1) local_unnamed_addr #0 {
  %3 = tail call noundef i64 @llvm.smax.i64(i64 %0, i64 %1)
  ret i64 %3
}
define noundef double @_Z9best_ratedd(double noundef %0, double noundef %1) local_unnamed_addr #0 {
  %3 = fcmp ogt double %0, %1
  %4 = select i1 %3, double %0, double %1
  ret double %4
}
define i64 @_Z9best_bill4TakaS_(i64 %0, i64 %1) local_unnamed_addr #0 {
  %3 = tail call i64 @llvm.smax.i64(i64 %0, i64 %1)
  ret i64 %3
}

তিনটি bigger কপিই উধাও: optimizer প্রতিটিকে ডাকার জায়গায় বসিয়ে দিয়েছে (inlining, পর্ব ৬৭), তারপর long-এর তুলনাকে একটি “বড়টি নেওয়া” নির্দেশে (llvm.smax) নামিয়েছে। সবচেয়ে সুন্দর ঘটনা best_bill-এ: Taka-র operator> ভেতরে একটি long তুলনা, আর Taka একটি long-এর মাপ, তাই generic কোড হাতে লেখা long কোডের সমান হয়ে গেছে। এটিকেই বলে zero-cost abstraction: generic লেখার জন্য চলার সময় কোনো দাম নেই। দাম দিতে হয় অন্য জায়গায়, যা নিচের run দেখায়।

~/haat $ zig c++ --target=x86_64-linux-gnu -fsyntax-only bag.cpp
bag.cpp:2:31: error: invalid operands to binary expression ('Bag' and 'Bag')
    2 | T bigger(T a, T b) { return a > b ? a : b; }
      |                             ~ ^ ~
bag.cpp:8:13: note: in instantiation of function template specialization 'bigger<Bag>' requested here
    8 |     Bag z = bigger(x, y);
      |             ^

এখানে Bag-এর কোনো > নেই। C++-এর template-এর শরীর যাচাই হয় instantiation-এর সময়, প্রতিটি type-এ আলাদা করে, আর error আসে template-এর ভেতরের লাইনে (লাইন ২), ডাকের লাইনে নয়। Haat-এর বর্ধিত রূপের T: Ord শর্ত (বা C++20-এর concept, Rust-এর trait bound) সমস্যাটি আগেই ধরে: শর্ত দেখে generic শরীর একবারই যাচাই হয়, আর ভুল ডাকে বার্তা আসে “Bag Ord নয়”। Template-এর বিস্তারিত আছে C++ কোর্সের পর্ব ২৮ · function template-এ। এবার monomorphizer নিজে বানান:

# Monomorphization: one copy of bigger<T> per type actually used
TEMPLATE = """def bigger__{T}(a, b):
    return a if {GT}(a, b) else b"""
GT_FOR = {"Int": "int_gt", "Str": "str_gt"}   # chosen at compile time

def int_gt(a, b): return a > b                 # one machine compare
def str_gt(a, b):                              # code point by code point
    for x, y in zip(a, b):
        if x != y: return ord(x) > ord(y)
    return len(a) > len(b)

# the extended-Haat program: bigger(2,5); bigger("chal","dal"); bigger(1040,996)
calls = [("Int", (2, 5)), ("Str", ("chal", "dal")), ("Int", (1040, 996))]

generated = {}                                 # instantiation cache
for T, _ in calls:
    if T not in generated:
        src = TEMPLATE.format(T=T, GT=GT_FOR[T])
        generated[T] = src
        print(f"--- instantiate bigger<{T}> ---")
        print(src)

namespace = {"int_gt": int_gt, "str_gt": str_gt}
for src in generated.values():
    exec(src, namespace)                       # "compile" each copy

print("--- run ---")
for T, args in calls:
    fn = namespace[f"bigger__{T}"]             # direct call, no lookup at run time
    print(f"bigger__{T}{args} = {fn(*args)}")
print("calls:", len(calls), "| generated functions:", len(generated))

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

--- instantiate bigger<Int> ---
def bigger__Int(a, b):
    return a if int_gt(a, b) else b
--- instantiate bigger<Str> ---
def bigger__Str(a, b):
    return a if str_gt(a, b) else b
--- run ---
bigger__Int(2, 5) = 5
bigger__Str('chal', 'dal') = dal
bigger__Int(1040, 996) = 1040
calls: 3 | generated functions: 2

তিনটি ডাক, দুটি কপি; তৃতীয় ডাক cache থেকে bigger__Int পেয়েছে, ঠিক Clang-এর best_qty2-এর মতো। __Int আর __Str প্রত্যয় হলো আমাদের ছোট name mangling. খেয়াল করুন, int_gt না str_gt, এই বাছাই হয়েছে কপি বানানোর সময়; চলার সময় কোনো বাছাই নেই। exec এখানে “compile”-এর অভিনয় করছে: বাস্তব compiler একই substitution করে AST-এর ওপর, লেখার ওপর নয়।

1fn bigger<T: Ord>(a: T, b: T) -> T {2    if a > b { return a; }3    return b;4}5print(bigger(2, 5));6print(bigger("chal", "dal"));7print(bigger(1040, 996));
Compiler-এর খাতা
এই ধাপে
T
cache
  1. Generic শরীর একবার যাচাই। T অজানা, কিন্তু শর্ত T: Ord বলে a > b বৈধ। Type scheme: ∀T: Ord. (T, T) -> T. এখনো কোনো machine code নেই।
  2. প্রথম ডাক। Argument 2 আর 5 থেকে T = Int (T-TApp). Cache-এ bigger__Int নেই, তাই কাজের তালিকায় যোগ হলো। ডাকটি সরাসরি সেই নামে বসানো হলো।
  3. কপি তৈরি। শরীরে T ↦ Int বসানো হলো। এখন a > b নিশ্চিতভাবে Int-এর তুলনা, যা back end একটি নির্দেশে নামাবে (Clang-এর icmp sgt-এর মতো)।
  4. দ্বিতীয় ডাক, নতুন type. T = Str; cache-এ নেই, তাই দ্বিতীয় কপি bigger__Str, যেখানে > হলো অক্ষর ধরে তুলনার loop. দুটি কপি সম্পূর্ণ আলাদা function.
  5. তৃতীয় ডাক, পুরোনো type. T = Int, cache-এ আছে। নতুন কপি নয়, সরাসরি bigger__Int ডাকা। তিন ডাকে দুই কপি।
  6. ফল। চলার সময় কোনো type-তথ্য, খাতা বা cast নেই: শুধু দুটি সাধারণ function আর সরাসরি ডাক। আউটপুট 5, dal, 1040. দাম: যতগুলো type, ততগুলো কপি।

Monomorphization-এর একটি মৌলিক শর্ত আছে: compiler-কে generic function-এর শরীর দেখতে হবে, কারণ কপি বানাতে উৎস লাগে। তাই C++-এর template সাধারণত header ফাইলে থাকে, আর separate compilation দুর্বল হয়: template বদলালে যত ফাইল সেটি ব্যবহার করে, সবগুলো আবার compile করতে হয়। Rust-এ generic function-এর মধ্যবর্তী রূপ library-র metadata-তে রাখা হয়, যাতে ব্যবহারকারীর crate কপি বানাতে পারে।

Rust-এ একই ধারণা (উদাহরণ, চালানো হয়নি): fn bigger<T: PartialOrd>(a: T, b: T) -> T { if a > b { a } else { b } } লিখে bigger(2, 5) আর bigger("chal", "dal") ডাকলে compiler দুটি কপি বানায়। কিন্তু একই trait দিয়ে &dyn Display লিখলে (trait object) কোনো কপি হয় না; তখন Rust একটি vtable ব্যবহার করে, যা পরের অংশের বিষয়ের খুব কাছের আত্মীয়।

৩ · Dictionary passing — type-এর সঙ্গে নির্দেশের খাতা

দ্বিতীয় পথে compiler একটিমাত্র কপি বানায়। কিন্তু a > b কীভাবে হবে, তা জানাতে প্রতিটি ডাকে একটি বাড়তি, লুকানো argument পাঠায়: সেই type-এর জন্য দরকারি function-গুলোর একটি table. একে বলে dictionary passing. Haskell-এর type class এর সবচেয়ে পরিচিত উদাহরণ; Philip Wadler আর Stephen Blott ১৯৮৯ সালের POPL প্রবন্ধে (“How to make ad-hoc polymorphism less ad hoc”) type class প্রস্তাব করেন, আর সেখানেই অনুবাদের এই কৌশলটি বর্ণনা করা হয়েছিল বলে সাধারণত উল্লেখ করা হয়। Haskell-এ (উদাহরণ, চালানো হয়নি):

bigger :: Ord a => a -> a -> a          -- "Ord a =>" = শর্ত
bigger a b = if a > b then a else b
-- ধারণাগতভাবে compiler এটিকে বানায়:
-- bigger dOrd a b = if (gt dOrd) a b then a else b

শর্ত Ord a => অনুবাদের পর একটি সাধারণ parameter হয়ে যায়। ডাকার জায়গায় compiler type জানে (T = Int), তাই সেখানে Ord Int-এর খাতাটি বসিয়ে দেয়। শর্ত একাধিক হলে লুকানো argument-ও একাধিক: (Ord a, Show a) => মানে দুটি খাতা। আর এক শর্ত আরেকটির ওপর দাঁড়ালে (Haskell-এ Ord-এর জন্য আগে Eq লাগে) খাতার ভেতরে খাতা থাকে: Ord-এর খাতায় একটি ঘর Eq-এর খাতার দিকে নির্দেশ করে, ঠিক যেমন বাজারের বড় ফর্দের এক লাইনে লেখা থাকে “মসলার তালিকা আলাদা কাগজে”। তালিকা-type-এর instance হলে (“a তুলনা করা গেলে a-এর list-ও তুলনা করা যায়”) খাতাটি চলার সময় একটি function দিয়ে বানানো হয়, যা a-এর খাতা নিয়ে list-এর খাতা ফেরত দেয়। Python-এ মূল ব্যবস্থাটি:

# Dictionary passing: ONE compiled bigger, plus a small table per type
def int_gt(a, b): return a > b
def str_gt(a, b):
    for x, y in zip(a, b):
        if x != y: return ord(x) > ord(y)
    return len(a) > len(b)

# "instance Ord Int" and "instance Ord Str": like a vtable, but per TYPE
ORD_INT = {"type": "Int", "gt": int_gt}
ORD_STR = {"type": "Str", "gt": str_gt}

lookups = 0
def bigger(ord_dict, a, b):                    # the only generated function
    global lookups
    lookups += 1
    gt = ord_dict["gt"]                        # look up the method at run time
    return a if gt(a, b) else b                # indirect call through the table

# the compiler adds the dictionary argument at each call site
calls = [(ORD_INT, (2, 5)), (ORD_STR, ("chal", "dal")), (ORD_INT, (1040, 996))]
for d, args in calls:
    print(f"bigger(ORD_{d['type'].upper()}, {args[0]!r}, {args[1]!r}) = {bigger(d, *args)}")

print("calls:", len(calls), "| generated functions: 1 | dictionaries: 2",
      "| run-time lookups:", lookups)

# a polymorphic caller just forwards the dictionary it received
def best_of_three(ord_dict, a, b, c):
    return bigger(ord_dict, bigger(ord_dict, a, b), c)
print("best_of_three(ORD_STR, ...) =", best_of_three(ORD_STR, "ata", "tel", "dal"))
print("run-time lookups now:", lookups)

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

bigger(ORD_INT, 2, 5) = 5
bigger(ORD_STR, 'chal', 'dal') = dal
bigger(ORD_INT, 1040, 996) = 1040
calls: 3 | generated functions: 1 | dictionaries: 2 | run-time lookups: 3
best_of_three(ORD_STR, ...) = tel
run-time lookups now: 5

উত্তর monomorphization-এর সঙ্গে হুবহু এক (5, dal, 1040), কিন্তু হিসাব উল্টো: function একটি, খাতা দুটি, আর প্রতিটি ডাকে চলার সময় একটি lookup আর একটি পরোক্ষ ডাক। শেষ অংশটি এই কৌশলের আসল শক্তি দেখায়। best_of_three নিজেও generic, তবু তার জন্য কোনো নতুন কপি লাগেনি; সে শুধু পাওয়া খাতাটি bigger-কে এগিয়ে দিয়েছে। দুটি ডাক, তাই lookup ৩ থেকে ৫ হলো। এর মানে generic library আগেই compile করে রাখা যায়, ব্যবহারকারীর type জানার দরকার নেই।

1ORD_INT = { gt: int_gt }2ORD_STR = { gt: str_gt }3fn bigger(d, a, b) {4    let gt = d.gt;5    if gt(a, b) { return a; }6    return b;7}8print(bigger(ORD_STR, "chal", "dal"));
bigger-এর frame
d
a, b
gt
  1. অনুবাদ। শর্ত T: Ord হয়ে গেল প্রথম parameter d. প্রতিটি instance (Ord Int, Ord Str) থেকে একটি খাতা, program শুরুর আগেই তৈরি। bigger-এর কপি মাত্র একটি।
  2. ডাকের জায়গা। Compiler এখানে static-ভাবে জানে T = Str, তাই লুকানো argument হিসেবে ORD_STR বসায়। খাতা বাছাই compile-এর সময়, ব্যবহার চলার সময়।
  3. খাতা খোলা। লাইন ৪-এ d.gt পড়া: একটি memory read. Monomorphization-এ এই ধাপ ছিল না।
  4. পরোক্ষ ডাক। gt-এর ঠিকানায় লাফ: str_gt("chal", "dal"). প্রথম অক্ষরেই পার্থক্য, 'c' (99) < 'd' (100), তাই false. পরোক্ষ ডাক সাধারণত inline করা যায় না, তাই কিছুটা ধীর।
  5. ফেরত। শর্ত মিথ্যা, তাই return b: আউটপুট dal, monomorphization-এর সঙ্গে একই।
  6. vtable-এর সঙ্গে তুলনা। পর্ব ০৮-এর vtable থাকে প্রতিটি object-এর ভেতরের pointer-এ, আর বাছাই হয় মানের আসল class দেখে। খাতা থাকে আলাদা argument-এ, প্রতি type-এ একটি, আর কোনো মান ছাড়াও পাঠানো যায়।

শেষ ধাপের পার্থক্যটি গভীর। পর্ব ০৮-এর vtable দিয়ে dynamic dispatch হয় একটি object থেকে: object না থাকলে vtable-ও নেই। কিন্তু Haskell-এ mempty :: Monoid a => a (“a type-এর শূন্য মান”) কোনো argument ছাড়াই খাতা থেকে মান তৈরি করে, কারণ খাতা আসে type থেকে, মান থেকে নয়। Rust-এর trait দুটোই দেয়: generic হিসেবে monomorphization, আর dyn Trait হিসেবে একটি “মোটা pointer” (মানের ঠিকানা + vtable-এর ঠিকানা)।

Dictionary passing-এর আরেকটি সুবিধা polymorphic recursion: একটি generic function নিজেকে বড় type-এ ডাকে। Monomorphization-এ প্রতিটি নতুন type নতুন কপি চায়, আর type অসীমভাবে বাড়লে কপিও অসীম। সত্যিকারের Clang 22.1.8 run:

template <typename T> struct Ref { const T* p; };

template <typename T>
int depth(T x, int n) {
    if (n == 0) return 0;
    return 1 + depth(Ref<T>{&x}, n - 1);   // calls itself at a BIGGER type
}
int main() { return depth(1, 3); }

~/haat $ zig c++ --target=x86_64-linux-gnu -fsyntax-only nest.cpp
nest.cpp:6:22: fatal error: recursive template instantiation exceeded maximum depth of 1024
nest.cpp:6:16: note: in instantiation of function template specialization 'depth<Ref<Ref<…<int>…>>>' requested here
   … (আরও ৯টি এমন note; প্রতিটি নামে হাজারখানেক Ref)
nest.cpp:6:22: note: use -ftemplate-depth=N to increase recursive template instantiation depth

চলার সময় n মাত্র ৩, অর্থাৎ program-টি ৩ ধাপেই থামত। কিন্তু compiler চালানোর আগে n জানে না, তাই depth<int>, depth<Ref<int>>, depth<Ref<Ref<int>>> … বানাতে বানাতে ১০২৪ ধাপে হাল ছেড়েছে। Dictionary passing বা erasure-এ এমন function একবারই compile হয়: খাতাটি চলার সময় এক ধাপ করে বড় হয় (Ref-এর খাতা, যার ভেতরে T-এর খাতা)। এই কারণেই Haskell polymorphic recursion মেনে নেয় (type লিখে দিতে হয়), আর সম্পূর্ণ monomorphizing compiler সাধারণত মানে না।

৪ · Uniform representation আর boxing — সব মান এক মাপের

অংশ ১-এর প্রথম প্রশ্ন ছিল মাপ। Dictionary passing >-এর সমস্যা মেটায়, কিন্তু মাপের সমস্যা মেটায় না: একটি কপি যদি Int (৮ byte) আর ১০০ byte-এর একটি record দুটোই নিতে চায়, register-এ কী রাখবে? সবচেয়ে সরল উত্তর হলো uniform representation: ভাষার প্রতিটি মানকে এক machine word-এ (৬৪-bit যন্ত্রে ৮ byte) আঁটানো। ছোট মান সরাসরি সেই word-এ, বড় মান heap-এ রেখে word-এ শুধু তার ঠিকানা। দ্বিতীয় কাজটিকে বলে boxing: মানকে একটি “বাক্সে” ভরে heap-এ রাখা।

OCaml এই পথের পরিচিত উদাহরণ (প্রচলিত বর্ণনা অনুযায়ী): প্রতিটি মান একটি word; integer-এর সবচেয়ে নিচের bit 1 রেখে চিহ্নিত করা হয়, তাই ৬৪-bit যন্ত্রে OCaml-এর int ৬৩-bit; আর pointer-এর নিচের bit 0. ফলে একই generic কোড যেকোনো মান কপি করতে পারে (সবই এক word), আর garbage collector নিচের bit দেখেই বোঝে কোনটি pointer. দাম হলো: float-এর মতো মান সাধারণত box করতে হয়, আর integer-এ প্রতিটি যোগে tag ঠিক রাখার ছোট বাড়তি কাজ।

সেই বাড়তি কাজটি হাতে হিসাব করে দেখুন। n সংখ্যাটি word-এ থাকে 2n + 1 হিসেবে। বাজারঘরের 996 টাকা তাই 1993, আর 60 টাকার delivery 121. দুটি word সরাসরি যোগ করলে 2114, যা জোড় সংখ্যা, অর্থাৎ ভুলভাবে একটি pointer-এর মতো দেখায়। তাই compiler যোগের পর একটি 1 বিয়োগ করে: (2a + 1) + (2b + 1) − 1 = 2(a + b) + 1, এখানে 2113, যা 1056-এর সঠিক রূপ। একটি বাড়তি নির্দেশ, বিনিময়ে প্রতিটি মান এক word আর GC-র জন্য স্পষ্ট চিহ্ন। Haat-এর RISC-V back end (পর্ব ৭২) এমন tag রাখে না, কারণ v1-এ generics নেই আর checker প্রতিটি মানের type আগেই জানে।

Java-ও একই পথে, তবে মিশ্রভাবে। Java-র generics শুধু reference type নেয়, তাই int-কে generic কোডে পাঠাতে হলে compiler তাকে Integer object-এ box করে (Java-র ভাষায় autoboxing). অংশ ৫-এর একই JDK-তে সত্যিকারের javap -c run-এ Integer q = bigger(2, 5);-এর bytecode-এ দুবার আছে invokestatic … Integer.valueOf:(I)Ljava/lang/Integer;: প্রতিটি সংখ্যাকে বাক্সে ভরা। একটি ArrayList<Integer>-এ দশ লাখ সংখ্যা মানে সাধারণত দশ লাখ আলাদা object, প্রতিটির নিজস্ব header; পর্ব ২৫-এর managed ভাষায় object-এর আকার আর boxing অংশে এর মাপ দেখেছেন। বিপরীতে C++-এর std::vector<long> monomorphization-এর কল্যাণে সংখ্যাগুলো পাশাপাশি রাখে, কোনো বাক্স ছাড়া।

মূল কথা

Uniform representation “মাপ” প্রশ্নের উত্তর দেয় (সব এক word), dictionary passing “কাজ” প্রশ্নের (খাতা), আর erasure (পরের অংশ) uniform representation-এর ওপর দাঁড়িয়ে বলে “type-এর আর দরকারই নেই”। Monomorphization একাই তিন প্রশ্নের উত্তর দেয়, কারণ প্রতিটি কপিতে type পুরোপুরি জানা।

৫ · Type erasure — Java আর TypeScript-এ type মুছে ফেলা

Type erasure মানে type checking শেষ হলে generic type-এর তথ্য মুছে ফেলা। Java-তে প্রতিটি type parameter তার সীমা (bound) দিয়ে বদলায়, সীমা না থাকলে Object দিয়ে; generic class-এর ঠিক একটি class file হয়; আর যেখানে মুছে-ফেলা type আর ব্যবহারকারীর প্রত্যাশিত type আলাদা, সেখানে compiler একটি cast বসায়। সত্যিকারের run: Eclipse Temurin JDK 21.0.13 (GPLv2 + Classpath Exception), javac আর javap -c:

class Box<T> {
    private T item;
    Box(T item) { this.item = item; }
    T get() { return item; }
    void set(T item) { this.item = item; }
}
// Erase.java-র main-এ: Box<String> b = new Box<>("tel"); String s = b.get();

~/haat $ javap -c Box
  T get();
    Code:
       0: aload_0
       1: getfield      #7                  // Field item:Ljava/lang/Object;
       4: areturn
~/haat $ javap -c Erase
      10: aload_1
      11: invokevirtual #14                 // Method Box.get:()Ljava/lang/Object;
      14: checkcast     #18                 // class java/lang/String
      17: astore_2

দুটি জিনিস দেখুন। Box-এর ভেতরে field-টি Ljava/lang/Object;, অর্থাৎ JVM-এর কাছে T বলে কিছু নেই। আর ডাকার জায়গায়, offset 14-এ, একটি checkcast java/lang/String: আমাদের কোডে কোনো cast লেখা ছিল না, compiler নিজে বসিয়েছে। Bound থাকলে মুছে-ফেলা type হয় সেই bound. static <T extends Comparable<T>> T bigger(T a, T b)-এর আসল descriptor একই run-এ: bigger:(Ljava/lang/Comparable;Ljava/lang/Comparable;)Ljava/lang/Comparable;, আর শরীরে a.compareTo(b) হয়েছে invokeinterface … Comparable.compareTo:(Ljava/lang/Object;)I: অর্থাৎ >-এর কাজটি এখানে চলছে Comparable interface-এর vtable-এর মতো dispatch দিয়ে। তবু সব তথ্য হারায় না: javap -v Box দেখায় class file-এ একটি Signature attribute আছে, যাতে <T:Ljava/lang/Object;>Ljava/lang/Object; আর ()TT; লেখা। এটি compiler আর reflection-এর জন্য, JVM-এর নির্দেশ চালানোর জন্য নয়। একই run-এ new ArrayList<String>().getClass() == new ArrayList<Integer>().getClass() ছাপল true, আর class-এর নাম শুধু java.util.ArrayList.

Cast কেন দরকার, আর কখন ব্যর্থ হয়? Java raw type রেখেছে (type argument ছাড়া Box), পুরোনো কোডের সঙ্গে মেলানোর জন্য। Raw type দিয়ে ভুল মান ঢোকানো যায়, শুধু একটি warning দিয়ে। এই অবস্থার নাম heap pollution. সত্যিকারের run:

        Box raw = b;              // raw type: generic checks off   (লাইন ১৩)
        raw.set(42);              // unchecked warning only         (লাইন ১৪)
        String t = b.get();       // the hidden cast fails here     (লাইন ১৫)

~/haat $ javac -Xlint:unchecked Erase.java
Erase.java:14: warning: [unchecked] unchecked call to set(T) as a member of the raw type Box
~/haat $ java Erase
tel
Exception in thread "main" java.lang.ClassCastException: class java.lang.Integer cannot be cast to class java.lang.String (…)
	at Erase.main(Erase.java:15)
10Box<String> b = new Box<>("tel");11String s = b.get();12System.out.println(s);13Box raw = b;14raw.set(42);15String t = b.get();
javac আর JVM-এর চোখে
b-এর type
b.item-এ
  1. Type checking, generics-সহ। javac জানে b একটি Box<String>, তাই T ↦ String বসিয়ে b.get() : String. এই ধাপে generics পুরোপুরি জীবিত।
  2. Erasure. Class Box-এ T মুছে Object: get-এর descriptor ()Ljava/lang/Object;. সব Box<X>-এর জন্য একটিই class file.
  3. Cast বসানো। Object ফেরত আসে, কিন্তু s-এর type String, তাই javac offset 14-এ checkcast String বসায়। চলার সময় JVM মানটির আসল class দেখে: "tel" সত্যিই String, তাই ঠিক আছে।
  4. Raw type দিয়ে ফাঁক। raw-এর type argument নেই, তাই set(42) কেবল একটি unchecked warning. চলার সময় set একটি Object নেয়, তাই Integer ঢুকে যায় কোনো error ছাড়া: heap pollution.
  5. দেরিতে ধরা। লাইন ১৫-এ আবার b.get(), আবার লুকানো checkcast String (offset 40), আর এবার আসল মান Integer: ClassCastException. বার্তা লাইন ১৫-এর, যেখানে কোডে কোনো cast লেখা নেই।
  6. শিক্ষা। Cast-গুলোই erasure-এর পাহারাদার: JVM-এর নিরাপত্তা ভাঙে না, কারণ ভুল type কখনো String হিসেবে ব্যবহৃত হয় না। কিন্তু ভুলের কারণ (লাইন ১৪) আর বার্তা (লাইন ১৫) আলাদা জায়গায়, ঠিক পর্ব ৩৩-এর শুক্রবারের ভুলের মতো।

Erasure-এর আরেকটি লুকানো কাজ হলো bridge method. final class Taka implements Comparable<Taka> লিখে শুধু compareTo(Taka) দিলে, সত্যিকারের javap -v দেখায় class-এ আরও একটি method আছে: public int compareTo(java.lang.Object), flags ACC_PUBLIC, ACC_BRIDGE, ACC_SYNTHETIC, যার শরীর checkcast Taka করে আসল compareTo(Taka)-কে ডাকে। কারণ erasure-এর পর interface চায় compareTo(Object), আর dynamic dispatch যেন ঠিক method-এ পৌঁছায়, তাই compiler একটি সেতু বানায়। পুরো প্রক্রিয়াটি ছোট আকারে:

# Erasure: Box<T> is compiled ONCE with T := Object; casts go to the call sites
prog = [  # (variable, declared static type, expression)
    ("b",   "Box<Str>", ("new", "tel")),
    ("s",   "Str",      ("get", "b")),          # Box<T>.get() returns T
    ("raw", "Box",      ("var", "b")),          # raw type: generic checks off
    ("_",   "Unit",     ("set", "raw", 42)),    # an Int slips into Box<Str>
    ("t",   "Str",      ("get", "b")),
]
types, code = {}, []
for var, ty, e in prog:                          # pass 1: erase + insert casts
    types[var] = ty
    if e[0] == "new":   code.append(("NEW_BOX", e[1]))
    elif e[0] == "var": code.append(("LOAD", e[1]))
    elif e[0] == "set": code.append(("BOX_SET", e[1], e[2]))
    elif e[0] == "get":
        code.append(("BOX_GET", e[1]))           # erased: returns Object
        arg = types[e[1]].partition("<")[2].rstrip(">")
        if arg: code.append(("CHECKCAST", arg))  # the compiler's hidden cast
    code.append(("STORE", var))
for i, ins in enumerate(code): print(f"{i:2} {' '.join(map(str, ins))}")

def class_of(v): return {str: "Str", int: "Int"}.get(type(v), "Box")
env, acc = {}, None; print("--- run ---")       # pass 2: run the erased code
for i, ins in enumerate(code):
    op = ins[0]
    if op == "NEW_BOX": acc = {"item": ins[1]}
    elif op == "LOAD": acc = env[ins[1]]
    elif op == "BOX_SET": env[ins[1]]["item"] = ins[2]; acc = None
    elif op == "BOX_GET": acc = env[ins[1]]["item"]
    elif op == "CHECKCAST" and class_of(acc) != ins[1]:
        print(f"{i:2} ClassCastException: {class_of(acc)} cannot be cast to {ins[1]}")
        break
    elif op == "STORE":
        env[ins[1]] = acc
        if ins[1] in ("s", "t"): print(f"{i:2} {ins[1]} = {acc!r}")

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

 0 NEW_BOX tel
 1 STORE b
 2 BOX_GET b
 3 CHECKCAST Str
 4 STORE s
 5 LOAD b
 6 STORE raw
 7 BOX_SET raw 42
 8 STORE _
 9 BOX_GET b
10 CHECKCAST Str
11 STORE t
--- run ---
 4 s = 'tel'
10 ClassCastException: Int cannot be cast to Str

প্রথম pass একটি ছোট “javac”: Box<Str> থেকে type argument পড়ে, প্রতিটি get-এর পরে CHECKCAST Str বসায়; raw Box-এর ক্ষেত্রে argument নেই, তাই কিছু বসায় না। দ্বিতীয় pass একটি ছোট “JVM”, যে type জানে না, শুধু মানের আসল class দেখে। নির্দেশ ৭-এ 42 নীরবে ঢুকল, ধরা পড়ল নির্দেশ ১০-এ: সত্যিকারের Java run-এর লাইন ১৪ আর ১৫-এর হুবহু প্রতিচ্ছবি।

TypeScript আরও এক ধাপ এগিয়ে: সে type মোছে, কিন্তু কোনো cast-ও বসায় না, কারণ JavaScript-এ চলার সময় পাহারা দেওয়ার মতো type-ই নেই (পর্ব ৩৩-এ এর প্রথম ঝলক দেখেছেন)। সত্যিকারের run: TypeScript 5.9.2 (Apache-2.0; tsc-এ telemetry নেই), tsc --strict --target es2022. উৎসে ছিল function bigger<T>(a: T, b: T, gt: (x: T, y: T) => boolean): T, class Box<T> আর শেষে new Box<string>(42 as any); tsc কোনো error দেয়নি। তৈরি JavaScript-এর প্রথম ১৫ লাইন হুবহু নিচের ব্লকের লাইন ২–১৬; বাকি অংশ চলার সময় কী টিকে থাকে তা পরীক্ষা করে:

// tsc 5.9.2 output of bigger.ts (--strict --target es2022): no <T> left
"use strict";
function bigger(a, b, gt) {
    return gt(a, b) ? a : b;
}
class Box {
    item;
    constructor(item) {
        this.item = item;
    }
    get() { return this.item; }
}
const qty = bigger(2, 5, (x, y) => x > y);
const word = bigger("chal", "dal", (x, y) => x > y);
const box = new Box("tel");
console.log(qty, word, box.get());
// --- what survives at run time? ---
console.log("bigger.length =", bigger.length);       // 3 value parameters, no T
const counts = new Box(7);                           // was Box<number>
console.log("Box<string> and Box<number> share a class:",
            box.constructor === counts.constructor);
const bad = new Box(42);          // TS source: new Box<string>(42 as any)
console.log("typeof bad.get() =", typeof bad.get());
try {
    bad.get().toUpperCase();
} catch (e) {
    console.log("caught", e.constructor.name, "far from the 'as any'");
}

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

5 dal tel
bigger.length = 3
Box<string> and Box<number> share a class: true
typeof bad.get() = number
caught TypeError far from the 'as any'

<T>, : T, : boolean সব উধাও; bigger-এর তিনটি parameter-ই মানের, type-এর নয়। Box<string> আর Box<number> একই class. TypeScript-এ generic ডাকের জন্য কোনো কপি, খাতা বা cast তৈরি হয় না; >-এর কাজ ভাষা নিজে চলার সময় মানের tag দেখে করে (JavaScript dynamic). তাই as any দিয়ে checker চুপ করালে কোনো checkcast-ও থাকে না, আর ভুলটি ধরা পড়ে আরও দূরে, যেখানে একটি সংখ্যার ওপর string-এর method ডাকা হয়। Java-র erasure অন্তত cast-এ থামায়; TypeScript-এর erasure থামায় শুধু যখন কোনো operation সত্যিই ব্যর্থ হয়।

Java-র ভেতরেই একটি মজার বৈপরীত্য আছে: array reified, generics erased. একটি String[] চলার সময় জানে তার উপাদান String, আর ভুল উপাদান রাখার চেষ্টা করলে JVM সঙ্গে সঙ্গে ArrayStoreException দেয় (Java-র covariant array-র এই ফাঁক পর্ব ৩৬-এর বিষয়)। কিন্তু List<String> জানে না সে কিসের list. দুটি একসাথে মেলালে নিরাপত্তা রাখা যায় না: new T[10] বানালে array-টি কোন উপাদান-type চলার সময় যাচাই করবে, তা কেউ জানে না। তাই Java-তে generic array তৈরি নিষিদ্ধ, আর ArrayList-এর ভেতরে আসলে একটি Object[] থাকে, যার প্রতিটি পড়া ডাকের জায়গার checkcast-এর ওপর নির্ভর করে।

৬ · Reification আর মিশ্র পথ — C#, Go আর Swift

Erasure-এর উল্টো হলো reified generics: চলার সময়ও type argument জানা থাকে। C# আর .NET এর প্রধান উদাহরণ। .NET 2.0 (২০০৫)-এ আসা generics-এর নকশা Andrew Kennedy আর Don Syme-এর PLDI ২০০১ প্রবন্ধে বর্ণিত। C#-এ (উদাহরণ, চালানো হয়নি) typeof(T) লেখা যায়, where T : new() শর্তে new T() লেখা যায়, আর List<int> আর List<string> চলার সময় আলাদা type. Java-তে এর কোনোটিই সরাসরি হয় না: new T() বা new T[10] compile error, আর যেকোনো Object সত্যিই List<String> কি না, তা চলার সময় যাচাই করা যায় না, কারণ সেই তথ্য আর নেই।

Reification-এর বাস্তবায়ন আকর্ষণীয়ভাবে মিশ্র। প্রচলিত বর্ণনা অনুযায়ী .NET-এর runtime reference type-এর (যেমন string, যেকোনো class) সব instantiation-এর জন্য একটিই machine code ভাগ করে নেয়, কারণ সবই এক মাপের pointer; আর value type-এর (int, double, struct) জন্য JIT আলাদা কপি বানায়, যাতে boxing লাগে না। অর্থাৎ pointer-এর জন্য uniform representation, সংখ্যার জন্য monomorphization, আর প্রতিটি object-এর সঙ্গে তার পূর্ণ type-তথ্য।

Go-ও মাঝামাঝি পথ নিয়েছে। Generics এসেছে Go 1.18-এ (মার্চ ২০২২)। Go দলের নকশা-দলিলে বর্ণিত কৌশলের নাম GC shape stenciling (dictionary-সহ): যে type-গুলোর memory-তে “আকার” একই (যেমন সব pointer type), তারা একটি কপি ভাগ করে, আর পার্থক্যগুলো (কোন method, কোন type) আসে একটি লুকানো dictionary argument থেকে। এটি monomorphization আর dictionary passing-এর একটি সংকর; বিস্তারিত সংস্করণভেদে বদলাতে পারে, তাই নির্দিষ্ট Go সংস্করণের দলিল দেখে নেবেন। Swift-ও (প্রচলিত বর্ণনা অনুযায়ী) ডিফল্টে witness table নামের খাতা দিয়ে একটি সাধারণ কপি চালায়, আর optimizer সুযোগ পেলে নির্দিষ্ট type-এর জন্য বিশেষ কপি (specialization) বানায়।

Parametric polymorphism-এর ধারণা এসেছে ML (১৯৭৩, Milner) আর CLU (১৯৭০-এর দশক, Barbara Liskov) থেকে; Ada ৮৩-তে generic unit ছিল। C++-এ template যোগ হয় ১৯৮০-এর দশকের শেষে (Stroustrup), আর মান হয় C++98-এ। Java-র generics এসেছে Java 5-এ (২০০৪), যার ভিত্তি ১৯৯৮ সালের GJ প্রস্তাব (Bracha, Odersky, Stoutamire, Wadler). GJ-এর লক্ষ্য ছিল পুরোনো library আর JVM না বদলে generics যোগ করা, আর সেই লক্ষ্যই erasure বেছে নেওয়ার প্রধান কারণ।

৭ · আপস — কোডের আকার, গতি আর separate compilation

কোনো কৌশল সব দিকে সেরা নয়। মূল আপসগুলো এক টেবিলে (গুণগত তুলনা, মাপা সংখ্যা নয়):

প্রশ্নMonomorphizationDictionary passingErasure + boxingReification (.NET)
কোডের আকারtype-প্রতি এক কপি (code bloat)এক কপি + ছোট খাতাএক কপিreference-এ এক, value-এ আলাদা
চলার গতিসবচেয়ে বেশি; inline আর বিশেষ নির্দেশপরোক্ষ ডাক; optimizer specialize করলে কম দামboxing আর cast-এর দামvalue type-এ বাক্স নেই
Separate compilationদুর্বল; শরীর লাগেভালোভালোভালো (JIT কপি বানায়)
চলার সময় type জানাকপির ভেতরে জানাখাতায় আংশিকনাহ্যাঁ
Polymorphic recursionসাধারণত না (Clang: ১০২৪-এ থামে)হ্যাঁহ্যাঁহ্যাঁ
উদাহরণ ভাষাC++, RustHaskell (GHC)Java, OCaml; TypeScript (cast-ও নেই)C#

বাজারঘরের দলের দৃষ্টিতে ভাবুন। দামের হিসাবের ভেতরের loop, যেখানে প্রতি সেকেন্ডে লাখো তুলনা হয়, সেখানে monomorphization-এর সরাসরি নির্দেশ লাভজনক। দোকানের plugin ব্যবস্থা, যেখানে অন্য দল পরে নতুন পণ্যের type যোগ করবে আর মূল কোড আবার compile করা যাবে না, সেখানে dictionary বা erasure-এর একটি compile-করা কপি অনেক সুবিধাজনক। আর কোনো সার্ভারে চলার সময় JSON থেকে আসা মানকে type দেখে আলাদা করতে হলে reification-এর type-তথ্য কাজে লাগে। তাই প্রশ্নটি কখনো “কোনটি সেরা” নয়, বরং “এই ভাষা কোন কাজের জন্য বেশি ব্যবহার হবে”।

সব কৌশলের একটি সাধারণ নিশ্চয়তা আছে: তারা type checker-এর রায় বদলায় না। Monomorphization-এর ক্ষেত্রে এটি একটি পরিচিত lemma থেকে আসে, যার পূর্ণ রূপ পর্ব ৩৮-এ (Type soundness — progress আর preservation).

দাবি ৩৭.১ — কপিও well-typed

যদি Γ, α ⊢ e : τ হয় (α একটি type variable, যা Γ-তে মুক্তভাবে নেই), তবে যেকোনো type T-এর জন্য Γ ⊢ [α ↦ T]e : [α ↦ T]τ. অর্থাৎ generic শরীর যাচাই পাস করলে প্রতিটি monomorphized কপিও যাচাই পাস করে, তাই কপিগুলো আলাদা করে যাচাই করার দরকার নেই।

প্রমাণের রূপরেখা (e-এর typing derivation-এর ওপর induction; discrete math কোর্সের induction দেখুন):

  1. T-Var: e = x আর (x : τ) পরিবেশে আছে। x যদি বাইরের নাম হয়, τ-তে α নেই (α Γ-তে মুক্ত নয়), তাই [α ↦ T]τ = τ. আর x যদি শরীরের ভেতরের নাম হয় (যেমন parameter a : α), substitution পরিবেশের সেই অংশেও ঘটে, তাই (x : [α ↦ T]τ) থাকে আর T-Var আবার খাটে।
  2. T-Int, T-Bool: type-এ α নেই, তাই substitution কিছু বদলায় না।
  3. T-Call: e = f(e1, e2), যেখানে f : (τ1, τ2) -> τ আর ei : τi. Induction hypothesis প্রতিটি premise-এ substitution দেয়; আর (τ1, τ2) -> τ-তে substitution মানে প্রতিটি অংশে substitution, তাই নিয়মটি আবার খাটে।
  4. বাকি নিয়ম (T-Add, T-If, T-Fn …) একইভাবে: প্রতিটি নিয়ম type-এর আকার দেখে, α কী তা দেখে না, আর substitution আকার অক্ষুণ্ণ রাখে। এটিই parametricity-র মূল ভাবনা। ∎

লক্ষ করুন, C++ template এই দাবির বাইরে: শর্ত না থাকায় generic শরীর আগে যাচাই হয় না, তাই প্রতিটি কপি আলাদা যাচাই হয়, আর bigger<Bag>-এর মতো কপি ব্যর্থ হতে পারে (অংশ ২)। Erasure-এর ক্ষেত্রে নিশ্চয়তাটি অন্য রূপে আসে: Java Language Specification (§4.12.2) অনুযায়ী heap pollution ঘটতে পারে মূলত তখনই, যখন program এমন কিছু করে যার জন্য compile-এর সময় unchecked warning আসে। অর্থাৎ unchecked warning-হীন program-এ লুকানো cast ব্যর্থ হওয়ার কথা নয়; warning-কে @SuppressWarnings দিয়ে চাপা দেওয়া মানে এই প্রতিশ্রুতি নিজের দায়িত্বে নেওয়া।

আরও গভীরে: বাস্তব compiler প্রায় কখনো একটি কৌশলে থামে না। GHC dictionary passing দিয়ে শুরু করে, কিন্তু optimizer গরম জায়গায় নির্দিষ্ট type-এর জন্য বিশেষ কপি বানায়, আর SPECIALIZE pragma দিয়ে programmer নিজেও তা চাইতে পারেন। উল্টো দিকে, monomorphizing compiler-এর code bloat কমাতে linker একই machine code-এর আলাদা কপি মিলিয়ে এক করতে পারে (identical code folding; যেমন lld-এর --icf). Whole-program ML compiler MLton পুরো program monomorphize করে বলে পরিচিত। আর Java-র Project Valhalla দীর্ঘদিন ধরে value class আর হয়তো ভবিষ্যতে primitive-এর ওপর generics আনার কাজ করছে, যা boxing-এর দাম কমাবে; চূড়ান্ত রূপ এখনো বদলাচ্ছে।

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

  • Java generics আর C++ template-এর মূল পার্থক্য? Java: erasure, এক class file, ডাকের জায়গায় cast, primitive-এ boxing; C++: monomorphization, type-প্রতি কপি, কোনো cast নেই।
  • Java-তে কেন new T() লেখা যায় না? Erasure-এর পর চলার সময় T কোন type, তা জানা নেই।
  • Type erasure-এর পর type safety কে রাখে? javac-এর বসানো checkcast; raw type বা unchecked cast থেকে heap pollution হলে সেই cast-এ ClassCastException.
  • Monomorphization-এর অসুবিধা? Code bloat, বেশি compile সময়, শরীর ছাড়া separate compilation কঠিন, polymorphic recursion অসম্ভব।
  • Type class-এর বাস্তবায়ন? Dictionary passing: শর্ত একটি লুকানো argument হয়, যাতে type-এর method-গুলোর table থাকে।

৮ · AI-এর যুগে generics-এর বাস্তবায়ন

Generics-এর ভেতরের কথা নিয়ে AI assistant-এর উত্তর প্রায়ই এক ভাষার নিয়ম অন্য ভাষায় চাপায়, আর bytecode বা IR “মনে থেকে” লেখে। এই বিষয়ে বারবার দেখা ভুল আর যাচাইয়ের উপায়:

AI-এর ভুলকীভাবে ধরবেন
“Java generics আর C++ template একই জিনিস” বা “C#-ও erasure করে”Java-তে javap -c দিয়ে checkcast খোঁজা; C++-এ -emit-llvm দিয়ে type-প্রতি কপি গোনা; C#-এর দাবি সংস্করণসহ দলিলে মেলানো
বানানো bytecode বা mangled নাম (যেমন ভুল descriptor)নিজে javap, clang -S -emit-llvm চালিয়ে আসল আউটপুট কপি করা
Error চুপ করাতে raw type, @SuppressWarnings("unchecked") বা as any-Xlint:unchecked আর --strict চালু রাখা; প্রতিটি suppress-এর পাশে কেন নিরাপদ তা লেখা
“Generics সবসময় zero-cost” বা “boxing-এর কোনো দাম নেই”ভাষা ধরে প্রশ্ন করা; Java-তে Integer.valueOf খোঁজা; গতি মাপতে দুই সংস্করণ চালিয়ে দেখা
Go বা Swift-এর বাস্তবায়ন নিয়ে নিশ্চিত, পুরোনো তথ্যনির্দিষ্ট সংস্করণের অফিসিয়াল নকশা-দলিল পড়া; বাস্তবায়ন সময়ের সঙ্গে বদলায়
নিজে বানানো monomorphizer-এ polymorphic recursion-এ অসীম loop বা কপির নামের সংঘর্ষসীমা আর cache রাখা; একই ইনপুটে dictionary-ভিত্তিক বাস্তবায়নের সঙ্গে differential test

AI-কে কাজে লাগাতে ভাষা, সংস্করণ আর যাচাইয়ের উপায় একসাথে চান:

আমি generics-এর বাস্তবায়ন শিখছি; ভাষা: Java 21 (javac/javap), C++20 (Clang 22), TypeScript 5.9. ১. নিচের generic কোডটি প্রতিটি ভাষার compiler কোন কৌশলে বানায় (monomorphization, erasure, dictionary passing), ভাষা ধরে আলাদা করে বলো: [এখানে আমার কোড] ২. কোনো bytecode, LLVM IR বা mangled নাম অনুমান করে লিখবে না; কোন command চালালে আমি নিজে দেখতে পাব (javap -c, clang -S -emit-llvm, tsc), শুধু তা বলো। ৩. কোথায় compiler লুকানো cast, boxing বা আলাদা কপি বসাবে, আর সেগুলোর চলার সময়ের দাম কী, তালিকা দাও। ৪. Error চুপ করাতে raw type, @SuppressWarnings বা as any প্রস্তাব করবে না; করলে কেন নিরাপদ তা প্রমাণসহ বলো।

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

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

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

প্র ০১Java কেন erasure বেছে নিয়েছিল, যখন C++-এর template আর গবেষণার ভাষাগুলোতে অন্য পথ জানা ছিল?

Java ১৯৯৫ সালে generics ছাড়াই এসেছিল, আর ২০০৪ সালে Java 5 আসার আগেই পৃথিবীতে বিপুল পরিমাণ Java কোড, library আর চালু JVM ছিল। নকশাকারদের সামনে কঠিন শর্ত ছিল: পুরোনো List আর নতুন List<String> যেন একসাথে চলে, পুরোনো compile-করা library নতুন কোড থেকে ডাকা যায়, আর JVM-এর নির্দেশমালা বদলাতে না হয়। ১৯৯৮ সালের GJ প্রস্তাব (Bracha, Odersky, Stoutamire, Wadler) এই লক্ষ্যকে বলেছিল “migration compatibility”, আর erasure সেই লক্ষ্যের সবচেয়ে সরল সমাধান: generic class-এর class file পুরোনো non-generic class file-এর মতোই দেখতে, শুধু বাড়তি Signature attribute-সহ (এই পর্বের javap -v run-এ যা দেখেছেন)।

এর দাম আজও Java বহন করছে। চলার সময় T জানা নেই, তাই new T(), new T[n] বা instanceof List<String> সরাসরি হয় না; বিকল্প হিসেবে Class<T> object হাতে করে পাঠাতে হয়। Primitive type generics-এ ঢোকে না, তাই Integer.valueOf-এর boxing (অংশ ৪-এর run), আর সংখ্যার বড় collection-এ memory আর গতির দাম। Raw type থেকে heap pollution, যার ভুল ধরা পড়ে দূরের একটি লুকানো cast-এ। Overload-এর একটি অদ্ভুত সীমাও আছে: void f(List<String>) আর void f(List<Integer>) একই class-এ রাখা যায় না, কারণ erasure-এর পর দুটির descriptor এক।

অন্য পথ কি সম্ভব ছিল? .NET পরে (২০০৫) দেখিয়েছিল যে runtime বদলে reified generics করা যায়, কিন্তু Microsoft তখন collection library-র নতুন generic সংস্করণ আলাদা namespace-এ এনেছিল, অর্থাৎ পুরোনো আর নতুন পাশাপাশি থাকল। Java সেই বিভাজন চায়নি। Monomorphization JVM-এর dynamic class loading আর separate compilation-এর সঙ্গে খাপ খায় না, কারণ নতুন type যেকোনো সময় load হতে পারে।

মূল উপলব্ধি: বাস্তবায়নের কৌশল প্রায়ই প্রযুক্তি নয়, পরিস্থিতি ঠিক করে। Erasure ছিল “পুরোনো কোড ভাঙবে না” প্রতিশ্রুতির দাম, আর সেই দাম পরিশোধ হচ্ছে boxing, cast আর হারানো type-তথ্যে।

প্র ০২C++ আর Rust-এ monomorphization-এর code bloat বাস্তবে কতটা বড় সমস্যা, আর compiler ও linker তা কমায় কীভাবে?

সমস্যাটি সত্যিকারের, তবে প্রায়ই অতিরঞ্জিত। অংশ ২-এর run-এ দুটি জিনিস দুই দিকে টানে। -O0-এ তিন type-এর জন্য তিনটি আলাদা bigger; ১০টি type আর ৫০টি generic function হলে কপি ৫০০ পর্যন্ত যেতে পারে, আর বড় generic library (container, algorithm, serialization) ব্যবহারে executable-এর আকার আর compile-এর সময় চোখে পড়ার মতো বাড়ে। কিন্তু -O2-এ ছোট কপিগুলো inline হয়ে পুরোপুরি মিলিয়ে গেছে; ছোট generic function-এর ক্ষেত্রে আকার প্রায়ই হাতে-লেখা কোডের সমান।

Toolchain কয়েক স্তরে লড়ে। প্রথমত, linkonce_odr/comdat (run-এ দেখেছেন): একই instantiation দশটি object file-এ থাকলেও linker একটি রাখে। দ্বিতীয়ত, identical code folding: bigger<long> আর bigger<Taka>-এর machine code যদি byte-ধরে এক হয় (Taka একটি long-এর মাপ, তুলনাও একই), কিছু linker (যেমন lld-এর --icf) দুটিকে এক করতে পারে, যদিও function-এর ঠিকানার সমতা নিয়ে সতর্কতা লাগে। তৃতীয়ত, programmer-এর কৌশল: C++-এ extern template দিয়ে একটি ফাইলেই instantiation করানো, বা generic শরীরের বড় অংশ একটি non-generic সহায়ক function-এ সরানো (Rust-এ প্রচলিত “inner function” ধাঁচ, যেখানে generic বাইরের অংশ শুধু রূপান্তর করে আর আসল কাজ একটি কপিতে)। চতুর্থত, compile-সময়ের জন্য C++20 module, যা header বারবার parse করার খরচ কমায়, যদিও instantiation-এর খরচ থেকেই যায়।

Embedded যন্ত্রে, যেখানে flash memory কয়েক কিলোবাইট, code bloat সত্যিই সিদ্ধান্ত বদলায়; সেখানে অনেক দল Rust-এ dyn Trait বা C-তে function pointer বেছে নেয়, ইচ্ছা করে dictionary-ধাঁচে।

মূল উপলব্ধি: monomorphization গতি কেনে কোডের আকার আর compile-সময় দিয়ে। কতটা দাম, তা নির্ভর করে instantiation-এর সংখ্যা, শরীরের আকার আর optimizer-এর ওপর; অনুমান না করে আসল build-এর symbol আর আকার মেপে দেখাই নিরাপদ।

প্র ০৩Dictionary passing পরোক্ষ ডাকের কারণে ধীর হতে পারে। তাহলে Haskell-এর মতো ভাষা কীভাবে দ্রুত চলে?

সরল dictionary passing-এ প্রতিটি > একটি memory read আর একটি পরোক্ষ ডাক (অংশ ৩-এর stepper-এর ধাপ ৩–৪)। পরোক্ষ ডাক নিজে খুব ব্যয়বহুল নয়, কিন্তু আসল ক্ষতি হলো optimizer অন্ধ হয়ে যায়: কোন function ডাকা হচ্ছে না জানলে inline করা যায় না, আর inline না হলে constant folding, loop optimization (পর্ব ৬৫–৬৭) কিছুই খাটে না। Int-এর একটি তুলনা যেখানে একটি নির্দেশ হতে পারত, সেখানে পুরো একটি function call হয়।

GHC কয়েকভাবে এর সমাধান করে। প্রথমত, ডাকার জায়গায় type জানা থাকলে খাতাটি একটি ধ্রুবক; optimizer তখন d.gt-কে সরাসরি int_gt-এ বদলাতে পারে, তারপর inline করতে পারে। এটি আসলে ডাকের জায়গায় monomorphization. দ্বিতীয়ত, specialization: optimizer একটি generic function-এর Int-বিশেষ কপি বানায়, আর SPECIALIZE pragma দিয়ে programmer নিজে বলে দিতে পারেন কোন type-এ কপি চাই। তৃতীয়ত, module-এর সীমানা পেরিয়ে inline করার জন্য GHC interface ফাইলে কিছু function-এর শরীর (unfolding) রাখে, যা monomorphization-এর “শরীর লাগে” শর্তের নরম রূপ।

ফলে বাস্তবে একটি মিশ্র ব্যবস্থা দাঁড়ায়: ডিফল্ট পথ dictionary, যা separate compilation আর polymorphic recursion রক্ষা করে; আর গরম পথে specialization, যা গতি ফেরায়। Swift আর .NET-ও প্রায় একই দর্শনে চলে, শুধু শুরুর বিন্দু আলাদা। উল্টো দিকে, monomorphization-ভিত্তিক Rust-ও প্রয়োজনে dyn দিয়ে dictionary-ধাঁচে নামে।

মূল উপলব্ধি: “dictionary ধীর, monomorphization দ্রুত” একটি সরলীকরণ। ভালো compiler দুটির মাঝে চলাচল করে: যেখানে type জানা, সেখানে বিশেষ কপি; যেখানে জানা নয়, সেখানে খাতা।

প্র ০৪Go প্রায় এক দশক generics ছাড়া চলেছে, আর শেষে একটি মাঝামাঝি বাস্তবায়ন বেছে নিয়েছে। এই ইতিহাস থেকে ভাষা নকশা সম্পর্কে কী শেখা যায়?

Go ২০০৯ সালে প্রকাশ্যে আসে, আর শুরু থেকেই generics নিয়ে প্রশ্ন ছিল। Go দলের Russ Cox ২০০৯ সালের একটি blog লেখায় সমস্যাটিকে “generic dilemma” বলে বর্ণনা করেছিলেন বলে পরিচিত: generics না রাখলে programmer ধীর হন (একই কোড বারবার লেখা বা interface{} আর cast), C++-এর মতো monomorphization করলে compiler ধীর হয় আর binary বড় হয়, আর Java-র মতো boxing করলে program ধীর চলে। Go-র দর্শনে দ্রুত compile একটি কেন্দ্রীয় লক্ষ্য ছিল, তাই কোনো পথই সহজে গ্রহণযোগ্য মনে হয়নি।

দীর্ঘ আলোচনা আর একাধিক প্রস্তাবের পর Go 1.18 (২০২২) type parameter আনে। বাস্তবায়ন-কৌশল হিসেবে নকশা-দলিল বর্ণনা করে GC shape stenciling: একই memory-আকারের type একটি কপি ভাগ করে (সব pointer একটি shape), আর বাকি তথ্য dictionary থেকে আসে। এটি তিন কোণের মাঝখানে একটি বিন্দু: কপির সংখ্যা সীমিত (compile সময় রক্ষা), সংখ্যার মতো ছোট type-এ আলাদা কপি (boxing এড়ানো), আর pointer type-এ খাতা (কিছুটা পরোক্ষতা)। বিভিন্ন সময়ে performance নিয়ে আলোচনা হয়েছে, আর বাস্তবায়ন সংস্করণভেদে উন্নত হচ্ছে বলে Go দল জানিয়েছে।

শিক্ষা কয়েকটি। এক, ভাষার feature-এর অর্থ (type checking-এর নিয়ম) আর বাস্তবায়ন আলাদা; Go-র spec বাস্তবায়ন-কৌশল বাধ্য করে না, তাই পরে বদলানো যায়। দুই, দেরিতে feature যোগ করা কঠিন কিন্তু অসম্ভব নয়; শর্ত হলো পুরোনো কোড না ভাঙা, যা Java-র অভিজ্ঞতারই প্রতিধ্বনি। তিন, “সেরা” কৌশল নির্ভর করে ভাষা কী নিয়ে গর্ব করে: Go-র ক্ষেত্রে compile গতি, Rust-এর ক্ষেত্রে চলার গতি।

মূল উপলব্ধি: generics-এর বাস্তবায়ন একটি ত্রিভুজের আপস: programmer-এর সময়, compiler-এর সময় আর চলার সময়। প্রতিটি ভাষা তার মূল্যবোধ অনুযায়ী ত্রিভুজের ভেতরে একটি বিন্দু বেছে নেয়।

প্র ০৫Haat-এ generics যোগ করলে (বর্ধিত রূপ) interpreter, bytecode VM আর RISC-V back end-এর জন্য কোন বাস্তবায়ন সবচেয়ে মানানসই?

প্রথমে type checker. T: Ord শর্তসহ generic শরীর একবার যাচাই হবে (দাবি ৩৭.১-এর কারণে কপি আলাদা যাচাই লাগবে না), আর প্রতিটি ডাকে T অনুমান হবে পর্ব ৩৫-এর unification দিয়ে। Syntax-এ একটি ফাঁদ আছে: Haat-এ < একটি তুলনা-operator, তাই bigger<Int>(2, 5) parser-এর কাছে bigger < Int > (2, 5)-ও হতে পারে। Rust এই কারণে expression-এ bigger::<Int>(…) (turbofish) লেখায়; Haat-এ সহজ সমাধান হলো ডাকের জায়গায় type argument কখনো না লিখে সবসময় অনুমান করা।

Tree-walking interpreter (পর্ব ৫৬)-এ প্রায় কিছুই করতে হয় না: Python-এ লেখা interpreter-এর প্রতিটি মান আগে থেকেই একটি Python object, অর্থাৎ uniform representation; আর > চলার সময় মানের ধরন দেখে Int বা Str তুলনা করতে পারে। এটি আসলে TypeScript-এর মতো erasure: checker-এর পরে type মুছে ফেলা। Bytecode VM (পর্ব ৫৮–৫৯)-এর ADD আজ checker-এর নিশ্চয়তার ওপর নির্ভর করে, কারণ v1-এ > শুধু Int. Generic শরীরে T অজানা, তাই দুটি পথ: VM-এ মানের tag দেখে তুলনা (erasure + dynamic tag), অথবা compiler প্রতিটি T-এর জন্য আলাদা bytecode function বানাবে (monomorphization), যেখানে Int-এর কপিতে সংখ্যা-তুলনা আর Str-এর কপিতে string-তুলনার নির্দেশ।

RISC-V back end (পর্ব ৭২)-এ একটি সুখবর: Haat-এর Int ৮ byte আর Str একটি ৮ byte-এর pointer, Bool-ও একটি register-এ আঁটে। অর্থাৎ সব মান এক register-এ, uniform representation বিনা খরচে। তুলনার জন্য dictionary (একটি function pointer) দেওয়া সহজ, কিন্তু গতির জন্য monomorphization ভালো, কারণ Int-এর কপিতে bigger একটি blt/bge-এর মতো নির্দেশে নেমে আসে। Haat program ছোট আর পুরো program একসাথে compile হয়, তাই separate compilation-এর অসুবিধা এখানে নেই।

মূল উপলব্ধি: একই ভাষার বিভিন্ন back end ভিন্ন কৌশল নিতে পারে, যতক্ষণ checker-এর অর্থ এক থাকে। Haat-এর জন্য যুক্তিসঙ্গত পছন্দ: interpreter-এ erasure, আর native back end-এ monomorphization.

অনুশীলন

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

  1. Monomorphizer বড় করুন (বাস্তবায়ন): অংশ ২-এর monomorphizer শুধু program-এর সরাসরি ডাক দেখে। এবার একটি generic function bigger3<T>(a, b, c) যোগ করুন, যার শরীর bigger<T>-কে দুবার ডাকে। একটি worklist দিয়ে এমনভাবে লিখুন যাতে bigger3<Str> চাইলে bigger<Str>-ও নিজে থেকে তৈরি হয়, আর কোনো কপি দুবার না হয়। Roots: bigger3<Str>, bigger<Int>, bigger3<Int>.
    TEMPLATES = {   # generic function -> (body template, generic functions it calls)
        "bigger":  ("def bigger__{T}(a, b):\n    return a if {GT}(a, b) else b", []),
        "bigger3": ("def bigger3__{T}(a, b, c):\n    return bigger__{T}(bigger__{T}(a, b), c)",
                    ["bigger"]),
    }
    def monomorphize(roots):
        done, work, out = set(), list(roots), []
        while work:
            name, T = work.pop()
            if (name, T) in done: continue           # cache hit
            done.add((name, T))
            body, callees = TEMPLATES[name]
            out.append(body.format(T=T, GT=GT_FOR[T]))
            work += [(c, T) for c in callees]        # callee at the SAME type
        return out

    সত্যিকারের run (Python 3.14; GT_FOR, int_gt, str_gt অংশ ২-এর মতো):

    generated: ['bigger3__Int', 'bigger3__Str', 'bigger__Int', 'bigger__Str']
    tel 1040

    চারটি কপি, কোনোটি দুবার নয়: bigger<Int> একবার root হিসেবে আর একবার bigger3<Int>-এর ভেতর থেকে চাওয়া হয়েছে, কিন্তু done সেট দ্বিতীয়টি আটকেছে। শেষ লাইন: bigger3__Str("ata", "tel", "dal") = tel, আর bigger3__Int(996, 1040, 60) = 1040. লক্ষ করুন, worklist-এ callee যায় একই T নিয়ে; শরীর যদি bigger<Ref<T>> ডাকত (polymorphic recursion), loop কখনো শেষ হতো না, তাই বাস্তব compiler-এর মতো একটি গভীরতার সীমা লাগত।

  2. ভুল খুঁজুন (erasure): একজন শিক্ষার্থী static <T extends Comparable<T>> T bigger(T a, T b) { return a.compareTo(b) > 0 ? a : b; }-এর erased রূপ লিখেছেন: static Object bigger(Object a, Object b), শরীরে a.compareTo(b), আর ডাকার জায়গায় Integer q = bigger(2, 5);-এর জন্য কোনো cast নেই। দুটি ভুল খুঁজুন, আর সঠিক রূপ বলুন।
    • ভুল ১ — erasure-এর লক্ষ্য: bound থাকলে T মুছে হয় তার bound, Object নয়। Object-এ compareTo নেই, তাই শিক্ষার্থীর রূপ নিজেই type-ভুল। সত্যিকারের javap -c-এ descriptor: bigger:(Ljava/lang/Comparable;Ljava/lang/Comparable;)Ljava/lang/Comparable;, আর শরীরে invokeinterface … Comparable.compareTo:(Ljava/lang/Object;)I.
    • ভুল ২ — cast নেই: ফেরত type Comparable, কিন্তু q একটি Integer; javac তাই ডাকের পরে cast বসায়। আসল bytecode: invokestatic … Integer.valueOf:(I)Ljava/lang/Integer; (দুবার, 2 আর 5-এর boxing), তারপর invokestatic … bigger:(…)Ljava/lang/Comparable;, তারপর checkcast java/lang/Integer. String-এর ডাকে একইভাবে checkcast java/lang/String.

    সংশোধিত রূপ: static Comparable bigger(Comparable a, Comparable b), আর প্রতিটি ডাকে box + call + checkcast. লক্ষ করুন, এখানে compareTo-এর dispatch interface দিয়ে, অর্থাৎ Java erasure-এর সঙ্গে অংশ ৩-এর মতো একটি “খাতা” ব্যবহার করছে, তবে খাতাটি object-এর ভেতরে (vtable), আলাদা argument নয়।

  3. গুনে বলুন (trace): template <typename T> T bigger(T a, T b) থাকলে নিচের পাঁচটি function-এর জন্য Clang -O0-এ bigger-এর কয়টি কপি বানাবে, আর তাদের mangled নাম কী? f1: bigger(2, 5), f2: bigger(2L, 5L), f3: bigger<int>(2, 5), f4: bigger(2.0, 5.0), f5: bigger('a', 'b').

    চারটি কপি: int, long, double আর char; f3 একই int কপি ব্যবহার করে। সত্যিকারের run (Clang 22.1.8, -g0 -O0 -S -emit-llvm, define-এর নামগুলো):

    @_Z2f1v
    @_Z6biggerIiET_S0_S0_
    @_Z2f2v
    @_Z6biggerIlET_S0_S0_
    @_Z2f3v
    @_Z2f4v
    @_Z6biggerIdET_S0_S0_
    @_Z2f5v
    @_Z6biggerIcET_S0_S0_

    Itanium C++ ABI-এর mangling-এ i = int, l = long, d = double, c = char; I…E-এর ভেতরে template argument. 2L-এর type long, তাই int থেকে আলাদা কপি; আর 'a' C++-এ char (C-তে character literal-এর type int, কিন্তু এখানে প্রশ্ন C++-এর)। পাঁচ ডাক, চার কপি।

  4. আউটপুট অনুমান করুন: (ক) Java 21-এ new ArrayList<String>().getClass() == new ArrayList<Integer>().getClass() কী ছাপবে? (খ) TypeScript-এর function bigger<T>(a: T, b: T, gt: (x: T, y: T) => boolean): T compile করে JavaScript-এ bigger.length কত? (গ) অংশ ৩-এর dictionary কোডে best_of_three(ORD_STR, "ata", "tel", "dal") চালানোর পর lookup-এর সংখ্যা কত বাড়ে? (ঘ) Clang -O2-এর IR-এ _Z6biggerIlET_S0_S0_ নামের define থাকবে কি?
    • (ক) true, আর getClass().getName() ছাপে java.util.ArrayList (সত্যিকারের JDK 21.0.13 run). Erasure: একটিই class.
    • (খ) 3 (সত্যিকারের tsc 5.9.2 + JavaScript run). T কোনো argument হয়ে টেকে না; শুধু a, b, gt.
    • (গ) ২ বাড়ে, ৩ থেকে ৫: best_of_three নিজে কোনো lookup করে না, শুধু খাতাটি দুটি bigger ডাকে এগিয়ে দেয়। ফল tel.
    • (ঘ) না। সত্যিকারের -O2 run-এ শুধু best_qty, best_rate, best_bill, best_qty2 আর operator>; কপিটি inline হয়ে llvm.smax.i64-এ মিশে গেছে। Monomorphization-এর কপি optimizer-এর কাছে সাধারণ function, তাই তাকে মুছে ফেলাও সাধারণ ব্যাপার।

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

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

ক্রমJava-তে Box<String> b = new Box<>("tel"); String s = b.get(); লিখলে compiler আর JVM যে কাজগুলো করে, সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. javac generics-সহ type check করে: T ↦ String বসিয়ে b.get() : String
  2. Box class-এ T মুছে Object করা হয়; get()-এর descriptor হয় ()Ljava/lang/Object;
  3. ডাকের পরে javac একটি checkcast String বসায়
  4. JVM invokevirtual দিয়ে get চালায়, ফেরত পায় একটি Object
  5. JVM checkcast-এ মানের আসল class যাচাই করে, তারপর s-এ রাখে

C++-এ template <typename T> T bigger(T a, T b) long, double আর একটি struct-এ ডাকলে Clang -O0-এ কী তৈরি করে?

  • একটি function, যা চলার সময় type দেখে তুলনা করে
  • প্রতিটি type-এর জন্য আলাদা function, mangled নামে type সহ
  • একটি function আর প্রতিটি type-এর জন্য একটি লুকানো dictionary argument
  • একটি Object-ভিত্তিক function, আর ডাকের জায়গায় cast

Java 21-এ javap -c একটি ডাকের পরে invokevirtual Box.get:()Ljava/lang/Object; আর তারপর checkcast java/lang/String দেখায়, যদিও উৎস-কোডে কোনো cast লেখা নেই। কেন?

  • javap নিজে নিরাপত্তার জন্য cast যোগ করে দেখায়
  • JVM-এর JIT চলার সময় cast যোগ করে
  • Erasure-এর পর get() Object ফেরত দেয়, তাই javac প্রত্যাশিত type-এ cast বসায়
  • Box<String>-এর জন্য আলাদা class file তৈরি হয়েছে, cast তার অংশ

একটি generic function depth<T>(x: T, n) নিজেকে depth<Ref<T>> হিসেবে ডাকে (polymorphic recursion). C++-এ Clang 22 আর dictionary passing-ভিত্তিক একটি বাস্তবায়নে কী হয়?

  • C++ compile error (instantiation গভীরতা ১০২৪ ছাড়িয়েছে); dictionary passing-এ একবারই compile হয়ে চলে
  • দুটোতেই ঠিকঠাক চলে, কারণ n ছোট হলে recursion থামে
  • C++ চলে, কিন্তু dictionary passing অসীম খাতা বানাতে গিয়ে compile-এ আটকে যায়
  • দুটোতেই type error, কারণ polymorphic recursion type-ভুল

Dictionary passing-এর খাতা আর OOP-এর vtable-এর মধ্যে মূল পার্থক্য কোনটি?

  • খাতায় function থাকে, vtable-এ থাকে data
  • vtable চলার সময় তৈরি হয়, খাতা compile-এর সময়
  • খাতা শুধু inheritance-এর জন্য ব্যবহার হয়
  • vtable আসে object-এর ভেতর থেকে, খাতা type থেকে আলাদা argument হিসেবে; তাই খাতা মান ছাড়াও কাজ করে

একটি generic library শুধু compile-করা রূপে (উৎস-কোড ছাড়া) বিতরণ করতে হবে, আর ব্যবহারকারী নিজের নতুন type দিয়ে generic function ডাকবেন। কোন কৌশল সবচেয়ে বেশি অসুবিধায় পড়ে?

  • Erasure
  • Monomorphization
  • Dictionary passing
  • Reification (.NET-এর মতো)

TypeScript 5.9-এ const bad = new Box<string>(42 as any); bad.get().toUpperCase(); — tsc --strict আর চলার সময় কী ঘটে?

  • tsc একটি type error দেয়, তাই JavaScript তৈরি হয় না
  • চলার সময় Box-এর constructor-এ একটি cast ব্যর্থ হয়
  • tsc চুপ থাকে; চলার সময় toUpperCase-এর জায়গায় TypeError
  • "42" ছাপা হয়, কারণ JavaScript সংখ্যাকে string বানিয়ে নেয়

শব্দকোষ

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

মনে রাখুন

  1. Type checking generic শরীর একবার যাচাই করে (T-TAbs, T-TApp); কিন্তু machine code-এর মাপ আর নির্দেশের প্রশ্নের উত্তর দেয় বাস্তবায়ন-কৌশল।
  2. Monomorphization (C++, Rust): type-প্রতি কপি, দ্রুত আর inline-যোগ্য; দাম code bloat, শরীর লাগে, polymorphic recursion চলে না।
  3. Dictionary passing (Haskell): এক কপি + type-প্রতি খাতা লুকানো argument-এ; separate compilation ভালো, পরোক্ষ ডাকের দাম, optimizer specialize করে।
  4. Erasure (Java): T মুছে bound বা Object, ডাকের জায়গায় checkcast, primitive-এ boxing; raw type থেকে heap pollution আর দেরিতে ClassCastException. TypeScript cast-ও বসায় না।
  5. Reification (C#) চলার সময় type রাখে; Go-র GC shape stenciling আর Swift-এর specialization মাঝামাঝি পথ।

পরের পর্বে: পর্ব ৩৮ (Type soundness — progress আর preservation). “Well-typed program ভুল পথে যায় না” কথাটির নির্ভুল অর্থ, একটি ছোট ভাষার জন্য পূর্ণ প্রমাণ, আর এমন একটি TypeScript program যা tsc পেরিয়েও চলার সময় ভেঙে পড়ে।

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

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