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

Environment আর closure-এর বাস্তবায়ন — interpreter-এর ভেতরে

Implementing Environments and Closures — Dict Chains, Resolver Slots and Cells, Heap Environments, Space Safety and the Cost of a Name Lookup

Taught in Bangla, this lesson implements environments two ways in in-page Python (Pyodide). First a chain of dicts as in the reference interpreter, counting lookups, with closures as code plus an environment pointer kept on the heap to solve the upward funarg problem. Then resolver addresses with slots and cells and flat closures that match the Haat VM. It covers fresh cells per loop iteration, space safety, lookup speed measured with CPython, JavaScript's with and eval, and differential testing.

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

  • একটি tree-walking interpreter-এর environment dict-এর শিকল হিসেবে লেখা, আর প্রতিটি খোঁজায় কত ধাপ লাগে তা গুনে দেখা
  • Closure object (code + environment) বানানো, আর environment কেন heap-এ থাকে তা funarg problem দিয়ে ব্যাখ্যা করা
  • Resolver-এর slot আর cell দিয়ে দ্বিতীয় একটি environment বানানো, যা Haat VM-এর সঙ্গে ঠিকানায় ঠিকানায় মেলে
  • Loop-এর closure, space safety আর গতি: কোন নকশা কী বাঁচিয়ে রাখে, কত সময় নেয়, সত্যিকারের মাপে
  • দুই বাস্তবায়নকে reference-এর সঙ্গে differential testing দিয়ে মেলানো, আর একটি ছোট প্রমাণ দিয়ে বোঝা কেন দুটি সবসময় একই ফল দেয়

১ · Environment — interpreter-এর নামের খাতা

Interpreter যখন count + step দেখে, তাকে জানতে হয় এই মুহূর্তে count মানে কোন মান। সেই উত্তর আসে environment থেকে: নাম থেকে মান (বা মানের ঘর) পর্যন্ত একটি খাতা। পর্ব ১৭-এ (Closure) দেখেছেন closure কী আর কেন variable ধরে; পর্ব ৫১-এ (Symbol table আর name resolution) compiler কীভাবে প্রতিটি নাম তার ঘোষণার সঙ্গে জোড়া দেয়। এই পর্বে প্রশ্নটি একেবারে যান্ত্রিক: চলার সময় খাতাটি কোন data structure, কোথায় থাকে, আর closure তার কতটুকু সঙ্গে নেয়।

বাজারঘরের প্রতিটি শাখা অফিসে একটি খাতা থাকে। কোনো পণ্যের দাম জানতে কর্মী প্রথমে নিজের শাখার খাতা দেখেন; না পেলে জেলা অফিসের খাতা, তারপর ঢাকার প্রধান অফিসের। এটিই environment-এর শিকল। এখন একজন কর্মীকে অন্য শহরে পাঠানো হলো, কিন্তু তাঁর হিসাব চলবে নিজের শাখার খাতা ধরে। তিনি খাতার কপি নেবেন, নাকি খাতাটি কোথায় আছে সেই ঠিকানার চিরকুট? আর পুরো খাতা নেবেন, নাকি শুধু যে দুটি পাতা লাগবে? এই পর্বের পুরোটাই এই দুই প্রশ্নের প্রকৌশল।

সংজ্ঞা ৫৭.১ — environment-এর তিনটি কাজ

একটি environment ρ হলো নাম থেকে ঘর (বা সরাসরি মান) পর্যন্ত একটি সসীম map, সঙ্গে বাইরের environment-এর একটি link. বাস্তবায়নকে চারটি কাজ দিতে হয়: extend (নতুন scope খোলা: block বা call), define (let/var/fn/parameter-এর প্রথম মান বসানো), lookup (নাম থেকে মান পড়া) আর assign (x = e;-এ ঘরের মান বদলানো)। Closure তৈরি হলে পঞ্চম একটি কাজ যোগ হয়: capture, অর্থাৎ পরে ব্যবহারের জন্য environment-এর একটি অংশ ধরে রাখা।

এই কাজগুলো বানানোর কয়েকটি প্রচলিত নকশা আছে। Haat-এ আমরা প্রথম আর চতুর্থটি পুরো বানাব, আর বাকিগুলোর সঙ্গে তুলনা করব:

নকশাLookupClosure কী রাখেকোথায় দেখবেন
Dict-এর শিকল (প্রতিটি scope একটি hash map)নাম ধরে শিকলে হাঁটাপুরো Env-এর pointerHaat interp.py, বহু শিক্ষণ-interpreter
Array frame + static link(কত frame বাইরে, কোন slot)বাইরের frame-এর pointerPascal-ধারার compiler, পর্ব ৩০
Displayএক ধাপে, গভীরতার array থেকেসাধারণত শুধু downward ব্যবহারপুরোনো ALGOL বাস্তবায়ন, পর্ব ৩০
Slot + cell, flat closurearray-র একটি ঘর (cell হলে আরও এক ধাপ)শুধু free variable-এর cellHaat vm.py, CPython
Open/closed upvaluestack-এর ঘর, পরে নিজের ভেতরপ্রতিটি free variable-এর upvalueLua, পর্ব ১৭

Static link আর display-এর ঘর ধরে হিসাব আছে পর্ব ৩০-এ (Subprogram-এর বাস্তবায়ন). এখানে মনোযোগ দুই প্রান্তে: সবচেয়ে সহজ dict-এর শিকল, আর resolver-এর ঠিকানায় চলা slot-ব্যবস্থা, যা পর্ব ৫৯-এর (Stack-based virtual machine) VM-এর হৃদয়। Interpreter-এর বাকি কাঠামো (statement চালানো, ReturnSignal, runtime error) পর্ব ৫৬-এর (Tree-walking interpreter) বিষয়।

২ · প্রথম রূপ — dict-এর শিকল, reference যেভাবে করে

পর্ব ৫৬-এ interpreter-এর সঙ্গে এই environment একবার দেখেছেন; এবার তাকে খুলে মাপব। Haat reference-এর interp.py-তে environment মাত্র কয়েক লাইনের: একটি Env class, যার ভেতরে একটি Python dict (vars) আর বাইরের Env-এর link (parent). Dict নিজে একটি hash table, তাই একটি Env-এ নাম আছে কি না দেখা গড়ে এক ধাপের কাজ; কিন্তু নামটি কয়েক Env বাইরে থাকলে প্রতিটিতে একবার করে দেখতে হয়। এই হাঁটাই scope chain-এর চলমান রূপ।

এই পাতার Python ব্লকগুলো একটি সহায়ক module, haat_front.py, import করে। এতে আছে আগের পর্বগুলোর lexer, parser আর resolver-এর সংক্ষিপ্ত রূপ (reference-এর একই নাম আর বার্তা), runtime-এর সাহায্যকারী function, আর Walker: reference-এর interp.py-র কাঠামো, যেখানে environment-এর প্রতিটি কাজ একটি আলাদা method (hook) হিসেবে রাখা। ফলে একই interpreter-এ environment-এর নকশা বদলানো যায় শুধু সাতটি method লিখে: global_env, scope, define, load, assign, make_fn আর enter.

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

class HaatError(Exception):                    # errors.py
    def __init__(self, line, col, message, runtime=False):
        super().__init__(message); self.line, self.col, self.message, self.runtime = line, col, message, runtime
    def __str__(self):
        return f"{self.line}:{self.col}: {'runtime error' if self.runtime else '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; nslots: dict; nglobals: int   # nslots: id(function) or None -> slot count

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

class Resolver:                                # resolver.py: scopes, slots, captured
    def __init__(self):
        self.scopes, self.errors, self.uses, self.decls = [], [], {}, {}
        self.nslots, self.nglobals, self.owner, self.depth = {None: 0}, 0, None, 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      # slots are never reused
        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)
    program = Program(Parser(tokenize(src)).statements_until("EOF"))
    return program, Resolver().program(program)

def free_bindings(f, res):                     # compile-time: what function f takes from outside, first-use order
    cache = res.__dict__.setdefault("free", {})
    if id(f) not in cache:
        inner, used = set(), []
        def walk(n):
            if isinstance(n, list):
                for x in n: walk(x)
            elif hasattr(n, "line"):
                if isinstance(n, (FnDecl, Lambda)): inner.add(id(n))
                b = res.uses.get(id(n))
                if b is not None and b not in used: used.append(b)
                for v in vars(n).values(): walk(v)
        walk(f)
        cache[id(f)] = [b for b in used if not b.is_global and id(b.owner) not in inner]
    return cache[id(f)]

MAX_CALL_DEPTH = 1000                          # runtime.py: shared helpers
UNSET = object()                               # vm.py: a global whose let/var has not run yet
def wrap(n): return ((n + 2**63) % 2**64) - 2**63
def runtime_error(line, col, msg): return HaatError(line, col, msg, runtime=True)
def c_div(a, b, line, col):
    if b == 0: raise runtime_error(line, col, "division by zero")
    q = abs(a) // abs(b); return wrap(q if (a < 0) == (b < 0) else -q)
def c_mod(a, b, line, col):
    if b == 0: raise runtime_error(line, col, "division by zero")
    q = abs(a) // abs(b); q = q if (a < 0) == (b < 0) else -q
    return wrap(a - b * 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 c_div(a, b, line, col)
    if op == "%": return c_mod(a, b, line, col)
    return {"==": a == b, "!=": a != b, "<": a < b, "<=": a <= b, ">": a > b, ">=": a >= b}[op]
def show(v): return ("true" if v else "false") if isinstance(v, bool) else str(v)

class ReturnSignal(Exception):                 # interp.py: unwinds from `return` to its call
    def __init__(self, value): self.value = value

class Walker:                                  # interp.py's shape (পর্ব ৫৬); every environment step is a hook
    def __init__(self, res, out=print): self.res, self.out, self.depth = res, out, 0
    def run(self, program):
        env = self.genv = self.global_env()
        for s in program.stmts:                # hoist top-level functions
            if isinstance(s, FnDecl): self.define(s, self.make_fn(s, s.name, env), env)
        for s in program.stmts:
            if not isinstance(s, FnDecl): self.exec(s, env)
    def exec_block(self, stmts, env):
        for s in stmts: self.exec(s, env)
    def exec(self, s, env):
        if isinstance(s, Let): self.define(s, self.eval(s.init, env), env)
        elif isinstance(s, FnDecl): self.define_fn(s, env)
        elif isinstance(s, Assign): self.assign(s, self.eval(s.value, env), env)
        elif isinstance(s, If):
            if self.eval(s.cond, env): self.exec_block(s.then.stmts, self.scope(env))
            elif isinstance(s.else_, If): self.exec(s.else_, env)
            elif s.else_ is not None: self.exec_block(s.else_.stmts, self.scope(env))
        elif isinstance(s, While):
            while self.eval(s.cond, env): self.exec_block(s.body.stmts, self.scope(env))  # fresh scope each round
        elif isinstance(s, Return): raise ReturnSignal(None if s.value is None else self.eval(s.value, env))
        elif isinstance(s, Print): self.out(show(self.eval(s.value, env)))
        elif isinstance(s, ExprStmt): self.eval(s.expr, env)
        elif isinstance(s, Block): self.exec_block(s.stmts, self.scope(env))
    def define_fn(self, s, env): self.define(s, self.make_fn(s, s.name, env), env)
    def eval(self, e, env):
        if isinstance(e, (Num, Str, Bool)): return e.value
        if isinstance(e, Var): return self.load(e, env)
        if isinstance(e, Unary):
            v = self.eval(e.operand, env); return wrap(-v) if e.op == "-" else not v
        if isinstance(e, Binary):
            if e.op == "&&": return self.eval(e.left, env) and self.eval(e.right, env)
            if e.op == "||": return self.eval(e.left, env) or self.eval(e.right, env)
            a = self.eval(e.left, env); b = self.eval(e.right, env)
            return arith(e.op, a, b, e.line, e.col)
        if isinstance(e, Call):
            f = self.eval(e.callee, env); args = [self.eval(a, env) for a in e.args]
            if self.depth >= MAX_CALL_DEPTH: raise runtime_error(e.line, e.col, "stack overflow")
            frame = self.enter(f, args); self.depth += 1
            try:
                self.exec_block(f.node.body.stmts, frame); return None
            except ReturnSignal as r: return r.value
            finally: self.depth -= 1
        if isinstance(e, Lambda): return self.make_fn(e, f"lambda@{e.line}:{e.col}", env)

def run_src(Interp, src):                      # output lines; a runtime error is the last line
    lines = []; program, res = front(src); it = Interp(res, lambda t: lines.extend(t.split("\n")))
    try: it.run(program)
    except HaatError as e: lines.append(str(e))
    return lines, it

প্রথম ব্লক reference-এর environment-অংশ: Env, closure-এর জন্য Function, আর সাতটি hook. সঙ্গে দুটি গণনা: কতবার নাম খোঁজা হলো (lookups), আর মোট কতবার কোনো dict-এ নাম আছে কি না দেখা হলো (probes). চালানো হয় reference-এর counter.haat আর নিচের checkout.haat, দুটিই পাতায় রাখা ফাইল। পরের তিনটি Python ব্লক একই namespace ভাগ করে (পরেরটি আগে চালালে আগেরগুলো নিজে চলে)।

// বাজারঘর: এক অর্ডারের বাজেট — দুটি closure একটি variable ভাগ করে
fn checkout(limit: Int) -> Int {
    var spent = 0;
    let buy = fn(x: Int) -> Bool {
        if spent + x > limit { return false; }
        spent = spent + x;
        return true;
    };
    let left = fn() -> Int { return limit - spent; };
    print(buy(400));
    print(buy(700));
    print(buy(250));
    return left();
}
print(checkout(1000));
from haat_front import *          # lexer, parser, resolver, runtime, Walker (interp.py's shape)

class Env:                        # interp.py: one scope = a dict + a link to the enclosing Env
    made = 0
    def __init__(self, parent=None):
        self.vars, self.parent = {}, parent; Env.made += 1

class Function:                   # a closure: code (the AST node) + the Env where it was made
    def __init__(self, name, node, env): self.name, self.node, self.env = name, node, env

class ChainInterp(Walker):
    probes = lookups = 0
    def global_env(self): return Env()
    def scope(self, env): return Env(env)            # every block: a new Env
    def define(self, node, value, env): env.vars[node.name] = value
    def home(self, node, env):                       # walk the chain until the name is found
        self.lookups += 1
        while env is not None:
            self.probes += 1
            if node.name in env.vars: return env
            env = env.parent
        raise runtime_error(node.line, node.col, f"'{node.name}' is not initialized yet")
    def load(self, node, env): return self.home(node, env).vars[node.name]
    def assign(self, node, value, env): self.home(node, env).vars[node.name] = value
    def make_fn(self, f, name, env): return Function(name, f, env)   # no copying: env is shared
    def enter(self, f, args):                        # params + body share one new Env
        env = Env(f.env); env.vars.update(zip([p.name for p in f.node.params], args))
        return env

for name in ("counter.haat", "checkout.haat"):
    Env.made = 0
    out, it = run_src(ChainInterp, open(name, encoding="utf-8").read())
    print(name, "->", " ".join(out))
    print(f"   Env objects: {Env.made}, name lookups: {it.lookups}, "
          f"dict probes: {it.probes} ({it.probes / it.lookups:.2f} per lookup)")

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

counter.haat -> 1 2 10 3 112 112
   Env objects: 10, name lookups: 35, dict probes: 56 (1.60 per lookup)
checkout.haat -> true false true 350
   Env objects: 7, name lookups: 22, dict probes: 34 (1.55 per lookup)

দুটি আউটপুটই reference-এর python -B haat.py run-এর সঙ্গে হুবহু। এবার গণনা। counter.haat-এ ১০টি Env: global একটি, make_counter-এর দুই call-এর দুটি, আর closure-এর সাতটি call-এর সাতটি (a তিনবার, b একবার, add দুবার, get একবার)। ৩৫টি খোঁজায় ৫৬টি dict-পরীক্ষা, গড়ে ১.৬০. checkout.haat-এ সাতটি Env: global, checkout-এর call, তিনটি buy, একটি left, আর একটি if-block (শুধু buy(700)-এ { return false; } চলেছে)। Block-এর জন্যও নতুন Env, কারণ Haat-এ প্রতিটি { } একটি scope (decision 14).

make_fn-এর লাইনটি লক্ষ করুন: closure = Function(name, node, env), অর্থাৎ code আর তৈরির জায়গার Env-এর pointer; কোনো মান কপি হয়নি। আর enter নতুন Env-এর parent বানায় f.env-কে, ডাকার জায়গার Env-কে নয়: static scope-এর পুরো নিয়ম এই এক শব্দে। নিচের stepper counter.haat-এর প্রথম অংশ চালায়; প্রতিটি ধাপ ল্যাবের trace থেকে মেলানো।

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}10let a = make_counter(1);11let b = make_counter(10);12print(a());13print(a());14print(b());
এই ধাপে
চলতি শিকল
E1 (a-এর খাতা)
probe
  1. শুরু: global Env E0. Program চলার আগে top-level function hoist হয় (decision 17): E0-তে make_counter = একটি Function, যার env নিজেই E0. শিকলে এখন একটিই Env.
  2. make_counter(1). নাম খুঁজতে E0-তে একটি probe. তারপর enter নতুন Env E1 বানায়, parent = function-এর env (E0), আর তাতে parameter step = 1. var count = 0; E1-এ count বসায়। Parameter আর দেহের top level একই Env ভাগ করে (decision 14).
  3. Closure তৈরি। fn() -> Int { … } মূল্যায়নে একটি Function বানানো হয়: code = lambda@4:16-এর AST, env = E1 (চলতি Env). E1-এ next = সেই Function. খেয়াল করুন, E1 আর closure পরস্পরকে দেখায়: একটি reference cycle.
  4. return next. next E1-এ প্রথম probe-এই মেলে। ReturnSignal call থেকে বেরিয়ে আসে, E0-তে a = closure. E1-কে এখন আর কোনো চলমান call দেখছে না, তবু সে মরে না: a.env তাকে ধরে আছে। এটিই upward funarg-এর সমাধান।
  5. make_counter(10). একই কাজ আবার: নতুন E2 = {step=10, count=0, next}, আর E0-তে b. একই code, আলাদা খাতা। E1 এতে একটুও বদলায়নি।
  6. প্রথম a(): count = count + step. E0-তে a খুঁজে (১ probe) call: নতুন E3, parent = a.env = E1, ভেতরে কিছু নেই (parameter নেই)। ডান দিকের count: E3-এ নেই, E1-এ আছে, ২ probe; step-ও ২; লেখার সময় count-এর ঘর খুঁজতে আবার ২. E1-এ count = 1.
  7. return count. আবার ২ probe-এ count = 1. ReturnSignal(1) call-এর except-এ ধরা পড়ে, main print করে 1. E3 এখন অদরকারি, Python-এর GC তাকে সরাবে।
  8. দ্বিতীয় a(). সম্পূর্ণ নতুন E4, কিন্তু parent সেই E1. চারটি খোঁজা, প্রতিটি ২ probe, মোট ৮; সঙ্গে a খুঁজতে ১. E1-এ count = 2, ছাপা হয় 2. প্রতিটি call-এর Env ক্ষণস্থায়ী; অবস্থা থাকে E1-এ।
  9. b(). নতুন E5, parent = b.env = E2. একই চারটি খোঁজা E2-তে মেলে: count = 0 + 10 = 10. E1-এর count এখনো 2. এই অংশে মোট ২৪টি খোঁজা, ৪০টি probe (ল্যাবের trace).

কেন শিকলের খোঁজা সবসময় ঠিক ঘোষণাটি পায়

Interpreter চলার সময় একটি নাম খোঁজে শুধু তার স্ট্রিং দিয়ে। তাহলে কী নিশ্চয়তা আছে যে সে resolver-এর বেছে নেওয়া ঘোষণাটিই পাবে, একই নামের অন্য কোনোটি নয়? উত্তরটি একটি সরল কাঠামোগত সত্য:

প্রস্তাব ৫৭.১ — চলমান শিকল লেখার scope-কে অনুসরণ করে

ধরি Haat program-টি resolver পার হয়েছে। চলার যেকোনো মুহূর্তে কোনো node-এর মূল্যায়নের সময় চলতি Env থেকে parent ধরে পাওয়া Env-গুলোর তালিকা, ঠিক সেই node-কে লেখার দিক থেকে ঘিরে থাকা scope-গুলোর (ভেতর থেকে বাইরে) সঙ্গে এক-এক মেলে। ফলে home(x) যে Env-এ থামে, সেটি resolver-এর বাছা ঘোষণার scope-এরই একটি চলমান কপি, আর probe-এর সংখ্যা = ১ + মাঝের scope-এর সংখ্যা।

প্রমাণের রূপরেখা. মূল্যায়নের ধাপের ওপর induction.

  1. শুরুতে চলতি Env = E0, আর top-level statement-কে ঘিরে আছে শুধু global scope. মেলে।
  2. Block, if-শাখা, while-এর প্রতি round: interpreter Env(env) বানায়, resolver ঠিক সেখানেই একটি scope খোলে। দুই তালিকার মাথায় একটি করে যোগ হয়, মিল থাকে।
  3. Function-এর call: নতুন Env-এর parent = closure-এর env. Closure তৈরি হয়েছিল function-এর লেখার জায়গায়, তাই induction-এর অনুমানে closure-এর env-এর শিকল লেখার জায়গার scope-গুলোর সঙ্গে মেলে; তার মাথায় call-এর Env = function-এর scope. ডাকার জায়গার শিকল এখানে একেবারেই আসে না।
  4. বাকি ধাপ (মান পড়া, লেখা, ফেরা) শিকলের আকার বদলায় না; ফেরার পর আগের Env-এ ফিরে যাওয়া মানে আগের মিলে ফেরা।
  5. Resolver প্রথম মিলে যাওয়া scope বেছে নেয়, শিকলও প্রথম মিলে যাওয়া Env-এ থামে; দুই তালিকা এক বলে দুটি একই স্তর। ব্যতিক্রম একটিই: hoist-করা function একটি top-level variable-এর let চলার আগেই চললে নামটি E0-তে নেই, শিকল ফুরিয়ে যায়, আর তখন 'k' is not initialized yet (decision 18). ∎

এই প্রস্তাবের একটি সরাসরি ফল: একটি নির্দিষ্ট নাম-ব্যবহারে probe-এর সংখ্যা প্রতিবার একই, তাই সেটি compile-এর সময়েই হিসাব করে রাখা যায়। অনুশীলন ১-এ এটিই একটি ছোট cache হয়ে উঠবে, আর অংশ ৪-এ পুরো একটি নতুন environment-নকশা।

৩ · Closure object আর funarg — environment কেন heap-এ

পর্ব ১৭-এর upward funarg মনে করুন: ফেরত দেওয়া function-এর বাইরের variable-কে তার frame-এর চেয়ে বেশি দিন বাঁচতে হয়। Dict-এর শিকলে সমস্যাটি আলাদা কোড ছাড়াই মেটে, কারণ প্রতিটি Env একটি সাধারণ Python object, আর Python-এর সব object heap-এ থাকে। make_counter-এর call শেষ হলে E1 মরে না, কারণ closure-এর env তাকে দেখায়; কতদিন বাঁচবে, ঠিক করে garbage collection.

একটি সূক্ষ্মতা: E1-এর next closure-কে দেখায়, আর closure-এর env E1-কে, একটি reference cycle. CPython-এর reference counting এমন cycle একা মুক্ত করতে পারে না, তাই তার আলাদা cycle collector আছে (পর্ব ৭৫, Garbage collection). Interpreter-টি C-তে লেখা হলে আর Env-গুলো C-র stack-এ থাকলে make_counter ফেরার পর closure একটি মুছে যাওয়া ঘরকে দেখাত: পর্ব ১৭-এর C++ [&]-এর মতো dangling reference, আর তাকে ব্যবহার করা undefined behavior. তাই first-class function-এর ভাষায় environment, অন্তত যে অংশ ধরা পড়তে পারে, heap-এ রাখা হয়।

ছবি ৫৭.১ — প্রথম a() চলার মুহূর্তে দুই রকম environment

ওপরে reference interpreter-এর Env-এর শিকল, নিচে slot আর cell-এর নকশা (অংশ ৪); একই program, একই মুহূর্ত।

One moment, two representations: a chain of Envs on top; slots, flat closure and cells below ক) Env-এর শিকল · interp.py E0 · global make_counter · a · b closure a lambda@4:16 closure b lambda@4:16 E1 make_counter(1) step=1, count=0 next E2 make_counter(10) step=10, count=0 next E3 · a() চলছে { } খালি a b env env parent E1, E2-এর সব নাম বেঁচে থাকে ডটেড সবুজ তির: parent link খ) slot + cell · vm.py-র নকশা closure a lambda@4:16 cells[0] · cells[1] Cell count = 0 Cell step = 1 frame · a() slots: [ ] খালি closure make_counter-এর frame নেই; বাঁচে শুধু দুটি cell একই মান, কম জিনিস বাঁচে
ছবি ৫৭.১ — ওপরে: প্রতিটি closure একটি পুরো Env-কে দেখায় (linked closure), আর Env-গুলো parent ধরে E0 পর্যন্ত জোড়া; চলমান call-এর E3 খালি, তার parent E1. নিচে: একই মুহূর্ত VM-এর নকশায়। make_counter-এর frame মুছে গেছে, closure a রেখেছে শুধু তার দুটি free variable-এর cell (ক্রম count, step, reference-এর dis-এর captures count, step-এর মতো)। চলমান a()-এর নিজের কোনো slot নেই।

৪ · দ্বিতীয় রূপ — resolver-এর ঠিকানা, slot আর cell

প্রস্তাব ৫৭.১ বলেছে একটি নাম-ব্যবহার কোথায় মিলবে তা লেখা থেকেই জানা যায়। তাহলে চলার সময় নাম দিয়ে খোঁজার দরকারই নেই: resolver আগেই প্রতিটি ব্যবহারের পাশে একটি ঠিকানা লিখে রাখতে পারে। এই ঠিকানার ধারণাটির নাম lexical address; Haat-এর resolver প্রতিটি ঘোষণাকে একটি Binding দেয় (মালিক function, slot-এর নম্বর, global কি না, অন্য function ধরেছে কি না), আর সেখান থেকে চার রকম ঠিকানা আসে, ঠিক bytecode compiler যেমন বেছে নেয় (পর্ব ৫১-এর টেবিল):

  • GLOBAL g: top-level variable বা function; program-এর global array-র ঘর g.
  • LOCAL s: চলতি function-এর নিজের, কেউ ধরেনি; frame-এর slot s.
  • CELL s: চলতি function-এর নিজের, কিন্তু ভেতরের কোনো function ধরেছে; slot s-এ একটি cell (এক-ঘরের বাক্স)।
  • FREE i: বাইরের কোনো function-এর variable; চলতি closure-এর cell-তালিকার ঘর i.

Block-এর জন্য কোনো নতুন frame লাগে না: reference-এর resolver একটি function-এর ভেতরের সব block-এর ঘোষণাকে আলাদা slot দেয় আর slot কখনো পুনর্ব্যবহার করে না, তাই একই frame-এ সবার জায়গা হয়। নিচের ব্লক এই ঠিকানা-ব্যবস্থার মূল অংশ (SlotCore): address একবার ঠিকানা হিসাব করে node-এর গায়েই লিখে রাখে (node.addr, একটি decorated AST), আর where সেই ঠিকানা থেকে “কোন array, কোন ঘর” বের করে। Cell এখানে এক-উপাদানের একটি Python list. শেষ অংশ checkout.haat-এর প্রতিটি নাম-ব্যবহারের ঠিকানা ছাপে, function ধরে ধরে।

from haat_front import *
class SlotCore(Walker):                           # a Cell is a one-element list: box[0]
    def global_env(self):
        self.globals = [UNSET] * self.res.nglobals   # UNSET: let/var not run yet
        return Frame(None, None, self.res.nslots[None])
    def scope(self, env): return env              # a block needs no frame: its slots are distinct
    def address(self, node, owner):               # Binding -> (kind, index), once per AST node
        b = self.res.uses.get(id(node)) or self.res.decls[id(node)]
        if b.is_global: node.addr = ("GLOBAL", b.slot)
        elif b.owner is owner: node.addr = ("CELL" if b.captured else "LOCAL", b.slot)
        else: node.addr = ("FREE", free_bindings(owner, self.res).index(b))
        return node.addr
    def where(self, node, env):                   # (array, index) that holds the value
        kind, i = getattr(node, "addr", None) or self.address(node, env.owner)
        if kind == "LOCAL": return env.slots, i
        if kind == "CELL": return env.slots[i], 0
        if kind == "FREE": return env.closure.cells[i], 0
        if self.globals[i] is UNSET: raise runtime_error(node.line, node.col, f"'{node.name}' is not initialized yet")
        return self.globals, i
    def load(self, node, env): box, i = self.where(node, env); return box[i]
    def assign(self, node, value, env): box, i = self.where(node, env); box[i] = value
    def define(self, node, value, env):           # MAKE_CELL: a NEW box every time the let runs
        kind, i = getattr(node, "addr", None) or self.address(node, env.owner)
        if kind == "GLOBAL": self.globals[i] = value
        else: env.slots[i] = [value] if kind == "CELL" else value
class Frame:                                      # one per call: an array of slots, no names
    def __init__(self, owner, closure, n): self.owner, self.closure, self.slots = owner, closure, [None] * n
program, res = front(open("checkout.haat", encoding="utf-8").read())
core, todo = SlotCore(res), [(None, "<main>", program.stmts)]
def visit(n, owner):                              # decorate every name use, function by function
    if isinstance(n, (FnDecl, Lambda)): todo.append((n, getattr(n, "name", f"lambda@{n.line}:{n.col}"), n.body))
    elif isinstance(n, list) or hasattr(n, "line"):
        if isinstance(n, (Var, Assign)): print(f"  {n.name}@{n.line}:{n.col} -> {core.address(n, owner)}")
        for v in (n if isinstance(n, list) else vars(n).values()): visit(v, owner)
for owner, name, body in todo: print(name); visit(body, owner)

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

<main>
  checkout@15:7 -> ('GLOBAL', 0)
checkout
  buy@10:11 -> ('LOCAL', 2)
  buy@11:11 -> ('LOCAL', 2)
  buy@12:11 -> ('LOCAL', 2)
  left@13:12 -> ('LOCAL', 3)
lambda@4:15
  spent@5:12 -> ('FREE', 0)
  x@5:20 -> ('LOCAL', 0)
  limit@5:24 -> ('FREE', 1)
  spent@6:9 -> ('FREE', 0)
  spent@6:17 -> ('FREE', 0)
  x@6:25 -> ('LOCAL', 0)
lambda@9:16
  limit@9:37 -> ('FREE', 0)
  spent@9:45 -> ('FREE', 1)

এবার reference-এর bytecode-এর সঙ্গে মেলান। ল্যাবে python -B haat.py dis checkout.haat-এর সত্যিকারের আউটপুট থেকে দুটি closure-এর listing:

== lambda@4:15 (arity 1, locals 1) ==
   0  LOAD_FREE      0     ; spent
   1  LOAD_LOCAL     0     ; x
   2  ADD
   3  LOAD_FREE      1     ; limit
   …
  11  STORE_FREE     0     ; spent
== lambda@9:16 (arity 0, locals 0) ==
   0  LOAD_FREE      0     ; limit
   1  LOAD_FREE      1     ; spent

প্রতিটি ঠিকানা হুবহু এক: buy-এর ভেতরে spent = FREE 0, limit = FREE 1, x = LOCAL 0; left-এ উল্টো ক্রমে limit = FREE 0, spent = FREE 1, কারণ free variable-এর ক্রম প্রথম ব্যবহারের ক্রম। checkout-এর নিজের buy আর left LOCAL 2 আর LOCAL 3 (VM-এ STORE_LOCAL 2 ; buy, STORE_LOCAL 3 ; left), আর main-এ checkout GLOBAL 0. VM আর এই interpreter আলাদা যন্ত্র, কিন্তু environment-এর নকশা একই; পার্থক্য শুধু এই যে VM ঠিকানাগুলো opcode-এর argument হিসেবে লেখে (পর্ব ৫৮, Bytecode নকশা), আর এখানে সেগুলো AST-এর node-এ বসে থাকে।

এখনো বাকি তিনটি hook: closure বানানো, nested function, আর call-এর frame. make_fn হলো VM-এর MAKE_CLOSURE: নতুন function-এর প্রতিটি free variable-এর cell চলতি frame থেকে নেয় (নিজের slot হলে env.slots, বাইরের হলে চলতি closure-এর cell থেকে), আর শুধু সেগুলোর reference একটি তালিকায় রাখে। মান কপি হয় না, বাক্সের ঠিকানা কপি হয়; তাই capture by reference অক্ষত থাকে। define-এর [value] প্রতিবার একটি নতুন বাক্স বানায়, VM-এর MAKE_CELL-এর মতো। define_fn আগে খালি cell বানিয়ে তারপর closure, যাতে nested function নিজের cell ধরে নিজেকে ডাকতে পারে।

class Closure:                                    # flat closure: code + only the cells it needs
    def __init__(self, name, node, cells): self.name, self.node, self.cells = name, node, cells

class SlotInterp(SlotCore):
    def make_fn(self, f, name, env):              # MAKE_CLOSURE: copy references to the cells
        return Closure(name, f, [env.slots[b.slot] if b.owner is env.owner
                       else env.closure.cells[free_bindings(env.owner, self.res).index(b)]
                       for b in free_bindings(f, self.res)])
    def define_fn(self, s, env):                  # the cell exists before the closure (recursion)
        self.define(s, None, env); fn = self.make_fn(s, s.name, env)
        if s.addr[0] == "CELL": env.slots[s.addr[1]][0] = fn
        else: env.slots[s.addr[1]] = fn
    def enter(self, f, args):                     # parameters arrive in slots 0..n-1
        fr = Frame(f.node, f, self.res.nslots[id(f.node)])
        for p, a in zip(f.node.params, args): self.define(p, a, fr)
        return fr

REF = {"counter.haat": "1 2 10 3 112 112", "checkout.haat": "true false true 350",   # haat.py run
       "nested.haat": "936 15 7 300 3 2 1", "bazar.haat": "996 5000 3", "report.haat": "2500000"}
for name, want in REF.items():
    src = open(name, encoding="utf-8").read()
    chain, slots = (" ".join(run_src(I, src)[0]) for I in (ChainInterp, SlotInterp))
    print(f"{name:14} chain: {chain == want}  slots: {slots == want}  ({want})")

program, res = front(open("report.haat", encoding="utf-8").read())    # who keeps what alive?
ch, sl = ChainInterp(res, lambda t: None), SlotInterp(res, lambda t: None)
ch.run(program); sl.run(program)
env, kept = ch.genv.vars["report"].env, []
while env is not None: kept += env.vars.items(); env = env.parent
print("Env chain keeps:", [k for k, v in kept], "| Str chars:", sum(len(v) for k, v in kept if isinstance(v, str)))
flat = sl.globals[res.decls[id(program.stmts[1])].slot]
print("flat closure keeps:", [box[0] for box in flat.cells], "| Str chars:",
      sum(len(box[0]) for box in flat.cells if isinstance(box[0], str)))

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

counter.haat   chain: True  slots: True  (1 2 10 3 112 112)
checkout.haat  chain: True  slots: True  (true false true 350)
nested.haat    chain: True  slots: True  (936 15 7 300 3 2 1)
bazar.haat     chain: True  slots: True  (996 5000 3)
report.haat    chain: True  slots: True  (2500000)
Env chain keeps: ['n', 'log', 'total', 'i', 'make_report', 'report'] | Str chars: 2000
flat closure keeps: [2500000] | Str chars: 0

প্রথম পাঁচ লাইন একটি ছোট differential test: পাঁচটি program, দুই রকম environment, প্রত্যাশিত আউটপুট reference-এর run থেকে। সব True. সবচেয়ে কঠিন nested.haat: নিজেকে ডাকা nested function (go, যা define_fn-এর নিয়মে চলে) আর loop-এ বানানো closure-এর শিকল। শেষ দুই লাইন অংশ ৬-এর বিষয়।

ল্যাবে পরীক্ষাটি বড় করে চালানো হয়েছে (CPython 3.14.4): reference-এর static error-হীন ১০টি উদাহরণ, দুই environment-এ (২০টি run), আর একটি seeded generator-এর ৫০০টি random Haat program (var, nested fn, loop-এর closure, counter-ধরনের factory, / আর %). প্রতিটি চলেছে চারটি বাস্তবায়নে: reference-এর interp.py ও vm.py, আর এই পাতার দুটি। ফল: ২০/২০ সমান; ৫০০টির ৫০০টিতেই চারটির আউটপুট অক্ষরে অক্ষরে এক (২১৯২টি লাইন; ১৫৪টি program runtime error-এ থামে, তার অবস্থান আর বার্তাও মিলেছে)।

নিচের stepper slot-নকশায় checkout(1000) চালায়। দেখুন কীভাবে দুটি closure একই দুটি বাক্স ভাগ করে, শুধু ভিন্ন ক্রমে। C1, C2 নাম দুটি বোঝার সুবিধার জন্য; প্রতিটি ধাপের মান ল্যাবের trace থেকে মেলানো।

2fn checkout(limit: Int) -> Int {3    var spent = 0;4    let buy = fn(x: Int) -> Bool {5        if spent + x > limit { return false; }6        spent = spent + x;7        return true;8    };9    let left = fn() -> Int { return limit - spent; };10    print(buy(400));11    print(buy(700));12    print(buy(250));13    return left();
এই ধাপে
checkout-এর slot
closure-এর cells
এই ধাপের কাজ
  1. Call-এর frame. enter চারটি slot-এর একটি frame বানায় (resolver গুনেছে: limit, spent, buy, left). limit একটি parameter, কিন্তু দুটি closure তাকে ধরে, তাই তার ঠিকানা CELL 0: argument 1000 সরাসরি slot-এ না বসে একটি নতুন বাক্স C1-এ যায় (VM-এ LOAD_LOCAL 0; MAKE_CELL 0).
  2. var spent = 0. spent-কেও ধরা হয়েছে, তাই CELL 1: slot 1-এ নতুন বাক্স C2, ভেতরে 0. এখনো কোনো closure নেই; frame নিজেই দুটি বাক্সের মালিক।
  3. buy তৈরি। free_bindings buy-এর দেহে প্রথম ব্যবহারের ক্রমে বাইরের নাম খোঁজে: spent, তারপর limit (x buy-এর নিজের)। make_fn slot 1 আর slot 0 থেকে বাক্স দুটির reference নিয়ে closure বানায়: cells = [C2, C1]. buy নিজে কারও ধরা নয়, তাই slot 2-এ সরাসরি (LOCAL 2).
  4. left তৈরি। left-এর দেহে আগে limit, পরে spent, তাই cells = [C1, C2]. দুটি closure-এর তালিকা ভিন্ন, কিন্তু ভেতরের বাক্স একই দুটি। এটিই ভাগ করা অবস্থার রহস্য: ভাগ হয় বাক্স, তালিকা নয়।
  5. buy(400). নতুন frame, slot 0-এ x = 400. spent = FREE 0 = cells[0][0] = C2-এর 0; limit = FREE 1 = C1-এর 1000. 400 > 1000 মিথ্যা, তাই spent = spent + x: FREE 0-এ লেখা মানে C2-এর ভেতরে 400. checkout-এর slot 1-ও এখন 400 দেখায়, কারণ সেটিও C2. ছাপা হয় true.
  6. buy(700). 400 + 700 = 1100 > 1000, তাই return false;. C2 বদলায়নি। Slot-নকশায় if-block-এর জন্য কোনো নতুন frame বা Env তৈরি হয়নি (scope একই frame ফেরত দেয়); dict-এর শিকলে এখানে একটি Env বানাতে হয়েছিল।
  7. buy(250). 400 + 250 = 650 ≤ 1000: C2-এ 650. ছাপা হয় true. প্রতিটি buy-call-এর frame ক্ষণস্থায়ী, অবস্থা থাকে C2-এ।
  8. left(). FREE 0 এখন C1 (1000), FREE 1 হলো C2 (650): 1000 − 650 = 350. left কখনো buy-কে দেখেনি, তবু buy-এর প্রতিটি বদল দেখেছে, কারণ দুজনের হাতে একই বাক্স। main ছাপে 350, reference-এর সঙ্গে হুবহু।

৫ · Array frame আর static link — আর loop-এর closure-এর ফাঁদ

Compiler-এর পাঠ্যবইয়ের ক্লাসিক নকশা আরেকটু সরল: প্রতিটি call-এর জন্য slot-এর একটি array, আর বাইরের function-এর frame-এ যাওয়ার জন্য একটি static link. Lexical address হয় জোড়া (কত frame বাইরে, কোন slot). Closure হলে frame-টি heap-এ রাখতে হয়, আর closure রাখে code + বাইরের frame-এর pointer: cell-এর কোনো দরকার নেই, কারণ সবাই সরাসরি frame-এর slot পড়ে-লেখে, তাই ভাগ করা অবস্থা আপনিই ঠিক থাকে। এটি SICP বইয়ের compiler-এর “lexical addressing”-এর মূল ধারণা (অংশ ৫.৫.৬)। তাহলে Haat-এর VM কেন cell নিয়ে এত ঝামেলা করে?

উত্তর decision 14-এর শেষ বাক্যে: “A while body is a fresh scope on every round, so a closure created in the loop captures that round's variables.” Loop-এর দেহের let k প্রতি round-এ একই slot পায়। Closure পুরো frame-এর pointer রাখলে প্রথম আর তৃতীয় round-এর closure একই slot দেখবে, অর্থাৎ শেষ round-এর k; spec চায় প্রতিটি নিজের round-এর k. Cell-ব্যবস্থায় প্রতি round-এ define একটি নতুন বাক্স বানিয়ে slot-এ রাখে, আর আগের round-এর closure পুরোনো বাক্সটি ধরে থাকে। Slot একই, বাক্স আলাদা।

// each loop round gets a fresh `k`, so each closure keeps its own
var fs = fn() -> Int { return 0; };
var r = 0;
while r < 3 {
    let k = r * 100;
    let old = fs;
    fs = fn() -> Int { return old() + k; };
    r = r + 1;
}
print(fs());

Reference-এর nested.haat-এর এই অংশ 300 ছাপে: তিনটি closure-এর শিকল, প্রতিটি নিজের round-এর old আর k ধরে (0 + 100 + 200). Frame-এর pointer রাখা নকশায় শেষ closure-এর old নিজের দিকেই ফিরত, তাই নিজেকে অবিরাম ডাকা আর ১০০০ call পার হলে stack overflow; কোন ভুল কোড ঠিক এটি করে, অনুশীলন ২-এ খুঁজবেন। নীতিটি: একটি variable-এর পরিচয় (কোন বাক্স) আর ঠিকানা (কোন slot) এক জিনিস নয়।

ছোট optimization, বড় ভুল: “Loop-এর প্রতি round-এ নতুন Env বা নতুন cell বানানো অপচয়, একবার বানিয়ে আবার ব্যবহার করি” ধরনের পরিবর্তন সাধারণ পরীক্ষায় প্রায় সবসময় পাস করে, কারণ বেশিরভাগ program loop-এর closure-কে পরের round পর্যন্ত বাঁচিয়ে রাখে না। ল্যাবের ৫০০টি random program-ও এমন একটি ভুল ধরেনি (অনুশীলন ২)। নিরাপদ পথ: এমন optimization-এর আগে আলাদা করে লেখা পরীক্ষা, যেখানে loop-এ বানানো closure পরে ডাকা হয়, আর তার ফল reference-এর সঙ্গে মেলানো।

৬ · Interpreter-এর Env বনাম VM-এর cell — কী বাঁচে, কতদিন

দুই নকশার আচরণ এক (অংশ ৪-এর পরীক্ষা), কিন্তু খরচ আলাদা। নিচের টেবিল reference-এর দুই back end-কে পাশাপাশি রাখে; ডান কলামের প্রতিটি কথা vm.py আর compiler.py-র কোড থেকে নেওয়া।

প্রশ্নinterp.py (Env-এর শিকল)vm.py (slot + cell)
নাম কখন ঠিকানা পায়চলার সময়, প্রতিবার, string দিয়েcompile-এর সময়, একবার (resolver + compiler)
নতুন scope-এর দামপ্রতিটি block আর call-এ একটি Env (dict)শুধু call-এ একটি frame; block-এ কিছুই না
Closure তৈরির দামএকটি pointer (চলতি Env)প্রতিটি free variable-এর জন্য একটি reference কপি
Closure কী বাঁচিয়ে রাখেতৈরির জায়গার Env আর তার সব পূর্বপুরুষ, সব নামসহশুধু free variable-এর cell
ধরা নয় এমন localEnv-এ, অন্য সবার মতোইসরাসরি slot-এ, বাক্স ছাড়া
Globalশিকলের শেষ Env-এ, নাম ধরেglobals list-এর ঘর; না বসলে UNSET
Debugger-এর চোখেপ্রতিটি নাম আর মান Env-এ দেখা যায়নাম শুধু local_names/free_names-এ, dis-এর জন্য

চতুর্থ সারিটি সবচেয়ে কম চোখে পড়ে, অথচ বড় program-এ সবচেয়ে দামি। অংশ ৪-এর শেষ ব্লকের শেষ দুই লাইন এটিই মেপেছে। report.haat-এ make_report(2000) একটি ২০০০ অক্ষরের খাতা (log) বানায়, কিন্তু ফেরত দেওয়া closure ব্যবহার করে শুধু total:

// বাজারঘর: বড় খাতা বানিয়ে শুধু মোট ফেরত দেওয়া closure
fn make_report(n: Int) -> () -> Int {
    var log = "";
    var total = 0;
    var i = 0;
    while i < n {
        log = log + "#";
        total = total + 1250;
        i = i + 1;
    }
    return fn() -> Int { return total; };
}
let report = make_report(2000);
print(report());

Env-এর শিকলে closure-এর env হলো make_report-এর call-এর Env (n, log, total, i), তার parent global Env. তাই closure যতদিন বাঁচবে, ২০০০ অক্ষরের log-ও বাঁচবে, যদিও কখনো পড়া হবে না। Flat closure রেখেছে একটি cell, ভেতরে 2500000. এই গুণের নাম safe for space: closure-এর কারণে শুধু তা-ই বাঁচে, যা সে সত্যিই ব্যবহার করতে পারে। ধারণাটি Andrew Appel আর Zhong Shao-র SML/NJ-বিষয়ক কাজে (যেমন ১৯৯৪ সালের “Space-Efficient Closure Representations”) নির্দিষ্ট রূপ পায় বলে সাধারণত উল্লেখ করা হয়। বাস্তবের JavaScript-এ এমন leak-এর সতর্কবার্তা পর্ব ১৭-এর অংশ ৮-এ; নিজের engine-এ profiler দিয়ে মেপে নিশ্চিত হোন।

Flat নকশার দাম দেখা যায় ডিবাগ করার সময়: closure যা ধরেনি, তা আর কোথাও নেই। left-এর ভেতরে থেমে buy-এর মান দেখা যায় শুধু Env-এর শিকলে (E1-এ); ভাবনার প্রশ্ন ৩ এই টানাপোড়েন নিয়ে।

৭ · গতি — নাম খোঁজা বনাম slot পড়া

Slot-এর নকশার মূল প্রতিশ্রুতি গতি: string-এর hash, dict-এর তুলনা আর শিকলে হাঁটার বদলে একটি array-র ঘর। নিচের stepper buy(400)-এর শর্ত spent + x > limit-এর তিনটি নাম দুই নকশায় পাশাপাশি পড়ে; probe-সংখ্যা অংশ ২-এর trace থেকে।

4    let buy = fn(x: Int) -> Bool {5        if spent + x > limit { return false; }6        spent = spent + x;7        return true;
এই ধাপে
dict-এর শিকল
slot-এর পথ
মোট কাজ
  1. শুরুর অবস্থা। buy(400) চলছে। শিকল-নকশায় চলতি Env E2-তে শুধু x; parent E1 হলো checkout-এর call-এর Env. Slot-নকশায় buy-এর frame-এ একটি slot (x = 400), আর closure-এর দুটি cell.
  2. spent, প্রথম চেষ্টা। শিকল: "spent" স্ট্রিংটির hash নিয়ে E2-এর dict-এ খোঁজা; নেই। Slot: কোনো খোঁজাই নেই; প্রথম চলার সময় address node-এ FREE 0 লিখে রেখেছে, এখন শুধু সেটি পড়া।
  3. spent পাওয়া গেল। শিকল: parent E1-এ দ্বিতীয় probe-এ মেলে, মান 0. Slot: cells[0] হলো C2, তার ভেতর থেকে 0: একটি list-index আর একটি বাক্স খোলা।
  4. x. শিকল: E2-তেই প্রথম probe-এ। Slot: LOCAL 0, frame-এর slot 0 থেকে সরাসরি 400; ধরা নয় বলে কোনো বাক্সও নেই।
  5. limit. শিকল: E2-তে না, E1-এ হ্যাঁ, আরও দুই probe; তিনটি নামে মোট পাঁচ। Slot: FREE 1, অর্থাৎ C1 থেকে 1000; তিনটি নামে তিনটি ঘর-পড়া, তার দুটিতে বাক্স খোলা।
  6. বড় ছবি। নিচের এক লাখ round-এর benchmark-এ মোট 850003টি নাম-ব্যবহার। শিকল-নকশায় তাতে 1850003টি probe, কারণ while আর if-এর ভেতর থেকে global খুঁজতে তিনটি Env পার হতে হয়। Slot-নকশায় একই 850003টি ব্যবহার, প্রতিটি একটি array-ঘর।

Probe গোনা যন্ত্র-নিরপেক্ষ, কিন্তু আসল প্রশ্ন সময়। ল্যাবে CPython 3.14.4-এ দুটি সত্যিকারের মাপ (একটি যন্ত্রের উদাহরণ মাত্র)। প্রথমটি benchmark-এর সবচেয়ে ছোট রূপ: চার Env-এর শিকলে একটি খোঁজা বনাম list-এর একটি ঘর, timeit-এ দশ লাখবার, পাঁচবারের সেরা। দ্বিতীয়টি পুরো program bench.haat: একই Walker-এর দুই interpreter (গণনার লাইন বাদ দিয়ে ChainFast আর SlotFast) আর reference-এর দুই back end, প্রতিটি সাতবার, median:

// বাজারঘর: এক লাখ round, অর্ধেক round-এ closure ডাকা
fn make_counter(step: Int) -> () -> Int {
    var count = 0;
    return fn() -> Int { count = count + step; return count; };
}
let tick = make_counter(3);
var i = 0;
var s = 0;
while i < 100000 {
    if i % 2 == 0 { s = s + tick(); } else { s = s - 1; }
    i = i + 1;
}
print(s);
~/haat $ python -B bench_final.py    # CPython 3.14.4, এক কম্পিউটার
dict chain, 4 Envs   89 ns per lookup
list index           23 ns per lookup
ChainFast                  0.715 s  3750025000
SlotFast                   0.575 s  3750025000
reference interp.py        0.558 s  3750025000
reference vm.py            0.570 s  3750025000

একটি খোঁজায় পার্থক্য প্রায় চার গুণ, কিন্তু পুরো program-এ সময় কমেছে মাত্র এক-পঞ্চমাংশের মতো (0.72 থেকে 0.58 সেকেন্ড)। কারণ tree-walker-এর বেশিরভাগ সময় যায় অন্য কাজে: isinstance-এর সারি, Python-এর method call, পূর্ণসংখ্যার wrap. আরও শিক্ষণীয়: Python-এ লেখা reference-এর VM এখানে tree-walker-এর চেয়ে দ্রুত নয় (0.570 বনাম 0.558, মাপের স্বাভাবিক ওঠানামার মধ্যেই)। Bytecode নিজে গতি আনে না; প্রতিটি নির্দেশ চালানোর খরচ (dispatch) কমলে তবেই আনে। এর বিস্তার পর্ব ৫৯ আর ৬১-এ (JIT compilation).

যখন ঠিকানা আগে জানাই যায় না — JavaScript-এর with আর eval

Slot-নকশা একটি শর্তে দাঁড়িয়ে: program লেখা দেখেই প্রতিটি নামের ঘোষণা জানা যায় (প্রস্তাব ৫৭.১)। কোনো ভাষা যদি চলার সময় নতুন নাম ঢোকাতে দেয়, শর্তটি ভাঙে। JavaScript-এর পুরোনো (sloppy) mode-এ ঠিক এমন দুটি দরজা আছে। নিচের কোড ব্রাউজারের JavaScript-এ চলে:

// sloppy-mode JavaScript: which binding does the name `rate` mean? Known only at run time.
function price(total, rules) {
  var rate = 5;                              // an ordinary local of price ...
  with (rules) {                             // ... but inside `with`, rules is searched first
    return total - total * rate / 100;
  }
}
console.log("price(1000, {})          ->", price(1000, {}));
console.log("price(1000, {rate: 10})  ->", price(1000, { rate: 10 }));

function fee(code) {
  var base = 60;
  eval(code);                                // direct eval may add a NEW local while fee runs
  return base + (typeof extra === "undefined" ? 0 : extra);
}
console.log('fee("")                  ->', fee(""));
console.log('fee("var extra = 40;")   ->', fee("var extra = 40;"));
console.log('fee("base = 0;")         ->', fee("base = 0;"));

// strict mode closes both doors, so every name can get a fixed place before running
try { new Function('"use strict"; with ({}) {}'); }
catch (e) { console.log("strict + with            ->", e.name); }
const strictFee = new Function("code",
  '"use strict"; var base = 60; eval(code); return typeof extra;');
console.log('strict fee: typeof extra  ->', strictFee("var extra = 40;"));

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

price(1000, {})          -> 950
price(1000, {rate: 10})  -> 900
fee("")                  -> 60
fee("var extra = 40;")   -> 100
fee("base = 0;")         -> 0
strict + with            -> SyntaxError
strict fee: typeof extra  -> undefined

price-এর একই rate প্রথম call-এ local variable (5, তাই 950), দ্বিতীয় call-এ rules-এর property (10, তাই 900). কোনটি, তা জানা যায় শুধু চলার মুহূর্তে object দেখে; তাই engine এই নামকে আগে থেকে slot দিতে পারে না। fee-এ direct eval চলার সময় নতুন local extra ঘোষণা করেছে (100), আর base = 0; function-এর local বদলেছে (0). Strict mode দুই দরজাই বন্ধ করে: with মানেই SyntaxError, আর strict eval-এর ঘোষণা নিজের scope-এ থাকে (typeof extra = "undefined"). Haat-এ eval বা with নেই; এটিই তার slot-নকশাকে সম্ভব করে। eval-এর নিরাপত্তার দিক পর্ব ১২-এ, JavaScript-এর scope chain JavaScript কোর্সের পর্ব ২২-এ।

আরও গভীরে: Environment-কে যন্ত্রের অবস্থার অংশ হিসেবে প্রথম স্পষ্টভাবে লেখেন Peter Landin, ১৯৬৪ সালের “The Mechanical Evaluation of Expressions” প্রবন্ধের SECD machine-এ: Stack, Environment, Control, Dump. পরে R. Kent Dybvig-এর ১৯৮৭ সালের PhD থিসিস “Three Implementation Models for Scheme” দেখায়, Scheme-এর মতো ভাষায়ও সব frame heap-এ রাখার দরকার নেই: frame stack-এ রেখে শুধু ধরা variable-কে বাক্সে তোলা আর closure-এ তাদের কপি রাখা (তাঁর ভাষায় display closure) একটি দ্রুত stack-ভিত্তিক মডেল দেয়। Haat VM-এর cell আর flat closure মূলত সেই ধারারই সরল রূপ।

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

  • Interpreter-এ environment কীভাবে বানাবেন? প্রতিটি scope একটি map আর বাইরের scope-এর link; lookup শিকল ধরে, define চলতি map-এ, assign যে map-এ নাম মেলে সেখানে।
  • Closure-এর runtime রূপ কী? Code (AST node বা bytecode) আর environment-এর pointer, বা flat রূপে শুধু free variable-এর cell-এর তালিকা।
  • Environment কেন heap-এ রাখতে হয়? ফেরত দেওয়া closure (upward funarg) তার জন্মের frame-এর চেয়ে বেশি বাঁচে; stack-এ রাখলে frame মুছে যেত।
  • Lexical addressing কী, লাভ কী? নামের বদলে (কত স্তর বাইরে, কোন slot) জোড়া, compile-এর সময় হিসাব করা; চলার সময় string খোঁজা লাগে না।
  • Loop-এর ভেতরের closure কেন নিজের round-এর মান দেখে? প্রতি round-এ ঘোষণা চললে নতুন বাক্স (cell) বা নতুন Env হয়; slot একই থাকলেও বাক্স আলাদা।

৮ · AI-এর যুগে environment আর closure-এর বাস্তবায়ন

“একটি ছোট interpreter লিখে দাও” বললে AI assistant কয়েক সেকেন্ডে চলার মতো কোড দেয়, আর environment-অংশেই সবচেয়ে সূক্ষ্ম ভুলগুলো লুকিয়ে থাকে, কারণ সহজ পরীক্ষায় সেগুলো ধরা পড়ে না। বারবার দেখা ভুল:

AI-এর ভুলকীভাবে ধরবেন
Call-এর নতুন environment-এর parent বানানো ডাকার জায়গার environment (dynamic scope), closure-এর environment নয়বাইরে একই নামের আলাদা variable রেখে closure অন্য function-এর ভেতর থেকে ডাকুন; ফল reference-এর সঙ্গে মেলান
Closure তৈরির সময় environment-এর কপি নেওয়া (dict copy), ফলে পরের বদল দেখা যায় নাপর্ব ১৭-এর মতো দুটি closure দিয়ে একটি variable ভাগ করে পরীক্ষা: একটি বদলায়, অন্যটি পড়ে
“Optimization”: loop-এর জন্য একটি environment বা একটি cell বারবার ব্যবহারLoop-এ closure বানিয়ে পরে ডাকার পরীক্ষা; nested.haat-এর মতো golden file
Assignment-এ নতুন binding চলতি scope-এ বানানো, বাইরের variable বদলানোর বদলেvar বাইরে রেখে ভেতরের block থেকে বদলে বাইরে ছাপুন
Slot-ভিত্তিক বাস্তবায়নে free variable-এর ক্রম বা captured চিহ্ন ভুল, ফলে ভুল cell পড়ানিজের ঠিকানা-টেবিল reference-এর dis-এর LOAD_FREE/captures-এর সঙ্গে মেলান
গতির দাবি (“slot দশ গুণ দ্রুত”) কোনো মাপ ছাড়ানিজের যন্ত্রে timeit আর পুরো program দুটিই মাপুন; একটি খোঁজার লাভ পুরো program-এর লাভ নয়

AI-কে ভালোভাবে কাজে লাগানোর উপায়: কোড চাওয়ার সঙ্গে সঙ্গে পরীক্ষা আর ঝুঁকির তালিকা চাওয়া, আর নিজে চালিয়ে মেলানো।

আমি Haat নামের একটি ছোট ভাষার tree-walking interpreter-এ environment আর closure বানাচ্ছি (static scope, block scope, closure by reference, while-এর প্রতি round-এ নতুন scope). নিচের কাজগুলো করো: ১. প্রতিটি scope-কে একটি dict আর parent link দিয়ে Env class লেখো; define, lookup আর assign আলাদা method-এ রাখো। Call-এর নতুন Env-এর parent কোনটি হবে, এক লাইনে কারণসহ বলো। ২. এমন পাঁচটি ছোট test program লেখো যা এই ভুলগুলো ধরবে: dynamic scope, closure-এ environment কপি করা, assignment-এ নতুন binding তৈরি, loop-এর জন্য একটি Env পুনর্ব্যবহার, আর দুটি closure-এর একটি variable ভাগ। প্রতিটির প্রত্যাশিত আউটপুট আলাদা করে লেখো; আমি reference বাস্তবায়নে চালিয়ে মেলাব, তাই নিশ্চিত না হলে "অনুমান" লেখো। ৩. একই interpreter-এর slot আর cell-ভিত্তিক রূপ কেমন হবে, কোন তথ্য resolver থেকে লাগবে, তার তালিকা দাও। ৪. গতির কোনো সংখ্যা বানিয়ে দেবে না; কীভাবে মাপব শুধু সেটি বলো।

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

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

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

প্র ০১প্রথম দিকের Scheme বাস্তবায়ন সব frame heap-এ রাখত। পরে কীভাবে stack-এ ফেরা গেল, আর Haat VM সেই গল্পের কোথায়?

Scheme (১৯৭৫) প্রথম থেকেই lexical scope আর পূর্ণ closure চেয়েছিল, পরে call/cc-এর মতো control-ও যোগ হয়। এমন ভাষায় frame কখন মরবে, তা stack-এর LIFO নিয়মে বলা যায় না: closure frame-এর variable ধরে রাখে, continuation পুরো frame-শিকলই ধরে রাখতে পারে। সবচেয়ে সরল আর নিশ্চিতভাবে ঠিক সমাধান ছিল সব frame heap-এ রাখা, আর বাকিটা garbage collector-এর হাতে দেওয়া। এই পর্বের Env-এর শিকল ঠিক এই “heap-ভিত্তিক মডেল”-এর ছোট রূপ।

দাম ছিল গতি: প্রতিটি call-এ heap-এ allocation, আর পরে GC-র কাজ। R. Kent Dybvig তাঁর ১৯৮৭ সালের থিসিস “Three Implementation Models for Scheme”-এ তিনটি মডেল পাশাপাশি রাখেন: heap-ভিত্তিক, stack-ভিত্তিক আর একটি string-ভিত্তিক (বিশেষ হার্ডওয়্যারের জন্য)। Stack-ভিত্তিক মডেলের মূল কৌশল দুটি। প্রথমত, যে variable কখনো assignment পায় না, closure তার মান সরাসরি কপি করে নিতে পারে, কারণ কপি আর আসল কখনো আলাদা হবে না। দ্বিতীয়ত, যে variable assignment পায় আর ধরা পড়ে, শুধু তাকে একটি heap-বাক্সে তোলা হয়, আর frame থেকে আর closure থেকে দুই জায়গা থেকেই সেই বাক্স দেখা হয়। ফলে frame আবার stack-এ ফিরতে পারে।

Haat VM এই নকশার আরেকটু সরল রূপ: ধরা প্রতিটি local (let হোক বা var) cell পায়, ধরা না হলে সরাসরি slot-এ থাকে। পর্ব ১৭-এর অনুশীলন ৪-এ যে প্রমাণ দেখেছেন (কখনো না বদলানো variable কপি করলেও আচরণ একই), সেটি Dybvig-এর প্রথম কৌশলকে বৈধ করে; Haat reference সেই optimization করে না, তবে চাইলে let-এর জন্য করা যেত। Lua-র open/closed upvalue (পর্ব ১৭) একই সমস্যার তৃতীয় সমাধান: frame stack-এ থাকা পর্যন্ত বাক্সই লাগে না।

মূল উপলব্ধি: “সব heap-এ” নকশা ভুল নয়, শুধু ধীর। ভালো বাস্তবায়ন সেই সরল নকশার আচরণ হুবহু রেখে খরচ কমায়, আর সেজন্য দরকার কোন variable বদলায় আর কোনটি ধরা পড়ে, সেই compile-time তথ্য।

প্র ০২CPython function-এর local-কে array-তে রাখে, কিন্তু module-এর নাম dict-এ। exec আর locals() এই নকশার সঙ্গে কীভাবে মানিয়ে চলে?

CPython-এর compiler একটি function compile করার সময়েই জানে কোন নাম local, কোনটি বাইরের function-এর (cell বা free variable), আর কোনটি global. Local-গুলো frame-এর একটি array-তে থাকে আর LOAD_FAST-এর মতো নির্দেশ সংখ্যা দিয়ে পড়ে; ধরা variable cell-এ, পড়া হয় LOAD_DEREF দিয়ে (পর্ব ১৭-এর সত্যিকারের dis). এটি এই পর্বের slot-নকশারই রূপ। কিন্তু module-এর top level আর class-এর দেহে নামগুলো একটি dict-এ থাকে, কারণ সেখানে নাম চলার সময় যোগ হতে পারে, বাইরে থেকে import বা setattr দিয়ে বদলাতে পারে। Global খুঁজতে তাই dict লাগে, যদিও সাম্প্রতিক version সেই খোঁজার ফল cache করে বলে জানা যায়।

এখন exec. Python 2-তে exec একটি statement ছিল, আর function-এর ভেতরে সেটি এমনভাবে নতুন local তৈরি করতে পারত যে compiler-এর array-নকশা ভেঙে যেত; nested function-এর free variable থাকলে এমন exec লিখলে Python 2 একটি SyntaxError দিত বলে মনে রাখা হয়। Python 3-এ exec একটি সাধারণ function, আর function-এর ভেতরে চালালে সে নতুন নাম লেখে একটি আলাদা dict-এ; function-এর compile-করা কোড সেই নাম কখনো দেখে না। ভাষা নিজেকে বদলে slot-নকশাকে রক্ষা করেছে।

locals()-এর গল্পও একই রকম। Function-এর local array-তে থাকলে locals()-কে একটি dict বানিয়ে দিতে হয়, আর সেই dict বদলালে array বদলায় কি না, তা বহু বছর অস্পষ্ট ছিল, debugger-এর জন্য বিশেষ করে। PEP 667 (Python 3.13) নিয়মটি স্পষ্ট করে: function-এর ভেতরে locals() প্রতিবার একটি স্বাধীন snapshot দেয়, আর debugger-এর জন্য frame-এর f_locals একটি proxy, যেখানে লেখা সত্যিই local-এ পৌঁছায়।

JavaScript-এর with আর direct eval (অংশ ৭) একই টানাপোড়েনের অন্য সমাধান: ভাষা দরজা খোলা রাখল, কিন্তু strict mode দিয়ে বন্ধ করার উপায় দিল।

মূল উপলব্ধি: দ্রুত environment-এর নকশা ভাষার একটি প্রতিশ্রুতির ওপর দাঁড়ায়: নাম চলার সময় হঠাৎ জন্মায় না। যে বৈশিষ্ট্য এই প্রতিশ্রুতি ভাঙে, ভাষাকে হয় তার জন্য ধীর পথ রাখতে হয়, নয় বৈশিষ্ট্যটিকে সীমিত করতে হয়।

প্র ০৩Flat closure memory বাঁচায়, কিন্তু debugger-এর কাজ কঠিন করে। এই টানাপোড়েন বাস্তবায়নকারীরা কীভাবে সামলান?

অংশ ৬-এ দেখেছেন, flat closure শুধু free variable-এর cell রাখে, আর বাকি সব (এখানে ২০০০ অক্ষরের log) মুক্ত হয়ে যায়। Memory-র জন্য এটি আদর্শ, কিন্তু একজন প্রোগ্রামার যখন closure-এর ভেতরে থেমে চারপাশের variable দেখতে চান, তখন যে variable closure ধরেনি তার মান আর কোথাও নেই। Env-এর শিকলে সব আছে, কারণ পুরো Env বেঁচে আছে।

বাস্তবের ব্যবস্থাগুলো কয়েকভাবে আপস করে। অনেক debugger closure-এর scope দেখায় শুধু ধরা variable দিয়ে, আর বাকিগুলোর জন্য “পাওয়া যাচ্ছে না” বা “optimized out” ধরনের বার্তা দেয়; C আর C++-এর optimize-করা কোডে gdb-র “<optimized out>” এই পরিবারের সবচেয়ে চেনা উদাহরণ। কিছু runtime debugger খোলা থাকলে বা debug mode-এ চললে optimization কমিয়ে দেয়, যাতে বেশি variable বাঁচে; খুঁটিনাটি engine আর version ভেদে আলাদা, তাই নিজের tool-এর documentation দেখে নিশ্চিত হওয়া দরকার। আরেকটি পথ debug information: কোন মুহূর্তে কোন variable কোথায়, তার আলাদা টেবিল।

Haat reference-এ এর একটি ছোট রূপ আছে: VM-এর Code object-এ local_names আর free_names রাখা হয় শুধু dis-এর জন্য, যাতে slot-নম্বরের পাশে নাম দেখানো যায়। চলার সময় VM এই নাম কখনো পড়ে না। একটি Haat debugger বানাতে চাইলে এই টেবিলই হবে তার ভিত্তি, আর যে variable কোনো closure ধরেনি, function ফিরে যাওয়ার পর তাকে দেখানোর কোনো উপায় থাকবে না।

উল্টো দিক থেকেও বিপদ আছে: শুধু debugger-এর সুবিধার জন্য সব environment বাঁচিয়ে রাখলে program-এর memory-র আচরণ debug আর release-এ আলাদা হয়ে যায়, আর debug-এ যে leak নেই, release-এ সেটি দেখা দিতে পারে, বা উল্টো। তাই নিয়মটি সাধারণত হয়: আচরণ (আউটপুট) একই থাকবে, শুধু পর্যবেক্ষণের সুবিধা কমবে-বাড়বে।

মূল উপলব্ধি: Environment-এর নকশা শুধু program চালানোর জন্য নয়, program বোঝার জন্যও। কতটুকু তথ্য বাঁচিয়ে রাখবেন, সেই সিদ্ধান্তে memory, গতি আর debug করার সুবিধা একসঙ্গে টানাটানি করে।

প্র ০৪Lexical address, de Bruijn index আর resolver-এর slot কি একই ধারণা? মিল আর অমিল কোথায়?

Nicolaas de Bruijn ১৯৭২ সালে lambda calculus-এর জন্য একটি লেখার পদ্ধতি প্রস্তাব করেন, যেখানে bound variable-এর নামের বদলে একটি সংখ্যা লেখা হয়: কত স্তর বাইরের λ তাকে বেঁধেছে। λx. λy. x হয়ে যায় λ. λ. 1 (শূন্য থেকে গুনলে)। উদ্দেশ্য: নাম বদলের (α-conversion) ঝামেলা দূর করা, যাতে দুটি term অক্ষরে অক্ষরে তুলনা করলেই চলে (পর্ব ৪৩)।

Compiler-এর lexical address একই ধারণার প্রকৌশল-রূপ। SICP বইয়ের compiler অধ্যায়ে (অংশ ৫.৫.৬) প্রতিটি variable-কে একটি জোড়া দেওয়া হয়: frame number (কত frame বাইরে) আর displacement (সেই frame-এর কোন ঘর)। এটি de Bruijn index-এর মতোই “কত স্তর বাইরে”, শুধু একটি স্তরে কয়েকটি নাম থাকতে পারে বলে দ্বিতীয় একটি সংখ্যা লাগে। পর্ব ৩০-এর static chain-এর হিসাব ঠিক এই জোড়া নিয়েই চলে।

Haat-এর resolver আরও এক ধাপ এগোয়। Slot-এর নম্বর পুরো function-এর ভেতরে অনন্য, তাই block-এর স্তর গুনতে হয় না; আর বাইরের function-এর variable-এর জন্য “কত স্তর বাইরে” গোনার বদলে flat closure তাকে নিজের তালিকার একটি নম্বর (FREE i) দেয়। ফলে চলার সময় কোনো শিকলে হাঁটা নেই; দাম দিতে হয় closure তৈরির সময়। তিনটির মিল: নামকে compile-এর সময়েই একটি অবস্থানে বদলে ফেলা।

অমিলও গুরুত্বপূর্ণ। de Bruijn index শুধু bound variable-এর পরিচয়, কোনো memory-র ঘর নয়; lexical address frame-এর ঘর দেখায়, যা বদলাতে পারে; আর Haat-এর CELL/FREE ঠিকানা একটি বাড়তি স্তর (বাক্স) যোগ করে, যাতে loop-এর প্রতি round-এ নতুন পরিচয় জন্মাতে পারে (অংশ ৫)। অর্থাৎ “কোথায় খুঁজব” আর “কোন পরিচয়” আলাদা প্রশ্ন, আর বাস্তবায়নকে দুটিরই উত্তর দিতে হয়।

মূল উপলব্ধি: নামকে সংখ্যায় বদলানো গণিত আর প্রকৌশল দুই জগতেরই পুরোনো কৌশল। গণিতে এটি তুলনা সহজ করে, compiler-এ চলার সময় বাঁচায়; আর দুই ক্ষেত্রেই কাজটি করা হয় একবার, ব্যবহারের আগে।

প্র ০৫Interpreter-এর গতি বাড়াতে environment কতটা গুরুত্বপূর্ণ? এই পর্বের মাপ থেকে কী শেখা যায়, আর কী শেখা যায় না?

অংশ ৭-এর মাপ দুটি আলাদা গল্প বলে। একটি নাম খোঁজায় dict-এর শিকল (চার Env) প্রায় ৮৯ ন্যানোসেকেন্ড, list-এর ঘর প্রায় ২৩: প্রায় চার গুণ। কিন্তু পুরো program-এ সময় কমেছে মোটে এক-পঞ্চমাংশের মতো, 0.72 থেকে 0.58 সেকেন্ড। Amdahl-এর নিয়মের পরিচিত শিক্ষা এখানে খাটে: কোনো অংশ যত গুণই দ্রুত করুন, মোট লাভ সীমিত সেই অংশ মোট সময়ের কতটুকু, তা দিয়ে। Python-এ লেখা tree-walker-এর বেশিরভাগ সময় যায় node বাছাই, method call আর পূর্ণসংখ্যার হিসাবে।

দ্বিতীয় শিক্ষা আরও সূক্ষ্ম: reference-এর VM এখানে tree-walker-এর চেয়ে দ্রুত নয় (0.570 বনাম 0.558 সেকেন্ড)। Bytecode-ভিত্তিক VM সাধারণত দ্রুত হয় যখন সেটি C-র মতো নিচু স্তরের ভাষায় লেখা আর প্রতিটি নির্দেশ চালানোর খরচ খুব কম। Python-এ লেখা VM-এর প্রতিটি নির্দেশে একটি tuple খোলা আর string-তুলনার সারি; সেই খরচ গাছে হাঁটার কাছাকাছি। তাই “VM মানেই দ্রুত” একটি অতি-সরল দাবি।

কী শেখা যায় না, সেটিও বলা দরকার। এই সংখ্যাগুলো একটি কম্পিউটার, একটি Python version আর একটি program-এর; অন্য যন্ত্রে, অন্য version-এ বা অন্য program-এ অনুপাত আলাদা হবে। C-তে লেখা interpreter-এ dict-খোঁজা আর array-পড়ার অনুপাত আরও বড় হতে পারে, কারণ সেখানে বাকি কাজ অনেক সস্তা; কিন্তু সেটি আমরা এখানে মাপিনি, তাই দাবি করছি না। মাপের ফল সাধারণীকরণের আগে নিজের পরিস্থিতিতে আবার মাপাই একমাত্র নিরাপদ পথ।

বাস্তবের engine তাই environment-কে একা দেখে না: inline cache, specializing interpreter আর JIT (পর্ব ৬০, ৬১) চলার সময় শেখা তথ্য দিয়ে খোঁজার খরচ কমায়, আর static ভাষার compiler variable-কে সরাসরি register-এ রাখে।

মূল উপলব্ধি: একটি অংশের গতি মাপা সহজ, পুরো ব্যবস্থার লাভ অনুমান করা কঠিন। দুটিই মাপুন, যন্ত্র আর version লিখে রাখুন, আর কোন অংশ মোট সময়ের কতটুকু, তা জেনে তারপর optimize করুন।

অনুশীলন

প্রথমে নিজে করুন, তারপর উত্তর খুলে মেলান। প্রতিটি সংখ্যা আর আউটপুট ল্যাবে CPython 3.14.4-এ, Haat reference বাস্তবায়নের সঙ্গে মিলিয়ে নেওয়া।

  1. বাস্তবায়ন — hop-এর cache: প্রস্তাব ৫৭.১ বলে একটি নির্দিষ্ট নাম-ব্যবহার প্রতিবার শিকলের একই স্তরে মেলে। (ক) ChainInterp-এর home বদলান, যাতে প্রথম সফল খোঁজার পর node-এর গায়ে “কত parent পার হতে হলো” (node.hops) লেখা থাকে, আর পরের বার সরাসরি সেখানে গিয়ে একবার দেখেই কাজ সারে। (খ) Cache-এর ওপর অন্ধভাবে ভরসা না করে একটি নিরাপত্তা-পরীক্ষা রাখুন: কোন একটি পরিস্থিতিতে cache-এর জায়গায় নামটি না-ও থাকতে পারে? (গ) counter.haat, checkout.haat আর bazar.haat-এ probe কত কমে?
    class Cached(ChainInterp):
        def home(self, node, env):
            self.lookups += 1
            h = getattr(node, "hops", None)
            if h is not None:                       # fast path: go straight there
                e = env
                for _ in range(h): e = e.parent
                self.probes += 1
                if e is not None and node.name in e.vars: return e
            e, n = env, 0                           # slow path: walk and remember
            while e is not None:
                self.probes += 1
                if node.name in e.vars: node.hops = n; return e
                e, n = e.parent, n + 1
            raise runtime_error(node.line, node.col, f"'{node.name}' is not initialized yet")

    (খ) প্রস্তাবের একমাত্র ব্যতিক্রম: hoist-করা function একটি top-level variable-এর let চলার আগেই চললে নামটি global Env-এ এখনো নেই। Cache-এর জায়গায় নাম না পেলে ধীর পথে নামা, আর সেখানেও না পেলে 'k' is not initialized yet, ঠিক আগের মতো। (গ) ল্যাবের run: probe counter.haat-এ ৫৬ থেকে ৪২, checkout.haat-এ ৩৪ থেকে ২৮, bazar.haat-এ ৫৮ থেকে ৪৪; আউটপুট তিনটিতেই অপরিবর্তিত, আর ৫০০টি random program-এ reference-এর সঙ্গে একটিও অমিল নেই। এটি lexical address-এর অর্ধেক (শুধু “কত স্তর বাইরে”); নাম-ধরে dict-খোঁজা রয়ে গেছে, বাকি অর্ধেক অংশ ৪-এর slot.

  2. ভুল খুঁজুন — loop-এর জন্য একটি Env: একজন সহকর্মী ভাবলেন, while-এর প্রতি round-এ নতুন Env বানানো অপচয়। তিনি লিখলেন: body_env = Env(env) একবার, তারপর while self.eval(s.cond, env): self.exec_block(s.body.stmts, body_env). ল্যাবে ৫০০টি random program-এ reference-এর সঙ্গে একটিও অমিল হয়নি। ভুলটি কোথায়? Reference-এর কোন উদাহরণ এটি ধরে, কী ছাপে, আর random test কেন ধরেনি?

    Decision 14 বলে while-এর দেহ প্রতি round-এ একটি নতুন scope, যাতে loop-এ বানানো closure সেই round-এর variable ধরে। একটি Env পুনর্ব্যবহার করলে প্রতি round-এর let k আর let old একই dict-এর একই চাবিতে লেখা হয়, আর সব round-এর closure একই Env দেখে। nested.haat তখন ছাপে 936, 15, 7, তারপর 23:31: runtime error: stack overflow (ঠিক উত্তর: 300, 3, 2, 1). কারণ: শেষ round-এ old = দ্বিতীয় round-এর closure, কিন্তু সেই closure-ও এখন একই Env-এর old পড়ে, যা নিজেই; ফলে নিজেকে অবিরাম ডাকা, আর ১০০০তম call-এ old()-এর অবস্থানে (লাইন 23, কলাম 31) error. Random generator-এর program loop-এ closure বানায়, কিন্তু সেই round-এর ভেতরেই ডাকে বা বাইরের variable ধরে; পুরোনো round-এর closure পরে ডাকা হয় না, তাই ভুলটি দেখা দেয় না। শিক্ষা: random test-এর জোর generator-এর কল্পনা পর্যন্ত; নির্দিষ্ট নিয়মের জন্য হাতে লেখা golden test লাগে। সমাধান: প্রতি round-এ self.scope(env), যেমন Walker-এ আছে। (Slot-নকশায় একই ভুলের রূপ হলো প্রতি round-এ নতুন cell না বানিয়ে পুরোনো cell-এ লেখা।)

  3. Trace আর হিসাব: নিচের Haat program কী ছাপবে? Dict-এর শিকলের interpreter মোট কয়টি Env বানাবে? Slot-নকশায় (আর reference VM-এ) কয়টি cell তৈরি হবে, আর k কি cell পাবে? f-এর ভেতরে rate খুঁজতে কয়টি probe লাগে?
    fn make_bonus(rate: Int) -> (Int) -> Int {
        var given = 0;
        let f = fn(x: Int) -> Int {
            given = given + 1;
            return x * rate / 100 + given;
        };
        return f;
    }
    let b = make_bonus(10);
    var i = 0;
    while i < 3 {
        let k = 100 * (i + 1);
        print(b(k));
        i = i + 1;
    }

    আউটপুট (reference-এর run আর vm দুটিতেই): 11, 22, 33. হিসাব: b(100)-এ given = 1, 100 × 10 / 100 + 1 = 11; b(200)-এ given = 2, 20 + 2 = 22; b(300)-এ 30 + 3 = 33. Env: global ১, make_bonus-এর call ১, while-এর তিন round ৩, b-এর তিন call ৩: মোট ৮ (ল্যাবের গণনা ৮)। Cell: ২টি, rate আর given; dis-এ make_bonus-এর শুরুতে LOAD_LOCAL 0; MAKE_CELL 0 ; rate আর CONST 0; MAKE_CELL 1 ; given, আর closure captures given, rate. k কেউ ধরেনি, তাই main-এর একটি সাধারণ slot (STORE_LOCAL 0 ; k), প্রতি round-এ নতুন cell লাগে না। rate খুঁজতে ২ probe: f-এর call-এর Env-এ নেই, make_bonus-এর Env-এ আছে। পুরো program-এ ৩৬টি খোঁজা, ৬০টি probe.

  4. প্রমাণ — দুই environment একই ফল দেয়: প্রমাণ করুন (রূপরেখা যথেষ্ট): resolver-পার-হওয়া যেকোনো Haat program-এ ChainInterp আর SlotInterp একই আউটপুট দেয়। একটি সম্পর্ক R প্রস্তাব করুন, যা দুই interpreter-এর অবস্থাকে জোড়ে, আর দেখান প্রতিটি ধাপ R রক্ষা করে। কোন ধাপে “প্রতিবার let চললে নতুন cell” শর্তটি লাগে?

    প্রমাণের রূপরেখা. দুই interpreter একই AST-এ পাশাপাশি চলে। প্রতিটি ঘোষণার প্রতিটি চলমান কপিকে (একবার চলা একটি let, একটি parameter-এর একবারের binding) একটি পরিচয় ধরুন। R বলে: প্রতিটি পরিচয়ের জন্য শিকল-নকশার যে dict-ঘরে তার মান আর slot-নকশার যে ঘরে (slot, cell বা global-এর ঘর) তার মান, দুটি সমান; আর প্রতিটি closure-এর জন্য, তার দেহের প্রতিটি free variable শিকল-নকশায় যে পরিচয়ে মেলে, flat closure-এর সংশ্লিষ্ট cell ঠিক সেই পরিচয়ের ঘর।

    1. শুরু: শুধু hoist-করা top-level function; দুই দিকে একই, R সত্য।
    2. পড়া আর লেখা: প্রস্তাব ৫৭.১ অনুযায়ী শিকল-নকশা resolver-এর বাছা ঘোষণার চলমান কপিতে থামে; slot-নকশা resolver-এর একই Binding থেকে ঠিকানা পায়। R অনুযায়ী দুই ঘরে একই মান, আর লেখা দুই দিকে একই পরিচয় বদলায়।
    3. Closure তৈরি: শিকল-নকশার closure চলতি Env রাখে, তাই তার free variable-গুলো এই মুহূর্তের পরিচয়ে মেলে; make_fn ঠিক সেই পরিচয়গুলোর cell কপি করে। R-এর দ্বিতীয় অংশ রক্ষা পায়।
    4. ঘোষণা আবার চলা (loop-এর পরের round, বা একই function-এর নতুন call): শিকল-নকশায় নতুন Env, তাই নতুন পরিচয়, আর পুরোনো closure পুরোনোটি ধরে রাখে। Slot-নকশায় একই slot আবার লেখা হয়। শর্তটি ঠিক এখানে লাগে: ধরা variable-এর জন্য define নতুন cell বানায়, তাই নতুন পরিচয় নতুন বাক্সে যায় আর পুরোনো closure-এর বাক্স অক্ষত থাকে। পুরোনো cell-এ লিখলে পুরোনো closure নতুন মান দেখত, R ভেঙে যেত (অনুশীলন ২-এর ভুলের slot-রূপ)। ধরা নয় এমন variable slot-এ সরাসরি লেখা নিরাপদ, কারণ কোনো closure তার পুরোনো পরিচয় দেখে না।
    5. Call আর return: নতুন Env বনাম নতুন frame, দুটিতেই parameter নতুন পরিচয়; ফেরার পর আগের অবস্থায় ফেরা। Print দুই দিকে একই মান ছাপে। ধাপের সংখ্যার ওপর induction-এ আউটপুট (runtime error-সহ) সমান। ∎

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

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

ক্রমDict-এর শিকলের tree-walking interpreter-এ print(a()); চলছে, যেখানে a একটি closure. ঘটনাগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. Callee-এর নাম a চলতি Env থেকে শিকল ধরে খুঁজে closure পাওয়া
  2. Argument-গুলো বাঁ থেকে ডানে মূল্যায়ন করা (এখানে কোনোটি নেই)
  3. নতুন Env বানানো, যার parent closure-এর env, আর তাতে parameter বসানো
  4. দেহ চালানো: প্রতিটি নাম নতুন Env থেকে বাইরের দিকে খোঁজা
  5. ReturnSignal ধরা পড়ে মান ফেরা, আর print সেটি ছাপে

একটি tree-walking interpreter-এ environment হলো dict আর parent link-এর শিকল। একটি closure call করার সময় নতুন Env-এর parent কোনটি হওয়া উচিত, যাতে static (lexical) scope রক্ষা পায়?

  • যে Env থেকে call করা হলো (caller-এর Env)
  • Closure তৈরির সময় যে Env ছিল (closure-এর env)
  • সবসময় global Env
  • কোনো parent নয়, শুধু parameter-এর Env

Haat-এ fn checkout(limit: Int) -> Int { var spent = 0; let buy = fn(x: Int) -> Bool { if spent + x > limit { return false; } spent = spent + x; return true; }; … }. প্রতিটি block আর call-এ একটি dict-Env বানানো interpreter-এ buy(400)-এর শর্ত spent + x > limit মূল্যায়নে মোট কয়টি dict-পরীক্ষা (probe) লাগে?

  • ৩
  • ৬
  • ৫
  • ৯

Haat-এর spec বলে while-এর দেহ প্রতি round-এ একটি নতুন scope, যাতে loop-এ বানানো closure সেই round-এর variable ধরে। Slot আর cell-ভিত্তিক বাস্তবায়নে (resolver প্রতিটি ঘোষণাকে একটি স্থায়ী slot দেয়) এটি কীভাবে নিশ্চিত করা হয়?

  • ধরা variable-এর ঘোষণা প্রতিবার চললে slot-এ একটি নতুন cell বসানো হয়
  • প্রতি round-এর জন্য resolver আলাদা slot বরাদ্দ করে
  • Closure তৈরির সময় সব free variable-এর মান কপি করা হয়
  • প্রতি round-এর জন্য একটি নতুন call frame তৈরি হয়

একটি function একটি বড় string log আর একটি সংখ্যা total বানিয়ে এমন closure ফেরত দেয়, যা শুধু total পড়ে। কোন বাস্তবায়নে closure বেঁচে থাকা পর্যন্ত log-ও বেঁচে থাকে?

  • Flat closure, যা শুধু free variable-এর cell রাখে
  • Lambda lifting, যেখানে free variable parameter হয়ে যায়
  • কোনো বাস্তবায়নেই নয়; GC সবসময় log মুক্ত করে
  • Linked closure, যা তৈরির জায়গার পুরো environment-এর pointer রাখে

JavaScript-এর sloppy mode-এ function price(t, rules) { var rate = 5; with (rules) { return t - t * rate / 100; } }. Engine কেন with-এর ভেতরের rate-কে compile-এর সময় একটি স্থির slot দিতে পারে না?

  • কারণ var hoist হয়, তাই তার slot অজানা
  • কারণ rate-এর মানে rules object-এ property থাকা-না-থাকার ওপর নির্ভর করে, যা চলার সময়ই জানা যায়
  • কারণ JavaScript-এ variable-এর type অজানা
  • কারণ with থাকলে কোডটি SyntaxError, তাই compile হয় না

Haat reference-এর python haat.py dis-এ একটি closure-এর ভেতরে LOAD_FREE 1 ; limit দেখা গেল। এর মানে কী?

  • global তালিকার ঘর 1 থেকে limit পড়া
  • চলতি frame-এর slot 1 থেকে limit পড়া
  • চলতি closure-এর cell-তালিকার ঘর 1-এর cell থেকে limit-এর মান পড়া
  • static chain ধরে এক স্তর বাইরের frame থেকে limit পড়া

শব্দকোষ

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

মনে রাখুন

  1. Env-এর শিকল: প্রতিটি block আর call-এ একটি dict + parent; lookup শিকল ধরে, probe = ১ + মাঝের scope. চলমান শিকল লেখার scope-কে অনুসরণ করে (প্রস্তাব ৫৭.১), কারণ call-এর Env-এর parent closure-এর env.
  2. Closure আর heap: Closure = code + Env-এর pointer, কোনো কপি নয়। Env heap-এ থাকে বলে ফেরত দেওয়া closure নিরাপদ; কতদিন বাঁচবে, ঠিক করে GC (E1 ↔ closure একটি cycle).
  3. Slot আর cell: Resolver-এর Binding থেকে GLOBAL/LOCAL/CELL/FREE ঠিকানা, একবার হিসাব; ধরা variable cell-এ, flat closure শুধু দরকারি cell রাখে। ঠিকানাগুলো haat.py dis-এর সঙ্গে হুবহু মেলে।
  4. পরিচয় বনাম ঠিকানা: একই slot, প্রতিবার ঘোষণায় নতুন cell; নইলে loop-এর closure ভুল (nested.haat: 300 বনাম stack overflow). Flat closure safe for space, linked নয় (২০০০ অক্ষর বনাম ০)।
  5. মাপ আর যাচাই: একটি খোঁজা ৮৯ বনাম ২৩ ns, পুরো program 0.72 বনাম 0.58 s (এক যন্ত্র); এই program-এ Python-এ লেখা VM tree-walker-এর চেয়ে দ্রুত নয়, যদিও পর্ব ৫৬-এর fib(22)-এ সামান্য দ্রুত ছিল। দুই environment চারটি বাস্তবায়নের differential test-এ ৫০০/৫০০ মিলেছে।

পরের পর্বে: Environment এখন ঠিকানায় চলে, কিন্তু interpreter এখনো গাছে হাঁটে। পর্ব ৫৮-এ (Bytecode নকশা) এই ঠিকানাগুলোই opcode-এর argument হবে: Code object, opcode-এর টেবিল আর stack-এর প্রভাব, expression থেকে post-order bytecode, jump দিয়ে if আর while, আর MAKE_CELL ও MAKE_CLOSURE দিয়ে closure compile করা।

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

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