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

ইন্টারভিউ আর প্রতিযোগিতায় ভাষা ও কম্পাইলার — interpreter, parser আর ভাষার খুঁটিনাটি

Programming Languages and Compilers in Interviews and Contests — Tokenizers, Pratt Parsers, Interpreters, Stack VMs and Language Trivia Done Properly

Taught in Bangla, this practice page covers compilers in interviews and contests in ten parts: a tokenizer, an expression evaluator with a Pratt parser and shunting-yard, a small interpreter with closures and a stack VM, each in under 30 lines with tests. It runs language trivia in JavaScript, Python, C and Java for real, adds a for loop to Haat, shrinks a compiler bug found by differential testing, and covers complexity questions and a seven-day plan. All examples are practice, not real company questions.

এই পর্বে যা পাবেন

  • ৩০ মিনিটে একটি tokenizer আর একটি Pratt evaluator লেখা, Haat-এর precedence আর C-ধাঁচের ভাগ মেনে
  • Environment-এর শিকল দিয়ে closure চালানো একটি ছোট interpreter, আর একই expression থেকে stack VM-এর bytecode
  • Loop-এর closure, mutable default, == বনাম is, C-র overflow, evaluation order, tail call আর erasure নিয়ে প্রশ্নে ভাষা ও version ধরে উত্তর
  • একটি নতুন feature-এ compiler-এর কোন ধাপে কী বদলায়, তা গুছিয়ে বলা
  • Differential test-এর ব্যর্থতা থেকে সবচেয়ে ছোট উদাহরণ বের করে ভুলটি ঠিক করা

১ · ইন্টারভিউতে ভাষা ও compiler — প্রশ্নের চার ধরন আর উত্তরের ছক

Software engineering-এর ইন্টারভিউতে compiler-এর নাম প্রায়ই সরাসরি আসে না, কিন্তু তার কাজগুলো আসে: “একটি string-এর গাণিতিক expression হিসাব করুন”, “একটি ছোট ভাষার interpreter লিখুন”, “এই JavaScript loop কেন তিনবার 30 ছাপে?”, “C-তে এই overflow-এর ফল কী?” দোকানের হিসাবরক্ষক যেমন খাতা দেখে বোঝেন টাকা কোথায় গেল, তেমনি ভাষার ভেতরটা জানলে এসব প্রশ্নের উত্তর অনুমানে নয়, কারণসহ দেওয়া যায়। প্রতিযোগিতার (contest) প্রোগ্রামিংয়েও expression parsing আর ছোট stack machine চেনা বিষয়।

প্রশ্নের ধরনউদাহরণভিত্তিএখানে
জায়গায় বসে বানানোtokenizer, calculator, interpreter, stack VMপর্ব ৪৬–৪৮, ৫৬–৫৯অংশ ২–৫
ভাষার খুঁটিনাটিloop-এর closure, overflow, is, erasureপর্ব ০৬, ১৭, ২৬, ২৯, ৩২, ৩৭অংশ ৬
নকশা ও debuggingHaat-এ for বা array যোগ; ব্যর্থ test থেকে bugপর্ব ২৪, ৫৪, ৫৫, ৮০অংশ ৭–৮
জটিলতাparser কি রৈখিক? HM কত ধীর?পর্ব ৩৫, ৪৮, ৭০অংশ ৯
ব্যাখ্যা ও আচরণসহকর্মীকে UB বা closure বোঝানোপুরো কোর্সঅংশ ১০

জায়গায় বসে বানানো ছোট ভাষা-যন্ত্র — এই পাতার অংশগুলো

একই AST থেকে দুটি back end; দুটির ফল মিলিয়ে দেখাই differential test.

Interview interpreter pipeline sourcetokens ২AST ৩ interpreter ৪bytecode+VM ৫ একই output? ৮ env emit
ছবি ৮৬.১ — প্রতিটি বাক্সের সংখ্যা এই পাতার অংশ। Interpreter সরল বলে সেটিকে “ঠিক উত্তরের উৎস” (oracle) ধরে VM বা optimizer-কে তার সঙ্গে মেলানো হয়; Haat-এর reference বাস্তবায়নও তাই করে।
উত্তরের পাঁচ ধাপ
স্পষ্ট করা → ছোট spec → সরল কোড → test → জটিলতা ও সীমা
  1. স্পষ্ট করা: কোন operator, কোন precedence, পূর্ণসংখ্যার ভাগ কোন দিকে কাটে, শূন্যে ভাগে কী হবে, ভুল input-এ কী বার্তা।
  2. ছোট spec: দুই-তিন লাইনের grammar বা binding power-এর ছক, বোর্ডে লিখে দেখানো।
  3. সরল কোড: আগে সবচেয়ে সোজা সঠিক রূপ; চালাকি পরে।
  4. Test: হাতে হিসাব করা কয়েকটি, প্রান্তের মান (শূন্য, ঋণাত্মক, সবচেয়ে বড় সংখ্যা), আর সম্ভব হলে দুটি বাস্তবায়নের তুলনা।
  5. জটিলতা ও সীমা: সময়, গভীরতা, কী এখনো সামলায় না, সৎভাবে।
১.১(সহজ) ইন্টারভিউয়ার বললেন: “একটি calculator লিখুন, যা "3 + 4 * 2" ধরনের string নেয়।” কোড লেখার আগে কোন পাঁচটি প্রশ্ন করবেন, আর প্রতিটির উত্তর কোডের কোথায় প্রভাব ফেলে?

(১) সংখ্যা কি শুধু পূর্ণসংখ্যা? তাহলে -7 / 2 কত: শূন্যের দিকে কেটে -3 (C, Java, Haat), নাকি নিচের দিকে -4 (Python-এর //)? এটি ভাগের একটি লাইন বদলায়। (২) Unary minus আছে কি, আর -2 ^ 2-এ কে আগে? এটি prefix-এর binding power ঠিক করে। (৩) ঘাত বা তুলনা থাকলে associativity কী, আর a < b < c বৈধ কি (Haat-এ নয়)? (৪) ভুল input বা শূন্যে ভাগে কী হবে: exception, বার্তা, নাকি অবস্থানসহ error? (৫) সংখ্যা কত বড় হতে পারে, overflow হলে wrap, error, নাকি বড় সংখ্যা? প্রশ্নগুলো সময় নষ্ট নয়: পর্ব ০৩-এ দেখেছেন, একই -7 / 2 C আর Python-এ আলাদা ফল দেয়। ইন্টারভিউয়ার যা বলেন, এক লাইনে লিখে রাখুন; পরে test সেই লাইন থেকেই আসবে।

১.২(মাঝারি) “একটি ছোট ভাষার জন্য interpreter আর bytecode VM দুটোই চাই, সময় ৯০ মিনিট।” কোনটি আগে লিখবেন, আর কেন?

আগে tree-walking interpreter. এটি AST থেকে সরাসরি ফল দেয়, ভুলের জায়গা কম, তাই এটিই হয় oracle: VM-এর প্রতিটি ফল এর সঙ্গে মেলানো যায়। তারপর compiler আর VM, আর শেষে একটি ছোট differential test: একই program দুটিতে চালিয়ে আউটপুট তুলনা। Haat-এর reference বাস্তবায়ন ঠিক এভাবে পরীক্ষিত: প্রতিটি উদাহরণে run আর vm-এর আউটপুট এক, আর ৪০০টি এলোমেলো expression দুই back end-এ একটি আলাদা Python evaluator-এর সঙ্গে মেলানো (reference-এর README অনুযায়ী)। সময় কম পড়লে VM অর্ধেক থাকলেও interpreter আর test-সহ একটি কাজের জিনিস হাতে থাকে।

এই পাতার কোনো প্রশ্ন কোনো নির্দিষ্ট প্রতিষ্ঠানের ইন্টারভিউ, contest বা পরীক্ষা থেকে নেওয়া নয়; এগুলো এমন ধরনের প্রশ্ন, যা ভাষা ও compiler-এর জ্ঞান যাচাইয়ে প্রায়ই আসে। আটটি Python ব্লক ব্রাউজারেই চলে (Pyodide, শুধু standard library; প্রথমবার কয়েক সেকেন্ড লাগে), একটি JavaScript ব্লক ব্রাউজারের নিজস্ব engine-এ, আর C ও Java ব্লক Wandbox-এর সত্যিকারের compiler-এ। Haat-এর সব দাবি reference বাস্তবায়নের tokens, ast, run, vm আর dis-এ মেলানো। মডিউল ১৪-এর অন্য পাতা: পর্ব ৮২-এ compiler-এর হিসাবের সমস্যা, পর্ব ৮৩-এ MCQ, পর্ব ৮৪-এ লিখিত ও ভাইভা, পর্ব ৮৫-এ typing আর semantics-এর derivation.

২ · জায়গায় বসে tokenizer — maximal munch, অবস্থান আর error

রেস্তোরাঁর অর্ডার স্লিপ পড়ার মতো: প্রথমে অক্ষরগুলোকে শব্দে ভাগ, তারপর অর্থ। Lexer-এর তিনটি নিয়ম মনে রাখলে ইন্টারভিউর tokenizer প্রায় নির্ভুল হয়। এক, maximal munch: যতটা লম্বা token মেলে, ততটাই নিন, তাই <=-কে আগে চেষ্টা, < পরে। দুই, keyword আলাদা pattern নয়: আগে পুরো identifier পড়ুন, তারপর টেবিলে দেখুন সেটি keyword কি না। তিন, অবস্থান: লাইনের শুরুর index মনে রাখলে column = এখনকার index − শুরু + ১, আর Python-এর string-এ index code point গোনে, তাই বাংলা অক্ষর এক column (Haat-এর নকশা-সিদ্ধান্ত ১)।

import re
KW = {"let", "var", "fn", "if", "else", "while", "return", "true", "false", "print"}
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 = re.compile(r'(?P<ws>[ \t\r]+|//[^\n]*)|(?P<nl>\n)|(?P<INT>[0-9]+)'
                  r'|(?P<IDENT>[A-Za-z_][A-Za-z0-9_]*)|(?P<STRING>"(?:\\["\\n]|[^"\\\n])*")'
                  r'|(?P<op>==|!=|<=|>=|&&|\|\||->|[-+*/%<>!=(){},;:])')
def tokens(src):
    out, pos, line, start = [], 0, 1, 0          # start = index where this line begins
    while pos < len(src):
        m = SPEC.match(src, pos)
        col = pos - start + 1                    # columns count code points (Bangla = 1)
        if not m:
            why = "unterminated string literal" if src[pos] == '"' else f"unexpected character {src[pos]!r}"
            raise SyntaxError(f"{line}:{col}: error: {why}")
        kind, text = m.lastgroup, m.group()
        if kind == "nl": line, start = line + 1, m.end()
        elif kind != "ws":
            if kind == "IDENT" and text in KW: kind = text.upper()
            if kind == "op": kind = OPS[text]
            out.append((f"{line}:{col}", kind, text))
        pos = m.end()
    return out + [(f"{line}:{pos - start + 1}", "EOF", "")]
src = 'let d = a<=-b && !ok(x); // ছাড়?\nprint("হাট\\"" + "!");\n'
for t in tokens(src): print(f"{t[0]:<6} {t[1]:<8} {t[2]}".rstrip())
for bad in ['let t = total | 2;', 'print("ok);']:
    try: tokens(bad)
    except SyntaxError as e: print(e)

আউটপুট reference বাস্তবায়নের python haat.py tokens-এর সঙ্গে অক্ষরে অক্ষরে এক (লেখকের যন্ত্রে মিলিয়ে দেখা), দুটি error-বার্তাসহ। a<=-b-এ <= একটি token, - আলাদা; // ছাড়? comment, তাই কোনো token নেই। দ্বিতীয় লাইনে "হাট\"" একটি STRING (escape-সহ লেখা হুবহু রাখা), আর পরের + কলাম ১৫-এ, কারণ “হাট” তিনটি code point. একা | Haat-এ কোনো operator নয় (শুধু || আছে), তাই কলাম ১৫-এ “unexpected character”; শেষ উদ্ধৃতিচিহ্ন না থাকায় দ্বিতীয়টি “unterminated string literal”. এই সংস্করণ Haat-এর সব token kind চেনে, কিন্তু অচেনা escape (\t) বা অতিবড় সংখ্যার error দেয় না; পূর্ণ রূপ reference-এর lexer.py.

২.১(সহজ) let x = 5;-এর পরে Haat-এ print(x<--1); লিখলে lexer কোন token দেয়, আর কী ছাপা হয়?

Haat-এ <- বা -- কোনো operator নয়, তাই maximal munch এখানে প্রতিটি চিহ্ন আলাদা নেয়: LT, MINUS, MINUS, INT. Parser এটিকে পড়ে x < (-(-1)), অর্থাৎ 5 < 1, তাই ছাপা হয় false; reference-এর tokens আর run দুটিই এটি দেখায়। অনেকে একে “x-এ বাঁদিকের তীর” বা “x-- …” পড়েন, কিন্তু lexer অর্থ বোঝে না, শুধু তার তালিকার সবচেয়ে লম্বা মিল খোঁজে। তালিকায় <- থাকলে একই input-এর token আর অর্থ দুটিই বদলে যেত।

২.২(মাঝারি) একজন প্রার্থী keyword-এর জন্য আলাদা pattern let|var|fn|… বসালেন identifier-এর pattern-এর আগে। কোন input-এ ভুল হবে, আর ঠিক করার দুটি উপায় কী?

let letter = 1;-এ দ্বিতীয় শব্দটি LET আর IDENT ter হয়ে যায়, কারণ regex-এর বিকল্প বাঁ থেকে চেষ্টা হয় আর let মিলে যায়। Reference এটিকে একটি IDENT letter দেয়। উপায় এক: উপরের কোডের মতো আগে identifier পুরো পড়ে টেবিলে খোঁজা। উপায় দুই: keyword-এর pattern-এ শব্দসীমা দেওয়া (\b বা “পরে কোনো অক্ষর বা অঙ্ক নয়”)। প্রথমটি সহজ আর দ্রুত, কারণ একটি dictionary-তে খোঁজা ধ্রুবক সময়ের।

২.৩(মাঝারি) print("হাট\"" + "!");-এ +-এর column code point গুনে ১৫। UTF-8 byte গুনলে কত হতো, আর কেন এটি editor-এর সঙ্গে কাজে গুরুত্বপূর্ণ?

“হাট”-এর তিনটি code point UTF-8-এ নয় byte, তাই byte গুনলে column ২১, UTF-16 unit গুনলে আবার ১৫ (এই তিনটি অক্ষর BMP-র ভেতরে)। Error-বার্তা বা editor-এর দাগ ভুল জায়গায় পড়ে, যদি compiler আর editor আলাদা একক গোনে। পর্ব ৮০-এ দেখেছেন, Language Server Protocol-এর column ০ থেকে আর ডিফল্টে UTF-16 unit-এ, অথচ Haat-এর ১ থেকে আর code point-এ; তাই language server-এ রূপান্তর লাগে। ইন্টারভিউতে এক বাক্যে বলুন “column কোন এককে গুনছি”, তারপর সেই মতো test লিখুন।

২.৪(কঠিন) Haat-এর reference প্রথম lexical error-এই থামে, অথচ parser সব error দেখায় (নকশা-সিদ্ধান্ত ২)। এই পার্থক্যের যুক্তি কী, আর lexer-এ recovery চাইলে কী করবেন?

Lexer-এর একটি ভুল পরের সবকিছু বদলে দিতে পারে: একটি অসমাপ্ত string বাকি লাইনকে string বানিয়ে ফেলে, আর তারপরের token-গুলো অর্থহীন হয়, তাই অনেক ভুয়া error আসে। Parser-এর panic-mode recovery-তে একটি ভালো থামার জায়গা আছে (পরের ; বা }, পর্ব ৫০), যা lexer-এর নেই। Recovery চাইলে অচেনা অক্ষরটিকে একটি ERROR token বানিয়ে এগোন, আর অসমাপ্ত string-কে লাইনের শেষেই বন্ধ ধরুন; editor-এর জন্য এটি কাজের, কারণ লেখা চলাকালীন code প্রায় সবসময় ভাঙা থাকে (পর্ব ৮০)।

৩ · Expression evaluator — Pratt parser আর shunting-yard

“eval ছাড়া expression হিসাব করুন” প্রশ্নে দুটি কৌশল জানা থাকলেই চলে। Pratt parsing-এ প্রতিটি infix operator-এর একটি বাঁ binding power (lbp): চলতি সীমা min_bp-এর চেয়ে কম হলে থামুন, নইলে নিন আর ডান operand পড়ুন lbp + 1 সীমায়, যাতে একই স্তরের পরের operator বাইরে থাকে (বাঁ-সংযোগ)। Dijkstra-র shunting-yard একই কাজ একটি operator-stack দিয়ে করে, আর ফল দেয় postfix (RPN) রূপে। নিচের ব্লক Haat-এর binding power-এর ছক হুবহু নেয়, তুলনাকে non-associative রাখে, আর মান হিসাব করে Haat-এর নিয়মে: ৬৪ বিটে wrap, / শূন্যের দিকে কাটে, %-এর চিহ্ন ভাজ্যের, আর &&, || short-circuit.

import re, random, operator as o
LBP = {"||": 10, "&&": 20, "==": 30, "!=": 30, "<": 40, "<=": 40, ">": 40, ">=": 40, "+": 50, "-": 50, "*": 60, "/": 60, "%": 60}
def lex(s): return re.findall(r"\d+|==|!=|<=|>=|&&|\|\||[-+*/%<>!()]", s) + ["$"]
def parse(toks, min_bp=0):
    t, last = toks.pop(0), None
    if t.isdigit(): left = int(t)
    elif t == "(": left = parse(toks); assert toks.pop(0) == ")", "expected ')'"
    elif t in "-!": left = (t, parse(toks, 70))                   # prefix: rbp 70
    else: raise SyntaxError(f"expected expression, found {t!r}")
    while LBP.get(toks[0], -1) >= min_bp:                         # lbp >= min_bp: keep going
        op = toks.pop(0)
        if LBP[op] in (30, 40) and last == LBP[op]: raise SyntaxError("comparison operators cannot be chained")
        left, last = (op, left, parse(toks, LBP[op] + 1)), LBP[op]
    return left
W = lambda v: (v + 2**63) % 2**64 - 2**63                         # 64-bit two's complement wrap
def cdiv(a, b): q = abs(a) // abs(b); return q if (a < 0) == (b < 0) else -q   # toward zero
OPS = {"+": lambda a, b: W(a + b), "-": lambda a, b: W(a - b), "*": lambda a, b: W(a * b),
       "/": lambda a, b: W(cdiv(a, b)), "%": lambda a, b: a - cdiv(a, b) * b,
       "<": o.lt, "<=": o.le, ">": o.gt, ">=": o.ge, "==": o.eq, "!=": o.ne}
def ev(e):
    if isinstance(e, int): return e
    if len(e) == 2: return W(-ev(e[1])) if e[0] == "-" else not ev(e[1])
    a = ev(e[1])
    if e[0] in ("&&", "||"): return ev(e[2]) if a == (e[0] == "&&") else a   # short-circuit
    return OPS[e[0]](a, ev(e[2]))
for s in ["1 - 2 - 3 * 4", "-7 / 2", "-7 % 2", "7 % -2", "2 * (3 + 4) > 13 || 1 / 0 == 0",
          "9223372036854775807 + 1", "1 < 2 == 3 < 4", "1 < 2 < 3", "5 % (2 - 2)"]:
    try: print(f"{s:31} -> {str(ev(parse(lex(s)))).lower()}")
    except SyntaxError as err: print(f"{s:31} -> error: {err}")
    except ZeroDivisionError: print(f"{s:31} -> runtime error: division by zero")

প্রথম সাতটি ফল reference-এর haat.py run-এর সঙ্গে এক (একই expression print করে মেলানো), আর 1 < 2 < 3-এ reference-ও “comparison operators cannot be chained” দেয়। 1 - 2 - 3 * 4 = -13, কারণ গাছ (- (- 1 2) (* 3 4)). -7 / 2 = -3 আর -7 % 2 = -1 C-র নিয়মে; 7 % -2 = 1, চিহ্ন ভাজ্যের। পঞ্চম লাইনে বাঁ পাশ true, তাই 1 / 0 কখনো হিসাব হয়নি। ষষ্ঠ লাইনে সবচেয়ে বড় Int-এ ১ যোগ করে সবচেয়ে ছোট Int (নকশা-সিদ্ধান্ত ১৩)। শেষ লাইনে শূন্যে ভাগ ধরা পড়েছে চলার সময়, parse-এর সময় নয়।

প্রতিটি সিদ্ধান্তের মুহূর্তে
চলমান ডাক
পড়া / দেখা
সিদ্ধান্ত
left এখন
  1. শুরু। সীমা 0. প্রথম token 1 হলো left. পরের --এর lbp 50 ≥ 0, তাই নেওয়া হলো; ডান operand পড়া হবে সীমা 51-এ।
  2. বাঁ-সংযোগের মুহূর্ত। ভেতরের ডাক 2 পড়ে, আবার - দেখে। কিন্তু 50 < 51, তাই সে এটি নেয় না, শুধু 2 ফেরত দেয়।
  3. প্রথম গাছ। বাইরের ডাকে left হলো (- 1 2). দ্বিতীয় --এর lbp 50 ≥ 0, তাই এবার এটি নেয়।
  4. গুণ বেশি শক্ত। ডান পাশের ডাক (সীমা 51) 3 পড়ে, * দেখে: 60 ≥ 51, তাই গুণ এই ডাকের ভেতরেই থাকে।
  5. সবচেয়ে ভেতরে। সীমা 61-এ 4 পড়া হলো; input শেষ (lbp −1), তাই 4 ফেরে, আর সীমা 51-এর ডাকে left হলো (* 3 4).
  6. ফেরার পথ। সীমা 51-এর ডাক শেষ দেখে (* 3 4) ফেরত দেয়; বাইরে left হলো (- (- 1 2) (* 3 4)), reference-এর ast-এর মতোই।
  7. শেষ। বাইরের ডাকও শেষ দেখে থামে। মান 1 − 2 − 12 = −13. মোট কাজ: প্রতিটি token একবারই পড়া।

এবার একই expression shunting-yard দিয়ে, আর দুটি সম্পূর্ণ আলাদা কৌশলকে একে অপরের পরীক্ষক বানানো: ৩,০০০টি এলোমেলো expression (বন্ধনী, unary minus আর পাঁচটি গাণিতিক operator-সহ), প্রতিটি দুই পথে হিসাব, শূন্যে ভাগও একটি ফল হিসেবে তুলনায়। এই ব্লক আগের ব্লকের lex, parse, ev আর OPS ব্যবহার করে।

def to_rpn(toks):                                  # Dijkstra's shunting-yard: + - * / % ( ) unary -
    out, st, prev = [], [], "("
    for t in toks[:-1]:
        if t.isdigit(): out.append(t)
        elif t == "(": st.append(t)
        elif t == ")":
            while (x := st.pop()) != "(": out.append(x)
        elif t == "-" and (prev in LBP or prev == "("): st.append("neg")    # prefix minus
        else:                                      # pop while the stack top binds at least as tight
            while st and st[-1] != "(" and (st[-1] == "neg" or LBP[st[-1]] >= LBP[t]): out.append(st.pop())
            st.append(t)
        prev = t
    return out + st[::-1]
def run_rpn(rpn):
    s = []
    for t in rpn:
        if t.isdigit(): s.append(int(t))
        elif t == "neg": s.append(W(-s.pop()))
        else: b, a = s.pop(), s.pop(); s.append(OPS[t](a, b))
    return s.pop()
def rnd(d):                                        # random arithmetic expression, depth <= d
    if d == 0 or random.random() < 0.25: return random.choice(["", "-"]) * (random.random() < 0.1) + str(random.randint(0, 9))
    e = f"{rnd(d - 1)} {random.choice('+-*/%')} {rnd(d - 1)}"
    return f"({e})" if random.random() < 0.3 else e
def safe(f, s):
    try: return f(s)
    except ZeroDivisionError: return "div0"
random.seed(86); tests = [rnd(4) for _ in range(3000)]
bad = [s for s in tests if safe(lambda s: ev(parse(lex(s))), s) != safe(lambda s: run_rpn(to_rpn(lex(s))), s)]
print(" ".join(to_rpn(lex("-2 * (3 - -4) % 5"))), "| tests:", len(tests), "| disagreements:", len(bad))

প্রথম অংশ -2 * (3 - -4) % 5-এর RPN: 2 neg 3 4 neg - * 5 %. Unary minus চেনার নিয়ম এক লাইনে: আগের token একটি operator, (, বা কিছুই না হলে - হলো neg. দ্বিতীয় অংশে ৩,০০০টির একটিতেও দুই কৌশলের ফল আলাদা হয়নি (seed 86, প্রতিবার একই)। এটি প্রমাণ নয়, কিন্তু precedence, associativity আর unary minus-এর সাধারণ ভুলগুলো এমন test-এ সেকেন্ডের ভগ্নাংশে ধরা পড়ে। লেখকের যন্ত্রে আরও ৪০০টি এলোমেলো expression reference-এর run-এ চালিয়ে ev-এর সঙ্গে ৪০০-তে ৪০০ মিলেছে।

৩.১(সহজ) একজন প্রার্থী ডান operand পড়লেন parse(toks, LBP[op]) দিয়ে, + 1 ছাড়া। 2 - 3 - 4 আর 100 / 10 / 5-এর মান কী হবে?

সীমা lbp-এর সমান হলে ভেতরের ডাক একই স্তরের পরের operator-ও নিয়ে নেয়, অর্থাৎ ডান-সংযোগ: 2 - (3 - 4) = 3 (ঠিক উত্তর -5), আর 100 / (10 / 5) = 50 (ঠিক উত্তর 2). লেখকের যন্ত্রে উপরের parse-এ শুধু এই বদল করে চালানো হয়েছে; ফল 3 আর 50. শিক্ষা: সত্যিই ডান-সংযোগী operator (যেমন ঘাত) চাইলে এটিই ঠিক কৌশল, বিয়োগ-ভাগে নয়। তাই প্রতিটি operator-এর associativity-র জন্য অন্তত একটি test রাখুন।

৩.২(মাঝারি) Haat-এ -7 / 2 আর -(7 / 2) দুটিই -3, কিন্তু Python 3.14-এ -7 // 2 = -4 আর -(7 // 2) = -3. কেন? আর Python-এ -2 ** 2 কত?

শূন্যের দিকে কাটা ভাগ চিহ্নের প্রতি সমমিত: q(−a, b) = −q(a, b). তাই Haat বা C-তে unary minus আগে হোক বা পরে, ফল একই। Python-এর // নিচের দিকে কাটে, তাই −3.5 হয় −4, অথচ −(3) হয় −3; এখানে unary minus-এর জায়গা ফল বদলায়। Python-এ unary minus * / // %-এর চেয়ে শক্ত, কিন্তু **-এর চেয়ে দুর্বল, তাই -2 ** 2 = -(2 ** 2) = -4. তিনটি ফলই লেখকের যন্ত্রে CPython 3.14.4-এ চালানো। Parser লেখার সময় তাই প্রথম প্রশ্ন: “prefix minus-এর binding power কোন operator-এর চেয়ে বেশি?”

৩.৩(মাঝারি) Shunting-yard-এ unary minus চেনার জন্য একজন প্রার্থী লিখলেন: “--এর আগে একটি সংখ্যা না থাকলে unary.” কোন input-এ এটি ভুল করে?

(1 + 2) - 3-এ --এর আগে ), সংখ্যা নয়, তাই নিয়মটি একে unary ধরে, আর RPN ভেঙে যায়। ঠিক নিয়ম উল্টো দিক থেকে: আগে operator, (, বা কিছুই না থাকলে unary; সংখ্যা, নাম বা ) থাকলে binary. উপরের prev in LBP or prev == "(" ঠিক এটিই করে (শুরুতে prev = "(")। এ ধরনের ভুল হাতে বানানো পাঁচটি test-এ ধরা না পড়লেও এলোমেলো differential test-এ দ্রুত ধরা পড়ে।

৩.৪(কঠিন) “আপনার Pratt parser-এর জটিলতা কত, আর কোন input তাকে ভাঙতে পারে?”

সময় O(n): প্রতিটি parse ডাক অন্তত একটি token খায়, আর loop-এর প্রতিটি পাক একটি operator খায়; কোনো token দুবার পড়া হয় না, পেছনে ফেরা (backtracking) নেই। কিন্তু recursion-এর গভীরতা input-এর ওপর নির্ভর করে: - - - … 1 বা অনেক বন্ধনী প্রতিটিতে একটি নতুন ডাক। লেখকের যন্ত্রে উপরের parse-কে ৩০০টি - দিলে ঠিক চলে, ২,০০০টি দিলে CPython-এর RecursionError. অবিশ্বস্ত input-এ তাই গভীরতার একটি সীমা আর স্পষ্ট বার্তা দিন, অথবা prefix অংশটি একটি loop আর নিজের stack দিয়ে লিখুন।

৪ · Environment আর closure-সহ ছোট interpreter

“Variable, function আর closure-সহ একটি interpreter লিখুন” প্রশ্নের হৃদয় একটি ছোট class: environment, অর্থাৎ নাম থেকে মানের একটি dictionary আর তার মা-environment-এর দিকে একটি pointer. নাম খুঁজতে এই scope chain ধরে ওপরে উঠুন, লাইব্রেরির তাকে না পেলে পাশের ঘরের তাকে। একটি closure তিনটি জিনিস মনে রাখে: parameter, দেহ, আর যে environment-এ সে তৈরি হয়েছিল। ডাকার সময় নতুন frame সেই তৈরির environment-এর নিচে ঝোলে, ডাকার জায়গার নিচে নয়; এটাই static scope. set নাম যেখানে পায় সেখানেই লেখে, তাই একই variable ভাগ করা দুই closure একে অপরের বদল দেখে (capture by reference, Haat-এর নিয়ম)।

import operator as o
class Env:                                       # one scope = a dict + a pointer to its parent
    def __init__(self, parent=None): self.vars, self.parent = {}, parent
    def where(self, name): return self if name in self.vars else self.parent.where(name)
class Return(Exception): pass
ARITH = {"+": o.add, "-": o.sub, "*": o.mul, "<": o.lt}
def evaluate(e, env):
    if isinstance(e, int): return e
    if isinstance(e, str): return env.where(e).vars[e]               # walk the scope chain
    if e[0] == "lambda": return ("closure", e[1], e[2], env)          # remember the DEFINING env
    if e[0] == "call":
        _, params, body, defenv = evaluate(e[1], env)
        frame = Env(defenv); frame.vars.update(zip(params, [evaluate(a, env) for a in e[2:]]))
        try: execute(body[1:], frame)
        except Return as r: return r.args[0]
    return ARITH[e[0]](evaluate(e[1], env), evaluate(e[2], env))
def execute(stmts, env):
    for s in stmts:
        if s[0] in ("let", "var"): env.vars[s[1]] = evaluate(s[2], env)
        elif s[0] == "set": env.where(s[1]).vars[s[1]] = evaluate(s[2], env)   # by reference: shared box
        elif s[0] == "print": print(evaluate(s[1], env))
        elif s[0] == "return": raise Return(evaluate(s[1], env))
        elif s[0] == "while":
            while evaluate(s[1], env): execute(s[2][1:], Env(env) if FRESH else env)   # new scope per round?
print("2 + 3 * 4 =", evaluate(["+", 2, ["*", 3, 4]], Env()))   # a first smoke test

এই ব্লক interpreter সংজ্ঞায়িত করে: Env, evaluate (expression) আর execute (statement); শেষ লাইনের ছোট পরীক্ষা ছাপে 2 + 3 * 4 = 14, অর্থাৎ list-রূপের গাছ ঠিকঠাক হিসাব হচ্ছে। return একটি exception দিয়ে বাস্তবায়িত; Haat-এর reference-এর interp.py-ও একই কৌশল নেয় (ReturnSignal). while-এর প্রতিটি পাকে নতুন Env হবে কি না, তা একটি global FRESH ঠিক করে, যাতে পরের ব্লকে দুই নকশা পাশাপাশি চালানো যায়।

Program লিখতে parser লাগবে না: S-expression-এ লিখুন, যা reference-এর ast-এর আউটপুটের মতো দেখতে, আর দশ লাইনের একটি reader দিয়ে list বানান। ইন্টারভিউতে সময় বাঁচানোর এটি একটি পরিচিত কৌশল; প্রশ্নকর্তা আসল syntax চাইলে অংশ ৩-এর parser পরে জোড়া যায়।

import re
def read(s):                                     # S-expression reader: "(+ 1 x)" -> ['+', 1, 'x']
    toks = re.findall(r"[()]|[^\s()]+", s)[::-1]
    def one():
        t = toks.pop()
        if t != "(": return int(t) if t.isdigit() else t
        out = []
        while toks[-1] != ")": out.append(one())
        toks.pop(); return out
    return [one() for _ in iter(lambda: toks, [])]
PROGRAM = """
(let make_counter (lambda (step) (block
    (var count 0)
    (let next (lambda () (block (set count (+ count step)) (return count))))
    (return next))))
(let a (call make_counter 1))  (let b (call make_counter 10))
(print (call a)) (print (call a)) (print (call b)) (print (call a))
(var fs (lambda () (block (return 0))))  (var r 0)
(while (< r 3) (block
    (let k (* r 100)) (let old fs)
    (set fs (lambda () (block (return (+ (call old) k)))))
    (set r (+ r 1))))
(print (call fs))"""
for FRESH in (True, False):
    print("fresh scope per round:", FRESH)
    try: execute(read(PROGRAM), Env())
    except RecursionError: print("RecursionError: old() keeps calling itself")

প্রথম রানে 1, 2, 10, 3: প্রতিটি make_counter ডাক একটি নতুন frame বানায়, তাই a আর b-এর count আলাদা, আর a-এর তৃতীয় ডাক 3 দেয়। এরপর 300: loop-এর প্রতি পাকে নতুন k (0, 100, 200), আর প্রতিটি closure নিজের k আর আগের fs (নাম old) ধরে রাখে, তাই 0 + 0 + 100 + 200. দুটি সংখ্যাই reference-এর examples/counter.haat আর nested.haat-এর আউটপুটের সঙ্গে এক (Haat-এর নকশা-সিদ্ধান্ত ১৪: while-এর দেহ প্রতি পাকে নতুন scope). দ্বিতীয় রানে সব পাক একই environment ভাগ করে: শেষ পাকের পরে সেখানে old মানে দ্বিতীয় পাকের closure, যার দেহ নিজেই আবার old() ডাকে, আর সেই old খোঁজা হয় একই ভাগের environment-এ, অর্থাৎ নিজেকেই। ফল অসীম recursion, আর CPython-এর RecursionError.

৪.১(সহজ) উপরের interpreter-কে dynamic scope-এর বানাতে ঠিক কোন একটি লাইন বদলাবেন? পরীক্ষার program: top level-এ fee = 60; charge() ফেরত দেয় fee; eid()-এর ভেতরে let fee = 0, তারপর charge(). eid() দুই নিয়মে কত দেয়?

frame = Env(defenv)-এর বদলে frame = Env(env): নতুন frame তখন ডাকার জায়গার environment-এর নিচে ঝোলে। Static scope-এ charge-এর fee খোঁজা হয় তার জন্মস্থানে, top level-এ, তাই 60; dynamic scope-এ ডাকার শিকলে, যেখানে eid-এর fee = 0, তাই ঈদের দিনে ডেলিভারি চার্জ “হঠাৎ” শূন্য। দুটি সংখ্যাই লেখকের যন্ত্রে এই interpreter-এ এক লাইন বদলে চালিয়ে পাওয়া। Dynamic scope-এ একটি function-এর অর্থ নির্ভর করে কে তাকে ডাকল তার ওপর, তাই কোড পড়ে বোঝা কঠিন; পুরো তত্ত্ব পর্ব ১৫-এ।

৪.২(মাঝারি) Python-এ এই interpreter-এর return exception দিয়ে কেন, আর এর বিকল্প কী? Bytecode VM-এ একই সমস্যা আছে কি?

return গভীর loop বা block-এর ভেতর থেকে পুরো function-এর বাইরে লাফ দেয়; recursive execute-এর অনেক স্তর পেরোতে exception সবচেয়ে কম কোডে কাজটি করে। বিকল্প হলো প্রতিটি execute একটি সংকেত ফেরত দেবে (“স্বাভাবিক” বা “return, মান v”), আর প্রতিটি loop সেটি দেখে থামবে; বেশি লাইন, কিন্তু exception-এর খরচ নেই। VM-এ সমস্যাটিই নেই: RETURN নির্দেশ শুধু চলতি frame সরিয়ে দেয়, কারণ সেখানে Python-এর recursion নয়, VM-এর নিজের frame-এর তালিকা (পর্ব ৫৯)।

৪.৩(মাঝারি) দ্বিতীয় রানটি ব্যর্থ হলো RecursionError-এ। JavaScript আর Python-এর কোন পরিচিত আচরণের সঙ্গে এর মিল, আর আসল ভাষাগুলো কীভাবে এটি এড়ায়?

মিল loop-এর closure-এর সঙ্গে: সব closure একটিই variable দেখে, তাই সবাই শেষ মান পায়। JavaScript-এর var-এ তিনটি closure 30, 30, 30 দেয়, Python-এর for-এ 20, 20, 20 (অংশ ৬)। এখানে সেই “শেষ মান” নিজেরই একটি closure, তাই ভুল ফলের বদলে অসীম recursion. সমাধান তিন ভাষায় তিন রকম: Haat প্রতি পাকে নতুন scope দেয় (নকশা-সিদ্ধান্ত ১৪), JavaScript-এর for (let …) প্রতি পাকে loop variable-এর নতুন binding বানায়, আর Python-এ আপনাকে নিজে default argument বা factory function দিয়ে মান ধরতে হয় (পর্ব ১৭)।

৫ · Stack VM — expression থেকে bytecode, তারপর চালানো

“এই expression-কে একটি stack machine-এর নির্দেশে বদলান আর চালান” প্রশ্নে AST-কে post-order-এ হাঁটুন: আগে বাঁ, তারপর ডান, তারপর operator-এর opcode. ধ্রুবকগুলো একটি টেবিলে (constant pool) একবার করে বসে, আর CONST k সেই টেবিলের k-তম মান stack-এ রাখে। && আর ||-এর আলাদা opcode নেই: Haat-এর bytecode-এ এরা JUMP_IF_FALSE আর JUMP (README-এর হুবহু ছাঁচ)। নিচের ব্লক অংশ ৩-এর parse ব্যবহার করে, আর listing-এর বিন্যাস reference-এর dis-এর মতো।

NAME = dict(zip("+ - * / % == != < <= > >=".split(), "ADD SUB MUL DIV MOD EQ NE LT LE GT GE".split()))
SYM = {v: k for k, v in NAME.items()}; show = lambda v: str(v).lower()
def emit(e, code, consts):                       # AST (from parse above) -> list of [opcode, arg]
    def const(v):
        if (type(v), v) not in consts: consts[(type(v), v)] = len(consts)
        code.append(["CONST", consts[(type(v), v)]])
    if isinstance(e, int): const(e)
    elif len(e) == 2: emit(e[1], code, consts); code.append(["NEG" if e[0] == "-" else "NOT", None])
    elif e[0] in ("&&", "||"):                   # short-circuit = jumps, no special opcode
        emit(e[1], code, consts); j1 = len(code); code.append(["JUMP_IF_FALSE", None])
        emit(e[2], code, consts) if e[0] == "&&" else const(True)
        j2 = len(code); code.append(["JUMP", None]); code[j1][1] = len(code)
        const(False) if e[0] == "&&" else emit(e[2], code, consts); code[j2][1] = len(code)
    else: emit(e[1], code, consts); emit(e[2], code, consts); code.append([NAME[e[0]], None])
def vm(code, vals, trace=False):
    stack, ip = [], 0
    while ip < len(code):
        at, (op, arg) = ip, code[ip]; ip += 1
        if op == "CONST": stack.append(vals[arg])
        elif op in ("NEG", "NOT"): x = stack.pop(); stack.append(W(-x) if op == "NEG" else not x)
        elif op == "JUMP": ip = arg
        elif op == "JUMP_IF_FALSE": ip = arg if not stack.pop() else ip
        else: b, a = stack.pop(), stack.pop(); stack.append(OPS[SYM[op]](a, b))
        if trace: print(f"{at:>4}  {op:<14} stack = [{', '.join(map(show, stack))}]")
    return stack.pop()
code, consts = [], {}; emit(parse(lex("(7 - 2) * 3 > 10 || 4 / 0 == 1")), code, consts)
vals = {i: v for (_, v), i in consts.items()}
for i, (op, arg) in enumerate(code):                         # same layout as haat.py dis
    t = f"{i:4}  {op:<15}{'' if arg is None else arg:<4}"; print(t + f"  ; {show(vals[arg])}" if op == "CONST" else t.rstrip())
print("result:", show(vm(code, vals, trace=True)))

Listing-এর ০ থেকে ১৪ নম্বর লাইন print((7 - 2) * 3 > 10 || 4 / 0 == 1);-এর জন্য reference-এর haat.py dis-এর সঙ্গে অক্ষরে অক্ষরে এক; reference এর পরে শুধু PRINT আর শেষের CONST (), RETURN যোগ করে। লক্ষ করুন true আর 1 আলাদা ধ্রুবক (৪ আর ৭), কারণ টেবিলের চাবি (type, মান); Python-এ True == 1, তাই শুধু মান দিয়ে চাবি বানালে এরা মিশে যেত। Trace দেখায় VM মাত্র দশটি নির্দেশ চালিয়েছে: ৯ নম্বরের JUMP 15 ১০–১৪ পুরোটা লাফিয়ে যায়, তাই 4 / 0 কখনো চলেনি, আর ফল true, reference-এর vm-এর মতোই।

নির্দেশ চালানোর পর
ip · নির্দেশ
stack
পরের ip
  1. প্রথম ধ্রুবক। 7 stack-এ।
  2. দ্বিতীয় ধ্রুবক। 2 উপরে; এখন দুটি মান।
  3. বিয়োগ। SUB দুটি তুলে 7 − 2 = 5 রাখে; বাঁ operand নিচে ছিল, তাই ক্রম ঠিক।
  4. আবার ধ্রুবক। 3 উপরে।
  5. গুণ। 5 × 3 = 15.
  6. তুলনার ধ্রুবক। 10 উপরে; stack-এর সর্বোচ্চ গভীরতা এই expression-এ ২।
  7. তুলনা। 15 > 10, তাই true.
  8. শর্তের লাফ। JUMP_IF_FALSE মানটি তুলে নেয়; true বলে লাফ দেয় না, পরের নির্দেশে যায়।
  9. || -এর ফল। বাঁ পাশ true হলে পুরো || true, তাই ধ্রুবক true রাখা হয়।
  10. ডান পাশ বাদ। JUMP 15 ডান পাশের পাঁচটি নির্দেশ লাফিয়ে যায়; 4 / 0 কখনো চলে না। ফল true.
৫.১(সহজ) 1 + (2 + (3 + 4)) আর ((1 + 2) + 3) + 4-এর জন্য এই VM-এর stack-এর সর্বোচ্চ গভীরতা কত? এই পার্থক্য কেন গুরুত্বপূর্ণ?

প্রথমটিতে ৪: চারটি ধ্রুবকই stack-এ বসে থাকে, কারণ প্রতিটি যোগের ডান পাশ শেষ না হওয়া পর্যন্ত বাঁ পাশ অপেক্ষা করে। দ্বিতীয়টিতে ২: প্রতি দুটি মানের পরেই যোগ। লেখকের যন্ত্রে এই VM-এর trace থেকে গুনে মেলানো (বন্ধনী ছাড়া 1 + 2 + 3 + 4-ও ২, কারণ বাঁ-সংযোগী)। বাস্তব VM প্রতিটি function-এর জন্য সর্বোচ্চ stack-গভীরতা আগে থেকে হিসাব করে রাখে; JVM-এর class file-এ এটি max_stack. Register allocation-এও একই ধারণা: ডান-ঝোঁকা গাছ বেশি register চায় (পর্ব ৬৯–৭০)।

৫.২(মাঝারি) একজন প্রার্থী ||-এর জন্য নতুন opcode OR বানালেন: দুই পাশ হিসাব করে stack-এ রাখা, তারপর OR. উপরের expression-এ কী হবে?

ডান পাশও হিসাব হবে, আর 4 / 0-এ runtime error division by zero, অথচ Haat-এর নিয়মে উত্তর true. && আর || function-এর মতো নয়: ডান পাশ শর্তসাপেক্ষে চলে, তাই এরা control flow, operator নয়। একই কারণে C-তে p != NULL && p->x > 0 নিরাপদ। সঠিক compile দুটি jump দিয়ে, উপরের emit-এর মতো।

৫.৩(মাঝারি) Compiler-এ constant folding যোগ করলে উপরের program কত ছোট হতে পারে? কোন অংশ fold করা চলবে না?

(7 - 2) * 3 > 10 সম্পূর্ণ ধ্রুবক, fold করলে CONST true. তখন true || …-এর ডান পাশ কখনো চলে না, তাই jump আর ডান পাশ বাদ দিয়ে পুরোটা একটি CONST true. কিন্তু ডান পাশটি একা fold করতে গেলে 4 / 0-কে compile-এর সময় হিসাব করা চলবে না: এটি runtime error, আর optimization দেখা যায় এমন আচরণ বদলাতে পারে না (পর্ব ৬৫)। নিয়ম: শূন্যে ভাগ থাকলে folder সেই node অপরিবর্তিত রেখে দেয়, যাতে চলার সময় একই error আসে।

৬ · ভাষার খুঁটিনাটি — অনুমান নয়, চালিয়ে দেখা

“এই কোড কী ছাপবে?” ধরনের প্রশ্নের উত্তর তিন অংশে দিন: ভাষা আর version, নিয়মটি (কোন specification বা বাস্তবায়নের কোন সিদ্ধান্ত), তারপর ফল। একটি বাস্তবায়নের ফল দেখে ভাষার নিয়ম ধরে নেবেন না; বিশেষ করে C-তে undefined behavior-এর কোনো “সঠিক আউটপুট” নেই। নিচের চারটি ব্লক চারটি ভাষায় সবচেয়ে চেনা ফাঁদগুলো সত্যিকারের engine বা compiler-এ চালায়।

"use strict";
// 1) closures in loops: var makes ONE binding, let makes one per round
const withVar = [], withLet = [];
for (var i = 0; i < 3; i++) withVar.push(() => i * 10);
for (let k = 0; k < 3; k++) withLet.push(() => k * 10);
console.log("var:", withVar.map(f => f()).join(","), "| let:", withLet.map(f => f()).join(","));
// 2) evaluation order: ECMAScript says left to right, side effects included
let n = 1;
const seen = [];
const tag = (name, v) => (seen.push(name + "=" + v), v);
const r = tag("L", n++) * 10 + tag("R", n);
console.log("order:", seen.join(" "), "| result:", r);
// 3) == converts types first, === does not; objects compare by identity
console.log(0 == "", "1" == 1, "1" === 1, null == undefined, [1] === [1]);
// 4) a call in tail position still grows V8's stack
function sum(n, acc) { return n === 0 ? acc : sum(n - 1, acc + n); }
console.log("sum(1000):", sum(1000, 0));
try { sum(1e6, 0); } catch (e) { console.log("sum(1e6):", e.name); }

আউটপুট (এই ব্লক আপনার ব্রাউজারের engine-এ চলে; লেখকের যন্ত্রে Node 24.15-এও হুবহু এক): var: 30,30,30 | let: 0,10,20; order: L=1 R=2 | result: 12; true true false true false; sum(1000): 500500; sum(1e6): RangeError. প্রথমটি per-iteration binding: var-এ পুরো function-এ একটি i, loop শেষে 3; let-এ প্রতি পাকে নতুন k. দ্বিতীয়টি ECMAScript-এর বাঁ-থেকে-ডান নিয়ম: বাঁ পাশ n++ আগে চলে 1 দেয়, তারপর ডান পাশ বাড়ানো n = 2 দেখে, 1 × 10 + 2 = 12. তৃতীয়টিতে == আগে type বদলায় ("" হয় 0), === বদলায় না, আর দুটি আলাদা array কখনো === নয়, ভেতরে যা-ই থাকুক। শেষটি: specification strict mode-এ proper tail call চায়, কিন্তু V8 (Chrome, Node) তা চালু করেনি, তাই দশ লাখ গভীরতায় stack ফুরায় (পর্ব ৩২); Firefox-এ error-এর নাম আলাদা হতে পারে।

# 1) late binding: a closure keeps the VARIABLE i, not its value at creation
fs = [lambda: i * 10 for i in range(3)]
gs = [lambda i=i: i * 10 for i in range(3)]      # default copies the value now
print("late:", [f() for f in fs], "| default copy:", [g() for g in gs])

# 2) mutable default argument: the list is made ONCE, when def runs
def add_item(item, cart=[]):
    cart.append(item)
    return cart
print(add_item("chal"), add_item("dal"), "| defaults:", add_item.__defaults__)
def add_item_ok(item, cart=None):
    cart = [] if cart is None else cart
    cart.append(item)
    return cart
print(add_item_ok("chal"), add_item_ok("dal"))

# 3) == compares values, is compares object identity
a, b = [1, 2], [1, 2]
x, y, p, q = int("256"), int("256"), int("257"), int("257")
print("lists:", a == b, a is b, "| 256:", x is y, "| 257:", p is q, p == q)

# 4) a tail call in CPython still uses one frame per call
import sys
def total(n, acc=0): return acc if n == 0 else total(n - 1, acc + n)
print("limit:", sys.getrecursionlimit(), "| total(900):", total(900))
try: total(5000)
except RecursionError as e: print("total(5000): RecursionError:", e)

প্রথম লাইন late binding: তিনটি lambda একটিই i ধরে, যার শেষ মান 2, তাই [20, 20, 20]; default argument মানটি তৈরির মুহূর্তে কপি করে, তাই [0, 10, 20]. দ্বিতীয় লাইনে default argument-এর list def চলার সময় একবার তৈরি হয়, তাই দুটি ডাক একই list ফেরত দেয়, আর print চলার আগে দুটিই হয়ে গেছে বলে দুবারই ['chal', 'dal'] (পর্ব ২৯)। None-এর কৌশলে প্রতিটি ডাকে নতুন list. তৃতীয় লাইনে == মান তুলনা করে, is একই object কি না; CPython −5 থেকে 256 পর্যন্ত ছোট int আগে থেকে বানিয়ে রাখে, তাই 256 is-এ True আর 257 False, অথচ == দুটিতেই True. এটি CPython-এর বাস্তবায়নের খুঁটিনাটি, ভাষার নিয়ম নয়; সংখ্যা বা string-এ is কখনো ব্যবহার করবেন না। শেষ দুই লাইন: CPython 3.14 tail call-কেও আলাদা frame দেয়, সীমা ১০০০, তাই 900 চলে আর 5000-এ RecursionError. লেখকের যন্ত্রের CPython 3.14.4-এ আউটপুট হুবহু এক।

#include <stdio.h>
#include <limits.h>
static int calls = 0;
int f(void) { printf("f "); return ++calls; }
int g(void) { printf("g "); return ++calls * 10; }
int main(void) {
    int s = f() + g();                  /* which call runs first: unspecified */
    printf("-> %d\n", s);
    printf("-7 / 2 = %d, -7 %% 2 = %d\n", -7 / 2, -7 % 2);
    unsigned int u = UINT_MAX;
    printf("UINT_MAX + 1 = %u (unsigned: wraps, defined)\n", u + 1);
    volatile int big = INT_MAX;         /* value unknown to the optimizer */
    int r;
    if (__builtin_add_overflow(big, 1, &r))
        printf("big + 1 would overflow: checked, never computed\n");
    if (big > INT_MAX - 1)
        printf("portable pre-check: big + 1 is not allowed\n");
    printf("in a wider type: %lld\n", (long long)big + 1);
    return 0;
}

Wandbox-এর GCC (warning চালু, কোনো warning আসেনি)-এ আউটপুট: f g -> 21; -7 / 2 = -3, -7 % 2 = -1; UINT_MAX + 1 = 0; তারপর দুটি পরীক্ষার বার্তা আর in a wider type: 2147483648. f() + g()-এ কোনটি আগে, C17-এ unspecified: এই compiler f আগে ডেকেছে, অন্য compiler বা option-এ উল্টো হতে পারে, আর দুটিই বৈধ (পর্ব ২৬)। Unsigned যোগ নিয়ম মেনে wrap করে; signed overflow undefined, তাই কোড কখনো big + 1 হিসাবই করে না, আগে পরীক্ষা করে: GCC আর Clang-এর __builtin_add_overflow (একটি extension, standard C নয়), অথবা portable big > INT_MAX - 1. পর্ব ০৬-এর সত্যিকারের Clang 22.1.8 run মনে করুন: একই x + 1 > x -O0-এ 0 আর -O2-এ 1 দিয়েছিল। সেটি “C-র উত্তর” নয়, undefined behavior-এর চেহারা।

import java.util.*;
class Box<T> {
    static int made = 0;                 // ONE static for every Box<...>
    T item;
    Box(T item) { this.item = item; made++; }
}
class Main {
    @SuppressWarnings("unchecked")
    static void sneak(List<String> names) { List raw = names; raw.add(42); }
    public static void main(String[] args) {
        List<String> s = new ArrayList<>();
        List<Integer> n = new ArrayList<>();
        System.out.println("same class: " + (s.getClass() == n.getClass()) + " (" + s.getClass().getName() + ")");
        new Box<String>("chal");
        new Box<Integer>(5);
        System.out.println("Box.made after Box<String> + Box<Integer>: " + Box.made);
        sneak(s);                        // heap pollution: an Integer inside a List<String>
        Object raw0 = ((List<?>) s).get(0);   // read without the String cast
        System.out.println("size: " + s.size() + ", element class: " + raw0.getClass().getSimpleName());
        try {
            String first = s.get(0);     // javac inserted a hidden cast here
            System.out.println(first.length());
        } catch (ClassCastException e) {
            System.out.println("ClassCastException at the hidden checkcast");
        }
        Integer a = 127, b = 127, c = 128, d = 128;
        System.out.println("127 ==: " + (a == b) + " | 128 ==: " + (c == d) + " | 128 equals: " + c.equals(d));
    }
}

Wandbox-এর OpenJDK 21-এ আউটপুট: same class: true (java.util.ArrayList); Box.made after Box<String> + Box<Integer>: 2; size: 1, element class: Integer; ClassCastException at the hidden checkcast; 127 ==: true | 128 ==: false | 128 equals: true. Type erasure-এর পর চলার সময় List<String> আর List<Integer> একই class, আর generic class-এর static field সব type argument-এ একটিই (C++-এর template-এ প্রতিটি instantiation-এর নিজের static থাকে)। Raw type দিয়ে একটি Integer ঢুকে গেল (heap pollution), ধরা পড়ল পরে, javac-এর বসানো লুকানো cast-এ (পর্ব ৩৭)। শেষ লাইন Java-র == বনাম Python-এর is-এর যমজ: Integer-এ == পরিচয় তুলনা করে, আর −128 থেকে 127-এর boxing একই object দেবে, এটুকু Java Language Specification নিশ্চিত করে; 128-এ ফল JVM-এর setting-নির্ভর। মান তুলনায় সবসময় equals.

৬.১(সহজ) C-তে int i = 1; int a = i++ + i++;-এর পরে a কত?

কোনো মান নেই: একই i-এ দুটি unsequenced বদল, তাই C17-এ undefined behavior. পর্ব ২৬-এর সত্যিকারের Clang compile-এর সময়েই -Wunsequenced warning দিয়েছিল (“multiple unsequenced modifications to 'i'”), আর সেই program ইচ্ছা করে চালানো হয়নি। ইন্টারভিউতে “3” বা “4” বলবেন না; বলুন “undefined, কারণ…”, তারপর ঠিক রূপ: আলাদা statement-এ দুটি বৃদ্ধি। Java বা JavaScript-এ একই expression বৈধ আর নির্দিষ্ট (বাঁ থেকে ডানে, 1 + 2 = 3), এটিও উল্লেখ করুন।

৬.২(মাঝারি) Java 21-এ একই class-এ static int total(List<Integer> xs) আর static int total(List<String> xs) দুটি overload লেখা যায় কি?

না। Erasure-এর পর দুটির signature একই total(List), তাই javac compile error দেয়। Wandbox-এর OpenJDK 21-এ সত্যিকারের বার্তা: error: name clash: total(List<String>) and total(List<Integer>) have the same erasure. C++-এ বা C#-এ (যেখানে generic type চলার সময়েও আলাদা) এমন overload সম্ভব। সমাধান: আলাদা নাম (totalInts), বা একটি generic method.

৬.৩(মাঝারি) Python-এ ফাঁকা list-এর default দেওয়া একটি function একজন সহকর্মী লিখেছেন, আর code review-তে আপনি আপত্তি করলেন। তিনি বললেন “test-এ তো ঠিক চলে।” কোন test-এ ভুলটি ধরা পড়বে?

যে test একই process-এ function-টি দুবার default দিয়ে ডাকে আর দ্বিতীয় ফল দেখে: উপরের run-এ দ্বিতীয় ডাক ['chal', 'dal'] দেয়, ['dal'] নয়। একবার ডাকা test সবসময় পাস করে, তাই ভুলটি টিকে যায়। প্রমাণ হিসেবে add_item.__defaults__ দেখান: সেখানে list-টি জমা হতে থাকে। সমাধান None দিয়ে, আর একটি linter নিয়ম; JavaScript (ES2015) প্রতিটি ডাকে default নতুন করে হিসাব করে, তাই সেখানে এই ফাঁদ নেই (পর্ব ২৯)।

৬.৪(কঠিন) “Python বা JavaScript-এ tail call optimization নেই কেন, আর দরকার হলে কী করবেন?”

CPython ইচ্ছা করেই করে না: প্রতিটি frame traceback-এ থাকে, আর debugging-এর এই সুবিধা নকশাকারীরা বেশি মূল্যবান মনে করেছেন; উপরের run-এ tail position-এর total-ও ৫০০০-এ ব্যর্থ। JavaScript-এর specification (ES2015) strict mode-এ proper tail call চায়, কিন্তু কার্যত শুধু Safari-র JavaScriptCore তা চালু করেছে; V8-এ নেই, যা উপরের RangeError-এ দেখলেন (পর্ব ৩২)। দরকার হলে recursion-কে loop-এ লিখুন, অথবা trampoline: function একটি “পরের কাজ” ফেরত দেয় আর একটি loop সেটি ডাকে, তাই stack জমে না। Scheme আর WebAssembly-র return_call-এ tail call নিশ্চিত।

৭ · “একটি feature যোগ করুন” — for, array আর pattern matching

নকশার প্রশ্নে ইন্টারভিউয়ার দেখতে চান আপনি compiler-কে ধাপে ধাপে ভাবেন কি না। ছক ধরে উত্তর দিন: প্রতিটি ধাপে কী বদলায়, কোথায় কিছুই বদলায় না, আর কোন test লাগবে। নিচের তিনটি feature Haat v1-এ নেই; এগুলো “Haat-এর বর্ধিত রূপ”, reference-এ নেই।

ধাপfor i in a..barray [1, 2], xs[i]match (ADT)
Lexerkeyword for, in; token ..[ ]match, =>, _
Parser ও ASTনতুন statementliteral; postfix index (call-এর মতো bp 80); index-এ assignmentpattern-এর grammar
Resolveri-এর scope আর পরিবর্তনযোগ্যতাকিছুই নয়pattern-এর নামগুলো শাখার scope-এ
Type checkera, b : Intনতুন type [T]; index Intexhaustiveness (পর্ব ৫৪)
Lowering / চালানোwhile-এ desugar (নিচে)heap object, সীমা পরীক্ষা, runtime errorপরীক্ষা আর jump-এর গাছে নামানো
VM ও GCকিছুই নয়নতুন opcode; GC-কে array চিনতে হবেtag পড়ার opcode

সবচেয়ে সস্তা পথ desugaring: নতুন syntax-কে পুরোনো core-এ নামিয়ে দিলে resolver থেকে VM পর্যন্ত কিছুই বদলাতে হয় না (পর্ব ৫৫)। কিন্তু “কেমন while-এ নামাবেন” প্রশ্নেই আসল নকশা লুকিয়ে। নিচের ব্লক একই program দুইভাবে নামায়: পুরো loop-এ একটি i, অথবা প্রতি পাকে নতুন i.

import re
SRC = """var fs = fn() -> Int { return 0; };
for i in 0..3 {
    let old = fs;
    fs = fn() -> Int { return old() * 10 + i; };
}
print(fs());"""
FOR = re.compile(r"for (\w+) in (.+?)\.\.(.+?) \{\n(.*?)\n\}", re.S)
counter = [0]
def lower(m, per_round):                         # for x in a..b { body }  ->  core Haat
    x, lo, hi, body = m.groups()
    counter[0] += 1; end = f"__end{counter[0]}"   # hidden name, yet a user may also write __end1
    if per_round:                                # a fresh x every round, like JS `let`
        k = f"__{x}{counter[0]}"
        loop = [f"var {k} = {lo};", f"let {end} = {hi};", f"while {k} < {end} {{",
                f"    let {x} = {k};", "    {", *["    " + l for l in body.splitlines()],
                "    }", f"    {k} = {k} + 1;", "}"]
    else:                                        # one x for the whole loop
        loop = [f"var {x} = {lo};", f"let {end} = {hi};", f"while {x} < {end} {{",
                *body.splitlines(), f"    {x} = {x} + 1;", "}"]
    return "{\n" + "\n".join("    " + l for l in loop) + "\n}"
for per_round in (False, True):
    print(f"// ---- per_round = {per_round}")
    print(FOR.sub(lambda m: lower(m, per_round), SRC))

দুটি আউটপুটই বৈধ Haat v1; লেখকের যন্ত্রে reference-এর check দুটিতেই ok বলেছে। run আর vm প্রথমটিতে 333 আর দ্বিতীয়টিতে 12 ছেপেছে। প্রথম রূপে তিনটি closure একই i ধরে, যা loop শেষে 3, তাই ((3)·10 + 3)·10 + 3 = 333: ঠিক JavaScript-এর var-এর ফাঁদ। দ্বিতীয় রূপে প্রতি পাকে let i = __i2; একটি নতুন, অপরিবর্তনীয় i বানায়, তাই ক্রমে 0, 1, 2 ধরা পড়ে: ((0)·10 + 1)·10 + 2 = 12, JavaScript-এর for (let …)-এর মতো। Upper bound একবারই হিসাব হয় (__end), আর দেহ একটি আলাদা block-এ, যাতে দেহের let loop-এর নিজের নামের সঙ্গে না মেশে।

৭.১(মাঝারি) উপরের lowering-এ লুকানো নাম __end1. এতে কোন ঝুঁকি, আর কীভাবে দূর করবেন?

Haat-এর identifier [A-Za-z_][A-Za-z0-9_]*, তাই ব্যবহারকারীও __end1 লিখতে পারেন; তখন দুই নাম মিশে যায় (একই scope-এ হলে “already declared”, ভেতরের scope-এ হলে নীরব shadowing). এটি macro-র hygiene-এর সমস্যা (পর্ব ৭৮)। সবচেয়ে সহজ সমাধান: লুকানো নাম এমন অক্ষর দিয়ে বানান, যা lexer কখনো identifier-এ দেয় না, যেমন $end1, আর desugaring AST-এর স্তরে করুন, text-এ নয়, যাতে এই নাম কখনো আবার lex হয় না। আরও ভালো: resolver-এর আগে প্রতিটি binding-এ একটি অনন্য id দিন, নাম নয়।

৭.২(মাঝারি) Array যোগ করলে Haat-এর কোন বিদ্যমান নকশা-সিদ্ধান্ত বদলাতে হয়, আর let xs = [1, 2]; xs[0] = 5; বৈধ হবে কি?

নকশা-সিদ্ধান্ত ৯ (assignment-এর লক্ষ্য শুধু একটি সাধারণ নাম) বদলাতে হবে: লক্ষ্য এখন xs[i]-ও। তারপর প্রশ্ন: let কি নামটিকে অপরিবর্তনীয় করে, নাকি ভেতরের মানও? Rust-এ দুটিই বন্ধ, JavaScript-এর const-এ শুধু নাম, তাই সেখানে xs[0] = 5 চলে। Haat-এর জন্য যেকোনো একটি বেছে লিখে রাখুন, আর type checker-এ সেই নিয়ম। সঙ্গে aliasing: let ys = xs;-এর পর একটির বদল অন্যটিতে দেখা যাবে কি (reference বনাম কপি, পর্ব ২৩)? আর সীমার বাইরে index-এ একটি নতুন runtime error, division by zero-এর মতো অবস্থানসহ।

৭.৩(কঠিন) Haat-এ enum Order { Cash(Int), Bkash(Int, Str), Free } আর match যোগ করতে হবে। সবচেয়ে কঠিন অংশ কোনটি, আর কীভাবে test করবেন?

দুটি: exhaustiveness আর lowering. Type checker-কে দেখাতে হবে প্রতিটি সম্ভাব্য মান অন্তত একটি শাখায় মেলে; নইলে “missing case Free” ধরনের বার্তা, অবস্থানসহ (পর্ব ৫৪, ধারণা পর্ব ২৪)। Nested pattern-এ এটি পরীক্ষার একটি matrix-এর প্রশ্ন, সরল তালিকা নয়। Lowering-এ match হয় tag-এর পরীক্ষা আর jump-এর গাছ, আর প্রতিটি শাখার নাম নতুন scope-এ। Test: প্রতিটি শাখা চলে এমন program, একটি শাখা বাদ দিলে নির্দিষ্ট error, আর একটি differential test: একই match-কে হাতে লেখা if-শিকলে বদলে দুই আউটপুট মেলানো।

৮ · Differential test থেকে compiler-এর bug — খোঁজা, ছোট করা, ঠিক করা

অনেক ইন্টারভিউর debugging-অংশে একটি ব্যর্থ test দিয়ে বলা হয়: “খুঁজে বের করুন।” Differential testing-এ দুটি বাস্তবায়ন একই input পায়; ফল আলাদা হলে অন্তত একটি ভুল। কাজের ধাপ: আবার ঘটানো (seed লিখে রাখা), সবচেয়ে ছোট উদাহরণে নামানো (shrinking), সন্দেহের লাইন খোঁজা, ঠিক করা, আর সেই ছোট উদাহরণকে স্থায়ী test বানানো। নিচে একটি constant folder তাড়াহুড়ায় লেখা: সে Python-এর // আর % ব্যবহার করেছে। অংশ ৩-এর ev এখানে oracle, আর এলোমেলো expression আসে rnd থেকে।

def fold(e, fixed):                              # a constant folder written in a hurry
    if isinstance(e, int): return e
    if len(e) == 2: return W(-fold(e[1], fixed))
    a, b = fold(e[1], fixed), fold(e[2], fixed)
    if e[0] == "/" and not fixed: return W(a // b)   # BUG? Python's // rounds toward -infinity
    if e[0] == "%" and not fixed: return a % b       # BUG? Python's % takes the divisor's sign
    return OPS[e[0]](a, b)
def outcome(f, e):
    try: return f(e)
    except ZeroDivisionError: return "division by zero"
def agrees(e, fixed): return outcome(ev, e) == outcome(lambda t: fold(t, fixed), e)
def shrink(e, fixed):                            # walk down while some child still disagrees
    while not isinstance(e, int):
        bad_kids = [k for k in e[1:] if not agrees(k, fixed)]
        if not bad_kids: return e
        e = bad_kids[0]
    return e
sx = lambda e: str(e) if not isinstance(e, tuple) else "(" + " ".join(map(sx, e)) + ")"
random.seed(2026); cases = [parse(lex(rnd(4))) for _ in range(2000)]
for fixed in (False, True):
    bad = [e for e in cases if not agrees(e, fixed)]
    print(f"fixed={fixed}: {len(bad)} of {len(cases)} programs disagree")
    if bad:
        small = shrink(bad[0], fixed)
        print("  first failure :", sx(bad[0]))
        print("  shrunk to     :", sx(small), "| interpreter:", outcome(ev, small), "| folder:", outcome(lambda t: fold(t, fixed), small))

২,০০০টির মধ্যে ১৫৫টিতে মতভেদ (seed 2026). প্রথম ব্যর্থ expression লম্বা আর পড়া কঠিন, কিন্তু shrink তাকে নামিয়েছে (% (% 4 9) (- 6))-এ, অর্থাৎ Haat-এ 4 % 9 % -6: interpreter বলে 4, folder বলে -2. কারণ এখন স্পষ্ট: Python-এর % ভাজকের চিহ্ন নেয়, Haat-এর ভাজ্যের। Reference-এর run-ও এই expression-এ 4 দেয়, আর লম্বা expression-টি reference-এর ast-এ হুবহু একই গাছ। ঠিক করার পর (fixed=True, অর্থাৎ OPS-এর C-ধাঁচের ভাগ) মতভেদ শূন্য। Shrink এখানে সবচেয়ে সরল রূপ: যতক্ষণ কোনো সন্তান-গাছও ব্যর্থ হয়, তার ভেতরে নামা। Property-based testing-এর tool-গুলো এর চেয়ে চতুর shrink করে (সফটওয়্যার টেস্টিং কোর্সের পর্ব ৫৮)।

৮.১(মাঝারি) ঠিক করার পর ২,০০০টিতে মতভেদ শূন্য। একজন বললেন “তাহলে folder এখন নির্ভুল।” কোন দুটি কারণে এটি বলা যায় না?

এক, input-এর পরিসর: সংখ্যা 0–9, গভীরতা ৪, তাই সর্বোচ্চ ১৬টি সংখ্যার গুণফলও 916, প্রায় 1.9 × 1015, যা 263-এর অনেক নিচে। Folder যদি *-এ wrap ভুলে যেত, এই test কখনো ধরত না; INT_MIN / -1-এর মতো প্রান্তও কখনো আসে না। দুই, common-mode ভুল: oracle আর folder দুজনেই একই OPS আর cdiv ব্যবহার করে, তাই সেখানে কোনো ভুল থাকলে দুজনেই একই ভুল উত্তর দেবে আর test পাস করবে। প্রতিকার: প্রান্তের মান ইচ্ছা করে মেশানো, আর oracle-কে আলাদা কোড থেকে বানানো (reference-এর ৪০০টি random test একটি স্বাধীন evaluator-এর সঙ্গে মেলায়)।

৮.২(মাঝারি) Bug report: “একটি Haat program run-এ 300 ছাপে, vm-এ 600.” কোন ক্রমে খুঁজবেন?

দুই back end একই AST পায়, তাই lexer আর parser সন্দেহের বাইরে প্রায়; check পাস করলে resolver আর checker-ও। এরপর: (১) program ছোট করুন, প্রতিবার run আর vm মিলিয়ে, যতক্ষণ পার্থক্য টেকে। (২) ছোট রূপের dis পড়ুন, আর হাতে VM-এর stack চালান। (৩) পার্থক্য closure বা loop-এর কাছে হলে সন্দেহ cell-এর দিকে: loop-এর প্রতি পাকে নতুন cell (MAKE_CELL) তৈরি হচ্ছে কি না, কারণ পুরোনো cell আবার ব্যবহার করলে closure-রা শেষ মান দেখে (অংশ ৪-এর দ্বিতীয় রানের মতো)। (৪) ঠিক করে ছোট program-টি golden test হিসেবে রাখুন। লক্ষ করুন, এখানে 300 = 0 + 100 + 200 আর 600 = 200 + 200 + 200: তিনটি closure-ই শেষ k দেখেছে, এই অনুমানের সঙ্গে সংখ্যা মেলে (লেখকের যন্ত্রে k-কে একটি ভাগের ঘরে রেখে চালিয়ে 600 মেলানো)।

৯ · জটিলতার প্রশ্ন — parsing, type inference আর register allocation

“এটি কত দ্রুত?” প্রশ্নে তিনটি জিনিস বলুন: কোন input-এর দৈর্ঘ্যে মাপছেন, সবচেয়ে খারাপ ক্ষেত্র কী, আর বাস্তবে কেন সাধারণত সমস্যা হয় না। নিচের ছকের প্রতিটি দাবি কোর্সের কোনো পর্বে প্রমাণ বা উৎসসহ আছে।

কাজখরচকোথায়
Pratt বা backtracking-হীন recursive descentO(n) সময়; recursion-এর গভীরতা O(n) হতে পারেপর্ব ৪৮, অংশ ৩
LL(1), LR(1) table-চালিত parsingO(n)গণনার তত্ত্ব পর্ব ৩৮, ৩৯
Earley (যেকোনো CFG)সবচেয়ে খারাপে O(n3), unambiguous-এ O(n2), অনেক LR grammar-এ রৈখিকগণনার তত্ত্ব পর্ব ৪১
Hindley–Milner inferenceDEXPTIME-complete (১৯৯০); বাস্তবে প্রায় রৈখিকপর্ব ৩৫
k রঙে graph colouring (k ≥ ৩)NP-complete; যেকোনো graph কোনো program-এর interference graph হতে পারে (Chaitin ও সহকর্মী, ১৯৮১)পর্ব ৭০

Hindley–Milner-এর সূচকীয় খরচ নিজে দেখুন। পর্ব ৩৫-এর Algorithm W-এর কোড অপরিবর্তিত কপি করে, Church-ধাঁচের জোড়া (pair = fn(a, b, k) k(a, b)) দিয়ে শিকল বানানো হলো: p1 = fn(y) pair(y, y), p2 = fn(y) p1(p1(y)), এভাবে pn. Let-polymorphism প্রতিটি ব্যবহারে নতুন কপি দেয়, তাই type-এর আকার প্রায় প্রতি ধাপে বর্গ হয়। সত্যিকারের run, লেখকের যন্ত্রে CPython 3.14.4-এ (সময় শুধু উদাহরণ, যন্ত্রভেদে আলাদা):

~/haat $ python hm_chain.py
n=1: type size        9 nodes, inference      0.2 ms
n=2: type size       21 nodes, inference      0.3 ms
n=3: type size       93 nodes, inference      0.8 ms
n=4: type size     1533 nodes, inference      3.8 ms
n=5: type size   393213 nodes, inference    843.9 ms

ছয়টি let-এর program, অথচ type-এ প্রায় চার লাখ node. ছয় নম্বর ধাপ চালানো হয়নি, কারণ আকার আবার প্রায় বর্গ হবে। বাস্তব program-এ এমন শিকল প্রায় আসে না, তাই ML বা OCaml-এর compiler দ্রুত চলে; পর্ব ৩৫-এ এর তাত্ত্বিক ব্যাখ্যাও আছে।

৯.১(মাঝারি) “Register allocation NP-complete হলে compiler এত দ্রুত চলে কীভাবে?”

Compiler সর্বোত্তম সমাধান খোঁজে না, একটি ভালো সমাধান খোঁজে। Chaitin-Briggs-এর simplify/select একটি heuristic: degree < k-এর node সরিয়ে রাখা, আটকালে spill. সময় প্রায় graph-এর আকারের অনুপাতে, আর ফল প্রায়ই সর্বোত্তমের কাছাকাছি। JIT আরও দ্রুত linear scan নেয় (Poletto–Sarkar ১৯৯৯), কিছুটা খারাপ ফলের বিনিময়ে। উত্তরের কাঠামো: “সমস্যাটি কঠিন, কিন্তু আমরা নিখুঁত উত্তর চাই না; ছোট মূল্যে প্রায়-ভালো উত্তর” (পর্ব ৭০)।

৯.২(কঠিন) Haat v1-এর type checking-এর খরচ HM-এর মতো সূচকীয় নয় কেন?

Haat v1-এ প্রতিটি parameter আর ফেরত-মানের type লেখা থাকে, আর let-এর type আসে তার initializer থেকে একবারে; কোনো type variable নেই, unification নেই, let-polymorphism নেই। তাই checker প্রতিটি AST node একবার দেখে, আর প্রতিটি node-এ type-এর তুলনা type-এর আকারের অনুপাতে। Type-এর আকার program-এ লেখা annotation-এর চেয়ে বড় হয় না, কারণ নতুন type কখনো জোড়া লাগিয়ে বানানো হয় না। সূচকীয় বিস্ফোরণের উৎস ছিল let-এর প্রতিটি ব্যবহারে নতুন কপি; annotation-বাধ্য ভাষায় সেটি নেই। এটি একটি আপস: লেখায় বেশি শব্দ, বদলে সরল আর দ্রুত checker আর স্পষ্ট error (পর্ব ৩৪, ৫২)।

১০ · ব্যাখ্যার প্রশ্ন, সাত দিনের প্রস্তুতি আর কোর্সের সমাপ্তি

কোডের পরে প্রায়ই আসে ব্যাখ্যার অংশ: compiler না জানা একজন সহকর্মীকে আপনি একটি সমস্যা কীভাবে বোঝাবেন। ভালো উত্তর ছোট, একটি উপমা দেয়, প্রমাণ দেয়, আর শেষে পরের কাজ বলে।

১০.১(মাঝারি) “Debug build-এ ঠিক চলছিল, release build-এ (-O2) বাজারঘরের একটি হিসাব ভুল আসছে। C-র কোডে একটি signed int-এর যোগ আছে।” Backend দলের একজন সহকর্মীকে চার বাক্যে বোঝান।

“C-তে signed সংখ্যার যোগ যদি সীমা পেরোয়, ভাষা কোনো ফলের প্রতিশ্রুতি দেয় না; compiler ধরে নিতে পারে এটি কখনো ঘটে না। Debug build যন্ত্রের সাধারণ যোগ করছিল বলে ফল ঘুরে ঋণাত্মক হচ্ছিল, আর optimize করা build সেই ‘অসম্ভব’ ক্ষেত্রটির পরীক্ষাই মুছে দিয়েছে; একই কোডে x + 1 > x একটিতে 0, অন্যটিতে 1 দেয়। তাই সমস্যাটি optimizer-এর নয়, কোডের: আমরা যোগের আগে সীমা পরীক্ষা বসাচ্ছি, আর হিসাবটি ৬৪ বিটে নিচ্ছি। সঙ্গে test-এ undefined behavior sanitizer চালু রাখছি, যাতে এমন ভুল আবার এলে সঙ্গে সঙ্গে ধরা পড়ে।” পরিভাষা কম, কারণ আছে, প্রমাণ আছে (পর্ব ০৬-এর run), পরের কাজ আছে।

১০.২(সহজ) “এমন একটি সময়ের কথা বলুন, যখন ভাষার ভেতরের জ্ঞান আপনার কাজে লেগেছে।” পেশাদার অভিজ্ঞতা না থাকলে কী বলবেন?

সত্যি ঘটনা বলুন, ছোট হলেও; বানানো গল্প পরের প্রশ্নেই ধরা পড়ে। কাঠামো: পরিস্থিতি, আপনার কাজ, সংখ্যায় ফল, শিক্ষা। এই কোর্সের Haat প্রকল্প যথেষ্ট উপাদান দেয়: “আমার নিজের ছোট ভাষার VM আর interpreter একটি loop-এর closure-এ আলাদা ফল দিচ্ছিল। দুটির আউটপুট মিলিয়ে program ছোট করতে করতে তিন লাইনে নামালাম, দেখলাম VM প্রতি পাকে নতুন cell বানাচ্ছিল না। ঠিক করে সেই তিন লাইন স্থায়ী test করেছি।” এই পাতার যেকোনো ব্লক এমন গল্পের বীজ, যদি আপনি নিজে সেটি বদলে, ভেঙে, আবার ঠিক করে দেখেন।

ইন্টারভিউ বা contest-এর আগের সাত দিন

দিনকাজকোথায়
১না দেখে tokenizer, ঘড়ি ধরে ২০ মিনিট; reference-এর tokens-এর সঙ্গে মেলানোঅংশ ২, পর্ব ৪৬
২Pratt evaluator আর shunting-yard, তারপর দুটির differential testঅংশ ৩, পর্ব ৪৮
৩Environment আর closure-সহ interpreter; counter আর loop-closure testঅংশ ৪, পর্ব ৫৬–৫৭
৪একই AST থেকে stack VM; short-circuit আর stack-গভীরতাঅংশ ৫, পর্ব ৫৮–৫৯
৫চার ভাষার ফাঁদ নিজে চালিয়ে, ভাষা ও version-সহ এক বাক্যে ব্যাখ্যাঅংশ ৬
৬একটি feature-এর ধাপভিত্তিক নকশা খাতায়; একটি bug-hunt নিজে বানিয়ে খোঁজাঅংশ ৭–৮
৭জটিলতা আর ব্যাখ্যার উত্তর জোরে বলা; নতুন বিষয় নয়, বিশ্রামঅংশ ৯–১০
অভিনন্দন

আপনি প্রোগ্রামিং ভাষা ও কম্পাইলার কোর্সের ৮৬টি পর্ব পেরিয়ে এসেছেন: ভাষার ইতিহাস আর paradigm থেকে নাম, scope, type system আর formal semantics; তারপর হাতে বানানো একটি পূর্ণ ভাষা-যন্ত্র: Haat-এর lexer, parser, resolver, type checker, interpreter আর bytecode VM, IR, SSA আর optimization, RISC-V আর WebAssembly-র code generation, linking আর garbage collection; শেষে ownership, concurrency, macro, DSL আর tooling. সবচেয়ে বড় অর্জন একটি অভ্যাস: কোনো ভাষার আচরণ নিয়ে দাবি করার আগে প্রশ্ন করা, “কোন ভাষা, কোন version, কোন নিয়মে?”, আর ছোট একটি program চালিয়ে উত্তর মেলানো।

এরপর কী করবেন

এই পাতা কোনো চাকরি বা contest-এর ফলের নিশ্চয়তা দেয় না। আপনার হাতে যা আছে, তা হলো একটি ছোট ভাষা-যন্ত্র নিজে বানানোর দক্ষতা, ভাষা আর version ধরে কথা বলার অভ্যাস, আর না-জানা জায়গায় সৎভাবে “এটি যাচাই না করে বলব না” বলার সাহস।

আরও গভীরে: Pratt-এর মূল প্রবন্ধ “Top Down Operator Precedence” ১৯৭৩ সালের, আর shunting-yard Dijkstra ALGOL 60-এর একটি compiler-এর কাজে ১৯৬০-এর দশকের শুরুতে বর্ণনা করেছিলেন বলে পরিচিত। Compiler-এর differential testing-কে বড় আকারে নিয়ে আসে Csmith (Yang, Chen, Eide আর Regehr, ২০১১), যা এলোমেলো কিন্তু undefined behavior-মুক্ত C program বানিয়ে GCC আর LLVM-এ কয়েকশো bug ধরেছিল বলে জানা; এর সবচেয়ে কঠিন অংশ ছিল ঠিক অংশ ৮-এর সমস্যা, অর্থাৎ oracle-কে বিশ্বাসযোগ্য রাখা। আর ছোট করার স্বয়ংক্রিয় পদ্ধতি delta debugging (Zeller ও Hildebrandt, ২০০২) আজ প্রায় সব fuzzer-এর অংশ।

পরীক্ষা ও ইন্টারভিউতে: “Precedence আর associativity Pratt-এ কীভাবে আসে?” — lbp তুলনা থেকে precedence, rbp = lbp + 1 থেকে বাঁ-সংযোগ। “Closure কী মনে রাখে?” — parameter, দেহ আর জন্মের environment. “&& কেন একটি opcode নয়?” — ডান পাশ শর্তসাপেক্ষে চলে, তাই jump. “Java-র Integer-এ ==?” — পরিচয় তুলনা; −128 থেকে 127-এ cache-এর কারণে কাকতালীয় true. “Differential test শূন্য মতভেদ দিলে?” — input-এর পরিসর আর oracle-এর স্বাধীনতা দেখুন, প্রমাণ বলবেন না।

AI-এর যুগে — নকল ইন্টারভিউ আর AI-এর কোড যাচাই

AI সহকারী একটি ভালো অনুশীলনের সঙ্গী, যদি তাকে প্রশ্নকর্তা বানান আর তার উত্তর যাচাই করেন। এই বিষয়ে তার চেনা ভুল: এক ভাষার নিয়ম সব ভাষায় চাপানো (“division সবসময় নিচের দিকে কাটে”), unspecified evaluation order বা undefined behavior-এর একটি ফলকে নিশ্চিত বলা, precedence বা associativity-ভুল parser (বিশেষ করে unary minus আর ডান-সংযোগে), বানানো compiler flag বা LLVM pass, আসল compiler-এর সঙ্গে না মেলা bytecode বা assembly, অর্থ বদলে দেওয়া “optimization” (যেমন x / x → 1), আর GC বা memory model-এর ভুল নিশ্চয়তা। যাচাইয়ের পথ এই পাতাতেই: আসল interpreter আর version-এ চালানো, specification মেলানো, edge case আর দুটি বাস্তবায়নের differential test, আর dis, -S, -emit-llvm বা javap-এর আসল আউটপুট পড়া।

নকল ইন্টারভিউর একটি কাঠামো; কোনো আসল প্রতিষ্ঠানের প্রশ্ন বা ব্যক্তিগত তথ্য দেবেন না:

তুমি একজন কড়া কিন্তু ভদ্র software engineering ইন্টারভিউয়ার, যার ঝোঁক প্রোগ্রামিং ভাষা আর compiler-এর দিকে। আমার স্তর: [শুরু/মাঝারি/উন্নত]। ১. আমাকে একটি "জায়গায় বসে বানান" প্রশ্ন দাও (tokenizer, expression evaluator, ছোট interpreter বা stack VM), spec-সহ: কোন operator, precedence, ভাগের নিয়ম, error-এ কী হবে। শুধু প্রশ্ন, উত্তর নয়। ২. আমি জোরে ভাবব। না চাইলে সংকেত দিও না; চাইলে একবারে একটি ছোট সংকেত। ৩. আমার কোড দেখে এমন সবচেয়ে ছোট input দাও, যাতে সেটি ভুল করে; আউটপুট নিজে দাবি করো না, আমি চালিয়ে দেখব। ৪. তারপর একটি "কী ছাপবে" প্রশ্ন দাও, ভাষা আর version উল্লেখ করে। undefined বা unspecified আচরণ থাকলে কোনো একটি মানকে সঠিক উত্তর বলবে না। ৫. শেষে চারটি দিকে ১ থেকে ৪ নম্বর দাও: প্রশ্ন স্পষ্ট করা, কোডের সঠিকতা, test, ব্যাখ্যা। ৬. কোনো compiler flag, pass, opcode বা তথ্যে নিশ্চিত না হলে "নিশ্চিত নই" লেখো; কোনো বই, প্রবন্ধ বা সংখ্যা বানাবে না।

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

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

প্রতিটি প্রশ্নে আগে খাতায় ভাবুন, তারপর উত্তর বাছুন। সব তথ্য প্রশ্নের ভেতরেই আছে।

ক্রমএকটি ছোট ভাষায় নতুন for loop যোগ করার কাজ compiler-এর ধাপ অনুযায়ী সাজান (▲▼ চেপে সরান)

  1. Lexer-এ নতুন keyword আর token
  2. Parser-এ grammar আর নতুন AST node
  3. Resolver আর type checker-এ scope ও type-এর নিয়ম
  4. while-এ desugar বা interpreter-এ চালানো
  5. Bytecode compiler আর VM-এ পরীক্ষা
  6. Golden test আর differential test যোগ

(সহজ) Haat-এর lexer maximal munch মানে, আর তার operator-এর তালিকায় != আর = আছে, !== নেই। JavaScript-এর অভ্যাসে লেখা a!==b-কে সে কোন token-এ ভাগ করে?

  • IDENT, !==, IDENT
  • IDENT, BANG_EQ, EQ, IDENT
  • IDENT, BANG, EQ_EQ, IDENT
  • lexical error: unexpected character

(সহজ) Python 3.14-এ fs = [lambda: i * 10 for i in range(3)]-এর পর [f() for f in fs] কী দেয়?

  • [0, 10, 20]
  • [0, 0, 0]
  • [20, 20, 20]
  • NameError

(মাঝারি) একটি Pratt parser-এ বিয়োগের lbp 50. একজন প্রার্থী ডান operand পড়লেন সীমা 50-এ (51-এ নয়)। 2 - 3 - 4-এর মান কত হবে?

  • -5
  • 1
  • syntax error
  • 3

(মাঝারি) একটি stack VM post-order-এ bytecode বানায় (বাঁ, ডান, তারপর operator). 1 + (2 + (3 + 4)) চালাতে stack-এর সর্বোচ্চ গভীরতা কত?

  • ৪
  • ২
  • ৩
  • ৭

(মাঝারি) Java 21-এ Integer c = 128, d = 128; তারপর c == d আর c.equals(d). ডিফল্ট JVM setting-এ কী ছাপবে?

  • true, true
  • false, true
  • false, false
  • compile error

(মাঝারি) C17-এ int s = f() + g();, যেখানে f আর g দুটিই কিছু ছাপে। একটি compiler আগে f চালাল। এ থেকে কী বলা যায়?

  • C সবসময় বাঁ থেকে ডানে হিসাব করে
  • program-টি undefined behavior
  • এই compiler-এর এই build-এর পছন্দ; অন্য build-এ উল্টো হতে পারে
  • associativity-র কারণে f আগে চলতেই হবে

(কঠিন) একটি constant folder-কে interpreter-এর সঙ্গে ২,০০০টি এলোমেলো expression-এ মেলানো হলো (সংখ্যা 0–9, + − * / %, গভীরতা ৪)। মতভেদ শূন্য। Folder যদি *-এ ৬৪-বিট wrap করতে ভুলে যায়, এই test কি তা ধরবে?

  • না, এই input-এ গুণফল কখনো 263 ছোঁয় না
  • হ্যাঁ, ২,০০০টি test যথেষ্ট
  • হ্যাঁ, unary minus-এর মাধ্যমে ধরা পড়বে
  • হ্যাঁ, Python overflow exception দেবে

শব্দকোষ

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

মনে রাখুন

  1. আগে spec: precedence, associativity, ভাগের দিক, শূন্যে ভাগ আর error-এর বার্তা এক লাইনে লিখে নিন; test সেখান থেকেই আসে।
  2. Lexer আর parser: maximal munch, keyword-টেবিল, code point-এ column; Pratt-এ lbp থেকে precedence আর rbp = lbp + 1 থেকে বাঁ-সংযোগ।
  3. Interpreter আর VM: closure = parameter + দেহ + জন্মের environment; loop-এর প্রতি পাকে নতুন scope; &&, || মানে jump.
  4. খুঁটিনাটিতে ভাষা আর version: late binding, mutable default, is আর Integer-এর ==, C-র unspecified আর undefined, V8 আর CPython-এ tail call নেই, Java-র erasure.
  5. যাচাই: oracle-এর সঙ্গে differential test, ব্যর্থতাকে ছোট করা, input-এর পরিসর আর oracle-এর স্বাধীনতা নিয়ে সৎ থাকা।

পথের শেষ: এটিই প্রোগ্রামিং ভাষা ও কম্পাইলার কোর্সের শেষ পর্ব; এর পরে আর কোনো পর্ব নেই। ৮৬টি পর্ব পেরিয়ে আসার জন্য অভিনন্দন। যেকোনো মডিউল আবার ঝালিয়ে নিতে কোর্স হোম বা পর্ব ০১-এর মানচিত্রে ফিরে যান, আর পাশের কোর্স হিসেবে গণনার তত্ত্ব বা DSA-র ইন্টারভিউ পাতায় অনুশীলন চালিয়ে যান। ইন্টারভিউ আর contest-এর জন্য শুভকামনা।

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

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