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

Bytecode নকশা — instruction set আর compiler থেকে bytecode

Bytecode Design — Instruction Sets and Compiling to Bytecode

Taught in Bangla, this lesson explains why compilers flatten an AST into bytecode and weighs stack against register instruction sets. It reads the Haat reference's Code object, its 31 opcodes and their stack effects, then writes a compiler in in-page Python (Pyodide) for expressions, statements with jumps, globals, functions and closures whose disassembly matches the reference. It computes maximum stack depth to catch bad bytecode and compares encoding, constant pools and superinstructions with real CPython 3.14.

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

  • Bytecode কেন, আর stack ও register instruction set-এর আপস কোথায়
  • Haat reference-এর Code object, ৩১টি opcode আর তাদের stack effect, আর disassembler-এর listing পড়া
  • Expression, statement, global, function আর closure compile করা: নিজের হাতে একটি compiler লেখা, যার dis reference-এর সঙ্গে হুবহু মেলে
  • Stack effect দিয়ে সর্বোচ্চ stack গভীরতা হিসাব আর ভুল bytecode ধরা
  • Encoding, constant pool, immediate operand আর superinstruction-এর মতো নকশার সিদ্ধান্ত, সত্যিকারের CPython ৩.১৪-এর সঙ্গে তুলনা করে

১ · কেন bytecode — গাছ থেকে নির্দেশের সারি

পুরান ঢাকার একটি রেস্তোরাঁর কথা ভাবুন। টেবিলে বসে অতিথি গল্পের মতো করে অর্ডার দেন: “দুটো পরোটা, তার সঙ্গে একটা ডিম ভাজি, ভাজিটা কম ঝাল; আর আগে চা দেবেন।” ওয়েটার যদি প্রতিবার রান্নাঘরে গিয়ে পুরো গল্পটা আবার বিশ্লেষণ করতেন, সময় নষ্ট হতো। তাই তিনি একবারেই একটি স্লিপ লেখেন: ১. চা, ২. পরোটা ×২, ৩. ডিম ভাজি (কম ঝাল)। রাঁধুনি শুধু স্লিপের লাইন ধরে ধরে কাজ করেন। গল্পটি হলো AST, স্লিপটি bytecode, আর রাঁধুনি virtual machine.

পর্ব ৫৬-এ (Tree-walking interpreter) Haat চালানো হয়েছে সরাসরি AST ঘুরে: প্রতিটি node-এ গিয়ে তার ধরন দেখা, সন্তানদের মান আনা, তারপর হিসাব। এই tree-walking interpreter বানানো সহজ, কিন্তু একটি loop হাজারবার ঘুরলে একই গাছও হাজারবার ঘোরা হয়, আর প্রতিবার নামের মানে খুঁজতে হয়। Bytecode সেই কাজের বড় অংশ একবারই সেরে রাখে:

  1. ছোট: গাছের প্রতিটি node একটি object, তাতে সন্তানদের pointer, position আর নাম। Bytecode-এ একই অর্থ কয়েকটি ছোট নির্দেশে; নামের বদলে নম্বর (slot).
  2. দ্রুত: নাম কোথায় থাকে (global, local, cell), লাফ কোথায় যাবে, সব compile-এর সময়েই ঠিক। চলার সময় VM শুধু একটি সংখ্যা দেখে কাজ বাছে। কতটা দ্রুত, তা ভাষা আর বাস্তবায়নের ওপর নির্ভর করে; Haat-এর দুই back end-এর মাপ পর্ব ৫৯-এ (Stack-based virtual machine) সত্যিকারের run দিয়ে দেখবেন।
  3. বহনযোগ্য: bytecode কোনো CPU-র নিজস্ব machine code নয়। যে যন্ত্রে VM আছে, সেখানেই একই bytecode চলে। Java-র class file এই portability-র সবচেয়ে পরিচিত উদাহরণ।

এই পর্বের প্রশ্ন: স্লিপের ভাষাটি কেমন হবে, আর ওয়েটার, অর্থাৎ compiler, গল্প থেকে স্লিপ লিখবেন কীভাবে? সেই ভাষার নির্দেশের পুরো তালিকাকে বলে instruction set, আর প্রতিটি নির্দেশের নামকে opcode. Haat reference বাস্তবায়নের তিনটি ফাইল এখানে মূল: compiler.py (AST থেকে bytecode), disasm.py (bytecode থেকে পড়ার মতো listing) আর vm.py (চালানো, পর্ব ৫৯-এর বিষয়)। Bytecode-এর প্রথম ঝলক দেখেছিলেন পর্ব ০১-এ, আর CPython ও Java কীভাবে এই পথ নেয় তা পর্ব ০৪-এ।

ছবি ৫৮.১ — একটি লাইন থেকে একটি Code object

bazar.haat-এর price, reference-এর সত্যিকারের compile থেকে

Compiling one Haat line into the price Code object: header fields, local names, constant pool, instructions with their source positions return p - p / 10; FnCompiler · post-order Code: price arity 2 · nlocals 3 local_names: qty unit p consts: [0] 1000 [1] 10 instrs positions 8 LOAD_LOCAL 24:27 9 LOAD_LOCAL 24:31 10 CONST 14:35 11 DIV4:33 12 SUB4:29 13 RETURN4:20 VM চালায় (পর্ব ৫৯)
ছবি ৫৮.১ — Haat compiler প্রতিটি function-এর জন্য একটি Code object বানায়। ওপরের অংশে মাথার তথ্য (কয়টি argument, কয়টি local ঘর, নামগুলো), তারপর ধ্রুবকের তালিকা, তারপর নির্দেশ। প্রতিটি নির্দেশের পাশে source-এর একটি position: DIV-এর পাশে 4:33, ঠিক / চিহ্নের ঘর, যাতে শূন্য দিয়ে ভাগ হলে VM সঠিক লাইন আর কলাম বলতে পারে। পুরো price-এর ১৬টি নির্দেশের মধ্যে এখানে শুধু 8–13.

২ · Stack না register — instruction set-এর প্রথম সিদ্ধান্ত

স্লিপের ভাষা বানানোর প্রথম প্রশ্ন: নির্দেশের মাঝের ফল কোথায় থাকবে? দুটি বড় পথ আছে। Stack machine-এ নির্দেশ operand-এর নাম বলে না; সে operand stack-এর ওপর থেকে মান তোলে আর ফল আবার ওপরে রাখে, যেমন রান্নাঘরে থালার স্তূপ। Register VM-এ প্রতিটি নির্দেশ নিজেই বলে কোন ঘর থেকে পড়বে আর কোন ঘরে লিখবে, অনেকটা three-address code-এর মতো। price-এর p - p / 10 দুই রূপে (p আছে ঘর ২-এ):

Stack রূপ (Haat-এর সত্যিকারের dis)Register রূপ (তুলনার জন্য কল্পিত)
LOAD_LOCAL 2
LOAD_LOCAL 2
CONST 1
DIV
SUB
RETURN
DIV r3, r2, K1
SUB r3, r2, r3
RETURN r3
৬টি নির্দেশ; প্রতিটি ছোট (বেশির ভাগে একটি বা শূন্য argument)৩টি নির্দেশ; প্রতিটিতে তিনটি ঘরের নম্বর, তাই প্রতিটি বড়
Compiler সহজ: গাছ post-order-এ ঘুরলেই কোডCompiler-কে মাঝের ফলের জন্য ঘর বাছতে হয় (register allocation-এর ছোট রূপ)

ডান দিকের রূপটি কোনো সত্যিকারের VM-এর আউটপুট নয়; শুধু ধারণা দেখাতে Lua-ধাঁচে লেখা (K1 মানে ধ্রুবক ১)। বাস্তবে দুই পথই চলছে। Stack-ভিত্তিক: JVM, CPython, .NET-এর CIL, WebAssembly আর Haat. Register-ভিত্তিক: Lua ৫.০ (২০০৩) থেকে Lua-র VM, আর Android-এর পুরোনো Dalvik VM. Lua-র নকশাকারেরা (Ierusalimschy, de Figueiredo, Celes) “The Implementation of Lua 5.0” প্রবন্ধে কারণ দেখিয়েছেন: interpreter-এ প্রতিটি নির্দেশ পড়া আর বাছার (dispatch) একটি নির্দিষ্ট খরচ আছে, তাই নির্দেশ কম হলে loop কম ঘোরে।

সংখ্যায় কতটা? Shi, Gregg, Beatty আর Ertl-এর “Virtual Machine Showdown: Stack Versus Registers” (VEE ২০০৫, পরে ACM TACO ২০০৮) JVM-এর stack কোডকে register কোডে অনুবাদ করে মেপেছিলেন: তাঁদের পরীক্ষায় চলা নির্দেশ গড়ে প্রায় ৪৭% কমেছিল, আর কোডের আকার প্রায় ২৫% বেড়েছিল; এগুলো VEE ২০০৫-এর সংখ্যা, পরিমার্জিত TACO ২০০৮ সংস্করণে দেখানো হয়েছে প্রায় ৪৬% কম চলা নির্দেশ আর ২৬% বড় কোড। সময়ের লাভ dispatch-এর পদ্ধতির ওপর নির্ভর করে, আর এই সংখ্যাগুলো তাঁদের benchmark আর যন্ত্রের, সব ভাষার জন্য নিয়ম নয়। Haat stack বেছে নিয়েছে শেখার সুবিধার জন্য: compiler সবচেয়ে সরল, আর ঘর বাছার কঠিন সমস্যাটি (register allocation) আসবে পর্ব ৭০-এ, সত্যিকারের CPU-র জন্য। Hardware-এর দিক থেকে stack, accumulator আর load-store ISA-র তুলনা কম্পিউটার আর্কিটেকচার কোর্সের পর্ব ২৫-এ।

৩ · Haat-এর Code object আর ৩১টি opcode

Haat reference-এ প্রতিটি function (আর পুরো program-এর জন্য <main>) একটি Code object হয়। এর ঘরগুলো README-এর “Bytecode” অংশে তালিকা করা:

ঘরকী থাকেprice-এ
name, arityনাম আর কয়টি parameter (arity)price, 2
nlocalsframe-এ কয়টি local ঘর; parameter আসে 0 থেকে arity−1-এ3 (qty, unit, p)
instrs(opcode, arg) জোড়ার তালিকা১৬টি
positionsপ্রতিটি নির্দেশের source-এর (line, col)১৬টি
constsধ্রুবক আর ভেতরের function-এর Code[1000, 10]
local_names, free_namesশুধু disassembler-এর মন্তব্যের জন্য নামqty unit p, —
capturesMAKE_CLOSURE parent-এর কোন ঘর থেকে cell নেবে—

ধ্রুবকের তালিকাটির নাম constant pool: নির্দেশ নিজে মান বহন করে না, শুধু তালিকার index বলে (CONST 1 মানে “consts[1]-এর মান stack-এ তোলা”)। একই মান দুবার লাগলে একই index. নিচের টেবিলে Haat-এর ৩১টি opcode, পরিবার ধরে সাজানো। “Stack effect” কলাম বলে নির্দেশটি stack-এর উচ্চতা কতটা বদলায়; অংশ ৭-এ এটিই যাচাইয়ের ভিত্তি।

OpcodeargStack আগে → পরেEffect
CONSTk→ consts[k]+1
LOAD_LOCAL LOAD_CELLs→ slot s-এর মান (cell হলে বাক্সের ভেতরের মান)+1
STORE_LOCAL STORE_CELLsv →−1
MAKE_CELLsv → (slot s = নতুন Cell(v))−1
LOAD_FREE / STORE_FREEiclosure-এর ধরা cell i থেকে পড়া / তাতে লেখা+1 / −1
DEFINE_GLOBAL STORE_GLOBALgv →−1
LOAD_GLOBALg→ global g+1
ADD SUB MUL DIV MOD–a b → r−1
EQ NE LT LE GT GE–a b → Bool−1
NEG NOT–a → r0
JUMPt– (পরের নির্দেশ t)0
JUMP_IF_FALSEtc → (মিথ্যা হলে t)−1
MAKE_CLOSUREk→ closure(consts[k], ধরা cell)+1
CALLnf a1 … an → r−n
RETURN–v → (frame শেষ, v থাকে caller-এর জন্য)−1
PRINT POP–v →−1

তিনটি জিনিস খেয়াল করুন। এক, opcode-এ কোনো type নেই: ADD দুটি Int যোগ করে, দুটি Str জোড়াও দেয়। Type checker (পর্ব ৫২) আগেই নিশ্চিত করেছে যে ভুল জোড়া আসবে না, তাই VM-কে আর জিজ্ঞেস করতে হয় না। দুই, && আর ||-এর কোনো opcode নেই; এরা লাফ দিয়ে তৈরি (অংশ ৫)। তিন, reference-এর সিদ্ধান্ত ২৮: listing-এর বাঁ দিকের সংখ্যা নির্দেশের index, byte-এর ঠিকানা নয়, আর লাফের argument-ও সেই index. Haat-এর নির্দেশ Python-এর tuple, তাই byte-এর হিসাব আসলে নেই; সত্যিকারের byte-এ লেখার প্রশ্ন অংশ ৮-এ।

এই পাতার Python ব্লকগুলো দুটি সহায়ক module import করে। haat_front.py-তে compiler-এর আগের সব ধাপ: পর্ব ৪৬–৪৯-এর lexer, AST আর parser, আর পর্ব ৫১-এর resolver, এবার slot নম্বরসহ, সঙ্গে type checker-এর always_returns. haat_code.py-তে Code class আর disassembler, reference-এর disasm.py-র হুবহু format. সহায়ক parser প্রথম ভুলে থামে, আর type check এখানে নেই, কারণ এই পর্বের program-গুলো আগেই reference-এর check-এ ok.

সহায়ক module haat_front.py দেখুন (ব্লকগুলো এটি import করে)
# haat_front.py — সহায়ক অংশ: compiler-এর আগের সব ধাপ, সংক্ষেপে।
# Reference-এর errors.py, tokens.py + lexer.py (পর্ব ৪৬), ast_nodes.py (পর্ব ৪৯), parser.py (পর্ব ৪৭–৪৮),
# resolver.py (পর্ব ৫১, এবার slot-সহ) আর typechecker.py-র always_returns; নাম আর বার্তা reference-এর মতো।
# পার্থক্য: lexer আর parser প্রথম error-এ থামে, আর type check এখানে নেই (পর্ব ৫২)।
import re
from dataclasses import dataclass, field, make_dataclass

class HaatError(Exception):                    # errors.py
    def __init__(self, line, col, message):
        super().__init__(message); self.line, self.col, self.message = line, col, message
    def __str__(self): return f"{self.line}:{self.col}: error: {self.message}"

class HaatErrors(Exception):                   # all errors of one phase, sorted by position
    def __init__(self, errors):
        self.errors = sorted(errors, key=lambda e: (e.line, e.col))
        super().__init__("\n".join(str(e) for e in self.errors))

@dataclass(frozen=True)
class Token:
    kind: str; text: str; line: int; col: int

KW = "let var fn if else while return true false print".split()
OPS = dict(zip("== != <= >= && || -> + - * / % < > ! = ( ) { } , ; :".split(),
    "EQ_EQ BANG_EQ LT_EQ GT_EQ AND_AND OR_OR ARROW PLUS MINUS STAR SLASH PERCENT LT GT "
    "BANG EQ LPAREN RPAREN LBRACE RBRACE COMMA SEMI COLON".split()))
SPEC = (r'(?P<skip>//[^\n]*|[ \t\r\n]+)|(?P<IDENT>[A-Za-z_][A-Za-z0-9_]*)|(?P<INT>[0-9]+)'
        r'|(?P<STRING>"(?:\\["\\n]|[^"\\\n])*")|(?P<op>==|!=|<=|>=|&&|\|\||->|[-+*/%<>!=(){},;:])|(?P<bad>.)')

def tokenize(src):                             # lexer stand-in: the first lexical error stops it
    toks = []
    for m in re.finditer(SPEC, src):
        g, t, at = m.lastgroup, m[0], m.start()
        line, col = src.count("\n", 0, at) + 1, at - src.rfind("\n", 0, at)
        if g == "bad":
            raise HaatError(line, col, "unterminated string literal" if t == '"' else f"unexpected character '{t}'")
        if g == "skip": continue
        kind = OPS[t] if g == "op" else t.upper() if g == "IDENT" and t in KW else g
        toks.append(Token(kind, t, line, col))
    return toks + [Token("EOF", "", src.count("\n") + 1, len(src) - src.rfind("\n"))]

NODES = {"Num": "value", "Str": "value", "Bool": "value", "Var": "name", "Unary": "op operand",
         "Binary": "op left right", "Call": "callee args", "Param": "name type",
         "Lambda": "params ret body", "Let": "name mutable type init", "Assign": "name value",
         "If": "cond then else_", "While": "cond body", "Return": "value", "Print": "value",
         "ExprStmt": "expr", "Block": "stmts", "FnDecl": "name params ret body"}
for _name, _fields in NODES.items():           # ast_nodes.py: same names and fields; line, col last
    globals()[_name] = make_dataclass(_name, _fields.split() + ["line", "col"], eq=False)
Program = make_dataclass("Program", ["stmts"], eq=False)
TypeName = make_dataclass("TypeName", ["name"], frozen=True, namespace={"__str__": lambda s: s.name})
FnType = make_dataclass("FnType", ["params", "ret"], frozen=True, namespace={
    "__str__": lambda s: "(" + ", ".join(map(str, s.params)) + ") -> " + str(s.ret)})
INT, BOOL, STR, UNIT = (TypeName(n) for n in ("Int", "Bool", "Str", "Unit"))

def start(e):                                  # where an expression begins (for error positions)
    while isinstance(e, (Binary, Call)): e = e.left if isinstance(e, Binary) else e.callee
    return e.line, e.col

INFIX = {"OR_OR": 10, "AND_AND": 20, "EQ_EQ": 30, "BANG_EQ": 30, "LT": 40, "LT_EQ": 40,
         "GT": 40, "GT_EQ": 40, "PLUS": 50, "MINUS": 50, "STAR": 60, "SLASH": 60, "PERCENT": 60}

class Parser:                                  # parser.py: recursive descent + Pratt
    def __init__(self, tokens): self.toks, self.pos = tokens, 0
    def peek(self, ahead=0): return self.toks[min(self.pos + ahead, len(self.toks) - 1)]
    def check(self, kind): return self.peek().kind == kind
    def advance(self):
        tok = self.peek()
        if tok.kind != "EOF": self.pos += 1
        return tok
    def match(self, kind): return self.advance() if self.check(kind) else None
    def expect(self, kind, message):
        if self.check(kind): return self.advance()
        if kind == "SEMI" and self.pos > 0:
            prev = self.toks[self.pos - 1]; self.fail(message, (prev.line, prev.col + len(prev.text)))
        self.fail(message)
    def fail(self, message, where=None):
        line, col = where or (self.peek().line, self.peek().col)
        raise HaatError(line, col, message)
    def statements_until(self, end):
        stmts = []
        while not self.check(end) and not self.check("EOF"): stmts.append(self.statement())
        return stmts
    def statement(self):
        kind = self.peek().kind
        if kind in ("LET", "VAR"):
            mutable = self.advance().kind == "VAR"; kw = "var" if mutable else "let"
            name = self.expect("IDENT", f"expected variable name after '{kw}'")
            ann = self.parse_type() if self.match("COLON") else None
            self.expect("EQ", f"expected '=' after variable name in '{kw}'"); init = self.expression()
            self.expect("SEMI", "expected ';' after variable declaration")
            return Let(name.text, mutable, ann, init, name.line, name.col)
        if kind == "FN" and self.peek(1).kind == "IDENT":
            self.advance(); name = self.advance()
            return FnDecl(name.text, *self.function_rest("expected '(' after function name"), name.line, name.col)
        if kind == "IF": return self.if_stmt()
        if kind == "WHILE":
            kw = self.advance(); cond = self.expression()
            return While(cond, self.block("expected '{' after while condition"), kw.line, kw.col)
        if kind == "RETURN":
            kw = self.advance(); value = None if self.check("SEMI") else self.expression()
            self.expect("SEMI", "expected ';' after return"); return Return(value, kw.line, kw.col)
        if kind == "PRINT":
            kw = self.advance(); self.expect("LPAREN", "expected '(' after 'print'")
            value = self.expression(); self.expect("RPAREN", "expected ')' after print argument")
            self.expect("SEMI", "expected ';' after print statement"); return Print(value, kw.line, kw.col)
        if kind == "LBRACE": return self.block("expected '{'")
        first = self.peek(); e = self.expression()
        if self.check("EQ"):
            if not isinstance(e, Var): self.fail("invalid assignment target")
            self.advance(); value = self.expression()
            self.expect("SEMI", "expected ';' after assignment"); return Assign(e.name, value, e.line, e.col)
        self.expect("SEMI", "expected ';' after expression"); return ExprStmt(e, first.line, first.col)
    def block(self, message):
        lb = self.expect("LBRACE", message); stmts = self.statements_until("RBRACE")
        self.expect("RBRACE", "expected '}' at end of block"); return Block(stmts, lb.line, lb.col)
    def if_stmt(self):
        kw = self.advance(); cond = self.expression(); then = self.block("expected '{' after if condition")
        else_ = None
        if self.match("ELSE"):
            else_ = self.if_stmt() if self.check("IF") else self.block("expected '{' or 'if' after 'else'")
        return If(cond, then, else_, kw.line, kw.col)
    def function_rest(self, lparen_message):
        self.expect("LPAREN", lparen_message); params = []
        if not self.check("RPAREN"):
            while True:
                p = self.expect("IDENT", "expected parameter name")
                self.expect("COLON", f"expected ':' and a type after parameter '{p.text}'")
                params.append(Param(p.text, self.parse_type(), p.line, p.col))
                if not self.match("COMMA"): break
        self.expect("RPAREN", "expected ')' after parameters")
        ret = self.parse_type() if self.match("ARROW") else UNIT
        return params, ret, self.block("expected '{' before function body")
    def parse_type(self):
        tok = self.peek()
        if tok.kind == "IDENT":
            if tok.text not in ("Int", "Bool", "Str", "Unit"): self.fail(f"unknown type '{tok.text}'")
            self.advance(); return TypeName(tok.text)
        if not self.match("LPAREN"): self.fail("expected a type")
        params = [] if self.check("RPAREN") else [self.parse_type()]
        while self.match("COMMA"): params.append(self.parse_type())
        self.expect("RPAREN", "expected ')' in function type"); self.expect("ARROW", "expected '->' in function type")
        return FnType(tuple(params), self.parse_type())
    def expression(self, min_bp=0):
        t = self.peek()
        if t.kind not in ("INT", "STRING", "TRUE", "FALSE", "IDENT", "LPAREN", "MINUS", "BANG", "FN"):
            self.fail("expected expression")
        self.advance()
        if t.kind == "INT": left = Num(int(t.text), t.line, t.col)
        elif t.kind == "STRING":
            left = Str(re.sub(r'\\(.)', lambda m: "\n" if m[1] == "n" else m[1], t.text[1:-1]), t.line, t.col)
        elif t.kind in ("TRUE", "FALSE"): left = Bool(t.kind == "TRUE", t.line, t.col)
        elif t.kind == "IDENT": left = Var(t.text, t.line, t.col)
        elif t.kind in ("MINUS", "BANG"): left = Unary(t.text, self.expression(70), t.line, t.col)
        elif t.kind == "FN": left = Lambda(*self.function_rest("expected '(' after 'fn'"), t.line, t.col)
        else:
            left = self.expression(); self.expect("RPAREN", "expected ')' after expression")
        last_cmp = None
        while True:
            t = self.peek()
            if t.kind == "LPAREN":
                if min_bp > 80: return left
                self.advance(); args = [] if self.check("RPAREN") else [self.expression()]
                while self.match("COMMA"): args.append(self.expression())
                self.expect("RPAREN", "expected ')' after arguments")
                left = Call(left, args, *start(left)); continue
            bp = INFIX.get(t.kind, -1)
            if bp < min_bp: return left
            if bp in (30, 40) and last_cmp == bp: self.fail("comparison operators cannot be chained")
            self.advance()
            left = Binary(t.text, left, self.expression(bp + 1), t.line, t.col); last_cmp = bp

@dataclass(eq=False)
class Binding:                                 # resolver.py (পর্ব ৫১): one per declaration
    name: str; kind: str; depth: int; slot: int; is_global: bool; owner: object
    line: int; col: int; captured: bool = False

@dataclass
class Scope:
    names: dict = field(default_factory=dict); pending: set = field(default_factory=set)

@dataclass
class Resolution:
    uses: dict; decls: dict                    # id(Var/Assign) -> Binding; id(Let/FnDecl/Param) -> Binding
    nslots: dict; nglobals: int                # id(function) or None -> slot count; global count

def declared(stmts): return {s.name for s in stmts if isinstance(s, (Let, FnDecl))}

class Resolver:                                # resolver.py: slots in declaration order, never reused
    def __init__(self):
        self.scopes, self.errors, self.uses, self.decls, self.owner, self.depth = [], [], {}, {}, None, 0
        self.nslots, self.nglobals = {None: 0}, 0
    def error(self, n, msg): self.errors.append(HaatError(n.line, n.col, msg))
    def declare(self, n, name, kind):
        scope = self.scopes[-1]
        if name in scope.names: self.error(n, f"'{name}' is already declared in this scope")
        is_global = len(self.scopes) == 1
        if is_global: slot, self.nglobals = self.nglobals, self.nglobals + 1
        else:
            key = None if self.owner is None else id(self.owner)
            slot = self.nslots[key]; self.nslots[key] += 1
        b = Binding(name, kind, self.depth, slot, is_global, self.owner, n.line, n.col)
        scope.names[name] = b; scope.pending.discard(name); self.decls[id(n)] = b
    def lookup(self, n, name):
        for scope in reversed(self.scopes):
            if name in scope.names:
                b = scope.names[name]
                if not b.is_global and b.owner is not self.owner: b.captured = True
                self.uses[id(n)] = b; return b
            if name in scope.pending: return self.error(n, f"'{name}' is used before its declaration")
        self.error(n, f"undefined variable '{name}'")
    def program(self, prog):
        self.scopes.append(Scope(pending=declared(prog.stmts)))
        for s in prog.stmts:
            if isinstance(s, FnDecl): self.declare(s, s.name, "fn")
        for s in prog.stmts:
            self.function(s) if isinstance(s, FnDecl) else self.stmt(s)
        if self.errors: raise HaatErrors(self.errors)
        return Resolution(self.uses, self.decls, self.nslots, self.nglobals)
    def block(self, stmts):
        self.scopes.append(Scope(pending=declared(stmts)))
        for s in stmts: self.stmt(s)
        self.scopes.pop()
    def stmt(self, s):
        if isinstance(s, Let): self.expr(s.init); self.declare(s, s.name, "var" if s.mutable else "let")
        elif isinstance(s, FnDecl): self.declare(s, s.name, "fn"); self.function(s)
        elif isinstance(s, Assign):
            self.expr(s.value); b = self.lookup(s, s.name)
            if b and b.kind != "var":
                what = {"let": f"'{s.name}': it is declared with 'let'", "param": f"parameter '{s.name}'",
                        "fn": f"function '{s.name}'"}[b.kind]
                self.error(s, f"cannot assign to {what}")
        elif isinstance(s, If):
            self.expr(s.cond); self.block(s.then.stmts)
            if isinstance(s.else_, If): self.stmt(s.else_)
            elif s.else_ is not None: self.block(s.else_.stmts)
        elif isinstance(s, While): self.expr(s.cond); self.block(s.body.stmts)
        elif isinstance(s, Return):
            if self.owner is None: self.error(s, "'return' outside of a function")
            if s.value is not None: self.expr(s.value)
        elif isinstance(s, Print): self.expr(s.value)
        elif isinstance(s, ExprStmt): self.expr(s.expr)
        elif isinstance(s, Block): self.block(s.stmts)
    def function(self, f):
        saved = self.owner, self.depth; self.owner, self.depth = f, self.depth + 1; self.nslots[id(f)] = 0
        self.scopes.append(Scope(pending=declared(f.body.stmts)))
        for p in f.params: self.declare(p, p.name, "param")
        for s in f.body.stmts: self.stmt(s)
        self.scopes.pop(); self.owner, self.depth = saved
    def expr(self, e):
        if isinstance(e, Var): self.lookup(e, e.name)
        elif isinstance(e, Unary): self.expr(e.operand)
        elif isinstance(e, Binary): self.expr(e.left); self.expr(e.right)
        elif isinstance(e, Call):
            self.expr(e.callee)
            for a in e.args: self.expr(a)
        elif isinstance(e, Lambda): self.function(e)

def front(src):                                # lexer + parser + resolver; returns (program, resolution)
    toks = tokenize(src); p = Parser(toks); stmts = p.statements_until("EOF")
    program = Program(stmts)
    return program, Resolver().program(program)

def always_returns(stmts):                     # typechecker.py: decision 21, a syntactic rule
    for s in stmts:
        if isinstance(s, Return): return True
        if isinstance(s, Block) and always_returns(s.stmts): return True
        if isinstance(s, If) and s.else_ is not None:
            other = [s.else_] if isinstance(s.else_, If) else s.else_.stmts
            if always_returns(s.then.stmts) and always_returns(other): return True
    return False
সহায়ক module haat_code.py দেখুন (Code আর disassembler)
# haat_code.py — সহায়ক অংশ: Code object আর disassembler.
# Reference-এর compiler.py-র Code class আর disasm.py-র সংক্ষিপ্ত রূপ; listing হুবহু `haat.py dis`-এর মতো।
from dataclasses import dataclass, field

BINARY_OPS = {"+": "ADD", "-": "SUB", "*": "MUL", "/": "DIV", "%": "MOD",
              "==": "EQ", "!=": "NE", "<": "LT", "<=": "LE", ">": "GT", ">=": "GE"}

@dataclass(eq=False)
class Code:                                    # one per function, plus one for <main>
    name: str; arity: int; nlocals: int = 0
    instrs: list = field(default_factory=list)       # [(opcode, arg)]
    positions: list = field(default_factory=list)    # [(line, col)], one per instruction
    consts: list = field(default_factory=list)       # constants and inner Code objects
    local_names: list = field(default_factory=list)  # slot -> name (only for dis)
    free_names: list = field(default_factory=list)   # free index -> name (only for dis)
    captures: list = field(default_factory=list)     # [(from_local, index)] for MAKE_CLOSURE
    global_names: list = field(default_factory=list) # only on <main>

def quote(s): return '"' + s.replace("\\", "\\\\").replace('"', '\\"').replace("\n", "\\n") + '"'

def const_text(c):
    if c is None: return "()"                  # the Unit value
    if isinstance(c, Code): return f"<fn {c.name}>"
    if isinstance(c, bool): return "true" if c else "false"
    return quote(c) if isinstance(c, str) else str(c)

def comment(code, op, arg, gnames):
    if op == "CONST": return const_text(code.consts[arg])
    if op in ("LOAD_LOCAL", "STORE_LOCAL", "MAKE_CELL", "LOAD_CELL", "STORE_CELL"): return code.local_names[arg]
    if op in ("LOAD_FREE", "STORE_FREE"): return code.free_names[arg]
    if op.endswith("_GLOBAL"): return gnames[arg]
    if op == "MAKE_CLOSURE":
        inner = code.consts[arg]
        return f"<fn {inner.name}>" + (" captures " + ", ".join(inner.free_names) if inner.free_names else "")
    return ""

def disassemble(main):                         # <main> first, then inner functions, breadth first
    out, todo = [], [main]
    while todo:
        code = todo.pop(0)
        out.append(f"== {code.name} (arity {code.arity}, locals {code.nlocals}) ==")
        for offset, (op, arg) in enumerate(code.instrs):   # decision 28: offset = instruction index
            text = f"{offset:4}  {op:<15}{'' if arg is None else arg:<4}"
            note = comment(code, op, arg, main.global_names)
            out.append((text + ("  ; " + note if note else "")).rstrip())
        todo.extend(c for c in code.consts if isinstance(c, Code))
        out.append("")
    return "\n".join(out).rstrip() + "\n"

৪ · Expression — post-order মানেই কোড

Stack machine-এর জন্য expression compile করার নিয়মটি এক লাইনের: গাছটি postorder traversal-এ ঘুরুন, অর্থাৎ আগে সব সন্তান, শেষে node নিজে, আর প্রতিটি node-এ তার নির্দেশ লিখুন। কারণ সহজ: operator চলার মুহূর্তে তার operand-গুলো stack-এর ওপরে তৈরি থাকতে হবে। নিয়মটি একটি compile function C দিয়ে লেখা যায়, যেখানে “;” মানে “তারপর”:

নিয়ম ৫৮.১ — expression-এর compile

C(n) = CONST k, যেখানে consts[k] = n  ·  C(x) = LOAD_w x, যেখানে w ∈ {GLOBAL, LOCAL, CELL, FREE}  ·  C(⊖e) = C(e); NEG বা NOT  ·  C(e1 ⊕ e2) = C(e1); C(e2); OP(⊕)  ·  C(f(e1, …, en)) = C(f); C(e1); …; C(en); CALL n

⊕ যেকোনো binary operator (&& আর || বাদে), ⊖ unary - বা !. বাঁ operand আগে, ডান পরে, আর call-এ callee আগে, তারপর argument বাঁ থেকে ডানে: এটি reference-এর সিদ্ধান্ত ১২-এর (বাঁ থেকে ডানে হিসাব) সরাসরি রূপ। বিয়োগ বা ভাগের মতো operator-এ ক্রম জরুরি: VM প্রথমে তোলে b (ওপরেরটি), তারপর a, আর হিসাব করে a − b. নিচের stepper-এ price-এর চতুর্থ লাইনের expression, আর ডানে দেখুন চলার সময় (price(2, 520) ডাকে, p = 1040) stack কেমন হবে।

1Binary "-"      4:292├─ Var p        4:273└─ Binary "/"   4:334   ├─ Var p     4:315   └─ Num 10    4:35
Compiler-এর খাতা
নতুন নির্দেশ
consts
চলার সময় stack
  1. মূল node বিয়োগ। post-order বলে আগে দুই সন্তান, তাই এখনো কিছু লেখা হয়নি। আগের লাইনগুলো থেকে ৮টি নির্দেশ (0–7) আর consts-এ 1000 আছে।
  2. বাঁ সন্তান p. Resolver বলেছে p হলো price-এর slot 2 (qty 0, unit 1), আর কোনো ভেতরের function একে ধরে না, তাই LOAD_LOCAL 2, index 8.
  3. ডান সন্তান ভাগ, তার বাঁ সন্তান p. আবার LOAD_LOCAL 2, index 9. চলার সময় stack-এ এখন দুটি 1040.
  4. ধ্রুবক 10. consts-এ 10 নেই, তাই শেষে বসে index 1-এ; নির্দেশ CONST 1, index 10. এখানে stack সবচেয়ে উঁচু: ৩টি মান।
  5. ভাগের দুই সন্তান শেষ। এবার DIV, index 11. চলার সময় এটি 10 আর 1040 তুলে 104 রাখে (C-র মতো শূন্যের দিকে কাটা ভাগ)।
  6. বিয়োগের দুই সন্তান শেষ। SUB, index 12: 1040 − 104 = 936. Expression শেষে stack-এ ঠিক একটি নতুন মান। এরপর return statement লেখে RETURN (13); পুরো listing reference-এর dis-এর সঙ্গে হুবহু এক।

একটি চুক্তি, আর তার প্রমাণের রূপরেখা। দাবি: ধরুন e-এর type ঠিক আছে আর চলার সময় কোনো runtime error হয় না। VM যদি C(e)-র শুরুতে stack S নিয়ে পৌঁছায়, তবে C(e)-র শেষে stack হয় S·v, যেখানে v হলো e-এর মান (পর্ব ৪০-এর big-step নিয়মে e ⇓ v), আর পথে S-এর কোনো মান ছোঁয়া হয় না। প্রমাণের রূপরেখা, e-এর গঠনের ওপর induction:

  1. ধ্রুবক বা নাম: একটি CONST বা LOAD_ নির্দেশ, যা S-এর ওপরে v রাখে।
  2. e1 ⊕ e2: অনুমান অনুযায়ী C(e1) শেষে S·v1, তারপর C(e2) শুরু হয় S·v1 থেকে, তাই শেষে S·v1·v2, আর v1-কে ছোঁয় না। OP দুটি তুলে v1 ⊕ v2 রাখে: S·v.
  3. Call: একই যুক্তিতে S·f·v1…vn; CALL n নতুন frame-এ function চালায়, যার RETURN ফলটি রেখে যায়: S·v. ∎

এই চুক্তি থেকেই আসে compiler-এর সবচেয়ে কাজের নিয়ম: প্রতিটি expression stack-এ ঠিক একটি মান যোগ করে। এবার কোডে। নিচের ব্লক reference-এর compiler.py-র FnCompiler-এর প্রথম অংশ, একই নাম আর একই কাজ; শেষে শুধু একটি expression compile করে দেখায়।

# ধাপ ১: 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)
program, res = front("fn price(qty: Int, unit: Int) -> Int { let p = qty * unit; return p - p / 10; }")
price = program.stmts[0]; c = FnCompiler(res, price, None, "price", 2)
c.expr(price.body.stmts[1].value); print("p - p / 10:")   # only this expression
for i, (op, arg) in enumerate(c.code.instrs): print(i, op, "" if arg is None else arg)
print("consts:", c.code.consts, " slot of p:", res.decls[id(price.body.stmts[0])].slot)

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

p - p / 10:
0 LOAD_LOCAL 2
1 LOAD_LOCAL 2
2 CONST 0
3 DIV 
4 SUB 
consts: [10]  slot of p: 2

নির্দেশগুলো stepper-এর সঙ্গে মেলে, শুধু index 0 থেকে, কারণ এখানে শুধু একটি expression compile হলো। আর ধ্রুবক 10 বসেছে index 0-এ, কারণ এই Code-এর তালিকায় আগে 1000 ঢোকেনি; পুরো function compile করলে হয় CONST 1. const function-এর একটি সূক্ষ্মতা দেখুন: শুধু c == value নয়, type(c) is type(value)-ও মিলতে হয়। Python-এ True == 1 সত্য, তাই এই পরীক্ষা না থাকলে Haat-এর true আর 1 একই ধ্রুবক হয়ে যেত, আর print(1) ছাপত true. এমন ভুল চোখে পড়ে না, শুধু test-এ ধরা পড়ে।

৫ · Statement আর লাফ — stack যেমন পেয়েছেন তেমন রাখুন

Expression-এর চুক্তির সঙ্গী statement-এর চুক্তি: প্রতিটি statement stack যেমন পেয়েছিল, তেমনই রেখে যায়। তাই প্রতিটি statement-এর কোড একটি expression দিয়ে শুরু হয় (+1) আর এমন একটি নির্দেশে শেষ হয় যা মানটি সরায় (−1):

  • let x = e; → C(e); DEFINE_GLOBAL বা STORE_LOCAL বা MAKE_CELL (প্রথম মান)। x = e; → C(e); STORE_w.
  • print(e); → C(e); PRINT. return e; → C(e); RETURN; return; হলে মান হিসেবে Unit, CONST ().
  • e; (যেমন add(5);) → C(e); POP. মানটি কেউ চায় না, কিন্তু stack থেকে সরাতেই হবে; অনুশীলন ২-এ দেখবেন POP ভুলে গেলে কী হয়।

if আর while লাফে নামে, আর সামনের লাফের লক্ষ্য পরে ভরা হয়: এই backpatching-এর পুরো কৌশল, প্রমাণসহ, পর্ব ২৭-এ (Control flow). এখানে নতুন দুটি কথা। প্রথম, reference-এর একটি ছোট সাশ্রয়: then-শাখা যদি সব পথে return করে (always_returns, সিদ্ধান্ত ২১-এর একই নিয়ম), তবে else ডিঙানোর JUMP লেখা হয় না, কারণ সেটি কখনো চলবে না। price-এ তাই 7-এর JUMP_IF_FALSE 14-এর পরে then-শাখা 13-এর RETURN-এ শেষ, কোনো JUMP নেই। দ্বিতীয়, short-circuit: a && b হয় a; JUMP_IF_FALSE L1; b; JUMP L2; L1: CONST false; L2:. দুই পথেই শেষে stack-এ ঠিক একটি Bool, তাই expression-এর চুক্তি রক্ষা পায়। || এর আয়না: a; JUMP_IF_FALSE L1; CONST true; JUMP L2; L1: b; L2:.

নিচের stepper-এ bazar.haat-এর while loop, compiler-এর চোখে। লাফের কৌশল পর্ব ২৭-এর মতোই; এবার নজর দিন অন্য দুটি খাতায়: global-এর নম্বর আর constant pool কীভাবে বাড়ে।

1while total < 5000 {2    total = total + 1250;3    rounds = rounds + 1;4}5print(total);6print(rounds - 1);
Compiler-এর খাতা
লেখা
ধ্রুবক
ফাঁকা
  1. শর্ত। আগে ২২টি নির্দেশ (0–21) লেখা হয়েছে, তাই top = 22. total একটি top-level var, resolver-এর global নম্বর 3 (price 0, delivery 1, first 2), তাই LOAD_GLOBAL 3. 5000 নতুন ধ্রুবক: consts-এ আগে ছিল দুটি Code আর 2, 520, 0, তাই 5000 যায় index 5-এ।
  2. লাফ, লক্ষ্য অজানা। JUMP_IF_FALSE লেখা হলো index 25-এ, লক্ষ্যের ঘর ফাঁকা; loop-এর শেষ এখনো তৈরি হয়নি।
  3. প্রথম assignment. value আগে (LOAD_GLOBAL 3, CONST 6 = 1250, ADD), তারপর STORE_GLOBAL 3. top-level-এর var, তাই global; assignment, তাই STORE, DEFINE নয়।
  4. দ্বিতীয় assignment. rounds হলো global 4. ধ্রুবক 1 নতুন, index 7-এ বসে।
  5. পেছনের লাফ। JUMP 22: লক্ষ্য আগে থেকেই জানা, কোনো ঘর ফাঁকা রাখতে হয় না।
  6. Loop শেষ। পরের নির্দেশ 35, তাই ঘর 25 ভরা হলো 35 দিয়ে। এরপর print(total): 35–36.
  7. print(rounds - 1). এবার 1 আগে থেকেই consts[7]-এ আছে, তাই নতুন কিছু যোগ হলো না, আবার CONST 7. program শেষে CONST 8 (Unit) আর RETURN; listing README-এর সত্যিকারের dis-এর সঙ্গে হুবহু এক।

এবার statement-এর অংশ কোডে। নিচের ব্লক আগের ব্লকের class-কেই বড় করে (একই নাম, আগেরটির ওপর subclass), তাই দুটি ব্লক পরপর চালাতে হবে। শেষে একটি ছোট program compile করে listing ছাপে; reference-এর python haat.py dis একই program-এ হুবহু এই listing-ই ছাপে (লেখকের যন্ত্রে মিলিয়ে দেখা)।

# ধাপ ২: 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]
program, res = front("var total = 0;\nvar rounds = 0;\nwhile total < 5000 { total = total + 1250; rounds = rounds + 1; }\nprint(total > 4000 && rounds != 0);")
main = FnCompiler(res, None, None, "<main>", 0)    # <main> by hand; compile_program comes in step 3
for s in program.stmts: main.stmt(s)
main.const(None); main.emit("RETURN"); main.code.global_names = ["total", "rounds"]
print(disassemble(main.code), end="")

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

== <main> (arity 0, locals 0) ==
   0  CONST          0     ; 0
   1  DEFINE_GLOBAL  0     ; total
   2  CONST          0     ; 0
   3  DEFINE_GLOBAL  1     ; rounds
   4  LOAD_GLOBAL    0     ; total
   5  CONST          1     ; 5000
   6  LT
   7  JUMP_IF_FALSE  17
   8  LOAD_GLOBAL    0     ; total
   9  CONST          2     ; 1250
  10  ADD
  11  STORE_GLOBAL   0     ; total
  12  LOAD_GLOBAL    1     ; rounds
  13  CONST          3     ; 1
  14  ADD
  15  STORE_GLOBAL   1     ; rounds
  16  JUMP           4
  17  LOAD_GLOBAL    0     ; total
  18  CONST          4     ; 4000
  19  GT
  20  JUMP_IF_FALSE  25
  21  LOAD_GLOBAL    1     ; rounds
  22  CONST          0     ; 0
  23  NE
  24  JUMP           26
  25  CONST          5     ; false
  26  PRINT
  27  CONST          6     ; ()
  28  RETURN

0–16 stepper-এর loop-ই, শুধু এখানে কোনো function নেই বলে global-এর নম্বর 0 আর 1. 17–25 হলো &&: বাঁ দিক (17–19) মিথ্যা হলে 20 থেকে 25-এ লাফ, CONST 5 মানে false; সত্য হলে ডান দিক (21–23) চলে আর 24 CONST false-কে ডিঙায়। দুই পথ 26-এ মেলে, দুই পথেই stack-এ একটি Bool. খেয়াল করুন 22-এর CONST 0: rounds != 0-এর 0 নতুন ধ্রুবক নয়, শুরুর var total = 0-এর consts[0]-ই। reference এই program চালালে (vm) ছাপে true.

৬ · Global, function, hoisting আর closure

একটি নাম পড়তে কোন opcode লাগবে, তা ঠিক করে where function: পুরো সিদ্ধান্তটি resolver আগেই নিয়ে রেখেছে (পর্ব ৫১), compiler শুধু পড়ে।

Binding-এর অবস্থাOpcode পরিবারউদাহরণ
top-level-এ ঘোষিত (is_global)*_GLOBALbazar-এর total, price
এই function-এর নিজের, কেউ ধরে না*_LOCALprice-এর p
এই function-এর নিজের, ভেতরের function ধরে (captured)MAKE_CELL, *_CELLmake_counter-এর count
বাইরের কোনো function-এর*_FREElambda-র ভেতরে count

Global আর hoisting. top-level-এর প্রতিটি নাম একটি global ঘর পায়, ঘোষণার ক্রমে নম্বর। কিন্তু Haat-এ top-level function যেকোনো জায়গা থেকে ডাকা যায়, ঘোষণার আগেও (সিদ্ধান্ত ১৭, hoisting নামে পরিচিত)। Compiler এটি বাস্তবায়ন করে সরলভাবে: compile_program প্রথমে সব top-level function-এর জন্য MAKE_CLOSURE আর DEFINE_GLOBAL লেখে, তারপর বাকি statement ক্রমে। bazar-এর listing তাই 0–3-এ price আর delivery দিয়ে শুরু। DEFINE_GLOBAL আর STORE_GLOBAL আলাদা কেন? সিদ্ধান্ত ১৮: একটি hoisted function এমন global variable পড়তে পারে, যার let এখনো চলেনি। তাই LOAD_GLOBAL আর STORE_GLOBAL চলার সময় পরীক্ষা করে ঘরটি ভরা কি না (না হলে 'k' is not initialized yet), আর DEFINE_GLOBAL হলো প্রথম ভরা, যার কোনো পরীক্ষা লাগে না।

Function. একটি function-এর শরীর নিজের FnCompiler-এ compile হয়, তৈরি Code বসে parent-এর consts-এ, আর parent লেখে MAKE_CLOSURE k. শরীর যদি সব পথে return না করে, শেষে CONST () আর RETURN যোগ হয়, যাতে Unit function-ও একটি মান রেখে ফেরে। ডাকা হয় CALL n দিয়ে; frame আর call sequence-এর পুরো বিবরণ পর্ব ৩০-এ।

Closure. পর্ব ১৭-এ দেখেছেন, Haat-এর closure বাইরের variable by reference ধরে, একটি cell-এর মাধ্যমে; চলার সময়ের বিবরণ পর্ব ৫৭-এ (Environment আর closure-এর বাস্তবায়ন). Compiler-এর কাজ চারটি: (১) ধরা local-এর প্রথম মান STORE_LOCAL নয়, MAKE_CELL দিয়ে লেখা; (২) ধরা parameter-কে function-এর শুরুতেই cell-এ তোলা (LOAD_LOCAL s; MAKE_CELL s); (৩) ভেতরের function-এ বাইরের নামকে একটি free variable নম্বর দেওয়া, প্রথম দেখার ক্রমে; (৪) প্রতিটি free variable-এর জন্য captures-এ লেখা parent সেটি কোথায় পাবে: (True, slot) মানে parent-এর নিজের slot-এর cell, (False, i) মানে parent-এর নিজের free cell i (দুই স্তর বাইরের নাম এভাবে ধাপে ধাপে নামে)। Lua-তে একই ধারণার নাম upvalue.

2fn make_counter(step: Int)      -> () -> Int {3    var count = 0;4    let next = fn() -> Int {5        count = count + step;6        return count;7    };8    return next;9}
বাইরে = make_counter, ভেতরে = lambda@4:16
বাইরে
ভেতরে
তালিকা
  1. Parameter. resolver জানিয়েছে, step slot 0-এ আসে আর ভেতরের lambda তাকে ব্যবহার করে। তাই শরীরের আগেই LOAD_LOCAL 0; MAKE_CELL 0: মানটি বাক্সে উঠল, slot 0-এ এখন বাক্স।
  2. var count = 0. count-ও ধরা, তাই প্রথম মান MAKE_CELL 1 দিয়ে; ধ্রুবক 0 হলো consts[0].
  3. Lambda-র শরীর, লাইন ৫. নতুন FnCompiler, নাম lambda@4:16 (সিদ্ধান্ত ২৩)। count আর step বাইরের, তাই FREE; প্রথম দেখার ক্রমে count পায় 0, step পায় 1. Assignment-এ value আগে, তাই LOAD_FREE 0; LOAD_FREE 1; ADD; STORE_FREE 0.
  4. return count. LOAD_FREE 0; RETURN. শরীর সব পথে return করে, তাই শেষে বাড়তি CONST () নেই।
  5. captures হিসাব। count আর step দুটিরই মালিক parent (make_counter), তাই (True, 1) আর (True, 0): “parent-এর slot 1-এর cell, তারপর slot 0-এর cell”, free নম্বরের ক্রমে।
  6. parent-এ ফেরা। lambda-র Code বসল consts[1]-এ, তাই MAKE_CLOSURE 1. next-কে কোনো ভেতরের function ধরে না, তাই সাধারণ STORE_LOCAL 2.
  7. return next. LOAD_LOCAL 2; RETURN. দুটি Code-এর listing reference-এর সত্যিকারের dis-এর সঙ্গে হুবহু, আর disassembler MAKE_CLOSURE-এর পাশে লেখে captures count, step.

একটি nested function নিজেকে ডাকলে কী হয়? nested.haat-এর countdown-এর ভেতরে go নিজেকে ডাকে, তাই go নিজের নামটিকেই ধরে। Closure তৈরির আগেই cell লাগবে, নইলে closure-এ ধরার মতো কিছু নেই। reference এর জন্য একটি ছোট কৌশল নেয়, সত্যিকারের dis:

== countdown (arity 1, locals 2) ==
   0  CONST          0     ; ()
   1  MAKE_CELL      1     ; go
   2  MAKE_CLOSURE   1     ; <fn go> captures go
   3  STORE_CELL     1     ; go
   4  LOAD_CELL      1     ; go
   5  LOAD_LOCAL     0     ; n
   6  CALL           1
   7  POP
   8  CONST          0     ; ()
   9  RETURN

আগে একটি খালি বাক্স (() দিয়ে), তারপর সেই বাক্স ধরে closure, তারপর closure-টিকেই বাক্সে রাখা: ডিমের আগে মুরগির খাঁচা। go(n); একটি expression statement, তাই 7-এ POP. নিচের ব্লক compiler সম্পূর্ণ করে আর তিনটি পুরো example ফাইল compile করে reference-এর আসল dis আউটপুটের সঙ্গে অক্ষরে অক্ষরে মেলায়। .dis ফাইলগুলো লেখকের যন্ত্রে python -B haat.py dis-এর সত্যিকারের আউটপুট, পাতায় রাখা।

# ধাপ ৩: 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
for name in ("bazar", "counter", "nested"):      # *.dis = real output of `python haat.py dis`
    mine = disassemble(compile_program(*front(open(name + ".haat", encoding="utf-8").read())))
    print(f"{name}.haat: {mine.count(chr(10))} lines, identical to reference dis: {mine == open(name + '.dis', encoding='utf-8').read()}")

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

bazar.haat: 72 lines, identical to reference dis: True
counter.haat: 74 lines, identical to reference dis: True
nested.haat: 142 lines, identical to reference dis: True

তিনটি ফাইলেই অক্ষরে অক্ষরে মিল: bazar (৭২ লাইন), counter (৭৪) আর nested (১৪২, যেখানে nested function, higher-order function, loop-এর ভেতরের closure আর নিজেকে ডাকা go সব আছে)। এটি একটি ছোট differential testing. লেখকের যন্ত্রে (CPython 3.14.4) বড় পরীক্ষাও চালানো হয়েছে: reference-এর examples ফোল্ডারের যে ১০টি ফাইল static check পেরোয়, তার ১০টিতেই মিল; আর seed 58 দিয়ে তৈরি ৩,০০০টি এলোমেলো Haat program-এর মধ্যে যে ১,৫৮৭টি reference-এর check পেরিয়েছে, তার ১,৫৮৭টিতেই dis হুবহু এক (এদের ১৯৩টিতে MAKE_CELL, ৪৯টিতে STORE_CELL, ১৯২টিতে LOAD_FREE আছে)। মিল মানে দুই বাস্তবায়নে একই ভুল থাকতে পারে না, এমন নয়; কিন্তু একটির ভুল অন্যটি ধরিয়ে দেয়।

৭ · Stack effect, সর্বোচ্চ গভীরতা আর যাচাই

VM-কে প্রতিটি frame-এর জন্য stack-এ কতটা জায়গা রাখতে হবে? চালিয়ে দেখার আগেই উত্তর বের করা যায়, কারণ প্রতিটি opcode-এর stack effect জানা (অংশ ৩-এর টেবিল)। পদ্ধতিটি abstract interpretation-এর সবচেয়ে সরল রূপ: আসল মানের বদলে শুধু “stack-এ কয়টি মান” হিসাব করে প্রতিটি নির্দেশে পৌঁছানো, প্রতিটি পথ ধরে। দুটি পথ একই নির্দেশে মিললে (loop-এর শুরু, if-এর join) দুই পথের গভীরতা সমান হতেই হবে; না হলে কোডটি ভুল। Expression আর statement-এর চুক্তি দুটি মানলে Haat compiler-এর কোডে এটি সবসময় সত্য, আর এই checker সেই দাবিটিই যন্ত্রে যাচাই করে।

Expression-এর জন্য গভীরতার একটি সূত্রও আছে: d(n) = d(x) = 1, d(⊖e) = d(e), d(e1 ⊕ e2) = max(d(e1), 1 + d(e2)), কারণ e2 হিসাবের পুরো সময় e1-এর মান নিচে বসে থাকে। p - p / 10-এ: d(p / 10) = max(1, 1 + 1) = 2, তাই d = max(1, 1 + 2) = 3, ঠিক stepper-এর সর্বোচ্চ।

# ধাপ ৪: stack effect দিয়ে প্রতিটি Code-এর সর্বোচ্চ stack গভীরতা — চালানো ছাড়াই
EFFECT = {"CONST": 1, "LOAD_LOCAL": 1, "LOAD_CELL": 1, "LOAD_FREE": 1, "LOAD_GLOBAL": 1,
          "MAKE_CLOSURE": 1, "STORE_LOCAL": -1, "STORE_CELL": -1, "STORE_FREE": -1,
          "MAKE_CELL": -1, "DEFINE_GLOBAL": -1, "STORE_GLOBAL": -1, "NEG": 0, "NOT": 0,
          "JUMP": 0, "JUMP_IF_FALSE": -1, "RETURN": -1, "PRINT": -1, "POP": -1}
EFFECT.update(dict.fromkeys(BINARY_OPS.values(), -1))      # a b -> r

def max_depth(code):
    seen, todo, deepest = {0: 0}, [0], 0                    # instruction index -> depth before it
    while todo:
        i = todo.pop(); op, arg = code.instrs[i]
        after = seen[i] + (-arg if op == "CALL" else EFFECT[op])   # CALL n: f a1..an -> r
        if after < 0: raise ValueError(f"{code.name}: stack underflow at {i}")
        deepest = max(deepest, after)
        nexts = [] if op == "RETURN" else [arg] if op == "JUMP" else [i + 1]
        if op == "JUMP_IF_FALSE": nexts.append(arg)
        for n in nexts:                                     # every path must agree on the depth
            if n in seen and seen[n] != after:
                raise ValueError(f"{code.name}: paths reach {n} with depth {seen[n]} and {after}")
            if n not in seen: seen[n] = after; todo.append(n)
    return deepest, len(seen)

def walk(code):                                             # <main> and every inner function
    yield code
    for c in code.consts:
        if isinstance(c, Code): yield from walk(c)

for name in ("bazar", "counter"):
    for code in walk(compile_program(*front(open(name + ".haat", encoding="utf-8").read()))):
        d, reached = max_depth(code)
        print(f"{name + ':':<9}{code.name:<14} max depth {d}, reachable {reached}/{len(code.instrs)}")
broken = Code("broken", 0, instrs=[("CONST", 0), ("JUMP_IF_FALSE", 3), ("CONST", 0), ("CONST", 0), ("RETURN", None)])
try: max_depth(broken)
except ValueError as err: print("rejected:", err)

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

bazar:   <main>         max depth 5, reachable 43/43
bazar:   price          max depth 3, reachable 16/16
bazar:   delivery       max depth 2, reachable 8/8
counter: <main>         max depth 2, reachable 43/43
counter: make_counter   max depth 1, reachable 8/8
counter: lambda@4:16    max depth 2, reachable 6/6
counter: lambda@18:11   max depth 2, reachable 6/6
counter: lambda@19:11   max depth 1, reachable 2/2
rejected: broken: paths reach 3 with depth 0 and 1

bazar-এর <main>-এ গভীরতা ৫, কারণ price(2, 520) + delivery(price(2, 520)): প্রথম ফলটি নিচে রেখে delivery, তার ওপরে price, 2, 520 (9–11 নম্বর নির্দেশে)। সব নির্দেশে পৌঁছানো যায় (৪৩/৪৩), কোনো মৃত কোড নেই। শেষের ইচ্ছাকৃত ভুল কোডটি চার নির্দেশের: শর্ত মিথ্যা হলে 3-এ পৌঁছায় শূন্য গভীরতায়, সত্য হলে একটি বাড়তি মান নিয়ে; checker সেটি ফিরিয়ে দিল। চলার সময়ের সঙ্গেও মেলানো হয়েছে: reference-এর vm.py-র একটি কপিতে (লেখকের lab-এ, মূল ফাইল অপরিবর্তিত) প্রতিটি frame-এর আসল সর্বোচ্চ উচ্চতা মাপা হলো, examples-এর ১০টি ফাইলের ৩৪টি Code object-এ। ৩৪টিতেই মাপা মান এই হিসাবের সমান। সাধারণভাবে হিসাবটি একটি ঊর্ধ্বসীমা: যে পথ কখনো চলে না, তার গভীরতাও গোনা হয়।

বাস্তব VM-গুলো ঠিক এটিই করে। CPython-এর compiler প্রতিটি code object-এ co_stacksize হিসাব করে রাখে, আর JVM-এর class file-এ প্রতিটি method-এর max_stack লেখা থাকে। JVM আরও এক ধাপ যায়: class লোড করার সময় bytecode verifier প্রমাণ করে যে প্রতিটি নির্দেশে stack-এর গভীরতা আর প্রতিটি ঘরের type সব পথে সামঞ্জস্যপূর্ণ, যাতে ভুল বা ক্ষতিকর class file VM-কে ভাঙতে না পারে। WebAssembly-র validation একই ধারণা, প্রতিটি module চালানোর আগে।

আরও গভীরে: পুরোনো JVM verifier প্রতিটি method-এ এই হিসাব fixpoint পর্যন্ত চালাত, যা ধীর আর জটিল। Java 6 থেকে class file-এ StackMapTable নামের সংকেত আসে: compiler নিজেই প্রতিটি লাফের লক্ষ্যে stack আর local-এর type লিখে দেয়, আর verifier শুধু একবার সামনে হেঁটে সেগুলো মিলিয়ে নেয়; Java 7-এর class file version থেকে এটি বাধ্যতামূলক। এখানে কাজ ভাগ হয়েছে: খোঁজার কঠিন কাজ compiler-এর, যাচাইয়ের সহজ কাজ VM-এর। Proof-carrying code-এর (Necula ও Lee, ১৯৯৬–৯৭) মূল ভাবনাও এই: প্রমাণ বানানো কঠিন হতে পারে, কিন্তু যাচাই সহজ হওয়া চাই।

৮ · Encoding, operand আর নকশার অন্য সিদ্ধান্ত

Haat-এর নির্দেশ Python tuple, পড়তে সহজ। সত্যিকারের bytecode byte-এর সারি, তাই আরও কয়েকটি সিদ্ধান্ত নিতে হয়। একই price function Python-এ লিখে CPython 3.14.4-এর dis দেখা যাক (সত্যিকারের run, লেখকের যন্ত্রে; Python-এর // floor করে আর Haat-এর / শূন্যের দিকে কাটে, ধনাত্মক সংখ্যায় দুটি এক)। CPython-এর bytecode-এর পুরো আলোচনা পর্ব ৬০-এ (বাস্তব virtual machine); এখানে শুধু নকশার তুলনা।

~/bcd $ python -B cpy.py
3.14.4
co_stacksize: 3  co_nlocals: 3  co_consts: (1000,)
co_code bytes: 66  instructions: 16
  2           RESUME                   0

  3           LOAD_FAST_BORROW_LOAD_FAST_BORROW 1 (qty, unit)
              BINARY_OP                5 (*)
              STORE_FAST               2 (p)

  4           LOAD_FAST_BORROW         2 (p)
              LOAD_CONST               0 (1000)
              COMPARE_OP             188 (bool(>=))
              POP_JUMP_IF_FALSE       16 (to L1)
              NOT_TAKEN

  5           LOAD_FAST_BORROW_LOAD_FAST_BORROW 34 (p, p)
              LOAD_SMALL_INT          10
              BINARY_OP                2 (//)
              BINARY_OP               10 (-)
              RETURN_VALUE

  6   L1:     LOAD_FAST_BORROW         2 (p)
              RETURN_VALUE

দুই VM-এরই ১৬টি নির্দেশ আর সর্বোচ্চ গভীরতা ৩: একই stack-যন্ত্রের চিন্তা। কিন্তু পার্থক্যগুলোই নকশার শিক্ষা:

সিদ্ধান্তHaatCPython 3.14
Encodingtuple-এর list; offset = index (সিদ্ধান্ত ২৮)২ byte-এর code unit (wordcode, ৩.৬ থেকে), সঙ্গে কিছু নির্দেশের পরে বাড়তি cache-এর ঘর; তাই ১৬টি নির্দেশ ৬৬ byte
ছোট ধ্রুবকসব ধ্রুবক constant pool-এ (CONST 1)ছোট int নির্দেশের ভেতরেই (LOAD_SMALL_INT 10), তাই consts-এ শুধু 1000
Superinstructionনেইদুটি load এক নির্দেশে (LOAD_FAST_BORROW_LOAD_FAST_BORROW)
Operatorপ্রতিটির নিজের opcode (ADD, DIV)একটি BINARY_OP, argument বলে কোনটি
Positionপ্রতিটি নির্দেশে (line, col)আলাদা location table; ৩.১১ থেকে কলামসহ (PEP 657)

প্রতিটির পেছনে একটি আপস। নির্দেশের ভেতরে মান রাখার কৌশলের নাম immediate operand: constant pool-এ একবার কম যেতে হয়, কিন্তু argument-এর জায়গা সীমিত (CPython-এ এক byte; বড় হলে আগে EXTENDED_ARG বসাতে হয়)। JVM-এর opcode এক byte, কিন্তু operand-এর দৈর্ঘ্য নির্দেশভেদে আলাদা; WebAssembly সংখ্যা লেখে LEB128-এ, ছোট সংখ্যায় কম byte. Superinstruction প্রায়ই একসঙ্গে আসা দুটি নির্দেশকে একটিতে জোড়ে, যাতে dispatch একবার কম হয়; বিনিময়ে opcode বাড়ে আর compiler-এ একটি peephole optimization লাগে। Haat-এর মতো আলাদা ADD/DIV দিলে VM-এর প্রতিটি শাখা ছোট; CPython-এর মতো একটি BINARY_OP দিলে opcode কম, আর বাকিটা সামলায় চলার সময়ের specialization (পর্ব ৬০)।

Position-এর প্রশ্নটি ছোট মনে হলেও জরুরি। Runtime error-এর বার্তা (সিদ্ধান্ত ২৬) source-এর ঠিক ঘর দেখায়, অথচ VM দেখে শুধু নির্দেশ। let n = 0; print(100 / n); চালালে reference-এর vm লেখে 2:11: runtime error: division by zero: DIV-এর position-এ / চিহ্নের ঘর, সিদ্ধান্ত ২৪-এর মতো। Haat প্রতিটি নির্দেশে একটি জোড়া রাখে (সরল কিন্তু বড়); বাস্তব VM সাধারণত একটি সংকুচিত position table রাখে, যা শুধু error বা debugger-এর সময় খোলা হয়।

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

  • a + b * c-এর stack code? LOAD a; LOAD b; LOAD c; MUL; ADD: post-order.
  • Stack VM বনাম register VM? Stack: নির্দেশ ছোট, compiler সহজ; register: চলা নির্দেশ কম, প্রতিটি বড়। JVM ও CPython stack, Lua ৫ register.
  • Constant pool কেন? নির্দেশ ছোট আর সমান মাপের রাখতে; বড় বা জটিল মান (string, function-এর কোড) একবার রেখে index দিয়ে বলা।
  • একটি expression-এর জন্য কত stack লাগে? d(e1 ⊕ e2) = max(d(e1), 1 + d(e2)), পাতার মান 1.
  • Expression statement-এর পরে POP কেন? প্রতিটি statement stack অপরিবর্তিত রাখে; না সরালে loop-এ stack বাড়তে থাকে।

৯ · AI-এর যুগে bytecode

AI assistant দিয়ে একটি ছোট compiler বা VM লেখানো আজ কয়েক মিনিটের কাজ। কিন্তু bytecode-এর ভুল প্রায়ই চুপচাপ থাকে: program বেশির ভাগ input-এ ঠিক ছাপে, অথচ stack ধীরে ধীরে নষ্ট হয়, বা অন্য version-এ ভেঙে যায়।

AI-এর ভুলকীভাবে ধরবেন
পুরোনো version-এর CPython opcode দাবি করা, যেমন ৩.১৪-এর জন্য BINARY_ADD (৩.১১-এ BINARY_OP এসে এদের জায়গা নিয়েছে)সেই version-এর Python-এ dis চালানো; sys.version লিখে রাখা
বিয়োগ বা ভাগে operand উল্টো: VM তোলে b আগে, অথচ কোডে a − b-এর জায়গায় b − a7 - 2, 7 / 2-এর মতো অসম test; দুই back end-এর differential test
Expression statement-এর পরে POP বাদ, বা একটি শাখায় বাড়তি মানঅংশ ৭-এর মতো stack-depth checker; loop-ওয়ালা program
লাফের লক্ষ্য byte offset আর instruction index গুলিয়ে ফেলাভাষার নিজের নিয়ম পড়া (Haat-এ সিদ্ধান্ত ২৮); disassembler দিয়ে লক্ষ্য মিলিয়ে দেখা
“register VM সবসময় দ্রুত”, “Java interpreted” ধরনের ঢালাও দাবিমূল প্রবন্ধ বা documentation; নিজের যন্ত্রে মাপা, এক যন্ত্রের ফল বলে চিহ্নিত করে
1 আর true-কে একই ধ্রুবক ধরা (Python-এ True == 1)print(1); print(true); চালিয়ে দেখা; constant pool-এ type-ও মেলানো

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

আমি একটি ছোট শিক্ষামূলক ভাষার (Haat) জন্য Python 3.14-এ bytecode compiler লিখছি। VM stack-ভিত্তিক; opcode: CONST k, LOAD_LOCAL s, STORE_LOCAL s, ADD, SUB, MUL, DIV, LT, JUMP t, JUMP_IF_FALSE t, CALL n, RETURN, PRINT, POP. লাফের argument হলো instruction index, byte offset নয়। ১. while আর if-else-কে এই opcode-এ নামানোর কোড লেখো, backpatching দিয়ে; প্রতিটি লাফের লক্ষ্য কেন ঠিক, মন্তব্যে বলো। ২. প্রতিটি opcode-এর stack effect-এর একটি টেবিল দাও, আর একটি function লেখো যা চালানো ছাড়াই প্রতিটি function-এর সর্বোচ্চ stack গভীরতা বের করে এবং দুই পথে গভীরতা না মিললে error দেয়। ৩. SUB আর DIV-এ VM কোন মানটি আগে তোলে, স্পষ্ট করে লেখো, আর 7 - 2 ও 7 / 2-এর test দাও। ৪. CPython-এর কোনো opcode-এর কথা বললে কোন version-এর, তা লেখো; নিশ্চিত না হলে বলো, অনুমান করবে না।

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

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

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

প্র ০১Lua ৫.০ কেন stack ছেড়ে register VM-এ গেল, অথচ CPython আর JVM এখনো stack-ভিত্তিক?

Lua ৪ পর্যন্ত Lua-র VM ছিল stack-ভিত্তিক। ২০০৩ সালের Lua ৫.০-এ নকশাকারেরা register-ভিত্তিক VM-এ যান, আর “The Implementation of Lua 5.0” (২০০৫) প্রবন্ধে কারণ লেখেন। একটি interpreter-এ প্রতিটি নির্দেশের একটি স্থির খরচ আছে: নির্দেশ পড়া, opcode দেখে শাখা বাছা, পরের নির্দেশে যাওয়া। Stack কোডে a = b + c-এর জন্য চারটি নির্দেশ লাগে (দুটি load, যোগ, store), register কোডে একটি। Lua-র local variable এমনিতেই frame-এর নম্বরওয়ালা ঘরে থাকে, তাই সেই ঘরগুলোকেই register হিসেবে ব্যবহার করা স্বাভাবিক। তাঁরা নির্দেশকে ৩২ বিটের একটি word-এ এঁটেছেন, ফলে প্রতিটি নির্দেশ বড় হলেও পড়ার খরচ বাড়েনি।

JVM-এর নকশা ১৯৯০-এর দশকের মাঝামাঝি, যখন লক্ষ্য ছিল নেটওয়ার্কে ছোট কোড পাঠানো আর অনেক রকম যন্ত্রে চালানো। Stack কোড ছোট, আর এর কোনো নির্দিষ্ট register-সংখ্যা ধরে নেওয়া নেই, তাই কম register-এর যন্ত্রেও সহজে মানায়। তাছাড়া JVM-এ গরম কোড শেষ পর্যন্ত JIT compiler machine code-এ অনুবাদ করে, তখন stack কোড শুধু একটি মধ্যবর্তী রূপ; JIT সেটিকে নিজের IR-এ বদলে নিজেই register বাছে। CPython-এর ক্ষেত্রে ঐতিহাসিক সরলতা আর সামঞ্জস্য বড় কারণ: compiler সহজ, অনেক tool আর debugger bytecode-এর ওপর নির্ভর করে, আর ৩.১১ থেকে গতি এসেছে অন্য পথে, যেমন চলার সময় নির্দেশকে বিশেষ রূপে বদলানো আর superinstruction.

Android-এর Dalvik VM register-ভিত্তিক ছিল, যুক্তির একটি অংশ ছিল কম শক্তির যন্ত্রে কম নির্দেশ চালানো; পরে Android-এর ART মূলত আগেভাগে machine code-এ compile করে। Shi ও সহকর্মীদের পরিমাপ দেখায় register কোডে চলা নির্দেশ অনেক কম, কিন্তু কোড বড়; লাভ কতটা, তা dispatch-এর খরচের ওপর নির্ভর করে।

মূল উপলব্ধি: stack বনাম register-এর উত্তর নির্ভর করে VM-টি নিজেই শেষ গন্তব্য (তখন কম dispatch জরুরি) নাকি JIT-এর পথে একটি ধাপ (তখন ছোট, সহজ কোড জরুরি), তার ওপর।

প্র ০২Bytecode-এ type থাকা উচিত কি? JVM-এর iadd/dadd, Haat-এর একটি ADD আর WebAssembly-র i32.add তুলনা করুন।

JVM-এ যোগের আলাদা opcode আছে প্রতিটি মৌলিক type-এর জন্য: iadd (int), ladd (long), fadd, dadd; load আর store-ও তাই (iload, aload ইত্যাদি)। এর বড় লাভ যাচাইয়ে: verifier প্রতিটি নির্দেশ দেখেই জানে stack-এ কোন type থাকার কথা, তাই অংশ ৭-এর মতো এক পথের হিসাবেই প্রমাণ করা যায় যে কোনো int-কে pointer হিসেবে ব্যবহার করা হচ্ছে না। নিরাপত্তা-চিন্তিত একটি VM-এর জন্য, যা অচেনা উৎসের কোড চালাবে, এটি কেন্দ্রীয় সুবিধা। দ্বিতীয় লাভ গতি: interpreter-কে চলার সময় type দেখে শাখা বাছতে হয় না।

WebAssembly-ও এই পথে: i32.add, i64.add, f64.add আলাদা, আর প্রতিটি module চালানোর আগে validation হয়। Wasm-এর নকশাই এমন যে validation এক pass-এ শেষ হয়।

Haat-এর ADD-এ type নেই, কারণ Haat-এর type checker (পর্ব ৫২) compile-এর আগেই নিশ্চিত করে যে ভুল জোড়া আসবে না, আর Haat-এর bytecode কখনো ফাইলে লিখে অন্য কারও হাতে যায় না। VM তাই compiler-কে বিশ্বাস করে। এর দাম: কেউ হাতে ভুল bytecode বানালে VM অদ্ভুত আচরণ করবে। CPython-ও কোনো type রাখে না, কারণ Python dynamic ভাষা; BINARY_OP চলার সময় operand-এর type দেখে কাজ বাছে, আর ৩.১১ থেকে বারবার একই type দেখলে নির্দেশটিকে একটি বিশেষ রূপে বদলে নেয় (PEP 659 অনুযায়ী)।

মাঝামাঝি পথও আছে: .NET-এর CIL-এ add একটি, কিন্তু verifier stack-এর type নিজে অনুমান করে। এতে opcode কম থাকে, verifier একটু বেশি কাজ করে।

মূল উপলব্ধি: typed bytecode যাচাই আর দ্রুত interpretation সহজ করে, untyped bytecode instruction set ছোট রাখে; কোনটি ভালো, তা নির্ভর করে bytecode কাকে বিশ্বাস করে: নিজের compiler-কে, নাকি যে কারও পাঠানো ফাইলকে।

প্র ০৩Bytecode-কে বিতরণের ফরম্যাট বানানোর ইতিহাস: BCPL-এর O-code, Pascal-এর P-code থেকে Java class file আর .pyc. কেন কোনোটি স্থির, কোনোটি নয়?

যন্ত্র-নিরপেক্ষ মধ্যবর্তী কোডের ধারণা পুরোনো। ১৯৬০-এর দশকের শেষে Martin Richards-এর BCPL compiler একটি মধ্যবর্তী রূপ, O-code, তৈরি করত, যাতে নতুন যন্ত্রে নিতে শুধু O-code থেকে machine code-এর ছোট অংশটি লিখতে হয়। ১৯৭০-এর দশকে Niklaus Wirth-এর দলের Pascal-P compiler P-code নামের একটি stack-যন্ত্রের কোড বানাত; পরে UCSD Pascal এই ধারণাকে একটি পুরো বহনযোগ্য পরিবেশে নিয়ে যায়। দুটিরই লক্ষ্য ছিল portability: একটি ছোট interpreter লিখলেই পুরো compiler আর library নতুন যন্ত্রে চলে। (তারিখগুলো উৎসভেদে একটু আগে-পরে বলা হয়।)

Java (১৯৯৫) ধারণাটিকে বিতরণের ফরম্যাট বানাল: class file-ই পণ্য, source নয়। তাই class file-এর ফরম্যাট JVM specification-এ লেখা, version নম্বরসহ, আর নতুন JVM পুরোনো class file চালাতে বাধ্য। এই স্থিরতার দাম: নতুন ধারণা যোগ করা কঠিন। Java 7-এ dynamic ভাষার জন্য একটি নতুন নির্দেশ, invokedynamic, যোগ করতে আলাদা প্রস্তাব আর দীর্ঘ কাজ লেগেছিল।

CPython-এর .pyc উল্টো নীতিতে চলে। এটি শুধু একটি cache: source থাকলে আবার বানানো যায়। তাই bytecode প্রায় প্রতিটি minor version-এ বদলায়, আর .pyc-এর শুরুতে একটি magic number থাকে, যা না মিললে ফাইলটি ফেলে দিয়ে আবার compile হয়। এই স্বাধীনতাই CPython-কে ৩.১১, ৩.১২, ৩.১৩-এ নির্দেশ বদলে গতি বাড়াতে দিয়েছে।

WebAssembly (২০১৭) আবার Java-র দিকে: browser যেকোনো সাইটের module চালায়, তাই ফরম্যাট স্থির আর validation কঠোর। Haat-এর bytecode কোনো ফাইলেই লেখা হয় না; অনুশীলন ১-এ আপনি একটি byte encoding বানাবেন, তখন এই প্রশ্নগুলো নিজেরই হবে।

মূল উপলব্ধি: bytecode যদি অন্যের হাতে যাওয়া পণ্য হয়, তবে ফরম্যাট স্থির আর যাচাইযোগ্য হতে হয়; যদি শুধু নিজের cache হয়, তবে প্রতিটি version-এ বদলানোর স্বাধীনতা থাকে।

প্র ০৪কেউ হাতে বানানো ভুল bytecode দিলে কী হয়? CPython, JVM আর Haat-এর নিরাপত্তার অবস্থান তুলনা করুন।

Compiler-এর তৈরি bytecode কিছু চুক্তি মানে: stack-এ যথেষ্ট মান না থাকলে তোলা হয় না, লাফ নির্দেশের সীমার ভেতরে যায়, local-এর নম্বর ঘরের সংখ্যার কম। কিন্তু bytecode যদি অন্য কোথাও থেকে আসে, বা হাতে বানানো হয়, এই চুক্তি ভাঙতে পারে। তখন একটি দ্রুত interpreter, যা প্রতিটি নির্দেশে সীমা পরীক্ষা করে না, ভুল মেমরি পড়তে বা লিখতে পারে।

JVM-এর নকশা শুরু থেকেই ধরে নেয় class file অবিশ্বস্ত হতে পারে, তাই verifier আছে: stack-এর উচ্চতা, type, লাফের লক্ষ্য আর access-এর নিয়ম, সব চালানোর আগে যাচাই। WebAssembly-ও একই, আর এর ওপর সব মেমরি-প্রবেশ একটি সীমিত linear memory-র ভেতরে পরীক্ষা হয়। এদের ক্ষেত্রে “ভুল bytecode” মানে লোড হওয়ার সময়েই প্রত্যাখ্যান।

CPython অন্য অবস্থান নেয়: bytecode বিশ্বাস করা হয়। হাতে বানানো code object দিয়ে CPython interpreter-কে crash করানো সম্ভব, আর Python-এর documentation বারবার সতর্ক করে যে অবিশ্বস্ত উৎসের marshal বা pickle ডেটা লোড করা উচিত নয়। এর মানে CPython-এ নিরাপত্তার সীমা bytecode নয়, পুরো প্রক্রিয়া: অবিশ্বস্ত কোড চালাতে হলে আলাদা process, container বা sandbox লাগে। নিরাপদ অভ্যাস তাই সহজ: শুধু নিজের তৈরি বা বিশ্বস্ত উৎসের .pyc চালানো।

Haat-এর VM-ও compiler-কে বিশ্বাস করে। তবে অংশ ৭-এর checker একটি ছোট verifier-এর শুরু: underflow আর অসমান গভীরতা ধরে। একে সম্পূর্ণ করতে লাগবে লাফের লক্ষ্য সীমার ভেতরে কি না, slot নম্বর nlocals-এর কম কি না, consts-এর index ঠিক কি না, আর type-এর হিসাব। এই কাজগুলো ঠিক JVM verifier-এর তালিকা।

মূল উপলব্ধি: bytecode-এর নিরাপত্তা নির্ভর করে VM কাকে বিশ্বাস করে তার ওপর; অবিশ্বস্ত কোড চালানোর VM চালানোর আগে যাচাই করে, আর যে VM যাচাই করে না, তার নিরাপত্তার সীমা অন্য স্তরে টানতে হয়।

প্র ০৫Bytecode কি সবসময় tree-walking interpreter-এর চেয়ে দ্রুত? AST interpreter-এর পক্ষে কী যুক্তি আছে?

প্রচলিত ধারণা: bytecode VM tree-walker-এর চেয়ে দ্রুত। এর পেছনে সত্য কারণ আছে। গাছের node মেমরিতে ছড়ানো, প্রতিটিতে পৌঁছাতে pointer অনুসরণ করতে হয়, আর প্রতিটি node-এ একটি function call বা virtual dispatch. Bytecode একটি ঘন array, ক্রমে পড়া হয়, cache-এর জন্য ভালো, আর নামের সব খোঁজ আগেই সংখ্যায় পরিণত। Ruby-র ইতিহাসে এর একটি উদাহরণ: Ruby ১.৯-এ মূল interpreter AST-ভিত্তিক থেকে YARV নামের bytecode VM-এ যায়, গতির জন্য।

কিন্তু “সবসময়” বলা ভুল। প্রথমত, পার্থক্যের বড় অংশ আসে কাজ আগেভাগে সেরে রাখা থেকে (নাম থেকে slot, লাফের লক্ষ্য), আর সেই কাজ একটি AST interpreter-ও গাছে লিখে রাখতে পারে, যেমন resolver-এর slot নম্বর node-এ রেখে (পর্ব ৫৭-এর slot-ভিত্তিক রূপ)। দ্বিতীয়ত, VM-এর নিজের খরচ আছে: প্রতিটি নির্দেশে dispatch, আর stack-এ মান তোলা-নামানো। Python-এ লেখা একটি VM-এ প্রতিটি নির্দেশ অনেকগুলো Python operation, তাই Haat-এর দুই back end-এর পার্থক্য কত, তা অনুমান না করে মাপতে হবে; পর্ব ৫৯-এ সেটিই করবেন।

তৃতীয়ত, গবেষণায় AST interpreter-এর একটি শক্তিশালী ধারা আছে। Würthinger ও সহকর্মীদের Truffle কাঠামোতে (২০১২-১৩ সালের দিকের প্রবন্ধ) গাছের node নিজেকে চলার সময় বিশেষ রূপে বদলে নেয় (self-optimizing AST), আর Graal compiler পুরো গাছকে partial evaluation দিয়ে machine code বানায়। এই পথে লেখা কিছু ভাষার বাস্তবায়ন প্রতিযোগিতামূলক গতি পেয়েছে বলে প্রকাশিত ফলাফল আছে, যদিও সংখ্যাগুলো benchmark-নির্ভর।

শেষ কথা: সবচেয়ে বড় গতির লাফ আসে interpretation থেকে বেরিয়ে machine code-এ যাওয়ায়, অর্থাৎ JIT (পর্ব ৬১)। Bytecode সেখানে একটি সুবিধাজনক শুরুর বিন্দু, কারণ এটি সমতল, ছোট আর profiling-এর জন্য সহজ।

মূল উপলব্ধি: bytecode-এর গতির সুবিধা আসে আগেভাগে সেরে রাখা কাজ আর ঘন বিন্যাস থেকে, আর সেই সুবিধা মাপতে হয়, ধরে নেওয়া যায় না; ভালো নকশার AST interpreter-ও অনেক দূর যেতে পারে।

অনুশীলন

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

  1. নকশা ও বাস্তবায়ন — Haat bytecode-কে byte-এ লেখা: Haat-এর নির্দেশ এখন Python tuple. একটি byte encoding নকশা করুন: প্রতিটি opcode এক byte (৩১টি opcode-এর বর্ণানুক্রমিক তালিকার index), argument থাকলে তার পরে ২ byte little-endian. encode(instrs) আর decode(data) লিখুন, দেখান যে decode(encode(x)) == x, আর bazar.haat-এর তিনটি Code কত byte হয় বের করুন। লাফের argument কি এখনো index থাকবে, নাকি byte offset হওয়া উচিত?
    import struct
    OPS = sorted([...31টি opcode...])          # ADD=0, CALL=1, CONST=2 …
    NOARG = {"ADD","SUB","MUL","DIV","MOD","EQ","NE","LT","LE","GT","GE",
             "NEG","NOT","RETURN","PRINT","POP"}
    def encode(instrs):
        out = bytearray()
        for op, arg in instrs:
            out.append(OPS.index(op))
            if arg is not None: out += struct.pack("<H", arg)
        return bytes(out)
    def decode(data):
        i, res = 0, []
        while i < len(data):
            op = OPS[data[i]]; i += 1
            if op in NOARG: res.append((op, None))
            else: res.append((op, struct.unpack_from("<H", data, i)[0])); i += 2
        return res

    লেখকের CPython 3.14.4-এ সত্যিকারের run: তিনটি Code-এই round trip ঠিক; <main> ৪৩টি নির্দেশ → ১১১ byte, price ১৬ → ৩৬, delivery ৮ → ১৮; মোট ৬৭টি নির্দেশ ১৬৫ byte (সব নির্দেশ ৩ byte করলে হতো ২০১)। delivery-র byte: 0e 00 00 02 00 00 06 09 06 00 02 01 00 19 02 02 00 19 (0e = LOAD_LOCAL, 02 = CONST, 06 = GE, 09 = JUMP_IF_FALSE, 19 = RETURN). লক্ষ্যের প্রশ্ন: নির্দেশের দৈর্ঘ্য এখন অসমান (১ বা ৩ byte), তাই index রাখলে VM-কে আগে একটি index → byte টেবিল বানাতে হবে, অথবা decode করে tuple-এর তালিকায় ফিরতে হবে। Byte offset রাখলে সরাসরি লাফ দেওয়া যায়, কিন্তু compiler-কে backpatching-এর সময় প্রতিটি নির্দেশের দৈর্ঘ্য জানতে হয়। CPython সমস্যাটি এড়াতে সব code unit ২ byte করেছে। ২ byte-এর argument-এ সর্বোচ্চ ৬৫,৫৩৫টি ধ্রুবক বা লক্ষ্য; বড় function-এর জন্য CPython-এর EXTENDED_ARG-এর মতো একটি বাড়তি নির্দেশ লাগবে।

  2. ভুল খুঁজুন: একজন সহকর্মী Haat compiler-এর stmt-এ expression statement-কে লিখলেন self.expr(s.expr), শেষে POP ছাড়া। নিচের program-এ আউটপুট কি বদলাবে? ভুলটি কোথায় ধরা পড়বে, আর কোন চুক্তি ভেঙেছে?
    fn tick(n: Int) -> Int { print(n); return n; }
    var i = 0;
    while i < 3 { tick(i); i = i + 1; }

    আউটপুট বদলায় না: ভুল compiler-এর কোড reference-এর vm.py-তে চালিয়ে সত্যিকারের ফল 0, 1, 2, ঠিক program-এর মতোই। আর এটিই বিপদ: ভুলটি চুপচাপ। প্রতিটি round-এ tick(i)-এর ফেরত মান stack-এ থেকে যায়, তিন round শেষে তিনটি বাড়তি মান; বড় loop-এ stack অসীমভাবে বাড়বে। ভুলটি ধরা পড়ে অংশ ৭-এর checker-এ, সত্যিকারের run: rejected: <main>: paths reach 4 with depth 0 and 1. নির্দেশ 4 হলো loop-এর শুরু (LOAD_GLOBAL 1 ; i): প্রথমবার সেখানে আসা হয় গভীরতা 0 নিয়ে, আর 15-এর JUMP 4 থেকে আসা হয় গভীরতা 1 নিয়ে। ভাঙা চুক্তি: “প্রতিটি statement stack যেমন পেয়েছিল তেমন রাখে”। tick(i); একটি expression statement, তার expression +1, তাই শেষে −1 (POP) লাগবেই। ঠিক কোডে checker বলে <main>-এর সর্বোচ্চ গভীরতা 2. শিক্ষা: আউটপুট-ভিত্তিক test এই শ্রেণির ভুল ধরে না; গঠনগত যাচাই লাগে।

  3. হিসাব ও trace: নিচের program-এর জন্য (ক) fee-এর bytecode হাতে লিখুন, constant pool-সহ; (খ) fee-এর সর্বোচ্চ stack গভীরতা কত? (গ) program কী ছাপে?
    fn fee(km: Int) -> Int {
        if km <= 3 { return 40; }
        return 40 + (km - 3) * 15;
    }
    print(fee(5) + fee(2));
    == fee (arity 1, locals 1) ==
       0  LOAD_LOCAL     0     ; km
       1  CONST          0     ; 3
       2  LE
       3  JUMP_IF_FALSE  6
       4  CONST          1     ; 40
       5  RETURN
       6  CONST          1     ; 40
       7  LOAD_LOCAL     0     ; km
       8  CONST          0     ; 3
       9  SUB
      10  CONST          2     ; 15
      11  MUL
      12  ADD
      13  RETURN

    (ক) এটি reference-এর সত্যিকারের python haat.py dis. consts = [3, 40, 15]: 3 আর 40 দ্বিতীয়বার এলে আগের index-ই ফেরে (6-এ CONST 1, 8-এ CONST 0 আবার)। then-শাখা return করে, তাই 5-এর পরে কোনো JUMP নেই। (খ) ৩: 6–8-এ 40, km, 3 একসঙ্গে, আবার 10-এ 40, (km − 3), 15. সূত্রে: d(40 + (km − 3) * 15) = max(1, 1 + max(2, 1 + 1)) = 3. অংশ ৭-এর checker-ও সত্যিকারের run-এ fee-এর জন্য 3 দিয়েছে (আর <main>-এর জন্যও 3 পেয়েছে)। (গ) fee(5) = 40 + 2 × 15 = 70, fee(2) = 40, তাই 110; reference-এর run আর vm দুটিই ছাপে 110.

  4. প্রমাণ — গভীরতার সূত্র আর operand-এর ক্রম: (ক) প্রমাণ করুন যে Haat compiler-এর C(e) চলার সময় stack-এর সর্বোচ্চ বাড়তি উচ্চতা d(e), যেখানে d(n) = d(x) = 1, d(⊖e) = d(e), d(e1 ⊕ e2) = max(d(e1), 1 + d(e2)). (খ) a + (b * (c - d)) আর ((c - d) * b) + a-এর d কত? (গ) একটি optimizer যদি গভীরতা কমাতে প্রথমটিকে দ্বিতীয়টিতে বদলায়, Haat-এ সেটি কখন বৈধ?

    (ক) প্রমাণ, e-এর গঠনের ওপর induction. ধ্রুবক আর নাম: একটি নির্দেশ, উচ্চতা 1. ⊖e: C(e) চলার সময় সর্বোচ্চ d(e), শেষে 1, তারপর NEG/NOT একটি তুলে একটি রাখে, তাই d(e). e1 ⊕ e2: C(e1) চলার সময় সর্বোচ্চ d(e1), শেষে 1 (expression-এর চুক্তি)। তারপর C(e2) সেই একটি মানের ওপরে চলে, তাই সর্বোচ্চ 1 + d(e2). OP-এর পরে 1, যা কোনোটিকে ছাড়ায় না। তাই সর্বোচ্চ max(d(e1), 1 + d(e2)). ∎

    (খ) প্রথমটি: d(c − d) = 2, d(b * …) = max(1, 1 + 2) = 3, d(a + …) = max(1, 1 + 3) = 4. দ্বিতীয়টি: d(c − d) = 2, d(… * b) = max(2, 1 + 1) = 2, d(… + a) = max(2, 2) = 2. অংশ ৭-এর checker-এর সত্যিকারের run-ও 4 আর 2 দিয়েছে, আর a = 7, b = 5, c = 9, d = 4 দিয়ে reference-এর vm দুটিতেই ছাপে 32. সূত্রটি বলে: ভারী subtree আগে হিসাব করলে stack কম লাগে। এই ধারণা Sethi ও Ullman-এর ১৯৭০ সালের register-সংখ্যা হিসাবের পদ্ধতির মূল কথা।

    (গ) + আর * Int-এ commutative (৬৪ বিট wrap করলেও, সিদ্ধান্ত ১৩), তাই মান একই। কিন্তু সিদ্ধান্ত ১২ বলে হিসাব বাঁ থেকে ডানে। operand-গুলোর কোনোটির side effect থাকলে (যেমন print করে এমন একটি function call), বা কোনোটি runtime error দিতে পারলে (ভাগ, যার শূন্য-ভাগের error কোনটি আগে হবে তা বদলাবে), ক্রম বদলানো অর্থ বদলায়। তাই বৈধ শুধু তখন, যখন সব operand side effect আর error ছাড়া: ধ্রুবক, variable আর + - *-এর মতো operator. + যদি Str জোড়ে, তবে commutative নয়, তখন একেবারেই নয়।

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

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

ক্রমHaat reference compiler একটি nested function (যা কেউ ধরে না) যে ক্রমে compile করে, সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. ভেতরের function-এর জন্য নতুন FnCompiler তৈরি
  2. ধরা parameter থাকলে LOAD_LOCAL s; MAKE_CELL s
  3. শরীরের statement-গুলো compile
  4. সব পথে return না হলে CONST (); RETURN
  5. প্রতিটি free variable-এর জন্য captures-এ লেখা
  6. parent-এর consts-এ Code রেখে MAKE_CLOSURE k, তারপর নামে রাখা

একটি stack VM-এর জন্য a - b * c-এর সঠিক bytecode কোনটি (a, b, c local)?

  • LOAD a; LOAD b; SUB; LOAD c; MUL
  • LOAD a; LOAD b; LOAD c; MUL; SUB
  • LOAD b; LOAD c; MUL; LOAD a; SUB
  • LOAD a; LOAD b; LOAD c; SUB; MUL

Haat-এর CALL n নির্দেশের stack effect কত?

  • −(n + 1)
  • +1
  • −n
  • 0

Haat-এ নিচের function-এ total কোন opcode পরিবারে পড়া হয়, ভেতরের lambda থেকে?
fn make(total: Int) -> () -> Int { return fn() -> Int { return total; }; }

  • LOAD_GLOBAL
  • LOAD_LOCAL
  • LOAD_CELL
  • LOAD_FREE

একটি compiler-এর constant pool-এর const function শুধু c == value দিয়ে আগের ধ্রুবক খোঁজে (Python-এ লেখা)। Haat-এ print(1); print(true); compile করলে কী সমস্যা হবে?

  • দুটি একই ধ্রুবক হয়ে যাবে, ফলে একটি print ভুল মান ছাপবে
  • Compile error হবে
  • কোনো সমস্যা নেই, শুধু pool একটু ছোট হবে
  • Stack-এর গভীরতা ভুল হিসাব হবে

একটি stack-depth checker দেখল, একটি while loop-এর প্রথম নির্দেশে এক পথে গভীরতা 0 আর পেছনের লাফ থেকে আসা পথে 1. সবচেয়ে সম্ভাব্য কারণ কী?

  • শর্তের কোডে JUMP_IF_FALSE আছে
  • Loop-এর body stack-এ একটি মান রেখে যায়
  • Loop global variable ব্যবহার করে
  • JUMP নির্দেশ stack-এ মান রাখে

Stack VM আর register VM-এর তুলনায় কোন কথাটি সবচেয়ে সঠিক?

  • Register VM-এর কোড সবসময় ছোট আর দ্রুত
  • JVM আর CPython register-ভিত্তিক, Lua stack-ভিত্তিক
  • Register VM-এ চলা নির্দেশ কম, কিন্তু নির্দেশ বড়; সময়ের লাভ dispatch-এর খরচের ওপর নির্ভর করে
  • Stack VM-এর compiler-কে register allocation করতে হয়

Haat reference-এ if c { return 1; } else { return 2; }-এর কোডে then-শাখার পরে else ডিঙানোর JUMP নেই কেন?

  • JUMP_IF_FALSE দুই দিকেই লাফ দিতে পারে
  • else-এর কোড then-এর আগে লেখা হয়
  • VM-এ JUMP নির্দেশ নেই
  • then-শাখা সবসময় return করে, তাই JUMP কখনো চলত না

শব্দকোষ

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

মনে রাখুন

  1. Bytecode = আগেভাগে সেরে রাখা কাজ: নাম থেকে slot, লাফের লক্ষ্য, ধ্রুবকের index সব compile-এর সময় ঠিক; VM শুধু সমতল সারি চালায়।
  2. Stack বনাম register: stack কোড ছোট আর compiler সহজ (Haat, CPython, JVM, Wasm); register কোডে চলা নির্দেশ কম (Lua ৫)।
  3. দুই চুক্তি: expression = post-order, stack-এ ঠিক +1; statement = stack অপরিবর্তিত (তাই expression statement-এর পরে POP লাগে)।
  4. নামের চার পরিবার: GLOBAL, LOCAL, CELL, FREE; hoisting মানে সব top-level function আগে MAKE_CLOSURE + DEFINE_GLOBAL; closure-এর জন্য MAKE_CELL আর captures.
  5. Stack effect দিয়ে যাচাই: সর্বোচ্চ গভীরতা আর “সব পথে সমান গভীরতা” চালানো ছাড়াই; CPython-এর co_stacksize আর JVM verifier একই ধারণা।

পরের পর্বে: পর্ব ৫৯ (Stack-based virtual machine — Haat VM তৈরি). এই পর্বের bytecode চালানোর fetch–decode–execute loop, frame, CALL আর RETURN, আর interpreter বনাম VM-এর সত্যিকারের মাপ।

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

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