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

Subprogram-এর বাস্তবায়ন — activation record, call stack আর calling convention

Implementing Subprograms — Activation Records, the Call Stack and Calling Conventions

Taught in Bangla, this lesson explains what an activation record holds (parameters, locals, return address, dynamic and static links) and how caller and callee split the work of a call and return. A stepper and an in-page Python (Pyodide) VM run real Haat bytecode to build and pop frames, static chains and displays are traced for nested functions, real Clang 22 output shows x86-64 and RISC-V prologues, epilogues and argument registers, and runnable probes show recursion depth limits.

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

  • Activation record-এর প্রতিটি ঘর কেন লাগে, আর একটি call ও return-এ caller আর callee কে কোন কাজ করে
  • Haat VM-এর আসল bytecode চালিয়ে frame তৈরি আর ভাঙা নিজের চোখে দেখা
  • Nested function-এর জন্য static link, static chain আর display; কোন ডাকে কোন static link বসে তার নিয়ম আর প্রমাণের রূপরেখা
  • পরীক্ষার ধাঁচে একটি নির্দিষ্ট মুহূর্তে activation record-এর পুরো stack আঁকা
  • সত্যিকারের Clang-এর x86-64 আর RISC-V আউটপুটে prologue, epilogue আর argument register চেনা, আর stack overflow-এর বাস্তব রূপ

১ · একটি call-এর পেছনে কী ঘটে — activation record

বাজারঘরের হিসাবরক্ষক একটি অর্ডারের মোট দাম কষছেন। মাঝপথে ডেলিভারি চার্জ জানা দরকার, সেটি কষেন আরেকজন সহকর্মী। হিসাবরক্ষক নিজের খাতা বন্ধ করার আগে একটি চিরকুটে লিখে রাখেন: কোন লাইনে থেমেছিলেন, কোন খাতা খোলা ছিল, আর সহকর্মীকে দেন একটি আলাদা কাগজ, তাতে লেখা “অর্ডারের মূল্য ৯৩৬ টাকা”। সহকর্মী নিজের কাগজে হিসাব করেন, উত্তর লিখে কাগজ ফেরত দেন, আর হিসাবরক্ষক চিরকুট দেখে ঠিক সেই লাইন থেকে আবার শুরু করেন। সহকর্মী যদি নিজেও কাউকে কিছু জিজ্ঞেস করেন, তিনিও একই নিয়মে নিজের চিরকুট রাখেন। চিরকুটগুলো একটির ওপর আরেকটি জমে, আর উত্তর আসার সঙ্গে সঙ্গে ওপর থেকে সরে।

Function, procedure, method: সবই একই ধারণার নানা নাম, পাঠ্যবইয়ে একসঙ্গে বলে subprogram বা procedure. প্রতিবার ডাকলে তার জন্য যে “চিরকুট আর কাগজ” তৈরি হয়, তার নাম activation record. Stack-এ রাখলে একে বলে stack frame, আর চলমান সব frame মিলে call stack. পর্ব ১৬-এ (Lifetime আর storage) দেখেছেন কেন local variable stack-এ থাকে আর recursion-এ প্রতিটি ডাক নিজের ঘর পায়; পর্ব ১৭-এ (Closure) দেখেছেন কোন variable stack ছেড়ে heap-এ যেতে বাধ্য হয়। এই পর্বে frame-এর ভেতরে ঢুকব: কী কী ঘর, কে কখন ভরে, আর আসল যন্ত্রে সেটি কেমন দেখায়।

ছবি ৩০.১ — একটি activation record-এর সাধারণ বিন্যাস

পাঠ্যবইয়ের মডেল; প্রতিটি ভাষা আর যন্ত্র কিছু ঘর বাদ দেয় বা জায়গা বদলায়

Activation record layout: arguments, return address, dynamic link, static link, saved registers, locals and temporaries, with fp and sp caller-এর frame argument (বাড়তি হলে) ফেরার ঠিকানা dynamic link (পুরোনো fp) static link (দরকার হলে) সংরক্ষিত register local variable temporary, spill stack বাড়ে নিচে fp sp বড় ঠিকানা ওপরে, ছোট ঠিকানা নিচে fp-এর সাপেক্ষে প্রতিটি ঘরের দূরত্ব compile-এর সময় জানা
ছবি ৩০.১ — একটি ডাকের activation record. ঘরগুলোর কাজ নিচের টেবিলে। frame pointer (fp) frame-এর একটি স্থির বিন্দু দেখায়, আর stack pointer (sp) stack-এর বর্তমান চূড়া।
ঘরকেন লাগেকে ভরে
Argument / parametercallee-র কাজের input; অনেক convention-এ প্রথম কয়েকটি register-এ আসে, frame-এ নামে শুধু দরকার হলেcaller (মান), callee (জায়গা)
Return addressকাজ শেষে caller-এর কোন নির্দেশে ফিরতে হবেcall নির্দেশ নিজে
Dynamic linkcaller-এর frame কোথায়; ফেরার সময় পুরোনো fp ফিরিয়ে আনতেcallee-র prologue
Static linknested function হলে লেখার দিক থেকে ঘিরে থাকা function-এর frame; C-তে নেইcaller
সংরক্ষিত registerযে register-এর মান call-এর পরে অক্ষত থাকার কথা, সেগুলো বাঁচিয়ে রাখাcaller বা callee, convention অনুযায়ী
Local আর temporaryfunction-এর নিজের variable আর হিসাবের মাঝের মান (register-এ জায়গা না হলে)callee

একটি গুরুত্বপূর্ণ বিষয় খেয়াল করুন: frame-টি মেমরির কোথায় বসবে তা চলার সময় ঠিক হয়, কিন্তু frame-এর ভেতরে কোন ঘর কোথায়, তা compiler আগেই জানে। তাই local variable p-এর ঠিকানা লেখা যায় “fp থেকে ৪৮ byte নিচে” হিসেবে, একটি ধ্রুবক দূরত্ব দিয়ে। এই পর্বের সব কৌশল এই একটি ধারণার ওপর দাঁড়ানো: চলার সময়ের একটি base, আর compile-এর সময়ের একটি offset.

২ · Call আর return — কে কোন কাজ করে

একটি call-কে compiler দুই ভাগে ভাগ করে। ডাকার জায়গার কোড (caller-এর অংশ) আর ডাকা function-এর শুরু ও শেষের কোড (callee-র অংশ)। এই পুরো ধারাবাহিক কাজকে বলে calling sequence. শুরুর অংশের নাম prologue, শেষের অংশ epilogue.

Caller-এর কাজ

১. argument-গুলোর মান হিসাব করা (Haat-এ বাঁ থেকে ডানে, README-এর সিদ্ধান্ত ১২). ২. সেগুলো নির্দিষ্ট register বা stack-এর ঘরে বসানো। ৩. দরকার হলে static link আর নিজের caller-saved register রাখা। ৪. call: ফেরার ঠিকানা রেখে callee-তে লাফ। ফেরার পরে: ফল নেওয়া, argument-এর জায়গা ছাড়া।

প্রতিটি ডাকার জায়গায় একবার

Callee-র কাজ

Prologue: sp সরিয়ে frame-এর জায়গা নেওয়া, পুরোনো fp আর (দরকার হলে) ফেরার ঠিকানা রাখা, নতুন fp বসানো, callee-saved register বাঁচানো। Epilogue: ফল নির্দিষ্ট register-এ রাখা, সব ফিরিয়ে আনা, sp ফেরত দেওয়া, ফেরার ঠিকানায় লাফ।

প্রতিটি function-এ একবার

কাজ এভাবে ভাগ কেন? একটি function-কে একশো জায়গা থেকে ডাকা হতে পারে। যে কাজ প্রতিটি ডাকে একই রকম (frame বানানো, register বাঁচানো), তা callee-তে রাখলে কোড লেখা হয় একবারই; caller-এ রাখলে একশো কপি। আবার argument-এর মান শুধু caller জানে, তাই সেটি caller-এর কাজ। কোন register কে বাঁচাবে, সেই ভাগাভাগিও একই হিসাবের ফল: কিছু register caller-saved (callee ইচ্ছামতো নষ্ট করতে পারে), কিছু callee-saved (callee ব্যবহার করলে আগের মান ফিরিয়ে দিতে বাধ্য)।

Haat VM-এ: দুটি নির্দেশেই পুরো ধারাবাহিকতা

Haat reference-এর VM (vm.py) এই কাজগুলো খুব সরল রূপে করে। প্রতিটি ডাকে একটি Frame(closure, ip, slots) তৈরি হয়, আর সব frame থাকে frames নামের একটি Python list-এ। একটি operand stack সব ডাক মিলে ভাগ করে ব্যবহার করে। README-এর bytecode টেবিল অনুযায়ী CALL n-এর আগে stack-এ থাকে callee আর তার ওপরে n-টি argument (callee আগে, সিদ্ধান্ত ১২)। CALL argument-গুলো তুলে নতুন frame-এর slot 0 থেকে n−1-এ বসায়, বাকি local-এর ঘর ফাঁকা রাখে। RETURN frame-টি সরিয়ে ফেলে, আর ফলের মান operand stack-এ caller-এর জন্য রেখে যায়। bazar.haat-এর ১০ নম্বর লাইন let first = price(2, 520) + delivery(price(2, 520));-এর সত্যিকারের dis (README থেকে):

   4  LOAD_GLOBAL    0     ; price
   5  CONST          2     ; 2
   6  CONST          3     ; 520
   7  CALL           2
   8  LOAD_GLOBAL    1     ; delivery
   9  LOAD_GLOBAL    0     ; price
  10  CONST          2     ; 2
  11  CONST          3     ; 520
  12  CALL           2
  13  CALL           1
  14  ADD
  15  DEFINE_GLOBAL  2     ; first

== price (arity 2, locals 3) ==

price-এর জন্য locals 3: দুটি parameter (qty, unit) আর একটি local (p). Parameter আর body-র প্রথম স্তর একই scope ভাগ করে (সিদ্ধান্ত ১৪), তাই একই slot-এর সারিতে বসে। এই VM-এ activation record-এর ঘরগুলো কোথায়? ফেরার ঠিকানা হলো caller-এর frame-এর ip (CALL চলার সময়েই সেটি পরের নির্দেশে এগিয়ে গেছে), dynamic link হলো list-এ ঠিক নিচের frame, আর argument ও local হলো slots. Temporary থাকে operand stack-এ। নিচের stepper reference VM-এর সত্যিকারের trace থেকে বানানো (লেখকের lab-এ reference-এর compiler আর একই loop চালিয়ে প্রতিটি CALL আর RETURN-এ অবস্থা ছাপানো হয়েছে)।

4LOAD_GLOBAL 0 ; price5CONST 2 ; 26CONST 3 ; 5207CALL 28LOAD_GLOBAL 1 ; delivery9LOAD_GLOBAL 0 ; price10CONST 2 ; 211CONST 3 ; 52012CALL 213CALL 114ADD
VM-এর অবস্থা
frames
ওপরের slots
operand stack
  1. Caller argument সাজায়। 4–6: callee price আগে, তারপর 2 আর 520. 7-এ CALL 2 পড়া হলো; vm.py প্রতিটি নির্দেশ পড়ার সঙ্গে সঙ্গেই ip এক ঘর বাড়ায়, তাই main-এর ip এখন 8.
  2. Frame তৈরি। CALL ওপরের দুটি মান তুলে নতুন frame-এর slot 0 আর 1-এ বসায়, তারপর callee-কে সরায়; slot 2 (p) ফাঁকা। main-এর frame-এ রয়ে যাওয়া ip 8-ই ফেরার ঠিকানা। operand stack খালি।
  3. Callee কাজ করে, ফেরে। price-এর নিজের নির্দেশ: p = 1040, শর্ত সত্য, তাই 13 নম্বর নির্দেশ RETURN (পড়ার পরে price-এর ip 14), stack-এ 936. RETURN frame সরায়, মানটি রেখে যায়; slots-এর 1040 frame-এর সঙ্গেই হারায়।
  4. Caller আবার চলে ip 8 থেকে। 936 নিচে অপেক্ষায় রেখে main তুলে নেয় delivery, তারপর ভেতরের ডাকের জন্য price, 2, 520. বাইরের ডাকের callee আগে, কারণ callee সবসময় argument-এর আগে।
  5. দ্বিতীয় price frame. একই function, কিন্তু একেবারে নতুন frame: slot আবার [2, 520, ·]. operand stack-এ main-এর অর্ধেক কাজ (936 আর delivery) নিচে বসে আছে; callee সেগুলো ছোঁয় না।
  6. আবার 936. ফেরার পরে stack: 936, delivery, 936. এখন ওপরের দুটি ঠিক CALL 1-এর যা দরকার: callee আর একটি argument.
  7. delivery-র frame. slot 0-এ 936 (total), ফেরার ঠিকানা main-এর ip 14. নিচে পড়ে আছে প্রথম 936.
  8. ফল জোড়া। 936 < 1000, তাই delivery 60 ফেরত দেয়। ADD 936 + 60 = 996, যা পরে first-এ বসে আর ছাপা হয়। মোট তিনটি frame এল আর গেল, কিন্তু কোনো মুহূর্তে দুটির বেশি ছিল না।

এবার একই ঘটনা নিজে চালিয়ে দেখুন। নিচের block reference-এর dis-এর price আর delivery-এর নির্দেশ হুবহু নেয় (শুধু CONST-এর arg-এ constant-এর index-এর বদলে সরাসরি মান), আর প্রতিটি CALL ও RETURN-এ frame-এর অবস্থা ছাপে। পূর্ণ রূপ reference-এর vm.py-তে।

# bazar.haat-এর আসল bytecode (reference-এর dis), frame-সহ একটি ছোট VM
# CONST-এর arg এখানে সরাসরি মান; <main>-এর অংশ শুরু dis-এর 4 নম্বরে
PRICE = [("LOAD_LOCAL", 0), ("LOAD_LOCAL", 1), ("MUL", None),
         ("STORE_LOCAL", 2), ("LOAD_LOCAL", 2), ("CONST", 1000), ("GE", None),
         ("JUMP_IF_FALSE", 14), ("LOAD_LOCAL", 2), ("LOAD_LOCAL", 2),
         ("CONST", 10), ("DIV", None), ("SUB", None), ("RETURN", None),
         ("LOAD_LOCAL", 2), ("RETURN", None)]
DELIVERY = [("LOAD_LOCAL", 0), ("CONST", 1000), ("GE", None),
            ("JUMP_IF_FALSE", 6), ("CONST", 0), ("RETURN", None),
            ("CONST", 60), ("RETURN", None)]
FNS = {"price": (PRICE, 2, 3), "delivery": (DELIVERY, 1, 1)}  # code, arity, nlocals
MAIN = [("LOAD_GLOBAL", "price"), ("CONST", 2), ("CONST", 520), ("CALL", 2),
        ("LOAD_GLOBAL", "delivery"), ("LOAD_GLOBAL", "price"), ("CONST", 2),
        ("CONST", 520), ("CALL", 2), ("CALL", 1), ("ADD", None), ("PRINT", None)]
OPS = {"MUL": lambda a, b: a * b, "SUB": lambda a, b: a - b, "ADD": lambda a, b: a + b,
       "DIV": lambda a, b: a // b, "GE": lambda a, b: a >= b}   # এখানে সব মান ধনাত্মক
stack, frames = [], [{"fn": "<main>", "code": MAIN, "ip": 0, "slots": [], "at": 4}]
while frames and frames[-1]["ip"] < len(frames[-1]["code"]):
    f = frames[-1]; op, arg = f["code"][f["ip"]]; f["ip"] += 1
    if op == "CONST": stack.append(arg)
    elif op == "LOAD_GLOBAL": stack.append(arg)          # function-এর নাম = মান
    elif op == "LOAD_LOCAL": stack.append(f["slots"][arg])
    elif op == "STORE_LOCAL": f["slots"][arg] = stack.pop()
    elif op in OPS: b, a = stack.pop(), stack.pop(); stack.append(OPS[op](a, b))
    elif op == "JUMP_IF_FALSE" and not stack.pop(): f["ip"] = arg
    elif op == "PRINT": print("PRINT", stack.pop())
    elif op == "CALL":
        args = stack[len(stack) - arg:]; del stack[len(stack) - arg:]
        name = stack.pop(); code, arity, nlocals = FNS[name]
        print(f"CALL {name}{args}  ফেরা: {f['fn']}@{f['ip'] + f.get('at', 0)}  stack={stack}")
        frames.append({"fn": name, "code": code, "ip": 0,
                       "slots": args + [None] * (nlocals - arity)})
    elif op == "RETURN":
        done = frames.pop()
        print(f"RETURN {stack[-1]} ({done['fn']}, slots={done['slots']})  stack={stack}")

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

CALL price[2, 520]  ফেরা: <main>@8  stack=[]
RETURN 936 (price, slots=[2, 520, 1040])  stack=[936]
CALL price[2, 520]  ফেরা: <main>@13  stack=[936, 'delivery']
RETURN 936 (price, slots=[2, 520, 1040])  stack=[936, 'delivery', 936]
CALL delivery[936]  ফেরা: <main>@14  stack=[936]
RETURN 60 (delivery, slots=[936])  stack=[936, 60]
PRINT 996

ফেরার জায়গা 8, 13, 14 আর প্রতিটি মুহূর্তের stack reference VM-এর trace-এর সঙ্গে হুবহু মেলে, আর ফল 996, bazar.haat-এর প্রথম লাইন। খেয়াল করুন, এখানে “ফেরার ঠিকানা” কোথাও আলাদা করে লেখা হয়নি: caller-এর frame-এ তার নিজের ip-টি রয়ে গেছে, আর frame list-এর ক্রমটিই dynamic link. আসল যন্ত্রে এই দুটি জিনিস মেমরিতে স্পষ্ট লিখে রাখতে হয় (অংশ ৪)। আরেকটি সরলীকরণ: এই block // দিয়ে ভাগ করে, যা শুধু ধনাত্মক সংখ্যায় C-র /-এর সমান; reference-এর runtime.py ঋণাত্মক সংখ্যাও ঠিকভাবে সামলায়।

৩ · Nested function — static link, static chain আর display

C-তে function-এর ভেতরে function লেখা যায় না (GCC-র একটি নিজস্ব extension ছাড়া), তাই C-র একটি function দেখতে পায় শুধু নিজের local আর global. Pascal, Ada, Haat, Python, JavaScript-এ nested function আছে, আর ভেতরের function বাইরের function-এর local পড়তে পারে। নিচের Haat program-এ extra লেখা আছে fee-এর ভেতরে, আর fee লেখা order-এর ভেতরে। extra পড়ে km (এক স্তর বাইরে) আর base (দুই স্তর বাইরে)।

fn order(qty: Int, unit: Int) -> Int {
    let base = qty * unit;
    fn fee(km: Int) -> Int {
        fn extra(w: Int) -> Int {
            return w * km + base / 100;
        }
        return 40 + extra(2);
    }
    fn total_for(km: Int) -> Int {
        return base + fee(km);
    }
    return total_for(3);
}
print(order(2, 520));

~/haat $ python haat.py run chain.haat
1096
~/haat $ python haat.py vm chain.haat
1096

সমস্যাটি হলো: extra চলার সময় base-এর মান কোন frame-এ? Caller-এর frame-এ খুঁজলে হবে না: fee-কে ডেকেছে total_for, যার ভেতরে base নেই। দরকার লেখার দিক থেকে ঘিরে থাকা function-এর frame. এর জন্য প্রতিটি frame-এ একটি বাড়তি pointer রাখা হয়: static link, যা ঘিরে থাকা function-এর সবচেয়ে সাম্প্রতিক frame দেখায় (পর্ব ১৫-এ এর পরিচয় পেয়েছেন)। আর caller-এর frame দেখানো pointer-টি হলো dynamic link. Dragon Book নামে পরিচিত পাঠ্যবই এদের বলে access link আর control link.

কোন ডাকে কোন static link — নিয়ম আর প্রমাণের রূপরেখা

প্রতিটি function-কে একটি গভীরতা দিন: top level-এর কোড 0, order 1, fee আর total_for 2, extra 3. গভীরতা compile-এর সময় জানা, কারণ এটি শুধু লেখার গঠনের ওপর নির্ভর করে। তাহলে দুটি নিয়ম:

  1. নাম পড়া: d গভীরতার function গভীরতা e-তে ঘোষিত একটি নাম পড়লে static link ধরে d − e বার হাঁটে, তারপর সেই frame-এর নির্দিষ্ট offset-এ পড়ে। এই হাঁটার পথের নাম static chain.
  2. ডাকা: df গভীরতার f যখন dg গভীরতার g-কে ডাকে, caller নিজের frame থেকে static link ধরে df − dg + 1 বার হাঁটে; যে frame-এ পৌঁছায়, সেটিই g-এর নতুন frame-এর static link.

দাবি। প্রতিটি সক্রিয় frame-এর static link তার function-এর লেখার দিক থেকে ঠিক বাইরের function-এর সঠিক (সবচেয়ে সাম্প্রতিক দৃশ্যমান) frame দেখায়। প্রমাণের রূপরেখা (ডাকের সংখ্যার ওপর induction):

  1. শুরুতে শুধু top level-এর frame, যার static link নেই; দাবি ফাঁকা অর্থে সত্য।
  2. ধরুন সব সক্রিয় frame-এর জন্য দাবি সত্য, আর f (গভীরতা df) ডাকছে g-কে (গভীরতা dg). f থেকে g দেখা যায়, তাই g ঘোষিত হয়েছে f-এর নিজের ভেতরে বা f-কে ঘিরে থাকা কোনো function-এ। g-এর বাইরের function-এর গভীরতা dg − 1, আর সেটি f বা f-এর কোনো পূর্বপুরুষ, তাই dg − 1 ≤ df.
  3. f-এর frame থেকে static link ধরে প্রতিটি ধাপে গভীরতা ঠিক ১ কমে (induction-এর অনুমান), তাই df − (dg − 1) = df − dg + 1 ধাপে পৌঁছানো যায় গভীরতা dg − 1-এর পূর্বপুরুষ frame-এ, যা ঠিক g-এর বাইরের function-এর frame. নতুন frame-এর জন্য দাবি সত্য; ফেরার সময় শুধু frame সরে, অন্য কারও link বদলায় না। ∎

নিচের stepper-এ পুরো program-টি চলে। প্রতিটি ডাকে নতুন frame-এর static link কত ধাপে খোঁজা হলো, আর ডানে একই সময়ে display (প্রতি গভীরতার জন্য একটি ঘরের ছোট array) কেমন দেখায়, দুটিই লক্ষ করুন।

1fn order(qty: Int, unit: Int) -> Int {2    let base = qty * unit;3    fn fee(km: Int) -> Int {4        fn extra(w: Int) -> Int {5            return w * km + base / 100;6        }7        return 40 + extra(2);8    }9    fn total_for(km: Int) -> Int {10        return base + fee(km);11    }12    return total_for(3);13}14print(order(2, 520));
Frame-এর stack (নিচ → ওপর)
stack
নতুন SL
display
  1. main ডাকে order. caller-এর গভীরতা 0, callee-র 1: 0 − 1 + 1 = 0 ধাপ, তাই static link হলো caller নিজে, top level-এর frame. display-এর D[1]-এ order.
  2. order ডাকে total_for. নিজের base = 2 × 520 = 1040 (0 ধাপ, নিজের frame). total_for গভীরতা 2, order-এর ভেতরে লেখা: 1 − 2 + 1 = 0 ধাপ, static link = order.
  3. total_for ডাকে fee. base পড়তে 1 ধাপ। এবার মজার অংশ: fee-ও গভীরতা 2, তাই 2 − 2 + 1 = 1 ধাপ: total_for-এর static link ধরে পৌঁছায় order-এ। dynamic link total_for, কিন্তু static link order. display-এ D[2]-এর পুরোনো মান (total_for) fee-র frame-এ রেখে D[2] = fee.
  4. fee ডাকে extra. extra লেখা fee-র ভেতরে: 2 − 3 + 1 = 0 ধাপ, static link = fee. এখন পাঁচটি frame, আর display-এ চারটি ঘর ভরা।
  5. km পড়া। km ঘোষিত গভীরতা 2-এ (fee-র parameter), extra গভীরতা 3: 1 ধাপ, fee-র frame-এ km = 3. display দিয়ে: D[2] সরাসরি fee, কোনো হাঁটা নেই।
  6. base পড়া। 3 − 1 = 2 ধাপ: extra → fee → order, মান 1040. খেয়াল করুন, পথে total_for আসেনি, যদিও সে stack-এ আছে। display দিয়ে D[1] = order, এক ধাপে। ফল 2 × 3 + 1040 / 100 = 6 + 10 = 16.
  7. ফেরা। extra 16 → fee 40 + 16 = 56 → total_for 1040 + 56 = 1096 → order 1096 → ছাপা 1096, reference-এর সত্যিকারের run আর vm-এর সমান। fee ফেরার সময় রাখা পুরোনো মানটি D[2]-এ ফিরিয়ে দেয় (আবার total_for), তাই display সবসময় সঠিক থাকে।

নিয়ম দুটি এবার কোডে। নিচের block chain.haat-কে হাতে “compile” করে: প্রতিটি Haat function একটি Python function, যার শুরুতে call একটি activation record বানায় আর ওপরের নিয়মে static link খোঁজে, আর প্রতিটি নাম পড়া হয় get দিয়ে, ঘোষণার গভীরতা বলে দিয়ে। সবচেয়ে ভেতরের মুহূর্তে পুরো stack ছাপা হয়।

# chain.haat হাতে "compile" করা: প্রতিটি ডাকে activation record, static আর dynamic link
class AR:
    def __init__(s, name, depth, static, dynamic, vars):
        s.name, s.depth, s.static, s.dynamic, s.vars = name, depth, static, dynamic, vars
def call(name, depth, caller, **args):        # callee-র static link খোঁজা
    sl = caller
    for _ in range(caller.depth - depth + 1): sl = sl.static
    return AR(name, depth, sl, caller, args)
def get(ar, name, decl_depth):                # static chain ধরে হাঁটা
    a = ar
    for _ in range(ar.depth - decl_depth): a = a.static
    return a.vars[name]
def snapshot(a):                              # dynamic link ধরে নিচে
    while a:
        sl = a.static.name if a.static else "-"; dl = a.dynamic.name if a.dynamic else "-"
        print(f"{a.name:9} depth {a.depth}  SL→{sl:9} DL→{dl:9} {a.vars}")
        a = a.dynamic
def extra(caller, w):                         # depth 3, fee-র ভেতরে লেখা
    ar = call("extra", 3, caller, w=w)
    snapshot(ar)
    km, base = get(ar, "km", 2), get(ar, "base", 1)
    print(f"km: {ar.depth - 2} hop -> {km}, base: {ar.depth - 1} hops -> {base}")
    return w * km + base // 100
def fee(caller, km):                          # depth 2, order-এর ভেতরে
    ar = call("fee", 2, caller, km=km)
    return 40 + extra(ar, 2)
def total_for(caller, km):                    # depth 2, order-এর ভেতরে
    ar = call("total_for", 2, caller, km=km)
    return get(ar, "base", 1) + fee(ar, km)
def order(caller, qty, unit):                 # depth 1, top level-এ
    ar = call("order", 1, caller, qty=qty, unit=unit)
    ar.vars["base"] = get(ar, "qty", 1) * get(ar, "unit", 1)
    return total_for(ar, 3)
main = AR("<main>", 0, None, None, {})
print("result:", order(main, 2, 520))

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

extra     depth 3  SL→fee       DL→fee       {'w': 2}
fee       depth 2  SL→order     DL→total_for {'km': 3}
total_for depth 2  SL→order     DL→order     {'km': 3}
order     depth 1  SL→<main>    DL→<main>    {'qty': 2, 'unit': 520, 'base': 1040}
<main>    depth 0  SL→-         DL→-         {}
km: 1 hop -> 3, base: 2 hops -> 1040
result: 1096

এটিই পরীক্ষায় চাওয়া “একটি নির্দিষ্ট মুহূর্তে activation record-এর stack”, পুরোটা হিসাব করা। সবচেয়ে গুরুত্বপূর্ণ লাইন fee … SL→order DL→total_for: দুটি link আলাদা হয় ঠিক তখন, যখন একটি function-কে তার “ভাই” ডাকে। ফল 1096, reference-এর সঙ্গে একই। এখানে // নিরাপদ, কারণ সব মান ধনাত্মক।

ছবি ৩০.২ — extra চলার মুহূর্তে পাঁচটি activation record

বাঁয়ের কালো তীর dynamic link, ডানের বেগুনি তীর static link; মান ওপরের block-এর আসল আউটপুট থেকে

Stack of activation records for chain.haat while extra runs, with dynamic links on the left and static links on the right extra (d 3) w = 2 fee (d 2) km = 3 total_for (d 2) km = 3 order (d 1) qty 2, unit 520 base = 1040 main (d 0) DL SL base: extra → fee → order
ছবি ৩০.২ — বাঁয়ে dynamic link প্রতিটি frame থেকে তার caller-এ; ডানে static link লেখার দিক থেকে ঘিরে থাকা function-এ। fee-র static link total_for-কে ডিঙিয়ে সরাসরি order-এ যায়। base পড়ার দুই ধাপের পথ: extra → fee → order.

Display — চলার খরচ কমানোর পুরোনো কৌশল

Static chain-এ k স্তর বাইরের নাম পড়তে k-টি মেমরি-পড়া লাগে। Display এই খরচ এক ধাপে নামায়: D[i] সবসময় গভীরতা i-এর সবচেয়ে সাম্প্রতিক দৃশ্যমান frame দেখায়, তাই গভীরতা e-তে ঘোষিত নাম পড়া মানে D[e] থেকে offset. দাম দিতে হয় ডাকার সময়: গভীরতা d-এর function শুরুতে D[d]-এর পুরোনো মান নিজের frame-এ রেখে D[d]-এ নিজেকে বসায়, আর ফেরার সময় পুরোনো মান ফিরিয়ে দেয় (stepper-এর ধাপ ৩ আর ৭)। এই ধারণা সাধারণত Dijkstra-র ১৯৬০ সালের ALGOL 60 বাস্তবায়নের কাজের সঙ্গে যুক্ত করা হয়।

কৌশলবাইরের নাম পড়াডাকার খরচFunction ফেরত দেওয়া যায়?
Static chaink স্তর বাইরে হলে k-টি পড়াstatic link খুঁজতে কয়েক ধাপনা: frame সরে গেলে link ঝুলে থাকে
Displayসবসময় এক ধাপএকটি ঘর রাখা আর ফেরত দেওয়ানা, একই কারণে
Closure আর cell (Haat reference)closure-এর নিজের তালিকা থেকে এক ধাপclosure বানানোর সময় cell-এর তালিকা কপিহ্যাঁ: cell heap-এ বাঁচে

Haat-এ function first-class, ফেরতও দেওয়া যায় (nested.haat-এর adder), তাই reference static link ব্যবহার করে না। chain.haat-এর extra-র সত্যিকারের dis:

== extra (arity 1, locals 1) ==
   0  LOAD_LOCAL     0     ; w
   1  LOAD_FREE      0     ; km
   2  MUL
   3  LOAD_FREE      1     ; base
   4  CONST          0     ; 100
   5  DIV
   6  ADD
   7  RETURN

base দুই স্তর বাইরে হলেও এখানে কোনো হাঁটা নেই: LOAD_FREE 1 মানে “আমার closure-এর ১ নম্বর cell”. fee যখন extra-র closure বানায়, তখনই km আর base-এর cell-গুলোর ঠিকানা তালিকায় কপি হয় (README-এর closure scheme). এর নাম flat closure, আর পুরো রূপান্তরটি closure conversion; বিস্তার পর্ব ১৭-এ আর পর্ব ৫৭-এ (Environment আর closure-এর বাস্তবায়ন)। পুরোনো static link কৌশল জানার কারণ দুটি: Pascal আর Ada-র ধাঁচের compiler এখনো এভাবে চলে, আর পরীক্ষায় activation record আঁকার প্রশ্ন এই মডেলেই আসে।

৪ · আসল যন্ত্রে — calling convention, prologue আর epilogue

VM-এ frame একটি Python object; আসল CPU-তে frame হলো stack মেমরির এক টুকরো, আর argument যায় register-এ। দুটি আলাদাভাবে compile করা function (হয়তো দুটি আলাদা compiler-এ) কীভাবে একমত হয় যে প্রথম argument কোন register-এ, ফল কোথায়, কোন register কে বাঁচাবে? এই চুক্তির নাম calling convention, যা একটি platform-এর ABI-এর অংশ। পুরো ABI, struct পাঠানো, varargs আর ভিন্ন platform-এর তুলনা পর্ব ৭১-এ (Calling convention আর ABI); এখানে শুধু মূল তিনটি:

বিষয়System V x86-64 (Linux, macOS)Windows x64RISC-V (LP64 psABI)
Integer argumentrdi rsi rdx rcx r8 r9rcx rdx r8 r9a0–a7
ফলের মানraxraxa0 (আর a1)
ফেরার ঠিকানাcall stack-এ রাখেcall stack-এ রাখেcall register ra-তে রাখে
Callee-savedrbx rbp r12–r15rbx rbp rdi rsi r12–r15 (আর xmm6–15)s0–s11, sp
বিশেষ১২৮ byte-এর red zone৩২ byte-এর shadow spacestack ১৬ byte-এ সাজানো

এবার সত্যিকারের compiler. একটি ফাইলে C-তে লেখা price (Haat-এর price-এর মতো), আরেকটি ফাইলে তাকে ডাকা order, যাতে compiler ডাকটি গিলে ফেলতে (inline করতে) না পারে:

/* fee.c */
long price(long qty, long unit) {
    long p = qty * unit;
    if (p >= 1000) return p - p / 10;
    return p;
}
/* order.c */
long price(long qty, long unit);
long order(void) { return price(2, 520) + 60; }

সত্যিকারের run: Zig 0.17.1-এর সঙ্গে আসা Clang 22.1.8, zig cc --target=… -S -g0, -O0-তে -fno-sanitize=undefined; .cfi directive আর কয়েকটি section-এর লাইন বাদ।

order:
        push    rbp
        mov     rbp, rsp
        mov     edi, 2              # ১ম argument
        mov     esi, 520            # ২য় argument
        call    price@PLT
        add     rax, 60             # ফল rax-এ
        pop     rbp
        ret
price:
        push    rbp                 # পুরোনো fp রাখা
        mov     rbp, rsp            # নতুন fp
        mov     qword ptr [rbp - 16], rdi   # qty
        mov     qword ptr [rbp - 24], rsi   # unit
        mov     rax, qword ptr [rbp - 16]
        imul    rax, qword ptr [rbp - 24]
        mov     qword ptr [rbp - 32], rax   # p
        …
        mov     rax, qword ptr [rbp - 8]
        pop     rbp
        ret
price:
        push    rbp
        mov     rbp, rsp
        imul    rdi, rsi            # p সরাসরি register-এ
        cmp     rdi, 1000
        jl      .LBB0_2
        movabs  rcx, -3689348814741910323
        mov     rax, rdi
        mul     rcx                 # ÷10, গুণ দিয়ে
        shr     rdx, 3
        sub     rdi, rdx
.LBB0_2:
        mov     rax, rdi
        pop     rbp
        ret
order:
        push    rbp
        sub     rsp, 32             # shadow space
        lea     rbp, [rsp + 32]
        mov     ecx, 2              # ১ম argument: rcx
        mov     edx, 520            # ২য় argument: rdx
        call    price
        add     eax, 60
        add     rsp, 32
        pop     rbp
        ret

তিনটি জিনিস পড়ুন। (১) Linux-এ argument এসেছে edi/esi-তে (rdi/rsi-এর নিচের অর্ধেক; ছোট ধ্রুবক লিখলে ওপরের অর্ধেক নিজেই শূন্য হয়), Windows-এ ecx/edx-এ, আর ফল দুটিতেই rax/eax-এ। একই C কোড, দুটি ভিন্ন চুক্তি। Windows-এ long ৩২ বিটের, তাই সেখানে eax; সেটিও ABI-র অংশ। (২) -O0-তে compiler প্রতিটি parameter আর local-কে frame-এ নামিয়ে রাখে ([rbp - 16], [rbp - 24], [rbp - 32]), যাতে debugger সব দেখতে পায়; -O2-তে p কখনো মেমরিতে যায়ই না। (৩) Windows-এর caller ডাকের আগে ৩২ byte ফাঁকা রাখে (sub rsp, 32), callee চাইলে চারটি register argument সেখানে নামাতে পারে। এই zig cc ডিফল্টে -O2-তেও push rbp/mov rbp, rsp রেখেছে; frame pointer বাদ দেওয়ার প্রশ্নে একটু পরে আসছি।

RISC-V — একটি পূর্ণ frame, ঘরে ঘরে

RISC-V-এর -O0 আউটপুট frame-এর গঠন সবচেয়ে পরিষ্কার দেখায়, কারণ এখানে call ফেরার ঠিকানা stack-এ নয়, register ra-তে রাখে, আর বাকি সব কাজ সাধারণ নির্দেশে স্পষ্ট লেখা। সত্যিকারের run --target=riscv64-linux-musl -O0: order-এর frame ১৬ byte (শুধু ra আর s0), price-এর ৪৮ byte. Hardware-এর দিক থেকে এই নিয়মগুলো Computer Architecture কোর্সের পর্ব ৩০-এ, আর C-র দিক থেকে C কোর্সের পর্ব ৪৬-এ আছে; এখানে compiler-এর চোখে দেখি। ধরুন ডাকের আগে sp-এর মান S.

1li   a0, 22li   a1, 5203call price4addi sp, sp, -485sd   ra, 40(sp)6sd   s0, 32(sp)7addi s0, sp, 488sd   a0, -32(s0)9sd   a1, -40(s0)10… mul, blt, ÷10 …11ld   a0, -24(s0)12ld   ra, 40(sp)13ld   s0, 32(sp)14addi sp, sp, 4815ret16addi a0, a0, 60
Register আর frame
a0, a1
sp, s0
ra
frame
  1. Caller-এর কাজ। order argument বসায় a0 = 2, a1 = 520, তারপর call price: পরের নির্দেশের ঠিকানা (ধরুন R) যায় ra-তে, লাফ price-এ। order-এর নিজের fp s0 = S+16, কারণ order-এর ১৬ byte-এর frame-এর ওপরের কিনারা সেটি।
  2. জায়গা নেওয়া। addi sp, sp, -48: stack নিচের দিকে বাড়ে, তাই ৪৮ বিয়োগ। ৪৮ ১৬-এর গুণিতক, RISC-V psABI-র alignment নিয়ম মেনে।
  3. দুটি জিনিস বাঁচানো। ra যায় S−8-এ, order-এর s0 (S+16) যায় S−16-এ। এই দ্বিতীয়টিই dynamic link: caller-এর frame কোথায় ছিল। price নিজে কাউকে ডাকে না, তবু -O0-তে compiler সব নিয়ম পুরোপুরি মানে।
  4. নতুন frame pointer. s0 = sp + 48 = S, অর্থাৎ frame-এর ওপরের কিনারা। এখন থেকে সব ঘর s0-এর সাপেক্ষে ধ্রুবক দূরত্বে: অংশ ১-এর “base আর offset”.
  5. Parameter নামানো। qty → S−32, unit → S−40. -O0-তে প্রতিটি variable-এর একটি স্থায়ী ঘর থাকে, যাতে debugger পড়তে পারে।
  6. Body আর ফল। p = 1040 যায় S−48-এ, ফল 936 যায় S−24-এ, আর ld a0, -24(s0) ফলটি a0-তে তোলে: convention অনুযায়ী ফেরত মানের register.
  7. Epilogue: উল্টো ক্রমে। ra আর s0 আগের মানে ফেরে (R আর S+16). caller-এর frame pointer আবার ঠিক জায়গায়।
  8. ছেড়ে দিয়ে ফেরা। sp আবার S, ret লাফ দেয় ra-তে, অর্থাৎ R-এ: order-এর addi a0, a0, 60, ফল 996. price-এর ৪৮ byte-এ পুরোনো মান পড়ে থাকে, কিন্তু সেগুলো এখন “মৃত”; পরের ডাক সেগুলোর ওপর লিখবে।

-O2 আর frame pointer বাদ দেওয়া

একই ফাইল -O2 -fomit-frame-pointer দিয়ে (সত্যিকারের run, riscv64):

price:                              order:
        mul     a0, a1, a0                  addi    sp, sp, -16
        li      a1, 1000                    sd      ra, 8(sp)
        blt     a0, a1, .LBB0_2             li      a0, 2
        lui     a1, 838861                  li      a1, 520
        …  (÷10, গুণ দিয়ে)                  call    price
        sub     a0, a0, a1                  addi    a0, a0, 60
.LBB0_2:                                    ld      ra, 8(sp)
        ret                                 addi    sp, sp, 16
                                            ret

price-এর কোনো prologue বা epilogue নেই, frame-ই নেই। এটি একটি leaf function: কাউকে ডাকে না, তাই ra নষ্ট হয় না, আর সব হিসাব register-এ ধরে যায়। order কিন্তু ra বাঁচাতে বাধ্য, কারণ তার নিজের call price ra-কে নতুন মান দিয়ে মুছে দেবে; না বাঁচালে order নিজের caller-এর কাছে আর ফিরতে পারত না। s0 আর রাখা হয়নি: এটিই frame pointer omission. লাভ একটি বাড়তি register আর কয়েকটি কম নির্দেশ; দাম হলো debugger আর profiler-এর পক্ষে frame-এর শিকল ধরে হাঁটা কঠিন হয় (ভাবনার প্রশ্ন ৪)। flag ছাড়া একই -O2-তে এই zig cc দুটি function-এই ra আর s0 রেখেছিল।

frame-এর আকার কে ঠিক করে? Compiler সব local, temporary আর spill-এর জায়গা যোগ করে, তারপর alignment অনুযায়ী ওপরের দিকে গোল করে। price-এর -O0 frame-এ ছয়টি ৮-byte ঘর (ra, s0, ফল, qty, unit, p) = ৪৮, যা আগেই ১৬-এর গুণিতক। C99-এর variable-length array বা alloca থাকলে frame-এর আকার চলার সময় ঠিক হয়; তখন sp নড়ে যায়, আর local খুঁজতে স্থির একটি frame pointer প্রায় বাধ্যতামূলক হয়ে পড়ে।

৫ · Stack কত গভীর — stack overflow, ভাষাভেদে

প্রতিটি ডাক কিছু মেমরি নেয়, আর stack-এর মাপ সীমিত। সীমা পার হলে ঘটে stack overflow. ভাষা আর runtime ভেদে এর রূপ খুব আলাদা। Haat reference দুই back end-এই ১০০০টির বেশি nested call হলে stack overflow runtime error দেয় (README-এর সিদ্ধান্ত ২৬; সত্যিকারের run আর গণনা পর্ব ১৬-এ, আর অনুশীলন ৪-এ একটি নতুন উদাহরণ)। VM-এ সীমাটি একটি সংখ্যা, কারণ vm.py প্রতিটি CALL-এর আগে len(frames) গোনে। অন্য runtime-গুলো কী করে? প্রথমে JavaScript, এই পাতাতেই, আপনার browser-এর engine-এ:

// কত গভীর পর্যন্ত recursion চলে? engine আর frame-এর আকারের ওপর নির্ভর করে
let depth = 0;
function small(n) {                 // ছোট frame: একটি parameter
  depth++;
  return small(n + 1) + 1;
}
function big(n) {                   // বড় frame: অনেক local
  depth++;
  const a = n + 1, b = a * 2, c = b - 3, d = c * a, e = d + b;
  const f = e * c, g = f - d, h = g + a, i = h * 2, j = i - b;
  return big(j % 7) + a + b + c + d + e + f + g + h + i + j;
}
function probe(fn) {
  depth = 0;
  try { fn(0); } catch (err) {
    return { depth, name: err.name, isRangeError: err instanceof RangeError };
  }
}
const s = probe(small), b = probe(big);
console.log("small:", JSON.stringify(s));
console.log("big:  ", JSON.stringify(b));
console.log("big frame -> fewer calls:", b.depth < s.depth);
console.log("both deeper than Haat's 1000:", s.depth > 1000 && b.depth > 1000);

আসল আউটপুট (যাচাইয়ের সময় Microsoft Edge-এর V8 engine-এ; আপনার browser-এ সংখ্যা আলাদা হবে):

small: {"depth":13548,"name":"RangeError","isRangeError":true}
big:   {"depth":6236,"name":"RangeError","isRangeError":true}
big frame -> fewer calls: true
both deeper than Haat's 1000: true

error-এর নাম RangeError, আর সেটি ধরা গেছে: program crash করেনি, নিয়ন্ত্রিত একটি exception পেয়েছে। দুটি সংখ্যাই একটি নির্দিষ্ট engine, version আর মুহূর্তের ফল; লেখকের Node 24-এ (একই V8 পরিবার) small পরপর দুবার দিল 10428 আর 10427, আর big 5688 আর 5687: engine-এর setting বদলালে সংখ্যা অনেক বদলায়, আর একই engine-এও এক ঘর নড়তে পারে। কিন্তু সম্পর্কটি স্থির: বড় frame-এ কম ডাক। কারণ V8-এর সীমা বাঁধা stack-এর byte-এর মাপে, ডাকের সংখ্যায় নয়। SpiderMonkey (Firefox) বা JavaScriptCore (Safari) নিজের নিয়মে চলে; তাই “JavaScript-এ সর্বোচ্চ recursion এত” ধরনের কোনো একক সংখ্যা নেই।

এবার CPython. Python-এর প্রতিটি ডাকেও একটি frame হয়, আর sys._getframe() দিয়ে তা হাতে ধরা যায়: f_back হলো ঠিক dynamic link, f_locals হলো local-এর ঘর, f_lineno বলে frame এখন কোন লাইনে (যা “ফেরার পরে কোথা থেকে চলবে” তা জানায়)। Python কীভাবে চলে তার বড় ছবি Python কোর্সের পর্ব ০৫-এ.

# CPython-এর নিজের frame: f_back = dynamic link, f_locals = local-এর ঘর
import sys
def show_stack():
    f = sys._getframe(1)                       # যে ডেকেছে, তার frame
    while True:
        name = f.f_code.co_name
        local = dict(f.f_locals) if name != "<module>" else ""
        print(f"   {name:9} line {f.f_lineno:2}  {local}")
        if name == "<module>": break           # program-এর নিচতলা
        f = f.f_back                           # dynamic link ধরে নিচে
def price(qty, unit):
    p = qty * unit
    return p - p // 10 if p >= 1000 else p
def delivery(total):
    show_stack()
    return 0 if total >= 1000 else 60
def order():
    first = price(2, 520)
    return first + delivery(first)
print(order())

def depth(n):
    return 0 if n == 0 else 1 + depth(n - 1)
print("recursion limit:", sys.getrecursionlimit())
for n in (500, 5000):
    try: print(n, "->", depth(n))
    except RecursionError as e: print(n, "->", type(e).__name__, "|", e)

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

   delivery  line 15  {'total': 936}
   order     line 19  {'first': 936}
   <module>  line 20  
996
recursion limit: 1000
500 -> 500
5000 -> RecursionError | maximum recursion depth exceeded

প্রথম তিন লাইন হলো delivery চলার মুহূর্তের call stack, ওপর থেকে নিচে: delivery (total = 936), তাকে ডেকেছে order, যার local first = 936, আর সবার নিচে module. price-এর frame নেই, কারণ সেটি আগেই ফিরে গেছে: ঠিক stepper-এর মতো, একই সময়ে সব frame থাকে না। order-এর লাইন 19 মানে order এখন সেই লাইনে আটকে আছে, delivery ফিরলে সেখান থেকেই চলবে। নিচের অংশে CPython-এর recursion limit: সীমার মধ্যে 500 ঠিক চলে, 5000-এ RecursionError. Haat-এর মতোই এটি interpreter-এর নিজের গোনা সীমা, যা প্রকৃত C stack ফুরানোর আগেই থামায়।

Runtimeকী ঘটেসীমা কে ঠিক করে
Haat reference<line>:<col>: runtime error: stack overflow, callee-র শুরুতে১০০০টি nested call, দুই back end-এ একই
CPythonRecursionError, ধরা যায়sys.setrecursionlimit
V8 (Chrome, Edge, Node)RangeError, ধরা যায়stack-এর byte-মাপ
Java (JVM)StackOverflowErrorthread-এর stack মাপ, যেমন -Xss
C, C++সাধারণত segmentation fault বা crash; ভাষার নিয়মে কোনো নিশ্চয়তা নেইoperating system আর linker-এর দেওয়া stack মাপ

C-র ক্ষেত্রে operating system সাধারণত stack-এর শেষে একটি নিষিদ্ধ পাতা, guard page, রাখে, যাতে উপচে পড়া stack নীরবে অন্য মেমরি নষ্ট না করে সঙ্গে সঙ্গে ধরা পড়ে। তবে একটি খুব বড় local array একবারে guard page ডিঙিয়ে যেতে পারে; এজন্য কিছু compiler “stack probe” দিয়ে বড় frame-এর প্রতিটি পাতা একে একে ছুঁয়ে দেখে। নিরাপত্তার দিক থেকে stack-এর ভুল ব্যবহার (overflow, ফেরার ঠিকানা নষ্ট) কীভাবে প্রতিরোধ করা হয়, তা Cybersecurity কোর্সে আছে; এখানে বোঝার বিষয় একটিই: ফেরার ঠিকানা আর data একই stack-এ থাকে বলেই সীমা পরীক্ষা এত জরুরি।

৬ · সব frame কি stack-এ থাকে? Interpreter, closure আর আধুনিক runtime

“Activation record = stack-এর এক টুকরো” কথাটি C-র জন্য প্রায় সবসময় সত্য, কিন্তু সব ভাষায় নয়। একটি frame stack-এ রাখা যায় তখনই, যখন তার lifetime ঠিক LIFO: যে পরে তৈরি, সে আগে শেষ। তিনটি পরিস্থিতিতে এই শর্ত ভাঙে:

  • Closure: ফেরত দেওয়া function বাইরের variable ধরে রাখলে, সেই variable frame-এর চেয়ে বেশি দিন বাঁচে। সমাধান: শুধু ধরা variable-গুলো heap-এর cell-এ (Haat, CPython), অথবা পুরো frame heap-এ (কিছু Scheme আর ML বাস্তবায়ন)। এটিই পর্ব ১৭-এর funarg problem-এর বাস্তবায়ন-দিক।
  • Generator আর coroutine: function মাঝপথে থেমে পরে আবার চলে, তাই তার local থামার সময়ও বাঁচিয়ে রাখতে হয়। Python-এর generator-এর frame তাই heap-এর object-এ থাকে। বিস্তার পর্ব ৩১-এ (Generator, coroutine আর async/await).
  • লক্ষ লক্ষ হালকা thread: Go-র প্রতিটি goroutine কয়েক KB-এর ছোট stack নিয়ে শুরু করে, দরকার হলে runtime পুরো stack একটি বড় জায়গায় কপি করে বাড়ায়। Go 1.3-এর আগে (২০১৪ সালের দিকে) টুকরো জোড়া “segmented stack” ছিল, পরে কপি করার পদ্ধতিতে বদলানো হয়।

Interpreter-এর ক্ষেত্রে দুটি stack থাকে, আর দুটিকে গুলিয়ে ফেলা খুব সাধারণ ভুল। Haat VM-এ frames list হলো Haat program-এর call stack, কিন্তু vm.py-র run নিজে একটি সাধারণ Python loop: Haat-এর একটি ডাক Python-এর কোনো ডাক তৈরি করে না। তাই Haat-এ ১০০০টি ডাক হলেও Python-এর stack একটুও বাড়ে না। Tree-walking interpreter (interp.py) অন্যরকম: Haat-এর প্রতিটি ডাকে Python-এর নিজের কয়েকটি recursive ডাক হয়, তাই সেখানে Haat-এর গভীরতা শেষ পর্যন্ত Python-এর recursion limit-এর ওপর নির্ভর করে। দুটি back end-এর একই সীমা (১০০০) রাখার একটি কারণ এটিই: সীমা নিজে গুনলে দুটি বাস্তবায়ন সবসময় একই উত্তর দেয়। Tree-walking interpreter পর্ব ৫৬-এ, আর stack VM পর্ব ৫৯-এ আপনি নিজে বানাবেন।

আরও গভীরে: Recursion-সহ ALGOL 60 বাস্তবায়নের জন্য stack-এর ব্যবহার Edsger Dijkstra বর্ণনা করেন ১৯৬০ সালের “Recursive Programming” প্রবন্ধে; display-এর ধারণাও সাধারণত এই সময়ের কাজের সঙ্গে যুক্ত করা হয়। আধুনিক processor-এ display-এর সুবিধা কমেছে, কারণ বেশিরভাগ nested access এক-দুই স্তরের, আর static link একটি register-এ রাখলেই চলে। LLVM IR-এ এজন্য একটি বিশেষ parameter attribute nest আছে, যা static chain-কে একটি নির্দিষ্ট register-এ পাঠাতে বলে; GCC-র C nested function extension এটি ব্যবহার করে, আর nested function-এর ঠিকানা নিলে stack-এ ছোট একটি executable কোড-টুকরো (trampoline) বানায়, যার জন্য stack-কে executable রাখতে হতে পারে। এই নিরাপত্তা-ঝুঁকির কারণে অনেক প্রকল্প এই extension এড়িয়ে চলে।

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

  • Activation record-এ কী কী থাকে? parameter, local, temporary, ফেরার ঠিকানা, dynamic link (পুরোনো fp), static link (nested ভাষায়), সংরক্ষিত register.
  • Static link আর dynamic link-এর পার্থক্য? static link লেখার দিক থেকে ঘিরে থাকা function-এর frame দেখায় (নাম খোঁজার জন্য), dynamic link caller-এর frame (ফেরার জন্য)।
  • k স্তর বাইরের variable পড়তে static chain-এ কত ধাপ? k ধাপ; display থাকলে এক ধাপ।
  • Caller-saved আর callee-saved register কী? প্রথমটি callee নষ্ট করতে পারে, দরকার হলে caller বাঁচায়; দ্বিতীয়টি callee ব্যবহার করলে আগের মান ফিরিয়ে দিতে বাধ্য।
  • একটি নির্দিষ্ট মুহূর্তে activation record-এর stack আঁকুন। প্রতিটি সক্রিয় ডাকের জন্য একটি বাক্স, প্রতিটিতে parameter আর local-এর মান, আর দুই পাশে dynamic ও static link (অংশ ৩-এর উদাহরণ)।

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

Assembly আর frame-এর প্রশ্নে AI assistant-এর উত্তর খুব আত্মবিশ্বাসী শোনায়, কিন্তু এই বিষয়ে ভুলগুলো সূক্ষ্ম, কারণ convention প্রতিটি platform আর compiler-এর setting-এ আলাদা:

AI-এর ভুলকীভাবে ধরবেন
এক platform-এর নিয়ম সবখানে: Windows x64-এর উত্তরে rdi/rsi, বা “x86-64-এ সবসময় red zone”target বলে দিয়ে -S চালানো (--target=x86_64-windows-gnu বনাম x86_64-linux-gnu)
হাতে লেখা “compiler-এর আউটপুট”, যা আসল আউটপুটের সঙ্গে মেলে না (ভুল offset, অপ্রয়োজনীয় push)একই flag আর version-এ সত্যিকারের compiler চালিয়ে পাশাপাশি মেলানো
“-O2-তে frame pointer সবসময় বাদ যায়” বা উল্টোটা, নিশ্চিত দাবি হিসেবেসেই toolchain-এর ডিফল্ট দেখতে flag ছাড়া আর -fomit-frame-pointer দিয়ে দুবার compile
Static link আর dynamic link গুলিয়ে ফেলা; caller-এর frame-কে static link বলা“ভাই function ডাকে ভাইকে” এমন একটি উদাহরণে দুটি link আলাদা হয় কি না, simulator চালিয়ে দেখা
“Python বা JavaScript-এ recursion-এর সীমা এত” ধরনের একক সংখ্যাসেই version আর engine-এ চালিয়ে মাপা; সংখ্যার সঙ্গে engine আর version লিখে রাখা
Stack overflow-কে C-তে “নিশ্চিত segfault” বলাভাষার নিয়মে এটি নিশ্চিত কিছু নয়; বাস্তব আচরণ OS আর compiler-এর setting-এর ওপর নির্ভর করে

AI-কে ভালোভাবে কাজে লাগাতে target, compiler আর version বলে দিন, আর প্রতিটি দাবির যাচাইয়ের উপায় চান:

আমি Clang 22 দিয়ে riscv64-linux-musl আর x86_64-linux-gnu-এর জন্য নিচের C function compile করছি: long price(long qty, long unit) { long p = qty * unit; if (p >= 1000) return p - p / 10; return p; } ১. -O0-তে price-এর stack frame কত byte হবে বলে তুমি মনে করো, আর প্রতিটি ঘরে কী থাকবে (ra, s0, qty, unit, p)? এটি অনুমান হিসেবে চিহ্নিত করো। ২. আমি নিজে যাচাই করতে কোন কমান্ড চালাব, তা দাও (zig cc --target=… -O0 -S). এমন কোনো flag লিখবে না যার অস্তিত্ব তুমি নিশ্চিত নও। ৩. System V x86-64, Windows x64 আর RISC-V-এ প্রথম দুটি argument কোন register-এ যায়? প্রতিটির জন্য কোন ABI দলিল দেখব, তার নাম বলো। ৪. Pascal-এর মতো nested function-এ static link আর dynamic link কখন আলাদা হয়, তার একটি ছোট উদাহরণ দাও।

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

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

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

প্র ০১প্রথম দিকের FORTRAN stack ছাড়াই চলত। ALGOL 60 কী বদলাল, আর আজও কোথায় stack ছাড়া static frame বেছে নেওয়া হয়?

১৯৫৭ সালের FORTRAN-এর বাস্তবায়নে প্রতিটি subroutine-এর local variable, parameter-এর ঠিকানা আর ফেরার ঠিকানা থাকত একটি নির্দিষ্ট, স্থায়ী মেমরি-জায়গায়। অর্থাৎ প্রতিটি subroutine-এর একটিই activation record, compile-এর সময়েই তার ঠিকানা ঠিক। এর সুবিধা স্পষ্ট: কোনো stack pointer নেই, frame বানানোর নির্দেশ নেই, প্রতিটি variable-এর ঠিকানা একটি ধ্রুবক। সেই যুগের যন্ত্রে, যেখানে register আর মেমরি দুটিই দুর্লভ, এটি দ্রুত আর সরল ছিল। দাম হলো recursion: একটি subroutine নিজেকে ডাকলে নতুন ডাক পুরোনো ডাকের একমাত্র ঘর মুছে দেয়। তাই সেই সময়ের FORTRAN recursion-এর নিশ্চয়তা দিত না; Fortran-এ RECURSIVE keyword এসেছে অনেক পরে, Fortran 90-এ।

ALGOL 60 recursive procedure-কে ভাষার অংশ করে, সঙ্গে nested procedure আর block structure. এর মানে একই procedure-এর একাধিক সক্রিয় ডাক একসঙ্গে থাকতে পারে, আর প্রতিটির নিজের ঘর লাগে। Edsger Dijkstra ১৯৬০ সালের “Recursive Programming” প্রবন্ধে দেখান কীভাবে একটি stack দিয়ে এই কাজ করা যায়, আর nested scope-এর জন্য display-জাতীয় ব্যবস্থার ধারণা সাধারণত এই সময়ের কাজের সঙ্গে যুক্ত। এর পর থেকে প্রায় সব ভাষার বাস্তবায়নে stack-এর ওপর frame মূলধারা হয়ে যায়।

কিন্তু static frame পুরোপুরি হারায়নি। ছোট embedded system আর নিরাপত্তা-সংবেদনশীল সফটওয়্যারে প্রায়ই recursion নিষিদ্ধ করা হয় (যেমন গাড়ির সফটওয়্যারের জন্য প্রচলিত MISRA C নির্দেশিকায় recursion এড়ানোর নিয়ম আছে), কারণ তাহলে compiler বা বিশ্লেষণ-tool call graph দেখে সর্বোচ্চ stack ব্যবহার আগেই হিসাব করতে পারে। কিছু ছোট microcontroller-এর compiler তো সরাসরি local-গুলোকে static ঘরে বসায়, কারণ সেই চিপে মেমরির ঠিকানা দিয়ে stack চালানো ব্যয়বহুল। এক অর্থে এটি FORTRAN-এর পথেই ফেরা, সচেতনভাবে।

মূল উপলব্ধি: static frame সরল আর পূর্বানুমেয়, stack frame recursion আর nesting সম্ভব করে; ALGOL 60 আর Dijkstra-র কাজ stack-কে মূলধারায় আনে, কিন্তু যেখানে নিশ্চিত মেমরি-সীমা দরকার, সেখানে আজও ইচ্ছা করে recursion বাদ দিয়ে static হিসাব বেছে নেওয়া হয়।

প্র ০২Static link, display আর closure: আধুনিক ভাষার compiler কেন সাধারণত closure-এর পথ নেয়? Haat reference-এর সিদ্ধান্ত কি ঠিক?

Static link আর display দুটিই একটি অনুমানের ওপর দাঁড়ানো: ভেতরের function যতক্ষণ চলে, বাইরের function-এর frame-ও ততক্ষণ stack-এ বেঁচে থাকে। Pascal-এ এটি সত্য, কারণ সেখানে nested procedure-কে argument হিসেবে পাঠানো যায় কিন্তু ফেরত দেওয়া বা variable-এ রেখে পরে ডাকা যায় না; ডাকা পর্যন্ত বাইরের frame বেঁচে থাকার নিশ্চয়তা আছে। C-তে nested function-ই নেই, তাই প্রশ্ন ওঠে না।

Haat, JavaScript, Python, Scheme-এ function first-class: ফেরত দেওয়া যায়, data structure-এ রাখা যায়। Haat-এর nested.haat-এ adder(7) একটি function ফেরত দেয় যা n পড়ে, অথচ ফেরত আসার মুহূর্তে adder-এর frame শেষ। Static link তখন একটি মৃত frame দেখাত, যার জায়গায় হয়তো অন্য কোনো ডাকের data. এটিই upward funarg problem. দুটি সমাধান আছে: পুরো frame heap-এ রাখা (তখন garbage collector ঠিক করে কখন মুছবে), অথবা শুধু যে variable-গুলো সত্যিই ধরা হয়েছে সেগুলো heap-এর cell-এ সরানো আর closure-এ তাদের ঠিকানার একটি সমতল তালিকা রাখা।

Haat reference দ্বিতীয় পথ নিয়েছে, CPython-এর মতো। সুবিধা তিনটি। প্রথমত সঠিকতা: ফেরত দেওয়া closure নিরাপদ। দ্বিতীয়ত গতি: বাইরের নাম যত স্তর দূরেই হোক, LOAD_FREE i সবসময় এক ধাপ, static chain-এর মতো হাঁটা নেই। তৃতীয়ত মেমরি: closure শুধু যা ব্যবহার করে তা-ই ধরে রাখে, পুরো বাইরের frame নয়। খরচ হলো closure তৈরির সময় cell-এর তালিকা কপি করা, আর ধরা variable-এর প্রতিটি পড়ায় একটি বাড়তি indirection (cell-এর ভেতরে যাওয়া)।

অনেক optimizing compiler আরও এক ধাপ যায়: escape analysis দিয়ে দেখে কোন closure কখনো বাইরে যায় না; সেগুলোর জন্য heap-এর বদলে stack বা register যথেষ্ট, ঠিক Pascal-এর মতো সস্তায়। অর্থাৎ পুরোনো static link কৌশল হারিয়ে যায়নি, বিশ্লেষণের পরে একটি বিশেষ ক্ষেত্রের optimization হয়ে ফিরেছে।

মূল উপলব্ধি: function first-class হলে frame-এর lifetime আর LIFO থাকে না, তাই cell-ওয়ালা flat closure সাধারণ সমাধান; Haat-এর জন্য এটি সঠিক, আর static link থেকে যায় escape না করা function-এর সস্তা বিশেষ রূপ হিসেবে।

প্র ০৩একই x86-64 যন্ত্রে Linux আর Windows কেন আলাদা calling convention ব্যবহার করে? এই পার্থক্যের দাম কে দেয়?

Calling convention হার্ডওয়্যারের নিয়ম নয়, সফটওয়্যারের চুক্তি। CPU-র কাছে rdi আর rcx দুটিই সাধারণ register; কোনটিতে প্রথম argument যাবে, তা ঠিক করে platform-এর ABI দলিল। AMD-এর ৬৪ বিট x86 আসার সময় (২০০০-এর দশকের শুরুতে) Unix-ধাঁচের system-গুলোর জন্য System V ABI-র x86-64 অংশ লেখা হয়, আর Microsoft নিজের Windows x64 convention ঠিক করে। দুটি দল আলাদা অগ্রাধিকার থেকে সিদ্ধান্ত নিয়েছিল।

System V বেশি register-এ argument দেয় (ছয়টি integer), আর leaf function-এর জন্য sp-এর নিচে ১২৮ byte-এর red zone দেয়, যেখানে sp না সরিয়েই ছোট data রাখা যায়। Windows x64 চারটি register-এ argument দেয়, আর caller প্রতিটি ডাকের আগে ৩২ byte-এর shadow space রাখে, যাতে callee দরকার হলে register-এর argument মেমরিতে নামিয়ে রাখতে পারে; varargs function আর debugger-এর জন্য এটি সুবিধাজনক। এই পর্বের সত্যিকারের আউটপুটে ঠিক তা-ই দেখা গেছে: Linux-এ edi, esi; Windows-এ ecx, edx আর sub rsp, 32. callee-saved register-এর তালিকাও আলাদা: Windows-এ rdi আর rsi callee-saved, System V-এ নয়।

দাম দেয় তিন পক্ষ। Compiler-লেখকেরা: প্রতিটি back end-কে দুটি convention-ই জানতে হয়। মিশ্র কোড যারা লেখেন: হাতে লেখা assembly, JIT compiler, বা অন্য ভাষা থেকে C library ডাকার কোড (foreign function interface) প্রতিটি platform-এর জন্য আলাদা লিখতে হয়; ভুল হলে argument চুপচাপ ভুল register থেকে পড়া হয়। আর যারা দুই platform-এর binary একসঙ্গে চালান, যেমন Wine-এর মতো compatibility layer, তাদের প্রতিটি সীমানায় convention বদলাতে হয়।

এই কারণেই ABI একবার ঠিক হলে প্রায় কখনো বদলায় না: বদলালে পুরোনো সব compile হওয়া library-র সঙ্গে নতুন program ভুল চলবে। ভাষার নতুন version আসে, কিন্তু ABI বছরের পর বছর একই থাকে। পূর্ণ বিবরণ পর্ব ৭১-এ।

মূল উপলব্ধি: calling convention হলো দুটি অচেনা কোডের মধ্যে চুক্তি; একই হার্ডওয়্যারে ভিন্ন চুক্তি থাকতে পারে, আর একবার চালু হলে তা বদলানো এত ব্যয়বহুল যে ভুল বা অসুবিধাও স্থায়ী হয়ে যায়।

প্র ০৪Frame pointer রাখা উচিত, না বাদ দেওয়া উচিত? কেন কিছু বড় Linux বিতরণ এ নিয়ে সিদ্ধান্ত বদলেছে?

Frame pointer (x86-64-এ rbp, RISC-V-এ s0) বাদ দিলে দুটি লাভ: একটি register সাধারণ কাজে মুক্ত হয়, আর প্রতিটি function-এর শুরু-শেষে দু-একটি নির্দেশ কমে। ৩২ বিট x86-এ সাধারণ register ছিল মাত্র আটটি, সেখানে একটি register ফেরত পাওয়া বড় ব্যাপার ছিল, তাই -fomit-frame-pointer optimization-এর ডিফল্ট অংশ হয়ে ওঠে। x86-64-এ ষোলোটি আর RISC-V-এ বত্রিশটি register থাকায় লাভ অনেক কম, যদিও শূন্য নয়।

অন্যদিকে frame pointer থাকলে প্রতিটি frame-এ পুরোনো fp রাখা থাকে, ফলে একটি সরল linked list তৈরি হয়: বর্তমান fp থেকে শুরু করে পুরো call stack হেঁটে যাওয়া যায়, ঠিক অংশ ৫-এর Python-এর f_back-এর মতো। Profiler (যেমন Linux-এর perf) প্রতি সেকেন্ডে হাজার বার program থামিয়ে দেখে কোন function চলছে আর কে তাকে ডেকেছে; fp-এর শিকল থাকলে এই কাজ সস্তা আর নির্ভরযোগ্য। Frame pointer না থাকলে stack হাঁটতে লাগে আলাদা unwind তথ্য (DWARF-এর CFI, এই পর্বের আউটপুট থেকে বাদ দেওয়া .cfi লাইনগুলো), যা পড়া ধীর আর জটিল।

এই কারণে কয়েকটি বড় Linux বিতরণ সাম্প্রতিক বছরে আবার frame pointer চালু রেখে package বানানোর সিদ্ধান্ত নিয়েছে বলে ঘোষণা করেছে; প্রকাশিত আলোচনা অনুযায়ী Fedora ২০২৩ সালে আর Ubuntu ২০২৪ সালের LTS-এ এই পথ নেয়। যুক্তি ছিল: সাধারণ কাজে গতির ক্ষতি সামান্য, কিন্তু পুরো system-এর performance বোঝার সুবিধা বড়। এই পর্বের zig cc-ও ডিফল্টে -O2-তে frame pointer রেখেছে, যা আমরা নিজের চোখে দেখেছি।

সঠিক উত্তর তাই প্রেক্ষাপটের ওপর নির্ভর করে, আর মাপা ছাড়া কোনো দাবি করা ঠিক নয়: নিজের program-এ দুটি রূপ compile করে একই কাজের সময় মাপুন, আর সেই সংখ্যাকে এক যন্ত্রের উদাহরণ হিসেবেই দেখুন।

মূল উপলব্ধি: frame pointer বাদ দেওয়া একটি ছোট গতির লাভের বিনিময়ে debugger আর profiler-এর দৃষ্টি কমায়; register-সমৃদ্ধ আধুনিক যন্ত্রে পাল্লা আবার পর্যবেক্ষণযোগ্যতার দিকে ঝুঁকেছে।

প্র ০৫Haat, CPython আর JavaScript-এ recursion-এর সীমা “নিজে গোনা”, অথচ C-তে OS থামায়। একটি ভাষার নকশাকার হিসেবে আপনি কোনটি বেছে নেবেন, আর কেন?

C-র stack একটি সাধারণ মেমরি-এলাকা, যার মাপ ঠিক করে operating system আর linker (অনেক Linux system-এ মূল thread-এর জন্য ডিফল্ট সাধারণত ৮ MB, Windows-এ সাধারণত ১ MB). C ভাষা নিজে stack overflow-এর কোনো নির্দিষ্ট আচরণের নিশ্চয়তা দেয় না। বাস্তবে guard page-এ লেখার চেষ্টা হলে OS program বন্ধ করে দেয়, আর বাকি সব নির্ভর করে setting-এর ওপর। এর সুবিধা হলো শূন্য খরচ: প্রতিটি ডাকে কোনো গোনা নেই। অসুবিধা: error ধরা যায় না, আর কতটা গভীরে যাওয়া যাবে তা আগে থেকে বলা কঠিন, কারণ frame-এর আকার optimization-এর সঙ্গে বদলায়।

Managed runtime-গুলো সীমাটিকে ভাষার একটি নিয়ন্ত্রিত error বানায়। CPython ডাকের সংখ্যা গোনে আর RecursionError তোলে, যা try দিয়ে ধরা যায়; Java-র StackOverflowError আর V8-এর RangeError-ও তা-ই, যদিও V8 মাপে byte-এ (এই পর্বের probe-এ বড় frame-এ ডাক কম হয়েছে)। এর ফলে একটি ভুল recursive function পুরো server বন্ধ না করে শুধু একটি অনুরোধ ব্যর্থ করে। Interpreter-এর ক্ষেত্রে আরও একটি কারণ আছে: interpreter নিজে C বা অন্য ভাষায় লেখা, আর Haat-এর tree-walking interpreter-এর মতো হলে ভাষার প্রতিটি ডাক host-এর কয়েকটি ডাক খায়। নিজের সীমা আগে না থামালে host-এর stack ফুরিয়ে পুরো interpreter crash করত।

Haat reference একটি সংখ্যা (১০০০) বেছে নিয়েছে আর দুই back end-এ হুবহু একই রেখেছে (সিদ্ধান্ত ২৬)। শিক্ষার ভাষার জন্য এটি ভালো নকশা: আচরণ নির্ধারিত, test-এ মেলানো যায়, আর বার্তা স্পষ্ট (stack overflow, callee-র অবস্থান সহ)। খরচ হলো প্রতিটি CALL-এ একটি তুলনা, আর গভীর কিন্তু বৈধ recursion-এর সীমা কৃত্রিমভাবে ছোট। Production ভাষায় অনেকে সংখ্যার বদলে byte-এর সীমা নেয়, বা Go-র মতো stack বাড়িয়ে নেয়।

আরেকটি পথ হলো দরকারই কমানো: tail call-কে লাফে বদলানো, যাতে loop-এর মতো recursion stack না বাড়ায় (পর্ব ৩২)।

মূল উপলব্ধি: stack-এর সীমা নিজে গুনলে overflow একটি নির্ধারিত, ধরা যায় এমন error হয়, প্রতিটি ডাকে ছোট খরচের বিনিময়ে; C সেই খরচ নেয় না, আর তার দাম দেয় অনির্ধারিত crash দিয়ে।

অনুশীলন

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

  1. নকশা ও বাস্তবায়ন — Haat-এর বর্ধিত রূপে static link: ধরুন Haat-এর একটি পরীক্ষামূলক back end cell-এর বদলে static link দিয়ে বাইরের নাম পড়বে। নতুন নির্দেশ LOAD_OUTER h s মানে “static link ধরে h ধাপ হেঁটে সেই frame-এর slot s পড়া”। (ক) compiler-এর জন্য একটি function লিখুন, যা প্রতিটি নাম-ব্যবহারের জন্য LOAD_LOCAL, LOAD_OUTER বা LOAD_GLOBAL বাছে; chain.haat-এর slot নম্বর reference-এর dis-এর সঙ্গে মেলাতে হবে। (খ) VM-এ নতুন frame-এর static link কোথা থেকে আসবে? (গ) এই নকশা nested.haat-এর adder-এ কেন ভাঙবে?
    # Haat-এর বর্ধিত রূপ (নকশার খসড়া, reference-এ নেই)
    FUNCS = {"order": (None, ["qty", "unit", "base", "fee", "total_for"]),
             "fee": ("order", ["km", "extra"]),
             "total_for": ("order", ["km"]),
             "extra": ("fee", ["w"])}          # parent, slot-এর ক্রম
    def address(fn, name):
        hops = 0
        while fn:
            parent, slots = FUNCS[fn]
            if name in slots:
                s = slots.index(name)
                return ("LOAD_LOCAL", s) if hops == 0 else ("LOAD_OUTER", hops, s)
            fn, hops = parent, hops + 1
        return ("LOAD_GLOBAL", name)

    লেখকের CPython 3.14.4-এ চালানো ফল: extra-এ w → ('LOAD_LOCAL', 0), km → ('LOAD_OUTER', 1, 0), base → ('LOAD_OUTER', 2, 2), order → ('LOAD_GLOBAL', 'order'); total_for-এ base → ('LOAD_OUTER', 1, 2), fee → ('LOAD_OUTER', 1, 3). slot নম্বরগুলো reference-এর dis-এর সঙ্গে মেলে (order-এ MAKE_CELL 2 ; base, MAKE_CELL 3 ; fee; fee-তে km slot 0). (খ) Haat-এ function একটি মান, তাই caller সবসময় জানে না সে কাকে ডাকছে (যেমন twice(f, x)). অংশ ৩-এর “df − dg + 1 ধাপ” নিয়ম কাজ করে শুধু নাম ধরে সরাসরি ডাকে। সাধারণ সমাধান: MAKE_CLOSURE যে frame-এ চলে, সেই frame-টিকেই closure-এর সঙ্গে রাখা, আর CALL নতুন frame-এর static link বসায় closure-এর রাখা frame দিয়ে। নামে ডাকার ক্ষেত্রে দুটি নিয়ম একই উত্তর দেয়। (গ) adder(7) ফেরার পরে তার frame frames list থেকে সরে যায়, অথচ ফেরত দেওয়া function-এর static link সেই frame দেখায়। Python-এ object বেঁচে থাকবে বলে এই খসড়া হয়তো ঠিক উত্তরই দেবে, কিন্তু আসল যন্ত্রে stack-এর সেই জায়গা পরের ডাক মুছে দিত: dangling static link. তাই এই back end কেবল তখনই নিরাপদ, যখন escape analysis প্রমাণ করে যে কোনো nested function তার বাইরের frame-এর চেয়ে বেশি দিন বাঁচে না; বাকি সবক্ষেত্রে reference-এর cell-ই লাগবে।

  2. ভুল খুঁজুন: একজন সহকর্মী অংশ ৩-এর simulator-এ call-কে “সরল” করলেন: static link খোঁজার loop মুছে লিখলেন return AR(name, depth, caller, caller, args), অর্থাৎ static link = caller. chain.haat-এ কী ঘটবে, ঠিক কোন নাম পড়ায়? ভুলটি আসলে কোন scope-নিয়ম বানিয়ে ফেলেছে?

    সত্যিকারের run (লেখকের CPython 3.14.4, শুধু এই একটি লাইন বদলে): snapshot ছাপার পরে program থামে KeyError: 'base'-এ, get-এর ভেতরে। কারণ: extra-র static link এখন fee (এটি সঠিকই, কারণ fee-ই caller), কিন্তু fee-র static link হয়ে গেছে total_for, কারণ total_for তাকে ডেকেছে। extra থেকে base পড়তে ২ ধাপ: extra → fee → total_for, আর total_for-এর ঘরে শুধু km. km পড়া কাকতালীয়ভাবে ঠিক থাকে, কারণ ১ ধাপে fee-তেই পৌঁছায়। ভুলটি static link আর dynamic link-কে এক করে ফেলেছে: নাম খোঁজা হচ্ছে ডাকের শিকল ধরে, যা আসলে dynamic scoping-এর বাস্তবায়ন (পর্ব ১৫)। এখানে error এল বলে ধরা পড়ল; কিন্তু total_for-এর ভেতরেও যদি base নামে কোনো variable থাকত, program চুপচাপ ভুল মান পড়ত। সঠিক নিয়ম: caller থেকে df − dg + 1 ধাপ হাঁটা (এখানে 2 − 2 + 1 = 1, total_for → order). শিক্ষা: “ভাই ডাকে ভাইকে” ধাঁচের একটি test সবসময় রাখুন; শুধু সরাসরি nested ডাকের test এই ভুল ধরে না।

  3. হিসাব ও trace — activation record আঁকুন: নিচের Haat program-এ step(0) যে মুহূর্তে return n * 10; চালাচ্ছে, সেই মুহূর্তের activation record-এর stack আঁকুন: প্রতিটি frame-এর parameter, static link আর dynamic link. n পড়তে কত ধাপ? program কী ছাপবে?
    fn pay(n: Int) -> Int {
        fn step(k: Int) -> Int {
            if k == 0 { return n * 10; }
            return step(k - 1) + 1;
        }
        return step(2);
    }
    print(pay(5));
    step      depth 2  SL→pay       DL→step      {'k': 0}
    step      depth 2  SL→pay       DL→step      {'k': 1}
    step      depth 2  SL→pay       DL→pay       {'k': 2}
    pay       depth 1  SL→<main>    DL→<main>    {'n': 5}
    <main>    depth 0  SL→-         DL→-         {}

    এটি অংশ ৩-এর simulator-এ একই ধাঁচে লেখা pay আর step চালিয়ে পাওয়া সত্যিকারের snapshot (লেখকের CPython 3.14.4). পাঁচটি frame. তিনটি step-এর dynamic link আলাদা (প্রতিটি তার caller), কিন্তু static link তিনটিরই একই pay-এর frame: step নিজেকে ডাকলে df − dg + 1 = 2 − 2 + 1 = 1 ধাপ, অর্থাৎ caller-এর নিজের static link-টিই কপি হয়। n পড়তে 2 − 1 = 1 ধাপ, মান 5. ফল: step(0) = 50, step(1) = 51, step(2) = 52, তাই ছাপা হয় 52; reference-এর run আর vm দুটিই সত্যিকারের run-এ 52 দিয়েছে। reference-এর dis-এ step-এর ভেতরে n পড়া হয় LOAD_FREE 0 ; n দিয়ে, আর নিজেকে ডাকা LOAD_FREE 1 ; step দিয়ে: step নিজেও একটি ধরা variable, কারণ nested function নিজের body-তে নিজেকে দেখে (সিদ্ধান্ত ১৭)।

  4. আউটপুট অনুমান করুন: Haat reference-এ (সর্বোচ্চ ১০০০টি nested call) নিচের program কী ছাপবে? দ্বিতীয় লাইনের সবচেয়ে গভীর মুহূর্তে কয়টি frame (top level-এর frame সহ) থাকার কথা ছিল?
    fn total(n: Int) -> Int { if n == 0 { return 0; } return n + total(n - 1); }
    fn wrap(n: Int) -> Int { return total(n); }
    print(wrap(998));
    print(wrap(999));

    সত্যিকারের run (python haat.py run আর vm, দুটিতেই হুবহু এক):

    498501
    1:62: runtime error: stack overflow

    wrap(998): nested call হলো wrap ১টি আর total(998) থেকে total(0) পর্যন্ত ৯৯৯টি, মোট ১০০০টি, সীমার ঠিক মধ্যে; ফল 998 × 999 / 2 = 498501. wrap(999)-এ total-এর ডাক ১০০০টি, wrap-সহ ১০০১টি nested call; top level-এর frame ধরলে ১০০২টি frame লাগত। VM প্রতিটি CALL-এর আগে দেখে len(frames) > 1000 কি না; ১০০১তম nested call-এর সময় list-এ ১০০১টি frame (top level সহ), তাই error. অবস্থান 1:62 হলো প্রথম লাইনের ভেতরের total(n - 1)-এর callee total-এর শুরু (সিদ্ধান্ত ২৪: call-এর error callee-র শুরুতে)। প্রথম লাইনের আউটপুট রয়ে যায়, কারণ runtime error শুধু তার পরের অংশ থামায় (সিদ্ধান্ত ২৬)। মূল শিক্ষা: সীমা গোনে সক্রিয় frame, মোট ডাক নয়; wrap(998)-এ মোট ডাকও ১০০০টি, কিন্তু wrap(999)-এর বেলায় মাত্র একটি বেশি গভীরতাই যথেষ্ট।

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

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

ক্রমRISC-V-এ order যখন price(2, 520) ডাকে (frame pointer সহ, -O0), ঘটনাগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. caller argument বসায়: a0 = 2, a1 = 520
  2. call ফেরার ঠিকানা ra-তে রেখে price-এ লাফ দেয়
  3. callee sp কমিয়ে frame-এর জায়গা নেয়
  4. callee ra আর caller-এর s0 stack-এ রাখে, তারপর নতুন s0 বসায়
  5. body চলে, ফল a0-তে রাখা হয়
  6. callee ra, s0 আর sp ফিরিয়ে ret করে

Pascal-ধাঁচের static link বাস্তবায়নে একটি activation record-এর static link কোন frame দেখায়?

  • যে function ডেকেছে, তার frame
  • লেখার দিক থেকে ঘিরে থাকা function-এর সবচেয়ে সাম্প্রতিক frame
  • সবসময় global frame
  • নিজের frame-এর শুরু

C-তে long price(long qty, long unit) x86-64 Linux-এর (System V ABI) জন্য compile করলে unit কোন register-এ আসে?

  • rdi
  • rdx
  • rsi
  • rcx

RISC-V-এ একটি leaf function (যে কাউকে ডাকে না) -O2 আর frame pointer ছাড়া compile হলে প্রায়ই কোনো prologue থাকে না। কিন্তু অন্য function ডাকে এমন function-কে অন্তত কী বাঁচাতেই হয়?

  • ra (ফেরার ঠিকানা)
  • a0
  • t0
  • s0, সবসময়

একটি nested function গভীরতা 3-এ চলছে, আর গভীরতা 1-এ ঘোষিত একটি variable পড়ছে। static chain-এ কত ধাপ লাগে, আর display থাকলে কত?

  • ৩ ধাপ, display-এ ৩
  • ২ ধাপ, display-এ ২
  • ১ ধাপ, display-এ ১
  • ২ ধাপ, display-এ ১

Haat reference VM-এ প্রতিটি ডাকে একটি Frame(closure, ip, slots) তৈরি হয়ে frames নামের list-এ যোগ হয়, আর সব ডাক একটি operand stack ভাগ করে। এই VM-এ “ফেরার ঠিকানা” কোথায় থাকে?

  • Operand stack-এর একটি বিশেষ ঘরে
  • Caller-এর নিজের frame-এর ip-তে
  • Callee-র slot 0-তে
  • Python-এর নিজের call stack-এ

Haat program: fn order(qty: Int, unit: Int) -> Int { let base = qty * unit; fn fee(km: Int) -> Int { return km + base; } fn total_for(km: Int) -> Int { return fee(km); } return total_for(3); }. static link দিয়ে বাস্তবায়ন করলে, fee চলার সময় তার frame-এর static link আর dynamic link কোন frame দেখায়?

  • দুটিই order
  • দুটিই total_for
  • static link order, dynamic link total_for
  • static link total_for, dynamic link order

শব্দকোষ

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

মনে রাখুন

  1. Activation record: প্রতিটি ডাকের নিজের ঘর: argument, local, temporary, ফেরার ঠিকানা, dynamic link, দরকার হলে static link আর সংরক্ষিত register. ঠিকানা = চলার সময়ের base + compile-এর সময়ের offset.
  2. কাজ ভাগাভাগি: caller argument বসায় আর ডাকে; callee prologue-এ frame বানায়, epilogue-এ ভাঙে। Haat VM-এ CALL n আর RETURN; ফেরার ঠিকানা caller-এর ip.
  3. Static link: নাম পড়তে d − e ধাপ; ডাকার সময় caller থেকে df − dg + 1 ধাপ হেঁটে নতুন static link. Display এক ধাপে পড়ে, Haat reference cell-ওয়ালা closure ব্যবহার করে।
  4. Calling convention: System V-এ rdi rsi …, Windows x64-এ rcx rdx … আর shadow space, RISC-V-এ a0 a1 … আর ra; leaf function প্রায়ই frame ছাড়াই চলে।
  5. Stack overflow: Haat-এ ১০০০টি nested call, CPython-এ RecursionError, V8-এ byte-মাপের RangeError, C-তে সাধারণত crash; closure আর generator-এর জন্য frame-এর অংশ heap-এ যায়।

পরের পর্বে: পর্ব ৩১ (Generator, coroutine আর async/await — বিরতি দিয়ে চলা function). যে function মাঝপথে থেমে পরে আবার চলে, তার frame কোথায় থাকে, আর compiler কীভাবে তাকে একটি state machine-এ বদলায়।

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

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