এই পর্বে যা শিখবেন
- দুই বা তিনটি ধারণার তুলনা একই মাপকাঠির ছকে লেখা, আর “কখন কোনটি” দিয়ে শেষ করা
- প্রতিটি দাবিতে ভাষা আর version বলা: “C-তে”, “Java 21-এ”, “CPython 3.14-এ”; এক ভাষার নিয়ম সব ভাষায় না চাপানো
- একটি ছোট program চালিয়ে উত্তরের সংখ্যা মেলানো: scope, parameter passing, stack code, register allocation আর GC
- নতুন কাউকে তিন মিনিটে closure, GC বা
-O2বোঝানো, সরল করেও ভুল না বলে - ভাইভায় এক বাক্যে মূল কথা, তারপর শর্ত আর উদাহরণ; না জানলে সৎভাবে বলা
১ · লিখিত উত্তরের কাঠামো — সংজ্ঞা, ছক, চালানো উদাহরণ, কখন কোনটি, সীমা
এই বিষয়ের লিখিত প্রশ্নের বড় অংশ তুলনার: compiler বনাম interpreter, static বনাম dynamic scope, erasure বনাম monomorphization, reference counting বনাম tracing GC. দুটি রেস্তোরাঁর তুলনায় দুজনকেই একই প্রশ্ন করতে হয়: কত সময়ে খাবার আসে, কত দাম, কত রকম পদ। একটির রান্না আর অন্যটির সাজসজ্জা বললে তুলনা হয় না। উত্তরেও একই সারির ছক, তারপর এমন একটি ছোট program, যেখানে দুটির আচরণ আলাদা।
- সংজ্ঞা: দুটি ধারণাই নির্দিষ্টভাবে, প্রয়োজনে প্রতীকে: “interpreter I(P, x) = ⟦P⟧(x); compiler P থেকে P′ বানায়, x ছাড়াই”.
- তুলনার ছক: তিন থেকে ছয়টি সারি, প্রতিটি সারিতে একই প্রশ্ন সব ধারণার জন্য।
- চালানো উদাহরণ: তিন থেকে দশ লাইনের program আর তার আসল আউটপুট, ভাষা ও version বলে।
- কখন কোনটি: এখানেই পরীক্ষক বোঝেন আপনি শুধু মুখস্থ করেননি।
- সীমা: কোন ভাষায় নিয়মটি খাটে না, কোন দাবি বাস্তবায়নের, ভাষার নয়, আর সাধারণত কোথায় ভুল হয়।
| প্রশ্নের ধরন | সংজ্ঞা | ছক | উদাহরণ | কখন কোনটি ও সীমা |
|---|---|---|---|---|
| ৫ নম্বর (ছোট তুলনা) | ১ | ২ | ১ | ১ |
| ১০ নম্বর (পূর্ণ তুলনা) | ২ | ৩ | ৩ | ২ |
এই ভাগ কোনো নির্দিষ্ট পরীক্ষার নিয়ম নয়; আপনার নির্দেশনা আলাদা হলে সেটিই মানুন। আটকে গেলে সংজ্ঞা আর ছক লিখে এগিয়ে যান; কাঠামোতেই অর্ধেক নম্বর। নিচের stepper-এ ক-০১ প্রশ্নের উত্তর ধাপে ধাপে গড়া হয়েছে।
| যোগ হলো | |
| খাতায় যা লিখলেন | |
| জমা নম্বর | |
| খরচ হওয়া সময় |
- সংজ্ঞা — ২ নম্বর। তিনটির পার্থক্য এক প্রশ্নে: অনুবাদ কখন হয়, আর তখন input জানা থাকে কি না।
- ছক — আরও ৩। একই পাঁচ প্রশ্ন তিনটির জন্য। মোট ৫ নম্বর, আট মিনিট।
- চালানো উদাহরণ — আরও ২। একই expression তিনভাবে, একই উত্তর; শুধু কাজের ধরন আলাদা।
- বাস্তব ব্যবস্থা — আরও ১। দুটি সত্যিকারের hybrid, নাম ধরে।
- ভুলের জায়গা — আরও ১। পরীক্ষকের প্রিয় পরের প্রশ্নটি আগেই উত্তর দেওয়া।
- কখন কোনটি — শেষ ১। কুড়ি মিনিটে দশ নম্বর।
| বিষয় | পর্ব | লিখিত | ভাইভা |
|---|---|---|---|
| ভিত্তি, অনুবাদক, interpreter আর VM | ০১–০৬, ৫৬–৬১ | অংশ ২ (ক-০১, ক-০২) | ভ-০১–ভ-০৪, ভ-১৬ |
| নাম, scope, subprogram | ১৪–৩২ | অংশ ৩ (খ-০১, খ-০২) | ভ-০৫–ভ-০৮ |
| Type system | ৩৩–৩৯ | অংশ ৪ (গ-০১–গ-০৩) | ভ-০৯, ভ-১০ |
| Semantics | ৪০–৪৪ | অংশ ৫ (ঘ-০১) | ভ-১১, ভ-১২ |
| Front end আর semantic analysis | ৪৫–৫৫ | অংশ ৬ (ঙ-০১) | ভ-১৩–ভ-১৫ |
| IR, optimization, code generation, runtime | ৬২–৭৫ | অংশ ৭ (চ-০১–চ-০৩) | ভ-১৭–ভ-২০ |
| আধুনিক ভাষা আর tool | ৭৬–৮১ | অংশ ৮ (ছ-০১, ছ-০২) | ভ-২১–ভ-২৪ |
এই পাতার কোনো প্রশ্ন কোনো নির্দিষ্ট পরীক্ষা, বিশ্ববিদ্যালয়, প্রতিষ্ঠান বা কোম্পানির ইন্টারভিউ থেকে নেওয়া নয়; এ ধরনের প্রশ্ন Programming Languages বা Compiler Design কোর্সে, চাকরির লিখিত পরীক্ষায় আর ইন্টারভিউতে প্রায়ই আসে। নয়টি Python ব্লক ব্রাউজারেই চলে (শুধু standard library); প্রথমবার Python নামাতে কয়েক সেকেন্ড লাগে। C ব্লকটি Wandbox-এর সত্যিকারের compiler-এ চলে। এখানে তুলনা আর ব্যাখ্যা; typing derivation, Hoare logic আর lambda calculus-এর হাতে-কলমে প্রমাণ পর্ব ৮৫-এ, three-address code, SSA আর activation record-এর হিসাব পর্ব ৮২-এ, MCQ পর্ব ৮৩-এ, আর ইন্টারভিউর কোড লেখা পর্ব ৮৬-এ।
২ · অংশ ক — অনুবাদক, interpreter আর virtual machine (মডিউল ১, ১০)
রিভিশন: পর্ব ০৪ (অনুবাদক), পর্ব ৫৬ (tree-walking interpreter), পর্ব ৫৮ (bytecode), পর্ব ৫৯ (stack VM), পর্ব ৬০ (CPython ও JVM), পর্ব ৬১ (JIT).
ছবি ৮৪.১ — একই program-এর তিন পথ
AOT compiler অনুবাদ শেষ করে তবে চালায়; interpreter অনুবাদ না করে চালায়; JIT চালাতে চালাতে গরম অংশ অনুবাদ করে, অনুমান ভাঙলে ফিরে আসে।
ক-০১Compiler, interpreter আর JIT compiler-এর সংজ্ঞা দিয়ে তুলনা করুন। “Python কি compiled না interpreted?” প্রশ্নটির সঠিক উত্তর কী? একটি hybrid ব্যবস্থা ব্যাখ্যা করুন। — ১০ নম্বর (সহজ–মাঝারি)
সংজ্ঞা: Compiler একটি source program P নিয়ে আরেক ভাষায় সমার্থক program P′ বানায়, যাতে প্রতিটি input x-এ ⟦P′⟧(x) = ⟦P⟧(x); কাজের সময় x জানা থাকে না। Interpreter P আর x একসঙ্গে নিয়ে সরাসরি ফল দেয়: I(P, x) = ⟦P⟧(x). JIT compiler একটি virtual machine-এর অংশ: চলার সময় গরম অংশ (hot spot) খুঁজে শুধু সেটুকু machine code-এ অনুবাদ করে, চলার profile দেখে। তিন পথের ছবি ওপরে (ছবি ৮৪.১)।
| মাপকাঠি | AOT compiler | Interpreter | JIT |
|---|---|---|---|
| অনুবাদ কখন | চালানোর আগে, একবার | হয় না; প্রতিবার পড়ে চালায় | চলার সময়, শুধু গরম অংশ |
| Input দেখে কি | না | হ্যাঁ, প্রতিটি ধাপে | হ্যাঁ, profile হিসেবে |
| শুরু হতে সময় | দ্রুত (অনুবাদ আগেই শেষ) | দ্রুত | ধীরে গরম হয় (warm-up) |
| সর্বোচ্চ গতি | বেশি | কম: প্রতিটি নির্দেশে বাছাইয়ের খরচ | বেশি; অনুমান করে আরও বেশি হতে পারে |
| Error কখন | অনেকটা compile-এর সময় | যে লাইন চলে, তখন | ভাষার নিয়ম অনুযায়ী; JIT অর্থ বদলায় না |
চালানো উদাহরণ: Haat-এর p - p / 10 (price-এর ছাড়ের হিসাব) তিনভাবে: tuple-এর AST-এর ওপর interpreter, একবার Python source-এ অনুবাদ করা “compiler”, আর তিন ডাকের পরে বদলানো একটি খেলনা JIT.
def cdiv(a, b): # Haat/C division: truncate toward zero
q = abs(a) // abs(b)
return q if (a >= 0) == (b >= 0) else -q
AST = ("-", ("var", "p"), ("/", ("var", "p"), ("num", 10))) # p - p / 10
visits = 0
def interp(e, env): # interpreter: walks the tree on every call
global visits; visits += 1
if e[0] == "num": return e[1]
if e[0] == "var": return env[e[1]]
a, b = interp(e[1], env), interp(e[2], env)
return a - b if e[0] == "-" else cdiv(a, b)
def to_py(e): # compiler: translate once, input not needed
if e[0] == "num": return str(e[1])
if e[0] == "var": return e[1]
l, r = to_py(e[1]), to_py(e[2])
return f"({l} - {r})" if e[0] == "-" else f"cdiv({l}, {r})"
src = "lambda p: " + to_py(AST)
compiled = eval(src, {"cdiv": cdiv})
print("compiler output:", src)
calls, fast = 0, None
def jit(p): # JIT: interpret while cold, compile when hot
global calls, fast
calls += 1
if fast is None and calls == 3:
fast = compiled; print(f" JIT: call {calls} is hot, compiled now")
return fast(p) if fast else interp(AST, {"p": p})
for p in (1040, -1040, 999, 7, 5000):
visits = 0; a = interp(AST, {"p": p}); v = visits
print(f"p={p:5}: interp {a:5} ({v} node visits) compiled {compiled(p):5} jit {jit(p):5}")আসল আউটপুট (ব্রাউজারের Python):
compiler output: lambda p: (p - cdiv(p, 10))
p= 1040: interp 936 (5 node visits) compiled 936 jit 936
p=-1040: interp -936 (5 node visits) compiled -936 jit -936
JIT: call 3 is hot, compiled now
p= 999: interp 900 (5 node visits) compiled 900 jit 900
p= 7: interp 7 (5 node visits) compiled 7 jit 7
p= 5000: interp 4500 (5 node visits) compiled 4500 jit 4500
পাঁচটি input-এ তিনটি পথের উত্তর এক, -1040-এ -936-সহ, কারণ ভাগ Haat spec-এর মতো (C-র মতোই) শূন্যের দিকে কাটে (পর্ব ৫৬)। পার্থক্য কাজের ধরনে: interpreter প্রতিটি ডাকে একই পাঁচটি node আবার ঘোরে; compiler-এর অনুবাদ (lambda p: (p - cdiv(p, 10))) input ছাড়াই একবার হয়েছে; JIT প্রথম দুই ডাকে interpret করে, তৃতীয় ডাকে “গরম” ধরে অনুবাদ করেছে।
বাস্তব hybrid: CPython 3.14 আগে source থেকে bytecode বানায়, তারপর সেই bytecode interpret করে; 3.11 থেকে interpreter চলতে চলতে নির্দেশ বিশেষায়িত করে (BINARY_OP থেকে BINARY_OP_MULTIPLY_INT, PEP 659; পর্ব ৬০)। Java-তে javac bytecode বানায়, JVM প্রথমে interpret করে, গরম method JIT-এ machine code হয়। পর্ব ৬১-এর সত্যিকারের Node 24-এ V8 নিজেই জানিয়েছে price আগে Maglev, পরে TurboFan-এ উঠেছে, আর কখনো না-চলা শাখায় পৌঁছাতেই deoptimization করেছে; একই কাজে --jitless-এ প্রায় ৭০০ ms, সব স্তর চালু রেখে প্রায় ২৮ ms (একটি যন্ত্রে মাপা, শুধু উদাহরণ)।
সঠিক উত্তর: “compiled ভাষা” বলে কিছু নেই, আছে compiled বা interpreted বাস্তবায়ন। CPython compile করে bytecode-এ, তারপর interpret করে; অন্য বাস্তবায়নে অন্য পথ।
কখন কোনটি: REPL, ছোট script আর দ্রুত শুরুতে interpreter; embedded, OS বা দ্রুত শুরু ও স্থির গতিতে AOT; অনেকক্ষণ চলা server-এ dynamic ভাষা হলে JIT, কারণ চলার আসল type আর শাখা দেখে অনুমান করা যায়।
পরীক্ষক যা খোঁজেন: তিন সংজ্ঞা, input-এর ভূমিকাসহ (২); ছক (৩); উদাহরণ (২); একটি hybrid নাম ধরে (১); ভাষা বনাম বাস্তবায়ন (১); কখন কোনটি (১)। পর্ব ০৪ · পর্ব ৬১
যেখানে নম্বর কাটে: “Java interpreted ভাষা” লেখা; “JIT মানে দ্রুত compiler” লেখা (আসল কথা চলার সময়ের তথ্য); deoptimization বাদ দেওয়া, যা ছাড়া অনুমান নিরাপদ নয়।
ক-০২Tree-walking interpreter, stack-ভিত্তিক VM আর register-ভিত্তিক VM-এর তুলনা করুন। p - p / 10-এর stack code আর register code লিখে নির্দেশ-সংখ্যা আর stack-এর গভীরতা দেখান। — ১০ নম্বর (মাঝারি)
সংজ্ঞা: Tree-walking interpreter AST-এর প্রতিটি node-এ গিয়ে মান হিসাব করে। Stack VM-এর নির্দেশ operand-কে একটি operand stack থেকে নেয় আর ফল সেখানে রাখে (Haat VM, CPython, JVM, WebAssembly). Register VM-এর নির্দেশ নিজেই বলে কোন ঘর থেকে পড়বে আর কোথায় লিখবে (Lua ৫.০ থেকে, BEAM).
| মাপকাঠি | Tree-walking | Stack VM | Register VM |
|---|---|---|---|
| যা চলে | AST নিজেই | সমতল নির্দেশের সারি | সমতল নির্দেশের সারি |
| নির্দেশ | নেই; node-প্রতি একটি শাখা | ছোট, সংখ্যায় বেশি | বড় (ঘরের নম্বরসহ), সংখ্যায় কম |
| Compiler-এর কাজ | নেই | সহজ: post-order | বেশি: ঘর বণ্টন করতে হয় |
| খরচের মূল | গাছ ঘোরা, pointer ধরে লাফ | dispatch বেশিবার | dispatch কম, decode বড় |
OPS = {"+": "ADD", "-": "SUB", "*": "MUL", "/": "DIV"}
def stack_code(e, out): # post-order: operands first, operator last
if isinstance(e, int): out.append(("CONST", e))
elif isinstance(e, str): out.append(("LOAD_LOCAL", e))
else:
stack_code(e[1], out); stack_code(e[2], out); out.append((OPS[e[0]], None))
return out
def reg_code(e, out): # three-address: one result name per operator
if not isinstance(e, tuple): return str(e)
l, r = reg_code(e[1], out), reg_code(e[2], out)
t = f"t{len(out) + 1}"; out.append(f"{t} = {l} {e[0]} {r}"); return t
def run_stack(code, env):
st, depth = [], 0
for op, arg in code:
if op == "CONST": st.append(arg)
elif op == "LOAD_LOCAL": st.append(env[arg])
else:
b, a = st.pop(), st.pop()
st.append({"ADD": a + b, "SUB": a - b, "MUL": a * b, "DIV": int(a / b)}[op])
depth = max(depth, len(st))
return st.pop(), depth
for name, e, env in [("p - p / 10", ("-", "p", ("/", "p", 10)), {"p": 1040}),
("(a + b) * (a - b)", ("*", ("+", "a", "b"), ("-", "a", "b")), {"a": 7, "b": 3})]:
sc, rc = stack_code(e, []), []
reg_code(e, rc)
val, depth = run_stack(sc, env)
print(f"{name} = {val}")
print(" stack :", "; ".join(f"{o} {a}" if a is not None else o for o, a in sc))
print(f" {len(sc)} instructions, max stack depth {depth}")
print(" register:", "; ".join(rc), f" ({len(rc)} instructions)")আসল আউটপুট (ব্রাউজারের Python):
p - p / 10 = 936
stack : LOAD_LOCAL p; LOAD_LOCAL p; CONST 10; DIV; SUB
5 instructions, max stack depth 3
register: t1 = p / 10; t2 = p - t1 (2 instructions)
(a + b) * (a - b) = 40
stack : LOAD_LOCAL a; LOAD_LOCAL b; ADD; LOAD_LOCAL a; LOAD_LOCAL b; SUB; MUL
7 instructions, max stack depth 3
register: t1 = a + b; t2 = a - b; t3 = t1 * t2 (3 instructions)
p - p / 10-এ stack code পাঁচটি নির্দেশ, register code দুটি। এই stack code-ই Haat reference-এর dis-এ price-এর ৮–১২ নম্বর নির্দেশ: LOAD_LOCAL 2; LOAD_LOCAL 2; CONST 1; DIV; SUB, শুধু সেখানে argument হলো slot আর constant pool-এর index. সর্বোচ্চ গভীরতা মেলে পর্ব ৫৮-এর সূত্রে: d(e1 ⊕ e2) = max(d(e1), 1 + d(e2)), পাতার মান ১; তাই 1 + d(p / 10) = 1 + 2 = 3.
বাস্তব সংখ্যা: পর্ব ৬০-এ price Haat VM, CPython আর JVM তিনটিতেই ১৬টি নির্দেশ; পার্থক্য খুঁটিনাটিতে: JVM-এর নির্দেশে type লেখা (lmul), আর চালানোর আগে verifier. পর্ব ৫৯-এ bazar.haat চালাতে Haat VM ঠিক ১২০টি নির্দেশ চালায়।
কখন কোনটি: শেখা, prototype আর ছোট DSL-এ tree-walking; portable ও সহজ compiler চাইলে stack VM; dispatch কমানো জরুরি হলে register VM, বা JIT-এর নিচের স্তর হিসেবে যেকোনোটি।
পরীক্ষক যা খোঁজেন: তিন সংজ্ঞা (২); ছক (৩); দুই রকম code আর গভীরতা (৩); বাস্তব VM-এর নাম (১); dispatch কমানোর উপায়: jump table, threaded code, superinstruction, JIT (১)। পর্ব ৫৮ · পর্ব ৫৯ · পর্ব ৬০
যেখানে নম্বর কাটে: “register VM মানে CPU-র register” লেখা (এগুলো VM-এর frame-এর ঘর); binary নির্দেশে কোনটি ডান operand ভুলে যাওয়া (ওপরেরটি)।
৩ · অংশ খ — নাম, scope আর parameter passing (মডিউল ৩, ৫)
রিভিশন: পর্ব ১৫ (scope), পর্ব ১৭ (closure), পর্ব ১৯ (evaluation strategy), পর্ব ২৯ (parameter passing), পর্ব ৩০ (activation record).
খ-০১Static (lexical) আর dynamic scope-এর পার্থক্য একটি program দিয়ে দেখান। Compiler প্রতিটির বাস্তবায়ন কীভাবে করে, আর closure-এর সঙ্গে static scope-এর সম্পর্ক কী? — ১০ নম্বর (সহজ–মাঝারি)
সংজ্ঞা: Static scope-এ একটি free variable খোঁজা হয় function যেখানে লেখা, সেখান থেকে বাইরে; dynamic scope-এ চলার সময় যে function ডেকেছে, তার কাছ থেকে, call stack ধরে।
Program: let rate = 5;, fn discount(t: Int) -> Int { return t * rate / 100; }, fn festival(t: Int) -> Int { let rate = 20; return discount(t); }, তারপর print(discount(1000)); print(festival(1000));. পর্ব ১৫-এর সত্যিকারের run: Haat ছাপে 50, 50; একই program bash-এ ছাপে 50, 200. নিচের ব্লকে একই নিয়মে দুই রকম parent.
# let rate = 5;
# fn discount(t: Int) -> Int { return t * rate / 100; }
# fn festival(t: Int) -> Int { let rate = 20; return discount(t); }
# print(discount(1000)); print(festival(1000));
class Frame:
def __init__(self, name, names, parent):
self.name, self.names, self.parent = name, names, parent
def lookup(self, x):
f = self
while x not in f.names: f = f.parent # follow the parent links
return f.names[x], f.name
GLOBAL = Frame("global", {"rate": 5}, None)
def call(fn, t, caller, mode):
parent = GLOBAL if mode == "static" else caller # the ONLY difference
frame = Frame(fn, {"t": t}, parent)
if fn == "festival":
frame.names["rate"] = 20
return call("discount", t, frame, mode)
rate, where = frame.lookup("rate")
print(f" rate = {rate:2} found in {where}")
return t * rate // 100
for mode in ("static", "dynamic"):
print(mode)
for fn in ("discount", "festival"):
print(f" {fn}(1000) = {call(fn, 1000, GLOBAL, mode)}")আসল আউটপুট (ব্রাউজারের Python):
static
rate = 5 found in global
discount(1000) = 50
rate = 5 found in global
festival(1000) = 50
dynamic
rate = 5 found in global
discount(1000) = 50
rate = 20 found in festival
festival(1000) = 200
পুরো পার্থক্য একটি লাইনে: নতুন frame-এর parent লেখার জায়গা (global), নাকি caller (festival-এর frame). Static-এ festival-এর rate = 20 discount-এর চোখেই পড়ে না; dynamic-এ পড়ে, তাই 200. Haat reference-এ python -B haat.py run একই program-এ 50, 50 দেয়।
| মাপকাঠি | Static (lexical) | Dynamic |
|---|---|---|
| নাম খোঁজার শিকল | লেখার দিক থেকে ঘিরে থাকা scope | call stack-এর সক্রিয় frame |
| কখন ঠিক হয় | compile-এর সময়: (কত স্তর বাইরে, কোন slot) | চলার সময়, প্রতিটি ডাকে |
| বাস্তবায়ন | static link, display, বা cell-ওয়ালা closure | নামের stack (shallow) বা frame ধরে খোঁজা (deep) |
| পড়ে বোঝা | শুধু function-এর লেখা দেখে | সব সম্ভাব্য caller জানতে হয় |
| উদাহরণ | Haat, C, Java, Python, JavaScript | bash-এর local, Perl-এর local |
Closure-এর সম্পর্ক: Closure = code + জন্মস্থানের environment. Static scope না থাকলে “জন্মস্থানের environment” কথাটির মানেই থাকত না। ফেরত দেওয়া function (upward funarg) তার জন্মের frame-এর চেয়ে বেশি বাঁচে, তাই ধরা variable heap-এ যায়: Haat VM-এ MAKE_CELL আর MAKE_CLOSURE, CPython-এ LOAD_DEREF (পর্ব ১৭, ৫৭)।
কখন কোনটি: প্রায় সব আধুনিক ভাষা static: পড়ে বোঝা, নাম বদলানো (refactor) আর দ্রুত code. Dynamic কাজে আসে সীমিত জায়গায়: shell-এর পরিবেশ-চলক, বা “এই ডাকের ভেতরে সাময়িকভাবে একটি সেটিং বদলাও” ধরনের ব্যবস্থা।
পরীক্ষক যা খোঁজেন: দুই সংজ্ঞা (২); একই program-এ দুই উত্তর (৩); ছক (২); বাস্তবায়ন আর closure (৩)। পর্ব ১৫ · পর্ব ৫৭
যেখানে নম্বর কাটে: dynamic scope আর dynamic typing গুলিয়ে ফেলা; JavaScript-এর var-কে dynamic scope বলা (সেটি function scope, তবু static); static link আর dynamic link-এর কাজ উল্টে লেখা।
খ-০২Call by value, reference, value-result, sharing, name আর need-এর তুলনা করুন। g = 2, দেহ x = x + 1; g = g * 10; x = x * 2;, ডাক f(g): প্রতিটি মোডে শেষে g কত? Java কি call by reference? — ১০ নম্বর (মাঝারি)
দুই স্তর: semantic মডেল বলে তথ্য কোন দিকে যায় (in, out, in-out); বাস্তবায়ন মডেল বলে কীভাবে: value-তে মানের কপি, reference-এ ঠিকানা, value-result-এ কপি আর ফেরার সময় ফিরতি কপি, name-এ argument-এর expression প্রতিটি ব্যবহারে নতুন করে, need-এ প্রথম ব্যবহারে একবার আর মনে রাখা (thunk-এ memo), sharing-এ reference-এর মানের কপি।
class Cell: # one storage location
def __init__(self, v): self.v = v
def body(x, g): # x = x + 1; g = g * 10; x = x * 2;
x.v = x.v + 1; g.v = g.v * 10; x.v = x.v * 2
def call_f(mode):
g = Cell(2)
if mode == "value": body(Cell(g.v), g)
elif mode in ("reference", "name"): body(g, g) # the argument is the name g
elif mode == "value-result":
x = Cell(g.v); body(x, g); g.v = x.v # copy back on return
return g.v
for m in ("value", "reference", "value-result", "name"):
print(f"f(g) by {m:12}: g = {call_f(m)}")
count = 0
def next_id(): # an argument with a side effect
global count; count += 1; return count
def triple(x): return x() + x() + x() # the parameter is used three times
def zero(x): return 0 # the parameter is never used
def by_value(e): v = e(); return lambda: v
def by_name(e): return e
def by_need(e):
memo = []
return lambda: memo[0] if memo else (memo.append(e()) or memo[0])
for name, wrap in (("value", by_value), ("name", by_name), ("need", by_need)):
count = 0; r = triple(wrap(next_id)); c1 = count
count = 0; zero(wrap(next_id)); c2 = count
print(f"by {name:5}: triple = {r}, next_id ran {c1}x; zero: ran {c2}x")আসল আউটপুট (ব্রাউজারের Python):
f(g) by value : g = 20
f(g) by reference : g = 60
f(g) by value-result: g = 6
f(g) by name : g = 60
by value: triple = 3, next_id ran 1x; zero: ran 1x
by name : triple = 6, next_id ran 3x; zero: ran 0x
by need : triple = 3, next_id ran 1x; zero: ran 0x
প্রথম চার লাইন পর্ব ২৯-এর সংখ্যা: 20, 60, 6, 60. Value-result আর reference আলাদা হয় শুধু aliasing-এ: এখানে x আর g একই ঘরের দুই নাম, তাই reference-এ g = 60, কিন্তু value-result-এ ফেরার সময় x-এর 6 g-এর 20-কে মুছে দেয়। Argument একটি সাধারণ variable বলে name আর reference এখানে একই। শেষ তিন লাইনে পার্থক্য সময় আর সংখ্যায়: name-এ next_id তিনবার চলে, ফল 1 + 2 + 3 = 6; need-এ একবার; ব্যবহার না হলে name ও need-এ একবারও না।
Java ও Python: Java সবসময় by value; object-এর বেলায় যে মান কপি হয় তা একটি reference (sharing). Callee object বদলাতে পারে, কিন্তু caller-এর variable-কে অন্য object-এ সরাতে পারে না। Python আর JavaScript-ও একই। Haat v1-এ শুধু value, আর parameter-এ লেখা নিষেধ: cannot assign to parameter 'n' (নকশা-সিদ্ধান্ত ১৯)।
কখন কোনটি: নিরাপদ ডিফল্ট value; বড় data শুধু পড়তে C++-এ const T&; একাধিক ফল ফেরাতে out বা reference; অদরকারি হিসাব এড়াতে need (Haskell); ALGOL 60-এর name আজ মূলত ইতিহাস আর Jensen's device-এর উদাহরণ।
পরীক্ষক যা খোঁজেন: দুই স্তরের পার্থক্য (২); ছয় মোডের সংজ্ঞা (৩); g-এর চার উত্তর, aliasing-এর ব্যাখ্যাসহ (৩); Java-র প্রশ্ন (২)। পর্ব ২৯ · পর্ব ১৯
যেখানে নম্বর কাটে: “Java-তে object by reference যায়” লেখা; value-result আর reference-কে সবসময় সমান বলা; aliasing-এর উদাহরণ না দেওয়া। পর্ব ২৯-এর সত্যিকারের Clang run-এ যোগ-বিয়োগের swap swap_add(p, p) মানটিকে 0 বানায়: aliasing-এর আরেকটি চেনা ফাঁদ।
৪ · অংশ গ — Type system, polymorphism আর generics (মডিউল ৬)
রিভিশন: পর্ব ৩৩ (static, dynamic, strong, weak), পর্ব ৩৬ (polymorphism), পর্ব ৩৭ (generics-এর বাস্তবায়ন), পর্ব ৩৮ (soundness). Typing derivation আর inference-এর হাতে-কলমে অনুশীলন পর্ব ৮৫-এ।
গ-০১Static বনাম dynamic typing আর strong বনাম weak typing ব্যাখ্যা করুন। “Python strong না weak?” প্রশ্নের ভালো উত্তর কী? Sound আর complete type checker কী? — ১০ নম্বর (মাঝারি)
সংজ্ঞা: Static typing-এ চালানোর আগে লেখা দেখে প্রতিটি expression-এর type যাচাই হয়, সব পথে; dynamic typing-এ চলার সময় মানের গায়ের tag দেখে, শুধু যে পথ চলে। Strong আর weak-এর সর্বসম্মত সংজ্ঞা নেই; তাই তিনটি স্পষ্ট প্রশ্নে উত্তর দিন: কখন যাচাই, কতটা নীরব রূপান্তর (implicit conversion), আর untrapped ভুল সম্ভব কি না। যে ভাষায় untrapped ভুল অসম্ভব, তাকে বলে safe.
একই লেখা, তিন ভাষা (পর্ব ০৩-এর সত্যিকারের run): C-তে "bazar" + 2 কোনো error ছাড়াই zar দেয় (pointer সরে যায়: untrapped); Python 3.14-এ TypeError (trapped); Node-এ bazar2, আর "5" - 3 হয় 2 (নীরব রূপান্তর, তবু safe).
| ভাষা | কখন যাচাই | নীরব রূপান্তর | untrapped ভুল সম্ভব? |
|---|---|---|---|
| C | static | অনেক (integer promotion, pointer) | হ্যাঁ |
| Java 21 | static, সঙ্গে চলার সময়ের cast-পরীক্ষা | কিছু (int থেকে long) | না |
| Python 3.14 | dynamic | কম | না |
| JavaScript | dynamic | অনেক | না |
| Haat | static | একটিও নয় | না |
Python-এর উত্তর: “Python dynamic, কম implicit conversion করে (1 + "a" TypeError), আর safe. ‘Strong’ বললে কোন অর্থে বলছি, তা জানাতে হবে।”
Sound আর complete: sound checker যা মেনে নেয় তা চলার সময় type-এর ভুলে আটকায় না; complete checker সব নিরাপদ program মেনে নেয়। Turing-complete ভাষায় দুটো একসঙ্গে অসম্ভব (Rice), তাই checker রক্ষণশীল: পর্ব ৩৩-এ ২,৯৪২টি ছোট expression-এর ২৭৫টি দিব্যি চলে, তবু Haat বাতিল করে; মেনে নেওয়া একটিও আটকায় না। TypeScript ইচ্ছা করেই unsound: পর্ব ৩৮-এ tsc --strict ০টি error দিয়েছে, অথচ চলার সময় TypeError.
কখন কোনটি: বড় দল, দীর্ঘ জীবন আর refactor-এ static; দ্রুত পরীক্ষা আর script-এ dynamic; মাঝে gradual typing (TypeScript, Python-এর type hint).
পরীক্ষক যা খোঁজেন: দুই অক্ষ আলাদা করা (২); তিন প্রশ্নের কাঠামো (২); ভাষার উদাহরণ, run-সহ (৩); sound/complete আর Rice (৩)। পর্ব ৩৩ · পর্ব ৩৮
যেখানে নম্বর কাটে: static/strong আর dynamic/weak-কে এক অক্ষ ভাবা; “type inference মানে dynamic typing” লেখা (inference static typing-এরই অংশ); “sound ভাষায় runtime error নেই” লেখা (শূন্য দিয়ে ভাগ ঘোষিত error, stuck নয়)।
গ-০২Parametric, ad hoc আর subtype polymorphism-এর উদাহরণসহ তুলনা করুন। Function-এর parameter কেন contravariant? — ৫ নম্বর (মাঝারি)
তিন রূপ (Strachey ১৯৬৭, Cardelli–Wegner ১৯৮৫): parametric: একই কোড সব type-এ একইভাবে, ∀α. α → α; ad hoc: একই নামের আলাদা কোড প্রতিটি type-এর জন্য (overloading, coercion, type class); subtype: T চাওয়া জায়গায় S <: T দেওয়া যায়, আর আসল method চলার সময় বাছা হয় (dynamic dispatch).
Contravariance: (Customer) → Int হলো (Member) → Int-এর subtype, যেখানে Member <: Customer: যে function যেকোনো Customer নিতে পারে, সে Member-ও নিতে পারে। উল্টোটা মানলে চলার সময় ভুল; পর্ব ৩৬-এ TypeScript-এর method syntax এই ফাঁক রাখে বলে সত্যিকারের run-এ TypeError. Java-র array covariant, তাই তার দাম ArrayStoreException; Java-র generics invariant (List<String> নয় List<Object>).
পরীক্ষক যা খোঁজেন: তিন সংজ্ঞা আর উদাহরণ (৩); variance-এর নিয়ম আর একটি ফাঁক (২)। পর্ব ৩৬
যেখানে নম্বর কাটে: overloading (compile-এর সময় বাছাই) আর overriding (চলার সময় dispatch) গুলিয়ে ফেলা; parameter-কেও covariant বলা।
গ-০৩Generics বাস্তবায়নের তিন পথ: type erasure, monomorphization আর dictionary passing. কোড-আকার, গতি, separate compilation আর চলার সময় type জানা: চার মাপকাঠিতে তুলনা করুন। Java-তে কেন new T() লেখা যায় না? — ১০ নম্বর (মাঝারি–কঠিন)
সংজ্ঞা: Monomorphization (C++, Rust): প্রতিটি ব্যবহৃত type-এর জন্য আলাদা কপি। Dictionary passing (Haskell-এর type class): একটি কপি, সঙ্গে একটি লুকানো argument, যাতে সেই type-এর operation-গুলোর টেবিল। Erasure (Java, TypeScript): type মুছে সব Object, আর ডাকের জায়গায় compiler একটি cast (checkcast) বসায়।
# one generic source: fn bigger<T>(a: T, b: T) -> T { if a > b {a} else {b} }
GT = {"Int": lambda a, b: a > b, "Str": lambda a, b: a > b,
"Taka": lambda a, b: a["paisa"] > b["paisa"]}
uses = [("Int", 7, 3), ("Str", "dal", "chal"), ("Taka", {"paisa": 500}, {"paisa": 900}),
("Int", 1, 2)]
copies = {} # 1) monomorphization: one copy per type used
for T, a, b in uses:
if T not in copies:
copies[T] = lambda a, b, gt=GT[T]: a if gt(a, b) else b
copies[T](a, b)
print("monomorphization:", len(copies), "copies:", ", ".join(f"bigger_{T}" for T in copies))
def bigger_dict(d, a, b): # 2) dictionary passing: one copy + hidden table
return a if d["gt"](a, b) else b
print("dictionary passing: 1 copy;", [bigger_dict({"gt": GT[T]}, a, b) for T, a, b in uses][:2])
def bigger_erased(a, b, gt): # 3) erasure: one copy on "Object", cast at the call site
return a if gt(a, b) else b
box = [] # a List<Int> after erasure: just a list of Object
box.append(5)
box.append("5") # a raw-type write: nothing checks it here
for i, x in enumerate(box):
try:
if type(x) is not int: raise TypeError(f"cast to Int failed at read {i}")
print(f" read {i}: {bigger_erased(x, 4, GT['Int'])}")
except TypeError as err:
print(" erasure:", err, "- the bad write happened earlier")আসল আউটপুট (ব্রাউজারের Python):
monomorphization: 3 copies: bigger_Int, bigger_Str, bigger_Taka
dictionary passing: 1 copy; [7, 'dal']
read 0: 5
erasure: cast to Int failed at read 1 - the bad write happened earlier
চারটি ডাকে তিনটি type, তাই monomorphization-এ তিন কপি (Int দুবার এলেও একটি); dictionary passing-এ এক কপি, প্রতিটি ডাকে আলাদা টেবিল। Erasure-এর ভুলটি ধরা পড়েছে পড়ার সময়ে, যেখানে cast বসানো, অথচ ভুল লেখা হয়েছিল আগে: Java-র raw type-এর heap pollution-এর মূল ছবি। এটি মডেল; সত্যিকারের প্রমাণ পর্ব ৩৭-এ: Clang 22-এ তিনটি mangled function (_Z6biggerIlET_S0_S0_ ইত্যাদি) আর javap-এ checkcast.
| মাপকাঠি | Monomorphization | Dictionary passing | Erasure |
|---|---|---|---|
| কোডের আকার | type-প্রতি কপি (code bloat) | এক কপি | এক কপি |
| গতি | সবচেয়ে দ্রুত, inline সম্ভব | টেবিল ধরে পরোক্ষ ডাক | cast আর primitive-এ boxing |
| Separate compilation | কঠিন: শরীর (source) লাগে | সহজ | সহজ |
| চলার সময় type জানা | হ্যাঁ, কপিতেই | টেবিলের মাধ্যমে | না |
| Polymorphic recursion | অসম্ভব; C++ ১০২৪ ধাপে থামে | চলে | চলে |
new T(): erasure-এর পরে চলার সময় T কোন type, তা জানা নেই; তাই কোন constructor ডাকতে হবে বলা যায় না।
কখন কোনটি: গতি আর শূন্য-খরচ চাইলে monomorphization; বড় library আর দ্রুত build চাইলে erasure বা dictionary; C# (reified) আর Go (GC shape stenciling) মাঝামাঝি পথ নিয়েছে।
পরীক্ষক যা খোঁজেন: তিন সংজ্ঞা (৩); চার মাপকাঠির ছক (৪); new T() (১); একটি বাস্তব প্রমাণ: mangled নাম বা checkcast (২)। পর্ব ৩৭
যেখানে নম্বর কাটে: “erasure মানে type safety নেই” লেখা (javac-এর বসানো cast তা রাখে; ভাঙে raw type বা unchecked cast-এ); C++ template-কে Java generics-এর সমান বলা।
৫ · অংশ ঘ — ভাষার semantics (মডিউল ৭)
রিভিশন: পর্ব ৪০, পর্ব ৪১, পর্ব ৪২. Derivation, Kleene approximant আর Hoare logic-এর পূর্ণ প্রমাণ লেখার অনুশীলন পর্ব ৮৫-এ; এখানে শুধু তুলনা।
ঘ-০১Operational, denotational আর axiomatic semantics-এর তুলনা করুন। একই ছোট loop-এ তিনটি কী বলে? কোনটি কোন কাজে লাগে? — ১০ নম্বর (মাঝারি–কঠিন)
সংজ্ঞা: Operational: যন্ত্রের ধাপ দিয়ে অর্থ: small-step ⟨S, σ⟩ ⟶ ⟨S′, σ′⟩, big-step ⟨S, σ⟩ ⇓ σ′. Denotational: অর্থ একটি গাণিতিক function ⟦S⟧ : State → State (⊥ মানে না-থামা), compositional, আর loop-এর অর্থ একটি least fixpoint. Axiomatic: চালানো নয়, চুক্তি: Hoare triple {P} S {Q}, “P সত্য অবস্থায় শুরু হয়ে থামলে Q সত্য”।
# S = while i < n { s = s + i; i = i + 1; } state = (i, s), n is fixed
def run(i, s, n): # operational: let the machine take steps
steps = 0
while i < n: i, s, steps = i + 1, s + i, steps + 1
return (i, s), steps
print("operational : (0, 0) ->", *run(0, 0, 5), "rounds (n = 5)")
def denote(n): # denotational: least fixpoint of F, from bottom
states = [(i, s) for i in range(n + 1) for s in range(n * n + 1)]
f, k = {}, 0 # f_0 = bottom: defined nowhere
while True:
g = {st: (st if st[0] >= n else f.get((st[0] + 1, st[1] + st[0])))
for st in states}
g = {st: v for st, v in g.items() if v is not None}
if g == f: return f, k
f, k = g, k + 1
f, k = denote(5)
print(f"denotational: [[S]](0, 0) = {f[(0, 0)]}; F applied {k} times to reach the fixpoint")
ok = all(run(0, 0, n)[0][1] == n * (n - 1) // 2 for n in range(0, 41))
print("axiomatic : {i = 0, s = 0, n >= 0} S {s = n(n-1)/2} on n = 0..40:", ok)
print("same answer from all three for n = 5:", run(0, 0, 5)[0] == f[(0, 0)] == (5, 10))আসল আউটপুট (ব্রাউজারের Python):
operational : (0, 0) -> (5, 10) 5 rounds (n = 5)
denotational: [[S]](0, 0) = (5, 10); F applied 6 times to reach the fixpoint
axiomatic : {i = 0, s = 0, n >= 0} S {s = n(n-1)/2} on n = 0..40: True
same answer from all three for n = 5: True
তিনটি দৃষ্টি একই উত্তরে পৌঁছায়: যন্ত্র পাঁচ ঘোরায় (5, 10)-এ থামে; ⊥ থেকে শুরু করে F ছয়বার খাটালে fixpoint মেলে (শুরুর অবস্থা থেকে পাঁচ ঘোরা, তাই ষষ্ঠ approximant-এ সংজ্ঞায়িত); আর triple-টি n = 0 থেকে 40 পর্যন্ত সব ক্ষেত্রে সত্য। শেষেরটি পরীক্ষা, প্রমাণ নয়: প্রমাণে loop invariant s = i(i − 1)/2 আর i ≤ n লাগে, যা পর্ব ৮৫-এর বিষয়।
| মাপকাঠি | Operational | Denotational | Axiomatic |
|---|---|---|---|
| যে প্রশ্নের উত্তর | কীভাবে চলে | কী হিসাব হয় | কী নিশ্চিত |
| Loop | ধাপের সারি বা derivation গাছ | least fixpoint (Kleene iteration) | loop invariant |
| না-থামা বনাম আটকানো | small-step আলাদা করে; big-step-এ দুটিই “গাছ নেই” | ⊥ আর err আলাদা | partial correctness দেখে না; total-এ variant লাগে |
| কাজে লাগে | interpreter, VM, type soundness | সমতা প্রমাণ, optimization-এর সঠিকতা | program যাচাই, verification tool |
বাস্তব সতর্কতা: পর্ব ৪২-এ গণিতের পূর্ণসংখ্যায় প্রমাণিত দাবি 64-bit wrap-এ ভেঙেছে: Z3 এমন qty আর unit দিয়েছে যাদের গুণফল wrap হয়ে −61, আর reference interpreter বিল ছেপেছে 5 টাকা। তাই semantics-এর অনুমান (ℤ, নাকি 64-bit) উত্তরে লিখুন।
পরীক্ষক যা খোঁজেন: তিন সংজ্ঞা, প্রতীকসহ (৩); ছক (৩); একই loop-এ তিন রূপ (২); কাজের ক্ষেত্র (২)। পর্ব ৪০ · পর্ব ৪১ · পর্ব ৪২
যেখানে নম্বর কাটে: “axiomatic semantics program চালায়” লেখা; least কেন, না বলা (while true { }-এ সব function-ই fixpoint); partial আর total correctness গুলিয়ে ফেলা।
৬ · অংশ ঙ — Front end: parsing-এর কৌশল (মডিউল ৮–৯)
রিভিশন: পর্ব ৪৫, পর্ব ৪৭ (recursive descent), পর্ব ৪৮ (Pratt). তত্ত্ব: গণনার তত্ত্ব কোর্সের পর্ব ৩৮ (LL(1)), পর্ব ৩৯ (LR), পর্ব ৪০ (parser generator).
ঙ-০১LL, LR আর Pratt parsing-এর তুলনা করুন, তত্ত্ব আর বাস্তব দুই দিক থেকে। Production compiler-গুলো বেশিরভাগ হাতে লেখা parser কেন ব্যবহার করে? a - b - c-এর associativity কোথায় ভাঙতে পারে? — ১০ নম্বর (মাঝারি)
সংজ্ঞা: LL(1) ওপর থেকে নিচে, leftmost derivation, একটি lookahead token দেখে নিয়ম বাছে; grammar-এ left recursion থাকা চলে না, common prefix-এ left factoring লাগে; হাতে লেখা recursive descent এর স্বাভাবিক রূপ। LR নিচ থেকে ওপরে: shift-reduce, rightmost derivation উল্টো ক্রমে; left recursion সহজে চলে, grammar-এর শ্রেণি বড় (প্রতিটি LL(1) grammar LR(1)), কিন্তু টেবিল সাধারণত parser generator (yacc, Bison) বানায়। Pratt: recursive descent-এর ভেতরে expression-এর জন্য binding power-এর টেবিল আর একটি loop.
import re
LBP = {"||": 10, "&&": 20, "==": 30, "!=": 30, "<": 40, "<=": 40, ">": 40, ">=": 40,
"+": 50, "-": 50, "*": 60, "/": 60, "%": 60} # Haat's binding powers
CMP = {30, 40} # non-associative levels
def parse(src):
toks = re.findall(r"\w+|[<>=!]=|&&|\|\||\S", src) + ["$"]
pos = 0
def expr(min_bp):
nonlocal pos
t = toks[pos]; pos += 1
if t in "-!": left = f"({t} {expr(70)})" # prefix: rbp 70
elif t == "(": left = expr(0); pos += 1 # skip ")"
else: left = t
last = None
while toks[pos] in LBP and LBP[toks[pos]] >= min_bp:
op = toks[pos]; pos += 1
if LBP[op] in CMP and LBP[op] == last:
raise SyntaxError("comparison operators cannot be chained")
left = f"({op} {left} {expr(LBP[op] + 1)})" # rbp = lbp + 1: left assoc.
last = LBP[op]
return left
return expr(0)
def naive(src): # textbook trap: E -> T - E (right recursion)
t, _, rest = src.partition(" - ")
return f"(- {t} {naive(rest)})" if rest else t
for s in ["a - b - c", "-a * b", "a < b == c < d", "a + b * c - d",
"!(a < b) || c == d && a != b", "a < b < c"]:
try: print(f"{s:30} {parse(s)}")
except SyntaxError as e: print(f"{s:30} error: {e}")
print("right-recursive grammar:", naive("a - b - c"), "<- wrong for 10 - 4 - 3:", 10 - (4 - 3))আসল আউটপুট (ব্রাউজারের Python):
a - b - c (- (- a b) c)
-a * b (* (- a) b)
a < b == c < d (== (< a b) (< c d))
a + b * c - d (- (+ a (* b c)) d)
!(a < b) || c == d && a != b (|| (! (< a b)) (&& (== c d) (!= a b)))
a < b < c error: comparison operators cannot be chained
right-recursive grammar: (- a (- b c)) <- wrong for 10 - 4 - 3: 9
প্রথম ছয়টি লাইন Haat reference-এর python -B haat.py ast-এর সঙ্গে অক্ষরে অক্ষরে মেলে, শেষটির error বার্তাও (নকশা-সিদ্ধান্ত ১০)। rbp = lbp + 1 বাঁ-সংযোগ দেয়; prefix-এর 70 > 60 বলে -a * b হয় (* (- a) b). শেষ লাইন ফাঁদটি দেখায়: left recursion এড়াতে E → T - E লিখলে গাছ ডানে ঝোঁকে, আর 10 − 4 − 3 হয় 9, 3 নয়।
| মাপকাঠি | LL(1) / recursive descent | LR (LALR, LR(1)) | Pratt |
|---|---|---|---|
| দিক | ওপর থেকে নিচে | নিচ থেকে ওপরে | ওপর থেকে, expression-এ loop |
| Left recursion | চলে না; loop বা রূপান্তর | চলে | প্রশ্নই আসে না: loop |
| Precedence | প্রতি স্তরে একটি function | grammar-এর স্তর বা %left ঘোষণা | টেবিলের সংখ্যা |
| Error message | সহজে ভালো | কঠিন (state-এর ভাষায়) | সহজে ভালো |
| সময় | O(n) | O(n) | O(n) |
বাস্তব: Clang, GCC, Go, rustc আর V8 হাতে লেখা recursive descent ব্যবহার করে: ভালো error message, error recovery, context-নির্ভর জায়গা সামলানো, আর বাড়তি tool ছাড়া build (পর্ব ৪৫)। ব্যতিক্রমও আছে: CPython grammar থেকে তৈরি PEG parser ব্যবহার করে (PEP 617). Haat-এর reference statement-এ recursive descent আর expression-এ Pratt; পর্ব ৪৮-এর ল্যাবে ৫,০০০টি এলোমেলো input-এ পাতার parser reference-এর সঙ্গে মিলেছে।
কখন কোনটি: নিজের ভাষা আর ভালো বার্তা চাইলে recursive descent + Pratt; grammar ঘন ঘন বদলালে বা বড় grammar দ্রুত চাইলে generator; শুধু expression হলে Pratt বা shunting-yard.
পরীক্ষক যা খোঁজেন: দুই কৌশলের সংজ্ঞা আর শ্রেণির সম্পর্ক (৩); ছক (৩); associativity-র ফাঁদ আর তার সমাধান (২); বাস্তব compiler-এর পছন্দ ও কারণ (২)। পর্ব ৪৭ · পর্ব ৪৮
যেখানে নম্বর কাটে: “LR সবসময় ভালো, কারণ শক্তিশালী” লেখা (বাস্তব পছন্দ error-এর মান আর রক্ষণাবেক্ষণে); left recursion সরাতে গিয়ে associativity উল্টে ফেলা; FIRST/FOLLOW-এর টেবিল দিয়ে উত্তর ভরানো, যখন প্রশ্ন বাস্তবের।
৭ · অংশ চ — IR, back end আর runtime (মডিউল ১১–১২)
রিভিশন: পর্ব ৬২ (three-address code ও CFG), পর্ব ৬৩ (SSA), পর্ব ৬৪ (dataflow), পর্ব ৭০ (register allocation), পর্ব ৭৫ (GC). হাতে হিসাবের অনুশীলন পর্ব ৮২-এ।
চ-০১AST, control flow graph আর SSA form-এর তুলনা করুন: কী স্পষ্ট দেখায়, কে বানায়, কোন কাজে লাগে। bazar.haat-এর while loop তিন রূপে দেখান। — ১০ নম্বর (মাঝারি)
সংজ্ঞা: AST: program-এর গঠন, অপ্রয়োজনীয় চিহ্ন বাদ। CFG: basic block (শুধু শুরুতে ঢোকা, শুধু শেষে বেরোনো নির্দেশের সারি) আর তাদের মাঝে লাফের edge. SSA: CFG-এর যে রূপে প্রতিটি নামে লেখা একবার; পথ মেলার জায়গায় φ.
একই loop, তিন রূপ (সত্যিকারের আউটপুট থেকে, কয়েকটি লাইন এক লাইনে জোড়া: প্রথমটি reference-এর ast, বাকি দুটি পর্ব ৬২ আর ৬৩-এর):
AST: (while (< total 5000)
(block (set total (+ total 1250)) (set rounds (+ rounds 1))))
CFG: B1: t8 = const 5000; t9 = total < t8; branch t9 B2 B3
B2: t10 = const 1250; total = total + t10
t11 = const 1; rounds = rounds + t11; jump B1
B1: pred [B0, B2] B2: pred [B1]
SSA: B1: rounds#2 = phi(B0: rounds#1, B2: rounds#3)
total#2 = phi(B0: total#1, B2: total#3)
t8 = const 5000; t9 = total#2 < t8; branch t9 B2 B3
| মাপকাঠি | AST | CFG (three-address) | SSA |
|---|---|---|---|
| স্পষ্ট দেখায় | গঠন আর nesting | নিয়ন্ত্রণের প্রবাহ, প্রতিটি মধ্যবর্তী ফল | প্রতিটি মান কোথা থেকে (def-use) |
| কে বানায় | parser | lowering, leader-নিয়মে টুকরো | dominance frontier-এ φ, তারপর নাম বদল |
| কাজে লাগে | type checking, interpreter, formatter | dataflow analysis, liveness | constant propagation, CSE, DCE সরল হয় |
| সীমা | while-এর ভেতরের লাফ লুকানো | একই নামে অনেক লেখা | machine code-এর আগে φ সরাতে হয় |
বাস্তব: LLVM IR নিজেই SSA; Clang আগে local-কে alloca/load/store দিয়ে লেখে, পরে mem2reg বা SROA তাদের φ-তে তোলে (পর্ব ৬৩, ৬৮)। পর্ব ৬৩-এ bazar-এর IR আর SSA দুটিতেই ৭৪টি নির্দেশ চলে; SSA থেকে ফেরার পরে ৮৪, কারণ φ-এর জায়গায় copy বসে।
পরীক্ষক যা খোঁজেন: তিন সংজ্ঞা (৩); একই কোড তিন রূপে (৩); ছক (২); φ কেন আর কোথায় (২)। পর্ব ৬২ · পর্ব ৬৩
যেখানে নম্বর কাটে: CFG-কে parse tree ভাবা; φ-কে একটি চলা নির্দেশ ভাবা (block-এর শুরুর সব φ একসঙ্গে, সমান্তরালভাবে মান নেয়); SSA থেকে ফেরার lost-copy আর swap সমস্যা না জানা।
চ-০২Graph-colouring register allocation আর linear scan-এর তুলনা করুন। কোনটি কোথায় ব্যবহার হয়, আর কেন? — ৫ নম্বর (মাঝারি–কঠিন)
সংজ্ঞা: Graph colouring (Chaitin ১৯৮১–৮২): liveness থেকে interference graph, তারপর k রঙে রং = k টি register; degree < k node সরিয়ে stack-এ (simplify), উল্টো ক্রমে রং (select); আটকে গেলে spill. Briggs আটকে যাওয়া node-কেও আশায় রাখেন (optimistic). Linear scan (Poletto–Sarkar ১৯৯৯): graph ছাড়া, live interval-এর ওপর শুরুর ক্রমে একবার হাঁটা।
def colour(nodes, edges, k, optimistic):
adj = {v: {w for e in edges for w in e if v in e and w != v} for v in nodes}
left, stack, spilled = set(nodes), [], []
while left:
low = sorted(v for v in left if len(adj[v] & left) < k)
v = low[0] if low else sorted(left)[0] # stuck: all have >= k neighbours
if not low and not optimistic: spilled.append(v); left.remove(v); continue
stack.append(v); left.remove(v)
col = {}
for v in reversed(stack): # select: pop and take a free colour
free = [c for c in range(k) if c not in {col.get(w) for w in adj[v]}]
if free: col[v] = free[0]
else: spilled.append(v)
return col, spilled
square = (["a", "b", "c", "d"], [("a", "b"), ("b", "c"), ("c", "d"), ("d", "a")])
for name, opt in (("Chaitin", False), ("Briggs", True)):
col, sp = colour(*square, 2, opt)
print(f"{name:8} k=2 cycle a-b-c-d: colours {col} spilled {sp}")
ranges = {"x": [(0, 1), (4, 5)], "y": [(2, 3)], "z": [(2, 3)]} # x: a hole at 2..3
edges = [(u, v) for u in ranges for v in ranges if u < v and any(
a <= d and c <= b for a, b in ranges[u] for c, d in ranges[v])]
print("interference edges:", edges, "->", colour(list(ranges), edges, 2, True))
iv = sorted((min(a for a, _ in r), max(b for _, b in r), v) for v, r in ranges.items())
active, spills = [], []
for s, e, v in iv: # linear scan sees one interval per name
active = [x for x in active if x[0] >= s]
if len(active) < 2: active.append((e, v))
else: spills.append(max(active + [(e, v)])[1])
print("linear scan intervals:", [(v, s, e) for s, e, v in iv], "spilled", spills)আসল আউটপুট (ব্রাউজারের Python):
Chaitin k=2 cycle a-b-c-d: colours {'d': 0, 'c': 1, 'b': 0} spilled ['a']
Briggs k=2 cycle a-b-c-d: colours {'d': 0, 'c': 1, 'b': 0, 'a': 1} spilled []
interference edges: [('y', 'z')] -> ({'z': 0, 'y': 1, 'x': 0}, [])
linear scan intervals: [('x', 0, 5), ('y', 2, 3), ('z', 2, 3)] spilled ['x']
বৃত্ত a–b–c–d-এর প্রতিটি node-এর দুই প্রতিবেশী, তাই k = 2-এ শুরুতেই আটকানো। Chaitin a-কে spill করেন; Briggs তাকে stack-এ রাখেন, আর select-এর সময় তার দুই প্রতিবেশী b আর d একই রং পেয়েছে বলে a-ও রং পায়: spill শূন্য। দ্বিতীয় অংশে x-এর জীবনে 2–3-এ একটি ফাঁক; graph দেখে যে x কারও শত্রু নয়, তাই দুই রঙেই চলে। সরল linear scan একটি নামের একটি interval [0, 5] দেখে, তাই 2–3-এ তিনটি জীবিত ভেবে x-কে spill করে। উন্নত linear scan জীবনের ফাঁক (lifetime hole) বোঝে আর interval ভাঙে।
কখন কোনটি: AOT compiler-এ, যেখানে সময় আছে আর কোডের মান জরুরি, graph colouring বা তার উত্তরসূরি; JIT-এ, যেখানে allocation দ্রুত হতে হবে, linear scan (পর্ব ৭০)। পর্ব ৭০-এর যাচাই: register-নামে লেখা কোড IR interpreter-এ চালিয়ে ৩,০১০টি program-এ reference-এর সঙ্গে হুবহু।
পরীক্ষক যা খোঁজেন: দুই সংজ্ঞা (২); একটি উদাহরণে spill-এর পার্থক্য (২); কোথায় কোনটি (১)। পর্ব ৭০ · পর্ব ৬৪
যেখানে নম্বর কাটে: “k-colouring polynomial সময়ে নিখুঁত হয়” লেখা (সাধারণ graph-এ NP-complete, তাই heuristic); “linear scan সবসময় খারাপ” লেখা (দ্রুততার বিনিময়ে কিছু বেশি spill).
চ-০৩Reference counting আর tracing GC (mark-sweep, copying, generational)-এর তুলনা করুন। তারপর GC আর Rust-এর ownership-এর আপস লিখুন। — ১০ নম্বর (মাঝারি–কঠিন)
সংজ্ঞা: Garbage মানে root (global, frame-এর slot, VM-এর stack) থেকে পৌঁছানো যায় না এমন object. Reference counting প্রতিটি object-এ গোনে কতজন তাকে দেখায়; শূন্য হলে সঙ্গে সঙ্গে মুক্ত। Mark-sweep root থেকে চিহ্ন দেয়, তারপর পুরো heap ঝাড়ে; copying (Cheney) জীবিতদের নতুন জায়গায় কপি করে; generational নতুনদের ঘন ঘন আলাদা করে দেখে।
heap = {"cart": ["item1", "item2"], "item1": [], "item2": [],
"f": ["cell"], "cell": ["f"], # a closure and its cell: a cycle
"tmp": ["note"], "note": []}
roots = {"cart", "f", "tmp"}
rc = {o: 0 for o in heap} # reference counts
for o in heap:
for p in heap[o]: rc[p] += 1
for r in roots: rc[r] += 1
freed = []
def dec(o): # RC: free as soon as the count hits 0
rc[o] -= 1
if rc[o] == 0:
freed.append(o)
for p in heap[o]: dec(p)
roots -= {"f", "tmp"} # the program drops two roots
dec("f"); dec("tmp")
print("RC freed at once:", freed, "| counts left on f, cell:", rc["f"], rc["cell"])
marked, todo, visits = set(), list(roots), 0 # tracing: mark from the roots
while todo:
o = todo.pop(); visits += 1
if o not in marked: marked.add(o); todo += heap[o]
garbage = sorted(set(heap) - marked)
print(f"mark-sweep: marked {len(marked)}, swept {len(garbage)} {garbage}, "
f"sweep looked at all {len(heap)}")
print(f"copying : copies the {len(marked)} live objects, never touches the "
f"{len(garbage)} dead ones")আসল আউটপুট (ব্রাউজারের Python):
RC freed at once: ['tmp', 'note'] | counts left on f, cell: 1 1
mark-sweep: marked 3, swept 4 ['cell', 'f', 'note', 'tmp'], sweep looked at all 7
copying : copies the 3 live objects, never touches the 4 dead ones
দুটি root ছাড়ার পরে RC সঙ্গে সঙ্গে tmp আর note ফেরত দেয়, কিন্তু closure f আর তার cell পরস্পরকে ধরে রাখে, গণনা 1-এই আটকে থাকে: cycle. Mark-sweep cycle-সহ চারটিই ঝাড়ে, কিন্তু sweep সাতটি ঘরই দেখে; copying শুধু তিনটি জীবিতকে ছোঁয়। পর্ব ৭৫-এর heap_demo.haat-এ একই ছবি বড় আকারে: ১১টি object-এর ৪টি RC সঙ্গে সঙ্গে ছাড়ে, cell ↔ closure cycle-এর ২টি থেকে যায়; mark-sweep ৫টি চিহ্ন দিয়ে ৬টি মোছে; Cheney শুধু ৫টি কপি করে।
| মাপকাঠি | Reference counting | Mark-sweep | Copying |
|---|---|---|---|
| কখন মুক্ত | সঙ্গে সঙ্গে | collection-এর সময় | collection-এর সময় |
| Cycle | ধরে না; weak বা cycle collector লাগে | ধরে | ধরে |
| কাজের মাপ | প্রতিটি pointer লেখায় গণনা | জীবিত + পুরো heap-এর sweep | শুধু জীবিত |
| Object সরে? | না | না, তাই fragmentation | হ্যাঁ; অর্ধেক heap খালি রাখতে হয় |
Generational আর barrier: বেশিরভাগ object অল্প বয়সে মরে, তাই young অংশ ঘন ঘন দেখা লাভজনক; কিন্তু পুরোনো object-এ নতুনের pointer লিখলে write barrier তা মনে না রাখলে জীবিত object মুছে যায়: পর্ব ৭৫-এ barrier ছাড়া pay(500) 450-এর বদলে মুছে ফেলা object-এ ঢোকে।
GC বনাম ownership: GC-তে লেখা সহজ, খরচ চলার সময়ে, আর মুক্তির মুহূর্ত অনির্দিষ্ট। Rust-এ প্রতিটি মানের একজন মালিক, move-এর পরে পুরোনো নাম অচল, আর ধার হয় যত খুশি &, নয়তো একটি &mut (aliasing XOR mutability). Borrow checker এসব compile-এর সময় প্রমাণ করে; মুক্তি নির্দিষ্ট মুহূর্তে, runtime খরচ প্রায় শূন্য, কিন্তু নিয়ম কড়া। Rust-এর Rc-ও reference counting, তাই cycle ভাঙতে Weak লাগে।
পরীক্ষক যা খোঁজেন: সংজ্ঞা আর root (২); ছক (৩); cycle-এর উদাহরণ (২); barrier (১); ownership-এর আপস (২)। পর্ব ৭৫ · পর্ব ৭৬
যেখানে নম্বর কাটে: “GC থাকলে memory leak হয় না” লেখা (পৌঁছানো যায় অথচ অদরকারি object থেকে যায়); “Rust-এ GC আছে” বা “Rust-এ memory ভুল অসম্ভব” লেখা (unsafe ব্লক ছাড়া, safe Rust-এ)।
৮ · অংশ ছ — Macro আর DSL (মডিউল ১৩)
রিভিশন: পর্ব ৭৮ (macro), পর্ব ৭৯ (DSL), আর C কোর্সের পর্ব ২৭ (preprocessor).
ছ-০১Macro আর function-এর পার্থক্য লিখুন। #define SQUARE(x) x * x দিয়ে 100 / SQUARE(2+3) কত, কেন? Hygienic macro কী? — ৫ নম্বর (সহজ–মাঝারি)
সংজ্ঞা: Macro compile-এর আগে বা সময়ে কোড বদলায়, argument পায় কোড হিসেবে, হিসাব না করে; function চলার সময় ডাকা হয়, argument একবার হিসাব হয়ে মান হিসেবে আসে। C preprocessor লেখা বা token বদলায়, গঠন চেনে না।
#include <stdio.h>
#define SQUARE(x) x * x /* text in, text out */
#define SQUARE2(x) ((x) * (x)) /* parenthesised, still text */
static int calls = 0;
static int next_id(void) { return ++calls; }
static inline int square(int x) { return x * x; } /* a real function */
int main(void) {
printf("100 / SQUARE(2+3) = %d\n", 100 / SQUARE(2+3));
printf("100 / SQUARE2(2+3) = %d\n", 100 / SQUARE2(2+3));
printf("100 / square(2+3) = %d\n", 100 / square(2+3));
calls = 0;
int m = SQUARE2(next_id());
printf("SQUARE2(next_id()) = %d, next_id ran %d times\n", m, calls);
calls = 0;
int f = square(next_id());
printf("square(next_id()) = %d, next_id ran %d times\n", f, calls);
return 0;
}আসল আউটপুট (Wandbox-এর C compiler):
100 / SQUARE(2+3) = 59
100 / SQUARE2(2+3) = 4
100 / square(2+3) = 4
SQUARE2(next_id()) = 2, next_id ran 2 times
square(next_id()) = 1, next_id ran 1 times
SQUARE(2+3) খুলে হয় 100 / 2+3*2+3 = 50 + 6 + 3 = 59. বন্ধনী দিলে 4 আসে, কিন্তু argument দুবার বসে বলে next_id দুবার চলে (double evaluation): 1 × 2 = 2. Function-এ argument একবার হিসাব হয়, ফল 1. পর্ব ৭৮-এ সত্যিকারের -E দিয়ে খোলা রূপটিও দেখানো।
Hygiene: hygienic expansion-এ macro-র বানানো নাম ব্যবহারকারীর নাম ধরে না, আর macro-র ব্যবহৃত বাইরের নাম সংজ্ঞার জায়গার অর্থই রাখে। gensym শুধু প্রথম দিক সারায়; পর্ব ৭৮-এর Haat expander প্রতিটি expansion-এ একটি চিহ্ন বসিয়ে দুটিই সারায়। Scheme আর Racket-এর hygienic macro দুই দিকই সামলায়; Rust-এর macro_rules!-এ hygiene আংশিক (mixed-site); C-র macro-তে hygiene নেই।
পরীক্ষক যা খোঁজেন: সংজ্ঞা (১); ৫৯ আর কারণ (২); double evaluation (১); hygiene (১)। পর্ব ৭৮
যেখানে নম্বর কাটে: উত্তর ৪ লেখা; বন্ধনী দিলেই সব সমস্যা মেটে বলা।
ছ-০২Internal আর external DSL-এর একটি করে সুবিধা আর অসুবিধা লিখুন। একটি DSL-কে অন্য ভাষায় অনুবাদ করার সময় কোন ভুলটি সবচেয়ে সহজে ঢোকে? — ৫ নম্বর (মাঝারি)
সংজ্ঞা: DSL এক কাজের ভাষা: SQL, regex, CSS, Make. External DSL-এর নিজের grammar আর parser; internal DSL একটি host ভাষার ভেতরে library হিসেবে বাঁচে (method chaining, operator overloading).
| মাপকাঠি | Internal | External |
|---|---|---|
| Parser আর tool | host-এর, বিনামূল্যে | নিজেকে লিখতে হয় |
| Syntax আর error | host-এর নিয়ম আর বার্তা | নিজের, ব্যবহারকারীর ভাষায় |
| নিরাপত্তা | host-এর পুরো ক্ষমতা হাতে | শুধু অনুমোদিত শব্দ |
উদাহরণ: পর্ব ৭৯-এর ছাড়লিপি (যদি মোট >= 1000 তাহলে ছাড় 10%) একটি external DSL, যার অর্থ দেওয়া হয়েছে Haat-এ অনুবাদ করে। সবচেয়ে সহজ ভুল precedence: অনুবাদ থেকে বন্ধনী সরালে ২০০টি এলোমেলো নিয়ম-ফাইলের ৯৬টিতে reference type error দেয়, আর ১৩টিতে চুপচাপ ভুল সংখ্যা। সমাধান: গাছ থেকে লেখার সময় প্রতিটি যৌগিক সন্তান বন্ধনীতে। ব্যবহারকারীর নিয়ম eval করা code injection-এর দরজা।
পরীক্ষক যা খোঁজেন: সংজ্ঞা আর উদাহরণ (১); ছক (২); অনুবাদের ফাঁদ (১); “নতুন ভাষা না বানানো”-র বিকল্প: library, টেবিল বা config (১)। পর্ব ৭৯
যেখানে নম্বর কাটে: internal DSL-কে “ভাষা নয়” বলা; DSL-কে Turing-complete হতেই হবে ভাবা।
৯ · তিন মিনিটে নতুনকে বোঝান — পাঁচটি আদর্শ উত্তর
“যিনি এই বিষয় পড়েননি, তাঁকে বোঝান”: দেখা হয় আপনি মূল কথা জানেন কি না, আর সরল করতে গিয়ে ভুল বলেন কি না। কাঠামো: উপমা → নিখুঁত মূল কথা → ছোট উদাহরণ → কোথায় উপমা ভাঙে।
ত-০১Python কেন সাধারণত C-র চেয়ে ধীর? (সহজ–মাঝারি)
উপমা: C যেন আগে থেকে বাংলায় অনুবাদ করা বই; CPython যেন একজন দোভাষী, যিনি প্রতিটি বাক্য পড়ার সময় আবার ভাবেন “এই শব্দটি কী ধরনের”।
মূল কথা: Clang C-কে আগে machine code-এ অনুবাদ করে, type জানা বলে a + b একটি নির্দেশ। CPython source-কে bytecode-এ নামায়, তারপর একটি loop প্রতিটি নির্দেশ বাছে; a + b-এ চলার সময় দেখতে হয় দুটি কী ধরনের মান, আর প্রতিটি সংখ্যা heap-এর একটি object.
উদাহরণ: CPython 3.11 থেকে interpreter গরম নির্দেশ বিশেষায়িত করে (BINARY_OP_MULTIPLY_INT), তাই ফাঁক কমেছে, মেটেনি।
সীমা: ধীরতা ভাষার নয়, বাস্তবায়নের: JIT-ওয়ালা বাস্তবায়ন আলাদা, আর NumPy-র ভারী কাজ চলে C-তে। কত গুণ ধীর, তা কাজভেদে আলাদা; শুধু নিজের যন্ত্রে মেপে বলুন। পর্ব ০৪ · পর্ব ৬০
ত-০২Closure আসলে কী? (সহজ)
উপমা: দোকান থেকে বের হওয়ার সময় হাতে দেওয়া একটি টোকেন, যেটি দোকানের নিজের খাতার পাতার সঙ্গে বাঁধা; যেখানেই যান, টোকেন দেখালে সেই খাতাই খোলে।
মূল কথা: Closure = function-এর কোড + জন্মস্থানের environment. Function পরে যেখানেই চলুক, বাইরের নাম খোঁজা হয় জন্মস্থানে, ডাকার জায়গায় নয়।
উদাহরণ: Haat-এ একটি counter function প্রতিবার ডাকে নিজের লুকানো count বাড়ায়; দুটি closure একই variable ধরলে দুজনেই একই বদল দেখে, কারণ Haat variable ধরে by reference (cell).
সীমা: ভাষাভেদে ধরা হয় variable বা মান: Python-এর [lambda: i for i in range(3)] ডাকলে সব 2, কারণ তিনটিই একই cell; C++-এ [=] কপি নেয়। পর্ব ১৭
ত-০৩Garbage collector কী করে? (সহজ)
উপমা: গুদামের দারোয়ান দেখেন কোন বাক্সে এখনো কোনো অর্ডারের স্লিপ লাগানো; কোনো স্লিপ যে বাক্সে পৌঁছায় না, সেটি খালি করে জায়গা ফেরত দেন।
মূল কথা: GC program-এর root (global, চলমান function-এর variable) থেকে pointer ধরে যা পাওয়া যায় তা রাখে; বাকিটা আর কখনো ব্যবহার হতে পারে না, তাই মুক্ত।
উদাহরণ: reference counting শুধু গোনে কতজন দেখায়; পরস্পরকে ধরে রাখা দুটি object-এর গণনা শূন্য হয় না, তাই সে ছাড়ে না; tracing GC ছাড়ে।
সীমা: “পৌঁছানো যায়” আর “দরকার” এক নয়: ভুলে রেখে দেওয়া বড় list GC ছাড়তে পারে না। পর্ব ৭৫
ত-০৪Rust compiler আমার কোড কেন বাতিল করে, অথচ C-তে চলে? (মাঝারি)
উপমা: লাইব্রেরির নিয়ম: একটি বই অনেকে একসঙ্গে পড়তে পারেন, কিন্তু কেউ দাগ দিতে চাইলে তখন বইটি শুধু তাঁর হাতে।
মূল কথা: Rust compile-এর সময় প্রমাণ চায় যে প্রতিটি মানের একজন মালিক, move-এর পরে পুরোনো নাম ব্যবহার হয়নি, আর একই সময়ে হয় অনেক পড়ুয়া (&), নয়তো একজন লেখক (&mut). C এগুলো যাচাই করে না; ভুল হলে undefined behavior.
উদাহরণ: একটি Vec move করে আবার পুরোনো নামে পড়লে E0382; C-তে free করা pointer আবার পড়লে compiler বড়জোর সতর্ক করে।
সীমা: checker রক্ষণশীল: কিছু নিরাপদ program-ও বাতিল হয় (NLL তার একটি অংশ মিটিয়েছে); আর unsafe ব্লকে প্রমাণের দায় প্রোগ্রামারের। পর্ব ৭৬
ত-০৫-O2 দিলে compiler কী বদলায়? (মাঝারি)
উপমা: রান্নার রেসিপি একই, শুধু অভিজ্ঞ রাঁধুনি কাজের ক্রম গুছিয়ে নেন, একই মশলা দুবার বাটেন না; খাবারের স্বাদ এক।
মূল কথা: Optimizer দেখা যায় এমন আচরণ (আউটপুট, error) রেখে কম কাজে পৌঁছায়: ধ্রুবক আগেই হিসাব, একই হিসাব একবার, অদরকারি কোড বাদ, ছোট function inline, loop-এর বাইরে সরানো।
উদাহরণ: পর্ব ৩২-এর সত্যিকারের Clang: -O0-তে callq settle, -O2-তে jmp settle (tail call), আর sum_to(10000000) -O0-তে stack overflow-এ মরে, -O2-তে চলে। পর্ব ৭৪-এ LTO-র পরে main সরাসরি 996 আর 5000 ছাপে।
সীমা: অর্থ রাখার প্রতিশ্রুতি শুধু নিয়ম-মানা program-এ: C-তে signed overflow undefined behavior, আর LLVM-এর nsw-ও একই প্রতিশ্রুতি; পর্ব ৬৮-এ Haat-এর অনুবাদে ভুল করে nsw দিলে -O2-তে x + 1 > x সবসময় true হয়ে গেছে। পর্ব ৬৫ · পর্ব ৬৬ · পর্ব ৩২
১০ · ভাইভা — কৌশল, ২৪টি প্রশ্ন, ফাঁদ, সৎ উত্তর আর AI
পরীক্ষক আপনার শেষ বাক্য থেকে পরের প্রশ্ন বানান; এই বিষয়ে প্রায় নিশ্চিত দুটি: “কোন ভাষায়, কোন version-এ?” আর “বাস্তবে কীভাবে বানানো হয়?” তাই প্রথম উত্তরেই ভাষা আর বাস্তবায়নের একটি ইঙ্গিত দিন।
“Tail call কী?” — “যে call-এর পরে ডাকা-পক্ষের আর কোনো কাজ নেই, শুধু ফল ফেরত দেওয়া (কী)। Scheme-এ তার জন্য নতুন frame না খোলা বাধ্যতামূলক, C-তে শুধু optimization, CPython-এ নেই (কোন ভাষায়)। পর্ব ৩২-এর Clang -O2-তে call-এর জায়গায় jmp দেখা যায় (বাস্তবায়ন)।”
| পরীক্ষক | |
| প্রার্থী (মূল কথা) | |
| কেন ভালো উত্তর | |
| জোড়া পর্ব |
- শুরু। সংজ্ঞা আর একটি শব্দ, “জন্মস্থান”; পুরো ইতিহাস নয়।
- ভাষা ধরে। Python-এর আচরণ, কারণ (একই cell) আর প্রচলিত সমাধান।
- বাস্তবায়ন। পরীক্ষক এখন দেখেন আপনি runtime জানেন কি না।
- পরের স্তর। heap-এ গেলে মুক্তির প্রশ্ন আসবেই।
- সীমা। RC-এর দুর্বলতা আর প্রতিকার, এক বাক্যে।
- শেষ। বিকল্প পথ আর তার দাম: কড়া নিয়ম।
২৪টি ছোট প্রশ্ন — মুখে বলার উত্তর আর পরের প্রশ্ন
জোরে উত্তর বলুন, তারপর প্রশ্নে চেপে মেলান; প্রতিটিতে ৩০ সেকেন্ডের বেশি নয়। “পরের প্রশ্ন”-এর উত্তরও মুখে বলুন।
ভিত্তি আর অনুবাদক (পর্ব ০১–০৬)
ভ-০১Front end, middle end আর back end কেন আলাদা? (সহজ)
ভ-০২-7 / 2 C আর Python-এ কত? (সহজ)
ভ-০৩Bootstrapping কী? (মাঝারি)
একটি ভাষার compiler সেই ভাষাতেই লেখা (self-hosting), আর প্রথমবার চালাতে অন্য কোনো compiler বা পুরোনো version দিয়ে compile করা; T-diagram দিয়ে আঁকা হয়। পর্ব ০৪
পরের প্রশ্ন: এতে নিরাপত্তার প্রশ্ন? — Ken Thompson (১৯৮৪): compiler-এর binary-তে লুকানো বদল source পড়ে ধরা যায় না; তাই compiler-কেও বিশ্বাসের ভিত্তি ধরে যাচাই করতে হয়।
ভ-০৪Cross-compiler কী? (সহজ)
নাম, data আর subprogram (পর্ব ১৪–৩২)
ভ-০৫Binding time-এর ধাপগুলো বলুন। (সহজ)
ভাষা নকশা, বাস্তবায়ন, compile, link, load আর run time. যেমন +-এর অর্থ নকশায়, C-র int-এর আকার বাস্তবায়নে, local-এর slot compile-এ, চলকের মান run time-এ। পর্ব ১৪
পরের প্রশ্ন: Static আর dynamic binding? — চালানোর আগে তৈরি হয়ে না বদলালে static; চলার সময় তৈরি হলে বা বদলালে dynamic.
ভ-০৬Activation record-এ কী কী থাকে? (সহজ)
Parameter, local, temporary, ফেরার ঠিকানা, dynamic link (caller-এর frame), প্রয়োজনে static link (লেখার দিক থেকে ঘিরে থাকা function-এর frame), আর সংরক্ষিত register. পর্ব ৩০
পরের প্রশ্ন: k স্তর বাইরের variable পেতে? — static chain-এ k ধাপ; display থাকলে এক ধাপ।
ভ-০৭Termination আর resumption exception model? (মাঝারি)
Termination-এ handler-এর পরে ছোড়ার জায়গায় আর ফেরা হয় না, stack unwinding হয়; resumption-এ ফেরা যায়। মূলধারার প্রায় সব ভাষা termination. পর্ব ২৮
পরের প্রশ্ন: try-তে return 1, finally-তে return 2? — Java, JavaScript আর Python-এ 2; finally আগের ফল মুছে দেয়।
ভ-০৮Tail call optimization কী? (মাঝারি)
Tail call-এ নতুন frame না খুলে বর্তমান frame-এ argument বসিয়ে লাফ; tail recursion তখন loop, stack O(1). return f(x) tail call, return 1 + f(x) নয়। পর্ব ৩২
পরের প্রশ্ন: Python-এ? — CPython TCO করে না; loop, explicit stack বা trampoline.
Type আর semantics (পর্ব ৩৩–৪৪)
ভ-০৯Type checking আর type inference-এর পার্থক্য? (সহজ)
Checking-এ type লেখা থাকে, শুধু যাচাই; inference-এ অজানা জায়গায় type variable বসে, সমীকরণ জমে, unification তা মেটায় (Hindley–Milner). পর্ব ৩৫
পরের প্রশ্ন: Occurs check কেন? — t ≐ (t) → u ধরনের সমীকরণে অসীম type ঠেকাতে, যেমন λx. x x-এ।
ভ-১০Progress আর preservation এক লাইনে? (মাঝারি)
Progress: well-typed term হয় value, নয় আরেক ধাপ চলতে পারে। Preservation: এক ধাপ চললেও type একই থাকে। দুটি মিলে type soundness. পর্ব ৩৮
পরের প্রশ্ন: তাহলে sound ভাষায় runtime error কেন? — শূন্য দিয়ে ভাগের মতো ঘোষিত error stuck অবস্থা নয়; soundness শুধু stuck বাদ দেয়।
ভ-১১Stuck, runtime error আর divergence আলাদা কেন? (মাঝারি)
Stuck: শেষ অবস্থা নয় অথচ কোনো নিয়ম খাটে না (true + 1); runtime error: semantics-এ ঘোষিত শেষ (E-DivZero); divergence: অসীম ধাপ (while true). পর্ব ৪০
পরের প্রশ্ন: Big-step এদের আলাদা করতে পারে? — না, stuck আর divergence দুটিতেই “কোনো derivation গাছ নেই”।
ভ-১২Curry–Howard এক লাইনে? (কঠিন)
Front end, interpreter আর VM (পর্ব ৪৫–৬১)
ভ-১৩a<=b-তে কয়টি token? (সহজ)
তিনটি: IDENT, <=, IDENT. Maximal munch: দুই অক্ষরের operator আগে দেখা হয়। পর্ব ৪৬
পরের প্রশ্ন: Token, lexeme, pattern? — Pattern নিয়ম ([0-9]+), lexeme আসল টুকরো (1000), token শ্রেণি আর সঙ্গের তথ্য (INT, অবস্থান)।
ভ-১৪Dangling else কী, Haat কীভাবে এড়ায়? (সহজ)
if a if b s1 else s2-এ else কোন if-এর, grammar বলে না। Haat, Rust আর Go block বাধ্যতামূলক করে এড়ায়; C আর Java নিয়ম দেয় “সবচেয়ে কাছের জোড়াহীন if”. পর্ব ৪৭
পরের প্রশ্ন: LR parser-এ এটি কী হিসেবে আসে? — shift-reduce conflict; সাধারণত shift বেছে সমাধান।
ভ-১৫Haat-এ দুটি top-level function পরস্পরকে ডাকতে পারে, nested function পারে না। কেন? (মাঝারি)
Resolver দুই pass-এ চলে: top-level function আগে নিবন্ধিত হয় (hoisting, নকশা-সিদ্ধান্ত ১৭), বাকি সব লেখার ক্রমে। Nested function শুধু ঘোষণা থেকে দৃশ্যমান। পর্ব ৫১
পরের প্রশ্ন: এক-pass compiler-এ? — C-র মতো forward declaration বা prototype লাগে।
ভ-১৬Deoptimization আর OSR কী? (কঠিন)
Deopt: JIT-এর অনুমানের guard ভাঙলে interpreter-এর সমান অবস্থা (ip, slot, stack) গড়ে সেখানে ফেরা। OSR: চলমান loop-কে মাঝপথে compile-করা কোডে সরানো। পর্ব ৬১-এর খেলনা JIT-এ price ৫০তম ডাকে compile, ৩০১তম ডাকে deopt, ৩৫১তম ডাকে আবার compile. পর্ব ৬১
পরের প্রশ্ন: OSR না থাকলে? — একবার ডাকা দীর্ঘ loop কখনো দ্রুত হয় না।
IR, optimization, back end আর runtime (পর্ব ৬২–৭৫)
ভ-১৭Liveness কেন backward analysis? (মাঝারি)
প্রশ্নটি ভবিষ্যৎ নিয়ে: “এই মান পরে পড়া হবে কি?” তাই তথ্য আসে successor থেকে; meet ∪. Reaching definitions সামনের দিকে। পর্ব ৬৪
পরের প্রশ্ন: Iterative algorithm থামে কেন? — Lattice-এর উচ্চতা সসীম আর transfer function monotone.
ভ-১৮Haat-এ x * 0 → 0 বৈধ, কিন্তু x / x → 1 নয়। কেন? (মাঝারি)
x = 0 হলে x / x runtime error division by zero দেয়, যা দেখা যায় এমন আচরণ; বদলালে তা হারায়। x * 0 wrap-সহ সবসময় 0. পর্ব ৬৫-এ জেনেশুনে বসানো x / x → 1 ৪৫টি program-এ খাটে, কিন্তু ধরা পড়ে মাত্র ১০টিতে। পর্ব ৬৫
পরের প্রশ্ন: C-তে Clang p * 5 / 100-কে p / 20 করে, Haat-এ কেন নয়? — C-তে signed overflow UB, Haat-এ wrap; wrap-এ দুটি সমান নয়।
ভ-১৯Caller-saved আর callee-saved register? (সহজ)
Caller-saved ডাকা function নষ্ট করতে পারে, দরকার হলে caller রাখে; callee-saved ব্যবহার করলে callee নিজে রেখে ফিরিয়ে দেয়। RISC-V psABI-তে s0–s11 আর sp callee-saved. পর্ব ৭১
পরের প্রশ্ন: RISC-V-এ ৯ম integer argument? — callee-তে ঢোকার মুহূর্তে 0(sp)-তে।
ভ-২০“undefined reference” কোন ধাপের error? (সহজ)
Linker-এর symbol resolution-এর: একটি U (undefined) নামের কোনো সংজ্ঞা কোনো object file বা library-তে পাওয়া যায়নি। “multiple definition”-ও linker-এর। পর্ব ৭৪
পরের প্রশ্ন: Relocation কী? — (offset, type, symbol, addend): পরে ঠিকানা বসানোর নির্দেশ; PC-relative-এ S + A − P.
আধুনিক ভাষা আর tool (পর্ব ৭৬–৮১)
ভ-২১NLL কী বদলেছে? (মাঝারি)
Non-lexical lifetimes: ধার শেষ হয় reference-এর শেষ ব্যবহারে, block-এর শেষে নয়; তাই আগে বাতিল কিছু নিরাপদ program এখন গৃহীত। Borrow checker আসলে একটি dataflow analysis. পর্ব ৭৬
পরের প্রশ্ন: Lifetime annotation 'a কি মানের জীবন বাড়ায়? — না; শুধু argument আর ফলের ধারের সম্পর্ক লেখে।
ভ-২২Data race আর DRF-SC কী? (কঠিন)
Happens-before-এ ক্রমহীন দুটি সংঘাতপূর্ণ ছোঁয়া (একটি অন্তত লেখা) data race. DRF-SC: race না থাকলে program sequential consistency-র মতো আচরণ করে (C++, Java, Go). C/C++-এ race UB; safe Rust-এ Send/Sync দিয়ে compile error. পর্ব ৭৭
পরের প্রশ্ন: বাস্তব যন্ত্র কি SC? — না; পর্ব ৭৭-এ memory_order_relaxed-এ store buffering-এর r1 = r2 = 0 সত্যিকারের run-এ ঘটেছে।
ভ-২৩Language Server Protocol কোন সমস্যা মেটায়? (সহজ)
M টি editor আর N টি ভাষার জন্য M × N plugin-এর বদলে M + N বাস্তবায়ন: editor আর language server JSON-RPC বার্তায় কথা বলে। পর্ব ৮০
পরের প্রশ্ন: অবস্থান গোনার ফাঁদ? — LSP-র column ০ থেকে, ডিফল্টে UTF-16 unit; Haat-এর ১ থেকে, code point ধরে।
ভ-২৪Formatter-এর সঠিকতা কীভাবে পরীক্ষা করবেন? (মাঝারি)
সাধারণ ফাঁদ — যেসব কথায় নম্বর কাটে
| ফাঁদের কথা | কেন ভুল | ঠিক কথা |
|---|---|---|
| “Java interpreted ভাষা” | ভাষা নয়, বাস্তবায়ন | javac bytecode বানায়; JVM interpret ও JIT করে |
| “Java-তে object by reference যায়” | caller-এর variable সরানো যায় না | সবসময় by value; object-এ reference-এর মান (sharing) |
| “Dynamic scope মানে dynamic typing” | দুটি আলাদা অক্ষ | scope নাম খোঁজার নিয়ম, typing যাচাইয়ের সময় |
| “Type inference মানে type নেই” | inference static | compiler type বের করে স্থির রাখে |
| “Optimization সব ক্ষেত্রে অর্থ রাখে” | UB-ওয়ালা program-এ প্রতিশ্রুতি নেই | নিয়ম-মানা program-এ রাখে; C-তে signed overflow UB |
| “Reference counting সব garbage ধরে” | cycle | weak reference বা cycle collector লাগে |
| “Macro মানে দ্রুত function” | argument কোড হিসেবে বসে | precedence আর double evaluation-এর ফাঁদ |
না জানলে — সৎভাবে উত্তর
আংশিক জানলে বলুন “V8-এর স্তরগুলোর নাম মনে আছে, কিন্তু কোন শর্তে deopt হয় তার পুরো তালিকা জানি না; মূল ধারণা হলো guard ভাঙলে interpreter-এ ফেরা।” কোনো ভাষার নিয়ম নিশ্চিত না হলে বলুন “কোন version-এ, তা যাচাই না করে বলব না।” সংখ্যা ভুলে গেলে ছোট উদাহরণে বের করুন: p - p / 10-এর stack code লিখে গুনলে পাঁচটি নির্দেশ। ভুল ধরা পড়লে বলুন “আগে যা বলেছি, তা ভুল; ঠিক হলো …”। flag, সাল বা benchmark-এর সংখ্যা বানাবেন না।
AI-এর যুগে — AI-কে কড়া পরীক্ষক বানান
AI সহকারী প্রশ্ন বানাতে আর উত্তর মেলাতে কাজে লাগে, কিন্তু এই বিষয়ে প্রায়ই আত্মবিশ্বাসী অথচ ভুল: এক ভাষার নিয়ম সব ভাষায় চাপানো, evaluation order বা undefined behavior-এর একটি ফলকে নিশ্চিত বলা, precedence বা associativity-ভুল parser, বানানো compiler flag বা LLVM pass, আসল compiler-এর সঙ্গে না মেলা bytecode বা assembly, অর্থ বদলে দেওয়া “optimization”, আর GC বা memory model-এর ভুল নিশ্চয়তা। তাই তাকে পরীক্ষক বানান, আর প্রতিটি দাবি আসল compiler বা interpreter আর তার version-এ চালিয়ে, ভাষার specification-এ মিলিয়ে, edge case আর দুই বাস্তবায়নের differential test দিয়ে, আর -S, -emit-llvm, dis বা javap-এর আসল আউটপুট পড়ে যাচাই করুন।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএকটি compiler-এর ধাপগুলো source থেকে শুরু করে ক্রমে সাজান (▲▼ চেপে সরান)
- Lexical analysis (token)
- Syntax analysis (AST)
- Name resolution (symbol table)
- Type checking
- IR তৈরি আর optimization
- Code generation
(সহজ) g = 2; function f(x)-এর দেহ x = x + 1; g = g * 10; x = x * 2;; ডাক f(g). Call by value-result-এ শেষে g কত?
- 20
- 60
- 6
- 2
(সহজ) let rate = 5; fn discount(t: Int) -> Int { return t * rate / 100; } fn festival(t: Int) -> Int { let rate = 20; return discount(t); }. Dynamic scope-এর নিয়মে festival(1000) কত?
- 50
- 200
- 250
- undefined variable error
(মাঝারি) Haat-এ prefix --এর binding power 70, *-এর 60. -a * b-এর AST কোনটি?
- (- (* a b))
- (* (- a) b)
- (- a (* a b))
- syntax error
(মাঝারি) C-তে #define SQUARE(x) x * x থাকলে 100 / SQUARE(2+3)-এর মান কত?
- 4
- 25
- 59
- 20
(মাঝারি) একটি closure আর তার cell পরস্পরকে দেখায়, আর কোনো root থেকে এদের কাছে পৌঁছানো যায় না। কোন কথাটি ঠিক?
- Reference counting দুটিকে সঙ্গে সঙ্গে মুক্ত করে
- Mark-sweep cycle বলে দুটিকে রেখে দেয়
- Copying collector দুটিকে নতুন জায়গায় কপি করে
- RC ছাড়ে না, mark-sweep ছাড়ে
(কঠিন) Interference graph একটি চার-node বৃত্ত a–b, b–c, c–d, d–a; register k = 2. Briggs-এর optimistic colouring-এ কয়টি spill?
- ০
- ১
- ২
- দুই রঙে অসম্ভব, তাই allocation ব্যর্থ
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব শব্দ এখানে একসাথে:
মনে রাখুন
- কাঠামোই নম্বর: সংজ্ঞা → একই সারির ছক → চালানো উদাহরণ → কখন কোনটি → সীমা।
- ভাষা নয়, বাস্তবায়ন: compiled বা interpreted হয় বাস্তবায়ন; CPython আর JVM দুটিই hybrid.
- ভাষা আর version বলুন:
-7 / 2C-তে -3, Python-এর//-এ -4; Java সবসময় by value. - সংখ্যা চালিয়ে মেলান: g-এর 20, 60, 6, 60; scope-এর 50 বনাম 200; macro-র 59; Briggs-এর শূন্য spill.
- আপস নাম ধরে: monomorphization বনাম erasure, RC বনাম tracing, GC বনাম ownership: প্রতিটিতে কী পাওয়া যায় আর কী দিতে হয়।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৮৫ · Type derivation আর semantics-এর অনুশীলন — typing rule, inference আর Hoare logicপরবর্তী পর্বTyping derivation, unification, semantics-এর derivation আর Hoare logic-এর প্রমাণ, ধাপে ধাপে।
- প্রোগ্রামিং ভাষা ও কম্পাইলার · কোর্স হোম৮৬টি পর্বপুরো কোর্সের মানচিত্র আর Haat প্রজেক্টের পথ।
- পর্ব ০৪ · অনুবাদক — compiler, interpreter, transpiler আর JITরিভিশনক-০১-এর সংজ্ঞা, hybrid ব্যবস্থা আর bootstrapping.
- পর্ব ২৯ · Parameter passing — by value, by reference, by sharing আর by nameরিভিশনখ-০২-এর simulator আর aliasing-এর সত্যিকারের run.
- পর্ব ৩৭ · Generics-এর বাস্তবায়ন — erasure, monomorphization আর dictionary passingরিভিশনগ-০৩-এর Clang আর javap-এর আসল আউটপুট।
- গণনার তত্ত্ব · পর্ব ৮৩ · লিখিত ও মৌখিক (ভাইভা) প্রশ্নপাশের ট্র্যাকAutomaton, grammar আর parsing-এর তত্ত্বের তুলনা-প্রশ্ন; এই কোর্সের front end-এর ভিত্তি।
- DSA · পর্ব ৭০ · লিখিত ও মৌখিক (ভাইভা) প্রশ্নপাশের ট্র্যাকGraph colouring, hash table আর complexity-র প্রশ্ন algorithm-এর দিক থেকে।