এই পর্বে যা শিখবেন
- Symbol table-এর তিনটি প্রচলিত নকশা, তাদের খরচ আর কোনটি কোথায় কাজে লাগে
- Haat-এর resolver নিজে লেখা:
declare,lookup, pending set, hoisting আর function-এর নতুন scope - নাম-সংক্রান্ত সাতটি error ঠিক reference-এর লেখা আর line:col-এ দেওয়া
- Slot নম্বর, depth আর captured চিহ্ন দিয়ে AST সাজানো, যাতে VM আর কিছু খুঁজতে না হয়
- নিজের resolver-কে reference-এর সঙ্গে differential test দিয়ে মেলানো, আর সত্যিকারের Clang-এর AST-এ একই কাজ দেখা
১ · Symbol table কী, আর resolver কোথায় বসে
মডিউল ৮-এ Haat-এর front end তৈরি হয়েছে: lexer (পর্ব ৪৬, হাতে লেখা lexer) লেখাকে token বানায়, parser (পর্ব ৪৭, Recursive descent parser) token থেকে AST বানায়। কিন্তু AST-এ Var("total", 8, 8) শুধু একটি নাম, একটি অক্ষরমালা। এই total কি delivery-র parameter, না program-এর শেষ দিকের var total? কোনো ঘোষণা আছে কি না? এই প্রশ্নের উত্তর দেয় semantic analysis-এর প্রথম ধাপ, name resolution. যে pass এটি করে, তাকে আমরা বলব resolver; Haat reference-এ সেটি resolver.py.
একটি বড় পরিবারের বিয়েবাড়ির কথা ভাবুন। “রহিম ভাইকে ডাকো” শুনলে আপনি আগে খোঁজেন নিজের টেবিলে, না পেলে নিজের পরিবারের ঘরে, তারপর পুরো বাড়িতে। দুজন রহিম থাকলে কাছেরজনকেই বোঝানো হয়। আর অতিথি-তালিকায় যাঁর নাম আছে কিন্তু এখনো এসে পৌঁছাননি, তাঁকে ডাকলে বলা হয়, “উনি তো এখনো আসেননি”, অন্য কোনো রহিমকে ধরে আনা হয় না। Resolver ঠিক এই খোঁজ করে: টেবিল, ঘর আর বাড়ি হলো scope; অতিথি-তালিকা হলো symbol table; আর “এখনো আসেননি” হলো এই পর্বের pending set.
Symbol table হলো সেই তথ্যভান্ডার, যেখানে compiler প্রতিটি ঘোষিত নামের খবর রাখে। কোন নাম কোন scope-এ, কী ধরনের ঘোষণা, কোথায় লেখা, চলার সময় কোথায় থাকবে। তত্ত্বের দিকটি আগেই পড়েছেন: নাম আর binding পর্ব ১৪-এ (নাম, variable আর binding), static scope, scope chain আর ঘোষণার আগে ব্যবহারের নিয়ম পর্ব ১৫-এ (Scope), lifetime পর্ব ১৬-এ (Lifetime আর storage), closure-এর cell পর্ব ১৭-এ (Closure). পর্ব ১৪-এর শেষ অংশে একটি খেলনা resolver-ও দেখেছিলেন, যার ইনপুটে line:col ছিল না। এখানে কাজটি পুরো: সত্যিকারের AST, সব নিয়ম, ঠিক reference-এর error আর slot.
Haat-এর pipeline-এ resolver বসে parser আর type checker-এর মাঝে: tokens → AST → resolver → type checker → interpreter বা compiler. Resolver AST বদলায় না; পাশে একটি টেবিল তৈরি করে। Reference-এ প্রতিটি ঘোষণার জন্য একটি Binding:
| Field | মানে | bazar.haat-এর p-এর জন্য |
|---|---|---|
name | ঘোষিত নাম | "p" |
kind | let, var, param বা fn | let |
depth | function-এর ভেতরে কত স্তর (০ = top level) | ১ |
slot | global নম্বর, বা মালিক function-এর local ঘর | ২ |
is_global | program-এর সবচেয়ে বাইরের scope-এ কি না | False |
owner | কোন FnDecl/Lambda-এর ঘর; None = মূল program | price |
line, col | ঘোষণার অবস্থান | 3:9 |
captured | ভেতরের কোনো function এটি ব্যবহার করে কি না | False |
type | পরে type checker ভরবে (পর্ব ৫২) | — |
Resolver-এর ফল Resolution নামের একটি বস্তু, যাতে তিনটি map: uses (প্রতিটি Var আর Assign node-এর id থেকে তার Binding), decls (প্রতিটি Let, FnDecl আর Param থেকে তার তৈরি করা Binding), আর nslots (প্রতিটি function-এর কয়টি local ঘর লাগবে)। পরের সব pass, type checker, interpreter আর bytecode compiler, নাম আর খোঁজে না; এই map থেকে সরাসরি উত্তর নেয়।
২ · তিনটি নকশা — stack of map, persistent map আর এক টেবিল
Symbol table-কে চারটি কাজ করতে হয়: enter (নতুন scope শুরু), declare (নাম যোগ), lookup (নাম খোঁজা, ভেতর থেকে বাইরে) আর exit (scope শেষ)। একই চার কাজের তিনটি প্রচলিত বাস্তবায়ন:
- Hash map-এর stack. প্রতিটি scope-এর জন্য একটি hash table, আর সেগুলো একটি তালিকায় সাজানো। খোঁজা মানে ওপর থেকে নিচে প্রতিটি map-এ একবার দেখা। Scope শেষ হলে পুরো map ফেলে দেওয়া। Haat reference ঠিক এটি করে:
self.scopesএকটি তালিকা, যার প্রতিটি ঘর একটিScope. - Persistent map. Environment একটি persistent data structure: নতুন নাম যোগ করলে পুরোনোটি বদলায় না, একটি নতুন সংস্করণ তৈরি হয় যা পুরোনোটির বেশিরভাগ অংশ ভাগ করে নেয়। Scope শেষ হলে শুধু পুরোনো সংস্করণে ফিরে যাওয়া। বড় সুবিধা: যেকোনো মুহূর্তের environment সস্তায় রেখে দেওয়া যায়।
- এক hash table, নামপ্রতি stack. সব scope-এর জন্য একটিমাত্র table; প্রতিটি নামের পাশে তার ঘোষণাগুলোর একটি stack, সবচেয়ে ভেতরেরটি ওপরে। খোঁজা একবারের hash, depth যত বড়ই হোক। দাম দিতে হয় scope শেষে: সেই scope-এ যোগ হওয়া প্রতিটি নাম আলাদা করে সরাতে হয়, তাই প্রতিটি scope নিজের নামের হিসাব রাখে।
| নকশা | lookup | exit | কোথায় মানানসই |
|---|---|---|---|
| Hash map-এর stack | scope-এর গভীরতা d-এর সমানুপাতিক (প্রতি স্তরে একটি hash) | O(1) | ছোট ও মাঝারি compiler, পড়তে সহজ |
| Persistent map | linked list হলে নামের সংখ্যার সমানুপাতিক; balanced tree হলে O(log n) | O(1) (পুরোনো সংস্করণে ফেরা) | IDE, যেখানে প্রতিটি জায়গার environment মনে রাখতে হয়; functional ভাষায় লেখা compiler |
| এক table, নামপ্রতি stack | গড়ে O(1) | সেই scope-এর নামের সংখ্যার সমানুপাতিক | গভীর nesting আর বড় ফাইল, যেখানে প্রতিটি lookup-এর খরচ গোনা হয় |
নিচের JavaScript ব্লক তিনটি নকশাই লিখে একই ঘটনার সারি চালায়: বাইরে let price = 500;, ভেতরের block-এ let price = 575;, তারও ভেতরে let vat = 15;, আর তিন জায়গায় জিজ্ঞেস করা হয় price আর vat কত।
"use strict"; // তিনটি symbol table নকশা — একই ঘটনা, একই প্রশ্ন
class StackOfMaps { // (১) প্রতিটি scope-এর জন্য একটি Map, stack-এ
constructor() { this.s = [new Map()]; }
enter() { this.s.push(new Map()); } exit() { this.s.pop(); }
declare(n, v) { this.s.at(-1).set(n, v); }
lookup(n) { for (let i = this.s.length - 1; i >= 0; i--) if (this.s[i].has(n)) return this.s[i].get(n); }
}
class Persistent { // (২) অপরিবর্তনীয় linked list: পুরোনো env কখনো নষ্ট হয় না
constructor() { this.env = null; this.saved = []; }
enter() { this.saved.push(this.env); } exit() { this.env = this.saved.pop(); }
declare(n, v) { this.env = { n, v, next: this.env }; }
lookup(n) { for (let e = this.env; e; e = e.next) if (e.n === n) return e.v; }
}
class OneTable { // (৩) এক hash table: নাম -> [scope নম্বর, মান]-এর stack
constructor() { this.t = new Map(); this.depth = 0; this.added = [[]]; }
enter() { this.depth++; this.added.push([]); }
exit() { for (const n of this.added.pop()) this.t.get(n).pop(); this.depth--; }
declare(n, v) { if (!this.t.has(n)) this.t.set(n, []); this.t.get(n).push([this.depth, v]); this.added.at(-1).push(n); }
lookup(n) { const st = this.t.get(n); return st && st.length ? st.at(-1)[1] : undefined; }
}
// let price = 500; { let price = 575; { let vat = 15; ? } ? } ?
const events = [["decl", "price", 500], ["enter"], ["decl", "price", 575], ["enter"],
["decl", "vat", 15], ["ask"], ["exit"], ["ask"], ["exit"], ["ask"]];
for (const T of [StackOfMaps, Persistent, OneTable]) {
const tab = new T(), answers = []; let snapshot = null;
for (const [op, n, v] of events) {
if (op === "decl") tab.declare(n, v);
else if (op === "ask") answers.push(`price=${tab.lookup("price")} vat=${tab.lookup("vat")}`);
else tab[op]();
if (T === Persistent && op === "ask" && !snapshot) snapshot = tab.env; // সবচেয়ে ভেতরের অবস্থা
}
console.log(T.name.padEnd(12), answers.join(" | "));
if (T === OneTable) console.log(" OneTable এখন:", JSON.stringify([...tab.t]));
if (snapshot) { let e = snapshot, s = []; for (; e; e = e.next) s.push(`${e.n}=${e.v}`); console.log(" পুরোনো snapshot এখনো:", s.join(" -> ")); }
}আসল আউটপুট (ব্রাউজারের JavaScript):
StackOfMaps price=575 vat=15 | price=575 vat=undefined | price=500 vat=undefined
Persistent price=575 vat=15 | price=575 vat=undefined | price=500 vat=undefined
পুরোনো snapshot এখনো: vat=15 -> price=575 -> price=500
OneTable price=575 vat=15 | price=575 vat=undefined | price=500 vat=undefined
OneTable এখন: [["price",[[0,500]]],["vat",[]]]
তিনটি নকশা তিন জায়গাতেই একই উত্তর দিয়েছে: সবচেয়ে ভেতরে price=575 vat=15, মাঝের block-এ ফিরে vat আর নেই, আর বাইরে এসে আবার পুরোনো price=500. পার্থক্য ভেতরের অবস্থায়। OneTable-এর শেষ অবস্থা দেখুন: price-এর stack-এ শুধু scope 0-এর ঘোষণা টিকে আছে, আর vat-এর stack খালি; scope শেষে exit প্রতিটি নাম আলাদা করে সরিয়েছে। Persistent-এ সবচেয়ে ভেতরের মুহূর্তের environment (vat=15 -> price=575 -> price=500) সব exit-এর পরেও অক্ষত, কারণ কিছুই মোছা হয় না; শুধু চলতি pointer পিছিয়েছে। এই snapshot-ই একটি editor-কে বলে দিতে পারে, “এই লাইনে কোন কোন নাম দেখা যায়”।
বাস্তবের compiler-ও এই তিন ধারায় পড়ে, যদিও খুঁটিনাটি অনেক। Clang-এর IdentifierResolver প্রতিটি নামের সঙ্গে তার ঘোষণাগুলোর একটি শৃঙ্খল রাখে, যা তৃতীয় নকশার কাছাকাছি। CPython-এর symtable module প্রতিটি function আর class-এর জন্য একটি করে table বানিয়ে গাছ সাজায় (পর্ব ১৪-এ আসল আউটপুট দেখেছেন)। ML-ধারার ভাষায় লেখা অনেক compiler persistent map ব্যবহার করে, কারণ সেই ভাষায় এটিই স্বাভাবিক। Hash table নিজে কীভাবে কাজ করে, তা DSA কোর্সের পর্ব ৩২-এ আছে।
৩ · Haat-এর resolver-এর হৃদয় — declare, lookup আর pending
এবার Haat-এর resolver নিজে লিখি, reference-এর নাম আর আচরণ হুবহু রেখে। এই পাতার Python ব্লকগুলো একটি সহায়ক module, haat_front.py, import করে: এতে আছে মডিউল ৮-এর lexer, reference-এর একই নাম আর field-এর AST class (পর্ব ৪৯, AST নকশা), আর পর্ব ৪৭-এর পুরো parser, যার expression অংশ পর্ব ৪৮-এর (Pratt parsing) সংক্ষিপ্ত রূপ। parse(src) একটি Program ফেরত দেয়, যার প্রতিটি node-এর line আর col reference-এর সঙ্গে মেলে। Module-টি পাতাতেই রাখা, খুলে পড়তে পারেন:
সহায়ক module haat_front.py দেখুন (ব্লকগুলো এটি import করে)
# haat_front.py — সহায়ক অংশ: পর্ব ৪৬–৪৯-এর lexer, AST আর parser-এর সংক্ষিপ্ত রূপ।
# Reference-এর tokens.py + lexer.py (পর্ব ৪৬), ast_nodes.py + ast_print.py-র sexpr (পর্ব ৪৯)
# আর parser.py-র expression অংশ (পর্ব ৪৮)-এর সংক্ষিপ্ত রূপ; নাম আর আউটপুট reference-এর মতো।
import re
from dataclasses import dataclass, field, make_dataclass
@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: 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":
msg = "unterminated string literal" if t == '"' else f"unexpected character '{t}'"
raise SyntaxError(f"{line}:{col}: error: {msg}")
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(): # same class names and fields; line, col always last
globals()[_name] = make_dataclass(_name, _fields.split() + ["line", "col"])
Program = make_dataclass("Program", ["stmts"])
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 quote(s):
return '"' + s.replace("\\", "\\\\").replace('"', '\\"').replace("\n", "\\n") + '"'
def sexpr(n, ind=0): # same text as `python haat.py ast`
pad = "\n" + " " * (ind + 1); sub = lambda m: sexpr(m, ind + 1); e = lambda m: sexpr(m, ind)
c = type(n).__name__
if c in ("Program", "Block"): return f"({c.lower()}" + "".join(pad + sub(s) for s in n.stmts) + ")"
if c in ("Num", "Bool"): return str(n.value).lower()
if c == "Str": return quote(n.value)
if c == "Var": return n.name
if c == "Unary": return f"({n.op} {e(n.operand)})"
if c == "Binary": return f"({n.op} {e(n.left)} {e(n.right)})"
if c == "Call": return "(call " + " ".join(e(x) for x in [n.callee] + n.args) + ")"
if c in ("Lambda", "FnDecl"):
params = " ".join(f"({p.name} {p.type})" for p in n.params)
head = "(lambda" if c == "Lambda" else f"(fn {n.name}"
return f"{head} ({params}) {n.ret}{pad}{sub(n.body)})"
if c == "Let":
ann = "" if n.type is None else f" {n.type}"
return f"({'var' if n.mutable else 'let'} {n.name}{ann} {e(n.init)})"
if c == "Assign": return f"(set {n.name} {e(n.value)})"
if c == "If": return f"(if {e(n.cond)}{pad}{sub(n.then)}" + ("" if n.else_ is None else pad + sub(n.else_)) + ")"
if c == "While": return f"(while {e(n.cond)}{pad}{sub(n.body)})"
if c == "Return": return "(return)" if n.value is None else f"(return {e(n.value)})"
if c == "Print": return f"(print {e(n.value)})"
return f"(expr {e(n.expr)})"
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 ExprStandIn: # Pratt expression parser (পর্ব ৪৮ builds it step by step)
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": # call f(a, b): postfix, binds tightest (80)
self.advance(); args = [] if self.check("RPAREN") else [self.expression()]
while self.match("COMMA"): args.append(self.expression())
self.expect("RPAREN", "expected ')' after arguments")
s = left
while isinstance(s, (Binary, Call)): s = s.left if isinstance(s, Binary) else s.callee
left = Call(left, args, s.line, s.col)
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
class Parser(ExprStandIn): # parser.py (পর্ব ৪৭): token helpers + program loop
def __init__(self, tokens): self.toks, self.pos = tokens, 0
def peek(self, ahead=0): # look, do not consume
return self.toks[min(self.pos + ahead, len(self.toks) - 1)]
def check(self, kind): return self.peek().kind == kind
def advance(self): # consume one token (never past EOF)
tok = self.peek()
if tok.kind != "EOF": self.pos += 1
return tok
def match(self, kind): # consume only if it is this 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: # decision 24: just after the previous token
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 SyntaxError(f"{line}:{col}: error: {message}")
def parse_program(self): return Program(self.statements_until("EOF"))
def statements_until(self, end):
stmts = []
while not self.check(end) and not self.check("EOF"): stmts.append(self.statement())
return stmts
class Parser(Parser): # parser.py: statements, one method per rule
def statement(self): # one token of lookahead picks the rule
kind = self.peek().kind
if kind in ("LET", "VAR"): return self.let_decl()
if kind == "FN" and self.peek(1).kind == "IDENT": return self.fn_decl()
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 '{'")
return self.expr_or_assign()
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): # else if → a nested If; else → a Block
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 expr_or_assign(self):
first = self.peek(); e = self.expression()
if self.check("EQ"): # decision 9: the target must be a plain name
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)
class Parser(Parser): # parser.py: declarations and types
def let_decl(self): # ("let" | "var") NAME [":" type] "=" expr ";"
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)
def fn_decl(self): # "fn" NAME, then the shared rest
self.advance(); name = self.advance()
params, ret, body = self.function_rest("expected '(' after function name")
return FnDecl(name.text, params, ret, body, name.line, name.col)
def function_rest(self, lparen_message): # "(" params ")" ["->" type] block
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): # Int | Bool | Str | Unit | "(" types ")" "->" type
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 parse(src): # source text -> Program (first syntax error stops)
return Parser(tokenize(src)).parse_program()একটি scope-এর দুটি অংশ: names, অর্থাৎ এ পর্যন্ত ঘোষিত নাম, আর pending, অর্থাৎ এই block-এ পরে ঘোষিত হবে এমন নাম। Block-এ ঢোকার মুহূর্তেই resolver পুরো block-এর statement তালিকা দেখে let, var আর fn-এর নামগুলো pending-এ রাখে (declared_names). ঘোষণায় পৌঁছালে নামটি pending থেকে names-এ যায়। খোঁজার সময় প্রতিটি scope-এ প্রশ্ন দুটি: নামটি কি এখানে আছে? না থাকলে, এখানে কি পরে আসবে? দ্বিতীয়টির উত্তর “হ্যাঁ” হলে খোঁজা থামে, বাইরের scope আর দেখা হয় না। এটিই decision 16 (use before declaration), কোডে।
প্রথম ব্লকে Binding, Scope আর resolver-এর দুটি মূল method. এটি reference-এর resolver.py-র প্রথম অর্ধেকের সঙ্গে মেলে। তিনটি Python ব্লক একই namespace ভাগ করে (পরের ব্লক আগে চালালে আগেরগুলো নিজে চলে নেবে), আর পরের ব্লক class Resolver(Resolver) লিখে আগেরটিকে বাড়ায়। প্রথমবার চালালে ব্রাউজারে Python নামতে কয়েক সেকেন্ড লাগতে পারে।
from haat_front import * # parse, AST nodes, dataclass, field (পর্ব ৪৬–৪৯-এর stand-in)
@dataclass(eq=False)
class Binding: # resolver.py: one symbol-table entry
name: str; kind: str # kind: "let", "var", "param" or "fn"
depth: int; slot: int; is_global: bool
owner: object; line: int; col: int # owner: FnDecl/Lambda, None = main
captured: bool = False # used by an inner function -> needs a cell
@dataclass
class Scope: # one block: names so far + names still to come
names: dict = field(default_factory=dict); pending: set = field(default_factory=set)
def declared_names(stmts): return {s.name for s in stmts if isinstance(s, (Let, FnDecl))}
class Resolver:
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, node, msg): self.errors.append((node.line, node.col, msg))
def declare(self, node, name, kind):
scope, is_global = self.scopes[-1], len(self.scopes) == 1
if name in scope.names: self.error(node, f"'{name}' is already declared in this scope")
key = None if self.owner is None else id(self.owner)
if is_global: slot, self.nglobals = self.nglobals, self.nglobals + 1
else: slot = self.nslots[key]; self.nslots[key] += 1
b = Binding(name, kind, self.depth, slot, is_global, self.owner, node.line, node.col)
scope.names[name] = b; scope.pending.discard(name); self.decls[id(node)] = b; return b
def lookup(self, node, name):
for scope in reversed(self.scopes): # innermost scope first
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(node)] = b; return b
if name in scope.pending: return self.error(node, f"'{name}' is used before its declaration")
return self.error(node, f"undefined variable '{name}'")
r = Resolver(); r.scopes.append(Scope(pending={"stock"})) # this block declares stock later
print(r.lookup(Var("stock", 2, 7), "stock"), r.errors)
r.declare(Let("stock", False, None, Num(12, 3, 13), 3, 5), "stock", "let"); print(r.lookup(Var("stock", 4, 7), "stock"))আসল আউটপুট (ব্রাউজারের Python):
None [(2, 7, "'stock' is used before its declaration")]
Binding(name='stock', kind='let', depth=0, slot=0, is_global=True, owner=None, line=3, col=5, captured=False)
ব্লকের শেষ তিন লাইন হাতে একটি ছোট দৃশ্য বানায়: একটি block, যা পরে stock ঘোষণা করবে, তাই stock শুরুতেই pending-এ। লাইন ২-এ stock খুঁজতে গেলে names-এ নেই, কিন্তু pending-এ আছে: lookup None ফেরত দেয় আর error-এর তালিকায় যোগ হয় (2, 7, "'stock' is used before its declaration"). তারপর লাইন ৩-এ ঘোষণা: এটি একমাত্র scope, তাই global, আর প্রথম global বলে slot=0. এবার লাইন ৪-এর খোঁজা সেই Binding-ই ফেরত দেয়। Error এখানে একটি tuple (line, col, বার্তা); শেষে অবস্থান অনুযায়ী সাজিয়ে reference-এর 3:7: error: … আকারে লেখা হবে, কারণ reference-ও (decision 2) একটি pass-এর সব error জমিয়ে সাজিয়ে দেখায়।
declare-এর তিনটি কাজ: একই scope-এ নামটি আগে থেকে থাকলে 'x' is already declared in this scope (decision 15); একটি slot দেওয়া; আর নামটি pending থেকে সরানো। Slot দেওয়ার নিয়ম সরল। শুধু একটি scope খোলা থাকলে (top level) নামটি global, আর global-এর একটি আলাদা গণনা। নাহলে নামটি চলতি function-এর (owner) local, আর সেই function-এর গণনা এক বাড়ে। lookup-এর সবচেয়ে সূক্ষ্ম লাইনটি captured-এর: খুঁজে পাওয়া binding যদি global না হয় আর তার মালিক চলতি function না হয়, তাহলে একটি ভেতরের function বাইরের function-এর variable ছুঁয়েছে। এর মানে অংশ ৬-এ।
খোলা scope-গুলো S1 (সবচেয়ে বাইরে) … Sk (সবচেয়ে ভেতরে)। নাম x-এর জন্য সবচেয়ে বড় i খুঁজুন, যেখানে x ∈ names(Si) অথবা x ∈ pending(Si). প্রথম ক্ষেত্রে ফল names(Si)[x]; দ্বিতীয় ক্ষেত্রে error “used before its declaration”; এমন কোনো i না থাকলে error “undefined variable”. অর্থাৎ বাইরের scope দেখা হয় কেবল তখনই, যখন ভেতরের প্রতিটি scope-এ নামটি এখনো নেই আর পরেও আসবে না।
৪ · AST হাঁটা — দুই pass, function আর block
দ্বিতীয় ব্লক resolver-কে পুরো AST-এর ওপর চালায়। চারটি method, প্রতিটি একটি নিয়ম:
program: top-level scope খোলে, তারপর দুই pass. প্রথম pass শুধু top-levelfn-গুলো ঘোষণা করে, তাই সেগুলো program-এর শুরু থেকেই দেখা যায় (hoisting, decision 17). দ্বিতীয় pass বাকি সব কিছু লেখার ক্রমে।function:FnDeclআর নামহীনLambdaদুটির জন্যই। নতুন মালিক, depth এক বাড়ে, slot-গণনা শূন্য থেকে, আর একটি নতুন scope যাতে parameter আর body-র top-level ঘোষণা দুটিই থাকে (decision 14: C-র মতো এক scope).stmt:Let-এ আগে initializer, পরে ঘোষণা, তাইlet a = a + 1;-এর ডান পাশেরaতখনো pending. Nestedfn-এ উল্টো: আগে ঘোষণা, পরে body, তাই একটি nested function নিজেকে ডাকতে পারে। প্রতিটি{ }একটি নতুন block scope.expr:Varহলেlookup,Lambdaহলেfunction, বাকিরা শুধু সন্তানদের দিকে নামে।
class Resolver(Resolver): # resolver.py: the walk over the AST
def program(self, prog):
self.scopes.append(Scope(pending=declared_names(prog.stmts)))
for f in [s for s in prog.stmts if isinstance(s, FnDecl)]: self.declare(f, f.name, "fn") # pass 1: hoist
for s in prog.stmts: # pass 2: everything, in order
self.function(s) if isinstance(s, FnDecl) else self.stmt(s)
return [f"{l}:{c}: error: {m}" for l, c, m in sorted(self.errors, key=lambda e: e[:2])]
def function(self, f): # FnDecl or Lambda: a new slot owner
saved, self.owner, self.depth = (self.owner, self.depth), f, self.depth + 1; self.nslots[id(f)] = 0
self.scopes.append(Scope(pending=declared_names(f.body.stmts)))
for p in f.params: self.declare(p, p.name, "param")
for s in f.body.stmts: self.stmt(s) # params + body: one scope (decision 14)
self.scopes.pop(); self.owner, self.depth = saved
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); self.lookup(s, s.name)
elif isinstance(s, If):
self.expr(s.cond); self.stmt(s.then)
if s.else_ is not None: self.stmt(s.else_) # a Block, or the If of `else if`
elif isinstance(s, While): self.expr(s.cond); self.stmt(s.body)
elif isinstance(s, Return) and s.value is not None: self.expr(s.value)
elif isinstance(s, (Print, ExprStmt)): self.expr(s.value if isinstance(s, Print) else s.expr)
elif isinstance(s, Block): # every { } is a scope
self.scopes.append(Scope(pending=declared_names(s.stmts)))
for x in s.stmts: self.stmt(x)
self.scopes.pop()
def expr(self, e):
if isinstance(e, Var): self.lookup(e, e.name)
elif isinstance(e, Lambda): self.function(e)
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(x) for x in [e.callee, *e.args]]
r = Resolver(); print(r.program(parse(open("bazar.haat", encoding="utf-8").read())), len(r.uses), "uses")
for b in r.decls.values(): print(f"{b.line:>2}:{b.col:<2} {b.name:<9}{b.kind:<6}depth {b.depth} slot {b.slot}", "global" if b.is_global else "local")আসল আউটপুট (ব্রাউজারের Python):
[] 18 uses
2:4 price fn depth 0 slot 0 global
7:4 delivery fn depth 0 slot 1 global
2:10 qty param depth 1 slot 0 local
2:20 unit param depth 1 slot 1 local
3:9 p let depth 1 slot 2 local
7:13 total param depth 1 slot 0 local
10:5 first let depth 0 slot 2 global
12:5 total var depth 0 slot 3 global
13:5 rounds var depth 0 slot 4 global
[] মানে কোনো error নেই, আর ১৮টি নাম-ব্যবহার resolve হয়েছে। তালিকার ক্রম লক্ষ করুন: price আর delivery সবার আগে, কারণ প্রথম pass-এ hoisting. তারপর price-এর ভেতরে qty, unit, p পেয়েছে local slot 0, 1, 2; delivery-র total নিজের function-এর slot 0. Top-level-এর first, total, rounds global 2, 3, 4. এই সংখ্যাগুলো reference-এর python -B haat.py dis-এর সঙ্গে হুবহু মেলে: সেখানে DEFINE_GLOBAL 2 ; first, STORE_GLOBAL 3 ; total, আর == price (arity 2, locals 3) ==-এর ভেতরে STORE_LOCAL 2 ; p. দুটি total একই নামের হলেও আলাদা binding: একটি delivery-র param (depth 1, slot 0), অন্যটি global var (depth 0, slot 3).
নিচের stepper-এ একই কাজ ধাপে ধাপে দেখুন। প্রতিটি ধাপের scope stack আর ফল reference-এর resolver.py-কে একটি logging subclass দিয়ে চালিয়ে নেওয়া (ল্যাবে, reference না বদলে)। Scope stack-এ ওপরে বাইরেরটি, নিচে ভেতরেরটি; f0 মানে fn, slot 0; p, l, v মানে param, let, var.
2fn price(qty: Int, unit: Int) -> Int {3 let p = qty * unit;4 if p >= 1000 { return p - p / 10; }5 return p;6}7fn delivery(total: Int) -> Int {8 if total >= 1000 { … } else { … }9}10let first = price(2, 520) + delivery(…);11print(first);12var total = 0;13var rounds = 0;14while total < 5000 { … }15print(total); print(rounds - 1);
| scope stack | |
| এইমাত্র | |
| গণনা |
- Pass 1: hoisting. Top-level scope খোলার সময় তার
pending-এ পাঁচটি নাম। প্রথম pass শুধু দুটিfnঘোষণা করে:priceglobal 0,deliveryglobal 1. বাকি তিনটি (first,total,rounds) এখনো pending. price-এর body. Pass 2 প্রথম statement-এfunction(price)ডাকে: নতুন মালিক, depth 1, নতুন scope. Parameter দুটি সেই scope-এ local slot 0 আর 1. Body দেখেpআগেই pending.let p = qty * unit;আগে initializer:qty(3:13) আরunit(3:19) সবচেয়ে ভেতরের scope-এই পাওয়া গেল, param slot 0 আর 1. তারপর ঘোষণা:pপায় slot 2, pending থেকে সরে।if-এর block. শর্তেরp(4:8) function-এর scope-এ।{ }-এ ঢুকতেই একটি নতুন, খালি scope; ভেতরের দুটিp(4:27, 4:31) এক স্তর ওপরে পাওয়া যায়। Block শেষে scope ফেলে দেওয়া হয়;return p;-এরp(5:12) আবার slot 2.delivery-রtotal. নতুন function, slot-গণনা আবার শূন্য থেকে: paramtotalslot 0. 8:8-এরtotalসবচেয়ে ভেতরের scope-এই মেলে। Global scope-এtotalতখনো pending, কিন্তু খোঁজা সেখানে পৌঁছায়ই না: ভেতরের ঘোষণা আগে পাওয়া গেছে।let first = …আবার top level. Initializer-এর তিনটি নাম (10:13, 10:29, 10:38) hoisted function, global 0, 1, 0. তারপরfirstglobal 2, আর 11:7-এরprint(first)সেটিকেই পায়।- শেষ অংশ.
totalglobal 3,roundsglobal 4.while-এর body একটি block scope, কিন্তু খালি; শর্ত আর body মিলিয়ে পাঁচটি ব্যবহার আর 15:7, 16:7-এর দুটি, সব global-এ যায়। মোট ১৮টি ব্যবহার, কোনো error নেই;<main>-এর local লাগে ০টি,price-এর ৩টি,delivery-র ১টি।
এবার hoisting-এর আসল কারণ দেখা যাক: mutual recursion. Reference-এর examples/mutual.haat-এ দুটি function একে অপরকে ডাকে, আর দুটিকেই ঘোষণার আগেই top level থেকে ডাকা হয়।
2print(is_even(10));3print(is_odd(7));4print(is_even(3));5fn is_even(n: Int) -> Bool {6 if n == 0 { return true; }7 return is_odd(n - 1);8}9fn is_odd(n: Int) -> Bool {10 if n == 0 { return false; }11 return is_even(n - 1);12}
| global scope | |
| ভেতরের scope | |
| এইমাত্র |
- Pass 1, প্রথম function. Top-level scope-এর pending-এ দুটি নাম। প্রথম pass ফাইলের ক্রমে
is_evenঘোষণা করে: global 0.is_oddতখনো pending. - Pass 1, দ্বিতীয় function.
is_oddglobal 1. Pending এখন খালি, অথচ কোনো statement এখনো resolve হয়নি। - Pass 2, ঘোষণার আগের লাইন. লাইন ২–৪-এর তিনটি ডাক লেখায় function-গুলোর আগে, তবু তিনটিই সরাসরি পাওয়া যায়, কারণ নাম দুটি ইতিমধ্যে
names-এ। is_even-এর body. নিজের scope-এnslot 0. 7:12-এরis_oddভেতরে নেই, ওপরের global scope-এ আছে (g1). এক pass-এর compiler এখানে আটকে যেত:is_odd-এর ঘোষণা তখনো পড়াই হয়নি।is_odd-এর body. এরn-ও slot 0, তবে নিজের function-এর: slot-গণনা প্রতিটি function-এর আলাদা। 11:12-এরis_evenglobal 0.- ফল. কোনো error নেই, আর reference চালালে
true,true,false. একই দুটি function একটিfn outer()-এর ভেতরে রাখলে reference বলে2:63: error: 'od' is used before its declaration: nested function hoisted নয় (decision 17), তাই প্রথমটির body-তে দ্বিতীয়টি তখনো pending.
৫ · নিয়মগুলো কোডে — redeclaration, assignment, return আর top-level variable
হাঁটার কাঠামো তৈরি; এবার তার ওপর নিয়ম। Haat-এর resolver মোট সাত রকম error দেয়, আর প্রতিটি একটি spec decision থেকে আসে:
| বার্তা | কোথায় ধরা পড়ে | Decision |
|---|---|---|
undefined variable 'x' | lookup: কোনো scope-এ নেই | spec |
'x' is used before its declaration | lookup: কোনো ভেতরের scope-এ pending | 16, 18 |
'x' is already declared in this scope | declare | 14, 15 |
cannot assign to 'x': it is declared with 'let' | Assign-এর নিয়ম | 19 |
cannot assign to parameter 'n' | ঐ | 19 |
cannot assign to function 'f' | ঐ | 19 |
'return' outside of a function | Return-এর নিয়ম | 20 |
প্রথম তিনটি আগের দুই ব্লকেই আছে। বাকি চারটি তৃতীয় ব্লক যোগ করে, stmt-কে মুড়ে: Return হলে আগে দেখে আমরা কোনো function-এর ভেতরে কি না, আর Assign হলে আগের ব্লকের lookup যে binding পেয়েছে, তার kind দেখে। ব্লকটি তারপর reference-এর examples/err_names.haat আর আরও তিনটি ছোট program পরীক্ষা করে, আর counter.haat-এর function-এর ভেতরের ঘোষণাগুলো দেখায়।
class Resolver(Resolver): # resolver.py: the rules on top of the walk
def stmt(self, s):
if isinstance(s, Return) and self.owner is None: # decision 20
self.error(s, "'return' outside of a function")
super().stmt(s)
b = self.uses.get(id(s)) if isinstance(s, Assign) else None
if b and b.kind != "var": # decision 19: only 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}")
def check_names(src): # like `haat.py check`, names only
r = Resolver(); errors = r.program(parse(src))
return r, errors or ["ok"]
for name in ("err_names.haat", "restock.haat"):
print(f"== {name}"); print(*check_names(open(name, encoding="utf-8").read())[1], sep="\n")
print("== fee:", *check_names("fn fee() -> Int { return rate; }\nlet rate = 5;")[1])
print("== self:", *check_names("let f = fn(n: Int) -> Int { return f(n); };")[1])
r, _ = check_names(open("counter.haat", encoding="utf-8").read())
for b in r.decls.values():
if b.depth > 0:
owner = b.owner.name if isinstance(b.owner, FnDecl) else f"lambda@{b.owner.line}:{b.owner.col}"
print(f"{b.name:<6}{b.kind:<6}owner {owner:<13}slot {b.slot} captured={b.captured}")আসল আউটপুট (ব্রাউজারের Python):
== err_names.haat
3:7: error: undefined variable 'totl'
4:1: error: cannot assign to 'rate': it is declared with 'let'
5:16: error: cannot assign to parameter 'n'
7:11: error: 'later' is used before its declaration
10:5: error: 'rate' is already declared in this scope
11:1: error: 'return' outside of a function
== restock.haat
5:20: error: 'stock' is used before its declaration
== fee: 1:26: error: 'rate' is used before its declaration
== self: 1:36: error: 'f' is used before its declaration
step param owner make_counter slot 0 captured=True
count var owner make_counter slot 1 captured=True
next let owner make_counter slot 2 captured=False
n param owner lambda@18:11 slot 0 captured=False
err_names.haat-এর ছয়টি error reference-এর python -B haat.py check-এর সঙ্গে অক্ষরে অক্ষরে এক, ক্রমসহ; reference-এর examples/err_names.out golden file-এও ঠিক এই ছয় লাইন। চারটি জিনিস লক্ষ করুন। (১) rate = 6; (4:1) let-এ assignment; একই ফাইলে লাইন ১০-এ let rate = 7; আবার ঘোষণা, যা (10:5) redeclaration. (২) fee: function hoisted হলেও তার body একটি top-level variable দেখতে পারে কেবল যদি সেটি function-এর আগে লেখা (decision 18); এখানে rate পরে, তাই top-level scope-এ তখনো pending, আর error 1:26-এ। (৩) self: let f = fn(…) { … f(n) … };-এ initializer আগে resolve হয়, তাই lambda-র ভেতরের f নিজের ঘোষণার আগে ব্যবহৃত; নিজেকে ডাকা function চাইলে fn f(…) লিখতে হয়। (৪) counter.haat: make_counter-এর step আর count captured=True, কারণ ভেতরের lambda এদের ব্যবহার করে; next শুধু নিজের function-এ ব্যবহৃত, তাই False. আর lambda-র মালিকের নাম reference-এর disassembler-এর মতো lambda@line:col (decision 23).
এখন restock.haat-এর error-টি ধীরে দেখা যাক। এটিই decision 16-এর সবচেয়ে শিক্ষণীয় দিক: বাইরে একটি stock আছে, তবু ভেতরের ব্যবহার error.
2let stock = 12;3fn restock(n: Int) -> Int {4 if n > 0 {5 let left = stock - n;6 let stock = left + 50;7 return stock;8 }9 return n;10}11print(restock(5));
| scope stack | |
| এইমাত্র | |
| errors |
- Top level. Pass 1-এ
restockglobal 0; তারপর pass 2-এlet stock = 12;global 1. দুটিই এখনnames-এ। - Function-এর scope.
restock-এর body: paramnslot 0. শর্তেরn(4:8) এখানেই পাওয়া যায়। - ভুলটি ধরা পড়ে.
if-এর block খোলার সময় resolver দেখে, এই blockleftআরstockদুটিই ঘোষণা করবে: দুটিই pending. 5:20-এরstockখুঁজতে গিয়ে প্রথম scope-ই (if-block) বলে “এখানে পরে আসবে”, তাই খোঁজা এখানেই থামে আর error. বাইরের globalstockপর্যন্ত যাওয়াই হয় না। - Resolver থামে না. Error জমা হয়, কাজ চলে: 5:28-এর
nঠিকঠাক slot 0, আরleftঘোষিত হয় slot 1-এ। একটি run-এ সব error দেখানোর জন্যই এই আচরণ (decision 2). - নতুন
stock. 6:21-এরleftslot 1. তারপর ভেতরেরstockঘোষিত হয়, slot 2, আর এটি globalstock-কে ঢেকে দেয় (shadowing). 7:16-এরreturn stockএই নতুনটিকেই পায়। - ফল. Block শেষ, scope ফেলে দেওয়া হলো; 9:12 আর 11:7 ঠিকঠাক। মোট একটি error, reference-এর
check-এর সঙ্গে হুবহু এক। একই আকারের কোড C17 বা Rust-এ বৈধ: সেখানে 5:20-এরstockবাইরের 12 পড়ত (পর্ব ১৫-এর টেবিল)। JavaScript-এরlet-এ চলার সময় ReferenceError হতো; Haat একই ভুল compile-এর আগেই ধরে।
দুটি ছোট বিষয় টেবিলে নেই, কিন্তু কোডে আছে। প্রথমত, assignment-এর error-এর অবস্থান নামের অবস্থান (Assign node-এর line:col, decision 24-এর ধারায়), আর বার্তার লেখা নির্ভর করে binding-এর kind-এর ওপর। দ্বিতীয়ত, decision 18-এর ফাঁক: function hoisted, তাই একটি top-level ডাক function-কে চালাতে পারে তার ব্যবহৃত top-level variable-এর let চলার আগেই। Resolver এটি ধরতে পারে না, কারণ কোন ডাক কখন চলবে তা static-ভাবে সাধারণভাবে জানা অসম্ভব; তাই দুই back end-ই চলার সময় 'k' is not initialized yet দেয় (উদাহরণ পর্ব ১৫-এ)। এটি একটি সচেতন আপস: compile-এর সময় যা নিশ্চিতভাবে ধরা যায় তা ধরা, বাকিটা runtime-এ। এমন বিশ্লেষণ কেন কখনো পুরোপুরি নিখুঁত হতে পারে না, তার তত্ত্ব গণনার তত্ত্ব কোর্সের পর্ব ৫৩-এ (Rice-এর theorem) আর পর্ব ৭৮-এ।
৬ · Slot, depth আর captured — VM-এর জন্য সাজানো AST
Resolver-এর আসল লাভ পরের ধাপে। Interpreter বা VM যদি প্রতিবার নামটি string হিসেবে scope chain ধরে খুঁজত, প্রতিটি variable পড়ায় একাধিক hash lookup লাগত। Resolver একবার খুঁজে প্রতিটি ব্যবহারের পাশে ঠিকানা লিখে রাখে, আর পরের pass শুধু সেই ঠিকানা পড়ে। এমন তথ্য-জোড়া AST-কে বলে decorated (বা annotated) AST; Haat-এ সেটি AST আর Resolution-এর map মিলিয়ে। Bytecode compiler (পর্ব ৫৮) প্রতিটি binding-কে তিন ভাগের একটিতে ফেলে:
| Binding | কোথায় থাকে | Opcode |
|---|---|---|
is_global | program-এর global তালিকার ঘর slot | DEFINE_GLOBAL, LOAD_GLOBAL, STORE_GLOBAL |
local, captured=False | চলতি frame-এর slot | LOAD_LOCAL, STORE_LOCAL |
local, captured=True | slot-এ একটি cell, closure-এর সঙ্গে ভাগ করা | MAKE_CELL, LOAD_CELL, STORE_CELL; ভেতরে LOAD_FREE |
ছবি ৫১.১ — bazar.haat-এর scope গাছ আর প্রতিটি ঘোষণার ঠিকানা
প্রতিটি বাক্স একটি scope. g = global ঘর, s = মালিক function-এর local slot. লাল লেখা দেখায় 8:8-এর total কোথায় resolve হয়, আর global total তখন কোন অবস্থায়।
total দুটি আলাদা বাক্সে, দুটি আলাদা ঠিকানায়। delivery-র body resolve হওয়ার সময় global total তখনো pending, কিন্তু ভেতরের param আগে পাওয়া যায় বলে সেটি কোনো সমস্যা নয়। while-এর block <main>-এর, তবু তার ভেতরের ঘোষণা global হতো না: একাধিক scope খোলা থাকলে নাম local (is_global শুধু সবচেয়ে বাইরের scope-এ)।এবার captured variable-এর আসল bytecode. counter.haat-এর make_counter-এ reference-এর dis (সত্যিকারের run, ট্রিম করা):
~/haat $ python -B haat.py dis examples/counter.haat
== make_counter (arity 1, locals 3) ==
0 LOAD_LOCAL 0 ; step
1 MAKE_CELL 0 ; step
2 CONST 0 ; 0
3 MAKE_CELL 1 ; count
4 MAKE_CLOSURE 1 ; <fn lambda@4:16> captures count, step
5 STORE_LOCAL 2 ; next
6 LOAD_LOCAL 2 ; next
7 RETURN
== lambda@4:16 (arity 0, locals 0) ==
0 LOAD_FREE 0 ; count
1 LOAD_FREE 1 ; step
2 ADD
3 STORE_FREE 0 ; count
4 LOAD_FREE 0 ; count
5 RETURN
পাতার resolver যা বলেছিল, bytecode ঠিক তা-ই মানে: locals 3 (step, count, next = slot 0, 1, 2); step আর count captured, তাই তাদের slot-এ MAKE_CELL; next captured নয়, তাই সাধারণ STORE_LOCAL 2. Lambda-র নিজের কোনো local নেই; সে বাইরের দুটি cell পড়ে LOAD_FREE দিয়ে। add lambda global shared বদলায়, কিন্তু global কখনো captured হয় না: সেখানে STORE_GLOBAL 3, কারণ global তালিকা সব function-এর জন্য একটাই। Cell আর closure-এর পুরো ছবি পর্ব ১৭-এ; Lua ভাষার বাস্তবায়নে এই ধরা variable-কে বলে upvalue.
একটি প্রশ্ন থেকে যায়: depth তাহলে কোথায় লাগে? Haat-এর VM cell দিয়ে closure বানায়, তাই চলার সময় বাইরের frame খুঁজতে হয় না। কিন্তু পর্ব ৩০-এ (Subprogram-এর বাস্তবায়ন) দেখা static link-এর নকশায় একটি variable-এর ঠিকানা হয় একটি জোড়া (কত স্তর ওপরে, কোন slot): ব্যবহারের depth থেকে ঘোষণার depth বাদ দিলে স্তরের সংখ্যা। এই জোড়াকে বলে lexical address; Pascal-ধারার compiler এভাবেই কাজ করত, আর ধারণাটি lambda calculus-এর de Bruijn index-এর আত্মীয়। Resolver দুই নকশার জন্যই তথ্য রাখে: depth আর slot.
শেষে একটি অপচয়। Reference slot আবার ব্যবহার করে না (README: “not reused”). নিচের function-এ x আর y কখনো একসঙ্গে বেঁচে থাকে না, তবু আলাদা ঘর পায় (সত্যিকারের run):
fn split(a: Int) -> Int {
if a > 0 { let x = a; print(x); } else { let y = 0 - a; print(y); }
let z = a * 2;
return z;
}
~/haat $ python -B haat.py dis slots.haat (অংশ)
== split (arity 1, locals 4) ==
5 STORE_LOCAL 1 ; x
12 STORE_LOCAL 2 ; y
18 STORE_LOCAL 3 ; z
চারটি ঘর, যেখানে দুটিই যথেষ্ট। অনুশীলন ১-এ resolver-কে এমনভাবে বদলাবেন যাতে পাশাপাশি block-এর ঘর আবার কাজে লাগে। বাস্তবের compiler এই কাজ অনেক সময় resolver-এ না করে পরে করে, register allocation-এ (পর্ব ৭০), যেখানে variable কোথায় বেঁচে আছে তার সূক্ষ্ম হিসাব থাকে।
৭ · সত্যিকারের compiler-এ — Clang-এর AST-এ resolve করা নাম
Haat-এর resolver আলাদা map রাখে; Clang একই তথ্য সরাসরি AST-এ বসায়। প্রতিটি নাম-ব্যবহার একটি DeclRefExpr node, আর তার ভেতরে ঘোষণার node-এর ঠিকানা। নিচে একটি ছোট C ফাইল, যার ভেতরের block-এ global rate-কে ঢেকে আরেকটি rate (সত্যিকারের run: Zig 0.17.1-এর সঙ্গে আসা clang 22.1.8, x86_64 Windows target; শুধু ঘোষণা আর নাম-ব্যবহারের লাইন রেখে ট্রিম করা; ঠিকানাগুলো প্রতি run-এ বদলায়):
int rate = 10;
int bill(int t) {
int cut = t * rate / 100;
{
int rate = 20;
cut = cut + rate;
}
return t - cut;
}
~/sym $ python -m ziglang cc -fsyntax-only -Xclang -ast-dump rate.c
|-VarDecl 0x20aca0bb9a8 <rate.c:1:1, col:12> col:5 used rate 'int' cinit
`-FunctionDecl 0x20aca0bbb68 <line:2:1, line:9:1> line:2:5 bill 'int (int)'
|-ParmVarDecl 0x20aca0bba90 <col:10, col:14> col:14 used t 'int'
| `-VarDecl 0x20aca10deb0 <col:5, col:26> col:9 used cut 'int' cinit
| | | `-DeclRefExpr 0x20aca10df18 <col:15> 'int' lvalue ParmVar 0x20aca0bba90 't' 'int'
| | `-DeclRefExpr 0x20aca10df38 <col:19> 'int' lvalue Var 0x20aca0bb9a8 'rate' 'int'
| | `-VarDecl 0x20aca10e018 <col:9, col:20> col:13 used rate 'int' cinit
| `-DeclRefExpr 0x20aca10e0f8 <col:21> 'int' lvalue Var 0x20aca10e018 'rate' 'int'
~/sym $ python -m ziglang cc -fsyntax-only -Wshadow rate.c
rate.c:5:13: warning: declaration shadows a variable in the global scope [-Wshadow]
দুটি DeclRefExpr দুটিই 'rate' লেখে, কিন্তু ঠিকানা আলাদা। লাইন ৩-এর (col:19) rate নির্দেশ করে 0x20aca0bb9a8-কে, অর্থাৎ লাইন ১-এর global; লাইন ৬-এর (col:21) rate নির্দেশ করে 0x20aca10e018-কে, ভেতরের block-এর VarDecl. এটিই Haat-এর uses map, শুধু pointer হিসেবে AST-এর ভেতরে। used চিহ্নটিও নাম-হিসাবের ফল: মোটামুটি, ঘোষণাটি কোথাও ব্যবহৃত হয়েছে কি না (পর্ব ৫৪-এর unused-variable warning এ থেকেই আসে)। আর -Wshadow দেখায় symbol table থেকে আরেকটি সুবিধা: ঘোষণার সময় বাইরের scope-এ একই নাম আছে কি না দেখে সতর্ক করা। খেয়াল করুন, C17-এ ভেতরের block-এর লাইন ৫-এর আগে rate ব্যবহার করলে সেটি বাইরেরটিই পেত; Haat-এ সেটি error হতো।
৮ · Reference-এর সঙ্গে মিলিয়ে দেখা — differential test
কয়েকটি উদাহরণে মিল দেখে resolver-কে ঠিক বলা যায় না। ল্যাবে একটি differential test চালানো হয়েছে: একই program পাতার তিন ব্লকের resolver (পাতার parser দিয়ে) আর reference-এর resolver.py (reference-এর parser দিয়ে) দুটিতেই। তুলনা হয় তিন স্তরে: error-এর পুরো তালিকা হুবহু; error না থাকলে প্রতিটি ঘোষণার (name, kind, depth, slot, is_global, মালিক, অবস্থান, captured) আর প্রতিটি ব্যবহার কোন ঘোষণায় গেল; আর প্রতিটি function-এর slot-সংখ্যা reference-এর bytecode compiler-এর locals-এর সঙ্গে।
$ python -B difftest.py 2000
examples 13/13 identical {'clean': 11, 'bindings': 76, 'uses': 141, 'dis_ok': 11, 'with_errors': 1, 'errors_total': 6, 'ref_syntax': 1}
lesson 3/3 identical {'with_errors': 3, 'errors_total': 3}
random 2000/2000 identical {'with_errors': 1992, 'errors_total': 17579, 'clean': 8, 'bindings': 15, 'uses': 7, 'dis_ok': 8}
scoped 2000/2000 identical {'with_errors': 1340, 'errors_total': 3381, 'clean': 660, 'bindings': 3881, 'uses': 3400, 'dis_ok': 660}
চারটি দল, মোট ৪,০১৬টি program. (১) Reference-এর ১৩টি উদাহরণ; একটি (err_syntax) parser-এই থামে, তাই resolver পর্যন্ত যায় না। (২) এই পর্বের তিনটি ছোট program. (৩) “এলোমেলো”: seed 51 দিয়ে ২,০০০টি program, যেখানে নাম ইচ্ছামতো বাছা হয়; প্রায় সবগুলোতে error, মোট ১৭,৫৭৯টি, আর সাত রকম বার্তার সবগুলোই এসেছে (সবচেয়ে বেশি undefined variable, ১৩,৫০৬টি)। এই দল error-পথ পরীক্ষা করে। (৪) “scope-সচেতন”: একই seed-এ আরেকটি generator, যা মনে রাখে কোন নাম কোথায় দেখা যায়, nested function, lambda আর capture বানায়; ৬৬০টি error ছাড়াই resolve হয়, যাদের ৩,৮৮১টি ঘোষণা, ৩,৪০০টি ব্যবহার আর সব function-এর slot-সংখ্যা মিলেছে, আর ৮৯টি program-এ মোট ১০৩টি captured variable ছিল। এলোমেলো দলে মাত্র ৮টি program error ছাড়া চলে, তাই slot আর captured-এর ভুল সেখানে প্রায় ধরা পড়ত না; আবার scope-সচেতন দলে redeclaration বা top-level return কখনো আসে না (generator সবসময় নতুন নাম বাছে)। দুই রকম generator রাখার কারণ এটাই: একটি error-পথ, অন্যটি ঠিক-পথ পরীক্ষা করে। Fuzzing-এর পদ্ধতি নিয়ে বিস্তারিত Software Testing কোর্সের পর্ব ৬০-এ।
Error-এর ক্রম মেলাতে একটি সূক্ষ্মতা লেগেছে। Reference সব error অবস্থান অনুযায়ী সাজায় কেবল (line, col) দিয়ে, আর Python-এর sort stable, অর্থাৎ একই অবস্থানের দুটি error যে ক্রমে এসেছিল সেই ক্রমেই থাকে। পাতার কোড tuple-এর তৃতীয় অংশ (বার্তা) দিয়েও সাজালে কিছু বিরল ক্ষেত্রে ক্রম বদলাতে পারত; তাই key=lambda e: e[:2]. এমন খুঁটিনাটি golden file আর differential test ছাড়া চোখে পড়া কঠিন।
আরও গভীরে: বড় compiler-এ name resolution প্রায়ই একটি একক pass নয়। C++-এ একটি নাম কী বোঝায় তা কখনো template instantiation পর্যন্ত জানা যায় না (দুই-ধাপের name lookup), আর argument-dependent lookup function-এর argument-এর type দেখে নাম খোঁজে, অর্থাৎ নাম আর type-এর কাজ জড়িয়ে যায়। Rust compiler-এ নাম resolve করা আর macro expand করা একসঙ্গে পুনরাবৃত্তি করে চলে, কারণ macro নতুন নাম তৈরি করতে পারে। IDE-র জন্য লেখা language server (যেমন rust-analyzer) আবার প্রতিটি টাইপের পরে পুরো কাজ নতুন করে করতে পারে না; তারা ফলাফল cache করে আর বদলানো অংশটুকুই আবার হিসাব করে, যেখানে persistent কাঠামো কাজে লাগে (পর্ব ৮০-তে language tooling).
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- Symbol table-এ কী কী থাকে? নাম, ধরন (variable/function/parameter), type, scope বা depth, ঠিকানা বা slot, ঘোষণার অবস্থান; প্রয়োজনে used/captured-এর মতো চিহ্ন।
- Nested scope-এর জন্য symbol table কীভাবে সাজাবেন? Scope-প্রতি hash table-এর stack; বা এক hash table যেখানে প্রতিটি নামের ঘোষণার stack আর scope শেষে সেই scope-এর নাম মোছা; বা persistent map.
- Forward reference বা mutual recursion কীভাবে সামলাবেন? দুই pass: আগে ঘোষণা সংগ্রহ (hoisting), পরে body resolve; এক-pass compiler-এ forward declaration বা prototype লাগে।
- একটি নাম-ব্যবহারের lexical address কী? (ব্যবহার আর ঘোষণার function-depth-এর পার্থক্য, slot); static link ধরে চলার সময় এটি দিয়ে variable পাওয়া যায়।
- Closure-এর জন্য resolver কী জানায়? কোন local ভেতরের function ব্যবহার করে (captured), যাতে সেটি stack-এর বদলে cell বা heap-এ রাখা হয়।
৯ · AI-এর যুগে symbol table আর resolver
“একটি ছোট ভাষার name resolver লিখে দাও” চাইলে AI assistant দ্রুত একটি scope stack দেবে, আর সাধারণ উদাহরণে সেটি চলবেও। ভুল লুকিয়ে থাকে নিয়মের কিনারায়, আর সেখানে AI প্রায়ই এক ভাষার নিয়ম অন্য ভাষায় চাপিয়ে দেয়। বারবার দেখা ভুল:
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
let-এ আগে ঘোষণা, পরে initializer (C-র নিয়ম), ফলে let a = a + 1; নিজেকেই পড়ে | Spec-এর decision 16 পড়া; { let price = price + 75; }-এর মতো test |
| Pending না রেখে শুধু “এখন পর্যন্ত ঘোষিত” দেখা, ফলে বাইরের একই নামের variable ধরা পড়ে | বাইরে আর ভেতরে একই নাম রেখে ভেতরে ঘোষণার আগে ব্যবহার |
“Python-এ block scope আছে” বা “JavaScript-এর var block-এ সীমিত” জাতীয় সাধারণীকরণ | ভাষা আর version ধরে চালিয়ে দেখা (পর্ব ১৫-এর তুলনা) |
| সব function-এর জন্য একটিই slot-গণনা, বা global-কেও captured চিহ্ন দেওয়া | Bytecode-এর locals আর opcode-এর সঙ্গে মেলানো (dis) |
| Nested function-ও hoist করা, বা top-level-ও না করা | Mutual recursion-এর দুটি test: top level-এ চলবে, nested-এ error |
| প্রথম error-এ থেমে যাওয়া, বা error-এর ক্রম আর অবস্থান আন্দাজে | Golden file-এর সঙ্গে হুবহু diff |
| অস্তিত্বহীন compiler flag বা “symbol table dump” option বানানো | Compiler-এর নিজের documentation আর --help-এ খোঁজা; চালিয়ে দেখা |
AI-কে কাজে লাগানোর ভালো উপায়: নিয়মগুলো নিজে লিখে দিন, error message-এর হুবহু লেখা দিন, আর কোডের সঙ্গে test চান। তারপর নিজের reference-এর সঙ্গে differential test চালান।
AI-এর লেখা resolver হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১C আর Pascal-এ “আগে ঘোষণা, পরে ব্যবহার” কেন এত কড়া ছিল, আর Haat দুই pass নিয়ে কী কিনল, কী হারাল?
১৯৭০-এর দশকের যন্ত্রে memory ছিল খুব কম, আর পুরো program-কে একসঙ্গে memory-তে রাখা অনেক সময় সম্ভব হতো না। তাই Wirth-এর Pascal আর Ritchie-র C দুটিই এমনভাবে নকশা করা যে compiler ফাইলটি একবার ওপর থেকে নিচে পড়েই কাজ শেষ করতে পারে: এক-pass compiler. এর শর্ত একটিই, কোনো নাম ব্যবহারের আগে তার ঘোষণা পড়া হয়ে থাকতে হবে। Mutual recursion-এর জন্য তাই আলাদা ব্যবস্থা লাগল: Pascal-এ forward ঘোষণা, C-তে function prototype, যা আজও header ফাইলের মূল কাজ। এর প্রভাব শুধু compiler-এ নয়, প্রোগ্রামারের অভ্যাসেও পড়ল: C-তে ফাইলের ওপরে prototype লেখা, নিচে body.
পরের প্রজন্মের ভাষা এই বাধা অনেকটা তুলে দিল। Java-য় একটি class-এর method যেকোনো ক্রমে লেখা যায়, কারণ compiler আগে পুরো class-এর ঘোষণা সংগ্রহ করে। Haat একই কাজ করে কেবল top level-এ: প্রথম pass function-এর নাম নিবন্ধন করে, দ্বিতীয় pass body. লাভ স্পষ্ট: is_even আর is_odd কোনো prototype ছাড়াই একে অপরকে ডাকে, আর ফাইলের ক্রম পাঠকের সুবিধামতো সাজানো যায়।
হারানোর দিকও আছে। প্রথমত, decision 18-এর ফাঁক: hoisted function চলতে পারে তার ব্যবহার করা top-level variable তৈরি হওয়ার আগেই, তাই একটি runtime পরীক্ষা (not initialized yet) লাগে, যা এক-pass নকশায় অপ্রয়োজনীয় হতো। দ্বিতীয়ত, nested function hoist না করার সিদ্ধান্ত একটি অসমতা তৈরি করে: একই দুটি function বাইরে চলে, ভেতরে চলে না। Haat এটি মেনে নিয়েছে, কারণ nested function-কে hoist করলে closure-এর প্রশ্ন জটিল হয়: hoisted nested function যদি বাইরের এমন variable ধরে যা তখনো তৈরি হয়নি? JavaScript এই সব প্রশ্নের উত্তর দিয়েছে hoisting আর TDZ মিলিয়ে, তার জটিলতাসহ। Haat-এর বেছে নেওয়া পথ সরল, আর তার সীমা একটি error message-এ স্পষ্ট।
মূল উপলব্ধি: ঘোষণার ক্রমের নিয়ম আসলে compiler-এর pass-সংখ্যার ছায়া; কত pass নেবেন, সেই সিদ্ধান্ত ভাষার ব্যবহারকারীর অভিজ্ঞতা আর runtime-এর পরীক্ষা দুটিকেই বদলায়।
প্র ০২Haat “block-এ পরে ঘোষিত নাম আগে ব্যবহার” নিষেধ করে, C আর Rust বাইরের নামটি দেখে। কোনটি ভালো নকশা, আর resolver-এর খরচ কোথায় বাড়ে?
C17-এ একটি variable-এর scope শুরু হয় তার declarator শেষ হওয়ার ঠিক পরে, আর Rust-এ let statement শেষ হওয়ার পরে। দুই ভাষাতেই let a = stock - n; let stock = …;-এর প্রথম stock বাইরের variable. এটি এক-pass resolver-এর জন্য স্বাভাবিক: যা পড়া হয়েছে তা-ই দেখা যায়। Rust এই আচরণকে ইচ্ছাকৃতভাবে কাজে লাগায়: let x = x.trim();-এর মতো shadowing তার একটি পরিচিত idiom.
JavaScript ২০১৫ সালে (ES2015) let আর const আনার সময় অন্য পথ নিল: নামটি পুরো block জুড়ে বাঁধা, কিন্তু ঘোষণা চলার আগে ব্যবহার করলে ReferenceError, যাকে বলে temporal dead zone. যুক্তি ছিল পাঠকের দিক থেকে: একই block-এ এক লাইনের ব্যবধানে একই নাম দুটি আলাদা জিনিস বোঝালে কোড পড়া কঠিন, আর এমন কোড প্রায়ই ভুল। Haat এই নিয়ম নিয়েছে, কিন্তু JavaScript-এর মতো চলার সময় নয়, compile-এর আগেই ধরে: resolver-এর pending set ঠিক এই কাজের জন্য।
খরচ সামান্য কিন্তু বাস্তব। প্রতিটি block-এ ঢোকার সময় তার statement তালিকা একবার দেখে ঘোষিত নামের set বানাতে হয় (declared_names), অর্থাৎ statement-এর সংখ্যার সমানুপাতিক কাজ, যা পুরো resolver-এর রৈখিক খরচকে বদলায় না। আসল খরচ নকশার: resolver আর এক-pass থাকে না, কারণ block-এর ভবিষ্যৎ জানা লাগে। পুরো AST আগে থেকে memory-তে থাকায় Haat-এর জন্য এটি সমস্যা নয়।
কোনটি “ভালো”, তা নির্ভর করে ভাষার লক্ষ্যের ওপর। Rust-এ shadowing একটি সুবিধা, কারণ সেখানে type রূপান্তরের ধাপে একই নাম রাখা স্বাভাবিক, আর borrow checker অনেক ভুল এমনিতেই ধরে। শেখার ভাষা Haat-এ স্পষ্টতা আগে: একটি block-এ একটি নাম একটিই জিনিস। দুই পথের কোনোটিই অন্যটির চেয়ে নিঃশর্তে শ্রেষ্ঠ নয়; যা জরুরি তা হলো নিয়মটি স্পষ্ট লেখা থাকা আর compiler সেটি হুবহু মানা।
মূল উপলব্ধি: একই কোডের তিন রকম অর্থ (বাইরের নাম, error, runtime error) তিনটি বৈধ নকশা-সিদ্ধান্ত; resolver-এর কাজ সিদ্ধান্তটি ঠিকভাবে বাস্তবায়ন করা, আর AI বা মানুষ কারও অনুমানে এক ভাষার নিয়ম অন্য ভাষায় না চাপানো।
প্র ০৩Compiler একবার চলে শেষ, কিন্তু editor প্রতিটি অক্ষর টাইপের পরে নাম চেনে। IDE-র symbol table কেন আলাদা রকমের হতে হয়?
Batch compiler-এর জন্য symbol table একটি সাময়িক কাঠামো: resolver চলার সময় scope খোলে, বন্ধ করে, শেষে শুধু ফল (Haat-এ Resolution) রেখে বাকিটা ফেলে দেয়। পুরো কাজ একবার, আর সময় সাধারণত ফাইলের আকারের রৈখিক। Editor-এর চাহিদা অন্যরকম। “Go to definition”, “rename symbol”, “এখানে কোন নাম দেখা যায়” (auto-complete)-এর মতো প্রশ্ন আসে যেকোনো লাইন থেকে, যেকোনো মুহূর্তে, আর প্রতিটি টাইপের পরে উত্তর বদলাতে পারে।
এই কারণে editor-এর পেছনের language server (Microsoft ২০১৬ সালে Language Server Protocol প্রকাশ করে, পরে বহু editor এটি গ্রহণ করে) দুটি জিনিস চায়। প্রথমত, প্রতিটি জায়গার environment মনে রাখা, যাতে auto-complete-এর প্রশ্নে আবার পুরো ফাইল হাঁটতে না হয়। Persistent map এখানে স্বাভাবিক: প্রতিটি scope-এর environment একটি snapshot, যা পরের scope-এর সঙ্গে বেশিরভাগ অংশ ভাগ করে, তাই হাজারটি snapshot রাখাও সস্তা। এই পর্বের JavaScript ব্লকে Persistent-এর snapshot সব exit-এর পরেও অক্ষত ছিল: এটিই সেই গুণ।
দ্বিতীয়ত, incremental হিসাব: একটি function-এর ভেতরে এক অক্ষর বদলালে অন্য ফাইলের symbol table আবার বানানো অপচয়। rust-analyzer-এর মতো আধুনিক টুল একটি query-ভিত্তিক কাঠামো ব্যবহার করে (প্রতিটি হিসাব একটি query, ফল cache, আর ইনপুট বদলালে শুধু নির্ভরশীল query আবার চলে); খুঁটিনাটি টুলভেদে আলাদা। তৃতীয় একটি চাহিদা ভাঙা কোড: টাইপ করার মাঝপথে ফাইল প্রায় কখনো সম্পূর্ণ সঠিক নয়, তাই parser-কে error recovery করতে হয় (পর্ব ৫০, Parser-এর error recovery) আর resolver-কে আধা-ভাঙা AST-এও যতটা সম্ভব উত্তর দিতে হয়। Haat-এর reference প্রথম phase-এর error-এ পরের phase চালায় না (decision 2); একটি IDE এভাবে চলতে পারে না।
মূল উপলব্ধি: একই কাজ (নাম থেকে ঘোষণা) দুই রকম ব্যবহারে দুই রকম ডেটা কাঠামো চায়: একবার চলা compiler-এ সরল stack, বারবার প্রশ্ন করা editor-এ snapshot রাখা যায় এমন persistent আর incremental কাঠামো। পর্ব ৮০-তে language tooling-এ এর বাকি অংশ।
প্র ০৪Static link, display আর cell — resolver-এর একই তথ্য (depth, slot, captured) চলার সময় তিনভাবে কাজে লাগে। কেন Haat cell বেছে নিল?
ALGOL 60 nested procedure আর block structure চালু করার পর প্রশ্ন উঠল: ভেতরের procedure বাইরের procedure-এর local variable চলার সময় কীভাবে খুঁজবে? প্রথম দিকের উত্তর ছিল static link: প্রতিটি frame-এ লেখার দিক থেকে ঘিরে থাকা function-এর frame-এর pointer. Resolver একটি ব্যবহারকে (স্তরের পার্থক্য, slot) জোড়ায় রূপান্তর করে; চলার সময় সেই সংখ্যক বার static link ধরে ওপরে গিয়ে slot পড়া হয়। Display এই শৃঙ্খলকে একটি array-তে রাখে, প্রতিটি nesting স্তরের জন্য একটি pointer, যাতে যেকোনো স্তর এক ধাপে পাওয়া যায়, তবে call আর return-এ array হালনাগাদ রাখার খরচ আছে। দুটির বিস্তারিত পর্ব ৩০-এ।
দুটি নকশাই ধরে নেয় যে বাইরের frame ভেতরের function-এর চেয়ে বেশি দিন বাঁচে। Pascal-এ এটি সত্য, কারণ nested procedure-কে বাইরে ফেরত দেওয়া যায় না। কিন্তু Haat-এ function প্রথম-শ্রেণির মান: make_counter ফেরত দেয় একটি closure, যা count ধরে রাখে make_counter-এর frame শেষ হওয়ার পরেও। এটি upward funarg সমস্যা (পর্ব ১৭)। তখন static link একটি মৃত frame-কে নির্দেশ করবে।
Haat-এর সমাধান flat closure আর cell: resolver যে local-কে captured চিহ্ন দেয়, শুধু সেগুলো একটি cell-এ (heap-এ এক-ঘরের বাক্সে) যায়, আর closure তৈরির সময় সেই cell-গুলোর reference নিজের সঙ্গে নেয়। ফলে চলার সময় কোনো শৃঙ্খল হাঁটতে হয় না (LOAD_FREE i সরাসরি), আর যে variable কেউ ধরে না সেগুলো সাধারণ slot-এ থাকে, বাড়তি খরচ ছাড়া। Lua 5.0-এর বাস্তবায়ন (Ierusalimschy, de Figueiredo ও Celes-এর প্রবন্ধ, ২০০৫ সালের দিকে প্রকাশিত) একটি মাঝামাঝি পথ নেয়: upvalue frame চালু থাকা পর্যন্ত stack-এর ঘরকেই নির্দেশ করে, frame শেষ হলে মান heap-এ সরে যায় (“closing”). তিন নকশাতেই resolver-এর একই তথ্য লাগে; শুধু ব্যবহার আলাদা।
দাম কোথায়? Cell-এর জন্য প্রতিটি captured variable-এ একটি বাড়তি heap বরাদ্দ আর প্রতিটি পড়ায় একটি বাড়তি indirection. আর resolver-কে ঠিকঠাক জানতে হয় কোনটি captured; একটি ভুল (যেমন global-কে captured ধরা, বা lambda-র মালিক বদলাতে ভুলে যাওয়া) VM-এ সরাসরি ভুল ঘর পড়ায়। এ কারণেই অংশ ৮-এর differential test-এ captured চিহ্নও তুলনা করা হয়েছে।
মূল উপলব্ধি: Resolver চলার সময়ের নকশা ঠিক করে না, কিন্তু তাকে সম্ভব করে; কোন তথ্য (depth, slot, captured) রাখবেন তা বেছে নিতে হয় back end কী চাইবে তা মাথায় রেখে।
প্র ০৫Resolve হয়ে গেলে নামের আর কী দরকার? কেন অনেক compiler নামকে সংখ্যা বা অনন্য পরিচয়ে বদলে ফেলে?
Resolver-এর পরে একটি নামের অক্ষরমালা আর তেমন কাজের নয়: total দুটি, দুটি আলাদা binding, আর পরের pass-গুলোকে binding-টাই জানতে হয়। Haat-এ এই কাজ করে uses map, যা node-এর id থেকে Binding-এ যায়; Clang-এ DeclRefExpr-এর ভেতরের pointer. দুটিই আসলে নামের বদলে একটি অনন্য পরিচয়।
এই ধারণার একটি গাণিতিক রূপ আছে। ওলন্দাজ গণিতবিদ N. G. de Bruijn ১৯৭২ সালে lambda calculus-এ bound variable-এর নামের বদলে একটি সংখ্যা ব্যবহারের প্রস্তাব দেন: “কত স্তর বাইরের λ এটিকে বাঁধে”। তখন λx. λy. x আর λa. λb. a হুবহু একই লেখা হয়, তাই নাম বদলের (alpha-renaming) সমস্যা আর থাকে না। এটি প্রায় হুবহু অংশ ৬-এর lexical address-এর প্রথম অংশ। Theorem prover আর কিছু functional compiler-এর ভেতরে de Bruijn index বা তার রূপান্তর ব্যবহার হয় (পর্ব ৪৩-এ lambda calculus).
বড় compiler প্রায়ই resolve-এর পরে প্রতিটি binding-কে একটি অনন্য পরিচয় দেয় (একটি সংখ্যা বা “unique”), যাতে পরের optimization নিশ্চিন্তে code সরাতে, কপি করতে (inlining, পর্ব ৬৭) বা জুড়তে পারে, নামের সংঘাতের ভয় ছাড়া। দুটি total একটি function-এ inline হয়ে একসঙ্গে এলে নাম দিয়ে আলাদা করা যেত না, পরিচয় দিয়ে যায়। একই কারণে compiler নামের string-গুলো একবারই রাখে (interning) আর তুলনা করে pointer দিয়ে।
উল্টো দিকের প্রশ্ন macro-তে আসে: macro যদি নতুন code তৈরি করে যাতে tmp নামের variable আছে, আর ব্যবহারকারীরও একটি tmp থাকে? নাম দিয়ে resolve করলে দুটি মিশে যায়। Scheme-এর hygienic macro এই সমস্যার সমাধান হিসেবে এসেছে, যার মূল ধারণাও ঠিক এটাই: নাম নয়, কোথা থেকে এসেছে সেই পরিচয় দিয়ে resolve করা। এর বিস্তার পর্ব ৭৮-এ।
মূল উপলব্ধি: নাম মানুষের জন্য, পরিচয় compiler-এর জন্য; resolver এই দুইয়ের মাঝের সেতু, আর তার পরে যত তাড়াতাড়ি নামকে পরিচয়ে বদলানো যায়, পরের pass-গুলো তত নিরাপদ।
অনুশীলন
প্রথমে নিজে করুন, তারপর উত্তর খুলে মেলান। প্রতিটি আউটপুট Haat reference বা পাতার resolver-এর সত্যিকারের run থেকে।
-
নকশা ও বাস্তবায়ন — slot আবার ব্যবহার: পাতার
Resolver-কে বাড়িয়েReuseSlotsলিখুন, যাতে একটি block শেষ হলে তার local slot-গুলো পাশের block আবার ব্যবহার করতে পারে, কিন্তু function-এরnslotsহয় একসঙ্গে লাগা সর্বোচ্চ সংখ্যা। অংশ ৬-এরsplit-এ কয়টি ঘর লাগবে? আর captured variable থাকলে এটি কি নিরাপদ?Block-এ ঢোকার আগে চলতি function-এর গণনা মনে রাখুন, block শেষে সেখানে ফিরিয়ে দিন, আর পথে দেখা সর্বোচ্চটি আলাদা রাখুন:
class ReuseSlots(Resolver): # sibling blocks share slots def stmt(self, s): if not isinstance(s, Block): return super().stmt(s) key = None if self.owner is None else id(self.owner) mark = self.nslots[key] # slots in use before the block super().stmt(s) self.high[key] = max(self.high.get(key, 0), self.nslots[key]) self.nslots[key] = mark # the block's slots are free again def program(self, prog): self.high = {}; errors = super().program(prog) for k, n in self.high.items(): self.nslots[k] = max(self.nslots[k], n) return errorsল্যাবের সত্যিকারের run:
split-এaslot 0, আরx,y,zতিনটিই slot 1;nslots৪ থেকে নেমে ২. একই ধারণা reference-এরblock()-এ লাগিয়ে reference-এর compiler আর VM-এ চালানো হয়েছে: ১০টি চালানো যায় এমন উদাহরণ আরslots.haat, মোট ১১টির ১১টিতেই আউটপুট আগের VM আর tree-walking interpreter-এর সঙ্গে হুবহু এক, আর সব function মিলিয়ে local ঘর ৩৯ থেকে ৩৬ (shadowing.haat-এ ৪ → ৩,slots.haat-এ ৪ → ২)। অংশ ৮-এর ৬৬০টি error-হীন scope-সচেতন program-এ এই পাতারReuseSlotsআর reference-ধাঁচের রূপ ৬৬০টিতেই একই slot দিয়েছে।Captured variable-এও নিরাপদ, কারণ পুরোনো slot-এর variable-এর scope শেষ, তাকে আর কেউ নামে পড়তে পারে না। কোনো closure যদি তাকে ধরে থাকে, closure-এর হাতে আছে cell-এর reference, slot-এর নয়; পাশের block একই slot-এ নতুন
MAKE_CELLকরলে একটি নতুন cell তৈরি হয়, পুরোনোটি closure-এর কাছে অক্ষত থাকে। একই যুক্তিতেwhile-এর প্রতিটি পাকে নতুন cell হয় (decision 14). -
ভুল খুঁজুন — আগে ঘোষণা: একজন
Let-এর শাখা “সরল” করলেন:self.declare(s, s.name, …); self.expr(s.init), অর্থাৎ আগে ঘোষণা, পরে initializer.bazar.haatআগের মতোই চলে,restock.haat-এ error-ও একই। ভুলটি কোথায়, কোন ইনপুটে ধরা পড়ে, আর না ধরা পড়লে চলার সময় কী হয়?let price = 500; { let price = price + 75; print(price); }আগে ঘোষণা করলে initializer-এর
priceনতুন, এখনো মান-না-পাওয়াprice-কেই পায়: এটি C-র নিয়ম, Haat-এর নয় (decision 16). সঠিক resolver এখানে3:17: error: 'price' is used before its declarationদেয় (reference-এরcheck-ও হুবহু তাই); বাগওয়ালাটি কিছুই বলে না।restock.haat-এ ভুলটি ধরা পড়ে না, কারণ সেখানে সমস্যার নাম অন্য statement-এর (left-এর initializer), আর সেই সময়ে নতুনstockতখনো pending.ল্যাবে বাগওয়ালা resolution reference-এর type checker আর VM-এ দিলে: type checker কিছু ধরেনি (সে resolver-এর ফল বিশ্বাস করে), আর VM ভেঙেছে Python-এর নিজের error দিয়ে:
TypeError unsupported operand type(s) for +: 'NoneType' and 'int', অর্থাৎ খালি slot পড়ে যোগ করার চেষ্টা। একটি পরিষ্কার Haat error-এর বদলে ভেতরের crash: resolver-এর ভুল পরের ধাপে কত খারাপ চেহারা নেয়, তার উদাহরণ। অংশ ৮-এর ২,০০০টি scope-সচেতন program-এর ৮৪টিতে বাগওয়ালা resolver-এর error-তালিকা আলাদা হয়েছে, তাই differential test এটি সঙ্গে সঙ্গে ধরত। -
আউটপুট বলুন: (ক) নিচের ফাইলে
python haat.py checkকী ছাপবে, ক্রম আর line:col-সহ? (খ) লাইন ৩-এরlet total = total + x;বদলেtotal = total + x;লিখলে, আর লাইন ৬–৭ মুছলে, কোন নাম কোন global নম্বর বা slot পাবে, আরprint(add(5));কী ছাপবে?var total = 0; fn add(x: Int) -> Int { let total = total + x; return total; } { let x = 1; let x = 2; } add = fn(y: Int) -> Int { return y; }; print(add(5));(ক) Reference-এর সত্যিকারের আউটপুট (পাতার resolver-ও হুবহু একই তিন লাইন দেয়):
3:17: error: 'total' is used before its declaration 6:18: error: 'x' is already declared in this scope 7:1: error: cannot assign to function 'add'লাইন ৩: function-এর scope-এ
totalপরে ঘোষিত (ঠিক এই statement-এই), তাই initializer-এরtotal(column 17) pending; বাইরেরvar totalপর্যন্ত খোঁজা যায় না। লাইন ৬: একই block-এ দ্বিতীয়x; error তার নামের ঘরে, column 18 ({ let x = 1; let-এর ১৭টি অক্ষরের ঠিক পরে)। লাইন ৭:addএকটি hoistedfn, তাই assignment নিষেধ (decision 19). Resolver error দিলে type checker আর চলে না, তাই লাইন ৮-এর কিছু আসে না।(খ) Hoisting-এর কারণে
addglobal 0, তারপরtotalglobal 1;xহলোadd-এর slot 0. Reference-এরdis:== add (arity 1, locals 1) ==, তার ভেতরেLOAD_GLOBAL 1 ; total,LOAD_LOCAL 0 ; x,STORE_GLOBAL 1 ; total. চালালে ছাপে5. -
প্রমাণ — resolver লেখার ক্রম মানে: দেখান যে Haat-এর resolver কোনো ব্যবহারকে এমন ঘোষণার সঙ্গে জোড়ে না যা একই block-এ ব্যবহারের পরে লেখা, top-level
fnছাড়া। আরও দেখান যে n-টি AST node আর সর্বোচ্চ d গভীরতার scope-এ মোট কাজ O(n·d).প্রমাণের রূপরেখা:
- অপরিবর্তনীয় শর্ত (invariant): resolver যখন একটি block B-এর k-তম statement-এ, তখন names(B)-এ আছে ঠিক B-এর প্রথম k−1টি statement-এর ঘোষিত নাম (function-এর scope-এ parameter-সহ; top level-এ সব
fn-সহ), আর pending(B)-এ B-এর বাকি ঘোষিত নাম, যা names-এ নেই। ভিত্তি: B খোলার সময় names খালি (বা শুধু parameter বা hoisted fn), আর pending =declared_names-এর ফল থেকে সেগুলো বাদ। ধাপ:declareএকটি নাম names-এ যোগ করে আর pending থেকে সরায়, আর এটি ঘটে ঠিক তার statement-এ পৌঁছালে। Let-এর initializer:stmtআগেexpr(s.init)ডাকে, পরেdeclare; তাই initializer resolve-এর মুহূর্তে নামটি এখনো pending, invariant অটুট।- দাবি: ধরুন একটি ব্যবহার u, যা block B-এর ভেতরে (বা B-এর ভেতরের কোনো block বা function-এ), এমন ঘোষণা D-এর সঙ্গে জোড়া পেল যা B-এ u-এর পরে লেখা আর top-level
fnনয়। u resolve-এর মুহূর্তে invariant অনুযায়ী D-এর নাম pending(B)-এ, names(B)-এ নয়।lookupভেতর থেকে বাইরে যায়; B-তে পৌঁছালে pending দেখে error দিয়ে থামে, তাই D ফেরত আসে না। B-এর ভেতরের কোনো scope-এ একই নাম থাকলে সেটি আগেই ফেরত আসে, D নয়। দুই ক্ষেত্রেই বিরোধ। ∎ (Top-levelfnব্যতিক্রম, কারণ pass 1 সেগুলো আগেই names-এ রাখে।) - খরচ: প্রতিটি node একবার দেখা হয়। প্রতিটি block আর function খোলার সময়
declared_namesতার statement-গুলো একবার দেখে, আর প্রতিটি statement ঠিক একটি block-এর, তাই মোট O(n). প্রতিটিlookupসর্বোচ্চ d-টি scope দেখে, প্রতিটিতে গড়ে O(1) hash; ব্যবহার ≤ n, তাই O(n·d).bazar.haat-এ: ১৮টি ব্যবহার, সর্বোচ্চ ৩টি scope (global, price, if-block).
এক hash table-এর নকশা (অংশ ২-এর তৃতীয়টি) নিলে lookup গড়ে O(1) হয়, আর scope শেষে মোছার মোট খরচ ঘোষণার সংখ্যার সমান, তাই মোট গড়ে O(n). কিন্তু তখন pending-এর জন্যও নামপ্রতি একটি চিহ্ন রাখতে হবে; চেষ্টা করে দেখতে পারেন।
- অপরিবর্তনীয় শর্ত (invariant): resolver যখন একটি block B-এর k-তম statement-এ, তখন names(B)-এ আছে ঠিক B-এর প্রথম k−1টি statement-এর ঘোষিত নাম (function-এর scope-এ parameter-সহ; top level-এ সব
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমHaat-এর resolver fn price(qty: Int, unit: Int) -> Int-এর body-তে let p = qty * unit; পেলে যে কাজগুলো করে, সেগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
stmt()একটিLetদেখে, আগে initializer resolve করতে নামেqtyখোঁজে: function-এর scope-এ param, slot 0unitখোঁজে: একই scope-এ param, slot 1declare: একই scope-এpআগে নেই, তাই কোনো redeclaration error নয়pপায়price-এর পরের slot, 2ppending থেকেnames-এ যায়, আর পরেরp-ব্যবহার এটিকেই পায়
Haat program: let stock = 12; / fn f() -> Int { / let a = stock; / let stock = 5; / return a + stock; / } / print(f()); (সাত লাইন; লাইন ৩-এর stock শুরু column 13-এ)। python haat.py check কী দেয়?
- ok, আর চালালে
17(a = 12, stock = 5) 3:13: error: undefined variable 'stock'3:13: error: 'stock' is used before its declaration4:9: error: 'stock' is already declared in this scope
তিনটি symbol table নকশার কোনটিতে একটি scope শেষ করার (exit) খরচ সেই scope-এ ঘোষিত নামের সংখ্যার সমানুপাতিক?
- Scope-প্রতি একটি hash map-এর stack
- Persistent map (linked list বা balanced tree)
- দুটিই, কারণ দুটিতেই lookup ধীর
- এক hash table, যেখানে প্রতিটি নামের পাশে ঘোষণার stack
Haat-এ var shared = 100; (top level), তারপর let add = fn(n: Int) { shared = shared + n; };. Resolver আর bytecode compiler shared-কে কীভাবে দেখে?
- captured=True, তাই একটি cell-এ রাখা হয় আর lambda পড়ে
LOAD_FREEদিয়ে - global, captured নয়; lambda পড়ে আর লেখে
LOAD_GLOBAL/STORE_GLOBALদিয়ে - Lambda-র একটি local slot, যেখানে
shared-এর কপি থাকে cannot assign to 'shared'error, কারণ lambda বাইরের variable বদলাতে পারে না
Haat function: fn f(a: Int, b: Int) -> Int { let c = a + b; if c > 0 { let d = c; return d; } return c; }. Reference-এর bytecode-এ f-এর locals কত?
- ৪
- ২
- ৩
- ৫
দুই লাইনের Haat program: print(g(1)); / fn g(x: Int) -> Int { return x + 1; }. কী ঘটে?
1:7: error: undefined variable 'g'1:7: error: 'g' is used before its declaration- ঠিকঠাক চলে, ছাপে
2 - চলার সময়
runtime error: 'g' is not initialized yet
Haat-এ fn f(n: Int) { let n = 2; } লিখলে reference-এর বার্তা কী, আর কেন?
- কোনো error নেই, ভেতরের
nparameter-কে ঢেকে দেয় 1:20: error: 'n' is already declared in this scope1:20: error: cannot assign to parameter 'n'1:24: error: 'n' is used before its declaration
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Resolver = নাম থেকে binding: প্রতিটি ব্যবহার একটি ঘোষণার সঙ্গে জোড়া, ফল
uses,declsআরnslots; পরের pass আর নাম খোঁজে না। - তিন নকশা: map-এর stack (সরল), persistent map (snapshot সস্তা), এক table নামপ্রতি stack (lookup দ্রুত, exit-এ মোছা)।
- Pending set: block-এ ঢোকার সময় পরের ঘোষণা জানা থাকে; সেখানে থামা মানে decision 16, নিজের initializer-সহ।
- দুই pass আর নতুন scope: শুধু top-level
fnhoisted; function মানে নতুন মালিক, নতুন slot-গণনা, parameter আর body এক scope. - VM-এর ঠিকানা: global নম্বর, local slot, আর captured হলে cell; সব reference-এর
disআর differential test দিয়ে যাচাই।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৫২ · Type checker বাস্তবায়ন — Haat-এর type নিয়ম কোডেপরবর্তী পর্বtyping rule থেকে recursive checker, missing return আর mutant test.
- প্রোগ্রামিং ভাষা ও কম্পাইলার · কোর্স হোম৮৬টি পর্ব১৪টি মডিউলের পুরো মানচিত্র আর Haat প্রজেক্টের পথ।
- পর্ব ১৫ · Scope — static বনাম dynamic scoping আর nested scopeতত্ত্বযে নিয়মগুলো এই পর্বে কোডে নামল, ভাষাভেদে তুলনাসহ।
- পর্ব ১৭ · Closure — lexical environment ধরে রাখা functionপাশের ধাপcaptured variable কেন cell-এ যায়, funarg সমস্যা।
- DSA · পর্ব ৩২ · Hash tableভিত্তিsymbol table-এর নিচের ডেটা কাঠামো।
- গণনার তত্ত্ব · পর্ব ৫৩ · Rice-এর theoremতত্ত্বকেন কিছু পরীক্ষা compile-এর সময় নয়, চলার সময় করতে হয়।