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

Recursion আর tail call — stack ছাড়া loop

Recursion and Tail Calls — Loops Without a Stack

Taught in Bangla, this lesson shows why recursion piles up frames, defines tail position precisely, and adds a TAIL_CALL instruction to a small bytecode VM in in-page Python (Pyodide). Real Clang runs compare the -O0 call with the -O2 jmp and show a deep tail-recursive C program crashing at -O0 but finishing at -O2. It sorts out the rules for Scheme, C, Python, JavaScript, Rust and WebAssembly, then makes deep recursion safe with accumulators, trampolines and continuation-passing style.

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

  • Recursion চলার সময় frame কেন জমে, আর tail position-এর নিয়ম দিয়ে কোন call tail call তা নির্ভুলভাবে চেনা
  • Tail call optimization কীভাবে frame পুনর্ব্যবহার করে: একটি bytecode VM-এ TAIL_CALL বানিয়ে আর সত্যিকারের Clang-এর assembly পড়ে
  • Scheme, C, Python, JavaScript, Java, Rust, WebAssembly আর Haat-এর নিয়ম আলাদা করে বলা, অনুমান না করে
  • Accumulator রূপান্তর, trampoline আর continuation-passing style দিয়ে গভীর recursion নিরাপদ করা, আর রূপান্তর যে অর্থ বদলায় না তা প্রমাণ করা
  • Haat-এ tail call যোগ করার নকশা, তার সীমা আর debugging-এর দাম বোঝা

১ · Recursion যন্ত্রে কীভাবে চলে — frame আর অপেক্ষমাণ কাজ

ধরুন আপনি জেলা অফিসে একটি সনদ তুলতে গেছেন। প্রথম টেবিলের কর্মী বলেন, “পাশের টেবিল থেকে সই এনে আমাকে দিন, আমি সিল দেব।” তিনি আপনাকে মনে রাখেন, কারণ আপনি ফিরে আসবেন আর তাঁর কাজ বাকি। পাশের টেবিলও একই কথা বলে, তারপরের টেবিলও। শেষে চারজন কর্মী চারটি অসমাপ্ত কাজ মাথায় রেখে বসে থাকেন। এবার ভাবুন অন্য এক অফিস, যেখানে প্রত্যেকে বলেন, “পাশের টেবিলে যান, সনদ ওখান থেকেই নেবেন, আমার কাছে আর আসতে হবে না।” এখানে কাউকে কিছু মনে রাখতে হয় না। প্রথম অফিস হলো সাধারণ recursion, দ্বিতীয়টি tail call.

Recursion-এর মূল ধারণা, base case আর DSA-র দিক থেকে কোড লেখা আপনি DSA কোর্সের পর্ব ০৭-এ আর C কোর্সের পর্ব ১৫-এ দেখেছেন। পর্ব ১৬-এ (Lifetime আর storage) দেখেছেন, প্রতিটি call নিজের stack frame পায়, আর Haat-এর reference ১০০০টির বেশি nested call হলে stack overflow দেয়। এই পর্বের প্রশ্ন এক ধাপ গভীরে: frame-টি ঠিক কেন দরকার, আর কখন দরকার নেই।

Factorial দুইভাবে লেখা যায়। দুটিই Haat v1-এ বৈধ, আর দুটিই 120 ছাপে (reference-এর সত্যিকারের run):

fn fact(n: Int) -> Int {
    if n <= 1 { return 1; }
    return n * fact(n - 1);
}
fn fact_acc(n: Int, acc: Int) -> Int {
    if n <= 1 { return acc; }
    return fact_acc(n - 1, acc * n);
}
print(fact(5));
print(fact_acc(5, 1));
~/haat $ python haat.py run fact.haat
120
120
~/haat $ python haat.py dis fact.haat      # শুধু শেষের অংশ
== fact (arity 1, locals 1) ==
  ...
  11  CALL           1
  12  MUL
  13  RETURN
== fact_acc (arity 2, locals 2) ==
  ...
  13  CALL           2
  14  RETURN

Bytecode-এ পার্থক্যটি এক নজরে ধরা পড়ে। fact-এ CALL 1-এর পরে MUL: callee ফিরলে তার ফলকে n দিয়ে গুণ করতে হবে। তাই ডাকা-পক্ষের n আর ফেরার জায়গা (instruction 12) কোথাও বাঁচিয়ে রাখতে হয়: সেটিই frame. fact_acc-এ CALL 2-এর ঠিক পরে RETURN: callee যা ফেরত দেবে, সেটিই হুবহু ওপরে চলে যাবে। ডাকা-পক্ষের frame-এ তখন আর কোনো দরকারি তথ্য নেই। নিচের stepper-এ দুটি একসঙ্গে চলুক:

1fn fact(n: Int) -> Int {2    if n <= 1 { return 1; }3    return n * fact(n - 1);4}5fn fact_acc(n: Int, acc: Int) -> Int {6    if n <= 1 { return acc; }7    return fact_acc(n - 1, acc * n);8}
এই ধাপের পরে (ওপরে নতুন frame)
fact-এর stack
fact_acc (TCO)
frame: fact / acc
  1. শুরু। দুটি function-ই একটি করে frame নিয়ে শুরু: fact(4) আর fact_acc(4, 1).
  2. প্রথম recursive call. fact(4) জানে না fact(3) কত, তাই “4 × □” অপেক্ষমাণ রেখে নতুন frame খোলে: ২টি frame. fact_acc আগেই গুণ করে নেয় (acc = 1 × 4 = 4), আর তার কিছু বাকি নেই, তাই TCO থাকলে একই frame-এ এখন fact_acc(3, 4).
  3. দ্বিতীয় call. fact-এর ৩টি frame, দুটিতে কাজ বাকি। fact_acc(2, 12): acc = 4 × 3 = 12, তখনো ১টি frame.
  4. Base case-এর ঠিক আগে। fact-এর ৪টি frame; এটাই সর্বোচ্চ উচ্চতা। fact_acc(1, 24): পুরো উত্তর ইতিমধ্যে acc-এ জমা।
  5. Base case. fact(1) 1 ফেরত দিয়ে সরে যায়; fact(2) এবার 2 × 1 = 2 হিসাব করে। fact_acc(1, 24) acc = 24 ফেরত দেয়, আর যেহেতু মাঝের কোনো frame নেই, সেটি সরাসরি মূল ডাকা-পক্ষে যায়।
  6. ফেরার পথ। fact(3) হিসাব করে 3 × 2 = 6. লক্ষ করুন, fact-এর আসল গুণগুলো হয় ফেরার পথে, আর fact_acc-এর হয়েছিল যাওয়ার পথে।
  7. শেষ। fact(4) 4 × 6 = 24 ফেরত দেয়। উত্তর এক, কিন্তু সর্বোচ্চ frame ৪ বনাম ১. n বড় হলে প্রথমটির stack n-এর সমানুপাতে বাড়ে, দ্বিতীয়টির (TCO থাকলে) স্থির থাকে।

ছবি ৩২.১ — সর্বোচ্চ উচ্চতার মুহূর্তে দুই stack

বাঁয়ে fact(4): চারটি frame, তিনটিতে কাজ বাকি। ডানে fact_acc(4, 1) TCO-সহ: একটিই frame, বারবার নতুন মান।

Call stack of fact(4) with four frames versus fact_acc(4, 1) reusing one frame fact(4) tail call নয় fact(1) ফেরত 1 fact(2) বাকি: 2 × □ fact(3) বাকি: 3 × □ fact(4) বাকি: 4 × □ ৪টি frame একসঙ্গে fact_acc(4, 1) tail call, TCO-সহ একটি frame n=4, acc=1 n=3, acc=4 n=2, acc=12 n=1, acc=24 ফেরত 24 ১টি frame, বারবার
ছবি ৩২.১ — বাঁ দিকের প্রতিটি হলুদ frame একটি অসমাপ্ত গুণ ধরে আছে; এগুলোই stack খায়। ডান দিকে গুণ আগেই হয়ে যায়, তাই ঘুরে আসা তীরটি বোঝায়: পুরোনো মান মুছে একই frame-এ পরের call.

একটি সূক্ষ্ম কথা মনে রাখুন: fact_acc লিখলেই stack বাঁচে না। বাঁচবে কি না, তা নির্ভর করে বাস্তবায়ন সেই সুযোগ নেয় কি না, তার ওপর। Haat v1-এর reference নেয় না; তাই fact_acc-ও ১০০০টি frame-এর পরে থামে, অংশ ৩-এ সত্যিকারের run দেখবেন।

২ · Tail position — কোন call আসলেই শেষ কাজ

“শেষ লাইনে call” আর “শেষ কাজ call” এক জিনিস নয়। return n * fact(n - 1); শেষ লাইনে, কিন্তু শেষ কাজ গুণ। তাই সংজ্ঞাটি অবস্থান দিয়ে দিতে হয়। একটি expression tail position-এ থাকে, যদি তার মান হিসাব হওয়ার পরে function-এর আর কিছু করার না থাকে, শুধু সেই মানটি ফেরত দেওয়া ছাড়া। Tail position-এ থাকা function call-ই tail call. আর একটি function যদি নিজেকে tail call দিয়ে ডাকে, তাকে বলে tail recursion.

Haat v1-এর জন্য নিয়মগুলো লিখি। “tail(e)” মানে “e আছে tail position-এ”। দাগের ওপরের শর্ত সত্য হলে নিচেরটিও সত্য; ওপরে কিছু না থাকলে নিয়মটি শর্তহীন:

function-এর দেহে return e;
tail(e)
(T-Ret)
tail(a && b)
tail(b)
(T-And)
tail(a ∣∣ b)
tail(b)
(T-Or)
tail(f(a1, …, an))
এই call একটি tail call
(T-Call)

T-And আর T-Or কেন? a && b-এ (Haat-এ short-circuit, পর্ব ২৬) a মিথ্যা হলে ফল false, আর a সত্য হলে ফল হুবহু b-এর মান। তাই b হিসাবের পরে কিছু বাকি থাকে না। কিন্তু a নিজে কখনো tail position-এ নয়: তার পরে b-এর সিদ্ধান্ত বাকি। আর যা কখনো tail position নয়: গাণিতিক বা তুলনার operand, call-এর argument, if/while-এর শর্ত, let x = f();-এর মতো initializer, আর print(f());-এর argument. Haat-এ return ছাড়া function থেকে মান ফেরত যায় না, তাই নিয়ম এত ছোট; Scheme বা Rust-এর মতো expression-ভিত্তিক ভাষায় if-এর দুই শাখা আর block-এর শেষ expression-ও tail position পায়।

কোডTail call?কারণ
return fact_acc(n - 1, acc * n);হ্যাঁT-Ret, তারপর T-Call
return n * fact(n - 1);নাCall-এর পরে গুণ বাকি
return ok(n) && check(n - 1);check হ্যাঁ, ok নাT-And শুধু ডান দিককে tail করে
return f(g(x));f হ্যাঁ, g নাg-এর ফল দিয়ে f-কে ডাকা বাকি
Python: try: return f(x) finally: log()নাফেরার আগে finally চলবে (পর্ব ২৮)
C++: std::string s = …; return f(n);সাধারণত নাফেরার আগে s-এর destructor চলবে

শেষ দুই সারি দেখায় যে ভাষার “লুকানো কাজ” tail position নষ্ট করে। Exception handler, finally, destructor, এমনকি C-তে একটি local variable-এর ঠিকানা callee-র কাছে চলে গেলে, ডাকা-পক্ষের frame আর ফেলা যায় না। অংশ ৪-এ Clang-এর সত্যিকারের output-এ শেষেরটি দেখবেন।

৩ · Tail call optimization — frame ফেলে দিয়ে লাফ

সাধারণ call তিনটি কাজ করে: argument বসায়, ফেরার ঠিকানা মনে রেখে নতুন frame খোলে, আর callee-তে লাফ দেয়। Tail call-এ ফেরার পরে কিছু করার নেই, তাই tail call optimization (TCO) নতুন frame না খুলে বর্তমান frame-এর জায়গায় callee-কে বসায়: নতুন argument পুরোনো parameter-এর ঘরে লেখে, আর call-এর বদলে সাধারণ jump দেয়। ফেরার ঠিকানা বদলায় না, তাই callee শেষে সরাসরি আমাদের ডাকা-পক্ষে ফেরে। Callee যদি একই function হয়, jump-টি function-এর শুরুতে, অর্থাৎ recursion একটি loop হয়ে যায় (tail recursion elimination). অন্য function হলে একে অনেক compiler sibling call বলে।

একটি bytecode VM-এ এটি কয়েক লাইনের কাজ। Haat reference-এর dis থেকে sum_to-এর ১৫টি সত্যিকারের instruction নিচে হুবহু তুলে আনা হয়েছে। একটি peephole pass CALL n-এর ঠিক পরে RETURN দেখলে তাকে TAIL_CALL n বানায়, আর ছোট VM-টি TAIL_CALL-এ নতুন frame না খুলে বর্তমান frame-এর ip আর slot বদলে দেয়। Frame-এর সীমা reference-এর মতোই ১০০০:

# sum_to's real bytecode from `haat.py dis` (Haat reference), as (opcode, arg)
SUM_TO = [("LOAD_LOCAL", 0), ("CONST", 0), ("EQ", None), ("JUMP_IF_FALSE", 6),
          ("LOAD_LOCAL", 1), ("RETURN", None), ("LOAD_GLOBAL", 0), ("LOAD_LOCAL", 0),
          ("CONST", 1), ("SUB", None), ("LOAD_LOCAL", 1), ("LOAD_LOCAL", 0),
          ("ADD", None), ("CALL", 2), ("RETURN", None)]
CONSTS = [0, 1]
def tail_pass(code):                     # peephole: CALL n; RETURN  ->  TAIL_CALL n
    return [("TAIL_CALL", a) if op == "CALL" and i + 1 < len(code)
            and code[i + 1][0] == "RETURN" else (op, a)
            for i, (op, a) in enumerate(code)]
def run(code, n, limit=1000):            # only sum_to frames are counted here
    frames, stack, peak = [[0, [n, 0]]], [], 1          # frame = [ip, slots]
    while True:
        f = frames[-1]; op, a = code[f[0]]; f[0] += 1
        if op == "LOAD_LOCAL": stack.append(f[1][a])
        elif op == "CONST": stack.append(CONSTS[a])
        elif op == "LOAD_GLOBAL": stack.append("sum_to")
        elif op in ("EQ", "ADD", "SUB"):
            b, x = stack.pop(), stack.pop()
            stack.append(x == b if op == "EQ" else x + b if op == "ADD" else x - b)
        elif op == "JUMP_IF_FALSE":
            if not stack.pop(): f[0] = a
        elif op in ("CALL", "TAIL_CALL"):
            args = stack[-a:]; del stack[-a:]; stack.pop()   # pop args, callee
            if op == "TAIL_CALL": f[0], f[1] = 0, args       # reuse this frame
            elif len(frames) >= limit: return f"stack overflow (n = {n})"
            else: frames.append([0, args]); peak = max(peak, len(frames))
        elif op == "RETURN":
            frames.pop()
            if not frames: return f"{stack.pop()}  (peak frames: {peak})"

for n in (999, 1000): print("CALL     ", run(SUM_TO, n))
opt = tail_pass(SUM_TO)
print("changed:", [(i, op) for i, (op, a) in enumerate(opt) if op != SUM_TO[i][0]])
for n in (1000, 100_000): print("TAIL_CALL", run(opt, n))

আসল আউটপুট (Pyodide-এ, আর লেখকের যন্ত্রে CPython 3.14.4-এ হুবহু এক):

CALL      499500  (peak frames: 1000)
CALL      stack overflow (n = 1000)
changed: [(13, 'TAIL_CALL')]
TAIL_CALL 500500  (peak frames: 1)
TAIL_CALL 5000050000  (peak frames: 1)

প্রথম দুই লাইন Haat reference-এর আচরণ: sum_to(999, 0)-এ ১০০০টি frame একসঙ্গে (n = 999 থেকে 0), যা সীমার ভেতরে; sum_to(1000, 0)-এ ১০০১তম call আটকে যায়। তৃতীয় লাইন: peephole pass শুধু instruction 13 বদলেছে; base case-এর RETURN (instruction 5) আর শেষ RETURN যেমন ছিল তেমনই থাকে, তাই কোনো jump target বদলায়নি। শেষ দুই লাইন: একই bytecode, শুধু একটি opcode আলাদা, আর এখন ১,০০,০০০ গভীর “recursion” একটিমাত্র frame-এ চলে। TAIL_CALL-এর কাজ মাত্র এক লাইন: f[0], f[1] = 0, args, অর্থাৎ “শুরু থেকে আবার, নতুন argument নিয়ে”। এটাই একটি loop.

তুলনার জন্য সত্যিকারের Haat reference (v1, কোনো TCO নেই) একই function-এ:

// বাজারঘর: ১ থেকে n পর্যন্ত অর্ডার নম্বরের যোগফল
fn sum_to(n: Int, acc: Int) -> Int {
    if n == 0 { return acc; }
    return sum_to(n - 1, acc + n);
}
print(sum_to(999, 0));
print(sum_to(1000, 0));
~/haat $ python haat.py run sum.haat
499500
4:12: runtime error: stack overflow
~/haat $ python haat.py vm sum.haat
499500
4:12: runtime error: stack overflow

দুই back end একই কথা বলে (নকশা-সিদ্ধান্ত ২৬: ১০০০টির বেশি nested call হলে stack overflow), আর error-টি callee-র শুরুতে, কলাম ১২-তে (নকশা-সিদ্ধান্ত ২৪)। sum_to নিখুঁত tail recursion হলেও Haat v1 সেই সুযোগ নেয় না। কেন, আর বর্ধিত রূপে কীভাবে নেবে, তা অংশ ৯-এ।

সংজ্ঞা ৩২.১ — Proper tail call

একটি ভাষার বাস্তবায়ন properly tail-recursive, যদি tail position-এ থাকা যেকোনো সংখ্যক call (নিজেকে বা অন্য function-কে) চলমান অবস্থায় সীমিত পরিমাণ stack জায়গা নেয়। এটি একটি নিশ্চয়তা, প্রোগ্রামার যার ওপর নির্ভর করে loop লিখতে পারেন। TCO হলো একটি optimization, যা compiler চাইলে করে, না চাইলে করে না। ফারাকটি পরীক্ষায় প্রায়ই জিজ্ঞেস হয়।

৪ · সত্যিকারের Clang — -O0-তে call, -O2-তে jmp আর loop

এবার সত্যিকারের compiler. নিচের C file-এ তিনটি function: non-tail fact, tail-recursive fact_acc, আর অন্য file-এ থাকা settle-কে tail call করা checkout:

long fact(long n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);          // not a tail call: multiply after
}
long fact_acc(long n, long acc) {
    if (n <= 1) return acc;
    return fact_acc(n - 1, acc * n); // tail call: nothing left to do
}
long settle(long total);             // defined in another file
long checkout(long total) {
    return settle(total + 60);       // tail call to another function
}
~/haat $ zig cc -O0 -S --target=x86_64-linux-musl -g0 -fno-sanitize=undefined \
      -fno-asynchronous-unwind-tables -fomit-frame-pointer tc.c -o tc_O0.s
~/haat $ cat tc_O0.s        # trimmed: directives removed
fact_acc:
        subq    $24, %rsp
        movq    %rdi, 8(%rsp)
        movq    %rsi, (%rsp)
        cmpq    $1, 8(%rsp)
        jg      .LBB1_2
        movq    (%rsp), %rax
        movq    %rax, 16(%rsp)
        jmp     .LBB1_3
.LBB1_2:
        movq    8(%rsp), %rdi
        subq    $1, %rdi
        movq    (%rsp), %rsi
        imulq   8(%rsp), %rsi
        callq   fact_acc
        movq    %rax, 16(%rsp)
.LBB1_3:
        movq    16(%rsp), %rax
        addq    $24, %rsp
        retq
checkout:
        pushq   %rax
        movq    %rdi, (%rsp)
        movq    (%rsp), %rdi
        addq    $60, %rdi
        callq   settle
        popq    %rcx
        retq
~/haat $ zig cc -O2 -S --target=x86_64-linux-musl -g0 -fno-asynchronous-unwind-tables \
      -fomit-frame-pointer -fno-unroll-loops tc.c -o tc_O2.s
~/haat $ cat tc_O2.s        # trimmed
fact:
        movl    $1, %eax
        cmpq    $2, %rdi
        jl      .LBB0_2
.LBB0_1:
        imulq   %rdi, %rax
        cmpq    $2, %rdi
        leaq    -1(%rdi), %rdi
        ja      .LBB0_1
.LBB0_2:
        retq
fact_acc:
        movq    %rsi, %rax
        cmpq    $2, %rdi
        jl      .LBB1_2
.LBB1_1:
        imulq   %rdi, %rax
        cmpq    $2, %rdi
        leaq    -1(%rdi), %rdi
        ja      .LBB1_1
.LBB1_2:
        retq
checkout:
        addq    $60, %rdi
        jmp     settle

সত্যিকারের run: PyPI-র ziglang 0.17.1 (MIT licence), যার ভেতরে Clang 22.1.8; এখানে zig মানে python -m ziglang. Target x86-64 Linux. -O0-তে fact_acc নিজেকে callq দিয়ে ডাকে, প্রতিবার ২৪ byte-এর frame (subq $24, %rsp) আর ফেরার ঠিকানার ৮ byte নিয়ে। checkout-ও callq settle. -O2-তে fact_acc-এ কোনো call নেই: .LBB1_1 থেকে ja .LBB1_1 পর্যন্ত একটি loop, যেখানে %rax হলো acc আর %rdi হলো n. checkout মাত্র দুটি instruction: argument-এ 60 যোগ, তারপর jmp settle. আর অবাক করা ব্যাপার, non-tail fact-ও loop হয়ে গেছে! LLVM-এর tail recursion elimination pass গুণের মতো associative আর commutative কাজের বেলায় নিজেই একটি accumulator যোগ করতে পারে, ঠিক যে রূপান্তরটি আপনি অংশ ৬-এ হাতে করবেন। (-fno-unroll-loops শুধু listing ছোট রাখার জন্য।)

RISC-V-এ (--target=riscv64-linux-musl, একই -O2) checkout আরও স্পষ্ট:

checkout:
        addi    a0, a0, 60
        tail    settle

tail একটি pseudo-instruction: এটি ra (ফেরার ঠিকানার register) না ছুঁয়ে লাফ দেয়। সাধারণ call-এ call settle ফেরার ঠিকানা ra-তে লিখত; এখানে ra-তে এখনো checkout-এর ডাকা-পক্ষের ঠিকানা, তাই settle-এর ret সরাসরি সেখানে ফেরে। হার্ডওয়্যারের দিকটি আছে Computer Architecture কোর্সের পর্ব ৩০-এ। x86-64-এ একই ঘটনা ধাপে ধাপে:

1checkout:          # -O02  pushq %rax3  movq  %rdi, (%rsp)4  movq  (%rsp), %rdi5  addq  $60, %rdi6  callq settle7  popq  %rcx8  retq9checkout:          # -O210  addq  $60, %rdi11  jmp   settle
এই ধাপের পরে (stack, ওপরে শীর্ষ)
stack
%rdi
এখন চলছে
  1. ঢোকা। main checkout(936) ডেকেছে: callq stack-এ main-এ ফেরার ঠিকানা রেখেছে, argument %rdi-তে 936.
  2. Frame. -O0-তে pushq %rax ৮ byte জায়গা নেয় (stack ১৬ byte-এ সাজানো রাখতেও), আর total সেখানে লেখা হয়, তারপর আবার পড়া হয়: optimization ছাড়া প্রতিটি variable মেমরিতে।
  3. যোগ। %rdi = 936 + 60 = 996, settle-এর argument তৈরি।
  4. callq settle. নতুন ফেরার ঠিকানা (checkout-এ) stack-এ যায়। এখন stack-এ তিনটি ঘর: settle চলার সময় checkout-এর frame অকারণে বেঁচে আছে।
  5. ফেরা। settle-এর retq checkout-এ ফেরে; ফল %rax-এ। popq %rcx নিজের ৮ byte সরায় (মানটি ফেলে দেওয়া হয়)।
  6. retq. এবার main-এ ফেরা। Checkout-এর শেষ কাজ ছিল শুধু “settle-এর ফল ওপরে পাঠানো”, তার জন্য একটি পুরো frame আর একটি বাড়তি ফেরা খরচ হলো।
  7. -O2: ঢোকা আর যোগ। একই অবস্থা দিয়ে শুরু: stack-এ শুধু ret→main. কোনো frame খোলা হয় না, %rdi সরাসরি 996.
  8. jmp settle. Stack-এ কিছু যোগ হয়নি; stack-এর শীর্ষে এখনো main-এর ঠিকানা। তাই settle-এর retq সরাসরি main-এ ফিরবে, checkout যেন কখনো ছিলই না। সর্বোচ্চ ১টি ঘর, ৩টির বদলে। এটাই sibling call.

এবার এর ফল একটি সত্যিকারের program-এ। নিচের tail-recursive sum_to একই source থেকে দুবার compile হলো, এবার লেখকের Windows যন্ত্রের জন্য (zig-এর ডিফল্ট target x86_64-windows-gnu):

#include <stdio.h>
#include <stdlib.h>

long long sum_to(long long n, long long acc) {  // 1 + 2 + ... + n
    if (n == 0) return acc;
    return sum_to(n - 1, acc + n);              // tail call
}

int main(int argc, char **argv) {
    if (argc < 2) return 2;
    long long n = atoll(argv[1]);
    printf("sum_to(%lld) = %lld\n", n, sum_to(n, 0));
    return 0;
}
~/haat $ zig cc -O0 -fno-sanitize=undefined -Wall -Wextra deep.c -o deep0.exe
~/haat $ zig cc -O2 -Wall -Wextra deep.c -o deep2.exe
~/haat $ ./deep0.exe 100000
sum_to(100000) = 5000050000
~/haat $ ./deep0.exe 10000000
(no output; exit status 0xC00000FD = STATUS_STACK_OVERFLOW)
~/haat $ ./deep2.exe 10000000
sum_to(10000000) = 50000005000000

সত্যিকারের run, একই Clang 22.1.8; exit status লেখকের নিজের একটি ছোট Python script-এ subprocess দিয়ে পড়া। -O0-তে ১ কোটি গভীর recursion Windows-এর ডিফল্ট stack ফুরিয়ে ফেলে, আর program কিছু না ছেপেই stack overflow-এ মরে। -O2-তে একই কোড ঠিক উত্তর দেয়। -O2-এর assembly খুলে দেখা গেল Clang এক ধাপ এগিয়ে গেছে: tail recursion-কে loop বানানোর পরে loop-টিকেও একটি সূত্রে (n(n+1)/2-এর একটি রূপ) বদলে দিয়েছে, তাই এখানে loop-ও নেই। শিক্ষা দুটি। এক, C-তে stack বাঁচবে কি না তা নির্ভর করে optimization flag-এর ওপর, ভাষার ওপর নয়। দুই, “আমার যন্ত্রে চলে” মানে “debug build-এও চলবে” নয়।

C আর C++ standard TCO-র কোনো নিশ্চয়তা দেয় না, আর compiler কখনো কখনো সুযোগ পেয়েও নিতে পারে না। একটি পরিচিত বাধা: local variable-এর ঠিকানা বাইরে চলে যাওয়া। নিচের কোডে note(&seen) ঠিকানাটি কোথাও রেখে দিতে পারে, তাই walk-এর frame মরতে পারে না। সত্যিকারের -O2 output-এ তাই callq walk থেকে যায়:

void note(long *p);                  // defined elsewhere, may keep p
long walk(long n) {
    long seen = n;
    note(&seen);                     // address of a local escapes
    if (n == 0) return seen;
    return walk(n - 1);
}
~/haat $ zig cc -O2 -S ... esc.c     # trimmed
walk:   ...
        leaq    8(%rsp), %rdi
        callq   note
        ...
        callq   walk
        jmp     .LBB0_3

অন্য বাধাগুলো: callee-র stack-এ পাঠানো argument ডাকা-পক্ষের চেয়ে বেশি জায়গা চায় (calling convention-এ, পর্ব ৭১), C++-এ destructor বাকি, বা function-টি variadic. এই অনিশ্চয়তা দূর করতে Clang 13 (২০২১) [[clang::musttail]] attribute এনেছে: return-এর আগে লিখলে Clang হয় tail call বানাবে, নয়তো compile error দেবে। সত্যিকারের run-এ -O0-তেও তখন jmp fact_mt পাওয়া গেল, callq নয়। এটি একটি Clang extension, C standard-এর অংশ নয়।

৫ · ভাষাভেদে tail call — নিশ্চয়তা, optimization, না কিছুই না

পর্ব ০৯-এ (Functional programming) সংক্ষেপে দেখেছেন যে Scheme নিশ্চয়তা দেয়, CPython দেয় না, আর JavaScript-এর মানদণ্ডে থাকলেও বেশির ভাগ engine দেয় না। এখানে পুরো ছবিটি, প্রতিটি ভাষার নাম আর version-সহ:

ভাষা / বাস্তবায়নTail call-এর অবস্থা
Scheme (R5RS, R7RS)মানদণ্ডে বাধ্যতামূলক: বাস্তবায়নকে properly tail-recursive হতেই হবে; loop-ও এর ওপর দাঁড়িয়ে
OCaml, Standard ML, Haskell (GHC)বাস্তবে নির্ভরযোগ্য; ভাষার প্রচলিত রীতি এর ওপর নির্ভর করে (Haskell-এ lazy evaluation ছবিটি একটু জটিল করে)
C, C++ (GCC, Clang)শুধু optimization, সাধারণত -O2-তে; standard-এ নিশ্চয়তা নেই; Clang-এ musttail
WebAssembly 3.0 (২০২৫)আলাদা নির্দেশ return_call আর return_call_indirect: এগুলো দিলে stack বাড়বে না, এটাই নিয়ম
JavaScript (ES2015 থেকে)মানদণ্ডে strict mode-এ proper tail call আছে, কিন্তু কার্যত শুধু Safari-র JavaScriptCore চালু করেছে; V8 (Chrome, Node) আর SpiderMonkey (Firefox)-এ নেই
CPython 3.14নেই, ইচ্ছাকৃত; ডিফল্ট সীমা ১০০০ frame, পার হলে RecursionError
Java 21 (HotSpot JVM)JVM নিশ্চয়তা দেয় না; Kotlin-এর tailrec আর Scala-র @tailrec compile-এর সময় নিজেকে-ডাকা recursion-কে loop বানায় (অন্য function-এ নয়)
Rust (stable)নিশ্চয়তা নেই, LLVM optimization হিসেবে প্রায়ই হয়; become keyword সংরক্ষিত, স্পষ্ট tail call এখনো পরীক্ষামূলক
Haat v1নেই; ১০০০টি nested call-এর পরে stack overflow (নকশা-সিদ্ধান্ত ২৬)

WebAssembly-র উদাহরণটি সবচেয়ে পরিষ্কার, কারণ সেখানে tail call একটি আলাদা opcode, compiler-এর মর্জি নয়। নিচের JS block ৯১ byte-এর একটি Wasm module হাতে বানায়, যাতে একই sum_to দুবার: একটি শেষ হয় return_call (opcode 0x12) দিয়ে, অন্যটি সাধারণ call (0x10) দিয়ে। বাকি ২৩ byte-এর দেহ হুবহু এক। শেষে JavaScript-এর নিজের strict-mode tail call-ও পরীক্ষা করা হয়:

// sum_to(n, acc) twice in WebAssembly: "tail" ends with return_call (0x12),
// "plain" ends with an ordinary call (0x10). Same 23-byte body otherwise.
const hex = "0061736d01000000 0107016002 7e7e017e 03030200 00071002047461696c00 00 05706c61696e0001" +
  "0a3102 17 00 2000 50 0440 2001 0f 0b 2000 4201 7d 2001 2000 7c 1200 0b" +
  "17 00 2000 50 0440 2001 0f 0b 2000 4201 7d 2001 2000 7c 1001 0b";
const bytes = new Uint8Array(hex.replace(/ /g, "").match(/../g).map(h => parseInt(h, 16)));

function probe(label, f, n) {
  try { console.log(label, n, "->", String(f(BigInt(n), 0n))); }
  catch (e) { console.log(label, n, "->", e.name + ": " + e.message); }
}

WebAssembly.instantiate(bytes).then(({ instance }) => {
  const { tail, plain } = instance.exports;
  console.log("module size:", bytes.length, "bytes");
  probe("plain", plain, 1000);
  probe("tail ", tail, 1000);
  probe("plain", plain, 1000000);
  probe("tail ", tail, 1000000);
  probe("js   ", jsSum, 100000);   // JavaScript itself, strict mode
}).catch(e => console.log("this browser cannot load it:", e.message));

// ES2015 says a strict-mode call in tail position must not grow the stack
function jsSum(n, acc) { "use strict"; return n === 0n ? acc : jsSum(n - 1n, acc + n); }

আসল আউটপুট (পাতার যাচাই-ব্রাউজারে, আর লেখকের যন্ত্রে Node 24.15-এ হুবহু এক):

module size: 91 bytes
plain 1000 -> 500500
tail  1000 -> 500500
plain 1000000 -> RangeError: Maximum call stack size exceeded
tail  1000000 -> 500000500000
js    100000 -> RangeError: Maximum call stack size exceeded

Module-এর দেহ পড়তে পারেন: 20 00 = local.get 0 (n), 50 = i64.eqz, 04 40 … 0b = if … end, যার ভেতরে acc ফেরত (0f = return); তারপর n − 1 (42 01 7d) আর acc + n (7c), আর শেষে 12 00 বা 10 01. ছোট n-এ দুটি একই উত্তর দেয়। ১০ লাখে সাধারণ call-এর stack ফুরিয়ে যায়, return_call ঠিক চলে, কারণ Wasm-এর নিয়মেই এটি নতুন frame রাখে না। শেষ লাইনটি engine-ভেদে আলাদা: Chrome, Firefox আর Node-এ RangeError, কারণ তারা JavaScript-এর proper tail call চালু করেনি; Safari-তে এই লাইনটি নাকি একটি সংখ্যা দেখাবে (এখানে চালিয়ে দেখা হয়নি)। একই মানদণ্ড, আলাদা আচরণ: AI বা কোনো blog “JavaScript-এ TCO আছে” বললে ঠিক এখানেই যাচাই করবেন।

এই তুলনা থেকে একটি নকশার শিক্ষা: tail call-এর নিশ্চয়তা দেওয়া সহজ, পরে যোগ করা কঠিন। Scheme আর Wasm শুরু থেকেই নিয়মটি রেখেছে, তাই সব বাস্তবায়ন সেভাবেই গড়া। JavaScript-এ মানদণ্ড পরে এল, ততদিনে engine-গুলোর debugger, stack trace আর নিরাপত্তা-ব্যবস্থা প্রতিটি frame দেখা যাবে ধরে নিয়ে তৈরি। ভাবনার প্রশ্ন ৩-এ এর ইতিহাস।

৬ · Accumulator রূপান্তর — non-tail থেকে tail recursion

অংশ ১-এর fact থেকে fact_acc কীভাবে এল? মূল কৌশল: “ফেরার পথে যে কাজ হতো, তা যাওয়ার পথে করে একটি বাড়তি parameter-এ জমিয়ে রাখা”। সেই parameter-ই accumulator. রেসিপিটি চার ধাপে:

  1. অপেক্ষমাণ কাজ খুঁজুন। return n * fact(n - 1);-এ অপেক্ষমাণ কাজ “n দিয়ে গুণ”।
  2. একটি accumulator যোগ করুন, যার অর্থ “এ পর্যন্ত জমা হওয়া অপেক্ষমাণ কাজের ফল”: fact_acc(n, acc), অর্থাৎ acc × n!.
  3. Recursive call-এ কাজটি আগেই করুন: fact_acc(n - 1, acc * n).
  4. Base case-এ accumulator ফেরত দিন, আর শুরুতে কাজের identity মান দিন: গুণে 1, যোগে 0. তাই fact(n) = fact_acc(n, 1).
শর্ত — কখন রূপান্তরটি নিরাপদ

ধাপ ৩-এ গুণের ক্রম বদলে গেছে: fact হিসাব করে 4 × (3 × (2 × 1)), আর fact_acc হিসাব করে ((1 × 4) × 3) × 2. দুটি সমান, কারণ গুণ associative আর এখানে commutative-ও। বিয়োগ, ভাগ বা string জোড়ার মতো কাজে ক্রম বদলালে উত্তর বদলায়। Haat-এর Int ৬৪-bit-এ wrap করে (নকশা-সিদ্ধান্ত ১৩), কিন্তু modular গুণও associative আর commutative, তাই wrap হলেও দুটি function একই উত্তর দেয়: fact(21) আর fact_acc(21, 1) একই wrap-করা সংখ্যা। অনুশীলন ২-এ এটি প্রমাণ করবেন।

সব recursion এত সহজে বদলায় না। Fibonacci-র fib(n - 1) + fib(n - 2)-এ দুটি recursive call; দুটি accumulator (পরপর দুটি Fibonacci সংখ্যা) রেখে একটি tail-recursive রূপ পাওয়া যায়, কিন্তু সেটি আসলে algorithm-ই বদলে দেয় (exponential থেকে linear). গাছ ঘোরার মতো সমস্যায়, যেখানে বাম আর ডান দুই দিকে যেতে হয়, একটি সংখ্যা জমিয়ে রাখা যথেষ্ট নয়: “বাকি কাজের তালিকা” রাখতে হয়। তখন accumulator হয়ে যায় একটি হাতে-বানানো stack, বা পরের দুই অংশের trampoline আর continuation. অনুশীলন ৪-এ এমন একটি ভুল দেখবেন।

৭ · Trampoline — ভাষা TCO না দিলেও stack ছাড়া

CPython TCO করে না, তাই Python-এ tail-recursive লেখা নিজে থেকে কিছু বাঁচায় না। সমাধান হলো trampoline: function পরের call নিজে না করে একটি parameter-হীন function (thunk) ফেরত দেয়, যার মানে “এরপর এটিকে ডাকতে হবে”। একটি ছোট loop সেই thunk ডাকে, যা আবার একটি thunk দেয়, যতক্ষণ না একটি সাধারণ মান আসে। প্রতিবার function সম্পূর্ণ ফিরে আসে, তাই stack কখনো জমে না; ট্রাম্পোলিনে লাফানোর মতো, প্রতিবার নিচে নেমে আবার ওঠা।

import sys
print("recursion limit:", sys.getrecursionlimit())

def sum_rec(n):                      # not a tail call: "n +" waits for the answer
    return 0 if n == 0 else n + sum_rec(n - 1)

def sum_acc(n, acc=0):               # tail call, but CPython keeps every frame
    return acc if n == 0 else sum_acc(n - 1, acc + n)

def sum_tramp(n, acc=0):             # trampoline style: return the next step
    return acc if n == 0 else (lambda: sum_tramp(n - 1, acc + n))

def trampoline(result):
    bounces = 0
    while callable(result):          # a function means "call me next"
        result = result()
        bounces += 1
    return result, bounces

for f in (sum_rec, sum_acc):
    for n in (900, 5000):
        try:
            print(f.__name__, n, "->", f(n))
        except RecursionError as e:
            print(f.__name__, n, "-> RecursionError:", e)
print("sum_tramp 5000 ->", trampoline(sum_tramp(5000)))
print("sum_tramp 100000 ->", trampoline(sum_tramp(100_000)))

def is_even(n): return True if n == 0 else (lambda: is_odd(n - 1))
def is_odd(n):  return False if n == 0 else (lambda: is_even(n - 1))
print("is_even(100001) ->", trampoline(is_even(100_001)))

আসল আউটপুট (Pyodide-এ; লেখকের যন্ত্রে CPython 3.14.4-এ হুবহু এক):

recursion limit: 1000
sum_rec 900 -> 405450
sum_rec 5000 -> RecursionError: maximum recursion depth exceeded
sum_acc 900 -> 405450
sum_acc 5000 -> RecursionError: maximum recursion depth exceeded
sum_tramp 5000 -> (12502500, 5000)
sum_tramp 100000 -> (5000050000, 100000)
is_even(100001) -> (False, 100001)

প্রথম পাঁচ লাইন: CPython-এর recursion limit ১০০০, তাই ৯০০ চলে আর ৫০০০ আটকায়, tail call হোক বা না হোক। sum_acc-এর accumulator CPython-এ কিছুই বাঁচায়নি। পরের দুই লাইন: trampoline-এ ৫০০০ আর ১,০০,০০০ দুটিই চলে, আর bounce-এর সংখ্যা ঠিক n: প্রতিটি পুরোনো recursive call এখন loop-এর একটি ঘোরা। শেষ লাইন: mutual recursion-এও কাজ করে, যেখানে loop-এ রূপান্তর এত সহজ নয়: is_even আর is_odd একে অপরের thunk ফেরত দেয়, আর একই trampoline দুটিকেই চালায়। 100001 বিজোড়, তাই False.

1def sum_tramp(n, acc=0):2    return acc if n == 0 else (lambda: sum_tramp(n - 1, acc + n))3def trampoline(result):4    bounces = 05    while callable(result):6        result = result()7        bounces += 18    return result, bounces9trampoline(sum_tramp(3))
এই ধাপের পরে
result
bounces
সর্বোচ্চ Python frame
  1. প্রথম ডাক। sum_tramp(3) নিজেকে ডাকে না; সে একটি thunk ফেরত দেয়, যার ভেতরে “এরপর sum_tramp(2, 3)” (acc = 0 + 3). Trampoline শুরু করে bounces = 0 দিয়ে।
  2. বাউন্স ১. result() thunk ডাকে, যা sum_tramp(2, 3) চালায়, আর সেটি নতুন thunk ফেরত দিয়ে সঙ্গে সঙ্গে শেষ হয়: ⟨sum_tramp(1, 5)⟩. চলার মুহূর্তে stack-এ মাত্র তিনটি frame: trampoline, lambda, sum_tramp.
  3. বাউন্স ২. acc = 5 + 1 = 6, thunk ⟨sum_tramp(0, 6)⟩. Stack-এর উচ্চতা আবার সেই তিন; n যত বড়ই হোক, বাড়ে না।
  4. বাউন্স ৩. sum_tramp(0, 6)-এ n = 0, তাই এবার thunk নয়, সাধারণ মান 6 ফেরত আসে। bounces = 3.
  5. শেষ। callable(6) মিথ্যা, loop থামে, ফল (6, 3). তিনটি recursive call তিনটি loop-ঘোরা হয়ে গেছে; আর প্রতিটি “call” আসলে একটি heap-এ বানানো ছোট closure. (Frame-এর সংখ্যা লেখকের যন্ত্রে sys._getframe দিয়ে গুনে মেলানো।)

Trampoline-এর দাম আছে: প্রতিটি ধাপে একটি closure তৈরি আর একটি বাড়তি call, তাই সাধারণ loop-এর চেয়ে ধীর। আর ভুল ফাঁদ একটি: যে function সত্যিই একটি function মান ফেরত দিতে চায়, trampoline তাকে “পরের ধাপ” ভেবে ডেকে ফেলবে; এজন্য বাস্তব library-গুলো thunk-কে একটি আলাদা class-এ মুড়ে রাখে। Clojure-এর মতো JVM-ভাষা (JVM TCO দেয় না) ঠিক এই কারণে standard library-তে trampoline function রাখে, আর নিজেকে-ডাকার জন্য recur নামে একটি বিশেষ রূপ, যা compiler loop বানায়।

৮ · Continuation-passing style — প্রতিটি call-কে tail call বানানো

Accumulator-এ একটি সংখ্যা জমিয়ে রাখা যায়, কিন্তু অপেক্ষমাণ কাজ যদি জটিল হয়? পর্ব ৩১-এ (Generator, coroutine আর async/await) দেখেছেন continuation মানে “বাকি হিসাব”, আর continuation-passing style (CPS)-এ function ফল return না করে continuation-কে ফল দিয়ে ডাকে। এখানে এর tail call-এর দিকটি: CPS-এ লেখা program-এ প্রতিটি call tail call. অপেক্ষমাণ কাজ “n দিয়ে গুণ, তারপর বাকিটা” নিজেই একটি নতুন continuation হয়ে যায়: lambda r: k(n * r). যে তথ্য আগে stack frame-এ থাকত, এখন থাকে heap-এ রাখা closure-এর শৃঙ্খলে।

1def fact_cps(n, k):2    if n <= 1:3        return k(1)4    return fact_cps(n - 1, lambda r: k(n * r))5fact_cps(3, lambda r: r)    # k0
এই ধাপের পরে
এখন চলছে
continuation
  1. শুরু। k0 হলো identity: “উত্তর পেলে সেটিই ফেরত”।
  2. n = 3. “3 দিয়ে গুণ করে ফল k0-তে” কাজটি stack-এ না রেখে নতুন continuation k1-এ মোড়া হলো, আর fact_cps(2, k1) একটি tail call.
  3. n = 2. k2 = “2 দিয়ে গুণ করে ফল k1-এ”। শৃঙ্খল এখন k2 → k1 → k0; এটাই আগের stack, শুধু heap-এ।
  4. Base case. n = 1, তাই k(1), অর্থাৎ k2(1): 2 × 1 = 2 যায় k1-এ। লক্ষ করুন, এটিও একটি tail call.
  5. শৃঙ্খল খোলা। k1(2): 3 × 2 = 6 যায় k0-এ।
  6. উত্তর। k0(6) = 6. সব গুণ হয়েছে continuation-এর ভেতরে, ঠিক যেভাবে fact-এর গুণ হতো ফেরার পথে।

কিন্তু Python TCO করে না, তাই CPS-এ লেখা কোডও Python-এর stack খায়; প্রতিটি tail call তো সাধারণ call-ই রয়ে গেল। সমাধান: CPS আর trampoline একসঙ্গে। প্রতিটি ধাপ, এমনকি continuation ডাকাও, একটি thunk ফেরত দেয়:

import math

def fact(n):                            # direct style: "n *" waits for the answer
    return 1 if n <= 1 else n * fact(n - 1)

def fact_cps(n, k):                     # k = "what to do with my answer"
    if n <= 1:
        return k(1)
    return fact_cps(n - 1, lambda r: k(n * r))      # a tail call
print("direct:", fact(10), " cps:", fact_cps(10, lambda r: r))

def fact_t(n, k):                       # CPS + trampoline: every step is a thunk
    if n <= 1:
        return lambda: k(1)
    return lambda: fact_t(n - 1, lambda r: lambda: k(n * r))

def run(t):
    steps = 0
    while callable(t):
        t, steps = t(), steps + 1
    return t, steps
print("fact_t(10):", run(fact_t(10, lambda r: r)))

v, steps = run(fact_t(3000, lambda r: r))
print("fact_t(3000): correct?", v == math.factorial(3000), "| steps:", steps,
      "| bits:", v.bit_length())
for name, f in (("direct", fact), ("cps", lambda n: fact_cps(n, lambda r: r))):
    try:
        f(3000)
    except RecursionError:
        print(name, "fact(3000): RecursionError")

আসল আউটপুট (Pyodide-এ; লেখকের যন্ত্রে CPython 3.14.4-এ হুবহু এক):

direct: 3628800  cps: 3628800
fact_t(10): (3628800, 19)
fact_t(3000): correct? True | steps: 5999 | bits: 30332
direct fact(3000): RecursionError
cps fact(3000): RecursionError

প্রথম লাইন: CPS-এ অর্থ বদলায়নি, 10! = 3628800. দ্বিতীয় আর তৃতীয় লাইন: trampoline-সহ CPS ৩০০০-এও ঠিক উত্তর দেয় (Python-এর math.factorial-এর সঙ্গে মিলিয়ে)। ধাপ 2n − 1: n − 1টি যাওয়ার পথে, একটি base case, আর n − 1টি continuation খোলার পথে; 10-এ 19, 3000-এ 5999. সংখ্যাটি ৩০৩৩২ bit লম্বা, তাই সংখ্যার বদলে শুধু bit গোনা হয়েছে। শেষ দুই লাইন: সাধারণ fact আর trampoline-ছাড়া CPS দুটিই আটকায়। শিক্ষা: CPS stack-এর কাজ heap-এ সরায়, আর trampoline (বা সত্যিকারের TCO) নিশ্চিত করে যে সেই tail call-গুলো সত্যিই stack খাবে না।

Compiler-এর জগতে CPS একটি পুরোনো আর শক্তিশালী intermediate representation. Guy Steele-এর Rabbit compiler (১৯৭৮, Scheme-এর জন্য) program-কে CPS-এ বদলে নিত, আর Andrew Appel-এর বই Compiling with Continuations (১৯৯২) Standard ML of New Jersey compiler-এর CPS-ভিত্তিক নকশা বর্ণনা করে। CPS-এ “ফেরা” বলে কিছু থাকে না, শুধু jump with arguments, তাই call stack, exception আর generator একই কাঠামোয় প্রকাশ করা যায়। আরেক দিক থেকে, continuation-গুলোকে closure না রেখে data structure-এ বদলে নিলে (পর্ব ১৭-এর defunctionalization) পাওয়া যায় হাতে-বানানো একটি stack: অর্থাৎ recursion থেকে loop + explicit stack-এ যাওয়ার একটি যান্ত্রিক পথ।

৯ · Haat-এ tail call — v1-এর সীমা আর একটি বর্ধিত রূপ

Haat v1 কেন TCO করে না? Spec এ বিষয়ে চুপ, আর reference সবচেয়ে সরল পথ নিয়েছে: প্রতিটি CALL একটি frame, সীমা ১০০০, দুই back end-এ হুবহু এক (নকশা-সিদ্ধান্ত ২৬)। এতে error-এর অবস্থান আর গভীরতা সহজে বোঝা যায়, আর tree-walking interpreter (যা Python-এর নিজের recursion দিয়ে চলে) আর VM একই আচরণ দেয়। Haat-এর বর্ধিত রূপে tail call যোগ করতে চাইলে compiler আর VM-এ দুটি ছোট পরিবর্তন: অংশ ৩-এর peephole pass (compiler.py-র function_body-এর শেষে) আর VM-এ TAIL_CALL, যা frames[-1]-কে নতুন Frame দিয়ে বদলে দেয়। লেখকের lab-এ reference-এর একটি কপিতে ঠিক এটাই করা হলো (মূল reference অপরিবর্তিত); reference-এর ১৩টি example-এর output আগের মতোই হুবহু মিলেছে। তারপর:

fn sum_to(n: Int, acc: Int) -> Int {
    if n == 0 { return acc; }
    return sum_to(n - 1, acc + n);
}
fn sum_rec(n: Int) -> Int {
    if n == 0 { return 0; }
    return n + sum_rec(n - 1);
}
print(sum_to(1000, 0));
print(sum_to(100000, 0));
print(sum_rec(1000));
~/haat-tc $ python haat.py vm sum2.haat       # বর্ধিত রূপ, TAIL_CALL-সহ
500500
5000050000
7:16: runtime error: stack overflow
~/haat-tc $ python haat.py dis sum2.haat      # sum_to-এর শেষ অংশ
  12  ADD
  13  TAIL_CALL      2
  14  RETURN

Tail call-এ এখন ১ লাখ গভীরতাও চলে, কিন্তু n + sum_rec(n - 1) tail call নয়, তাই সেটি আগের মতোই আটকায়: এটাই ঠিক আচরণ। নকশার তিনটি প্রশ্ন বাকি থাকে, আর তিনটিই বাস্তব ভাষাগুলোকে ভাবিয়েছে:

  • দুই back end কি এক থাকবে? Tree-walking interpreter-এও একই নিশ্চয়তা দিতে হলে তার call-কে একটি loop বানাতে হবে, যা tail call পেলে frame না বাড়িয়ে পরের function-এ যায়; আসলে interpreter-এর ভেতরে একটি trampoline. নইলে run আর vm আলাদা ফল দেবে, যা reference-এর “দুই back end এক” নীতির বিরুদ্ধে।
  • সব tail call কি ধরা পড়ে? না। return n > 0 && all_paid(n - 1); T-And অনুযায়ী tail call, কিন্তু && jump দিয়ে compile হয় বলে CALL-এর পরে RETURN নয়, JUMP. বর্ধিত রূপের সত্যিকারের run-এ all_paid(2000) তাই 3:21: runtime error: stack overflow দিল। পূর্ণ সমাধানে peephole-কে JUMP অনুসরণ করে দেখতে হবে সেটি একটি RETURN-এ যায় কি না, অথবা AST-তে T-Ret/T-And নিয়ম দিয়ে tail call চিহ্নিত করতে হবে।
  • Error message কী বলবে? TCO মুছে ফেলা frame আর কোনো stack trace-এ দেখা যাবে না। Haat-এর এক লাইনের error-এ এটি সমস্যা নয়, কিন্তু একটি পূর্ণ traceback দেখানো ভাষায় এটিই Python-এর আপত্তির মূল কারণ।

আরও গভীরে: William Clinger ১৯৯৮ সালের “Proper tail recursion and space efficiency” প্রবন্ধে “properly tail-recursive” কথাটিকে একটি space-complexity শ্রেণি হিসেবে গাণিতিকভাবে সংজ্ঞায়িত করেন, যাতে কোনো বাস্তবায়ন নিয়ম মানে কি না তা প্রমাণ করা যায়; Scheme-এর পরের মানদণ্ডগুলো এই ধারণা ব্যবহার করে বলে জানা যায়। C-তে compile করা Scheme বাস্তবায়নের জন্য Henry Baker-এর “Cheney on the M.T.A.” (১৯৯৫) কৌশলে C-র stack-কে বাড়তে দেওয়া হয়, আর ভরে গেলে জীবিত data heap-এ সরিয়ে longjmp দিয়ে stack খালি করা হয়; Chicken Scheme এই পথে চলে। আর CPython 3.14-এর নতুন ঐচ্ছিক interpreter (Clang 19 বা নতুন, x86-64 ও AArch64) প্রতিটি opcode-কে একটি ছোট C function বানিয়ে পরেরটিকে tail call করে; Python-এর ডকুমেন্টেশন নিজেই সতর্ক করে যে এটিকে Python function-এর tail call optimization ভাবা চলবে না, যা CPython-এ এখনো নেই।

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

  • Tail call কী? যে call-এর পরে ডাকা-পক্ষের আর কোনো কাজ নেই, শুধু ফলটি ফেরত দেওয়া; return f(x) হ্যাঁ, return 1 + f(x) না।
  • TCO কী করে? নতুন frame না খুলে বর্তমান frame-এ argument বসিয়ে jump; tail recursion তখন loop, stack O(1).
  • Python-এ গভীর recursion কীভাবে চালাবেন? Loop-এ লিখে, explicit stack দিয়ে, বা trampoline দিয়ে; sys.setrecursionlimit বাড়ানো ঝুঁকিপূর্ণ।
  • Non-tail recursion-কে tail বানানোর উপায়? Accumulator (associative কাজে) বা CPS (সাধারণভাবে)।
  • Proper tail call আর TCO-র পার্থক্য? প্রথমটি ভাষার নিশ্চয়তা (Scheme, Wasm return_call), দ্বিতীয়টি compiler-এর ঐচ্ছিক optimization (C -O2).

১০ · AI-এর যুগে recursion আর tail call

Tail call নিয়ে AI assistant-এর ভুলগুলো প্রায়ই “আত্মবিশ্বাসী সাধারণীকরণ”: এক ভাষার আচরণ সব ভাষায় চাপানো, বা “tail-recursive লিখেছি, তাই নিরাপদ” ধরে নেওয়া। এই বিষয়ে বারবার দেখা ভুল আর ধরার উপায়:

AI-এর ভুলকীভাবে ধরবেন
“Python/JavaScript/Java tail call optimize করে” বলা১ লাখ গভীর tail recursion চালিয়ে দেখা; ভাষা আর engine-এর নাম ধরে ডকুমেন্টেশন খোঁজা
return 1 + f(n - 1) বা return f(f(n))-এর ভেতরেরটিকে tail call বলাT-Ret/T-Call নিয়মে অবস্থান মিলিয়ে দেখা: call-এর পরে কিছু বাকি কি না
“C compiler সবসময় tail call বাদ দেয়” বলা-O0 আর -O2 দুটিতেই -S output দেখা; debug build-এ গভীর ইনপুট চালানো
Accumulator রূপান্তরে বিয়োগ বা string-জোড়ার ক্রম উল্টে দেওয়াপুরোনো আর নতুন function একই random ইনপুটে চালিয়ে differential test
নেই এমন flag বা attribute বানানো (যেমন GCC-তে কোনো “-ftail-call” বলে নিশ্চয়তার দাবি)Compiler-এর নিজের ডকুমেন্টেশনে খোঁজা; flag দিয়ে compile করে দেখা
Trampoline-এ function-মান ফেরত দেওয়া function ভেঙে যাওয়া খেয়াল না করাযে function একটি function ফেরত দেয়, তা দিয়ে আলাদা test

AI-কে ভালোভাবে কাজে লাগানোর উপায়: ভাষা, version আর বাস্তবায়ন (CPython, V8, Clang -O2) বলে দেওয়া, আর প্রতিটি দাবির সঙ্গে যাচাইয়ের পরীক্ষা চাওয়া।

আমি recursion আর tail call শিখছি। নিচের function-টি [Python 3.14 / JavaScript (Chrome) / C, Clang -O2 / Haat] -এর। তুমি: ১. প্রতিটি recursive call tail position-এ আছে কি না বলো, আর কেন (call-এর পরে কোন কাজ বাকি)। ২. এই ভাষা ও বাস্তবায়ন tail call-এর নিশ্চয়তা দেয়, optimization হিসেবে করে, নাকি একেবারেই করে না, তা সূত্রসহ লেখো; না জানলে স্পষ্ট বলো। ৩. Function-টি accumulator বা trampoline দিয়ে বদলে লেখো, আর বলো রূপান্তরে কোন কাজের ক্রম বদলেছে ও কেন তা নিরাপদ। ৪. পুরোনো আর নতুন রূপ মেলানোর জন্য একটি differential test আর একটি গভীর ইনপুটের test দাও। ৫. C হলে কোন compile command দিয়ে assembly দেখে call বনাম jmp যাচাই করব, তা বলো। [এখানে function]

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

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

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

প্র ০১“Procedure call দামি, তাই loop লিখুন” — Guy Steele ১৯৭০-এর দশকে এই প্রচলিত ধারণা কেন ভুল বললেন, আর Scheme কেন tail call-কে মানদণ্ডে বেঁধে দিল?

১৯৭০-এর দশকে প্রোগ্রামারদের মধ্যে একটি দৃঢ় বিশ্বাস ছিল: procedure call ধীর, তাই গতির দরকার হলে বড় function আর goto-ওয়ালা loop লিখুন। Gerald Sussman আর Guy Steele ১৯৭৫ সালে MIT-তে Scheme তৈরি করেন, আর Steele ১৯৭৭ সালের একটি MIT AI Memo-তে, যার নামগুলোর একটি “Lambda: The Ultimate GOTO”, যুক্তি দেন যে সমস্যা call-এ নয়, call-এর বাস্তবায়নে। তাঁর মূল পর্যবেক্ষণ এই পর্বের কেন্দ্রে: tail position-এর call আসলে argument সহ একটি goto; তার জন্য stack-এ কিছু রাখার দরকার নেই। যে compiler প্রতিটি call-কে ফেরার ঠিকানা রেখে বাস্তবায়ন করে, সে অকারণে খরচ বাড়ায়।

এ থেকে Scheme একটি সাহসী সিদ্ধান্ত নেয়: ভাষায় আলাদা loop-এর দরকারই নেই। do loop-এর মতো রূপগুলো আসলে recursive procedure-এর ওপর বানানো, আর মানদণ্ড (Revised Report, যেমন R5RS ও R7RS) বলে যে বাস্তবায়নকে properly tail-recursive হতে হবে। এটি optimization নয়, চুক্তি: একজন Scheme প্রোগ্রামার জানেন যে tail-recursive loop লক্ষ কোটি বার ঘুরলেও memory বাড়বে না, যেকোনো বাস্তবায়নে।

এই নিশ্চয়তা কেন জরুরি, তা অংশ ৪-এর C run-এ দেখেছেন: একই কোড -O2-তে চলে, -O0-তে মরে। যে ভাষায় TCO শুধু optimization, সেখানে কেউ সেই আচরণের ওপর program-এর শুদ্ধতা দাঁড় করাতে পারে না। Scheme-এর পছন্দ তাই শুধু গতির নয়, শুদ্ধতার: mutual recursion দিয়ে লেখা state machine (প্রতিটি অবস্থা একটি function, যা পরের অবস্থাকে tail call করে) নির্ভয়ে চলতে পারে।

পরের ইতিহাসও Steele-এর পক্ষে গেছে। CPS-ভিত্তিক compiler (Rabbit, SML/NJ), আধুনিক register-ভিত্তিক calling convention, আর WebAssembly-র return_call সবই দেখায় যে call আর jump-এর পার্থক্য মূলত বাস্তবায়নের পছন্দ।

মূল উপলব্ধি: কোনো ভাষা-বৈশিষ্ট্য “দামি” কি না, তা প্রায়ই বাস্তবায়নের প্রশ্ন, ভাষার নয়। আর একটি optimization যখন নিশ্চয়তা হয়, তখন সেটি প্রোগ্রামিং-এর রীতিই বদলে দেয়।

প্র ০২CPython 3.14-এর interpreter নিজেই tail call দিয়ে লেখা, অথচ Python function-এ TCO নেই — এই আপাত-বিরোধের ব্যাখ্যা কী?

পর্ব ০৯-এ Guido van Rossum-এর ২০০৯ সালের সিদ্ধান্তের কারণগুলো দেখেছেন: traceback-এ সব frame দেখা যাওয়া, আর কোন নাম চলার সময় কোন function-কে বোঝায় তা আগে থেকে নিশ্চিত না হওয়া। CPython 3.14-এ একটি নতুন মোড় এসেছে, যা প্রথম দেখায় উল্টো মনে হয়। “What's New in Python 3.14” জানায়, একটি নতুন ধরনের interpreter যোগ হয়েছে, যা একটি বিশাল C switch-এর বদলে প্রতিটি Python opcode-কে একটি ছোট C function বানায়, আর এক opcode-এর function পরের opcode-এর function-কে tail call করে। এটি এখন ঐচ্ছিক (build-এর সময় --with-tail-call-interp), Clang 19 বা নতুন, x86-64 ও AArch64-এ চলে।

বিরোধ নেই, কারণ দুটি আলাদা স্তর। Interpreter-এর C কোডে tail call মানে C-র frame না বাড়িয়ে পরের handler-এ যাওয়া; এতে compiler প্রতিটি handler আলাদাভাবে ভালো optimize করতে পারে (register বরাদ্দ, branch prediction), যা একটি বিশাল function-এ কঠিন। এটি সম্ভব হয়েছে Clang-এর musttail (অংশ ৪) আর একটি বিশেষ calling convention-এর কারণে, যা নিশ্চিত করে প্রতিটি handler-এর call সত্যিই jump হবে। কৌশলটি নতুন নয়: Josh Haberman ২০২১ সালে protobuf parser-এ musttail দিয়ে একই ধাঁচের নকশার কথা লেখেন, আর আরও কিছু interpreter এই পথ নিয়েছে বলে জানা যায়।

Python program-এর স্তরে কিছুই বদলায়নি: def f(n): return f(n - 1) এখনো প্রতিবার একটি Python frame নেয়, আর ১০০০-এর সীমায় RecursionError. Python-এর ডকুমেন্টেশন নিজেই সতর্ক করে যে নতুন interpreter-কে Python function-এর tail call optimization ভাবা চলবে না, যা CPython-এ এখনো নেই।

এখান থেকে একটি বড় শিক্ষা: একটি ভাষার semantics আর তার বাস্তবায়নের কৌশল আলাদা। বাস্তবায়নকারীরা যে কৌশল নিজের কাজে ব্যবহার করেন, তা ব্যবহারকারীকে দেওয়া হবে কি না, সেটি ভাষার নকশার প্রশ্ন, যার উত্তর debugging, সামঞ্জস্য আর অভ্যাসের ওপর নির্ভর করে।

মূল উপলব্ধি: “X ভাষায় tail call আছে কি না” জিজ্ঞেস করার সময় স্তর স্পষ্ট করুন: ভাষার semantics, নাকি তার বাস্তবায়নের ভেতরের কৌশল।

প্র ০৩JavaScript-এর মানদণ্ডে proper tail call আছে, অথচ বেশির ভাগ engine তা চালু করেনি — একটি মানদণ্ড কীভাবে কাগজে থেকে যায়?

ECMAScript 2015 (ES6) strict mode-এ proper tail call যোগ করে: tail position-এর call stack বাড়াবে না। মানদণ্ড চূড়ান্ত হওয়ার পরে Apple-এর JavaScriptCore (Safari) এটি বাস্তবায়ন করে, প্রায় ২০১৬ সালে। V8 দলও একটি বাস্তবায়ন নিয়ে কাজ করেছিল, কিন্তু পরে তা সরিয়ে নেয় বলে জানা যায়; Firefox-এর SpiderMonkey চালু করেনি। ফলে অংশ ৫-এর run-এ Chrome ও Node RangeError দেয়।

আপত্তিগুলো মূলত তিনটি। এক, debugging: developer tool-এর stack trace থেকে frame হারিয়ে যায়, আর error-এর পথ খোঁজা কঠিন হয়। দুই, অদৃশ্যতা: কোনো call tail position-এ কি না তা কোড দেখে সহজে বোঝা যায় না, তাই একটি ছোট পরিবর্তন (যেমন return f(x)-কে return f(x) + 0 লেখা) চুপচাপ stack-এর আচরণ বদলে দেয়। তিন, বিদ্যমান ব্যবস্থার সঙ্গে সংঘাত: কিছু নিরাপত্তা-যাচাই আর telemetry stack-এ সব frame থাকা ধরে নিয়েছিল। এই আপত্তি থেকে কয়েকটি engine দল একটি বিকল্প প্রস্তাব করে, “syntactic tail calls”, যেখানে প্রোগ্রামার স্পষ্ট চিহ্ন দিয়ে tail call চাইবেন; প্রস্তাবটি এগোয়নি বলে জানা যায়।

এর মধ্যে WebAssembly অন্য পথ নিয়েছে। সেখানে tail call আলাদা নির্দেশ, return_call: compiler স্পষ্টভাবে বলে দেয় কোনটি tail call, আর সেখানে নিশ্চয়তা আছে। এটি ঠিক “syntactic” প্রস্তাবের মূল ধারণা: অদৃশ্য নিয়মের বদলে দৃশ্যমান চিহ্ন। Rust-এর সংরক্ষিত become keyword আর Clang-এর musttail একই দর্শন অনুসরণ করে।

মানদণ্ড শুধু লেখা থাকলেই বাস্তব হয় না; বাস্তবায়নকারীদের সম্মতি, খরচ আর পুরোনো ব্যবস্থার সঙ্গে মিল লাগে। একটি ভাষা-বৈশিষ্ট্য যত দেরিতে আসে, তার জন্য তত বেশি বিদ্যমান tool বদলাতে হয়।

মূল উপলব্ধি: tail call-এর নিশ্চয়তা দেওয়ার দুই পথ: সব tail position-এ চুপচাপ (Scheme), নাকি স্পষ্ট চিহ্ন দিয়ে (Wasm, musttail, become). দ্বিতীয় পথ debugging আর পাঠযোগ্যতার আপত্তির একটি ভারসাম্যপূর্ণ উত্তর।

প্র ০৪Recursion, explicit stack, trampoline আর CPS — গভীর ডেটা (যেমন বড় JSON বা গাছ) প্রক্রিয়ায় বাস্তব প্রকৌশলে কোনটি কখন বেছে নেবেন?

বাস্তবে গভীর recursion-এর ঝুঁকি শুধু তাত্ত্বিক নয়। একটি parser বা serializer যদি nested ডেটা recursion দিয়ে পড়ে, তাহলে অস্বাভাবিক গভীর ইনপুট (হাজার স্তরের বন্ধনী) stack ফুরিয়ে program থামিয়ে দিতে পারে; বাইরের ইনপুট নেওয়া সার্ভারে এটি একটি পরিচিত denial-of-service ঝুঁকি। তাই অনেক library গভীরতার একটি সীমা বসায়, বা recursion বাদ দিয়ে explicit stack ব্যবহার করে। এখানে চারটি পথের তুলনা।

সাধারণ recursion পড়তে সবচেয়ে সহজ, আর গভীরতা যদি স্বাভাবিকভাবে সীমিত হয় (যেমন balanced গাছ, যার উচ্চতা log n), তাহলে এটিই সেরা। কিন্তু গভীরতা ইনপুটের ওপর নির্ভর করলে একটি স্পষ্ট সীমা আর পরিষ্কার error দরকার, Haat-এর ১০০০-এর মতো।

Explicit stack (একটি list-এ বাকি কাজ রাখা) heap ব্যবহার করে, তাই সীমা অনেক বড়, আর ভাষার TCO-র ওপর নির্ভর করে না। দাম: কোড বেশি যান্ত্রিক, অবস্থা হাতে সামলাতে হয়। এটি আসলে CPS-এর defunctionalized রূপ।

Trampoline tail-recursive বা mutual recursive কোডের গঠন প্রায় অক্ষত রাখে, কিন্তু প্রতিটি ধাপে একটি closure তৈরি করে, তাই ধীর। Python বা JVM-ভাষায় state machine বা interpreter লেখায় এটি কাজে আসে।

CPS সবচেয়ে সাধারণ, যেকোনো recursion-কে tail call বানায়, কিন্তু হাতে লেখা কঠিন আর পড়া কঠিনতর; এটি মানুষের চেয়ে compiler-এর হাতিয়ার। Language-agnostic কোনো “সেরা” উত্তর নেই: ভাষা TCO নিশ্চিত করলে (Scheme, OCaml) tail recursion স্বাভাবিক; না করলে explicit stack সবচেয়ে বহনযোগ্য।

মূল উপলব্ধি: recursion আর loop-এর বিতর্ক আসলে “বাকি কাজের তালিকা কোথায় থাকবে” প্রশ্ন: call stack-এ, heap-এর list-এ, না closure-এর শৃঙ্খলে। ইনপুট বাইরের হলে গভীরতার সীমা বা explicit stack নিরাপত্তার অংশ।

প্র ০৫CPS আর SSA — দুটি আলাদা compiler IR কেন একই জিনিসের দুই রূপ বলে গবেষকেরা দেখিয়েছেন?

১৯৭০ থেকে ১৯৯০-এর দশকে functional ভাষার compiler-গুলো (Rabbit, ORBIT, SML/NJ) CPS-কে প্রধান IR হিসেবে ব্যবহার করত: প্রতিটি মধ্যবর্তী মানের একটি নাম, প্রতিটি control-এর স্থানান্তর একটি continuation-এর ডাক, আর প্রতিটি call tail call. অন্যদিকে imperative ভাষার compiler-গুলো (পরে GCC আর LLVM) গ্রহণ করে SSA form (Cytron ও সহকর্মী, ১৯৯১), যেখানে প্রতিটি variable একবারই assign হয় আর control-flow-এর মিলনবিন্দুতে φ function মান বেছে নেয় (পর্ব ৬৩-এ বিস্তারিত)।

Richard Kelsey ১৯৯৫ সালে দেখান যে দুটির মধ্যে একটি সরাসরি অনুবাদ আছে, আর Andrew Appel ১৯৯৮ সালের “SSA is Functional Programming” প্রবন্ধে বিষয়টি সহজ ভাষায় তুলে ধরেন। মূল কথা: SSA-র প্রতিটি basic block একটি nested function-এর মতো, যার parameter হলো block-এর শুরুর φ-গুলো; আর একটি block থেকে অন্য block-এ jump মানে সেই function-কে argument দিয়ে tail call. φ-এর “কোন পথ থেকে এলাম, সেই মান” নিয়ম তখন সাধারণ parameter passing.

এই চোখে দেখলে এই পর্বের অংশ ৩ আর ৪ নতুন অর্থ পায়: tail call আর jump with arguments একই জিনিস, আর একটি loop হলো নিজেকে tail call করা একটি block. LLVM-এর tail recursion elimination ঠিক এটিই উল্টো দিক থেকে করে: নিজেকে-ডাকা call-কে function-এর শুরুর block-এ jump বানায়, আর parameter-গুলোর জন্য φ বসায়।

কোনটি ভালো? CPS-এ continuation স্পষ্ট বলে exception আর non-local control সহজে প্রকাশ হয়; SSA-তে control-flow graph স্পষ্ট বলে dataflow analysis আর register allocation-এর প্রচলিত algorithm সরাসরি চলে। কিছু আধুনিক compiler দুটির মাঝামাঝি নকশা নিয়েছে, যেমন block-এর argument দেওয়া SSA (MLIR আর Swift-এর SIL এমন রূপ ব্যবহার করে বলে জানা যায়)।

মূল উপলব্ধি: “call”, “jump” আর “loop” তিনটি আলাদা ধারণা মনে হলেও tail call-এর চোখে এক। এই ঐক্যই compiler-কে recursion থেকে loop আর loop থেকে recursion-এ অবাধে যাতায়াত করতে দেয়।

অনুশীলন

প্রথমে নিজে করুন, তারপর উত্তর খুলে মেলান। প্রতিটি আউটপুট সত্যিকারের Haat reference (বা তার বর্ধিত কপি), Clang 22.1.8 বা CPython 3.14.4-এ চালিয়ে মেলানো।

  1. নকশা ও বাস্তবায়ন — Haat VM-এ TAIL_CALL: Haat-এর বর্ধিত রূপের জন্য দুটি জিনিস লিখুন: (ক) compiler.py-র function_body-এর শেষে একটি peephole, যা CALL n-এর ঠিক পরে RETURN থাকলে তাকে TAIL_CALL n বানায়; (খ) vm.py-তে TAIL_CALL-এর handler. কেন jump target-গুলো বদলাতে হয় না, আর ১০০০-এর সীমার পরীক্ষা এখানে লাগে কি না, তাও বলুন।

    লেখকের lab-এ reference-এর একটি কপিতে বসিয়ে চালানো সমাধান:

    # compiler.py, end of FnCompiler.function_body (after the body is compiled)
    ins = self.code.instrs                 # peephole: CALL n; RETURN -> TAIL_CALL n
    for i in range(len(ins) - 1):
        if ins[i][0] == "CALL" and ins[i + 1][0] == "RETURN":
            ins[i] = ("TAIL_CALL", ins[i][1])
    
    # vm.py, inside the dispatch loop
    elif op == "TAIL_CALL":                # replace the frame, depth unchanged
        args = stack[len(stack) - arg:]
        del stack[len(stack) - arg:]
        frames[-1] = Frame(stack.pop(), args)

    যুক্তি: peephole শুধু একটি instruction-এর নাম বদলায়, কিছু যোগ বা বাদ দেয় না; তাই সব instruction-এর index আর positions তালিকা আগের মতোই মিলে থাকে, আর JUMP/JUMP_IF_FALSE-এর লক্ষ্য (নকশা-সিদ্ধান্ত ২৮: absolute instruction index) বদলাতে হয় না। কোনো jump যদি পরের RETURN-এ এসে পড়ে, সেটিও অক্ষত। TAIL_CALL frame-এর সংখ্যা বাড়ায় না, তাই সীমার পরীক্ষা লাগে না; নতুন Frame callee-র নিজের nlocals অনুযায়ী slot বানায়, তাই অন্য function-এ (sibling call) গেলেও কাজ করে। <main>-এ কখনো CALL; RETURN হয় না (top-level return নিষেধ, নকশা-সিদ্ধান্ত ২০), তাই main-এর frame কখনো বদলায় না। Captured parameter-এর cell callee নিজের শুরুতে বানায় (LOAD_LOCAL; MAKE_CELL), তাই closure-ও নিরাপদ। যাচাই: reference-এর ১৩টি example-এর vm output হুবহু আগের মতো, sum_to(100000, 0) দেয় 5000050000, আর sum_rec(1000) আগের মতোই 7:16: runtime error: stack overflow. সীমা: &&/||-এর ডান দিকের tail call ধরা পড়ে না (অংশ ৯), আর run (tree-walking) back end আলাদা আচরণ দেবে, যদি না সেখানেও trampoline বসানো হয়।

  2. প্রমাণ — accumulator রূপান্তর অর্থ বদলায় না: Haat-এর fact আর fact_acc (অংশ ১) দেওয়া আছে। Int-এর গুণ ৬৪-bit-এ wrap করে। প্রমাণ করুন: প্রতিটি n আর acc-এর জন্য fact_acc(n, acc) = acc × fact(n) (গুণ mod 264), তাই fact_acc(n, 1) = fact(n).

    প্রমাণ, n-এর ওপর induction (পদ্ধতি Discrete Mathematics কোর্সের পর্ব ১০-এ)। এখানে × মানে mod 264-এ গুণ (তারপর signed রূপে লেখা), যা associative আর commutative, আর 1 তার identity. দাবি P(n): সব acc-এর জন্য fact_acc(n, acc) = acc × fact(n).

    1. ভিত্তি, n ≤ 1: সংজ্ঞা থেকে fact_acc(n, acc) = acc, আর fact(n) = 1. তাই acc × fact(n) = acc × 1 = acc. P(n) সত্য।
    2. Induction-এর ধাপ, n ≥ 2: ধরি P(n − 1) সত্য (সব acc-এর জন্য)। সংজ্ঞা থেকে fact_acc(n, acc) = fact_acc(n − 1, acc × n).
    3. P(n − 1)-কে acc′ = acc × n দিয়ে প্রয়োগ করি: fact_acc(n − 1, acc × n) = (acc × n) × fact(n − 1).
    4. Associativity দিয়ে = acc × (n × fact(n − 1)), আর সংজ্ঞা থেকে n × fact(n − 1) = fact(n). তাই fact_acc(n, acc) = acc × fact(n). P(n) সত্য।
    5. acc = 1 বসালে fact_acc(n, 1) = 1 × fact(n) = fact(n). ∎

    লক্ষ করুন দুটি জিনিস। এক, দাবিটি “সব acc-এর জন্য” লিখতে হয়েছে, নইলে ধাপ ৩-এ acc × n বসানো যেত না; accumulator-এর প্রমাণে এটাই সবচেয়ে প্রচলিত কৌশল (দাবিকে শক্তিশালী করা)। দুই, ধাপ ৪-এ শুধু associativity লেগেছে; বিয়োগে এটি ভাঙে। Wrap থাকলেও প্রমাণ টেকে, কারণ modular গুণ associative. সত্যিকারের run-এ fact(21) আর fact_acc(21, 1) একই wrap-করা মান দেয়: -4249290049419214848.

  3. আউটপুট অনুমান করুন — mutual recursion: নিচের Haat program-এর আউটপুট (ক) Haat v1 reference-এ আর (খ) অনুশীলন ১-এর TAIL_CALL-সহ বর্ধিত রূপে vm দিয়ে কী হবে? is_even(998)-এ সর্বোচ্চ কয়টি frame একসঙ্গে থাকে?
    print(is_even(998));
    print(is_even(1000));
    fn is_even(n: Int) -> Bool {
        if n == 0 { return true; }
        return is_odd(n - 1);
    }
    fn is_odd(n: Int) -> Bool {
        if n == 0 { return false; }
        return is_even(n - 1);
    }

    প্রথমে বৈধতা: function দুটি top-level, তাই ঘোষণার আগেই ডাকা যায় (নকশা-সিদ্ধান্ত ১৭)। is_even(998) ডাকে is_odd(997), is_even(996), …, শেষে is_even(0): n = 998 থেকে 0, মোট ৯৯৯টি call একসঙ্গে বেঁচে (main ছাড়া), সীমার ভেতরে; উত্তর true. is_even(1000)-এ ১০০১টি call দরকার, তাই ১০০১তম call-এ, অর্থাৎ is_odd-এর ভেতরের is_even(n - 1) call-এর শুরুতে (লাইন ৯, কলাম ১২), error. সত্যিকারের run:

    ~/haat $ python haat.py run mutual.haat      # (ক) v1, vm-ও একই
    true
    9:12: runtime error: stack overflow
    ~/haat-tc $ python haat.py vm mutual.haat    # (খ) TAIL_CALL-সহ
    true
    true

    (খ)-তে দুটি return is_…(n - 1);-ই CALL 1; RETURN, তাই দুটিই TAIL_CALL হয়; একটি frame একবার is_even, একবার is_odd হয়ে চলে। এটি sibling call: trampoline ছাড়াই mutual recursion stack-মুক্ত। প্রথম লাইনের output দুই রূপেই এক, কারণ TCO অর্থ বদলায় না, শুধু জায়গা বাঁচায়।

  4. ভুল খুঁজুন: একটি AI assistant দাবি করল, নিচের C function “fully tail-recursive, তাই Clang -O2-তে O(1) stack-এ যেকোনো গাছ গুনবে”। দাবিটি কোথায় ভুল, আর কোন আকারের গাছে stack সবচেয়ে বেশি লাগবে?
    struct node { struct node *left, *right; };
    
    long count(const struct node *t, long acc) {
        if (!t) return acc;
        return count(t->right, count(t->left, acc + 1));
    }

    বাইরের call count(t->right, …) tail position-এ (T-Ret, T-Call), কিন্তু ভেতরের count(t->left, acc + 1) একটি argument, আর argument কখনো tail position নয়: তার ফল দিয়ে বাইরের call করা বাকি। সত্যিকারের -O2 output-এ ঠিক এটাই দেখা যায়: ডান দিকের call loop হয়েছে (jne .LBB0_2), বাম দিকের callq count রয়ে গেছে:

    count:
            movq    %rsi, %rax
            testq   %rdi, %rdi
            je      .LBB0_4
            pushq   %rbx
            movq    %rdi, %rbx
    .LBB0_2:
            movq    (%rbx), %rdi
            movq    8(%rbx), %rbx
            addq    $1, %rax
            movq    %rax, %rsi
            callq   count
            testq   %rbx, %rbx
            jne     .LBB0_2
            popq    %rbx
    .LBB0_4:
            retq

    তাই stack-এর গভীরতা = কোনো পথে পরপর কতগুলো বাম সংযোগ আছে। শুধু ডান দিকে ঝোঁকা গাছ (linked list-এর মতো) O(1) stack নেয়, কিন্তু শুধু বাম দিকে ঝোঁকা গাছে n গভীরতা, আর বড় n-এ stack overflow. সমাধান: একটি explicit stack (বাকি node-গুলোর তালিকা) দিয়ে loop, অথবা CPS + trampoline. শিক্ষা: “tail-recursive” দাবি প্রতিটি call ধরে যাচাই করতে হয়, আর -S output এর সবচেয়ে দ্রুত প্রমাণ।

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

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

ক্রমএকটি stack VM-এ return f(a, b); TCO-সহ চলছে। ঘটনাগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. Callee f-এর মান operand stack-এ তোলা হয়
  2. a আর তারপর b হিসাব করে stack-এ তোলা হয়
  3. TAIL_CALL 2 দুটি argument আর callee stack থেকে নামায়
  4. বর্তমান frame-এর জায়গায় f-এর নতুন frame বসে, ip শুরুতে
  5. f-এর RETURN ফলটি সরাসরি আসল ডাকা-পক্ষে পাঠায়

নিচের কোন return-এ recursive call-টি tail call?

  • return n * fact(n - 1);
  • return f(n - 1) + 0;
  • return f(n - 1, acc * n);
  • return f(f(n));-এর ভেতরের f(n)

Haat v1 reference-এ এই program চালালে কী হয়? fn s(n: Int, acc: Int) -> Int { if n == 0 { return acc; } return s(n - 1, acc + n); } print(s(999, 0)); print(s(1000, 0));

  • 499500, তারপর 500500
  • 499500, তারপর runtime error: stack overflow
  • Static error, কিছুই ছাপে না
  • শুধু runtime error, কিছুই ছাপে না

Clang -O2, x86-64-এ long checkout(long t) { return settle(t + 60); } (settle অন্য file-এ) সাধারণত কোন রূপে compile হয়?

  • pushq, callq settle, popq, retq
  • settle-এর দেহ inline হয়ে যায়
  • একটি loop
  • শুধু addq $60, %rdi আর jmp settle

Trampoline কৌশলে একটি tail-recursive function পরের ধাপের জন্য কী করে?

  • পরের call-টি না করে একটি thunk ফেরত দেয়, যা একটি বাইরের loop ডাকে
  • Recursion limit বাড়িয়ে নিজেকে ডাকে
  • একটি exception ছুড়ে stack খালি করে
  • প্রতিটি ধাপ নতুন thread-এ চালায়

কোন ভাষার মানদণ্ড বাস্তবায়নকে properly tail-recursive হতে বাধ্য করে?

  • Python 3.14
  • Java 21
  • Scheme (R7RS)
  • C23

Continuation-passing style (CPS)-এ লেখা def fact_cps(n, k): return k(1) if n <= 1 else fact_cps(n - 1, lambda r: k(n * r)) CPython 3.14-এ n = 3000-এ RecursionError দেয়। কেন?

  • CPS-এ recursive call tail position-এ থাকে না
  • সব call tail call, কিন্তু CPython tail call-এর frame ফেলে দেয় না
  • Lambda-গুলো stack-এ রাখা হয় বলে
  • Int overflow-এর কারণে

WebAssembly 3.0-এ একটি function-এর শেষে call-এর বদলে return_call লিখলে কী নিশ্চিত হয়?

  • ডাকা-পক্ষের frame ছেড়ে দেওয়া হয়, তাই tail call-এ stack বাড়ে না
  • Call-টি সাধারণ call-এর চেয়ে দ্বিগুণ দ্রুত হয়
  • Callee সবসময় inline হয়
  • Browser তা মানে না, শুধু Safari-তে চলে

শব্দকোষ

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

মনে রাখুন

  1. Frame কেন লাগে: call-এর পরে কাজ বাকি থাকলে (n * □) ডাকা-পক্ষের অবস্থা বাঁচিয়ে রাখতে হয়; বাকি না থাকলে (tail call) frame ফেলে দেওয়া যায়।
  2. Tail position-এর নিয়ম: return e-এর e, আর &&/||-এর ডান দিক; operand, argument, শর্ত, finally বা destructor-এর আগের call কখনো নয়।
  3. TCO = argument বসিয়ে jump: Haat VM-এ CALL; RETURN → TAIL_CALL; Clang -O2-তে callq → jmp বা loop; -O0-তে নয়।
  4. নিশ্চয়তা বনাম optimization: Scheme আর Wasm return_call নিশ্চয়তা দেয়; C/C++ শুধু optimization (Clang-এ musttail); CPython, Java, V8 আর Haat v1-এ নেই।
  5. তিন কৌশল: accumulator (associative কাজে), trampoline (TCO ছাড়া ভাষায়), CPS (সব recursion-কে tail call; stack যায় heap-এর continuation-এ)।

পরের পর্বে: মডিউল ৫ এখানে শেষ। মডিউল ৬ শুরু হবে পর্ব ৩৩ (Type system — static, dynamic, strong আর weak typing) দিয়ে: Haat-এর type mismatch error কোথা থেকে আসে, আর “strong typing” কথাটি কেন এত ঝাপসা।

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

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