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

Stack-based virtual machine — Haat VM তৈরি

A Stack-Based Virtual Machine — Building the Haat VM

Taught in Bangla, this lesson builds the Haat stack virtual machine: the fetch-decode-execute loop, a shared operand stack, call frames with slots, globals, cells for captured variables, CALL and RETURN with a 1000-call limit, and runtime errors that report line and column. It counts executed instructions, compares dispatch techniques and stack versus register VMs, and uses differential testing against the reference implementation. Steppers trace the stack, and in-page Python (Pyodide) blocks run the VM.

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

  • Fetch–decode–execute loop কীভাবে bytecode চালায়, আর operand stack-এ প্রতিটি নির্দেশের পরে কী থাকে
  • নিজের হাতে Haat-এর পূর্ণ VM লেখা: slot, global, cell, closure, CALL আর RETURN, ৩১টি opcode-এর সবকটি
  • Runtime error-এ সঠিক line:col দেখানো আর stack overflow ধরা
  • Instruction গুনে VM-এর খরচ বোঝা, আর switch, table, threaded code ও computed goto ধরনের dispatch কৌশলের তুলনা
  • Tree-walking interpreter আর VM-কে differential testing দিয়ে মিলিয়ে নেওয়া, আর পরীক্ষায় VM-এর stack trace লেখা

১ · Virtual machine কী, আর stack কেন

একটি ব্যস্ত রেস্তোরাঁর রান্নাঘর কল্পনা করুন। ওয়েটার একটি অর্ডার স্লিপ দিয়ে গেছেন, তাতে ক্রমিক নম্বর দেওয়া ছোট ছোট নির্দেশ: “১. চাল নেওয়া, ২. ডাল নেওয়া, ৩. দুটো মেশানো, ৪. থালায় তোলা”। বাবুর্চি একটি আঙুল রাখেন এখন কোন লাইনে আছেন সেখানে। প্রতিবার তিনি লাইনটি পড়েন, বোঝেন কী করতে হবে, কাজটি করেন, তারপর আঙুল এক লাইন নামান। হাতের কাছে আছে থালার একটি স্তূপ: নতুন জিনিস ওপরে রাখেন, মেশানোর সময় ওপরের দুটি নামিয়ে ফল আবার ওপরে রাখেন। স্লিপে কখনো লেখা থাকে “৩ নম্বরে ফেরা”, তখন আঙুল লাফিয়ে যায়।

একটি virtual machine (VM) ঠিক এই বাবুর্চি, শুধু সফটওয়্যারে। অর্ডার স্লিপ হলো bytecode, আঙুল হলো instruction pointer (Haat-এ ip), আর থালার স্তূপ হলো operand stack. যে VM-এর নির্দেশ register-এর নাম না নিয়ে শুধু stack-এর চূড়া থেকে মান নেয়, তাকে বলে stack-based VM বা stack machine. JVM, CPython-এর VM আর WebAssembly এই পরিবারের। আসল CPU-ও একই চক্রে চলে, যার নাম fetch–decode–execute cycle; hardware-এর দিক থেকে এটি দেখতে পারেন কম্পিউটার আর্কিটেকচারের পর্ব ৩২-এ।

এই কোর্সে Haat ধাপে ধাপে বড় হয়েছে। পর্ব ৫৬-এ (Tree-walking interpreter — Haat চালানো) AST সরাসরি চালানো হয়, পর্ব ৫৭-এ environment আর closure-এর বাস্তবায়ন দেখেছেন, আর পর্ব ৫৮-এ (Bytecode নকশা — instruction set আর compiler থেকে bytecode) compiler প্রতিটি function-কে একটি Code object-এ বদলায়: name, arity, nlocals, instrs, positions, consts, local_names, free_names, captures. এই পর্বে সেই Code object-গুলো চালানোর যন্ত্রটি আপনি নিজে বানাবেন। তার আচরণ হতে হবে Haat reference-এর vm.py-র হুবহু সমান, আর প্রতিটি দাবি আমরা reference-এর python -B haat.py vm আর dis চালিয়ে মিলিয়ে দেখব।

Stack কেন? কারণ stack-এর নির্দেশে operand-এর ঠিকানা লিখতে হয় না। 2 + 3 * 4-এর জন্য register যন্ত্রে লিখতে হতো “r1 = 3 * 4; r2 = 2 + r1”, অর্থাৎ প্রতিটি নির্দেশে তিনটি নাম। Stack যন্ত্রে লেখা হয় শুধু “CONST 2; CONST 3; CONST 4; MUL; ADD”: MUL জানে ওপরের দুটি মানই তার operand. তাই compiler সরল হয় (AST-এর post-order হাঁটাই যথেষ্ট, পর্ব ৫৮), আর নির্দেশ ছোট হয়। দাম হলো নির্দেশের সংখ্যা বেশি, কারণ প্রতিটি মান আলাদা নির্দেশে stack-এ তুলতে হয়। এই আপসের হিসাব অংশ ৬-এ।

ছবি ৫৯.১ — Haat VM-এর ভেতরটা, bazar.haat-এর প্রথম price(2, 520) ডাকের এক মুহূর্তে

reference VM-এর সত্যিকারের trace থেকে: price-এর ip 2-এর MUL চলার ঠিক আগে

Haat VM state: code with ip, operand stack, fetch-decode-execute cycle, frames and globals price-এর নির্দেশ operand stack 0 LOAD_LOCAL 0 1 LOAD_LOCAL 1 2 MUL 3 STORE_LOCAL 2 4 LOAD_LOCAL 2 5 CONST 0 ip 2 520 চূড়া ১ fetch ২ decode ৩ execute আবার ১-এ, যতক্ষণ frame আছে frames (ওপরেরটি চলছে) price ip 2 slots [2, 520, ·] main ip 8 globals 0 price 1 delivery 2 first = · 3, 4 = ·
ছবি ৫৯.১ — VM-এর পুরো অবস্থা পাঁচটি জিনিসে: চলমান Code-এর নির্দেশ, ip, একটি operand stack, frame-এর তালিকা (ওপরেরটি চলছে, main-এর ip 8 হলো ফেরার জায়গা), আর global-এর তালিকা। “·” মানে এখনো মান বসেনি; first, total, rounds-এর let/var তখনো চলেনি।

২ · Fetch, decode, execute — দশ লাইনের হৃৎপিণ্ড

পুরো VM-এর কেন্দ্রে একটি while loop. Reference-এর vm.py-তে তার কাঠামো এমন (সরল করে):

while frames:                          # কোনো frame বাকি থাকলে চলবে
    f = frames[-1]                     # ওপরের frame-ই এখন চলছে
    op, arg = f.code.instrs[f.ip]      # fetch: পরের নির্দেশ
    line, col = f.code.positions[f.ip] # error হলে এই ঠিকানা
    f.ip += 1                          # আগেই এক ঘর এগোনো
    if op == "CONST": ...              # decode: কোন opcode?
    elif op == "ADD": ...              # execute: তার কাজ
    ...

তিনটি বিষয় খেয়াল করুন। প্রথমত, ip নির্দেশ চালানোর আগেই বাড়ে; তাই JUMP শুধু f.ip = arg লিখলেই চলে, আর CALL-এর সময় caller-এর frame-এ রয়ে যাওয়া ip-টিই ফেরার ঠিকানা। দ্বিতীয়ত, Haat-এর jump-এর arg হলো নির্দেশের index, byte offset নয় (README-এর সিদ্ধান্ত ২৮), তাই instrs একটি সাধারণ Python list. তৃতীয়ত, loop থামে যখন frame-এর তালিকা খালি হয়, অর্থাৎ <main> নিজে RETURN করেছে। প্রতিটি opcode কী নেয় আর কী রাখে, তার পূর্ণ টেবিল পর্ব ৫৮-এ; এখানে আমরা সেটিকে চালাব।

সবচেয়ে ছোট উদাহরণ print(2 + 3 * 4);. Reference-এর dis-এ এর <main> আটটি নির্দেশ। নিচের stepper প্রতিটি নির্দেশের পরের অবস্থা দেখায় (reference-এর loop-এ প্রতিটি নির্দেশের পরে অবস্থা ছাপিয়ে নেওয়া সত্যিকারের trace).

0CONST 0 ; 21CONST 1 ; 32CONST 2 ; 43MUL4ADD5PRINT6CONST 3 ; ()7RETURN
VM-এর অবস্থা
ip
operand stack
frames
  1. CONST 0. consts[0]-এর মান 2 stack-এ উঠল। ip ইতিমধ্যে 1-এ: পরের নির্দেশ।
  2. CONST 1. 3 উঠল 2-এর ওপরে। এখনো কোনো হিসাব হয়নি, শুধু operand জমছে।
  3. CONST 2. 4 উঠল; stack-এর গভীরতা এখন 3, এই program-এ সর্বোচ্চ।
  4. MUL. ওপরের দুটি নামল: আগে b = 4, তারপর a = 3. ফল 12 উঠল। গুণ আগে হলো, কারণ compiler post-order-এ 3 * 4-এর কোড আগে লিখেছে।
  5. ADD. 12 আর 2 নেমে 14 উঠল। পুরো expression-এর মান এখন একটিমাত্র ঘরে।
  6. PRINT. 14 নামিয়ে লেখা হলো, সঙ্গে newline. Stack আবার খালি: প্রতিটি statement শেষে stack খালি থাকার কথা।
  7. CONST 3. Unit মান () উঠল: <main>-ও একটি function, তাকেও কিছু ফেরত দিতে হয়।
  8. RETURN. শেষ frame সরল; তালিকা খালি, তাই VM ()-টি ফেলে দিয়ে loop থেকে বের হলো। মোট ৮টি নির্দেশ।

এবার নিজের expression দিয়ে দেখুন। নিচের JavaScript block-এ একটি ছোট Pratt parser (পর্ব ৪৮-এর একই binding power) expression-কে post-order-এ Haat-এর opcode-এ বদলায়, তারপর একটি খুদে VM চালায় আর প্রতিটি নির্দেশের পরে stack-এর ছবি আঁকে। SRC বদলে আবার চালান।

// Haat-এর পূর্ণসংখ্যা expression → bytecode → operand stack-এর ছবি, প্রতিটি নির্দেশের পরে
const SRC = "2 + 3 * 4 - (10 - 4) / 3";        // এখানে নিজের expression লিখে আবার চালান
const toks = SRC.match(/\d+|[-+*\/%()]/g);
let i = 0; const code = [], consts = [];
const BP = { "+": 50, "-": 50, "*": 60, "/": 60, "%": 60 };
const NAME = { "+": "ADD", "-": "SUB", "*": "MUL", "/": "DIV", "%": "MOD" };
function expr(minBp) {                          // Pratt: পর্ব ৪৮-এর একই binding power
  let t = toks[i++];
  if (t === "(") { expr(0); i++; }
  else if (t === "-") { expr(70); code.push(["NEG"]); }
  else { let k = consts.indexOf(+t); if (k < 0) k = consts.push(+t) - 1; code.push(["CONST", k]); }
  while (i < toks.length && BP[toks[i]] >= minBp) {
    const op = toks[i++]; expr(BP[op] + 1); code.push([NAME[op]]);   // post-order: বাম, ডান, তারপর op
  }
}
expr(0); code.push(["PRINT"]);
const run = { ADD: (a, b) => a + b, SUB: (a, b) => a - b, MUL: (a, b) => a * b,
              DIV: (a, b) => Math.trunc(a / b), MOD: (a, b) => a % b };   // C-ধাঁচের / আর %
const stack = []; console.log(SRC);
code.forEach(([op, k], ip) => {
  if (op === "CONST") stack.push(consts[k]);
  else if (op === "NEG") stack.push(-stack.pop());
  else if (op === "PRINT") console.log("PRINT →", stack.pop());
  else { const b = stack.pop(), a = stack.pop(); stack.push(run[op](a, b)); }
  const label = (String(ip).padStart(2) + "  " + op + (k === undefined ? "" : " " + k)).padEnd(14);
  console.log(label + "│ " + stack.map(v => "[" + v + "]").join(" "));
});

আসল আউটপুট (browser-এর JavaScript):

2 + 3 * 4 - (10 - 4) / 3
 0  CONST 0   │ [2]
 1  CONST 1   │ [2] [3]
 2  CONST 2   │ [2] [3] [4]
 3  MUL       │ [2] [12]
 4  ADD       │ [14]
 5  CONST 3   │ [14] [10]
 6  CONST 2   │ [14] [10] [4]
 7  SUB       │ [14] [6]
 8  CONST 1   │ [14] [6] [3]
 9  DIV       │ [14] [2]
10  SUB       │ [12]
PRINT → 12
11  PRINT     │ 

একই expression reference-এ print(2 + 3 * 4 - (10 - 4) / 3); হিসেবে চালালে dis-এর 0 থেকে 11 নম্বর নির্দেশ এখানকার সঙ্গে হুবহু এক (constant-এর index-সহ: 10 পেয়েছে index 3, আর দ্বিতীয় 4 পুরোনো index 2 আবার ব্যবহার করেছে), আর haat.py vm ছাপে 12. Stack-এর সর্বোচ্চ গভীরতা 3, যা compiler আগেই হিসাব করতে পারে (পর্ব ৫৮-এর stack-effect checker). এখানে NEG wrap করে না আর মান JavaScript-এর number; পূর্ণ ৬৪-বিট নিয়ম (সিদ্ধান্ত ১৩) Python block-গুলোতে।

৩ · Haat VM, ধাপ ১ — stack, slot, global আর jump

এবার আসল VM. VM-এর input তৈরি করবে পর্ব ৫৮-এর compiler, কোনো বদল ছাড়াই। এই পাতার Python block-গুলো একটি সহায়ক module, haat_vm.py, import করে। তাতে আছে পর্ব ৫৮-এর তিনটি compiler block (compile_expr, compile_stmt, compile_fn) হুবহু, শুধু প্রতিটির শেষের পরীক্ষার লাইন বাদ দিয়ে; সেগুলো পর্ব ৫৮-এর দুটি সহায়ক module, haat_front.py (lexer, parser, slot-সহ resolver) আর haat_code.py (Code আর disassemble), import করে, যা এই পাতায়ও হুবহু রাখা। সঙ্গে যোগ হয়েছে reference-এর runtime.py-র সংক্ষিপ্ত রূপ আর vm.py-র তিনটি ছোট অংশ: Closure (Code আর ধরা cell), Frame (closure, ip, slots) আর UNSET চিহ্ন। লেখকের lab-এ এই compiler-এর dis সব উদাহরণ আর ৫০০টি এলোমেলো program-এ haat.py dis-এর সঙ্গে অক্ষরে অক্ষরে মিলেছে (অংশ ৭)। Type checker নেই, তাই এখানে শুধু ঠিক-type-এর program চালানো হয়।

সহায়ক module haat_vm.py দেখুন (ব্লকগুলো এটি import করে)
# haat_vm.py — সহায়ক অংশ: VM-এর আগের সব ধাপ।
# পর্ব ৫৮-এর তিনটি compiler block (compile_expr, compile_stmt, compile_fn) হুবহু, শুধু শেষের পরীক্ষার লাইন বাদ;
# তারা import করে পর্ব ৫৮-এর haat_front.py (lexer, parser, slot-সহ resolver) আর haat_code.py (Code, disassemble).
# নিচে যোগ: runtime.py-র সংক্ষিপ্ত রূপ আর vm.py-র তিনটি ছোট অংশ (Closure, Frame, UNSET).
# ---- পর্ব ৫৮-এর compile_expr.py, হুবহু (শেষের পরীক্ষার লাইন বাদে) ----
# ধাপ ১: expression থেকে bytecode (reference-এর compiler.py-র FnCompiler, প্রথম অংশ)
from haat_front import *                         # tokenize, Parser, AST class, Resolver, front
from haat_code import *                          # Code, BINARY_OPS, disassemble
class FnCompiler:                                # one per function; makes one Code object
    def __init__(self, res, owner, parent, name, arity):
        self.res, self.owner, self.parent, self.free, self.pos = res, owner, parent, [], (1, 1)
        self.code = Code(name, arity, res.nslots.get(None if owner is None else id(owner), 0))
        self.code.local_names = ["?"] * self.code.nlocals
    def emit(self, op, arg=None, node=None):     # append one instruction, return its index
        if node is not None: self.pos = (node.line, node.col)
        self.code.instrs.append((op, arg)); self.code.positions.append(self.pos)
        return len(self.code.instrs) - 1
    def const(self, value, node=None):           # constant pool: reuse an equal value of the same type
        for i, c in enumerate(self.code.consts):
            if not isinstance(c, Code) and type(c) is type(value) and c == value:
                return self.emit("CONST", i, node)
        self.code.consts.append(value); return self.emit("CONST", len(self.code.consts) - 1, node)
    def where(self, b):                          # which family of opcodes reaches this variable
        if b.is_global: return "GLOBAL", b.slot
        if b.owner is self.owner: return ("CELL" if b.captured else "LOCAL"), b.slot
        return "FREE", self.free_index(b)
    def load(self, b, node): kind, arg = self.where(b); self.emit("LOAD_" + kind, arg, node)
    def expr(self, e):                           # post-order: operands first, operator last
        if isinstance(e, (Num, Str, Bool)): self.const(e.value, e)
        elif isinstance(e, Var): self.load(self.res.uses[id(e)], e)
        elif isinstance(e, Unary): self.expr(e.operand); self.emit("NEG" if e.op == "-" else "NOT", None, e)
        elif isinstance(e, Binary): self.expr(e.left); self.expr(e.right); self.emit(BINARY_OPS[e.op], None, e)
        elif isinstance(e, Call):                # callee first, then arguments left to right
            for part in [e.callee] + e.args: self.expr(part)
            self.emit("CALL", len(e.args), e)

# ---- পর্ব ৫৮-এর compile_stmt.py, হুবহু (শেষের পরীক্ষার লাইন বাদে) ----
# ধাপ ২: statement, লাফ আর short-circuit (একই নামের class আগেরটির ওপর বড় হয়)
class FnCompiler(FnCompiler):
    def patch(self, at):                         # backpatching (পর্ব ২৭): target = next index
        self.code.instrs[at] = (self.code.instrs[at][0], len(self.code.instrs))
    def store(self, b, node): kind, arg = self.where(b); self.emit("STORE_" + kind, arg, node)
    def define(self, b, node):                   # first value of a new name
        if b.is_global: return self.emit("DEFINE_GLOBAL", b.slot, node)
        self.code.local_names[b.slot] = b.name; self.emit("MAKE_CELL" if b.captured else "STORE_LOCAL", b.slot, node)
    def expr(self, e):
        if not (isinstance(e, Binary) and e.op in ("&&", "||")): return super().expr(e)
        self.expr(e.left); skip = self.emit("JUMP_IF_FALSE", None, e)   # no && or || opcode
        self.expr(e.right) if e.op == "&&" else self.const(True, e)
        end = self.emit("JUMP", None, e); self.patch(skip)
        (self.const(False, e) if e.op == "&&" else self.expr(e.right)); self.patch(end)
    def stmt(self, s):
        if isinstance(s, Let): self.expr(s.init); self.define(self.res.decls[id(s)], s)
        elif isinstance(s, Assign): self.expr(s.value); self.store(self.res.uses[id(s)], s)
        elif isinstance(s, If):
            self.expr(s.cond); to_else = self.emit("JUMP_IF_FALSE", None, s); self.stmt(s.then)
            if s.else_ is None: self.patch(to_else)
            elif always_returns(s.then.stmts): self.patch(to_else); self.stmt(s.else_)
            else: to_end = self.emit("JUMP", None, s); self.patch(to_else); self.stmt(s.else_); self.patch(to_end)
        elif isinstance(s, While):
            top = len(self.code.instrs); self.expr(s.cond); to_end = self.emit("JUMP_IF_FALSE", None, s)
            self.stmt(s.body); self.emit("JUMP", top, s); self.patch(to_end)
        elif isinstance(s, Return):              # return; gives the Unit value ()
            (self.const(None, s) if s.value is None else self.expr(s.value)); self.emit("RETURN", None, s)
        elif isinstance(s, Print): self.expr(s.value); self.emit("PRINT", None, s)
        elif isinstance(s, ExprStmt): self.expr(s.expr); self.emit("POP", None, s)
        elif isinstance(s, Block): [self.stmt(inner) for inner in s.stmts]

# ---- পর্ব ৫৮-এর compile_fn.py, হুবহু (শেষের পরীক্ষার লাইন বাদে) ----
# ধাপ ৩: function, closure, hoisting — তারপর reference-এর আসল `dis`-এর সঙ্গে মেলানো
class FnCompiler(FnCompiler):
    def free_index(self, b):                     # a variable of an enclosing function
        if b not in self.free: self.free.append(b); self.code.free_names.append(b.name)
        return self.free.index(b)
    def expr(self, e):                           # an anonymous fn is an expression too
        return super().expr(e) if not isinstance(e, Lambda) else self.closure(e, f"lambda@{e.line}:{e.col}")
    def stmt(self, s):
        if not isinstance(s, FnDecl): return super().stmt(s)
        b = self.res.decls[id(s)]                # a nested fn declaration
        if b.captured:                           # cell first, so the fn can see itself
            self.const(None, s); self.define(b, s); self.closure(s, s.name); self.store(b, s)
        else: self.closure(s, s.name); self.define(b, s)
    def closure(self, f, name):                  # compile the inner function, then MAKE_CLOSURE
        inner = FnCompiler(self.res, f, self, name, len(f.params)); inner.function_body(f)
        self.code.consts.append(inner.code); self.emit("MAKE_CLOSURE", len(self.code.consts) - 1, f)
    def function_body(self, f):
        for p in f.params:                       # parameters arrive in slots 0..arity-1
            b = self.res.decls[id(p)]; self.code.local_names[b.slot] = p.name
            if b.captured: self.emit("LOAD_LOCAL", b.slot, p); self.emit("MAKE_CELL", b.slot, p)
        for s in f.body.stmts: self.stmt(s)
        if not always_returns(f.body.stmts): self.const(None, f.body); self.emit("RETURN")
        for b in self.free:                      # where MAKE_CLOSURE (in the parent) finds each cell
            self.code.captures.append((True, b.slot) if b.owner is self.parent.owner else (False, self.parent.free_index(b)))
def compile_program(program, res):
    main = FnCompiler(res, None, None, "<main>", 0)
    for s in program.stmts:                      # decision 17: top-level functions first (hoisting)
        if isinstance(s, FnDecl): main.closure(s, s.name); main.emit("DEFINE_GLOBAL", res.decls[id(s)].slot, s)
    for s in (s for s in program.stmts if not isinstance(s, FnDecl)): main.stmt(s)
    main.const(None); main.emit("RETURN")
    main.code.global_names = [b.name for b in sorted((b for b in res.decls.values() if b.is_global), key=lambda b: b.slot)]
    return main.code

# ---- runtime.py: interpreter আর VM-এর ভাগ করা মান-নিয়ম ----
class HaatRuntimeError(HaatError):            # errors.py-র HaatError(runtime=True)
    def __str__(self): return f"{self.line}:{self.col}: runtime error: {self.message}"
MAX_CALL_DEPTH = 1000                         # decision 26
def wrap(n): return ((n + 2**63) % 2**64) - 2**63          # decision 13: 64-bit wrap
def c_quot(a, b, line, col):                  # C-style: truncate toward zero
    if b == 0: raise HaatRuntimeError(line, col, "division by zero")
    q = abs(a) // abs(b); return q if (a < 0) == (b < 0) else -q
def arith(op, a, b, line, col):
    if op == "+": return a + b if isinstance(a, str) else wrap(a + b)
    if op == "-": return wrap(a - b)
    if op == "*": return wrap(a * b)
    if op == "/": return wrap(c_quot(a, b, line, col))
    if op == "%": return wrap(a - b * c_quot(a, b, line, col))
    return {"==": a == b, "!=": a != b, "<": a < b, "<=": a <= b, ">": a > b, ">=": a >= b}[op]
def show(v):                                  # decision 27
    if isinstance(v, bool): return "true" if v else "false"
    return str(v)
ARITH = {op: sym for sym, op in BINARY_OPS.items()}   # VM-এর জন্য: "ADD" -> "+"

# ---- vm.py-র তিনটি ছোট অংশ (VM নিজে পাতার block-এ) ----
class Closure:                                # একটি function-মান: Code + ধরা cell-গুলো
    def __init__(self, code, cells): self.code, self.cells = code, cells
class Frame:                                  # একটি ডাকের ঘর: কোন closure, পরের নির্দেশ (ip), slots
    def __init__(self, closure, args):
        self.closure, self.code, self.ip = closure, closure.code, 0
        self.slots = list(args) + [None] * (closure.code.nlocals - len(args))
UNSET = object()                              # যে global-এর let/var এখনো চলেনি

def compile_src(src):                         # source -> <main> Code (type check নেই: ঠিক-type-এর program)
    return compile_program(*front(src))

প্রথম ধাপে আমরা সেই opcode-গুলো লিখব যেগুলো function-এর ডাক ছাড়াই চলে: constant, local slot, global, এগারোটি গাণিতিক ও তুলনার নির্দেশ, NEG, NOT, দুটি jump, PRINT, POP আর RETURN. Reference-এর vm.py এগুলো একটি লম্বা if/elif শিকলে বাছে; এখানে আমরা প্রতিটি opcode-এর জন্য একটি method লিখে একটি dispatch table বানাই। দুই পদ্ধতির ফল এক, কিন্তু খরচ আলাদা (অংশ ৬)। পূর্ণ রূপ reference-এর vm.py-তে।

from haat_vm import *     # পর্ব ৫৮-এর compiler + disassemble, Frame, Closure, UNSET, arith, show
class VM:
    def __init__(self, main, out=print):
        self.main, self.out, self.stack, self.G = main, out, [], [UNSET] * len(main.global_names)
        self.frames = [Frame(Closure(main, []), [])]
        self.table = {n[3:]: getattr(self, n) for n in dir(self) if n.startswith("op_")}
    def run(self):
        while self.frames:
            f = self.frames[-1]
            name, arg = f.code.instrs[f.ip]                 # fetch
            self.pos = f.code.positions[f.ip]; f.ip += 1
            self.table.get(name, self.op_ARITH)(f, arg, name)  # decode (table) + execute
    def fail(self, msg): raise HaatRuntimeError(*self.pos, msg)
    def glob(self, g):
        if self.G[g] is UNSET: self.fail(f"'{self.main.global_names[g]}' is not initialized yet")
        return self.G[g]
    def op_CONST(self, f, k, _): self.stack.append(f.code.consts[k])
    def op_LOAD_LOCAL(self, f, s, _): self.stack.append(f.slots[s])
    def op_STORE_LOCAL(self, f, s, _): f.slots[s] = self.stack.pop()
    def op_DEFINE_GLOBAL(self, f, g, _): self.G[g] = self.stack.pop()
    def op_LOAD_GLOBAL(self, f, g, _): self.stack.append(self.glob(g))
    def op_STORE_GLOBAL(self, f, g, _): self.glob(g); self.G[g] = self.stack.pop()
    def op_ARITH(self, f, _, name):
        b, a = self.stack.pop(), self.stack.pop(); self.stack.append(arith(ARITH[name], a, b, *self.pos))
    def op_NEG(self, f, _, __): self.stack.append(wrap(-self.stack.pop()))
    def op_NOT(self, f, _, __): self.stack.append(not self.stack.pop())
    def op_JUMP(self, f, t, _): f.ip = t
    def op_JUMP_IF_FALSE(self, f, t, _): f.ip = f.ip if self.stack.pop() else t
    def op_PRINT(self, f, _, __): self.out(show(self.stack.pop()))
    def op_POP(self, f, _, __): self.stack.pop()
    def op_RETURN(self, f, _, __):
        self.frames.pop()                                    # ফলের মান stack-এ থেকে যায়
        if not self.frames: self.stack.pop()                 # <main> শেষ
code = compile_src("print(2 + 3 * 4);\nvar t = 0;\nwhile t < 5000 { t = t + 1250; }\nprint(t);")
print(disassemble(code), end=""); VM(code).run()

আসল আউটপুট (browser-এর Python):

== <main> (arity 0, locals 0) ==
   0  CONST          0     ; 2
   1  CONST          1     ; 3
   2  CONST          2     ; 4
   3  MUL
   4  ADD
   5  PRINT
   6  CONST          3     ; 0
   7  DEFINE_GLOBAL  0     ; t
   8  LOAD_GLOBAL    0     ; t
   9  CONST          4     ; 5000
  10  LT
  11  JUMP_IF_FALSE  17
  12  LOAD_GLOBAL    0     ; t
  13  CONST          5     ; 1250
  14  ADD
  15  STORE_GLOBAL   0     ; t
  16  JUMP           8
  17  LOAD_GLOBAL    0     ; t
  18  PRINT
  19  CONST          6     ; ()
  20  RETURN
14
5000

উপরের listing পর্ব ৫৮-এর compiler-এর, আর এটি reference-এর dis-এর সঙ্গে হুবহু এক। তারপর VM ছাপল 14 আর 5000. খেয়াল করুন কয়েকটি নকশার সিদ্ধান্ত:

  • self.table তৈরি হয় op_ দিয়ে শুরু হওয়া সব method থেকে। গাণিতিক এগারোটি opcode আলাদা method নয়: table-এ না পেলে op_ARITH চলে, আর সে ARITH থেকে চিহ্ন নিয়ে runtime.py-র arith ডাকে। তাই / আর % C-র মতো শূন্যের দিকে কাটে, আর সব Int ৬৪-বিটে wrap করে (সিদ্ধান্ত ১৩).
  • Operand-এর ক্রম: b, a = pop(), pop(). ওপরেরটি ডান operand, কারণ compiler বাঁ দিক আগে লিখেছে (সিদ্ধান্ত ১২). এটি উল্টালে 7 - 10 হয়ে যায় 3.
  • UNSET: top-level function আগেই (hoisted) চলতে পারে, তখন তার পড়া কোনো global-এর let হয়তো এখনো চলেনি। তাই LOAD_GLOBAL আর STORE_GLOBAL আগে দেখে নেয়, আর না থাকলে দেয় 'k' is not initialized yet (সিদ্ধান্ত ১৮). DEFINE_GLOBAL এই পরীক্ষা করে না, কারণ সেটিই প্রথম মান বসায়।
  • while t < 5000: 8–11 শর্ত, 12–15 দেহ, 16-এর JUMP 8 আবার শর্তে ফেরে, আর শর্ত মিথ্যা হলে 11-এর JUMP_IF_FALSE 17 loop-এর বাইরে লাফায়। এই লক্ষ্যগুলো compiler backpatching দিয়ে বসিয়েছে (পর্ব ২৭)।

একটি variable কোথায় থাকে, তা compiler আগেই ঠিক করে দেয় (resolver-এর Binding দেখে), আর VM শুধু নির্দেশ মেনে চলে। চার রকম জায়গা:

কোন variableকোথায়নির্দেশ
Top level-এর let/var/fnVM-এর G তালিকা, index = slotDEFINE_GLOBAL, LOAD_GLOBAL, STORE_GLOBAL
চলমান function-এর নিজের local, কেউ ধরেনিframe-এর slots[s]-এ সরাসরি মানLOAD_LOCAL, STORE_LOCAL
নিজের local, ভেতরের function ধরেছেslots[s]-এ একটি cell, মান তার ভেতরেMAKE_CELL, LOAD_CELL, STORE_CELL
বাইরের function-এর variable (free variable)closure-এর cells[i]LOAD_FREE, STORE_FREE

Loop কীভাবে চলে, তা bazar.haat-এর while দিয়ে দেখা যাক। শেষ round-টিই সবচেয়ে শিক্ষণীয়, কারণ সেখানে শর্ত একবার সত্য আর একবার মিথ্যা হয়। নিচের stepper reference VM-এর trace-এর ৯৬ থেকে ১১৪ নম্বর নির্দেশ দেখায় (পুরো program ১২০টি নির্দেশ).

22LOAD_GLOBAL 3 ; total23CONST 5 ; 500024LT25JUMP_IF_FALSE 3526LOAD_GLOBAL 3 ; total27CONST 6 ; 125028ADD29STORE_GLOBAL 3 ; total30LOAD_GLOBAL 4 ; rounds31CONST 7 ; 132ADD33STORE_GLOBAL 4 ; rounds34JUMP 2235LOAD_GLOBAL 3 ; total36PRINT
VM-এর অবস্থা
ip
operand stack
total (G[3])
rounds (G[4])
  1. শর্ত হিসাব। 22–24: total (3750) আর 5000 উঠল, LT দুটি নামিয়ে true রাখল। ip এখন 25.
  2. লাফ নয়। JUMP_IF_FALSE 35 মান নামাল; সেটি সত্য, তাই ip বদলাল না, পরের নির্দেশ 26. শর্তের মান stack-এ আর নেই।
  3. total + 1250. 26–28: 3750 আর 1250 যোগ হয়ে 5000 উঠল; এখনো global-এ লেখা হয়নি।
  4. STORE_GLOBAL 3. 5000 নেমে G[3]-এ বসল। আগে দেখে নেওয়া হলো total-এর মান আছে কি না (সিদ্ধান্ত ১৮); আছে।
  5. rounds + 1. 30–33 একই ধাঁচে: rounds 3 থেকে 4. Statement শেষে stack আবার খালি।
  6. JUMP 22. শর্তহীন লাফ: ip সরাসরি 22. পেছনের দিকে লাফ মানেই loop.
  7. আবার শর্ত। এবার 5000 < 5000 মিথ্যা, stack-এ false.
  8. লাফ। JUMP_IF_FALSE মিথ্যা পেয়ে ip = 35. Loop শেষ; চারটি round-এ ৪ × ১৩ = ৫২টি নির্দেশ, আর শেষ পরীক্ষায় আরও ৪টি।
  9. print(total). 35–36: 5000 ছাপা হলো, bazar.haat-এর দ্বিতীয় লাইন। এরপর 37–40 ছাপবে rounds − 1 = 3.

৪ · Haat VM, ধাপ ২ — CALL, RETURN, closure আর cell

বাকি থাকল সাতটি opcode: পাঁচটি cell-সংক্রান্ত, MAKE_CLOSURE আর CALL. Frame-এর ভেতরে কী থাকে আর activation record-এর কোন ঘর VM-এর কোথায়, তা পর্ব ৩০-এ (Subprogram-এর বাস্তবায়ন) bazar.haat-এর price → price → delivery দিয়ে দেখেছেন; cell আর LOAD_FREE-এর ধারণা পর্ব ১৭-এ (Closure). এখানে আমরা সেগুলো আমাদের VM-এ যোগ করব আর পুরো Haat চালাব।

  • CALL n: stack-এ নিচে callee, তার ওপরে n-টি argument (callee আগে মূল্যায়িত, সিদ্ধান্ত ১২). VM ওপরের n-টি কেটে নেয়, তারপর callee-কে নামায়, আর একটি নতুন frame বানিয়ে তালিকায় যোগ করে। পরের fetch নতুন frame-এর ip 0 থেকে। আগে দেখে নেয় তালিকায় ১০০০টির বেশি frame আছে কি না; থাকলে stack overflow (সিদ্ধান্ত ২৬).
  • RETURN: শুধু frame সরায়। ফলের মান যেখানে ছিল সেখানেই থাকে, অর্থাৎ caller-এর operand-গুলোর ঠিক ওপরে, যেন caller নিজেই সেটি push করেছে।
  • MAKE_CLOSURE k: consts[k]-এর Code আর তার captures তালিকা ধরে cell সংগ্রহ: (True, s) মানে “আমার slot s-এর cell”, (False, i) মানে “আমার নিজের ধরা cell i”. Cell-এর ঠিকানা কপি হয়, মান নয়: তাই সবাই একই বাক্স দেখে।
class Cell:                                   # captured variable-এর এক-ঘরের বাক্স (পর্ব ১৭)
    def __init__(self, value): self.value = value
class VM(VM):                                 # আগের block-এর VM, বাকি সাতটি opcode যোগ
    def op_MAKE_CELL(self, f, s, _): f.slots[s] = Cell(self.stack.pop())
    def op_LOAD_CELL(self, f, s, _): self.stack.append(f.slots[s].value)
    def op_STORE_CELL(self, f, s, _): f.slots[s].value = self.stack.pop()
    def op_LOAD_FREE(self, f, i, _): self.stack.append(f.closure.cells[i].value)
    def op_STORE_FREE(self, f, i, _): f.closure.cells[i].value = self.stack.pop()
    def op_MAKE_CLOSURE(self, f, k, _):
        code = f.code.consts[k]               # captures: (নিজের slot?, index)
        cells = [f.slots[i] if mine else f.closure.cells[i] for mine, i in code.captures]
        self.stack.append(Closure(code, cells))
    def op_CALL(self, f, n, _):
        if len(self.frames) > MAX_CALL_DEPTH: self.fail("stack overflow")
        args = self.stack[len(self.stack) - n:]; del self.stack[len(self.stack) - n:]
        self.frames.append(Frame(self.stack.pop(), args))   # callee নিচে, argument ওপরে

def vm_lines(src):                            # tests/helpers.py-র run(src, "vm")-এর মতো
    lines = []
    try: VM(compile_src(src), lambda t: lines.extend(t.split("\n"))).run()
    except HaatError as e: lines.append(str(e))
    return lines

print(len(VM(compile_src("")).table), "opcode handler")
print(*vm_lines(open("examples/bazar.haat", encoding="utf-8").read()))
print(*vm_lines("fn d(n: Int) -> Int { return d(n + 1); } print(d(0));"))
names = "bazar counter err_divzero loops mutual nested recursion shadowing shortcircuit strings".split()
same = [n for n in names if vm_lines(open(f"examples/{n}.haat", encoding="utf-8").read())
        == open(f"examples/{n}.out", encoding="utf-8").read().splitlines()]
print(f"golden .out মিলেছে: {len(same)}/{len(names)}")

আসল আউটপুট (browser-এর Python):

21 opcode handler
996 5000 3
1:30: runtime error: stack overflow
golden .out মিলেছে: 10/10

২১টি handler মিলে ৩১টি opcode (এগারোটি গাণিতিক একটি handler ভাগ করে)। bazar.haat ছাপল 996, 5000, 3: reference-এর মতোই। অসীম recursion থামল 1:30-এ: return d(n + 1);-এর callee d-এর শুরু, কারণ call-এর error callee-র শুরুতে দেখানো হয় (সিদ্ধান্ত ২৪)। শেষ লাইনটিই সবচেয়ে গুরুত্বপূর্ণ: reference-এর প্রতিটি উদাহরণের সঙ্গে রাখা .out ফাইল (golden file) এই VM-এর আউটপুটের সঙ্গে দশে দশ মিলেছে, closure (counter, nested), mutual recursion, Bangla string, ৬৪-বিট wrap আর division by zero-সহ। পাতায় এই উদাহরণগুলো reference-এর examples/ থেকে হুবহু রাখা আছে। Syntax, নাম আর type-এর error-ওয়ালা তিনটি উদাহরণ বাদ: সেগুলো VM পর্যন্ত পৌঁছায়ই না।

একটি ডাকের ভেতরে আরেকটি ডাক হলে operand stack-এ কী ঘটে, তা দেখতে একটি ছোট higher-order program নেওয়া যাক। twice একটি function আর একটি সংখ্যা নেয়, আর function-টি দুবার লাগায়:

fn inc(n: Int) -> Int { return n + 1; }
fn twice(f: (Int) -> Int, x: Int) -> Int { return f(f(x)); }
print(twice(inc, 5));

f(f(x))-এর জন্য compiler লেখে: বাইরের callee f, ভেতরের callee f, x, CALL 1, CALL 1. অর্থাৎ ভেতরের ডাক চলার পুরো সময় বাইরের callee stack-এর নিচে অপেক্ষা করে। নিচের ধাপগুলো reference VM-এর ২৫টি নির্দেশের trace থেকে বাছাই করা।

m4LOAD_GLOBAL 1 ; twicem5LOAD_GLOBAL 0 ; incm6CONST 2 ; 5m7CALL 2m8PRINTt0LOAD_LOCAL 0 ; ft1LOAD_LOCAL 0 ; ft2LOAD_LOCAL 1 ; xt3CALL 1t4CALL 1t5RETURNi0LOAD_LOCAL 0 ; ni1CONST 0 ; 1i2ADDi3RETURN
VM-এর অবস্থা
frames
ওপরের slots
operand stack
  1. Argument সাজানো। main-এর 4–6: callee twice আগে, তারপর inc (একটি function-ও সাধারণ মান) আর 5. ip এখন 7.
  2. CALL 2. ওপরের দুটি (fn inc, 5) twice-এর slot 0 আর 1-এ গেল, তারপর fn twice নামল। Stack খালি; main-এর ip 8-ই ফেরার জায়গা।
  3. দুটি callee আর x. twice-এর 0–2: f দুবার, তারপর x. নিচের fn inc বাইরের ডাকের callee, ওপরেরটি ভেতরের।
  4. ভেতরের CALL 1. 5 গেল inc-এর slot 0-এ, ওপরের fn inc নামল। নিচে একটি fn inc পড়ে রইল: সেটি twice-এর অর্ধেক-শেষ কাজ। তিনটি frame একসঙ্গে।
  5. inc চলে। n আর 1 উঠে ADD: 6. inc-এর হিসাব ঠিক বাইরের callee-র ওপরে হচ্ছে, কিন্তু inc সেটি ছোঁয় না।
  6. RETURN. inc-এর frame গেল, 6 যেখানে ছিল সেখানেই রইল। এখন stack ঠিক বাইরের CALL 1-এর যা দরকার: callee আর একটি argument.
  7. বাইরের CALL 1. একই function-এর নতুন frame, এবার slot-এ 6. twice-এর ip 5-এ ফিরবে।
  8. আবার inc. 6 + 1 = 7, RETURN; inc-এর দ্বিতীয় frame-ও গেল।
  9. twice-এর RETURN. 7 stack-এ রেখে twice-এর frame সরল। main ip 8 থেকে চলবে।
  10. PRINT. 7 ছাপা হলো। তারপর main-এর CONST () আর RETURN; মোট ২৫টি নির্দেশ, সর্বোচ্চ ৩টি frame.

দুটি stack আলাদা রাখা জরুরি। frames তালিকা Haat program-এর call stack, আর operand stack হিসাবের কাজের জায়গা; দুটিই VM-এর নিজের Python list. Haat-এর একটি ডাক Python-এর কোনো ডাক তৈরি করে না, তাই VM-এ Haat-এর গভীরতা Python-এর recursion limit-এ আটকায় না। সীমাটি (১০০০) VM নিজে গোনে, ঠিক tree-walking interpreter-এর মতো, যাতে দুই back end একই জায়গায় থামে।

৫ · Runtime error — কোন লাইন, কোন কলাম

Bytecode-এ source-এর কোনো চিহ্ন নেই, তবু VM বলে 3:18: runtime error: division by zero. কীভাবে? Compiler প্রতিটি নির্দেশ লেখার সময় পাশের positions তালিকায় একটি (line, col) লেখে, যে AST node থেকে নির্দেশটি এসেছে তার অবস্থান। DIV-এর জন্য সেটি / চিহ্নের অবস্থান (সিদ্ধান্ত ২৪)। VM fetch-এর সময় নির্দেশের সঙ্গে position-টিও পড়ে রাখে, আর error হলে সেটিই ছাপে। CPython একই কাজ করে আরও ঘন একটি টেবিলে (line আর column-এর range); Java-র class file-এ আছে LineNumberTable.

indexনির্দেশpositionsource-এ
0LOAD_LOCAL 0 ; total3:12total
1LOAD_LOCAL 1 ; people3:20people
2DIV3:18/ চিহ্ন
3RETURN3:5return

reference-এর err_divzero.haat-এ share(1000, 4) ছাপে 250, তারপর share(1000, 0)-এর ভেতরের DIV-এ (program-এর ১৮তম নির্দেশ) থামে। সত্যিকারের run:

$ python -B haat.py vm examples/err_divzero.haat
250
3:18: runtime error: division by zero      (stderr, exit status 1)

লক্ষ করুন, error ঘটেছে share-এর ভেতরে, কিন্তু position বলছে share-এর সংজ্ঞার লাইন (3), ডাকার লাইন (6) নয়। আরও তথ্য দিতে চাইলে VM error-এর সময় পুরো frames তালিকা হেঁটে প্রতিটি frame-এর ip থেকে position বের করতে পারত, ঠিক Python-এর traceback-এর মতো (অনুশীলন ১-এর পরের ধাপ হিসেবে ভাবতে পারেন)। Haat-এর তিনটি runtime error আর তাদের ঠিকানা:

Errorকোন নির্দেশেposition কোথায়
division by zeroDIV, MOD/ বা % চিহ্ন
'k' is not initialized yetLOAD_GLOBAL, STORE_GLOBALনামের ব্যবহারের জায়গা
stack overflowCALLcallee-র শুরু

ভুলের ফাঁদ: error-এর পরে আগের আউটপুট মুছে যায় না (সিদ্ধান্ত ২৬): 250 ছাপা থাকে। VM-এর print সরাসরি লেখে, তাই এটি স্বাভাবিকভাবেই সত্য; কিন্তু যদি আপনি আউটপুট একটি buffer-এ জমিয়ে শেষে লেখেন, error-এর সময় buffer ফেলে দিলে এই নিয়ম ভাঙবে, আর interpreter-এর সঙ্গে আউটপুট মিলবে না।

৬ · খরচ মাপা — instruction গোনা আর dispatch কৌশল

VM কতটা কাজ করে, তা মাপার সবচেয়ে সৎ একক হলো চালানো নির্দেশের সংখ্যা: সময়ের মতো এটি যন্ত্র বা browser বদলালে বদলায় না। নিচের block একটি ছোট profiler: VM-এর loop-এ একটি গণনা যোগ করে, কোন opcode কতবার আর কোন function-এ কতগুলো। সঙ্গে হিসাব করে, reference-এর if/elif শিকলে একটি opcode খুঁজে পেতে মোট কয়টি শাখা-পরীক্ষা লাগত (প্রতিটি if/elif একটি পরীক্ষা ধরে)।

from collections import Counter
class CountingVM(VM):                         # profiler: প্রতিটি নির্দেশ গোনা, কোন function-এ তাও
    def run(self):
        self.ops, self.fns = Counter(), Counter()
        while self.frames:
            f = self.frames[-1]
            name, arg = f.code.instrs[f.ip]
            self.ops[name] += 1; self.fns[f.code.name] += 1
            self.pos = f.code.positions[f.ip]; f.ip += 1
            self.table.get(name, self.op_ARITH)(f, arg, name)

# reference vm.py-র if/elif শিকলের ক্রম: একটি opcode পেতে কতটি পরীক্ষা লাগে
CHAIN = ["CONST", "LOAD_LOCAL", "STORE_LOCAL", "MAKE_CELL", "LOAD_CELL", "STORE_CELL",
         "LOAD_FREE", "STORE_FREE", "DEFINE_GLOBAL", "LOAD_GLOBAL STORE_GLOBAL",
         "ADD SUB MUL DIV MOD EQ NE LT LE GT GE", "NEG", "NOT", "JUMP", "JUMP_IF_FALSE",
         "MAKE_CLOSURE", "CALL", "RETURN", "PRINT", "POP"]
TESTS = {op: i + 1 for i, group in enumerate(CHAIN) for op in group.split()}

FIB = "fn fib(n: Int) -> Int { if n < 2 { return n; } return fib(n - 1) + fib(n - 2); }\nprint(fib(15));"
for title, src in [("bazar.haat", open("examples/bazar.haat", encoding="utf-8").read()), ("fib(15)", FIB)]:
    vm = CountingVM(compile_src(src), out=lambda t: None); vm.run()
    total = sum(vm.ops.values())
    chain = sum(TESTS[op] * k for op, k in vm.ops.items())
    print(f"{title}: মোট {total} নির্দেশ; function অনুযায়ী {dict(vm.fns)}")
    print("  সবচেয়ে বেশি:", ", ".join(f"{op} {k}" for op, k in vm.ops.most_common(5)))
    print(f"  if/elif শিকলে মোট পরীক্ষা {chain} (গড় {chain / total:.2f}), table-এ {total} lookup")

আসল আউটপুট (browser-এর Python):

bazar.haat: মোট 120 নির্দেশ; function অনুযায়ী {'<main>': 86, 'price': 28, 'delivery': 6}
  সবচেয়ে বেশি: CONST 27, LOAD_GLOBAL 19, LOAD_LOCAL 11, ADD 9, JUMP_IF_FALSE 8
  if/elif শিকলে মোট পরীক্ষা 1022 (গড় 8.52), table-এ 120 lookup
fib(15): মোট 21706 নির্দেশ; function অনুযায়ী {'<main>': 8, 'fib': 21698}
  সবচেয়ে বেশি: LOAD_LOCAL 4932, CONST 3947, RETURN 1974, LOAD_GLOBAL 1973, CALL 1973
  if/elif শিকলে মোট পরীক্ষা 186494 (গড় 8.59), table-এ 21706 lookup

bazar.haat-এ ১২০টি নির্দেশ, reference VM-এর trace-এর সংখ্যার সঙ্গে হুবহু এক: price দুবার × ১৪, delivery ৬, বাকি ৮৬টি main-এ, যার ৫৬টি loop-এ। fib(15)-এ ২১৭০৬টি নির্দেশ: প্রতিটি n < 2 ডাকে ৬টি, প্রতিটি বাকি ডাকে ১৬টি; ৯৮৭ × ৬ + ৯৮৬ × ১৬ + main-এর ৮ = ২১৭০৬. সবচেয়ে বেশি চলে LOAD_LOCAL আর CONST: stack যন্ত্রে মান তোলার নির্দেশই কাজের বড় অংশ। আর if/elif শিকলে গড়ে প্রায় সাড়ে আটটি পরীক্ষা লাগে, কারণ ঘন ঘন চলা CALL, RETURN আর গাণিতিক নির্দেশ শিকলের মাঝে বা শেষে বসে আছে।

Dispatch — opcode থেকে তার কোডে পৌঁছানোর পথ

“কোন opcode? তার কোডে যাও” এই অংশের নাম dispatch. ছোট নির্দেশের VM-এ প্রতিটি নির্দেশের আসল কাজ (দুটি সংখ্যা যোগ) খুব ছোট, তাই dispatch-এর খরচই প্রায়ই সময়ের বড় অংশ। প্রচলিত কৌশল চারটি:

if/elif বা switch

Python-এ শিকল: প্রতিটি নির্দেশে গড়ে কয়েকটি তুলনা (bazar-এ ৮.৫২)। C-তে ঘন case-ওয়ালা switch সাধারণত compiler একটি jump table বানায়, ফলে একটি সীমা-পরীক্ষা আর একটি indirect jump.

Haat reference-এর vm.py

Handler-এর table

opcode দিয়ে একটি table থেকে function বের করে ডাকা: প্রতিটি নির্দেশে একটি lookup আর একটি function call. পরিষ্কার, সহজে বাড়ানো যায়; এই পাতার VM.

এই পাতার VM

Threaded code আর computed goto

প্রতিটি handler-এর শেষে নিজেই পরের নির্দেশের handler-এ লাফ দেয়, কেন্দ্রীয় loop-এ না ফিরে। GCC আর Clang-এর “labels as values” (goto *table[op]) দিয়ে C-তে এটি লেখা যায়; একে বলে computed goto, আর মূল ধারণার নাম threaded code.

CPython (সমর্থিত compiler-এ)

Tail-call interpreter

প্রতিটি opcode একটি ছোট C function, আর প্রতিটি পরেরটিকে tail call দিয়ে ডাকে। CPython 3.14-এ নতুন, এখন opt-in: Clang 19 বা নতুন, x86-64 আর AArch64-এ, --with-tail-call-interp দিয়ে build করতে হয়।

CPython 3.14, ঐচ্ছিক

শেষ দুটি কেন দ্রুত হতে পারে? একটি কেন্দ্রীয় loop-এ সব নির্দেশের জন্য একটিই indirect jump থাকে, ফলে CPU-র branch prediction-এর কাছে সেই একটি jump-এর গন্তব্য প্রায় এলোমেলো। প্রতিটি handler-এর শেষে আলাদা jump থাকলে predictor শিখতে পারে “LOAD_LOCAL-এর পরে প্রায়ই CONST আসে”। এই ব্যাখ্যা বহু গবেষণায় মাপা হয়েছে, তবে আধুনিক CPU-র predictor অনেক উন্নত হওয়ায় লাভের পরিমাণ যন্ত্রভেদে বেশ আলাদা; CPython 3.14-এর release note-ও tail-call interpreter-এর লাভকে প্রাথমিক benchmark-এ গড়ে ৩–৫% বলে, platform-ভেদে। আরেকটি পুরোনো কৌশল superinstruction: প্রায়ই একসঙ্গে আসা নির্দেশ জোড়া (যেমন LOAD_LOCAL + CONST) একটি নির্দেশে মেলানো, ফলে dispatch কমে।

Python-এ লেখা VM-এ হিসাব উল্টে যেতে পারে। লেখকের যন্ত্রে fib(22) (৬,৩০,৪৪৬টি নির্দেশ, ৫৭,৩১৩টি CALL) তিনভাবে চালানো হলো, প্রতিটি পাঁচবার, সবচেয়ে কম সময় নেওয়া:

$ python -B timing.py                       # সত্যিকারের run, CPython 3.14.4, একটি Windows ল্যাপটপ
reference vm.py (if/elif)            0.158 s   output ['17711']
page VM (method table)               0.212 s   output ['17711']
reference interp.py (tree walking)   0.200 s   output ['17711']

এই সংখ্যা শুধু একটি যন্ত্রের উদাহরণ, benchmark নয়; কিন্তু শিক্ষাটি পরিষ্কার। CPython-এ একটি method call কয়েকটি string তুলনার চেয়ে বেশি দামি, তাই আমাদের table-ওয়ালা VM শিকলের চেয়ে ধীর। আর Python-এ লেখা bytecode VM tree-walking interpreter-এর চেয়ে সামান্যই দ্রুত, কারণ দুটির ক্ষেত্রেই প্রতিটি ছোট কাজের পেছনে CPython-এর নিজের অনেকগুলো bytecode চলে। Bytecode VM-এর আসল সুবিধা আসে C, C++ বা Rust-এ লিখলে, যেখানে একটি ADD সত্যিই কয়েকটি যন্ত্র-নির্দেশ। তবু Python-এর VM-টি শিক্ষার জন্য মূল্যবান: এটি পরিষ্কার দেখায় নির্দেশের সংখ্যা কোথায় যায়, আর পর্ব ৬১-এর (JIT compilation — profiling, tracing আর deoptimization) toy JIT ঠিক এই গণনা থেকেই “গরম” function খুঁজবে।

Stack VM বনাম register VM

Lua 5.0 (২০০৩ সালের দিকে) stack VM ছেড়ে register VM-এ যায়: ADD r1 r2 r3 ধাঁচের নির্দেশ, যেখানে operand frame-এর ঘরের নম্বর। একই কাজে নির্দেশ কম লাগে (Haat-এর LOAD_LOCAL 2; CONST 0; GE হতে পারত একটি নির্দেশ), ফলে dispatch-ও কম; দাম হলো প্রতিটি নির্দেশ বড়, আর compiler-কে register বণ্টন করতে হয়। Lua-র লেখকদের প্রবন্ধ আর পরে Shi, Gregg, Beatty ও Ertl-এর “Virtual Machine Showdown: Stack versus Registers” গবেষণা এই আপস মেপেছে; ফলাফল কাজভেদে আলাদা, তাই “register VM সবসময় দ্রুত” বলা ভুল। JVM, CPython আর WebAssembly stack নকশা রেখেছে, আর Android-এর Dalvik register নকশা নিয়েছিল। বাস্তব VM-এর গভীর তুলনা পর্ব ৬০-এ (বাস্তব virtual machine — CPython bytecode আর JVM).

৭ · দুটি back end, একটি উত্তর — differential testing

Haat-এর এখন দুটি back end: tree-walking interpreter (run) আর compiler + VM (vm). দুটি একই program-এ একই আউটপুট দেবে, এটিই ভাষার অর্থের সংজ্ঞা। এই দাবি যাচাইয়ের সবচেয়ে কার্যকর উপায় differential testing: একই input দুই বাস্তবায়নে চালিয়ে মেলানো, অমিল মানে অন্তত একটিতে ভুল। এখানে test oracle হলো অন্য বাস্তবায়নটি, তাই প্রত্যাশিত আউটপুট হাতে লিখতে হয় না, আর হাজার হাজার এলোমেলো program পরীক্ষা করা যায়।

Reference নিজেই এভাবে পরীক্ষিত। লেখকের lab-এ তার test suite আর এই পাতার VM-এর তুলনার সত্যিকারের run:

$ python -B -m unittest discover -s tests          # reference-এর নিজের test
Ran 32 tests in 0.673s
OK

$ python -B difftest.py 500                        # পর্ব ৫৮-এর compiler + এই পাতার VM বনাম reference
examples: 10 files; vm output == `haat.py vm`: 10; dis == `haat.py dis`: 10
random: tried 500, well-typed 500, page VM == reference VM: 500, dis equal: 500,
reference interp == reference VM: 500, ending in runtime error: 113;
with CALL: 413; with LOAD_FREE/STORE_FREE: 269; avg lines: 36.7

Reference-এর test-এ আছে প্রতিটি উদাহরণে interp আর VM-এর সমতা, আর ৪০০টি এলোমেলো Int/Bool expression দুই back end এবং একটি স্বাধীন Python evaluator-এ। আমাদের difftest.py আরও এক ধাপ যায়: seed 59 দিয়ে তৈরি ৫০০টি পূর্ণ program (গড়ে ৩৭ লাইন: function, nested block, while, closure যা বাইরের var বদলায়, if/else, ভাগ আর ভাগশেষ), প্রতিটির জন্য পূর্ণ dis listing আর আউটপুট (runtime error-এর লাইনসহ) মেলায়। ৫০০-এ ৫০০ মিলেছে; ১১৩টি শেষ হয়েছে runtime error-এ (বেশিরভাগ ভাগে শূন্য), যা error-এর position-ও যাচাই করে।

নিয়ম ৫৯.১ — differential testing-এর অন্ধ জায়গা

দুটি বাস্তবায়ন যা ভাগ করে নেয়, সেখানকার ভুল differential testing ধরতে পারে না। Haat-এর interp আর VM দুটিই runtime.py-র c_div আর wrap ব্যবহার করে; সেখানে ভুল থাকলে দুটিই একই ভুল উত্তর দেবে, আর তুলনা “মিলেছে” বলবে। এজন্যই reference-এর random test একটি স্বাধীনভাবে লেখা evaluator-এর সঙ্গেও মেলায়, আর golden .out ফাইল হাতে যাচাই করা।

আরও গভীরে: Stack-ভিত্তিক মধ্যবর্তী কোডের পুরোনো উদাহরণ ১৯৭০-এর দশকের Pascal-এর P-code; UCSD Pascal-এর p-System একই P-code বিভিন্ন যন্ত্রে চালিয়ে বহনযোগ্যতার ধারণা জনপ্রিয় করে, যা পরে JVM-এর “একবার compile, সব জায়গায় চালাও” ভাবনার পূর্বসূরি হিসেবে প্রায়ই বলা হয়। “Threaded code” নামটি James Bell-এর ১৯৭৩ সালের প্রবন্ধ থেকে, আর Forth ভাষা এর বিখ্যাত ব্যবহারকারী। আধুনিক interpreter-এর dispatch আর branch prediction-এর সম্পর্ক বিস্তারিত মেপেছেন Anton Ertl ও David Gregg, ২০০০-এর দশকের শুরুর দিকের কাজে।

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

  • একটি expression-এর stack code লিখে প্রতিটি নির্দেশের পরে stack দেখান। Post-order-এ নির্দেশ, binary নির্দেশে ওপরেরটি ডান operand (অংশ ২-এর stepper-এর মতো টেবিল).
  • Stack VM আর register VM-এর পার্থক্য? Stack VM-এ নির্দেশ ছোট আর compiler সরল, কিন্তু নির্দেশ বেশি; register VM-এ নির্দেশ কম আর বড়, compiler-কে register বণ্টন করতে হয়।
  • VM-এ function call আর return কীভাবে হয়? CALL নতুন frame বানায় আর argument slot-এ বসায়, ফেরার ঠিকানা caller-এর ip; RETURN frame সরায়, ফল stack-এ থাকে।
  • Interpreter-এর dispatch overhead কী, কমানোর উপায়? প্রতিটি নির্দেশে opcode বাছাইয়ের খরচ; jump table, threaded code, computed goto, superinstruction, register VM, JIT.
  • একটি interpreter-কে কীভাবে test করবেন? Golden output, দ্বিতীয় বাস্তবায়নের সঙ্গে differential testing, এলোমেলো program; ভাগ করা অংশের জন্য স্বাধীন oracle.

৮ · AI-এর যুগে VM লেখা

“একটি bytecode VM লিখে দাও” AI assistant খুব দ্রুত করে, আর কোডটি প্রায়ই চলেও। সমস্যা হলো ছোট ছোট নিয়ম, যেগুলো সাধারণ উদাহরণে ধরা পড়ে না:

AI-এর ভুলকীভাবে ধরবেন
Binary নির্দেশে operand উল্টো: a, b = pop(), pop(), ফলে 7 - 10 = 3বিয়োগ, ভাগ আর <-এর জন্য অসমমিত test; reference-এর সঙ্গে random expression-এর differential test
Python-এর // আর % সরাসরি ব্যবহার, ফলে -7 / 2 = −4ঋণাত্মক সংখ্যার test; spec-এ “শূন্যের দিকে কাটা” নিয়ম মিলিয়ে দেখা
CALL-এ callee আগে pop করা (callee আসলে argument-এর নিচে)dis পড়ে stack-এর ক্রম মেলানো; দুই argument-এর ডাকে চালানো
Closure-এ cell-এর বদলে মান কপি করা, ফলে দুটি closure একই variable ভাগ করে নাreference-এর counter.haat (112, 112) চালিয়ে দেখা
Runtime error-এ ভুল position, বা error-এর আগের আউটপুট হারানোerr_divzero.haat-এর golden আউটপুটের সঙ্গে হুবহু তুলনা
“computed goto সবসময় ২০% দ্রুত” ধরনের নিশ্চিত সংখ্যানিজের যন্ত্রে, নির্দিষ্ট version-এ মাপা; সংখ্যার সঙ্গে যন্ত্র আর compiler লেখা

AI-কে ভালোভাবে কাজে লাগাতে spec, opcode-এর তালিকা আর যাচাইয়ের উপায় একসঙ্গে দিন:

আমি Haat নামের একটি ছোট ভাষার stack VM Python 3.14-এ লিখছি। opcode-এর তালিকা আর প্রতিটির stack effect নিচে দিলাম (CONST k, LOAD_LOCAL s, ..., CALL n, RETURN). নিয়ম: binary নির্দেশে ওপরের মান ডান operand; / আর % C-র মতো শূন্যের দিকে কাটে; Int ৬৪-বিটে wrap করে; CALL-এর আগে stack-এ নিচে callee, ওপরে n-টি argument. ১. CALL আর RETURN-এর handler লেখো, আর প্রতিটি লাইনের পাশে stack-এর অবস্থা মন্তব্যে লেখো। ২. আমার handler-এর সঙ্গে তুলনা করার জন্য ১০টি ছোট test program দাও, যেগুলো operand-এর ক্রম, ঋণাত্মক ভাগ, nested call আর দুটি closure-এর ভাগ করা variable ধরবে; প্রতিটির প্রত্যাশিত আউটপুট তুমি কীভাবে হিসাব করলে তা দেখাও। ৩. কোনো performance সংখ্যা বলবে না; বরং আমি নিজে কী মাপব, তা বলো।

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

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

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

প্র ০১Pascal-এর P-code থেকে JVM আর WebAssembly পর্যন্ত বহু নকশাকার stack VM বেছে নিয়েছেন। কেন, আর Lua কেন উল্টো পথে গেল?

Stack VM-এর প্রথম সুবিধা compiler-এর দিকে। Expression-এর AST post-order-এ হাঁটলেই stack code তৈরি হয়: প্রতিটি পাতায় একটি push, প্রতিটি operator-এ একটি নির্দেশ। কোন মান কোন register-এ থাকবে, কোনটি কখন খালি হবে, এসব সিদ্ধান্ত লাগে না। ১৯৭০-এর দশকে Pascal-এর P-code এই সরলতা কাজে লাগায়: একটি ছোট compiler P-code বানায়, আর নতুন কোনো যন্ত্রে Pascal নিতে শুধু একটি ছোট P-code interpreter লিখলেই চলে। UCSD Pascal-এর p-System এই বহনযোগ্যতাকে জনপ্রিয় করে।

দ্বিতীয় সুবিধা আকার। Stack-এর নির্দেশে operand-এর ঠিকানা থাকে না, তাই অনেক নির্দেশ এক byte-এই আঁটে। ১৯৯৫ সালের Java যখন নেটওয়ার্কে কোড পাঠানোর কথা ভাবছিল, ছোট class file গুরুত্বপূর্ণ ছিল। তৃতীয় সুবিধা যাচাই: JVM-এর bytecode verifier প্রতিটি নির্দেশের আগে stack-এ কোন type-এর কয়টি মান আছে তা হিসাব করে নিরাপত্তা নিশ্চিত করে, আর stack-এর গভীরতা স্থির হলে এই হিসাব সহজ। WebAssembly (২০১৭) একই কারণে stack-ভিত্তিক নির্দেশ আর কঠোর validation নিয়েছে, যদিও তার stack-এর ব্যবহার কাঠামোবদ্ধ।

Lua 5.0 উল্টো দিকে যায়, কারণ তার লক্ষ্য ছিল interpreter হিসেবেই যতটা সম্ভব দ্রুত হওয়া, JIT ছাড়া। Register VM-এ local a = b + c একটি নির্দেশ, stack VM-এ চারটি (দুটি load, একটি add, একটি store). প্রতিটি নির্দেশের dispatch খরচ থাকায় নির্দেশ কমানো সরাসরি সময় কমায়। দাম হলো বড় নির্দেশ (Lua-তে ৩২-বিট) আর একটু জটিল compiler. Shi, Gregg, Beatty ও Ertl-এর তুলনামূলক গবেষণা দেখায় register নকশায় চালানো নির্দেশ উল্লেখযোগ্যভাবে কমে, কিন্তু কোডের আকার বাড়ে; মোট লাভ dispatch-এর পদ্ধতি আর কাজের ধরনের ওপর নির্ভর করে।

আরেকটি বিষয়: যে VM-এর পেছনে একটি শক্তিশালী JIT আছে (আধুনিক JVM), সেখানে bytecode-এর ধরন গতির জন্য কম গুরুত্বপূর্ণ, কারণ গরম কোড শেষ পর্যন্ত machine code-এ যায়, আর JIT নিজেই register বণ্টন করে। তখন stack bytecode-এর ছোট আকার আর সহজ যাচাইই বড় কথা।

মূল উপলব্ধি: stack VM compiler, আকার আর যাচাইয়ের দিক থেকে সরল; register VM interpreter-এর গতির জন্য নির্দেশ কমায়। কোনটি “ভালো”, তা নির্ভর করে VM-টি একা চলবে নাকি পেছনে JIT থাকবে, আর কোড কতটা ছোট রাখা জরুরি তার ওপর।

প্র ০২এই পাতার মাপে Python-এ লেখা VM tree-walking interpreter-এর চেয়ে সামান্যই দ্রুত। তাহলে CPython, Ruby (YARV) বা Lua কেন AST ছেড়ে bytecode-এ গেল?

লেখকের যন্ত্রে fib(22)-এ reference-এর VM ০.১৫৮ সেকেন্ড আর tree-walking interpreter ০.১৯৭ সেকেন্ড নিয়েছে: পার্থক্য মোটে ২০%-এর মতো। কারণ দুটিই Python-এ লেখা। VM-এর একটি ADD চালাতে CPython-কে list থেকে tuple পড়তে হয়, string তুলনা করতে হয়, list-এ pop আর append করতে হয়, wrap ডাকতে হয়; tree-walker-এর একটি Binary node-এর খরচও প্রায় একই মাপের। যখন “host” ভাষা নিজেই একটি interpreter, তখন দুই নকশার পার্থক্য host-এর খরচের নিচে চাপা পড়ে।

C-তে লিখলে ছবি বদলায়। Tree-walker-এ প্রতিটি node-এ একটি pointer অনুসরণ (মেমরির এলোমেলো জায়গায়, cache miss-এর ঝুঁকি), node-এর ধরন অনুযায়ী একটি indirect call বা switch, আর recursive function call. Bytecode-এ নির্দেশ একটি ঘন array-তে পাশাপাশি থাকে, যা cache-এর জন্য ভালো; ip বাড়ানো একটি যোগ; আর কোনো recursion নেই, একটি loop. ফলে একটি সরল ADD কয়েকটি যন্ত্র-নির্দেশে নামে। Ruby 1.9-এ (২০০৭ সালের দিকে) AST interpreter ছেড়ে YARV bytecode VM আনা হয়, আর এর বড় কারণ ছিল গতি; CPython প্রথম থেকেই bytecode ব্যবহার করে।

গতি ছাড়াও কারণ আছে। Bytecode একবার বানিয়ে জমা রাখা যায় (CPython-এর .pyc), ফলে পরের বার parse করতে হয় না। Bytecode-এর ওপর profiling, specialization আর JIT সহজ, কারণ প্রতিটি নির্দেশের একটি স্থির index আছে, যেখানে counter বা cache বসানো যায়; CPython 3.11-এর specializing adaptive interpreter ঠিক এটিই করে (PEP 659). আর VM-এর অবস্থা (frames, stack) সাধারণ data, তাই generator, debugger বা stack overflow-এর নিয়ন্ত্রণ সহজ, যেমন Haat VM Python-এর recursion limit-এ আটকায় না।

উল্টো দিকে, কিছু আধুনিক প্রকল্প AST interpreter-কেই দ্রুত করেছে: GraalVM-এর Truffle node-গুলোকে চলতে চলতে বিশেষায়িত করে আর partial evaluation দিয়ে machine code বানায়। তাই “AST মানেই ধীর” কথাটিও পুরো সত্য নয়; বাস্তবায়নের কৌশল নকশার মতোই গুরুত্বপূর্ণ।

মূল উপলব্ধি: bytecode-এর গতির সুবিধা তখনই বড়, যখন VM একটি দ্রুত ভাষায় লেখা; পাশাপাশি জমা রাখা, profiling আর JIT-এর জন্য bytecode একটি সুবিধাজনক মধ্যবর্তী রূপ। নিজের মাপ নিজে নিন, আর সংখ্যাকে যন্ত্র ও version-সহ লিখুন।

প্র ০৩Dispatch-এর খরচ কমাতে switch থেকে threaded code, computed goto আর CPython 3.14-এর tail-call interpreter পর্যন্ত বিবর্তন কেন ঘটল?

একটি bytecode interpreter-এর প্রতিটি নির্দেশে দুটি অংশ: কাজ (যোগ, load) আর dispatch (পরের opcode পড়া আর তার কোডে যাওয়া)। Haat-এর মতো ছোট নির্দেশে কাজ খুব কম, তাই dispatch প্রায়ই সমান বা বেশি সময় নেয়। প্রথম সমাধান C-র switch: compiler ঘন case-এর জন্য একটি jump table বানায়, ফলে প্রতিটি নির্দেশে একটি সীমা-পরীক্ষা, একটি table পড়া আর একটি indirect jump; তারপর loop-এর মাথায় ফেরা।

১৯৭৩ সালে James Bell “threaded code” নামে একটি ধারণা প্রকাশ করেন: প্রোগ্রাম হলো routine-এর ঠিকানার একটি তালিকা, আর প্রতিটি routine শেষে নিজেই পরের ঠিকানায় লাফ দেয়। কেন্দ্রীয় loop নেই, তাই loop-এ ফেরার লাফ বাঁচে। Forth ভাষা এই কৌশলের বিখ্যাত ব্যবহারকারী। C-তে এটি লেখার উপায় GCC-র “labels as values” extension, যা Clang-ও সমর্থন করে: প্রতিটি handler-এর শেষে goto *table[next_opcode]. একে computed goto বলে, আর CPython সমর্থিত compiler-এ build হলে এটি ব্যবহার করে; অন্যথায় সাধারণ switch.

লাভের মূল কারণ branch prediction. একটি কেন্দ্রীয় indirect jump-এর গন্তব্য প্রতিবার আলাদা হতে পারে, তাই পুরোনো predictor প্রায়ই ভুল করত। প্রতিটি handler-এর শেষে আলাদা jump থাকলে প্রতিটির নিজস্ব ইতিহাস থাকে, আর opcode-এর ক্রমের ধরন (যেমন compare-এর পরে প্রায়ই jump) predictor শিখে নিতে পারে। Ertl ও Gregg-এর মতো গবেষকরা ২০০০-এর দশকের শুরুতে এই প্রভাব বিস্তারিত মাপেন। পরে CPU-র indirect predictor অনেক উন্নত হয়েছে, তাই আজকের যন্ত্রে লাভ আগের চেয়ে কম আর যন্ত্রভেদে আলাদা।

CPython 3.14-এর tail-call interpreter একই ভাবনার নতুন রূপ: প্রতিটি opcode একটি ছোট C function, আর প্রতিটি পরেরটিকে tail call দিয়ে ডাকে, যা compiler একটি লাফে নামায়। ছোট function হওয়ায় compiler প্রতিটির register বণ্টন আলাদাভাবে ভালো করতে পারে, যা একটি বিশাল switch-ওয়ালা function-এ কঠিন। এটি এখন opt-in, শুধু Clang 19 বা নতুন compiler-এ x86-64 আর AArch64-এ; release note প্রাথমিক benchmark-এ গড়ে ৩–৫% লাভের কথা বলে।

মূল উপলব্ধি: dispatch-এর প্রতিটি নতুন কৌশল একই লক্ষ্যে: প্রতি নির্দেশে লাফ, ভুল অনুমান আর অপ্রয়োজনীয় কাজ কমানো। কোনটি কতটা লাভ দেবে, তা CPU আর compiler-এর ওপর নির্ভর করে, তাই মাপই শেষ কথা।

প্র ০৪Interp আর VM ৫০০-এ ৫০০ program-এ মিলেছে। এর মানে কি দুটিই নির্ভুল? Differential testing কী প্রমাণ করে আর কী করে না?

Differential testing একটি জিনিস খুব ভালো দেখায়: পরীক্ষিত input-গুলোতে দুটি বাস্তবায়ন একমত। এটি সঠিকতা প্রমাণ নয়, তিনটি কারণে। প্রথমত, পরীক্ষা শুধু সেই program-গুলোর, যেগুলো generator তৈরি করতে পারে। আমাদের generator কখনো string, else if-এর লম্বা শিকল বা গভীর recursion বানায় না; সেখানে কোনো ভুল থাকলে এই ৫০০টি test তা দেখবে না। তাই generator-এর coverage মাপা জরুরি, যেমন আমরা গুনেছি ৪১৩টিতে CALL আর ২৬৯টিতে closure-এর free variable ছিল।

দ্বিতীয়ত, ভাগ করা অংশের ভুল (common-mode error). Haat-এর interp আর VM একই runtime.py ব্যবহার করে, একই lexer, parser, resolver আর type checker-এর পরে চলে। Resolver যদি কোনো নামকে ভুল declaration-এর সঙ্গে জুড়ে দেয়, দুটি back end একই ভুল নামে একই ভুল উত্তর দেবে। নিরাপত্তা-সংবেদনশীল ক্ষেত্রে “N-version programming” নামে স্বাধীন দল দিয়ে একাধিক বাস্তবায়ন লেখার চেষ্টা হয়েছে, কিন্তু গবেষণায় দেখা গেছে স্বাধীন দলও প্রায়ই একই কঠিন জায়গায় একই ধরনের ভুল করে।

তৃতীয়ত, দুটি বাস্তবায়নই spec-এর ভুল ব্যাখ্যা করতে পারে, যেমন দুজনই ভেবে নিল %-এর ফলের চিহ্ন ভাজকের মতো। তাই reference আরও দুটি পাহারা রাখে: হাতে যাচাই করা golden .out ফাইল, আর একটি স্বাধীনভাবে লেখা evaluator, যা অন্য কৌশলে (// দিয়ে ভাগ করে সংশোধন) C-র ভাগ হিসাব করে। এই দুই oracle ভাগ করা ভুলের বিরুদ্ধে রক্ষা দেয়।

বাস্তব জগতে এই পদ্ধতি অত্যন্ত সফল: Csmith নামের tool এলোমেলো C program বানিয়ে বিভিন্ন C compiler-এর আউটপুট মিলিয়ে GCC আর LLVM-এ বহু ভুল খুঁজে পেয়েছে (এর ধারণা পর্ব ৪৪-এ)। কিন্তু সেখানেও সবচেয়ে কঠিন কাজ ছিল এমন program বানানো, যার আচরণ ভাষার নিয়মে সুনির্দিষ্ট; undefined behaviour থাকলে অমিল কোনো ভুল প্রমাণ করে না।

মূল উপলব্ধি: differential testing কম খরচে প্রচুর ভুল ধরে, কিন্তু শুধু অমিল দেখাতে পারে; ভাগ করা অংশ আর spec-এর ভুল ব্যাখ্যার জন্য স্বাধীন oracle, golden file আর যত্নে লেখা test লাগে, আর পূর্ণ নিশ্চয়তার জন্য প্রমাণ (পর্ব ৪৪)।

প্র ০৫Haat VM তার compiler-কে অন্ধভাবে বিশ্বাস করে। কেউ যদি হাতে বানানো ভুল bytecode দেয়? JVM, WebAssembly আর CPython এই প্রশ্নে কী করে?

Haat VM-এ কোনো যাচাই নেই। JUMP 999 থাকলে পরের fetch-এ Python IndexError দেবে; argument-এর আগে callee না থাকলে CALL একটি সংখ্যাকে function ভেবে AttributeError দেবে (অনুশীলন ২-এ ঠিক এটিই ঘটে)। Python নিজে memory-safe, তাই ক্ষতি সীমিত: program একটি Python exception-এ থামে, মেমরি নষ্ট হয় না। কিন্তু একই VM C-তে লেখা হলে ভুল index মেমরির যেকোনো জায়গা পড়তে বা লিখতে পারত, যা নিরাপত্তার গুরুতর ঝুঁকি।

JVM এই সমস্যার জন্য নকশা থেকেই প্রস্তুত, কারণ সে নেটওয়ার্ক থেকে আসা অবিশ্বস্ত কোড চালানোর কথা ভেবেছিল। Class load করার সময় bytecode verifier পরীক্ষা করে: প্রতিটি jump বৈধ নির্দেশে যায়, কোনো পথে stack underflow বা overflow হয় না, প্রতিটি নির্দেশ ঠিক type-এর মান পায় (যেমন int-এর জায়গায় reference নয়)। Java 6-এ আসা আর Java 7-এর class file-এ বাধ্যতামূলক StackMapTable নামের অংশে compiler প্রতিটি শাখা-বিন্দুর type-এর তথ্য লিখে দেয়, যাতে verifier একবার হেঁটেই যাচাই শেষ করতে পারে। WebAssembly-ও চালানোর আগে পুরো module validate করে, আর তার কাঠামোবদ্ধ control flow (block, loop, br) এই কাজ সহজ রাখে।

CPython অন্য পথে। তার bytecode অবিশ্বস্ত উৎস থেকে চালানোর জন্য নকশা করা নয়: হাতে বানানো code object দিয়ে interpreter crash করানো সম্ভব, আর এ নিয়ে CPython-এর অবস্থান হলো এটি নিরাপত্তার সীমা নয়। সে কারণেই অবিশ্বস্ত .pyc ফাইল বা marshal data চালানো নিরাপদ নয়। নিরাপত্তার সীমা টানতে হয় অন্যত্র: process-এর বিচ্ছিন্নতা বা sandbox দিয়ে।

Haat-এর জন্য যুক্তিসংগত মাঝামাঝি পথ: compiler-এর আউটপুট VM সরাসরি চালাক, কিন্তু অন্য উৎসের bytecode load করার আগে একটি ছোট verifier চালাক, যা পর্ব ৫৮-এর stack-effect checker-এর মতো প্রতিটি পথে stack-এর গভীরতা হিসাব করে, jump-এর লক্ষ্য সীমার মধ্যে কি না আর CONST/LOAD_LOCAL-এর index বৈধ কি না দেখে।

মূল উপলব্ধি: VM যে bytecode চালায় তাকে কতটা বিশ্বাস করবে, এটি একটি নকশার সিদ্ধান্ত। অবিশ্বস্ত কোড চালাতে হলে (JVM, WebAssembly) load-এর সময় যাচাই বাধ্যতামূলক; নিজের compiler-এর আউটপুট চালালে (CPython, Haat) যাচাই বাদ দিয়ে গতি পাওয়া যায়, কিন্তু তখন bytecode-কে বাইরের input হিসেবে গ্রহণ করা চলে না।

অনুশীলন

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

  1. নকশা ও বাস্তবায়ন — নির্দেশের সীমা (fuel): বাজারঘরের ওয়েবসাইটে দোকানদাররা নিজেদের ছাড়ের নিয়ম Haat-এ লিখে চালাবেন। কেউ ভুল করে while true { … } লিখলে server আটকে যাবে। এই পাতার VM-কে বাড়িয়ে একটি FuelVM লিখুন, যা সর্বোচ্চ fuel-টি নির্দেশ চালায়, তারপর <line>:<col>: runtime error: instruction limit exceeded দেয়। কোন position দেখানো উচিত, আর bazar.haat-এর জন্য সবচেয়ে কম কত fuel লাগে?
    class FuelVM(VM):                            # প্রতি run-এ সর্বোচ্চ কতটি নির্দেশ
        def __init__(self, main, out=print, fuel=10_000):
            super().__init__(main, out); self.fuel = fuel
        def run(self):
            while self.frames:
                f = self.frames[-1]
                name, arg = f.code.instrs[f.ip]
                self.pos = f.code.positions[f.ip]; f.ip += 1
                self.fuel -= 1
                if self.fuel < 0: self.fail("instruction limit exceeded")
                self.table.get(name, self.op_ARITH)(f, arg, name)

    সত্যিকারের run (লেখকের CPython 3.14.4, এই পাতার VM-এর ওপর): print("শুরু"); var n = 0; while true { n = n + 1; } (চার লাইনে লেখা) দেয় শুরু, তারপর 3:7: runtime error: instruction limit exceeded: যে নির্দেশে জ্বালানি ফুরাল, সেটি while-এর শর্ত true-এর CONST. bazar.haat fuel=120-এ পুরো চলে (996, 5000, 3), আর fuel=119-এ তিনটি লাইন ছাপার পরে শেষ RETURN-এ থামে (16:1), কারণ পুরো program ঠিক ১২০টি নির্দেশ। নকশার দুটি সিদ্ধান্ত: fuel নির্দেশ গোনে, সময় নয়, তাই ফল যন্ত্রভেদে একই (deterministic); আর error-টি সাধারণ runtime error, তাই আগের আউটপুট থাকে (সিদ্ধান্ত ২৬)। এটি Haat-এর বর্ধিত রূপ, reference-এ নেই।

  2. ভুল খুঁজুন: একজন সহকর্মী op_CALL “পরিষ্কার” করতে লিখলেন: প্রথমে callee = self.stack.pop(), তারপর ওপরের n-টি argument কেটে নেওয়া, তারপর Frame(callee, args). bazar.haat চালালে কী হবে? ঠিক কোন মানটি callee হিসেবে নেওয়া হলো?

    সত্যিকারের run: program একটি লাইনও ছাপে না, থামে Python-এর AttributeError: 'int' object has no attribute 'code'-এ। প্রথম ডাক price(2, 520)-এ CALL 2-এর সময় stack [fn price, 2, 520]. Stack-এর চূড়ায় callee নয়, শেষ argument: তাই pop() দেয় 520. তারপর argument হিসেবে কাটা হয় [fn price, 2], আর Frame(520, …) 520-এর .code খুঁজতে গিয়ে ভাঙে। নিয়ম: compiler callee-কে argument-এর আগে মূল্যায়ন করে (সিদ্ধান্ত ১২), তাই সে stack-এ argument-এর নিচে; আগে argument কাটতে হবে, তারপর callee. এই ভুল কোনো type error হিসেবে আগে ধরা পড়ে না, কারণ VM bytecode যাচাই করে না (প্র ০৫)।

  3. হিসাব ও trace: print(-7 / 2 * 2 + -7 % 2);-এর bytecode লিখুন (constant-এর index-সহ), প্রতিটি নির্দেশের পরে operand stack দেখান, আর আউটপুট বলুন। Stack-এর সর্বোচ্চ গভীরতা কত?
     0  CONST  0 ; 7    [7]
     1  NEG             [-7]
     2  CONST  1 ; 2    [-7, 2]
     3  DIV             [-3]          -7 / 2 শূন্যের দিকে: -3
     4  CONST  1 ; 2    [-3, 2]
     5  MUL             [-6]
     6  CONST  0 ; 7    [-6, 7]
     7  NEG             [-6, -7]
     8  CONST  1 ; 2    [-6, -7, 2]
     9  MOD             [-6, -1]      ভাগশেষের চিহ্ন ভাজ্যের মতো
    10  ADD             [-7]
    11  PRINT           [ ]           ছাপে -7
    12  CONST  2 ; ()
    13  RETURN

    Listing reference-এর haat.py dis-এর সঙ্গে হুবহু এক, আর haat.py vm ছাপে -7. -7 একটি literal নয়: lexer শুধু 7 চেনে, আর unary - হয় NEG (spec: সংখ্যার আগে চিহ্ন থাকে না)। Unary --এর binding power বেশি, তাই -7 / 2 মানে (-7) / 2. 7 আর 2 দুবার এলেও constant দুটিই একবার জমা (index 0 আর 1). সর্বোচ্চ গভীরতা 3, ৮ নম্বর নির্দেশের পরে। Python-এর // আর % দিয়ে হিসাব করলে (−4) × 2 + 1 = −7, কাকতালীয়ভাবে একই উত্তর; তাই এই একটি উদাহরণ দিয়ে C আর Python-এর ভাগ আলাদা করা যায় না। আলাদা করতে print(-7 / 2); চালান: Haat −3, Python-এর // −4.

  4. আউটপুট আর গণনা অনুমান করুন: নিচের program কী ছাপবে, আর Haat VM মোট কয়টি নির্দেশ চালাবে? (সংকেত: n < 2 শাখায় কয়টি নির্দেশ, অন্য শাখায় কয়টি, আর কয়টি ডাক কোন শাখায় যায়?)
    fn fib(n: Int) -> Int { if n < 2 { return n; } return fib(n - 1) + fib(n - 2); }
    print(fib(10));

    আউটপুট 55. fib-এর bytecode: LOAD_LOCAL 0; CONST 0; LT; JUMP_IF_FALSE 6; LOAD_LOCAL 0; RETURN, তারপর 6 থেকে LOAD_GLOBAL 0; LOAD_LOCAL 0; CONST 1; SUB; CALL 1; LOAD_GLOBAL 0; LOAD_LOCAL 0; CONST 2; SUB; CALL 1; ADD; RETURN. তাই n < 2 ডাকে ৬টি নির্দেশ, বাকি ডাকে ৪ + ১২ = ১৬টি। fib(10)-এ মোট ডাক ১৭৭টি; তার মধ্যে পাতা (n = 0 বা 1) ৮৯টি, ভেতরের ডাক ৮৮টি (একটি binary গাছে পাতা = ভেতরের node + ১)। মোট = ৮৯ × ৬ + ৮৮ × ১৬ + main-এর ৮ (MAKE_CLOSURE, DEFINE_GLOBAL, LOAD_GLOBAL, CONST, CALL, PRINT, CONST, RETURN) = ৫৩৪ + ১৪০৮ + ৮ = ১৯৫০। অংশ ৬-এর profiler দিয়ে সত্যিকারের run-এ ঠিক এই সংখ্যা এসেছে: মোট 1950, CALL 177, fib-এর ভেতরে 1942. সাধারণ সূত্র: fib(k)-এ ডাক 2·F(k+1) − 1, যেখানে F ফিবোনাচ্চি সংখ্যা।

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

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

ক্রমHaat-এর stack VM যখন CALL 2 নির্দেশটি পায় (stack-এ নিচে callee, ওপরে দুটি argument), ঘটনাগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. Fetch: চলমান frame-এর ip থেকে CALL 2 আর তার position পড়া
  2. Caller-এর ip এক ঘর বাড়ানো, যা পরে ফেরার জায়গা হবে
  3. Frame-এর সংখ্যা ১০০০ পার হয়েছে কি না দেখা
  4. Stack-এর ওপরের দুটি মান argument হিসেবে কেটে নেওয়া
  5. এর নিচের callee closure-টি stack থেকে নামানো
  6. নতুন frame বানিয়ে তালিকায় যোগ করা; পরের fetch তার ip 0 থেকে

একটি stack VM-এ CONST 8; CONST 3; SUB চলল (CONST মান push করে, SUB ওপরের দুটি pop করে ফল push করে)। আগে আসা মান বাঁ operand ধরলে, SUB-এর পরে stack-এর চূড়ায় কী?

  • −5
  • 3
  • 5
  • 8

Haat VM-এ CALL n-এর ঠিক আগে operand stack-এ কী থাকে, নিচ থেকে ওপরে?

  • n-টি argument, তারপর চূড়ায় callee
  • callee, তারপর প্রথম থেকে শেষ argument, শেষটি চূড়ায়
  • callee, তারপর শেষ থেকে প্রথম argument
  • একটি খালি frame, তারপর argument

একটি bytecode VM print(10 / (5 - 5)); চালাতে গিয়ে বলে 1:10: runtime error: division by zero. VM এই 1:10 কোথা থেকে জানল?

  • Error-এর সময় source আবার parse করে
  • Operand stack-এ রাখা একটি বিশেষ মান থেকে
  • ip-এর মানই লাইন নম্বর
  • প্রতিটি নির্দেশের পাশে compiler-এর লেখা positions তালিকা থেকে

দুটি closure একটি বাইরের var ভাগ করে, আর একটি সেটি বদলালে অন্যটি নতুন মান দেখে। Haat-এর মতো cell-ভিত্তিক VM-এ MAKE_CLOSURE আসলে কী কপি করে?

  • মানটি যে cell-এ আছে, সেই cell-এর reference
  • Variable-এর সেই মুহূর্তের মান
  • বাইরের function-এর পুরো frame-এর একটি কপি
  • সব global variable-এর তালিকা

একটি C-তে লেখা interpreter-এ কেন্দ্রীয় switch-এর বদলে প্রতিটি opcode-handler-এর শেষে goto *table[next_op] (computed goto) লেখা হলো। গতির মূল সম্ভাব্য কারণ কোনটি?

  • নির্দেশের সংখ্যা কমে যায়
  • VM register-ভিত্তিক হয়ে যায়
  • Indirect jump ছড়িয়ে যাওয়ায় branch prediction ভালো হয় আর কেন্দ্রীয় loop-এ ফেরা লাগে না
  • Bytecode machine code-এ compile হয়ে যায়

একটি ভাষার tree-walking interpreter আর bytecode VM দুটিই একই runtime module-এর ভাগ আর ভাগশেষের function ব্যবহার করে। এক হাজার এলোমেলো program-এ দুটির আউটপুট হুবহু মিলল। কোন ধরনের ভুল এই পরীক্ষায় সবচেয়ে কম ধরা পড়ার কথা?

  • VM-এর compiler-এ loop-এর jump-এর ভুল লক্ষ্য
  • ভাগ করা runtime-এর ভাগের function-এ ভুল
  • VM-এ বিয়োগের operand উল্টো
  • VM-এর closure-এ cell-এর বদলে মান কপি

Haat VM-এ fib(n)-এর n < 2 শাখায় ৬টি আর অন্য শাখায় ১৬টি নির্দেশ চলে, আর top level-এ ৮টি। fib(4) চালাতে মোট কয়টি নির্দেশ? (fib(4)-এ মোট ৯টি ডাক, তার ৫টি n < 2)

  • ১০২
  • ৯৪
  • ১৫২
  • ১১২

শব্দকোষ

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

মনে রাখুন

  1. VM-এর loop: fetch (নির্দেশ আর position), ip বাড়ানো, decode, execute; frame-এর তালিকা খালি হলে থামা।
  2. অবস্থা: একটি ভাগ করা operand stack, প্রতিটি ডাকের frame (closure, ip, slots), global-এর তালিকা (না-চলা let = UNSET), আর ধরা variable-এর cell.
  3. CALL n আর RETURN: argument কেটে নিচের callee সরানো, নতুন frame; RETURN শুধু frame সরায়, ফল stack-এ থাকে। ১০০০-এর বেশি frame হলে stack overflow.
  4. খরচ: নির্দেশ গুনুন (bazar ১২০, fib(15) ২১৭০৬); dispatch-এর কৌশল: switch, table, threaded code, computed goto, tail call; Python-এ host-এর খরচই প্রধান।
  5. যাচাই: golden file, interp বনাম VM-এর differential testing আর স্বাধীন oracle; এই পাতার VM ১০টি উদাহরণ আর ৫০০টি এলোমেলো program-এ reference-এর সঙ্গে হুবহু মিলেছে।

পরের পর্বে: পর্ব ৬০ (বাস্তব virtual machine — CPython bytecode আর JVM). আপনার Haat VM-এর পাশে রেখে দেখবেন CPython 3.14 আর JVM একই ধারণা কীভাবে বাস্তবায়ন করে: dis আর javap -c-এর সত্যিকারের আউটপুট, constant pool, আর চলতে চলতে নিজেকে বিশেষায়িত করা interpreter.

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

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