এই পর্বে যা করবেন
- বাদ দেওয়ার পদ্ধতিতে উত্তর বের করা, আর প্রতিটি distractor-এর পেছনের ভুল ধারণা চেনা
- একটি Haat, C, Python বা JavaScript program পড়ে আউটপুট বা error-এর বার্তা আর অবস্থান বলা
- Scope, closure, parameter passing আর evaluation order-এর প্রশ্নে “ভাষা আর version কোনটি” আগে জিজ্ঞেস করা
- Token, AST, bytecode, three-address code, liveness আর φ-এর ছোট হিসাব দ্রুত করা
- Optimization কোন ভাষায় বৈধ আর কোনটিতে নয়, তা undefined behavior আর runtime error দেখে ঠিক করা
- ঘড়ি ধরে মিশ্র মহড়া দিয়ে নিজের প্রস্তুতি মাপা আর দুর্বল মডিউলে ফেরা
১ · কীভাবে অনুশীলন করবেন — প্রশ্নের ধরন, বাদ দেওয়া আর সময়
এই পাতা বিশ্ববিদ্যালয়ের Programming Languages বা Compiler Design কোর্সের পরীক্ষা, IT ও প্রোগ্রামার পদের লিখিত পরীক্ষা, software ইন্টারভিউ আর নিজে শেখার ঝালাইয়ের জন্য। এই বিষয়ের MCQ-তে নম্বর সবচেয়ে বেশি হারায় তিন জায়গায়: এক ভাষার নিয়ম সব ভাষায় চাপানো (“−7 / 2 সবখানে −4”), হিসাবের ক্রম ভুলে যাওয়া (কোন operand আগে, কোন ডাক আগে), আর “অব্যবহৃত, তাই মুছে ফেলা যায়” ধরনের ঢিলে যুক্তি।
প্রশ্নের চার ছাঁচ
| ধরন | উদাহরণ | কৌশল |
|---|---|---|
| ধারণা | Compiler বনাম interpreter, sound checker, DRF-SC | সংজ্ঞার প্রতিটি শব্দ মেলান |
| যুক্তি | কোন optimization বৈধ, কোন subtype সঠিক | প্রতিটি অপশনে একটি counterexample খুঁজুন |
| Program পড়া | Haat-এর আউটপুট, error-এর অবস্থান, JS-এর ক্রম | খাতায় state আর stack লিখে ধাপে ধাপে চালান |
| হিসাব | Token গোনা, struct-এর আকার, liveness, relocation | নিয়ম লিখে, তারপর ছোট উদাহরণে মিলিয়ে দেখুন |
কোন মডিউলে কতটি প্রশ্ন
Questions per module, roughly in proportion to the number of lessons; 10 more in the mixed mock
কৌশল ১ · বাদ দেওয়ার পদ্ধতি — একটি Haat আউটপুটের প্রশ্ন ধাপে ধাপে
“কী ছাপবে” ধরনের প্রশ্নে প্রতিটি ভুল অপশন সাধারণত একটি ভুল মডেল থেকে আসে: উল্টো মূল্যায়নের ক্রম, closure-কে মানের কপি ভাবা, বা error-এর আশঙ্কা। প্রতিটি মডেলকে আলাদা করে পরীক্ষা করে কাটুন।
- প্রশ্ন
কী ছাপবে?চারটি অপশন - check
ঘ বাদtype ঠিক - closure
গ বাদvariable ভাগ - ক্রম
খ বাদবাঁ থেকে ডান - উত্তর
32run আর vm
var stock = 5;
let take = fn(n: Int) -> Int {
stock = stock - n;
return stock; };
print(take(2) * 10 + take(1));
ক) 32 খ) 24
গ) 34 ঘ) check error
stock একটি var: লেখা বৈধ take : (Int) -> Int take(2) * 10 + take(1) : Int print Int নেয় → check ok
ভুল মডেল: প্রতি ডাকে 5 থেকে take(2) = 3, take(1) = 4 3 * 10 + 4 = 34 আসলে stock একটিই: দ্বিতীয় ডাক দেখে 3
ভুল মডেল: ডান আগে take(1) = 4, take(2) = 2 2 * 10 + 4 = 24 Haat: বাঁ operand আগে (README সিদ্ধান্ত ১২)
take(2): stock 5 → 3 3 * 10 = 30 take(1): stock 3 → 2 30 + 2 = 32 run: 32, vm: 32
- আগে প্রশ্নটি নিজের ভাষায় বলুন। একটি ভাগ করা variable, দুটি ডাক, আর একটি expression-এ দুই ডাকের ফল জোড়া। উত্তর নির্ভর করে দুটি প্রশ্নে: ডাক কোন ক্রমে, আর দ্বিতীয় ডাক কোন stock দেখে।
- Error-এর অপশন আগে যাচাই করুন। stock একটি
var, তাই closure থেকে লেখা বৈধ; সব type Int, আর print Int নেয়। reference-এর check বলে ok; ঘ বাদ। - Closure-এর মডেল কাটুন। Closure variable ধরে, মানের কপি নয়। তাই দ্বিতীয় ডাক প্রথম ডাকের বদলানো stock দেখে; প্রতিবার 5 ধরলে 34 আসত, তাই গ বাদ।
- ক্রমের মডেল কাটুন। Haat-এ বাঁ operand আগে হিসাব হয় (reference README-এর সিদ্ধান্ত ১২)। ডান আগে হলে 24 আসত; খ বাদ।
- উত্তর আর যাচাই। take(2) দেয় 3, গুণে 30, তারপর take(1) দেয় 2, যোগে 32. reference-এর
runআরvmদুটিই 32 ছাপে; নিচের block তিনটি মডেলের ফল পাশাপাশি দেখায়।
প্রথমবার চালালে ব্রাউজারে Python নামতে কয়েক সেকেন্ড লাগতে পারে; এই পাতার সব Python block শুধু standard library ব্যবহার করে।
from fractions import Fraction as F
def run(order, by_copy=False):
stock = 5
def take(n):
nonlocal stock
if by_copy: # ভুল মডেল: প্রতি ডাকে তৈরির সময়ের 5 থেকে
return 5 - n
stock = stock - n # সঠিক: একটিই ভাগ করা stock
return stock
if order == "বাঁ→ডান":
a = take(2); b = take(1)
else: # ডান operand আগে
b = take(1); a = take(2)
return a * 10 + b
print("বাঁ→ডান, ভাগ করা stock:", run("বাঁ→ডান"))
print("ডান→বাঁ, ভাগ করা stock:", run("ডান→বাঁ"))
print("বাঁ→ডান, কপি-করা stock:", run("বাঁ→ডান", by_copy=True))
# negative marking: ঠিক +1, ভুল −1/4, চারটি অপশন
for cut in range(3):
k = 4 - cut
ev = F(1, k) - F(k - 1, k) * F(1, 4)
print(f"{cut}টি বাদ দিয়ে আন্দাজ: প্রত্যাশিত নম্বর {ev} ≈ {float(ev):.3f}")আসল আউটপুট:
বাঁ→ডান, ভাগ করা stock: 32
ডান→বাঁ, ভাগ করা stock: 24
বাঁ→ডান, কপি-করা stock: 34
0টি বাদ দিয়ে আন্দাজ: প্রত্যাশিত নম্বর 1/16 ≈ 0.062
1টি বাদ দিয়ে আন্দাজ: প্রত্যাশিত নম্বর 1/6 ≈ 0.167
2টি বাদ দিয়ে আন্দাজ: প্রত্যাশিত নম্বর 3/8 ≈ 0.375
তিনটি মডেল তিনটি আলাদা অপশন দেয়: সঠিক মডেলে 32, উল্টো ক্রমে 24, কপি-করা stock-এ 34. প্রতিটি distractor তাই একটি নির্দিষ্ট ভুল ধারণার ছাপ। শেষ তিন লাইন negative marking-এর হিসাব: ঠিক হলে +১ আর ভুলে −০.২৫ ধরলে অন্ধ আন্দাজের প্রত্যাশিত লাভ মাত্র ১/১৬, একটি অপশন নিশ্চিত কাটলে ১/৬, দুটি কাটলে ৩/৮. কত কাটে বা আদৌ কাটে কি না, তা পরীক্ষাভেদে আলাদা; নিজের পরীক্ষার নিয়ম দেখে নিন।
কৌশল ২ · প্রথমে ভাষা আর version, তারপর সময় ভাগ
প্রশ্নে কোন ভাষা আর কোন version, তা আগে চিহ্নিত করুন: একই -7 / 2 C-তে −3, Python-এর //-এ −4; একই overflow C-তে undefined behavior, Java আর Haat-এ wrap. প্রথম দফায় ধারণা আর যুক্তির প্রশ্ন, দ্বিতীয় দফায় program পড়া আর হিসাব, খাতায় প্রতিটি state লিখে।
দশটি বড় ফাঁদ
| ফাঁদ | ভুল ধারণা | সঠিক কথা |
|---|---|---|
| ভাগ আর ভাগশেষ | “−7 / 2 সব ভাষায় −4” | C আর Haat শূন্যের দিকে কাটে (−3), Python-এর // নিচের দিকে (পর্ব ০৩) |
| Overflow | “সব ভাষায় wrap করে” | C-তে signed overflow undefined behavior; Java আর Haat-এ wrap; Python-এ overflow নেই (পর্ব ০৬) |
| Closure | “তৈরির সময়ের মান কপি হয়” | Haat, Python, JavaScript variable ধরে; C++-এর [=] কপি নেয় (পর্ব ১৭) |
| হিসাবের ক্রম | “ক্রমে কিছু যায় আসে না” | Haat আর Java বাঁ থেকে ডানে; C-তে একই variable-এ দুটি unsequenced side effect undefined behavior (পর্ব ২৬) |
| Function subtype | “parameter-ও covariant” | Parameter contravariant, ফল covariant (পর্ব ৩৬) |
| Missing return | “while true-এ return থাকলেই হলো” | Haat-এর নিয়ম syntactic: while কখনো গোনা হয় না (পর্ব ৫২) |
| Dead code | “ফল অব্যবহৃত, তাই মুছে ফেলা যায়” | x / y runtime error দিতে পারে, তাই থাকে (পর্ব ৬৫) |
| Liveness | “forward বিশ্লেষণ” | Backward, মিলনে ∪ (পর্ব ৬৪) |
| Reference counting | “সব আবর্জনা সঙ্গে সঙ্গে মোছে” | চক্রে আটকে থাকা object কখনো ০-তে নামে না (পর্ব ৭৫) |
| Move | “move-এর পরে পুরোনো নামও চলে” | Rust-এ compile error E0382 (পর্ব ৭৬) |
এই পাতার প্রশ্নগুলো সম্পর্কে: প্রশ্নগুলো এই কোর্সের পর্বগুলো থেকে নতুন করে লেখা, এ ধরনের প্রশ্ন প্রায়ই আসে এমন ধারণা থেকে। কোনোটিই কোনো নির্দিষ্ট পরীক্ষা, বিশ্ববিদ্যালয় বা প্রতিষ্ঠানের আসল প্রশ্ন নয়। Haat এই কোর্সের শেখার ভাষা, আর “বাজারঘর” একটি কাল্পনিক অনলাইন দোকান।
২ · মডিউল ১ ও ২ — ভিত্তি আর programming paradigm (১১টি প্রশ্ন)
মডিউল ১ — ভিত্তি (৫টি প্রশ্ন)
(সহজ) Haat-এর এক লাইনের program print(true + 1); চালাতে দিলে কোন ধাপ থামায়?
- Lexer, কারণ true আর 1 একসঙ্গে জোড়া যায় না
- Parser, কারণ এটি syntax error
- Type checker (semantic analysis), চালানোর আগেই
- Interpreter, চলার সময়
(সহজ) Compiler আর interpreter-এর মৌলিক পার্থক্য কোনটি?
- Compiler অনুবাদ করে, interpreter কোনো অনুবাদই করে না
- Compiler input না দেখে নতুন program বানায়; interpreter program আর input নিয়ে আউটপুট দেয়
- Compiled ভাষা আর interpreted ভাষা দুটি আলাদা শ্রেণি, বাস্তবায়ন যাই হোক
- Compiler সবসময় machine code বানায়
(মাঝারি) ৬টি source ভাষা আর ৩টি লক্ষ্য-যন্ত্রের জন্য compiler বানাতে হবে। মাঝখানে একটি সাধারণ IR রাখলে কয়টি অনুবাদ-অংশ (front end আর back end মিলে) লাগে, আর না রাখলে কয়টি পূর্ণ compiler?
- IR সহ ৯টি, IR ছাড়া ১৮টি
- IR সহ ১৮টি, IR ছাড়া ৯টি
- IR সহ ৬টি, IR ছাড়া ১৮টি
- দুই ক্ষেত্রেই ৯টি
(মাঝারি) একটি transpiler Haat-এর a % b-কে (Haat-এ ভাগশেষ ভাজ্যের চিহ্ন নেয়, C-র মতো) সরাসরি Python 3-এর a % b-এ অনুবাদ করে। কোন input-এ দুই ফল আলাদা?
- a = 7, b = 2
- a = −7, b = 2
- a = 8, b = −2
- a = 6, b = 3
(মাঝারি) কোন জোড়ায় দুই ভাষাতেই নিজ নিজ পূর্ণসংখ্যা type-এর (Java 21-এর int, Haat-এর Int, C17-এর int) signed overflow-এর ফল ভাষার নিয়মেই নির্দিষ্ট, wrap করে?
- C17 আর Java 21
- C17 আর Haat
- Python 3 আর Haat
- Java 21 আর Haat
মডিউল ২ — programming paradigm (৬টি প্রশ্ন)
(সহজ) Haat program: var a = 4; var b = 9; a = a + b; b = a - b; a = a - b; print(a - b); কী ছাপবে?
- 5
- -5
- 13
- 0
(মাঝারি) C++-এ একটি virtual function-এর ডাক (object-এর আসল type compile-এর সময় অজানা) সাধারণত কোন যন্ত্র-কাজে নামে?
- Function-এর নামে একটি সরাসরি call
- চলার সময় method-এর নাম দিয়ে একটি hash table খোঁজা
- Object থেকে vptr, vtable থেকে function-এর ঠিকানা, তারপর পরোক্ষ call
- Argument-এর static type দেখে compile-এর সময় বাছাই
(মাঝারি) তালিকা [2, 3, 4]-এ শুরু 0 নিয়ে foldl (a, x) ↦ a − x আর foldr (x, a) ↦ x − a-এর ফল যথাক্রমে কত?
- −9 আর −9
- −9 আর 3
- −9 আর −5
- 9 আর 9
(মাঝারি) Prolog-ধাঁচের term q(f(X), Y, b) আর q(Z, g(Z), W)-এর most general unifier কোনটি?
- {Z/f(X), Y/g(X), W/b}
- Occurs check-এ ব্যর্থ, কোনো unifier নেই
- {Y/g(f(X)), W/b}
- {Z/f(X), Y/g(f(X)), W/b}
(মাঝারি) দুটি thread একটি ভাগ করা count-এ (শুরু 0) একবার করে কাজ করে: প্রথমে পড়া, তারপর পড়া মান + 1 লেখা (দুটি অবিভাজ্য ধাপ)। প্রতিটি thread-এর নিজের ধাপের ক্রম ঠিক রেখে সম্ভাব্য interleaving কয়টি, আর কয়টিতে শেষে count = 2?
- ২৪টি, যার ২টিতে 2
- ৬টি, সবগুলোতে 2
- ৬টি, যার ২টিতে 2
- ৬টি, যার ৪টিতে 2
(মাঝারি) Python 3.14-এ fs = [lambda: i + 1 for i in range(4)] লিখে print([f() for f in fs]) চালালে কী ছাপা হয়?
- [4, 4, 4, 4]
- [1, 2, 3, 4]
- [5, 5, 5, 5]
- NameError, কারণ i comprehension-এর বাইরে নেই
সব প্রশ্ন শেষ হলে নিচের block-এ ওপরের হিসাবগুলো মিলিয়ে নিন।
from itertools import permutations
def c_mod(a, b): # Haat আর C: ভাগফল শূন্যের দিকে কাটে
q = abs(a) // abs(b) * (1 if (a < 0) == (b < 0) else -1)
return a - b * q
for a, b in [(7, 2), (-7, 2), (8, -2), (6, 3)]:
print(f"{a} % {b}: Haat = {c_mod(a, b)}, Python = {a % b}")
print("IR সহ অংশ:", 6 + 3, "| IR ছাড়া:", 6 * 3)
xs, acc, r = [2, 3, 4], 0, 0
for x in xs:
acc = acc - x # foldl: ((0 − 2) − 3) − 4
for x in reversed(xs):
r = x - r # foldr: 2 − (3 − (4 − 0))
print("foldl:", acc, "| foldr:", r)
ok = seen = 0
for order in set(permutations("AABB")): # প্রতিটি thread: পড়া, তারপর লেখা
mem, reg = 0, {}
for t in order:
if t not in reg:
reg[t] = mem
else:
mem = reg[t] + 1
seen += 1; ok += mem == 2
print("interleaving:", seen, "| count = 2 হয়:", ok)আসল আউটপুট:
7 % 2: Haat = 1, Python = 1
-7 % 2: Haat = -1, Python = 1
8 % -2: Haat = 0, Python = 0
6 % 3: Haat = 0, Python = 0
IR সহ অংশ: 9 | IR ছাড়া: 18
foldl: -9 | foldr: 3
interleaving: 6 | count = 2 হয়: 2
চারটি input-এর মধ্যে শুধু (−7, 2)-এ দুই ভাষার % আলাদা। দুই thread-এর ৬টি interleaving-এর ২টিতেই সঠিক 2. Haat-এর দুটি প্রশ্ন reference বাস্তবায়নে চালানো (সত্যিকারের run): print(true + 1); দেয় 1:7: error: type mismatch: expected Int, found Bool, আর অদলবদলের program ছাপে 5. MGU-টি একটি ছোট unification script-এ মেলানো, ফল {Z: f(X), Y: g(f(X)), W: b}.
৩ · মডিউল ৩ ও ৪ — নাম, scope আর data type (১১টি প্রশ্ন)
মডিউল ৩ — নাম, binding আর scope (৬টি প্রশ্ন)
(সহজ) Top level-এ rate = 5; f() শুধু rate ফেরত দেয়; g()-এর ভেতরে local rate = 20 রেখে f() ফেরত দেয়। দুটি function-ই top level-এ লেখা। g()-এর মান static scope-এ আর dynamic scope-এ যথাক্রমে কত?
- 20 আর 5
- 5 আর 20
- 5 আর 5
- 20 আর 20
(মাঝারি) ছয় লাইনের Haat program: লাইন ১ let k = 3;, লাইন ২ {, লাইন ৩ print(k); (k আছে column 11-এ), লাইন ৪ let k = 4;, লাইন ৫ print(k);, লাইন ৬ }. Reference-এর check কী বলে?
- ok; চালালে 3 আর 4 ছাপে
- 2:1: error: 'k' is already declared in this scope
- 3:11: error: 'k' is used before its declaration
- চালালে 3:11: runtime error: 'k' is not initialized yet
(মাঝারি) Haat program: var n = 0; let inc = fn() -> Int { n = n + 2; return n; }; let get = fn() -> Int { return n; }; inc(); inc(); print(get() + inc()); কী ছাপবে?
- 10
- 12
- 8
- 2
(মাঝারি) C++20-এ int rate = 5; auto a = [=] { return rate * 2; }; auto b = [&] { return rate * 2; }; rate = 7; তারপর a() + b()-এর মান কত?
- 28
- 20
- Compile error
- 24
(মাঝারি) next() একটি global counter (শুরু 0) এক বাড়িয়ে নতুন মান ফেরত দেয়; triple(x) ফেরত দেয় x + x + x. triple(next())-এর মান call-by-name আর call-by-need-এ যথাক্রমে কত?
- 6 আর 6
- 6 আর 3
- 3 আর 3
- 3 আর 6
(কঠিন) Haat-এ (closure variable ধরে, আর while-এর দেহ প্রতি round-এ নতুন scope) নিচের program কী ছাপে? var i = 0; var f = fn() -> Int { return 0; }; while i < 3 { let j = i * 10; if i == 1 { f = fn() -> Int { return j; }; } i = i + 1; } print(f());
- 20
- 0
- 10
- 30
মডিউল ৪ — data type (৫টি প্রশ্ন)
(সহজ) Python 3.14-এ print(0.1 + 0.2 == 0.3, 0.1 + 0.2) কী ছাপে?
- True 0.3
- False 0.3
- TypeError
- False 0.30000000000000004
(মাঝারি) String “চাল🛒” (চ, া, ল আর U+1F6D2) UTF-8-এ রাখা। C17-এর strlen, Python 3-এর len() আর JavaScript-এর .length কী দেবে?
- 13, 4, 5
- 13, 4, 4
- 10, 4, 5
- 4, 4, 4
(মাঝারি) C-তে int A[4][5], base ঠিকানা 2000, int ৪ byte. A[3][2]-এর ঠিকানা কত?
- 2044
- 2068
- 2017
- 2080
(মাঝারি) x86-64 Linux-এ struct T { char a; double d; char b; int i; };-এর sizeof কত, আর packed না করে শুধু field-এর ক্রম বদলে সবচেয়ে ছোট কত করা যায়?
- 14 আর 14
- 16 আর 16
- 24 আর 16
- 32 আর 24
(কঠিন) enum Size { S, M, L }. Type Option<(Bool, Size)> (হয় None, নয় Some(একটি জোড়া))-এর কতগুলো আলাদা মান সম্ভব?
- 6
- 6, কারণ 1 + 2 + 3
- 12
- 7
from itertools import product
frames = [{"rate": 5}] # dynamic scope: চলমান frame-এর stack
def f_dynamic():
return next(fr["rate"] for fr in reversed(frames) if "rate" in fr)
frames.append({"rate": 20}); dyn = f_dynamic(); frames.pop()
print("static:", frames[0]["rate"], "| dynamic:", dyn)
cnt = 0
def nxt():
global cnt
cnt += 1
return cnt
by_name = nxt() + nxt() + nxt() # triple(x) = x + x + x, প্রতিবার আবার চলে
cnt = 0; v = nxt(); by_need = v + v + v # একবার চলে, মান মনে রাখা
print("by name:", by_name, "| by need:", by_need)
print("A[3][2] row-major:", 2000 + (3 * 5 + 2) * 4, "| column-major:", 2000 + (2 * 4 + 3) * 4)
def size(fields): # (আকার, alignment), x86-64-এর নিয়মে
off = big = 0
for sz, al in fields:
off = -(-off // al) * al + sz; big = max(big, al)
return -(-off // big) * big
C, D, I = (1, 1), (8, 8), (4, 4)
print("char,double,char,int:", size([C, D, C, I]), "| double,int,char,char:", size([D, I, C, C]))
vals = ["None"] + [f"Some({b}, {s})" for b, s in product([False, True], "SML")]
print("Option<(Bool, Size)>-এর মান:", len(vals))
s = "চাল🛒"
print("UTF-8 byte:", len(s.encode()), "| code point:", len(s), "| UTF-16 unit:", len(s.encode("utf-16-le")) // 2)
print(0.1 + 0.2 == 0.3, 0.1 + 0.2)আসল আউটপুট:
static: 5 | dynamic: 20
by name: 6 | by need: 3
A[3][2] row-major: 2068 | column-major: 2044
char,double,char,int: 24 | double,int,char,char: 16
Option<(Bool, Size)>-এর মান: 7
UTF-8 byte: 13 | code point: 4 | UTF-16 unit: 5
False 0.30000000000000004
Frame-এর stack দিয়ে dynamic scope অনুকরণ করলে 20, আর static নিয়মে 5. Struct-এর আকার alignment-এর নিয়মে হিসাব করা, x86-64-এ ctypes-এর সত্যিকারের sizeof-এর সঙ্গে মেলে। Haat-এর চারটি প্রশ্ন reference-এ চালানো: scope-এর program ছাপে 5, block-এর program দেয় 3:11: error: 'k' is used before its declaration, ভাগ করা n-এর program ছাপে 10, আর loop-এর closure ছাপে 10. C++-এর lambda-র উত্তর পাতার শেষের দিকের C++ block-এ চালানো।
৪ · মডিউল ৫ ও ৬ — subprogram আর type system (১২টি প্রশ্ন)
মডিউল ৫ — expression, control আর subprogram (৬টি প্রশ্ন)
(সহজ) Haat-এ print(20 - 6 - 4 * 2); কী ছাপে?
- 22
- 20
- 6
- 16
(মাঝারি) Haat program: let z = 0; print(z != 0 && 10 / z > 1); print(z == 0 || 10 / z > 1); কী ঘটে?
- false, তারপর true
- প্রথম print-এ runtime error: division by zero
- false, তারপর runtime error: division by zero
- check-এর সময় error, কারণ 10 / z-তে z = 0
(মাঝারি) শুরুতে g = 3. f(x) { x = x * 2; g = g + 1; x = x + g; }, তারপর f(g). Call by reference আর call by value-result-এ শেষে g যথাক্রমে কত?
- 14 আর 4
- 14 আর 10
- 10 আর 14
- 4 আর 4
(মাঝারি) JavaScript-এ function g() { try { throw 1; } catch (e) { return 2; } finally { console.log(3); } } তারপর console.log(g()); কী ছাপে?
- শুধু 2
- Uncaught 1
- 2, তারপর 3
- 3, তারপর 2
(মাঝারি) Node.js 24-এ: async function f() { console.log("a"); await null; console.log("c"); } f(); Promise.resolve().then(() => console.log("d")); console.log("b"); কোন ক্রমে ছাপে?
- a c d b
- a b d c
- a b c d
- b a c d
(কঠিন) Haat-এ (১,০০০-এর বেশি nested call হলে runtime error) fn s(n: Int) -> Int { if n == 0 { return 0; } return 1 + s(n - 1); } লাইন ১–৪-এ (ভেতরের s আছে লাইন ৩, column 16-এ), তারপর print(s(999)); print(s(1000));. কী ঘটে?
- 999, তারপর 1000
- 999, তারপর 3:16: runtime error: stack overflow
- দুটিতেই stack overflow
- check-এর সময় error
মডিউল ৬ — type system (৬টি প্রশ্ন)
(সহজ) "3" + 4 Python 3-এ আর JavaScript-এ কী দেয়?
- Python: চলার সময় TypeError; JavaScript: "34"
- দুটিতেই "34"
- Python: TypeError; JavaScript: 7
- Python: চালানোর আগেই error; JavaScript: "34"
(মাঝারি) দুই লাইনের Haat ফাইল: let ok = 3 > 2; আর let n: Int = ok; (দ্বিতীয় লাইনে ok আছে column 14-এ)। Reference-এর check কী বলে?
- ok, কারণ true মানে 1
- 1:10: error: type mismatch: expected Int, found Bool
- 2:14: error: type mismatch: expected Int, found Bool
- 2:14: error: undefined variable 'ok'
(মাঝারি) Hindley–Milner-এ λf. λx. f (f x)-এর principal type কোনটি?
- (a → b) → a → b
- (a → a) → a → a
- (Int → Int) → Int → Int
- Occurs check-এ ব্যর্থ
(মাঝারি) Member <: Customer. নিচের কোন function type (Customer) -> Customer-এর subtype?
- (Member) -> Customer
- (Member) -> Member
- (Int) -> Customer
- (Customer) -> Member
(মাঝারি) Generics-এর সাধারণ বাস্তবায়ন-কৌশল নিয়ে কোন মিলটি সঠিক?
- C++ template — monomorphization; Java generics — erasure; Haskell type class — dictionary passing
- C++ — erasure; Java — monomorphization; Haskell — dictionary passing
- C++ — dictionary passing; Java — erasure; Haskell — monomorphization
- তিনটিই erasure
(কঠিন) একটি ছোট ভাষার checker if-এর নিয়ম ঢিলে করে: শর্ত Bool হলে else-শাখার type-ই পুরো if-এর type, then-শাখা যাচাই হয় না। if true then false else 1 দেখে কোন theorem ভাঙে?
- Progress
- Progress আর preservation দুটিই
- Preservation
- কোনোটিই নয়
print("20 - 6 - 4 * 2 =", (20 - 6) - 4 * 2, "| ডান-সংযোগী ভুলে:", 20 - (6 - 4 * 2))
g = 3 # by reference: x আর g একই ঘর
g = g * 2; g = g + 1; g = g + g
by_ref = g
g = 3; x = g # value-result: ঢোকার সময় কপি
x = x * 2; g = g + 1; x = x + g
print("by reference:", by_ref, "| value-result:", x, "| by value-তে g:", g)
sub = {("Member", "Customer")} # Member <: Customer
def st(a, b):
if a == b or (a, b) in sub:
return True
if isinstance(a, tuple) and isinstance(b, tuple): # (param, ফল)
return st(b[0], a[0]) and st(a[1], b[1]) # S-Arrow
return False
T = ("Customer", "Customer")
for c in [("Member", "Customer"), ("Customer", "Member"), ("Member", "Member"), ("Int", "Customer")]:
print(f"({c[0]}) -> {c[1]} <: (Customer) -> Customer ?", st(c, T))
def step_if(cond, then_v, else_v): # ঢিলে checker: else-শাখার type-ই পুরো if-এর type
claimed = type(else_v).__name__
got = type(then_v if cond else else_v).__name__
return claimed, got
print("if true then false else 1 → (দাবি, আসল):", step_if(True, False, 1))আসল আউটপুট:
20 - 6 - 4 * 2 = 6 | ডান-সংযোগী ভুলে: 22
by reference: 14 | value-result: 10 | by value-তে g: 4
(Member) -> Customer <: (Customer) -> Customer ? False
(Customer) -> Member <: (Customer) -> Customer ? True
(Member) -> Member <: (Customer) -> Customer ? False
(Int) -> Customer <: (Customer) -> Customer ? False
if true then false else 1 → (দাবি, আসল): ('int', 'bool')
ছোট subtype checker-এ S-Arrow নিয়মে চারটির মধ্যে শুধু (Customer) -> Member পাস করে; শেষ লাইনে ঢিলে checker-এর দাবি আর আসল ফলের type আলাদা। Haat-এর প্রশ্নগুলো reference-এ চালানো (সত্যিকারের run): short-circuit-এর program ছাপে false, true; recursion-এর program ছাপে 999, তারপর 3:16: runtime error: stack overflow; type-এর ফাইলে 2:14: error: type mismatch: expected Int, found Bool. HM-এর type একটি ছোট Algorithm W script-এ বের করা: (a -> a) -> a -> a. JavaScript-এর তিনটি উত্তর শেষের JS block-এ।
৫ · মডিউল ৭ ও ৮ — semantics আর compiler-এর front end (১০টি প্রশ্ন)
মডিউল ৭ — ভাষার semantics (৪টি প্রশ্ন)
(মাঝারি) Big-step নিয়মে (B-WhileT: শর্ত true, দেহ, তারপর আবার while; B-WhileF: শর্ত false) σ₀ = {total ↦ 0} থেকে while total < 3000 { total = total + 1250; }-এর derivation-এ কয়টি B-WhileT আর কয়টি B-WhileF, আর শেষ state কী?
- ২টি B-WhileT, ১টি B-WhileF; total ↦ 2500
- ৩টি B-WhileT, ১টি B-WhileF; total ↦ 3750
- ৩টি B-WhileT, কোনো B-WhileF নেই; total ↦ 3750
- ৩টি B-WhileT, ১টি B-WhileF; total ↦ 3000
(মাঝারি) Haat-core-এ (expression state বদলায় না) wp(x = x * 2;, x > 10) কোনটি?
- x * 2 > 10
- x > 10
- x * 2 > 20
- x / 2 > 10
(মাঝারি) ০ থেকে গোনা de Bruijn index-এ λx. λy. λz. x z (y z) কীভাবে লেখা হয়?
- λ. λ. λ. 0 2 (1 2)
- λ. λ. λ. 3 1 (2 1)
- λ. λ. λ. 1 0 (2 0)
- λ. λ. λ. 2 0 (1 0)
(মাঝারি) কোন প্রশ্নের উত্তর small-step semantics দিতে পারে, কিন্তু সাধারণ (inductive) big-step semantics পারে না?
- একটি থেমে যাওয়া program-এর শেষ মান কত
- Operand কোন ক্রমে হিসাব হয়
- একটি program চিরকাল চলছে, নাকি আটকে (stuck) গেছে
- একটি expression-এর type কী
মডিউল ৮ — compiler-এর front end (৬টি প্রশ্ন)
(সহজ) Haat-এর lexer x!=-1&&y থেকে (EOF বাদে) কোন token-এর সারি বানায়?
- IDENT, BANG, EQ, MINUS, INT, AND_AND, IDENT
- IDENT, BANG_EQ, MINUS, INT, AND_AND, IDENT
- IDENT, BANG_EQ, INT, AND_AND, IDENT
- IDENT, BANG_EQ, MINUS, INT, AND, AND, IDENT
(মাঝারি) Haat-এর binding power-এ (prefix - 70, * 60, + 50) -a * b + c-এর AST কোনটি?
- (+ (* (- a) b) c)
- (+ (- (* a b)) c)
- (* (- a) (+ b c))
- (- (+ (* a b) c))
(মাঝারি) Haat-এ print(1 < 2 == 3 < 4); আর print(1 < 2 < 3); আলাদা ফাইলে চালালে কী ঘটে?
- দুটিই true ছাপে
- দুটিই syntax error
- প্রথমটি true ছাপে; দ্বিতীয়টি 1:13: error: comparison operators cannot be chained
- প্রথমটি true ছাপে; দ্বিতীয়টি type mismatch
(মাঝারি) দুই লাইনের Haat ফাইল: লাইন ১ let price = 520 (520 শুরু column 13-এ, শেষে ; নেই), লাইন ২ print(price);. Error কোথায় জানানো হয়?
- 2:1: error: expected ';' after variable declaration
- 1:13: error: expected ';' after variable declaration
- 2:1: error: type mismatch
- 1:16: error: expected ';' after variable declaration
(মাঝারি) Haat ফাইল: লাইন ১ let a = 5 +;, লাইন ২ let b = (2 * 3;, লাইন ৩ print(a b);. Panic-mode recovery-সহ reference-এর check কয়টি error দেয়?
- ১টি, প্রথমটিতেই থামে
- ৩টি
- ৫টি, কিছু ভুয়া cascade-সহ
- ২টি
(কঠিন) সবচেয়ে কম বন্ধনীর pretty-printer (haat.py fmt) print((a - b) + (c - d)); কে কীভাবে ছাপে?
- print(a - b + (c - d));
- print(a - b + c - d);
- print((a - b) + (c - d));
- print((a - b + (c - d)));
total, rules = 0, [] # big-step: B-WhileT / B-WhileF গোনা
while True:
if total < 3000:
rules.append("B-WhileT"); total = total + 1250
else:
rules.append("B-WhileF"); break
print(rules, "| শেষে total =", total)
ok = all((x * 2 > 10) == (x > 5) for x in range(-50, 51))
print("wp(x = x * 2, x > 10) = x * 2 > 10; ছোট পরিসরে x > 5-এর সমান:", ok)
def db(t, env=()): # ০ থেকে গোনা de Bruijn index
if isinstance(t, str):
return str(env.index(t))
if t[0] == "lam":
return "λ. " + db(t[2], (t[1],) + env)
return "(" + db(t[1], env) + " " + db(t[2], env) + ")"
body = ("app", ("app", "x", "z"), ("app", "y", "z"))
print(db(("lam", "x", ("lam", "y", ("lam", "z", body)))))
M = 2 ** 64
wrap = lambda v: (v + 2 ** 63) % M - 2 ** 63
x = 2 ** 62
print("x * 2 / 2, x = 2^62:", wrap(x * 2) // 2, "| x =", x)আসল আউটপুট:
['B-WhileT', 'B-WhileT', 'B-WhileT', 'B-WhileF'] | শেষে total = 3750
wp(x = x * 2, x > 10) = x * 2 > 10; ছোট পরিসরে x > 5-এর সমান: True
λ. λ. λ. ((2 0) (1 0))
x * 2 / 2, x = 2^62: -4611686018427387904 | x = 4611686018427387904
Derivation-এ তিনটি B-WhileT আর একটি B-WhileF, শেষে 3750. de Bruijn রূপান্তর λ. λ. λ. 2 0 (1 0) দেয়। শেষ লাইন পরের একটি প্রশ্নের জন্য: ৬৪-বিট wrap-এ x * 2 / 2 সবসময় x নয়। Front end-এর উত্তর reference CLI-এর সত্যিকারের run থেকে:
$ python -B haat.py tokens ... # x!=-1&&y
1:1 IDENT x
1:2 BANG_EQ !=
1:4 MINUS -
1:5 INT 1
1:6 AND_AND &&
1:8 IDENT y
2:1 EOF
$ python -B haat.py ast ... # print(-a * b + c);
(program
(print (+ (* (- a) b) c)))
$ python -B haat.py check ... # তিনটি ভাঙা লাইন
1:12: error: expected expression
2:15: error: expected ')' after expression
3:9: error: expected ')' after print argument
$ python -B haat.py fmt ...
print(a - b + (c - d));
Comparison-এর দুটি ফাইল ছাপে true আর দেয় 1:13: error: comparison operators cannot be chained; হারানো ;-এর ফাইল দেয় 1:16: error: expected ';' after variable declaration.
৬ · মডিউল ৯ ও ১০ — semantic analysis, interpreter আর VM (১১টি প্রশ্ন)
মডিউল ৯ — semantic analysis (৫টি প্রশ্ন)
(মাঝারি) Haat function fn f(x: Int) -> Int { let y = x + 1; { let z = y * 2; return z; } }. Reference-এর dis-এ f-এর locals কত?
- ২
- ৩
- ২, আর block-এর জন্য আলাদা frame-এ ১
- ৫, temp-সহ
(মাঝারি) Haat ফাইল print("a" < 1);-এ reference-এর check কয়টি error দেয়?
- একটিও নয়, Str-এর তুলনা বৈধ
- দুটি, প্রতিটি operand-এ একটি
- দুটি: একটি operand-এ, একটি print-এ
- একটি, 1:7-এ expected Int, found Str
(মাঝারি) Haat-এর missing-return নিয়মে (statement list return করে যদি তাতে return, return-করা block, বা else-সহ এমন if থাকে যার দুই শাখাই return করে; while কখনো গোনা হয় না) কোন function গৃহীত?
- fn a(n: Int) -> Int { if n > 0 { return 1; } }
- fn b(n: Int) -> Int { while n > 0 { return 1; } }
- fn d(n: Int) -> Int { if n > 0 { return 1; } else { if n < 0 { return 2; } else { return 0; } } }
- fn c(n: Int) -> Int { if n > 0 { return 1; } else { print(n); } }
(মাঝারি) বাঁ থেকে ডানে temp-নম্বর বসানো একটি syntax-directed translation a + b * c - d-এর জন্য কোন three-address code দেয়?
- t1 = b * c; t2 = a + t1; t3 = t2 - d
- t1 = a + b; t2 = t1 * c; t3 = t2 - d
- t1 = b * c; t2 = t1 - d; t3 = a + t2
- t1 = d; t2 = b * c; t3 = a + t2; t4 = t3 - t1
(কঠিন) একটি desugarer for i in 0..n() { … }-কে var i = 0; while i < n() { …; i = i + 1; }-এ নামায়। n() প্রতিবার 3 ফেরত দেয়। Loop চলাকালীন n() কতবার ডাকা হয়?
- ১ বার
- ৩ বার
- ৬ বার
- ৪ বার
মডিউল ১০ — interpreter আর virtual machine (৬টি প্রশ্ন)
(সহজ) একটি stack VM-এ CONST 20; CONST 6; CONST 2; DIV; SUB চলল (binary নির্দেশ ওপরের দুটি pop করে, আগে আসা মান বাঁ operand). শেষে stack-এর চূড়ায় কী?
- -20
- 17
- 7
- 3
(মাঝারি) Haat-এ top-level let a = 9; let b = 2; let c = 3; এরপর print(a - b * c);-এর reference bytecode কোন ক্রমে?
- LOAD_GLOBAL b, LOAD_GLOBAL c, MUL, LOAD_GLOBAL a, SUB, PRINT
- LOAD_LOCAL a, LOAD_LOCAL b, LOAD_LOCAL c, MUL, SUB, PRINT
- LOAD_GLOBAL a, LOAD_GLOBAL b, LOAD_GLOBAL c, MUL, SUB, PRINT
- CONST 3, PRINT
(মাঝারি) Haat-এর stack VM-এ print(1 + 2 * (3 + 4)); চালাতে operand stack-এ একসঙ্গে সর্বোচ্চ কয়টি মান থাকে?
- ৪
- ২
- ৩
- ৭
(মাঝারি) Haat-এ fn make(start: Int) -> () -> Int { var next = start; print(next); return fn() -> Int { next = next + 1; return next; }; }. Reference-এর dis-এ make নিজে next পড়তে আর ভেতরের lambda next পড়তে কোন opcode ব্যবহার করে?
- LOAD_LOCAL আর LOAD_LOCAL
- LOAD_GLOBAL আর LOAD_FREE
- LOAD_FREE আর LOAD_CELL
- LOAD_CELL আর LOAD_FREE
(মাঝারি) একটি program-এর প্রায় সব সময় যায় top level-এর একটি বড় loop-এ, যা একবারই চলে। শুধু function-call গুনে compile করা একটি JIT-এ কোন কৌশল না থাকলে এই loop দ্রুত হবে না?
- Inlining
- On-stack replacement (OSR)
- Deoptimization
- Inline cache
(কঠিন) CPython 3.14-এ y + 2 * 3 আর y + 2 + 3-এর bytecode-এ কোনটিতে compiler ধ্রুবক ভাঁজ করে একটি সংখ্যা বসায়?
- দুটিতেই
- শুধু y + 2 + 3
- শুধু y + 2 * 3
- কোনোটিতেই নয়
import dis
n = 0
def gen(e): # বাঁ থেকে ডানে temp-নম্বর
global n
if isinstance(e, str): return e
a, b = gen(e[1]), gen(e[2]); n += 1
print(f" t{n} = {a} {e[0]} {b}")
return f"t{n}"
gen(("-", ("+", "a", ("*", "b", "c")), "d"))
calls, i = [], 0
while i < (calls.append(1) or 3): # for i in 0..n()-এর নামানো রূপ, n() = 3
i = i + 1
print("n() ডাকা হলো:", len(calls), "বার")
def vm(code):
st, deep = [], 0
for op in code:
if isinstance(op, int): st.append(op) # CONST
else:
b, a = st.pop(), st.pop()
st.append({"ADD": a + b, "SUB": a - b, "MUL": a * b, "DIV": int(a / b)}[op])
deep = max(deep, len(st))
return st[-1], deep
print("CONST 20; CONST 6; CONST 2; DIV; SUB →", vm([20, 6, 2, "DIV", "SUB"])[0])
print("1 + 2 * (3 + 4): (ফল, সর্বোচ্চ গভীরতা) =", vm([1, 2, 3, 4, "ADD", "MUL", "ADD"]))
for src in ("y + 2 * 3", "y + 2 + 3"):
ins = [f"{i.opname} {i.argrepr or i.argval}" for i in dis.get_instructions(compile(src, "s", "eval"))]
print(src, "→", ins[1:-1])আসল আউটপুট:
t1 = b * c
t2 = a + t1
t3 = t2 - d
n() ডাকা হলো: 4 বার
CONST 20; CONST 6; CONST 2; DIV; SUB → 17
1 + 2 * (3 + 4): (ফল, সর্বোচ্চ গভীরতা) = (15, 4)
y + 2 * 3 → ['LOAD_NAME y', 'LOAD_SMALL_INT 6', 'BINARY_OP +']
y + 2 + 3 → ['LOAD_NAME y', 'LOAD_SMALL_INT 2', 'BINARY_OP +', 'LOAD_SMALL_INT 3', 'BINARY_OP +']
শেষ দুই লাইন ব্রাউজারের CPython-এর নিজের dis; ভাঁজ হয় শুধু 2 * 3-এ। Haat-এর উত্তর reference-এর সত্যিকারের run থেকে: function f-এর শিরোনাম == f (arity 1, locals 3) ==; print("a" < 1); দেয় একটি error 1:7: error: type mismatch: expected Int, found Str; চারটি function-এর মধ্যে শুধু d পাস করে, বাকিরা missing return: not every path of function 'a' returns Int ধাঁচের বার্তা পায়। make-এর listing (কয়েক লাইনে ভাগ করে লেখা ফাইল থেকে, তাই lambda-র নামে অবস্থান 4:12):
== make (arity 1, locals 2) ==
0 LOAD_LOCAL 0 ; start
1 MAKE_CELL 1 ; next
2 LOAD_CELL 1 ; next
3 PRINT
4 MAKE_CLOSURE 0 ; <fn lambda@4:12> captures next
5 RETURN
== lambda@4:12 (arity 0, locals 0) ==
0 LOAD_FREE 0 ; next
1 CONST 0 ; 1
2 ADD
3 STORE_FREE 0 ; next
4 LOAD_FREE 0 ; next
5 RETURN
৭ · মডিউল ১১ ও ১২ — IR, optimization, code generation আর runtime (১২টি প্রশ্ন)
মডিউল ১১ — IR আর optimization (৬টি প্রশ্ন)
(সহজ) নিচের রৈখিক IR-এ কয়টি basic block? (label নিজে কোনো নির্দেশ নয়) 0: s = const 0 · 1: i = const 0 · 2: label L1 · 3: t1 = i < n · 4: branch t1 L2 L3 · 5: label L2 · 6: s = s + i · 7: i = i + 1 · 8: jump L1 · 9: label L3 · 10: return s
- ৩
- ৪
- ৫
- ১১
(মাঝারি) একটি block-এ চারটি নির্দেশ: a = b * c, d = a - e, b = d + a, return b. Block-এর শুরুতে কোন নামগুলো live?
- {b, c, e}
- {a, b, c, e}
- {b, c}
- {b, c, d, e}
(মাঝারি) CFG-র edge: B0→B1, B1→B2, B1→B3, B2→B4, B3→B4, B4→B1, B4→B5. Variable x লেখা হয় শুধু B0 আর B2-তে। Iterated dominance frontier অনুযায়ী x-এর φ কোথায় বসে?
- শুধু B4-এ
- শুধু B1-এ
- B1, B4 আর B5-এ
- B1 আর B4-এ
(মাঝারি) Haat-এ (Int ৬৪-বিটে wrap করে, শূন্য দিয়ে ভাগ runtime error) কোন rewrite সব state-এ program-এর অর্থ রাখে?
- x / x → 1
- x * 2 / 2 → x
- অব্যবহৃত t = x * y মুছে ফেলা
- অব্যবহৃত t = x / y মুছে ফেলা
(মাঝারি) একটি loop-এ i-এর একমাত্র লেখা i = i + 3, আর t = i * 4. Strength reduction-এর পরে s = i * 4 রাখতে প্রতি round-এ s-এ কত যোগ হয়?
- 4
- 12
- 7
- 3
(কঠিন) Haat-এর একটি loop-এর দেহ: let t1 = a * b; if c { let t2 = x / d; s = s + t2; } s = s + t1; i = i + 1;. a, b, c, d, x loop-এ লেখা হয় না। LICM কোনটিকে loop-এর আগে (preheader-এ) তুলতে পারে?
- শুধু t1 = a * b
- t1 আর t2 দুটিই
- কোনোটিই নয়
- s = s + t1
মডিউল ১২ — code generation আর runtime (৬টি প্রশ্ন)
(সহজ) RV64I-এর addi-এর immediate ১২ বিটের, sign-সহ। p একটি register-এ থাকলে কোনটি একটি addi-তে হয়?
- p + 2048
- p - 2049
- p + 2047
- p + 4096
(মাঝারি) Interference graph-এর edge: a–b, b–c, c–a, c–d. দুটি register (k = 2) দিয়ে spill ছাড়া allocation সম্ভব কি?
- হ্যাঁ, কারণ d-এর একটিই প্রতিবেশী
- না, a–b–c ত্রিভুজের জন্য অন্তত ৩টি register লাগে
- হ্যাঁ, coalescing করলে
- না, ৪টি register লাগে
(মাঝারি) RISC-V psABI (RV64)-তে একটি function ১১টি long argument নেয়। ঢোকার মুহূর্তে ১১তম argument কোথায়?
- a10 register-এ
- 0(sp)-এ
- -16(sp)-এ
- 16(sp)-এ
(মাঝারি) Haat-এর a / b (b = 0)-কে সরাসরি RISC-V-এর div আর WebAssembly-র i64.div_s-এ নামালে কী হয়?
- RISC-V ফল দেয় −1, trap নেই; Wasm trap করে
- দুটিই trap করে
- দুটিই −1 দেয়
- দুটিই Haat-এর runtime error: division by zero দেয়
(মাঝারি) x86-64-এ একটি PC-relative relocation-এর হিসাব S + A − P. S = 0x401230, A = −4, P = 0x401100 হলে চার byte-এর ক্ষেত্রে কোন দশমিক সংখ্যা বসে?
- 304
- -300
- 300
- 4198960
(কঠিন) Heap: root থেকে শুধু A; A → B, B → C, D → E, E → D, আর F কারো দ্বারা নির্দেশিত নয়। একটি mark-sweep collector আর একটি শুধু-reference counting runtime (cycle collector নেই) কোন object-গুলো ফেরত আনে?
- দুটিই D, E, F
- Mark-sweep: D, E, F; RC: শুধু F
- Mark-sweep: শুধু F; RC: D, E, F
- Mark-sweep: C, D, E, F; RC: শুধু F
code = ["s = const 0", "i = const 0", "label L1", "t1 = i < n", "branch t1 L2 L3",
"label L2", "s = s + i", "i = i + 1", "jump L1", "label L3", "return s"]
leaders = {0} | {next(j for j in range(k + 1, len(code)) if not code[j].startswith("label"))
for k, ins in enumerate(code[:-1]) if ins.startswith(("label", "branch", "jump"))}
print("leader:", sorted(leaders), "| block:", len(leaders))
live = set() # পেছন থেকে: (live − {লেখা}) ∪ পড়া
for dst, uses in reversed([("a", {"b", "c"}), ("d", {"a", "e"}), ("b", {"d", "a"}), (None, {"b"})]):
live = (live - {dst}) | uses
print("block-এর শুরুতে live:", sorted(live))
succ = {0: [1], 1: [2, 3], 2: [4], 3: [4], 4: [1, 5], 5: []}
pred = {b: [p for p in succ if b in succ[p]] for b in succ}
dom = {b: set(succ) for b in succ}; dom[0] = {0}
for _ in succ: # সরল iterative dominator
for b in list(succ)[1:]:
dom[b] = {b} | set.intersection(*(dom[p] for p in pred[b]))
idom = {b: max(dom[b] - {b}, key=lambda d: len(dom[d])) for b in list(succ)[1:]}
df = {b: set() for b in succ}
for b in (b for b in succ if len(pred[b]) > 1):
for r in pred[b]: # Cytron et al.: idom পর্যন্ত উঠে যাওয়া
while r != idom[b]:
df[r].add(b); r = idom[r]
phi, work = set(), [0, 2] # x লেখা হয় B0 আর B2-তে
while work:
for y in df[work.pop()] - phi:
phi.add(y); work.append(y)
print("idom:", idom, "| x-এর φ:", sorted(f"B{y}" for y in phi))আসল আউটপুট:
leader: [0, 3, 6, 10] | block: 4
block-এর শুরুতে live: ['b', 'c', 'e']
idom: {1: 0, 2: 1, 3: 1, 4: 1, 5: 4} | x-এর φ: ['B1', 'B4']
Leader চারটি, block-এর শুরুতে live {b, c, e}. Dominator tree-তে B1 সবার ওপরে loop-এর ভেতরে; join block থেকে idom পর্যন্ত উঠে frontier বের করে iterated frontier-এ φ পড়ে B1 আর B4-এ, Cytron et al.-এর পদ্ধতিতে।
from itertools import product
fits = lambda k: -2048 <= k <= 2047 # addi-র ১২ বিটের signed immediate
for k in (2047, 2048, -2049, 4096):
print(f"p + {k}: এক addi-তে ধরে?", fits(k))
V = "abcd"
E = {("a", "b"), ("b", "c"), ("c", "a"), ("c", "d")}
for k in (2, 3): # সব রং-বিন্যাস চেষ্টা
ok = any(all(col[V.index(u)] != col[V.index(v)] for u, v in E)
for col in product(range(k), repeat=len(V)))
print(f"{k}টি register-এ spill ছাড়া রং সম্ভব?", ok)
print("১১তম argument: ঢোকার মুহূর্তে", (11 - 9) * 8, "(sp)")
S, A, P = 0x401230, -4, 0x401100
print("S + A − P =", S + A - P)
heap = {"A": ["B"], "B": ["C"], "C": [], "D": ["E"], "E": ["D"], "F": []}
marked, todo = set(), ["A"] # root থেকে শুধু A
while todo:
o = todo.pop()
if o not in marked:
marked.add(o); todo += heap[o]
rc = {o: 0 for o in heap}; rc["A"] = 1 # root-এর গণনা
for o in heap:
for t in heap[o]:
rc[t] += 1
print("mark-sweep মোছে:", sorted(set(heap) - marked), "| RC-তে গণনা ০:", sorted(o for o in heap if rc[o] == 0))আসল আউটপুট:
p + 2047: এক addi-তে ধরে? True
p + 2048: এক addi-তে ধরে? False
p + -2049: এক addi-তে ধরে? False
p + 4096: এক addi-তে ধরে? False
2টি register-এ spill ছাড়া রং সম্ভব? False
3টি register-এ spill ছাড়া রং সম্ভব? True
১১তম argument: ঢোকার মুহূর্তে 16 (sp)
S + A − P = 300
mark-sweep মোছে: ['D', 'E', 'F'] | RC-তে গণনা ০: ['F']
সব রং-বিন্যাস চেষ্টা করে দেখা গেল ২টি register-এ অসম্ভব, ৩টিতে সম্ভব। Mark-sweep চক্রসহ তিনটি object মোছে, reference counting শুধু F. RISC-V আর Wasm-এর ভাগের প্রশ্ন: Wasm-এর trap শেষের JS block-এ সত্যিকারের i64.div_s চালিয়ে দেখানো; RISC-V-এর ফল −1 আসে RISC-V-এর M extension-এর নিয়ম থেকে, যা পর্ব ৬৯ আর ৭২-এ আছে।
৮ · মডিউল ১৩ — আধুনিক ভাষা আর tool (৪টি প্রশ্ন)
(মাঝারি) Rust 1.82-এ let s = String::from("EID-50"); let t = s; println!("{} {}", s, t); compile করলে কী হয়?
- EID-50 EID-50 ছাপে
- Compile হয়, চলার সময় panic
- Compile error E0382: moved value ব্যবহার
- Compile error: lifetime annotation লাগবে
(মাঝারি) Store buffering litmus test, শুরুতে x = y = 0: thread A — x = 1; r1 = y;, thread B — y = 1; r2 = x;. Sequential consistency-তে কোন ফল অসম্ভব?
- r1 = 0, r2 = 1
- r1 = 1, r2 = 0
- r1 = 1, r2 = 1
- r1 = 0, r2 = 0
(মাঝারি) C-তে #define DOUBLE(x) x+x থাকলে printf("%d\n", 3 * DOUBLE(4)); কী ছাপে?
- 16
- 24
- Compile error
- 12
(সহজ) ৬টি editor আর ৭টি প্রোগ্রামিং ভাষা। প্রতিটি editor-এ প্রতিটি ভাষার সমর্থন দিতে LSP ছাড়া আর LSP দিয়ে কয়টি বাস্তবায়ন লাগে?
- ১৩ আর ৪২
- ৪২ আর ১৩
- ৪২ আর ৭
- ৪২ আর ৪২
৯ · মিশ্র মহড়া — ঘড়ি ধরে ১০টি প্রশ্ন, সব মডিউল থেকে
সব ভাগ শেষ হলে এই অংশটি একটি ছোট মহড়া পরীক্ষা হিসেবে করুন। প্রশ্নগুলো ইচ্ছা করে এলোমেলো, কারণ আসল পরীক্ষায় closure-এর পরেই GC, তারপর type inference আসতে পারে। ওপরের প্রশ্ন থেকে এগুলো আলাদা।
- ঘড়ি ধরুন: ১৫ মিনিটের টাইমার চালু করুন; প্রতি প্রশ্নে গড়ে দেড় মিনিট।
- আগে খাতায়: ১ থেকে ১০ নম্বরের পাশে অপশন আর এক লাইনের কারণ লিখুন; সময় শেষ হলে তবেই অপশন চাপুন।
- ফল পড়ুন এভাবে: ৮ বা বেশি ঠিক হলে প্রস্তুতি ভালো; ৫ থেকে ৭ হলে ভুল প্রশ্নের পর্বগুলো ঝালিয়ে নিন; ৪ বা কম হলে আগে মডিউলের ভাগগুলো আবার করুন। এই সীমা শুধু অনুশীলনের সুবিধার জন্য ধরা, কোনো পরীক্ষার মান নয়।
(সহজ) Haat-এ fn price(qty: Int, unit: Int) -> Int { let p = qty * unit; if p >= 1000 { return p - p / 10; } return p; } থাকলে print(price(3, 400) + price(1, 999)); কী ছাপে?
- 2199
- 1979
- 2079
- 1080
(মাঝারি) JavaScript-এ for (var i = 0; i < 3; i++) fv.push(() => i); আর for (let k = 0; k < 3; k++) fl.push(() => k);. সব function ডাকলে fv আর fl থেকে কী আসে?
- দুটিতেই 0 1 2
- fv: 3 3 3; fl: 0 1 2
- fv: 2 2 2; fl: 0 1 2
- দুটিতেই 3 3 3
(সহজ) C17-এ -7 / 2 আর -7 % 2, আর Python 3-এ -7 // 2 আর -7 % 2-এর মান কী?
- C: −3, −1; Python: −4, 1
- C: −4, 1; Python: −3, −1
- দুটিতেই −3, −1
- দুটিতেই −4, 1
(মাঝারি) Haat-এ print(-9223372036854775807 - 1 - 1); কী ছাপে?
- -9223372036854775809
- runtime error: integer overflow
- lexical error: integer literal too large
- 9223372036854775807
(সহজ) তিন লাইনের Haat ফাইল: fn f(n: Int) {, n = n + 1;, }. Reference-এর check কী বলে?
- ok
- missing return
- 2:5: error: cannot assign to parameter 'n'
- 2:5: error: undefined variable 'n'
(মাঝারি) Python 3.14-এ def tag(x, seen={}): seen[x] = len(seen); return len(seen), তারপর print(tag("a"), tag("b"), tag("a")) কী ছাপে?
- 1 1 1
- 1 2 2
- 1 2 3
- TypeError
(মাঝারি) Linear scan-এ চারটি live interval: a [1, 5], b [2, 3], c [4, 8], d [6, 9]. Spill ছাড়া সবচেয়ে কম কয়টি register লাগে?
- ২
- ৩
- ৪
- ১
(মাঝারি) একটি pure ভাষায় (side effect, exception বা চলার সময় type দেখার সুযোগ নেই) ∀α. α -> α type-এর একটি function, যা সবসময় থামে, কী করতে পারে?
- সবসময় 0 ফেরত দিতে পারে
- Int হলে 1 যোগ করতে পারে, নইলে argument ফেরত
- Argument-টিকে দুবার জুড়ে ফেরত দিতে পারে
- শুধু argument-টিই ফেরত দিতে পারে
(মাঝারি) Generational garbage collector-এ write barrier কেন লাগে?
- Heap-এ লেখা দ্রুত করতে
- নতুন object-কে সরাসরি old generation-এ পাঠাতে
- Old object থেকে young object-এর pointer লিখে রাখতে, যাতে young collection সেগুলো root ধরে
- প্রতিটি object-এর reference count বাড়াতে
(মাঝারি) JavaScript-এ function s(o) { o.x = 5; o = { x: 9 }; o.x = 7; } const p = { x: 1 }; s(p); console.log(p.x); কী ছাপে?
- 1
- 5
- 9
- 7
মহড়া শেষ করে, নম্বর লিখে তবেই নিচের তিনটি block চালান: প্রথমটি Python-এ হিসাব, দ্বিতীয়টি JavaScript-এর আচরণ আর সত্যিকারের WebAssembly ভাগ, তৃতীয়টি Wandbox-এ C++-এর উত্তর।
from itertools import combinations
A, B = [("x", 1), ("r1", "y")], [("y", 1), ("r2", "x")]
results = set()
for pos in combinations(range(4), 2): # program-ক্রম রেখে সব SC interleaving
mem, regs, ia, ib = {"x": 0, "y": 0}, {}, iter(A), iter(B)
for k in range(4):
dst, src = next(ia) if k in pos else next(ib)
if isinstance(src, int): mem[dst] = src
else: regs[dst] = mem[src]
results.add((regs["r1"], regs["r2"]))
print("SC-তে (r1, r2):", sorted(results))
print("LSP ছাড়া:", 6 * 7, "| LSP দিয়ে:", 6 + 7)
M = 2 ** 64
wrap = lambda v: (v + 2 ** 63) % M - 2 ** 63
c_div = lambda a, b: abs(a) // abs(b) * (1 if (a < 0) == (b < 0) else -1)
def price(q, u):
p = wrap(q * u)
return wrap(p - c_div(p, 10)) if p >= 1000 else p
print("price(3, 400) + price(1, 999) =", price(3, 400) + price(1, 999))
print("INT_MIN - 1 =", wrap(-2 ** 63 - 1))
def tag(x, seen={}):
seen[x] = len(seen)
return len(seen)
print("tag:", tag("a"), tag("b"), tag("a"))
iv = {"a": (1, 5), "b": (2, 3), "c": (4, 8), "d": (6, 9)}
print("একসঙ্গে live সর্বোচ্চ:", max(sum(s <= t <= e for s, e in iv.values()) for t in range(1, 10)))আসল আউটপুট:
SC-তে (r1, r2): [(0, 1), (1, 0), (1, 1)]
LSP ছাড়া: 42 | LSP দিয়ে: 13
price(3, 400) + price(1, 999) = 2079
INT_MIN - 1 = 9223372036854775807
tag: 1 2 2
একসঙ্গে live সর্বোচ্চ: 2
ছয়টি SC interleaving-এ (0, 0) কখনো আসে না। Python-এ wrap আর C-ধাঁচের ভাগ দিয়ে লেখা price reference-এর সত্যিকারের run-এর মতোই 2079 দেয়, আর reference নিজে INT_MIN − 1-এ ছাপে 9223372036854775807; parameter-এর ফাইলে দেয় 2:5: error: cannot assign to parameter 'n'.
function g() { try { throw 1; } catch (e) { return 2; } finally { console.log("finally: 3"); } }
console.log("g() =", g());
const fv = [], fl = [];
for (var i = 0; i < 3; i++) fv.push(() => i);
for (let k = 0; k < 3; k++) fl.push(() => k);
console.log("var:", fv.map(h => h()).join(" "), "| let:", fl.map(h => h()).join(" "));
console.log('"3" + 4 =', "3" + 4, '| "3" * 4 =', "3" * 4);
function s(o) { o.x = 5; o = { x: 9 }; o.x = 7; }
const p = { x: 1 };
s(p);
console.log("call by sharing: p.x =", p.x);
console.log('"চাল🛒".length =', "চাল🛒".length);
// (i64, i64) -> i64 { local.get 0; local.get 1; i64.div_s }, export "div"
const bytes = new Uint8Array([0, 97, 115, 109, 1, 0, 0, 0, 1, 7, 1, 96, 2, 126, 126, 1, 126,
3, 2, 1, 0, 7, 7, 1, 3, 100, 105, 118, 0, 0, 10, 9, 1, 7, 0, 32, 0, 32, 1, 127, 11]);
const div = new WebAssembly.Instance(new WebAssembly.Module(bytes)).exports.div;
console.log("Wasm 17 / 5 =", String(div(17n, 5n)));
try { div(17n, 0n); } catch (e) { console.log("Wasm 17 / 0 →", e.constructor.name); }
async function f() { console.log("a"); await null; console.log("c"); }
f();
Promise.resolve().then(() => console.log("d"));
console.log("b");আসল আউটপুট:
finally: 3
g() = 2
var: 3 3 3 | let: 0 1 2
"3" + 4 = 34 | "3" * 4 = 12
call by sharing: p.x = 5
"চাল🛒".length = 5
Wasm 17 / 5 = 3
Wasm 17 / 0 → RuntimeError
a
b
c
d
finally-র 3 ছাপে g ফেরার আগেই; var-এর closure তিনটিই 3 দেখে, let-এর closure নিজের round-এর মান। হাতে লেখা ৪১ byte-এর Wasm module একটি i64.div_s চালায়: 17 / 5 = 3, আর শূন্যে trap. সবশেষে async-এর a, b ছাপে sync অংশে, c আর d পরে microtask হিসেবে।
#include <cstdio>
#define DOUBLE(x) x+x
int main() {
int rate = 5;
auto a = [=] { return rate * 2; }; // তৈরির সময়ের কপি
auto b = [&] { return rate * 2; }; // variable-টিই
rate = 7;
std::printf("a() + b() = %d\n", a() + b());
std::printf("-7 / 2 = %d, -7 %% 2 = %d\n", -7 / 2, -7 % 2);
std::printf("3 * DOUBLE(4) = %d\n", 3 * DOUBLE(4));
}আসল আউটপুট:
a() + b() = 24
-7 / 2 = -3, -7 % 2 = -1
3 * DOUBLE(4) = 16
[=] তৈরির সময়ের 5 কপি করে, [&] variable-টিই দেখে, তাই 10 + 14. C++-এও C-র মতো ভাগ শূন্যের দিকে কাটে। Macro-র লেখা-বদল 3 * 4+4 দেয়। Rust-এর প্রশ্নটি Wandbox-এর rustc 1.82.0-এ আলাদা চালানো; সত্যিকারের বার্তার প্রথম অংশ:
error[E0382]: borrow of moved value: `s`
--> prog.rs:4:23
|
2 | let s = String::from("EID-50");
| - move occurs because `s` has type `String`, which does not implement the `Copy` trait
3 | let t = s;
| - value moved here
4 | println!("{} {}", s, t);
| ^ value borrowed here after move
AI-এর যুগে — AI দিয়ে আরও MCQ বানান, কিন্তু উত্তর নিজে চালিয়ে দেখুন
AI assistant মুহূর্তে শত শত প্রশ্ন বানাতে পারে, কিন্তু এই বিষয়ে সে প্রায়ই এক ভাষার নিয়ম সব ভাষায় চাপায়, undefined behavior-এর একটি ফলকে নিশ্চিত বলে, ভুল evaluation order ধরে, precedence ভুল এমন parse tree দেয়, বানানো compiler flag বা LLVM pass-এর নাম বলে, আসল compiler-এর সঙ্গে না-মেলা bytecode বা assembly লেখে, অর্থ বদলে দেয় এমন “optimization” ঠিক বলে, আর GC বা memory model-এর নিশ্চয়তা ভুল বলে। তাই AI-এর প্রশ্ন অনুশীলনের কাঁচামাল, উত্তরপত্র নয়।
| AI-এর প্রচলিত ভুল | উদাহরণ | কীভাবে ধরবেন |
|---|---|---|
| নিয়ম সাধারণীকরণ | “−7 % 2 সব ভাষায় 1” | C, Python, JS-এ আলাদা চালিয়ে দেখুন |
| UB-কে নিশ্চিত ফল বলা | “i++ + i++ = 3” | Standard-এর বাক্য পড়ুন; দুটি optimization স্তরে চালান |
| ভুল bytecode | CPython 3.14-এ পুরোনো opcode-এর নাম | নিজের version-এ dis চালান |
| অর্থ-বদলানো optimization | “x / x সবসময় 1” | শূন্য আর সীমার মানে দুই রূপ চালিয়ে তুলনা |
| বানানো উৎস | “অমুক পরীক্ষায় এসেছিল” | উৎস দেখাতে না পারলে দাবি বাদ |
নিচের প্রম্পটটি AI-কে প্রশ্ন বানাতে বলে, আর যাচাইয়ের উপায়ও চায়। উত্তর পেলে প্রতিটি আউটপুট আসল interpreter বা compiler-এ চালান, আর Haat-এর প্রশ্ন reference বাস্তবায়নে।
যাচাইয়ের চেকলিস্ট
কেন এই উত্তর ভুল? — রিভিশনের কৌশল আর বড় ধারণা
আগে নিজে ভাবুন, তারপর খুলে দেখুন।
প্র ০১“কী ছাপবে” প্রশ্নে ভাষা আর version কেন উত্তরের অংশ?
কারণ একই লেখার অর্থ ভাষাভেদে আলাদা, আর কিছু ক্ষেত্রে ভাষা কোনো অর্থই নির্দিষ্ট করে না। -7 / 2 C-তে −3, Python-এর //-এ −4; INT_MAX + 1 Java-তে নির্দিষ্টভাবে wrap করে, C-তে undefined behavior; i++ + i++ C-তে কোনো নির্দিষ্ট মানই রাখে না।
- ইতিহাস: ১৯৮৯ সালের ANSI C standard “sequence point” দিয়ে ঠিক করে কোন side effect কখন শেষ হয়, আর C11 তার জায়গায় “sequenced before” সম্পর্ক আনে (পর্ব ২৬)। ১৯৯৬ সালের প্রথম Java Language Specification থেকেই Java-তে operand বাঁ থেকে ডানে হিসাব হয়; Haat-ও তাই (README সিদ্ধান্ত ১২)।
- ভাগের নিয়ম: C89-এ ঋণাত্মক ভাগের দিক implementation-defined ছিল; C99 থেকে শূন্যের দিকে কাটা নির্দিষ্ট (পর্ব ০৩)।
- Version-এর প্রভাব: CPython-এর bytecode version-ভেদে বদলায়; 3.14-এ ছোট ধ্রুবকের জন্য
LOAD_SMALL_INTদেখা যায়, যা পুরোনো version-এ ছিল না (পর্ব ০১, ৬০)।
রিভিশনে প্রতিটি “কী ছাপবে” প্রশ্নের পাশে তিনটি প্রশ্ন লিখুন: কোন ভাষা আর version, হিসাবের ক্রম কি নির্দিষ্ট, আর undefined বা implementation-defined কিছু আছে কি না। তৃতীয়টির উত্তর “হ্যাঁ” হলে, যে অপশন একটি নির্দিষ্ট সংখ্যা দাবি করে, সেটি সাধারণত distractor; সঠিক অপশন হলো “নির্দিষ্ট মান নেই”। একই প্রশ্ন Haat-এ এলে উল্টো: Haat-এর spec আর reference-এর সিদ্ধান্তগুলো সব ফল নির্দিষ্ট করে, এমনকি INT_MIN / -1-ও (wrap করে INT_MIN).
আরেকটি অভ্যাস কাজে আসে: যে উত্তর একটি compiler চালিয়ে পেয়েছেন, তা শুধু সেই compiler আর সেই flag-এর ফল। Undefined behavior-এ -O0 আর -O2 আলাদা ফল দিতে পারে, পর্ব ০৬-এ Clang-এ ঠিক এমন দেখা গেছে। তাই “আমার যন্ত্রে এটি ছাপল” আর “ভাষা এটি নিশ্চিত করে” দুটি আলাদা দাবি।
মূল উপলব্ধি: আউটপুটের প্রশ্নে আগে নিয়মের উৎস ঠিক করুন, তারপর হিসাব।
প্র ০২Closure আর scope-এর প্রশ্নে “variable ধরে, মান নয়” কথাটি কেন এত গুরুত্বপূর্ণ?
Closure-এর প্রায় সব ফাঁদ একটি প্রশ্নে নামে: function তৈরির সময় বাইরের নামের মান কপি হয়, নাকি variable-টিই ভাগ হয়? Haat, Python আর JavaScript-এ variable ভাগ হয়; C++-এর [=] কপি নেয়, [&] ভাগ করে; Java-র lambda শুধু effectively final local ধরতে দেয়, তাই প্রশ্নটিই ওঠে না।
- ইতিহাস: Peter Landin ১৯৬৪ সালের SECD machine-এর প্রবন্ধে function আর তার environment-এর জোড়াকে “closure” বলেন বলে সাধারণত ধরা হয়। Joel Moses ১৯৭০ সালের একটি MIT memo-তে funarg সমস্যাকে নাম দেন। Sussman আর Steele-এর Scheme (১৯৭৫) lexical scope-এর closure-কে মূলধারায় আনে (পর্ব ১৫, ১৭)।
- Loop-এর ফাঁদ: ECMAScript 2015-এর
letপ্রতি round-এ নতুন binding দেয়,varদেয় না; Python-এর comprehension-এ lambda একই variable দেখে, তাই [4, 4, 4, 4]. Haat-এ while-এর দেহ প্রতি round-এ নতুন scope (README সিদ্ধান্ত ১৪)। - বাস্তবায়ন: Haat-এর VM ধরা variable-কে cell-এ রাখে; ঘোষণাকারী function
LOAD_CELL, closureLOAD_FREEদিয়ে একই বাক্স পড়ে (পর্ব ৫৭)।
রিভিশনে প্রতিটি closure-এর প্রশ্নে খাতায় বাক্স আঁকুন: প্রতিটি variable একটি বাক্স, প্রতিটি closure একটি তীর। তারপর প্রতিটি assignment কোন বাক্সে লেখে, তা চিহ্নিত করুন। Loop থাকলে জিজ্ঞেস করুন, প্রতি round-এ নতুন বাক্স হয় কি না। ভাগ করা বাক্সে হিসাবের ক্রমও গুরুত্বপূর্ণ হয়ে ওঠে: get() + inc() বাঁ থেকে ডানে 10, উল্টো ক্রমে 12. Static আর dynamic scope গুলিয়ে গেলে মনে রাখুন: static scope লেখার কাঠামো দেখে নাম খোঁজে, dynamic scope চলার সময়ের call-শিকল দেখে; প্রায় সব আধুনিক ভাষা static.
মূল উপলব্ধি: Closure একটি function আর কয়েকটি ভাগ করা বাক্স; বাক্স কে কখন বদলায়, সেটিই উত্তর।
প্র ০৩Type checker-এর রায় নিয়ে প্রশ্নে “sound” আর “complete” কেন আলাদা রাখতে হয়?
Sound checker যা মেনে নেয়, তা চলার সময় প্রতিশ্রুত ভুলে পড়ে না; complete checker প্রতিটি নিরাপদ program মেনে নেয়। বাস্তবের checker প্রায় সবসময় sound হতে চায় কিন্তু complete নয়, তাই কিছু নিরাপদ program বাতিল হয়। Haat-এর missing-return নিয়ম এর উদাহরণ: while true { return n; } কখনো return ছাড়া শেষ হয় না, তবু বাতিল, কারণ নিয়মটি syntactic (README সিদ্ধান্ত ২১)।
- ইতিহাস: Robin Milner ১৯৭৮ সালের প্রবন্ধে “well-typed programs cannot go wrong” কথাটি প্রমাণসহ দেন; Andrew Wright আর Matthias Felleisen ১৯৯৪ সালে progress আর preservation-এর syntactic পদ্ধতি দেন, যা আজ পাঠ্যবইয়ের মানক (পর্ব ৩৮)।
- সীমা: Henry Rice-এর ১৯৫৩ সালের theorem অনুযায়ী program-এর অ-তুচ্ছ অর্থগত ধর্ম সাধারণভাবে undecidable, তাই sound আর complete একসঙ্গে, সব program-এ, পাওয়া যায় না (পর্ব ৩৩, ৮০)।
- ইচ্ছাকৃত ফাঁক: TypeScript-এর
anyযাচাই বন্ধ করে, আর চলার সময় type মুছে যায়; তাই checker-এর number আসলে string হতে পারে (পর্ব ৩৮, ৩৯)।
MCQ-তে একটি অপশন যদি বলে “checker এটি বাতিল করেছে, তাই program-টি চলার সময় ভুল করত”, সেটি সন্দেহ করুন: incomplete checker নিরাপদ program-ও বাতিল করে। উল্টো দিকে, “checker মেনে নিয়েছে, তাই কোনো runtime error হবে না” অপশনও সাবধানে পড়ুন: Haat-এ শূন্য দিয়ে ভাগ আর stack overflow ঘোষিত runtime error, soundness-এর বিরোধী নয়, কারণ semantics এগুলোকে stuck অবস্থা নয়, নির্দিষ্ট ফল হিসেবে সংজ্ঞায়িত করে। কোন ভুল type system ঠেকানোর প্রতিশ্রুতি দেয়, আর কোনটি দেয় না, তা ভাষার spec থেকে আলাদা করে লিখে রাখুন।
মূল উপলব্ধি: Sound মানে “গ্রহণ করলে নিরাপদ”, complete মানে “নিরাপদ হলে গ্রহণ”; দুটি দুই দিকের প্রতিশ্রুতি।
প্র ০৪একই optimization এক ভাষায় বৈধ আর আরেক ভাষায় অবৈধ কেন?
কারণ optimization-এর একমাত্র শর্ত হলো দেখা যায় এমন আচরণ না বদলানো, আর কোন আচরণ “দেখা যায়”, তা ভাষার semantics ঠিক করে। C-তে শূন্য দিয়ে ভাগ undefined behavior, তাই Clang x / x-কে 1 বানাতে পারে; Haat-এ শূন্য দিয়ে ভাগ একটি নির্দিষ্ট runtime error, তাই একই rewrite অবৈধ (পর্ব ৬৫)। একই কারণে অব্যবহৃত t = x / y Haat-এ মোছা যায় না, অথচ অব্যবহৃত t = x * y মোছা যায়।
- ইতিহাস: Frances Allen আর John Cocke ১৯৭১ সালে optimizing transformation-এর একটি প্রভাবশালী তালিকা প্রকাশ করেন; Gary Kildall ১৯৭৩ সালে dataflow analysis-এর lattice-ভিত্তিক কাঠামো দেন; Cytron আর সহকর্মীরা ১৯৯১ সালে SSA তৈরির দক্ষ পদ্ধতি দেন (পর্ব ৬৩, ৬৪)।
- যাচাই: Xavier Leroy-র CompCert (২০০৬ থেকে প্রকাশিত কাজ) একটি proof assistant-এ প্রমাণিত C compiler; ২০১১ সালের Csmith গবেষণা এলোমেলো C program দিয়ে GCC আর LLVM-এ বহু ভুল খুঁজে পায়, কিন্তু CompCert-এর প্রমাণিত অংশে নয় বলে প্রতিবেদন করে (পর্ব ৪৪)।
- Wrap-এর প্রভাব: ৬৪-বিট wrap-এ
x * 2 / 2 → xভুল (x = 262), কিন্তু strength reduction ঠিক, কারণ mod 264-এ বণ্টন-নিয়ম খাটে (পর্ব ৬৬)।
MCQ-তে কোনো rewrite দেখলে তিনটি মান বসান: শূন্য, ঋণাত্মক, আর type-এর সীমা (INT_MIN, INT_MAX). দুই রূপ কোনো একটিতে আলাদা ফল বা আলাদা error দিলে rewrite অবৈধ। LICM-এর প্রশ্নে আরেকটি প্রশ্ন যোগ করুন: নির্দেশটি কি প্রতি round-এ, সব পথে চলে? শর্তসাপেক্ষ ভাগ loop-এর বাইরে তুললে এমন অবস্থায়ও চলবে, যেখানে আগে চলত না, আর নতুন error আনবে।
মূল উপলব্ধি: “এটি দ্রুত করে” যথেষ্ট নয়; “এটি কোনো input-এ ফল বদলায় না” প্রমাণ করতে হয়, সেই ভাষার নিয়মে।
প্র ০৫Register allocation আর GC-র প্রশ্নে কেন graph বা heap আঁকাই সবচেয়ে দ্রুত পথ?
দুটি বিষয়ের প্রশ্নই আসলে graph-এর প্রশ্ন। Register allocation-এ interference graph-এর রং: একটি k-clique থাকলে অন্তত k রং লাগে। GC-তে heap-এর object graph: mark-sweep root থেকে পৌঁছানো দেখে, reference counting শুধু আগত তীর গোনে, তাই চক্র তার চোখে আবর্জনা নয়।
- ইতিহাস: Gregory Chaitin ১৯৮১–৮২ সালে graph coloring-এ register allocation-এর পদ্ধতি দেন; Preston Briggs আর সহকর্মীরা ১৯৯৪ সালে optimistic coloring দেন, যা কিছু spill এড়ায়; Massimiliano Poletto আর Vivek Sarkar ১৯৯৯ সালে দ্রুত linear scan দেন, যা JIT-এ জনপ্রিয় (পর্ব ৭০)।
- GC-র ইতিহাস: John McCarthy ১৯৬০ সালের LISP প্রবন্ধে স্বয়ংক্রিয় memory ফেরতের বর্ণনা দেন; George Collins একই বছর reference counting প্রকাশ করেন; C. J. Cheney ১৯৭০ সালে copying collector দেন; Lieberman আর Hewitt (১৯৮৩) আর David Ungar (১৯৮৪) generational ধারণা দেন (পর্ব ৭৫)।
- Linear scan-এর হিসাব: interval-গুলোর সবচেয়ে বড় একসঙ্গে-live সংখ্যাই ন্যূনতম register, কারণ interval graph-এ clique-এর আকার আর রং-সংখ্যা সমান (পর্ব ৭০)।
খাতায় node আর তীর আঁকতে তিরিশ সেকেন্ড লাগে, কিন্তু তাতে প্রায় সব distractor কেটে যায়: degree দেখে “simplify আটকাবে কি না”, ত্রিভুজ দেখে “৩ রং লাগবে”, root থেকে পৌঁছানো দেখে “কে বাঁচবে”, চক্র দেখে “RC কাকে ছাড়বে না”। Generational GC-র প্রশ্নে old থেকে young-এর তীরগুলো আলাদা রঙে আঁকুন: write barrier ঠিক এই তীরগুলোই remembered set-এ লিখে রাখে। Haat-এর VM-এ এমন লেখা ঘটে শুধু STORE_CELL আর STORE_FREE-এ (পর্ব ৭৫)।
মূল উপলব্ধি: ছবি আঁকলে প্রশ্নটি রং গোনা বা পৌঁছানো খোঁজায় নামে, যা মুখস্থের চেয়ে নির্ভরযোগ্য।
শেষ ধাপ — ক্রম সাজান আর স্কোর দেখুন
উপরের সব MCQ শেষ করলে নিচে আপনার মোট স্কোর দেখাবে।
ক্রমHaat reference-এ python haat.py vm একটি ফাইল নিয়ে যে ছয়টি ধাপ পেরোয়। আগে থেকে পরে সাজান (▲▼ চেপে সরান)
- Lexer: অক্ষর থেকে token
- Parser: token থেকে AST
- Resolver: প্রতিটি নাম তার ঘোষণার সঙ্গে জোড়া, slot আর capture
- Type checker: প্রতিটি expression-এর type আর missing return
- Bytecode compiler: AST থেকে Code object
- Stack VM: নির্দেশ একে একে চালানো
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব শব্দ এখানে একসাথে:
মনে রাখুন
- ভাষা আর version আগে: ভাগ, overflow, closure আর হিসাবের ক্রম ভাষাভেদে আলাদা; undefined behavior-এ কোনো ফল নিশ্চিত নয়।
- Closure বাক্স ভাগ করে: variable ধরে, মান নয়; loop-এ নতুন বাক্স হয় কি না জিজ্ঞেস করুন।
- Error-এর ধাপ আর অবস্থান: lexer প্রথম ভুলে থামে, parser আর checker সব জানায়; হারানো ; আগের token-এর ঠিক পরে।
- Optimization-এর শর্ত: শূন্য, ঋণাত্মক আর সীমার মানে দুই রূপ একই আচরণ দিলে তবেই বৈধ।
- ছবি আঁকুন: CFG, interference graph আর heap-এর graph এঁকে liveness, রং আর পৌঁছানো গুনুন।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৮৪ · লিখিত ও মৌখিক (ভাইভা) প্রশ্নপরবর্তী পর্বতুলনা আর ব্যাখ্যার লিখিত প্রশ্ন, সঙ্গে ভাইভার ছোট উত্তর।
- প্রোগ্রামিং ভাষা ও কম্পাইলার · কোর্স হোম৮৬টি পর্বপুরো কোর্সের মানচিত্র আর ১৪টি মডিউল।
- পর্ব ৮৫ · Type derivation আর semantics-এর অনুশীলনঅনুশীলনTyping rule, inference আর Hoare logic-এর পূর্ণ derivation.
- পর্ব ২৬ · Expression আর evaluation orderভিত্তি“কী ছাপবে” প্রশ্নের মূল নিয়ম।
- পর্ব ৬৫ · Optimizationভিত্তিকোন rewrite কোন ভাষায় বৈধ।
- গণনার তত্ত্ব · MCQ প্রশ্নব্যাংক (পর্ব ৮২)পাশের ট্র্যাকAutomaton, grammar আর parsing তত্ত্বের MCQ.
- সি প্রোগ্রামিং · MCQ প্রশ্নব্যাংক (পর্ব ৫৮)পাশের ট্র্যাকC-র আচরণ, pointer আর undefined behavior-এর MCQ.