Polymorphism — একটা interface, কয়টা implementation, আর খরচ কত

আগে এটা বুঝি

Module-এর driving question-এর শেষ অংশে এলাম: Python আর Rust — নিচে পার্থক্য কোথায়? চার লেসনে আমরা দেখলাম semantics কীভাবে গণিতে লেখা হয়, টাইপ কখন check হয়, inference কীভাবে annotation-এর বোঝা কমায়। আজকের প্রশ্নটা সবচেয়ে engineering-flavored: একই অপারেশন অনেক টাইপে চলবে — সেই “অনেক”-টা implement করার কয়টা উপায়, আর প্রতিটার runtime খরচ ঠিক কত?

আমরা সবাই polymorphism শব্দটা জানি, কিন্তু বেশিরভাগ course-এ সেটা শেখানো হয় OOP-চ্যাপ্টারে — যেন polymorphism মানেই inheritance আর virtual method। ইতিহাসটা উল্টো: Strachey 1967-এ polymorphism- এর দুই রূপ নাম দিলেন parametric আর ad-hoc — generic container আর overloaded function — অথচ OO-র subtype-polymorphism তখন mainstream-এই ছিল না। অর্থাৎ আজ যেটাকে “polymorphism” বলে সবাই বোঝে, সেটা ঐতিহাসিকভাবে তিন ভাইয়ের সবচেয়ে ছোটটা।

আর প্রশ্নের সবচেয়ে মজার অংশটা হলো খরচ। একটা sort function int-এর উপরে চলুক বা string-এর উপরে — machine level-এ ঠিক কী ঘটছে? Compile-time-এ দুইটা আলাদা machine-code কপি তৈরি হয় (monomorphisation)? নাকি একটাই কপি দুই data-তে চলে (erasure)? নাকি runtime-এ একটা table ঘেঁটে সঠিক function খোঁজা হয় (vtable)? উত্তরগুলো ভিন্ন, আর performance-এর পার্থক্য measurable — আজ assembly খুলে প্রমাণ করব, assembly module-এর reading-compiler-output skill-টা কাজে লাগবে।

আজকের প্রশ্ন তিনটা: (১) তিন ধরনের polymorphism ঠিক কী promise করে — এবং কোনটা কোন promise দেয় না? (২) generics-এর “zero-cost abstraction” দাবিটা ঠিক কোথায় সত্যি, কোথায় বিক্রির কৌশল? (৩) virtual dispatch-এর প্রতিটা call-এ ঠিক কত instruction বাড়তি, আর সেই খরচের আসল বড় অংশ কি cycle না অন্য কিছু?

মূল ধারণা

তিনটা রূপ — তিনটা ভিন্ন promise

	Parametric	Ad-hoc	Subtype
মূল idea	একটা কোড, সব টাইপে হুবহু একই আচরণ	প্রতি টাইপে (বা জুটিতে) আলাদা কোড, statically বাছাই	hierarchy-তে upward substitution, runtime-এ বাছাই
ভাষা-construct	generics/templates (`List<T>`, `fn max<T>`)	overloading, typeclasses, traits	inheritance + virtual method
টাইপ-relationship	∀α — universal	নাম-অনুযায়ী সীমাবদ্ধ set	Liskov substitutability
Runtime খরচ	monomorphised: শূন্য / erased: boxing	শূন্য বা dictionary-passing	vtable indirection
কোথায় resolve হয়	compile time	compile time	runtime

তিনটার প্রতিশ্রুতি ভিন্ন — আর এখানেই বেশিরভাগ confusion:

Parametric promise: “এই function টাইপ নিয়ে কিছু জানে না।” identity : ∀α. α → α ফল হিসেবে argument ছাড়া আর কিছুই দিতে পারে না — টাইপ-নিরপেক্ষ হওয়াটাই তার শক্তি ও সীমা। এই theorem- টার নাম parametricity (“theorems for free”)।
Ad-hoc promise: “এই নামটা এই টাইপগুলোর জন্য বৈধ, প্রতিটার জন্য আলাদা definition আছে।” + int-এ যোগ, string-এ concat — behavior ভিন্ন, নাম shared। Compile-time-এই exact version select হয়।
Subtype promise: “যে-কোনো subclass-instance superclass-এর জায়গায় বসবে, আর সঠিক override চলবে।” বাছাই এখানে runtime-এ — value-র ভেতরের tag দেখে।

Haskell typeclass আর Rust trait — দুই জগতের ad-hoc

Typeclass/trait প্রথম দেখায় parametric-এর মতো (sort : Ord a => [a] -> [a]), কিন্তু পার্থক্য সূক্ষ্ম ও গুরুত্বপূর্ণ: constraint (Ord) মানে function টাইপ জানে, এবং প্রতিটা instance-এর জন্য আলাদা code/dictionary থাকে — ঠিক overloading-এর organized রূপ। Cardelli-Wegner taxonomy-তে bounded quantification-এর এই মিশ্র রূপটাই আধুনিক ভাষায় “ad-hoc, statically resolved”। Rust-এর trait object (dyn Trait) তখন subtype-জাতীয় dynamic dispatch-এ চলে যায় — এক ভাষাতেই দুই জগৎ।

Parametric-এর দুই বাস্তবায়ন — এক কপি বনাম কপি-কপি

Generic function-কে machine code বানাতে হলে একটা সিদ্ধান্ত নিতেই হয়: টাইপ-parameter-এর জায়গায় কী বসবে?

Monomorphisation (Rust, Swift, C++ templates): প্রতিটা concrete টাইপের জন্য আলাদা specialized copy generate হয়। scale::<u32> আর scale::<f64> দুইটা আলাদা function — imul একটাতে, mulsd অন্যটাতে। Runtime খরচ শূন্য; দাম দিতে হয় compile time আর binary size-এ (code bloat)।

Type erasure (Java generics, Go interfaces, Haskell): একটাই compiled copy, যেটা uniform representation-এর উপর চলে — সব value একই shape-এর (pointer/tagged)। Primitive int-এর জন্য Java- তে দাঁড়ায় boxing (ArrayList<Integer>-এ প্রতিটা int heap-object), আগের লেসনের tag-বহনের বিলটা এখানেই ফেরত আসে। দাম runtime-এ, লাভ compile speed আর compact code।

Ad-hoc-এর resolution — সব কটা compile-time

Overloading: compiler argument-এর টাইপ দেখে exact overload বাছে (static binding) — call-site-এ direct call। Typeclasses: প্রতিটা instance একটা dictionary (function-pointer-দের record) — GHC concrete টাইপ জানলে dictionary specialize করে direct call, না জানলে dictionary-pass (runtime indirection)। Rust trait generic: monomorphised; dyn Trait: fat-pointer-via-vtable।

Subtype-এর resolution — runtime table

Virtual dispatch-এর mechanical ধাপ (hood section-এ assembly পর্যন্ত):

Object-এর শুরুতে থাকা vptr পড়ো (pointer chase)।
Method-এর fixed slot-index ধরে vtable-এ ঢোকো।
Target address পড়ে indirect call।

প্রতিটা ধাপের খরচ ছোট (কয়েক cycle), কিন্তু আসল দাম indirect-এর পেছনে: compiler target address compile-time-এ জানে না, তাই inline করতে পারে না — আর modern CPU-তে inlining-হারানোর খরচ indirect-call-এর চেয়ে অনেক বড় হতে পারে (optimization cascade থেমে যায়)। JIT-রা এজন্যই devirtualization-এর যুদ্ধ করে।

ভেতরে কী ঘটছে

Vtable anatomy — object-এর পেছনের ছক

Square object (heap):              Square-এর vtable (read-only segment):
┌─────────────────┐               ┌────────────────────────────┐
│ vptr ───────────┼─────────────▶ │ slot 0: &Square::area      │
├─────────────────┤               ├────────────────────────────┤
│ side: 2.0       │               │ slot 1: &Square::~Square   │
└─────────────────┘               ├────────────────────────────┤
                                  │ ... RTTI / offset info     │
                                  └────────────────────────────┘

Dispatch sequence — s.area() যেখানে s : const Shape&:

১. mov  rax, [rdi]        ; object থেকে vptr লোড (rdi = this —
                          ; System V <Term id="calling-convention">calling convention</Term>-এ
                          ; প্রথম argument register)
২. call [rax + 8]         ; slot 1-এর target-এ indirect call
                          ; (slot 0 হলে [rax])

দুই instruction বাড়তি — শোনায় নগণ্য। কিন্তু তিনটা hidden খরচ:

Pointer chase: object cache-miss হলে vptr-load-ই stall — array-of-objects iteration-এ প্রতিটা element-এ।
Indirect branch: predictor ঠিকঠাক monomorphic site শিখে ফেলে (practical কোডে ৯৫%+ correct), তবে megamorphic call-site (হাজার receiver-type) প্রতি miss ~20 cycle।
Inlining-blockade — আসল দামটা এটাই। Direct call inline হলে constant-propagation, dead-code elimination সব chain চলে; indirect-এ compiler হাত গুটিয়ে দাঁড়ায়। Hot loop-এ পার্থক্য ২-১০× পর্যন্ত যায় — কারণটা call-এর cycle না, optimization-এর মৃত্যু।

Erasure-এর খরচের anatomy

Java-তে List<Integer>-এ add(5) লিখলে যা হয়:

১. javac: int 5 → Integer.valueOf(5)     // autoboxing — heap alloc!
২. ভেতরে: Object[] array — প্রতিটা element reference
৩. get() ফেরালে (Integer) cast → intValue() unbox

প্রতিটা element: 16-byte Integer header (refcnt-না-থাকলে mark-word + klass-pointer + value) + GC pressure + pointer-indirection access-এ। int[]-এর সাথে তুলনায় sequential-scan পার্থক্য প্রায়ই ২-৪×। Go interfaces একই জায়গায় আটকে small-value-গুলোকে stack-escape করায় (escaping analysis fail হলে heap)। Erasure বিনামূল্যে না — খরচটা representation-এ সরিয়ে দেয়।

Monomorphisation-এর খরচের anatomy

twice_tpl<int>(int)      ─┐
twice_tpl<long>(long)     ├─ প্রতিটাই আলাদা symbol, আলাদা machine code
twice_tpl<double>(double)─┘

binary size: N টাইপ × M template = N×M copies
compile time: প্রতিটা instantiation parse+optimize

C++-এর ধীর compile-এর বড় একটা কারণ এটা — আর Rust এটাকে generic-symbol deduplication (cross-crate) দিয়ে সামলায়। লাভ: specialization শুধু খরচ বাঁচায় না, আরও ভালো কোড বানায় — প্রতিটা copy-র ভেতরে টাইপ-specific constants fold হয় (Vec<u8> -এ SIMD memcpy path যেটা Vec<String>-এ অসম্ভব)।

তিন mechanism, তিন জায়গায় দাম

Monomorphisationদাম compile time + binary size-এ; runtime শূন্য, inlining পূর্ণ
Type erasureদাম runtime representation-এ — boxing, indirection, GC pressure
Subtype/vtableদাম per-call indirection + inlining-হারানো — আসল খরচ optimization-এর

উদাহরণ

একই call, তিন যাত্রা — compile থেকে silicon

কাজটা একটাই: দ্বিগুণ করা। তিন mechanism-এ একই expression-এর ভিন্ন ভাগ্য:

যাত্রা ১ — template (parametric, monomorphised):

template <typename T> T twice(T x) { return x + x; }
twice(21);          // twice<int>

compile time: T=int bind → instantiation → dedicated codegen
runtime:      add eax, eax        (বা -O2-তে inline হয়ে মিলিয়ে যায়)
symbol table: _Z9twiceIiET_S0_   ← 'Ii' = instantiated with int

যাত্রা ২ — overload (ad-hoc, static pick):

int twice_ovl(int x) { return x + x; }
twice_ovl(21);

compile time: overload resolution — argument int → exact match pick
runtime:      call _Z9twice_ovli   (direct call — address known)

যাত্রা ৩ — virtual (subtype, runtime pick):

struct D : Shape { double area() const override; };
double f(const Shape& s) { return s.area(); }

compile time: call-site শুধু slot-number জানে (area = slot 0)
runtime:      mov rax,[rdi] ; call [rax]   — দুই ধাপ indirection

এখন মূল observation — তিনটা যাত্রার কোনোটাতেই “polymorphic magic” নেই: প্রতিটাই শেষমেশ final-এ একটা concrete address-এ call করে। পার্থক্য একটাই — কোন সময়ে, কার হাতে সেই address জানার দায়িত্ব গেল। Template-এ compiler instantiation-এর সময়; overload-এ resolution-এর সময়; virtual-এ CPU runtime-এ, table থেকে। এই এক বাক্য polymorphism-এর পুরো implementation theory।

flexibility ▼                                    ▲ per-call cost

  direct call          ──▶  known addr, inline-able      (খরচ ≈ 0)
  monomorphised gen.   ──▶  direct call per type         (খরচ ≈ 0,
                                                         size ↑)
  overload             ──▶  direct call, static pick     (খরচ ≈ 0)
  typeclass w/ spec.   ──▶  dict folded → direct         (≈ 0)
  typeclass w/o spec.  ──▶  dict-passed indirect         (~1-2 cyc)
  virtual (mono site)  ──▶  vptr+slot, predicted well    (~2-4 cyc,
                                                         inline ✗)
  virtual (mega site)  ──▶  unpredictable indirect       (~20 cyc)
  erased + boxed       ──▶  alloc + ptr chase + dispatch (alloc খরচ
                                                         dominant)

flexibility ▲                                    ▼ per-call cost

Dispatch-cost ladder — উপরে সস্তা কিন্তু কম flexible, নিচে flexible কিন্তু প্রতি-call বিল।

ছবিতে

(A) MONOMORPHISED (Rust/Swift/C++)

  caller                    .text segment
  ┌────────────┐   direct   ┌──────────────────┐
  │ call site ─┼──────────▶ │ scale_u32: imul  │
  └────────────┘            ├──────────────────┤
                            │ scale_f64: mulsd │
                            └──────────────────┘
  প্রতি টাইপে এক copy; কোনো indirection নেই।

(B) ERASED (Java/Go/Haskell)

  caller          heap                     single .text
  ┌─────────┐  ┌──────────────┐         ┌──────────────┐
  │ call ───┼─▶│ Integer box  │──ptr──▶ │ shared impl  │
  └─────────┘  │ [hdr][5]     │         │ (uniform rep)│
               └──────────────┘         └──────────────┘
  একটাই কপি; দাম box-allocation + pointer-chase-এ।

(C) SUBTYPE/VTABLE (C++/Java methods)

  caller        object          vtable           .text
  ┌────────┐  ┌─────────┐    ┌──────────┐    ┌────────────┐
  │ call ──┼─▶│ vptr ───┼───▶│ slot[0] ─┼───▶│ Square::area│
  └────────┘  │ side    │    │ slot[1]  │    └────────────┘
              └─────────┘    └──────────┘
  দুই-ধাপ indirection; target runtime-এ জানা যায়।

তিন বাস্তবায়নের memory-layout — কোথায় code, কোথায় data, কোন pointer কোথায় নড়ে।

Diagram-টা পড়ার মন্ত্র: arrow যত বেশি, runtime তত কাজ। A-তে arrow একটাই আর সেটা compile-time-এ fix; C-তে arrow তিনটা, প্রতিটা CPU-cycle খায়; B-তে allocation-arrow টা GC-র জগতে ফিরে আসে (module- এর পরের লেসনগুলোর বিষয়)।

নিজে চালিয়ে দেখুন

EXPERIMENT

Monomorphisation-এর প্রমাণ — একই generic fn, দুই assembly

Rust toolchain (বা godbolt.org), ঐচ্ছিকভাবে g++/nm· ২০ মিনিট

অংশ ১ — Rust:

// mono.rs
use std::ops::Mul;

fn scale<T: Mul<Output = T> + Copy>(x: T, k: T) -> T {
    x * k
}

#[inline(never)]
pub fn scale_u32(x: u32, k: u32) -> u32 { scale(x, k) }

#[inline(never)]
pub fn scale_f64(x: f64, k: f64) -> f64 { scale(x, k) }

fn main() {
    println!("{}", scale_u32(7, 3));
    println!("{}", scale_f64(1.5, 2.0));
}

rustc -O --emit=asm mono.rs -o mono.s && grep -A4 "scale_u\|scale_f" mono.s

প্রত্যাশিত assembly (godbolt/rustc output — symbol hash ভিন্ন হবে):

example::scale_u32:
        mov     eax, esi
        imul    eax, edi          ← INTEGER multiply unit
        ret

example::scale_f64:
        mulsd   xmm0, xmm1        ← FLOATING-POINT/SIMD unit
        ret

দুইটা আলাদা function, দুই রকম instruction, দুই আলাদা hardware unit (integer ALU বনাম FP/SIMD pipe — computer-architecture module-এর functional units মনে করুন)। Source-এ একটাই scale; machine-এ দুইটা সম্পূর্ণ আলাদা কোড। এটাই monomorphisation-এর হাতে-নাগাল প্রমাণ।

অংশ ২ — C++ template-এ একই প্রমাণ, symbol table দিয়ে:

// tpl.cpp
template <typename T> T twice(T x) { return x + x; }
volatile long sink;
int main() {
    sink = twice(21);        // T = int
    sink = twice(2.5);       // T = double
}

g++ -O0 tpl.cpp -o tpl && nm -C tpl | grep twice

প্রত্যাশিত:

0000000100003f60 T twice<int>(int)
0000000100003f80 T twice<double>(double)

Symbol table-ই স্বীকারোক্তি: দুইটা আলাদা function, দুইটা আলাদা address। -C ছাড়া চালালে mangled নাম দেখবেন (_Z5twiceIiET_S0_, _Z5twiceIdET_S0_) — ম্যাংলিং-এর Ii/Id অংশটাই instantiation-type। Erasure-based ভাষায় এমন দুই symbol কখনো পাবেন না — সেখানে একটাই method, টাইপ-তথ্য runtime tag-এ।

ভাবার বিষয়: #[inline(never)] কেন? -O-তে Rust ছোট generic-গুলো call-site-এ inline করে ফেলে — symbol-ই হারিয়ে যাবে। Abstraction তখন “zero-cost” আক্ষরিক অর্থে: কোডের অস্তিত্বই নেই।

এটা কী প্রমাণ করে

একটা generic Rust function u32 আর f64-এ instantiate করলে binary-তে দুইটা আলাদা symbol জন্মায়, একটাতে integer multiply (imul), অন্যটাতে floating-point multiply (mulsd) — monomorphisation কোনো abstraction না, literal দুই কপি machine code।

নিজে বানান

BUILD IT

তিন mechanism, এক ভাষা, এক disassembly — নিজের চোখে

C++ (g++ বা clang++, objdump) · ●●○○○

Template version লিখুন — parametric, monomorphisation-এর জন্য
Overload pair লিখুন — ad-hoc, static resolution-এর জন্য
Abstract base + derived + override লিখুন — subtype/vtable-এর জন্য
একটা non-inlinable wrapper-এ virtual call আটকে disassemble করুন
তিন call-site-এর assembly পাশাপাশি রাখুন — direct/direct/indirect

// three.cpp — একই "দ্বিগুণ" ধারণা, তিন mechanism-এ
#include <cstdio>

// ── ১. Parametric: template → monomorphisation ──────────────
template <typename T>
T twice_tpl(T x) { return x + x; }

// ── ২. Ad-hoc: overloading → static pick ────────────────────
int    twice_adhoc(int x)    { return x + x; }
double twice_adhoc(double x) { return x + x; }

// ── ৩. Subtype: virtual → vtable dispatch ───────────────────
struct Shape {
    virtual ~Shape() = default;
    virtual double area() const = 0;
};
struct Square : Shape {
    double side;
    explicit Square(double s) : side(s) {}
    double area() const override { return side * side; }
};
struct Circle : Shape {
    double r;
    explicit Circle(double rr) : r(rr) {}
    double area() const override { return 3.14159265358979 * r * r; }
};

// virtual call-কে inline হতে দেব না — যেন disassembly-তে দেখা যায়
__attribute__((noinline))
double dispatch_area(const Shape& s) { return s.area(); }

int main() {
    printf("%d %f\n", twice_tpl(21), twice_tpl(2.5));   // parametric ×২
    printf("%d\n", twice_adhoc(21));                    // ad-hoc: int-pick
    Square sq{3.0}; Circle ci{1.0};
    Shape* shapes[] = {&sq, &ci};
    for (const Shape* s : shapes)
        printf("%f\n", dispatch_area(*s));              // subtype ×২
    return 0;
}

g++ -O2 three.cpp -o three
objdump -dC three | less        # খুঁজুন: twice_tpl, twice_adhoc, dispatch_area
nm -C three | grep twice

Disassembly-তে যা খুঁজবেন (exact registers ভিন্ন হবে):

; ── parametric: দুই আলাদা instantiation, কোনো call নেই (-O2-তে inline)
lea  eax, [rdi+rdi]              ; twice_tpl(21) → সরাসরি doubling!
addsd xmm0, xmm0                 ; twice_tpl(2.5) → FP doubling

; ── ad-hoc: direct call, address compile-time-known
call twice_adhoc(int)

; ── subtype: দুই-ধাপ indirection, target runtime-এ
dispatch_area(Shape const&):
    mov  rax, QWORD PTR [rdi]    ; ১. vptr লোড
    call QWORD PTR [rax]         ; ২. slot 0 → indirect call
    ret

আর dispatch_area-এর সবচেয়ে সুন্দর দিক: Square আর Circle — দুই ভিন্ন receiver, হুবহু একই দুই-instruction dispatch code। Template- জগতে দুই receiver মানে দুই কোড; virtual-জগতে এক কোড, দুই vtable। Trade-off-টা এখানেই চোখের সামনে।

নিজে বাড়ান:

dispatch_area-এ dynamic_cast<Circle*> যোগ করে RTTI-check-এর assembly দেখুন — typeinfo comparison আরও কয়েক instruction।
-fdump-class-hierarchy (gcc) চালিয়ে vtable layout ছাপান — slot-order, RTTI pointer, thunk-দের সাথে পরিচয়।
চ্যালেঞ্জ: multiple inheritance যোগ করুন (Circle যেন Drawable-ও) এবং second-base-এ cast করলে vptr-adjustment (thunk) কীভাবে আসে দেখুন — C++-এর সবচেয়ে অপ্রিয় complexity-র মূল।

বাস্তব সিস্টেমে

Polymorphism-এর তিন জগৎ বাস্তবে

std::sort বনাম qsort — ক্লাসিক benchmark anecdote। C++-এর std::sort comparator inline করে (template — monomorphised); C-এর qsort comparator function-pointer-এ call করে (erasure-ঘরানার indirection)। একই algorithm, same data — প্রায়ই ২-৩× পার্থক্য, আর কারণ ঠিক এই লেসনের cost-table: inlining হারানো মানে branch, prefetch, vectorization সব হারানো।

Java Collections-এর erasure-বেদনা। new T() লেখা যায় না, T[] array বানানো ঝামেলা, primitive-দের জন্য আটটা আলাদা stream- interface (IntStream ইত্যাদি) — প্রতিটা workaround-এর পেছনে erasure-এর একটা সীমা। Project Valhalla দশক-লম্বা effort-এর লক্ষ্য: value-types দিয়ে boxing-bill মারা।

Linux kernel-এর hand-rolled vtable। C-তে inheritance নেই, তবু struct file_operations — .read, .write, .ioctl function- pointer-দের ছক — প্রতিটা device-driver ভরে দেয়, VFS layer generic কোড থেকে indirect-call করে। Subtype polymorphism-এর purest production form — কোনো language support ছাড়াই। OS module-এর system-call পথে আপনি প্রতিদিন এই dispatch পার হন।

Go interfaces আর itab। (value, type) জোড়া + method-table — erasure-এর Go-স্বাদ; small value interface-এ ঢুকলে escape-analysis fail হলে heap-allocation — Go profiler-এর common flame।

Swift protocol witness tables। Generic-এ monomorphisation, protocol existential-এ witness-table dispatch — দুই mode পাশাপাশি, ঠিক Rust-এর generic-বনাম-dyn Trait বিভাজনের মতো।

GHC-র dictionary passing। Typeclass constraint compile-এ extra-parameter-এ transform হয় — Ord a => ... মানে লুকানো comparison-dictionary argument। Specialisation optimization on থাকলে hot-path dictionary-গুলো fold হয়ে direct call — ad-hoc- এর theoretical model-এর সবচেয়ে faithful industrial deployment।

COM (Windows)। Binary-level interface = pure vtable contract — language-agnostic subtype polymorphism, 1993 থেকে আজ পর্যন্ত Windows API-র ভিত্তি।

যে ভুলগুলো সবাই করে

“Polymorphism মানে OOP-র virtual method — বাকিটা ভিন্ন কিছু।”

Taxonomy-র ভুল পড়া। Strachey 1967-এ parametric আর ad-hoc নাম দিয়েছেন OO mainstream-হওয়ার আগে; ML-family-তে inheritance নেই বললেও polymorphism-এর বাহুল্য (HM-এর ∀-types = parametric, typeclass = ad-hoc)। Interview-তে “polymorphism” শুনলে তিনটা clarify করে কথা বলুন — এক শব্দে তিন promise, তিন implementation, তিন খরচ।

“Zero-cost abstraction মানে generics-এর কোনো খরচ নেই।”

Zero-cost মানে runtime-এ zero — relative-to-hand-written-specialized-code। খরচটা সরে গেছে compile time-এ (C++ template-heavy কোডে minute-scale builds) আর binary size-এ (N টাইপ × M generic = N×M copies, icache-pressure পর্যন্ত যেতে পারে)। আর “abstractions you don’t pay for” -এর উল্টো দিকটাও সত্য: যে specialization লাগবেই না, সেটাও generate হয়ে যায়। খরচ eliminate না — relocate; relocation-টা ভালো কোথায় সেটা domain- নির্ভর।

“Virtual call ধীর — performance-sensitive কোডে এড়িয়ে চলতেই হবে।”

Modern predictor-এ monomorphic virtual-site-এর penalty প্রায়শই noise-এর মধ্যে (~২-৪ cycle, correctly predicted)। আসল খরচ inlining- blockade — hot loop-এ যে optimization-cascade থেমে যায়। তাই সঠিক practice: measure করা ছাড়া pre-optimization না, তবে hot inner loop-এ (per-element dispatch, 10⁷+ calls) devirtualize করা — enum/ closed-trait/template — justified। Blanket rule দুই দিকেই ভুল।

“Python-এর duck typing তৃতীয় ধরনের polymorphism — Python সব কিছুতেই polymorphic।”

Duck typing-কে untyped parametric-এর সাথে তুলনা করা যায় (কোনো টাইপ-constraint ঘোষণা নেই), কিন্তু formal taxonomy-র তিনটার কোনোটাই না: কোনো universal quantifier-এর guarantee নেই (parametricity-র theorem-free), কোনো static resolution নেই, কোনো declared hierarchy নেই। ভুল টাইপের attribute-access runtime-এ AttributeError — অর্থাৎ contract enforcement সম্পূর্ণ runtime-tag-driven (লেসন ৩-এর যন্ত্র)। Python-এর জগৎটা powerful, তবে তার power-এর formal নাম ভিন্ন — structural conformance at runtime, checked lazily।

বুঝেছেন কি না দেখুন

তিন ধরনের polymorphism-এর প্রতিটার জন্য: (ক) এক-বাক্য promise, (খ) দুইটা ভাষা-construct উদাহরণ, (গ) resolve হয় কোন সময়ে।

স্মরণ

Parametric: “একই কোড সব টাইপে, টাইপ সম্পর্কে অজ্ঞ” — generics (Rust fn id<T>), C++ templates; compile-time (instantiation)।

Ad-hoc: “নির্দিষ্ট টাইপ-set-এর প্রত্যেকটার জন্য আলাদা definition, এক নামে” — overloading (C++/Java), typeclasses (Haskell), traits (Rust); compile-time।

Subtype: “subclass-instance superclass-এর জায়গায়, সঠিক override runtime-এ” — virtual methods (C++/Java/C#), protocol existentials (Swift); runtime (vtable)।

List<Integer>-এ ১০ লক্ষ element add করলে আনুমানিক কত byte বাড়তি (box-header 16 byte ধরে)? int[1000000]-এর সাথে তুলনা করুন, আর access-pattern-এর পার্থক্য বলুন।

প্রয়োগ

List<Integer>: ১০ লক্ষ box × 16 bytes = ~16 MB বাড়তি (plus array-র প্রতি-element 4/8-byte reference — total ~24 MB)। int[]: flat 4 MB, একটাই allocation।

Access-pattern: int[i] এক memory-read (sequential prefetch-friendly); list.get(i) মানে pointer→box→value দুই-hop chase — random-access- এ cache-miss দ্বিগুণ সম্ভাবনা, sequential-এও footprint ৬× বড় বলে cache-residency খারাপ। এই পার্থক্যই numeric Java কোডে IntStream/array preference-এর কারণ — erasure-এর boxing-bill-এর সরাসরি প্রমাণ।

Experiment-এ scale_u32 আর scale_f64-এ দেখলেন imul বনাম mulsd — ভিন্ন execution-unit। এই পার্থক্যটা erasure-based ভাষায় (একটাই shared code) কীভাবে সম্ভব নয়? Uniform representation ঠিক কী compromise?

যুক্তি

Shared code-কে যে-কোনো input-এ চলতে হয়, তাই সে কোনো specific instruction বেছে নিতে পারে না — সব arithmetic হয় interpreter-style tag-check + generic path-এ (বা primitive-দের জন্য separate handwritten paths — Java-র IntStream ঠিক সেই manual monomorphisation!)। mulsd emit করতে হলে compiler-কে compile-time-এই জানতে হয় operand f64 — erasure সেই knowledge runtime পর্যন্ত মুছে দেয়। Compromise: representation uniform (সব boxed/tagged) → instruction-selection generic → প্রতিটা operation-এ dispatch overhead + scalar-only path (SIMD-width specialization অসম্ভব)। Monomorphisation knowledge retain করে ঠিক এই জন্য।

Game engine-এ ১০,০০০ entity প্রতি frame update(dt) কল করে। Entity- type ৫০টা, প্রতি-entity logic ভিন্ন। Design choice: (a) virtual update() (b) type-id + switch (c) Rust-এ enum + match। Cache- behavior আর dispatch-cost মিলিয়ে evaluate করুন।

ডিজাইন

(a) Virtual: dispatch খরচ নগণ্য (predictable sites), কিন্তু objects heap-scattered হলে প্রতি-element vptr-chase + cold vtables — cache-miss dominant। Data-oriented fix: entity-array-of-structures → structures-of- arrays, তবু virtual per-element inlining-হারানো থাকে।

(b) Switch: type-id int compare + predictable branch — monomorphic hot path-এ JIT/AOT দুটোতেই cluster-by-type করলে (bucketing) switch near-perfectly predicted; inline-ও হয়। Manual monomorphisation-এর hand-rolled রূপ।

(c) Enum+match: Rust-এ closed set — compiler exhaustive-match optimize করে jump-table/branch; data inline enum-variant-এ (no pointer chase); new variant-এ compile error — flexibility trade explicit।

Recommendation: hot loop-এ (b)/(c) — bucket-by-type আর flat storage; editor/debug path-এ (a)-র ergonomics। মূল শিক্ষা: dispatch-cost-এর চেয়ে memory-layout বড় factor — আর তা ভাষা-feature না, data-design।

dispatch_area-এর disassembly-টা আবার পড়ুন: mov rax,[rdi]; call [rax]; ret। প্রতিটা instruction-এর মানে বাংলায় লিখুন, আর বলুন এই দুই instruction-এর কোনটা branch-predictor-এর দায়িত্বে, কেন।

প্রয়োগ

mov rax,[rdi]: rdi-তে থাকা this-pointer (calling convention-এর প্রথম arg register) dereference করে object-এর প্রথম word — vptr — rax-এ আনা। call [rax]: rax-এ ধরা vtable-address-এর slot 0-তে থাকা target-address পড়ে সেখানে call। ret: caller-এ ফেরা।

Branch-predictor-এর দায়িত্ব দ্বিতীয়টায় — indirect call-এর target runtime-এ জানা, predictor-কেই history থেকে guess করতে হয় (modern CPU-তে indirect-target predictor আলাদা structure)। প্রথমটা plain data-load — তার ঝুঁকি cache-miss, misprediction না। তাই megamorphic site-এ penalty predictor-target-এ, আর scattered objects-এ penalty প্রথমটার cache-এ — দুই ভিন্ন রোগ, দুই ভিন্ন ওষুধ।

Haskell typeclass আর C++ overloading — দুটোই ad-hoc। তবু typeclass দিয়ে এমন function লেখা যায় যেখানে দুই ভিন্ন টাইপের value একই generic context-এ travel করে (যেমন read :: String -> a) — overloading কেন এটা পারে না? Dictionary-passing-এর সাথে যুক্ত করে ব্যাখ্যা করুন।

যুক্তি

Overloading-এর resolution পুরোপুরি call-site-static: compiler argument/result-এর concrete টাইপ দেখে exact instance বাছে — টাইপ unknown জায়গায় overload-ই undefined। Typeclass-এ constraint টা quantified variable-এর সাথে travel করে: read :: forall a. Read a => String -> a মানে function টা extra hidden parameter নেয় — Read-dictionary — আর caller সেটা supply করে। অর্থাৎ polymorphism-টা dictionary-argument-এর parametric polymorphism-এ lower হয়ে যায় — first-class, composition-এ বাঁচে (map read চলে, কারণ dictionary-টা higher-order value-র মতো ঘোরে)। Overloading-এ dictionary-র বদলে direct-name-substitution হয় — name-টা context ছাড়া অস্তিত্বহীন, travel করার কিছু নেই। এটাই “ad-hoc-এর দুই স্তর”: resolved-at-site বনাম carried-as-evidence।

এরপর কী

আজ দেখলাম “এক নাম, অনেক টাইপ” বাস্তবায়নের তিন পথ — আর প্রতিটার বিল আলাদা ঠিকানায় যায়: monomorphisation-এর বিল compile-time/binary-তে, erasure-এর বিল heap-এ (boxing), vtable-এর বিল প্রতি-call indirection- এ। লক্ষ্য করুন কোন থিমটা বারবার ফিরল: memory — কে allocate করল, কোথায় বসল, কে ফেরত নিল। Box-গুলো heap-এ জন্মাল, কিন্তু মরবে কখন?

পরের লেসনে — Memory Models — এই প্রশ্নের চারটা ভিন্ন দর্শন দেখব: manual (C-এর malloc/free), RAII (C++/Rust-এ scope-bound lifetime), ownership (Rust-এর borrow checker — lifetime compile- এ প্রমাণ), আর garbage collection (tracing)। Polymorphism-এর boxed world-টা GC-র জগতে পুরোপুরি ঘরে বসে — আর Rust কেন boxing- ছাড়া generics দিতে পেরেছে তার উত্তরও সেখানে।

Polymorphism — একটা interface, কয়টা implementation, আর খরচ কত

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

আগে এটা বুঝি

মূল ধারণা

তিনটা রূপ — তিনটা ভিন্ন promise

Parametric-এর দুই বাস্তবায়ন — এক কপি বনাম কপি-কপি

Ad-hoc-এর resolution — সব কটা compile-time

Subtype-এর resolution — runtime table

ভেতরে কী ঘটছে

Vtable anatomy — object-এর পেছনের ছক

Erasure-এর খরচের anatomy

Monomorphisation-এর খরচের anatomy

উদাহরণ

একই call, তিন যাত্রা — compile থেকে silicon

ছবিতে

নিজে চালিয়ে দেখুন

Monomorphisation-এর প্রমাণ — একই generic fn, দুই assembly

নিজে বানান

তিন mechanism, এক ভাষা, এক disassembly — নিজের চোখে

বাস্তব সিস্টেমে

Polymorphism-এর তিন জগৎ বাস্তবে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী

এরপর কী

আরও পড়ুন

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

◔আগে এটা বুঝিWhy this matters

◆মূল ধারণাCore concept

তিনটা রূপ — তিনটা ভিন্ন promise

Parametric-এর দুই বাস্তবায়ন — এক কপি বনাম কপি-কপি

Ad-hoc-এর resolution — সব কটা compile-time

Subtype-এর resolution — runtime table

⚙ভেতরে কী ঘটছেUnder the hood

Vtable anatomy — object-এর পেছনের ছক

Erasure-এর খরচের anatomy

Monomorphisation-এর খরচের anatomy

▶উদাহরণExample

একই call, তিন যাত্রা — compile থেকে silicon

◫ছবিতেDiagram

⌘নিজে চালিয়ে দেখুনExperiment

Monomorphisation-এর প্রমাণ — একই generic fn, দুই assembly

⚒নিজে বানানBuild it yourself

তিন mechanism, এক ভাষা, এক disassembly — নিজের চোখে

◉বাস্তব সিস্টেমেReal-world usage

Polymorphism-এর তিন জগৎ বাস্তবে

⚠যে ভুলগুলো সবাই করেMisconceptions

?বুঝেছেন কি না দেখুনCheck understanding

→এরপর কীNext step

এরপর কী

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

ভেতরে কী ঘটছে

উদাহরণ

ছবিতে

নিজে চালিয়ে দেখুন

নিজে বানান

বাস্তব সিস্টেমে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী