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

ক্যাপস্টোন — Haat-এর পূর্ণ compiler, source থেকে চলমান program

Capstone — The Complete Haat Toolchain: Front End, Interpreter, Bytecode VM, SSA Optimiser, LLVM IR, RISC-V and WebAssembly, Differential Testing and Your Own Language Feature

Taught in Bangla, this capstone runs one new Haat program, a warehouse stock report, through the course's whole toolchain: front end, tree-walking interpreter, bytecode VM, SSA optimiser, LLVM IR, RISC-V and WebAssembly back ends, with every back end printing the same output. It traces one statement through eleven stages, runs a large differential test across twelve implementations, locates a planted optimiser bug from a mismatch, and sets a project to add for loops or arrays to Haat with an assessment checklist.

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

  • Haat-এর পুরো toolchain একটি মানচিত্রে বসানো: কোন পর্বে কোন ধাপ, কোন ফাইলে কত লাইন, কোন ধাপের ইনপুট আর আউটপুট কী
  • একটি statement-কে source থেকে token, AST, bytecode, Haat IR, LLVM IR, RISC-V আর WebAssembly পর্যন্ত অনুসরণ করা
  • একই program সব back end-এ চালিয়ে একই আউটপুট দেখানো, আর কেন নির্দেশের সংখ্যা আলাদা হয় তা ব্যাখ্যা করা
  • এলোমেলো program দিয়ে differential testing চালানো, আর অমিল থেকে দায়ী ধাপ ও pass খুঁজে বের করা
  • Haat-এ নিজের একটি feature শুরু থেকে শেষ পর্যন্ত যোগ করার পরিকল্পনা: কোন ধাপ বদলাবে, কোন test লিখবেন, কীভাবে মূল্যায়ন হবে

১ · পুরো পথের মানচিত্র — ত্রিশটির বেশি পর্ব একটি ছবিতে

পর্ব ৪৫ থেকে আপনি একটি ভাষার বাস্তবায়ন টুকরো টুকরো বানিয়েছেন। প্রতিটি পর্ব একটি ধাপ নিয়েছে, আগের ধাপের আউটপুটকে নিজের ইনপুট ধরেছে, আর নিজের পরীক্ষা চালিয়েছে। এই পর্বে টুকরোগুলো জোড়া লাগে। প্রশ্ন একটাই: একটি নতুন Haat program লিখলে কি সবগুলো পথ দিয়ে সেটি চলে, আর সব পথ কি একই উত্তর দেয়?

উপমা — বাজারঘরের একটি অর্ডারের যাত্রা: গ্রাহকের লেখা অর্ডার স্লিপ প্রথমে যায় কাউন্টারে, সেখানে অক্ষর পড়ে শব্দ আলাদা করা হয় (lexer). তারপর হিসাবরক্ষক স্লিপটি ফর্মের ঘরে সাজান (parser), দেখেন প্রতিটি পণ্যের নাম তালিকায় আছে কি না (resolver), আর পরিমাণের ঘরে সংখ্যা আছে কি না (type checker). এরপর অর্ডার পূরণের তিন রকম পথ: দোকানের কর্মী নিজে তাক থেকে জিনিস তোলেন (interpreter); একটি ছাপা চেকলিস্ট ধরে গুদামের সহকারী তোলেন (bytecode আর VM); অথবা পুরো কাজ আগেই একটি স্বয়ংক্রিয় যন্ত্রের নির্দেশে রূপান্তর করা হয় (native code). পথ আলাদা, কিন্তু গ্রাহকের ব্যাগে একই জিনিস পৌঁছাতে হবে। এই “একই জিনিস” মিলিয়ে দেখাই এই পর্বের কাজ।

নিচের ছবিতে প্রতিটি বাক্স একটি পর্বের লিংক। ওপরের নীল অংশ front end: source থেকে যাচাই-করা AST. তারপর পথ তিন ভাগ হয়। বাঁয়ে tree-walking interpreter, মাঝে bytecode আর stack virtual machine, ডানে middle end: Haat IR, SSA, dataflow analysis আর optimiser. Middle end-এর পরে তিনটি target: LLVM IR, RISC-V আর WebAssembly. সবুজ টিক-চিহ্ন যেখানে, সেখানে program সত্যিই চলে আর আউটপুট ছাপে।

ছবি ৮১.১ — Haat-এর পূর্ণ toolchain: প্রতিটি বাক্স একটি পর্ব

ওপর থেকে নিচে: source, front end, তারপর তিনটি শাখা আর তিনটি target. বাক্সে চাপলে সেই পর্বে যাবেন। সবুজ ✓ মানে এখানে program চলে; সবার আউটপুট নিচের সবুজ বাক্সের সমান।

The Haat toolchain: source, front end (lexer, parser, resolver, type checker), then interpreter, bytecode VM, and the IR path with SSA, dataflow and optimiser feeding LLVM IR, RISC-V and WebAssembly; every runnable path prints the same output stock.haat (source) Front end · পর্ব ৪৫–৫৫ ৪৬ lexer → token ৪৭–৪৯ parser → AST (৫০ error) ৫১ resolver → binding, scope ৫২ type checker (৫৪, ৫৫) ৫৬–৫৭interpreter ✓ ৫৮ bytecode ৫৯ stack VM ✓ (৬১ JIT) ৬২ Haat IR ৬৩ SSA ৬৪ dataflow ৬৫ optimiser (৬৬,৬৭) ৬৮ LLVM IR→ Clang ✓ ৬৯–৭২RISC-V ✓ ৭৩ Wasmbrowser, Node ✓ বাস্তব compiler-এর বাকি অংশ: ৭০ register ৭১ ABI ৭৪ linking ৭৫ GC প্রতিটি ✓ পথের আউটপুট: 3004 4005 7004 8005 4 8620 true
ছবি ৮১.১ — তিনটি শাখা একই যাচাই-করা AST থেকে শুরু। Interpreter আর VM সরাসরি চালায়; IR-এর পথ আগে রূপান্তর আর optimization করে, তারপর তিনটি ভিন্ন যন্ত্রের ভাষায় নামে। ধূসর বাক্সগুলোর বিষয় এই কোর্সে আছে, কিন্তু এই পাতার Int/Bool program-এ লাগে না: পর্ব ৭২-এর back end register allocation না করে প্রতিটি মান stack-এর ঘরে রাখে, আর closure বা string নেই বলে garbage collection-এর কাজ নেই।

ছবির ক্রমটিই পর্ব ০৫-এর compiler-এর ধাপ, তফাত শুধু এই যে প্রতিটি ধাপ আপনার নিজের বানানো। পর্ব ০৪-এর তিন রকম বাস্তবায়ন, interpreter, bytecode VM আর ahead-of-time compiler, এখন একই ভাষার জন্য পাশাপাশি।

২ · কোন ধাপ, কোন ফাইল, কত লাইন

Haat-এর দুটি বাস্তবায়ন আছে। একটি reference: কোর্সের শুরুতে কেন্দ্রীয়ভাবে বানানো, পরীক্ষিত Python বাস্তবায়ন, যার python haat.py run আর vm প্রতিটি পর্বের মাপকাঠি। অন্যটি পাতার module: প্রতিটি পর্ব নিজের পাতায় যে ছোট Python ফাইল রেখেছে, browser-এ চালানোর জন্য। Reference থামে stack bytecode-এ; IR, SSA, optimiser আর তিনটি native target শুধু পাতার module-এ আছে। নিচের টেবিলে reference-এর প্রতিটি ফাইলের লাইন, ল্যাবে গুনে (ফাঁকা লাইন আর শুধু-comment লাইন বাদ দিলে কত, তা-ও):

ধাপ (পর্ব)Reference-এর ফাইললাইনকোডের লাইন
Lexer (৪৬)tokens.py, lexer.py১১৪৮৭
AST আর printer (৪৯)ast_nodes.py, ast_print.py৩৩৮২৫৮
Parser, recovery সহ (৪৭, ৪৮, ৫০)parser.py, errors.py২৯৯২৫০
Resolver (৫১)resolver.py১৭৭১৫১
Type checker (৫২)typechecker.py১৬৪১৪০
Interpreter (৫৬)interp.py, runtime.py১৯১১৪৪
Bytecode আর VM (৫৮, ৫৯)compiler.py, vm.py, disasm.py৩৮০৩২৪
Command linehaat.py৭৪৬২
Testtests/ (৪টি ফাইল)৪৫১৩৫৭
মোট১৮টি ফাইল২১৮৮১৭৭৩

দুটি জিনিস চোখে পড়ার মতো। প্রথমত, front end (lexer থেকে checker, AST আর printer-সহ) ১০৯২ লাইন, মোটের প্রায় অর্ধেক, আর test বাদ দিলে প্রায় ৬৩%; interpreter আর VM মিলে ৫৭১। একটি ভাষার নিয়ম ঠিকভাবে যাচাই করা, আর ভুলের ভালো বার্তা দেওয়া, চালানোর চেয়ে বেশি কাজ। দ্বিতীয়ত, test-এর লাইন প্রায় এক-পঞ্চমাংশ। বাস্তব compiler-এ test-এর ভাগ সাধারণত আরও বড়, কারণ প্রতিটি bug-এর জন্য একটি regression test জমা হয়।

পাতার ২২টি module-এর হিসাব। প্রতিটি আগের পর্বের পাতা থেকে হুবহু: ২১টি ফাইল যেমন ছিল তেমন কপি, আর p56/interp.py পর্ব ৫৬-এর তিনটি ব্লকের কোড হুবহু জোড়া (শুধু শেষের পরীক্ষার লাইন বাদ, ওপরে দুই লাইনের পরিচয়-comment).

ধাপফাইল (যে পর্বের পাতা থেকে)লাইন
Front end + type checkerp52/haat_front.py (৫২), p52/haat_check.py (৫২-এর তিনটি ব্লক, ৮০-এর পাতায় এভাবে জোড়া)২৬৯ + ৯২
Tree-walking interpreterp56/haat_front.py, p56/interp.py (৫৬-এর দুটি ব্লক আর run_src)১৬৫ + ৬৭
Bytecode compiler + VMp59/haat_front.py, haat_code.py, haat_vm.py (৫৮–৫৯), stack_vm.py (৫৯-এর দুটি ব্লক, ৬১-এর পাতায় জোড়া)২৬৯ + ৪৮ + ১৩৩ + ৫১
Haat IR, CFG, IR interpreterhaat_front.py, haat_ir.py, haat_gen.py (৬২)১৯১ + ২১৫ + ৬৪
SSA, dataflow, optimiserhaat_ssa.py (৬৩), haat_dfa.py (৬৪), haat_opt.py (৬৫)১৯৯ + ১০৮ + ১৮০
LLVM IRhaat_llvm.py, ll_mini.py (৬৮)১৭৪ + ৬৪
RISC-Vhaat_isel.py, rv_text.py (৬৯), haat_abi.py (৭১), haat_rv.py, rv_run.py (৭২)২৪০ + ৪০ + ৫৭ + ৮২ + ৫৪
WebAssemblyhaat_wasm.py (৭৩)২৫৪
নতুন, এই পর্বেরcapstone.py৬১

একটি প্রকৌশল-সমস্যা আছে। প্রতিটি পর্ব নিজের পাতাকে ছোট রাখতে reference-এর front end-এর নিজস্ব সংক্ষিপ্ত রূপ রেখেছিল, আর সবগুলোর নাম haat_front.py. পর্ব ৫২-এরটিতে resolver আছে, ৫৯-এরটিতে slot-সহ resolver, ৫৬-এরটিতে resolver নেই, ৬২-এরটিতে runtime-এর সাহায্যকারী function. চারটি একই নামে একই Python-এ থাকতে পারে না। সমাধান: প্রতিটিকে আলাদা ফোল্ডারে রাখা, আর একটি ছোট loader দিয়ে প্রতিটি পরিবারকে আলাদাভাবে import করা। এটিই capstone.py-এর কেন্দ্র:

OWN = ("haat_front", "haat_check", "interp", "haat_code", "haat_vm", "stack_vm")
def load(folder, *names):          # each old page keeps its own haat_front.py
    keep = {m: sys.modules.pop(m) for m in OWN if m in sys.modules}
    sys.path.insert(0, folder)
    try: return [importlib.import_module(n) for n in names]
    finally:
        sys.path.remove(folder)
        for m in OWN: sys.modules.pop(m, None)
        sys.modules.update(keep)
chk, = load("p52", "haat_check")   # পর্ব ৫২: type checker
itp, = load("p56", "interp")       # পর্ব ৫৬: tree-walking interpreter
svm, = load("p59", "stack_vm")     # পর্ব ৫৮–৫৯: bytecode compiler + stack VM

কৌশলটি Python-এর module cache (sys.modules) নিয়ে: import-এর আগে একই নামের পুরোনো module সরিয়ে রাখা, ফোল্ডারটিকে খোঁজার পথে প্রথমে বসানো, শেষে সব ফেরত দেওয়া। যে module একবার import হয়েছে, সে নিজের haat_front-এর reference ধরে রাখে। ফাইলে আরও আছে পর্ব ৭৩-এর run_wasm (সেখানকার শেষ ব্লক থেকে হুবহু), আর একটি তালিকা যা প্রতিটি back end-কে একই চেহারা দেয়: Haat source নেয়, ছাপা লাইনের তালিকা ফেরত দেয়, runtime error হলে সেটি শেষ লাইন। এই সমান চেহারাই অংশ ৬-এর differential test-কে সম্ভব করে।

৩ · ক্যাপস্টোনের program — গুদামের মজুদ রিপোর্ট

সব back end একই ভাষা সমর্থন করে না। পর্ব ৬২-এর Haat IR closure আর function-মান নেয় না, পর্ব ৭২-এর RISC-V back end Str নেয় না, পর্ব ৭৩-এর Wasm শুধু Str ছাপতে পারে, যোগ বা তুলনা করতে পারে না। তাই ক্যাপস্টোনের program লেখা হয়েছে এদের ছেদে: Int আর Bool, top-level function, if/else, while, recursion, top-level variable (একটি function থেকে বদলানোও), আর Int ও Bool-এর print. বাজারঘরের গুদামে আটটি পণ্যের মজুদ দেখে কোনগুলো আবার অর্ডার করতে হবে, কত ব্যাচে, আর মোট মূল্য কত:

// বাজারঘর: গুদামের মজুদ রিপোর্ট
var low = 0;
fn stock(item: Int) -> Int {
    return (item * 37 + 11) % 50;
}
fn needs_order(qty: Int, min: Int) -> Bool {
    return qty < min || qty % 10 == 0;
}
fn batches(qty: Int, size: Int) -> Int {
    if qty <= 0 { return 0; }
    return 1 + batches(qty - size, size);
}
fn mark() -> Int {
    low = low + 1;
    return low;
}
let shelf = 60;
let box = 12;
let min = shelf / 2 - 5;
var item = 1;
var worth = 0;
while item <= 8 {
    let q = stock(item);
    if needs_order(q, min) {
        print(item * 1000 + batches(shelf - q, box));
        mark();
    }
    worth = worth + q * (item * 5 + 20);
    item = item + 1;
}
print(low);
print(worth);
print(low >= 3 && worth / 100 > 50);

প্রতিটি অংশ কোনো ধাপকে পরীক্ষা করে। stock-এ %; needs_order-এ ||, তাই short-circuit-এর শাখা আর SSA-তে phi; batches recursion (৬০ − মজুদ সংখ্যক পণ্য ১২টির বাক্সে কত ব্যাচে); mark একটি top-level var বদলায় (সিদ্ধান্ত ১৮: low ঘোষিত function-এর আগে); let min = shelf / 2 - 5; optimiser-এর জন্য; শেষ লাইনে && দিয়ে একটি Bool. Reference-এ সত্যিকারের run (CPython 3.14.4):

~/haat $ python -B haat.py check stock.haat
ok
~/haat $ python -B haat.py run stock.haat
3004
4005
7004
8005
4
8620
true
~/haat $ python -B haat.py vm stock.haat     # একই সাত লাইন

আউটপুট পড়তে: 3004 মানে পণ্য ৩, চার ব্যাচ। পণ্য ৩-এর মজুদ (3 × 37 + 11) % 50 = 22, যা ২৫-এর কম; 60 − 22 = 38 পণ্য, ১২-র বাক্সে চার ব্যাচ। একইভাবে পণ্য ৪, ৭ আর ৮. চারটি পণ্য কম, মোট মূল্য ৮৬২০, আর শেষ শর্ত সত্য। এবার এই সাত লাইনই প্রতিটি পথের মাপকাঠি।

৪ · এক statement, এগারো ধাপ

পুরো program-এর বদলে একটি লাইন ধরে সব ধাপ দেখা যাক: লাইন ১৯, let min = shelf / 2 - 5;. নিচের stepper-এর প্রতিটি মান আসল আউটপুট থেকে নেওয়া: token আর AST reference-এর tokens আর ast থেকে, বাকিগুলো পাতার module থেকে (নিচের প্রথম ব্লকে সেগুলোই আবার চালানো হয়েছে)।

1source2lexer3parser4resolver5type checker6bytecode7Haat IR8optimiser9LLVM IR10RISC-V11WebAssembly
এই ধাপে
পর্ব
রূপ
  1. Source. লাইন ১৯-এ একটি top-level let. এর মান নির্ভর করে আগের লাইনের shelf-এর ওপর।
  2. Lexer (পর্ব ৪৬). নয়টি token, অবস্থান ১ থেকে গোনা: let 19:1-এ, / 19:17-এ। এই অবস্থান পরে প্রতিটি error message-এ ফেরে।
  3. Parser (পর্ব ৪৭–৪৯). Pratt parser shelf-এর পরে / দেখে (lbp 60), ডান operand পড়ে min_bp 61 দিয়ে, তাই - (lbp 50) সেখানে থামে। ফল: (- (/ shelf 2) 5).
  4. Resolver (পর্ব ৫১). shelf আগে ঘোষিত top-level let, ব্যবহার বৈধ (সিদ্ধান্ত ১৬)। Reference আর পর্ব ৫৯-এর VM-এ top-level নাম global slot পায়: shelf 5, min 7.
  5. Type checker (পর্ব ৫২). / আর - Int, Int নেয় (সিদ্ধান্ত ১১), তাই annotation ছাড়াই min : Int.
  6. Bytecode (পর্ব ৫৮). ছয়টি নির্দেশ, offset ১৪–১৯. Stack: 60 ওঠে, তারপর 2; DIV রাখে 30; 5 ওঠে; SUB রাখে 25; DEFINE_GLOBAL 7 সেটি global-এ রাখে।
  7. Haat IR (পর্ব ৬২). একই হিসাব three-address রূপে, প্রতিটি মধ্যবর্তী মান একটি temporary. IR-এ shelf আর min <main>-এর local, কারণ কোনো function এদের ব্যবহার করে না; শুধু low হয় @low.
  8. Optimiser (পর্ব ৬৫). Constant propagation জানে shelf = 60, আর ভাজক 2 শূন্য নয়, তাই ভাগটি fold করা নিরাপদ: চারটি নির্দেশ একটিতে, min = const 25. ভাজক শূন্য হতে পারলে এটি কখনো fold হতো না।
  9. LLVM IR (পর্ব ৬৮). পর্ব ৬৮-এর অনুবাদক optimise না করা SSA থেকে লেখে, তাই ভাগটি আছে। LLVM-এর sdiv শূন্যে undefined behaviour, তাই ভাগ যায় @haat.div-এ, অবস্থান 19:17 সহ।
  10. RISC-V (পর্ব ৬৯–৭২). প্রতিটি মান stack-এর একটি ঘরে: shelf −32(s0)-এ, min −72(s0)-এ। ভাজক একটি ধ্রুবক, শূন্য নয়, তাই instruction selection শূন্যের পরীক্ষা বাদ দিয়েছে; - 5 হয়েছে একটি addi, কারণ −5 ১২ বিটের immediate-এ ধরে।
  11. WebAssembly (পর্ব ৭৩). Top-level নাম এখানে Wasm global: shelf global 2, min global 4. i64.div_s শূন্যে আর INT_MIN / −1-এ trap করে; ভাজক 2 দুটির কোনোটি নয়, তাই বাড়তি পরীক্ষা নেই। একই statement, পাঁচটি ভিন্ন যন্ত্রের ভাষা।

লক্ষ করুন, একই নাম min একেক back end-এ একেক জায়গায় থাকে: VM-এর global slot, IR-এর local, RISC-V-এ stack-এর ঘর, Wasm-এর global. ভাষার অর্থ এক, কিন্তু মান কোথায় রাখা হবে তা প্রতিটি বাস্তবায়নের নিজের সিদ্ধান্ত। এবার পুরো program-এর জন্য একই যাত্রা নিজে চালিয়ে দেখুন। ব্লকটি প্রতিটি ধাপের আকার (token, নির্দেশ, byte) আর লাইন ১৯-এর রূপ ছাপে।

# stock.haat ধাপে ধাপে; প্রতিটি ধাপ আগের পর্বের module, হুবহু (capstone.py শুধু জোড়া লাগায়)
from capstone import *
from haat_wasm import Module, parse, wat
src = open("stock.haat", encoding="utf-8").read()
front, = load("p52", "haat_front")             # পর্ব ৪৬–৫১, পর্ব ৫২-এর পাতার রূপে
toks = front.tokenize(src)
print("46 lexer   :", len(toks), "token; line 19 =", " ".join(t.text for t in toks if t.line == 19))
program, res = front.front(src)
print("47-51 parse:", len(program.stmts), "top-level statements,", len(res.decls), "declarations resolved")
print("52 check   :", chk.check(src))
print("56 interp  :", " ".join(itp.run_src(src)))
main = svm.compile_src(src); dis = svm.disassemble(main).split("\n")
print("58 bytecode:", sum(len(c.instrs) for c in [main] + [k for k in main.consts if hasattr(k, "instrs")]),
      "instructions; line 19 =", " | ".join(" ".join(l.split()[1:3]) for l in dis[15:21]))
ir = compile_ir(src); m = ir.funcs["<main>"].blocks["B0"]
print("62 IR      :", sum(size(f) for f in ir.funcs.values()), "instructions;", " | ".join(map(str, m[4:8])))
ssa = map_module(compile_ir(src), to_ssa)
print("63 SSA     :", sum(i.kind == "phi" for f in ssa.funcs.values() for b in f.blocks.values() for i in b), "phi")
op = opt_module(src)
print("65 opt     :", sum(size(f) for f in op.funcs.values()), "instructions;", op.funcs["<main>"].blocks["B0"][4])
ll = to_llvm(src)[0].split("\n")
print("68 LLVM IR :", len(ll), "lines;", " | ".join(l.strip() for l in ll if "i64 60, i64 2" in l or "%min =" in l))
asm = compile_rv(src).split("\n"); k = asm.index("  li t1, 2")
print("72 RISC-V  :", sum(l.startswith("  ") for l in asm), "instructions;", " |".join(asm[k - 1:k + 4]))
w = Module(parse(src)); code = wat(w.bodies[0].code).split("\n")
print("73 Wasm    :", len(w.binary()), "bytes;", " |".join(code[8:13]))

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

46 lexer   : 222 token; line 19 = let min = shelf / 2 - 5 ;
47-51 parse: 14 top-level statements, 16 declarations resolved
52 check   : ok
56 interp  : 3004 4005 7004 8005 4 8620 true
58 bytecode: 125 instructions; line 19 = LOAD_GLOBAL 5 | CONST 7 | DIV | CONST 8 | SUB | DEFINE_GLOBAL 7
62 IR      : 80 instructions; t2 = const 2 | t3 = shelf / t2 | t4 = const 5 | min = t3 - t4
63 SSA     : 4 phi
65 opt     : 77 instructions; min = const 25
68 LLVM IR : 185 lines; %t3 = call i64 @haat.div(i64 60, i64 2, i64 19, i64 17) | %min = sub i64 %t3, 5
72 RISC-V  : 268 instructions;   ld t0, -32(s0) |  li t1, 2 |  div t0, t0, t1 |  addi t0, t0, -5 |  sd t0, -72(s0)
73 Wasm    : 755 bytes;   global.get 2 |  i64.const 2 |  i64.div_s |  i64.const 5 |  i64.sub

২২২টি token-এর শেষেরটি EOF; ১৬টি ঘোষণা মানে চারটি function, পাঁচটি parameter, ছয়টি top-level variable আর লুপের q. Stack bytecode-এ ১২৫টি নির্দেশ, three-address IR-এ ৮০টি, কারণ IR-এর একটি নির্দেশ দুটি operand নাম ধরে, আলাদা load লাগে না। RISC-V-এ ২৬৮টি, কারণ প্রতিটি মান stack-এর ঘরে আনা-নেওয়া হয়, আর প্রতিটি call-এর আগে-পরে call-গণনার পরীক্ষা (১০০০-এর সীমা, সিদ্ধান্ত ২৬)। চারটি phi: needs_order-এর ||-এর ফল, শেষ লাইনের &&-এর ফল, আর লুপের মাথায় item ও worth. Constant folding ৮০-কে ৭৭ করেছে: লাইন ১৯-এর চারটি নির্দেশ একটিতে।

৫ · সব back end, একই সাত লাইন

এবার আসল দাবি: প্রতিটি back end stock.haat চালিয়ে reference-এর সাত লাইন দেয়। Browser-এ আটটি back end Python-এ চলে: পর্ব ৫৬-এর interpreter, পর্ব ৫৯-এর VM, পর্ব ৬২-এর IR interpreter, SSA রূপ (phi-সহ চালানো), SSA থেকে আবার সাধারণ IR, optimised IR, পর্ব ৬৮-এর LLVM IR (একটি ছোট LLVM IR interpreter-এ, শুধু অর্থ যাচাইয়ের জন্য) আর পর্ব ৭২-এর RISC-V assembly (Python-এ লেখা RV64 interpreter-এ)। নবমটি সত্যিকারের: পর্ব ৭৩-এর Wasm byte browser-এর নিজের WebAssembly engine-এ। Reference-এর আউটপুট stock.out ফাইলে, ল্যাবে চালিয়ে রাখা।

# একই program, নয়টি back end: আটটি Python-এ, নবমটি browser-এর আসল WebAssembly engine-এ
from capstone import *
src = open("stock.haat", encoding="utf-8").read()
want = open("stock.out", encoding="utf-8").read().split("\n")[:-1]   # reference `run`, ল্যাবে
print("reference run :", " ".join(want))
for name, run in BACKENDS.items():
    out = run(src)
    print(f"{name:14}: {' '.join(out)}  {'==' if out == want else '!='}")
out = await run_wasm(compile_haat(src))
print(f"{'73 Wasm':14}: {' '.join(out)}  {'==' if out == want else '!='}")
quiet = lambda m: run_ir(m, out=lambda s: None)       # ফেরত: কয়টি IR নির্দেশ চলল
print("IR instructions executed:", quiet(compile_ir(src)), "->", quiet(opt_module(src)))
print("RISC-V instructions executed (rv_run):", run_program(compile_rv(src))[1])

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

reference run : 3004 4005 7004 8005 4 8620 true
56 interpreter: 3004 4005 7004 8005 4 8620 true  ==
59 VM         : 3004 4005 7004 8005 4 8620 true  ==
62 IR         : 3004 4005 7004 8005 4 8620 true  ==
63 SSA        : 3004 4005 7004 8005 4 8620 true  ==
63 SSA->IR    : 3004 4005 7004 8005 4 8620 true  ==
65 optimised  : 3004 4005 7004 8005 4 8620 true  ==
68 LLVM IR    : 3004 4005 7004 8005 4 8620 true  ==
72 RISC-V     : 3004 4005 7004 8005 4 8620 true  ==
73 Wasm       : 3004 4005 7004 8005 4 8620 true  ==
IR instructions executed: 469 -> 466
RISC-V instructions executed (rv_run): 1618

নয়টি back end, নয়বার ==. শেষ দুই লাইন দেখায় “একই আউটপুট” মানে “একই কাজ” নয়। IR interpreter ৪৬৯টি নির্দেশ চালিয়েছে, optimization-এর পরে ৪৬৬টি: লাইন ১৯ একবারই চলে, তাই তিনটি নির্দেশ বাঁচানো মানে মোটে তিনটি কম। Optimization-এর আসল লাভ আসে লুপের ভেতরে, যেখানে এই program-এ fold করার মতো কিছু নেই। RISC-V-এ ১৬১৮টি নির্দেশ, কারণ প্রতিটি IR মান stack-এর ঘর থেকে ld আর sd দিয়ে আনা-নেওয়া হয়। পর্ব ৭২-এ দেখেছেন, Clang -O2 একই ধরনের কাজ অনেক কম নির্দেশে করে (fact(20)-এ Haat ৬৮৯, Clang -O0 ৪৬৮, -O2 ৯০)।

Browser-এ আটটি back end-ই Python-এ “অনুকরণ”। আসল যন্ত্রে চালানো হয়েছে ল্যাবে: Node 24-এর WebAssembly engine, Zig 0.17.1-এর সঙ্গে আসা Clang 22.1.8 দিয়ে RISC-V assembly-কে আসল ELF ফাইলে assemble ও link করে Unicorn 2.1.4 CPU emulator-এ চালানো (Unicorn-এর Python binding BSD, engine GPLv2; শুধু ল্যাবে ব্যবহার), আর পর্ব ৬৮-এর LLVM IR-কে একই Clang দিয়ে x86-64 executable বানিয়ে চালানো। সত্যিকারের run:

~/haat/cap $ python showcase.py
reference haat.py check            ok
reference haat.py run              3004 4005 7004 8005 4 8620 true
reference haat.py vm               3004 4005 7004 8005 4 8620 true
page 56 interpreter                3004 4005 7004 8005 4 8620 true
page 59 VM                         3004 4005 7004 8005 4 8620 true
page 62 IR                         3004 4005 7004 8005 4 8620 true
page 63 SSA                        3004 4005 7004 8005 4 8620 true
page 63 SSA->IR                    3004 4005 7004 8005 4 8620 true
page 65 optimised                  3004 4005 7004 8005 4 8620 true
page 68 LLVM IR                    3004 4005 7004 8005 4 8620 true
page 72 RISC-V                     3004 4005 7004 8005 4 8620 true
Wasm, Node v24.15.0                3004 4005 7004 8005 4 8620 true
RISC-V Clang+Unicorn               3004 4005 7004 8005 4 8620 true
LLVM IR clang -O0 (x86-64 exe)     3004 4005 7004 8005 4 8620 true
LLVM IR clang -O2 (x86-64 exe)     3004 4005 7004 8005 4 8620 true
all identical to reference run: True
IR static 80 -> opt 77; dynamic 469 -> 466; phi 4
rv_run steps 1618 unicorn instructions (incl. runtime+_start) 2192 exit 0
wasm bytes 755 llvm lines 184
elf size 17216

Browser-এর rv_run গোনে ১৬১৮টি নির্দেশ, Unicorn ২১৯২টি। পার্থক্য runtime: rv_run haat_print_int-এর মতো runtime function Python-এ এক ধাপে করে, আর আসল ELF-এ সেগুলো পর্ব ৭২-এর ৩৮ লাইনের C runtime (haat_rt.c), যা সংখ্যা দশমিকে লিখতে লুপ চালায়, আর _start থেকে haat_main ডাকে। LLVM IR-এর লাইন এখানে ১৮৪, ব্লকে ১৮৫: ব্লক শেষের newline-এর পরের খালি টুকরোটিও গোনে।

৬ · Differential testing — হাজার program, বারোটি বাস্তবায়ন

একটি program-এ মিল ভালো লক্ষণ, প্রমাণ নয়। stock.haat-এ কোনো runtime error নেই, INT_MIN নেই, গভীর shadowing নেই। আরও শক্ত পরীক্ষা: হাজার হাজার program, যেগুলো মানুষ বেছে লেখেনি। পর্ব ৬২-এর haat_gen.py একটি seed থেকে এলোমেলো, কিন্তু reference-এর check পাস করা Haat program বানায়: wrap হওয়া Int হিসাব, C-ধাঁচের / আর %, শূন্য দিয়ে ভাগ, && ||, if/else, while, call, global আর shadowing. প্রতিটি program সব বাস্তবায়নে চলে, আর আউটপুট মেলানো হয় reference run-এর সঙ্গে। Reference এখানে test oracle: কোন উত্তর ঠিক, তা সে-ই বলে।

সংজ্ঞা ৮১.১ — back end-এর differential সঠিকতা

ধরা যাক P হলো সেই program-গুলোর সেট যা check পাস করে আর একটি back end B গ্রহণ করে (Unsupported দেয় না)। B differential-ভাবে সঠিক, যদি প্রতিটি p ∈ P-এর জন্য outB(p) = outref(p), যেখানে out মানে ছাপা লাইনের পুরো তালিকা, ক্রমসহ, আর runtime error হলে তার পুরো বার্তা (অবস্থানসহ) শেষ লাইন হিসেবে। Test এই দাবির একটি নমুনা পরীক্ষা করে, পুরো P নয়; তাই test কখনো সঠিকতা প্রমাণ করে না, শুধু একটি অমিল খুঁজে পেলে ভুল প্রমাণ করে।

সংজ্ঞায় তিনটি সূক্ষ্ম কথা। “ক্রমসহ পুরো তালিকা”: লাইনের set মেলালে evaluation order-এর bug (সিদ্ধান্ত ১২) ফসকে যায় (অনুশীলন ২)। Error-এর অবস্থানও তুলনার অংশ। আর Unsupported আলাদা গোনা হয়, কারণ সৎ “পারি না” আর ভুল উত্তর এক জিনিস নয়। ব্রাউজারে ছোট রূপ: ৪০টি seed, নয়টি back end. Reference-এর আউটপুট রাখা আছে digest হিসেবে (random_ref.txt: প্রতিটি seed-এর পুরো আউটপুটের SHA-256-এর প্রথম ১০টি hex অক্ষর, পর্ব ৬২-এর ল্যাবে বানানো)।

# পার্থক্য-পরীক্ষা: পর্ব ৬২-এর এলোমেলো program, প্রতিটি back end, reference-এর আউটপুটের সঙ্গে
from capstone import *
from haat_gen import gen_program
ref = open("random_ref.txt", encoding="utf-8").read().split()   # seed 0–199: reference `run`-এর digest
N, stops = 40, []
same = {name: 0 for name in [*BACKENDS, "73 Wasm"]}
for s in range(N):
    src = gen_program(s)
    for name, run in BACKENDS.items():
        out = run(src); same[name] += digest(out) == ref[s]
    if out and "runtime error" in out[-1]: stops.append((s, out[-1]))   # RISC-V-এর শেষ লাইন
    same["73 Wasm"] += digest(await run_wasm(compile_haat(src))) == ref[s]
for name, k in same.items(): print(f"{name:14} {k}/{N} identical")
print(f"{len(stops)} of {N} stop with a runtime error, e.g. seed {stops[0][0]}: {stops[0][1]}")

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

56 interpreter 40/40 identical
59 VM          40/40 identical
62 IR          40/40 identical
63 SSA         40/40 identical
63 SSA->IR     40/40 identical
65 optimised   40/40 identical
68 LLVM IR     40/40 identical
72 RISC-V      40/40 identical
73 Wasm        40/40 identical
4 of 40 stop with a runtime error, e.g. seed 12: 38:14: runtime error: division by zero

৩৬০টি তুলনা, সব মিল। চারটি program শূন্য দিয়ে ভাগে থেমেছে, আর সেই চারটিতেও প্রতিটি back end একই অবস্থান দিয়েছে: interpreter আর VM-এ Python-এর raise, RISC-V-এ haat_div_zero(38, 14)-এ লাফ, Wasm-এ host-এর error import, LLVM IR-এ @haat.div-এর ভেতরের পরীক্ষা। পাঁচটি আলাদা কৌশল, একই বার্তা।

ল্যাবে একই পরীক্ষা বড় আকারে: seed ০ থেকে ২৯৯৯, আর reference-এর ১০টি চালানো যায় এমন উদাহরণ, মোট ৩০১০টি program. মাপকাঠি সত্যিকারের python haat.py run, প্রতিটি program আলাদা process-এ; তুলনায় যোগ হয়েছে reference-এর vm, Node 24-এ Wasm, Clang + Unicorn-এ RISC-V আর Clang -O2-এ LLVM IR. তিনটি thread-এ পুরো run ৫১৩ সেকেন্ড (এক মেশিনে, শুধু ধারণার জন্য)। নিচের stepper ফল দেখায় সারি ধরে।

1reference vm2৫৬ interpreter, ৫৯ VM3৬২ IR, ৬৩ SSA ×2, ৬৫ opt4৬৮ LLVM IR ×25৭২ RISC-V ×26৭৩ Wasm (Node)7মোট
এই সারিতে
মিল
বাদ (Unsupported)
অমিল
  1. Reference নিজের সঙ্গে. haat.py vm আর haat.py run একই front end ব্যবহার করে, কিন্তু চালানোর কৌশল আলাদা। ৩০১০-এ ৩০১০. Reference-এর নিজের test-ও এই তুলনা করে।
  2. পাতার interpreter আর VM. পর্ব ৫৬ আর ৫৯-এর module সব Haat নেয়, closure আর Str-সহ: দুটিতেই ৩০১০টি মিল।
  3. Middle end. চারটি রূপ: IR, SSA, SSA থেকে ফেরত IR, optimised IR. প্রতিটিতে ৩০০৮টি মিল; বাদ দুটি উদাহরণ, counter আর nested, কারণ Haat IR v1 closure নেয় না। এলোমেলো program-গুলো first-order, তাই সবগুলোই চলেছে।
  4. LLVM IR. একই ৩০০৮টি, দুইভাবে: পাতার ছোট LLVM IR interpreter-এ, আর সত্যিকারের Clang 22 -O2-এ compile করা executable-এ। Clang-এর পুরো optimization pipeline-এর পরেও মিল আছে, অর্থাৎ পর্ব ৬৮-এর IR-এ এমন কোনো undefined behaviour নেই যা Clang কাজে লাগাতে পারত।
  5. RISC-V. পাতার rv_run আর আসল ELF + Unicorn, দুটিতেই ৩০০৩. বাদ সাতটি: closure-এর দুটি, আর পাঁচটি উদাহরণ যেগুলো Str ছাপে বা জোড়া দেয় (err_divzero-ও একটি Str ছাপে)।
  6. WebAssembly. Node 24-এ ৩০০৪: Wasm Str ছাপতে পারে, তাই err_divzero চলে, কিন্তু Str-এর যোগ বা তুলনা লাগে এমন চারটি উদাহরণ আর closure-এর দুটি বাদ।
  7. মোট. বারোটি বাস্তবায়নে ৩৬,০৮৮টি তুলনা, অমিল শূন্য। ৩০০০টি এলোমেলো program-এর ৩২৫টি শূন্য দিয়ে ভাগে থেমেছে, আর প্রতিটির বার্তা ও অবস্থান সব back end-এ এক।

শূন্য অমিল মানে কী নয়: এটি “কোনো bug নেই” প্রমাণ করে না। haat_gen কখনো closure, Str বা ১০০০-এর বেশি গভীর recursion বানায় না, তাই এসবের bug এই পরীক্ষা দেখতে পায় না। ভুল program (type error, syntax error) সে বানায়ই না, তাই error message-এর পরীক্ষা আলাদা: reference-এর err_*.haat ফাইল আর তাদের golden file. যে নিয়ম generator কখনো ছোঁয় না, সেখানে differential test অন্ধ। এই সীমার ভাষায় বলে generator-এর পক্ষপাত (bias). বড় compiler-এর fuzzer-গুলোর বড় অংশের কাজই এই পক্ষপাত কমানো।

৭ · অমিল থেকে bug-এর ঠিকানা

Differential test-এর সবচেয়ে বড় উপহার শুধু “কোথাও ভুল আছে” বলা নয়, “কোথায়” বলা। ধরুন একটি program-এ IR interpreter ঠিক উত্তর দেয়, SSA-ও দেয়, কিন্তু optimised IR ভুল দেয়। তাহলে bug প্রায় নিশ্চিত optimiser-এ, কারণ তার আগের সব ধাপ অন্য পথে পরীক্ষিত। Back end-এর তালিকা আসলে pipeline-এর বিভিন্ন বিন্দুতে বসানো পর্যবেক্ষক। পরীক্ষা করতে পর্ব ৬৫-এর optimiser-এ একটি ইচ্ছাকৃত ভুল নিয়ম চালু করা যাক: simplify(fn, wrong=True), যা x / x-কে 1 বানায়। Haat-এ এটি ভুল, কারণ x = 0 হলে reference division by zero দেয় (সিদ্ধান্ত ২৬)।

# ইচ্ছাকৃত bug: optimiser-এ ভুল নিয়ম x / x -> 1 (পর্ব ৬৫-এর simplify, wrong=True) — কে ধরে, কোন pass দায়ী?
import haat_opt
from capstone import *
src = """fn unit_share(qty: Int) -> Int {
    return qty / qty;
}
print(unit_share(7));
print(unit_share(0));
"""
def simplify_wrong(fn): return haat_opt.simplify(fn, wrong=True)
PASSES = [simplify_wrong if p is haat_opt.simplify else p for p in haat_opt.PIPELINE]
def buggy(s): m = compile_ir(s); optimize_module(m, PASSES); return run_lines(m)
want = itp.run_src(src)
print("56 interpreter:", want)
for name, run in {**BACKENDS, "65 buggy opt": buggy}.items():
    out = run(src)
    if out != want: print(f"{name}: DIFFERENT {out}")
print("all other back ends agree with the interpreter")
for k in range(1, len(PASSES) + 1):           # bisection: প্রথম কয়টি pass চালালে ফল বদলায়?
    m = compile_ir(src)
    for fn in m.funcs.values():
        for p in PASSES[:k]: p(fn)
    if run_lines(m) != want:
        print(f"first {k} passes -> wrong; culprit: {PASSES[k - 1].__name__}")
        print(show_ir(m.funcs["unit_share"])); break

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

56 interpreter: ['1', '2:16: runtime error: division by zero']
65 buggy opt: DIFFERENT ['1', '1']
all other back ends agree with the interpreter
first 2 passes -> wrong; culprit: simplify_wrong
fn unit_share(qty):
B0:
  t1 = const 1
  return t1

আটটি সঠিক back end interpreter-এর সঙ্গে একমত: unit_share(0)-এ লাইন ২, column ১৬-এর /-এ division by zero. শুধু ভুল optimiser ছাপে 1, তারপর আরও একটি 1. দ্বিতীয় অংশ pass-এর তালিকাকে ছোট করে দেখে: প্রথম kটি pass চালিয়ে ফল মেলায়, k = 1, 2, …. প্রথম pass (fold) পর্যন্ত ঠিক, দুটি pass পরে ভুল, তাই দায়ী দ্বিতীয়টি, simplify_wrong. শেষে ভুল IR: ভাগটি পুরো উধাও।

এই কৌশলের নাম pass bisection. Pass অনেক হলে ক্রমানুসারে না খুঁজে binary search চলে। LLVM-এ এর জন্য একটি option আছে বলে তাদের নথিতে উল্লেখ আছে (-opt-bisect-limit). দ্বিতীয় দরকারি কৌশল test-case reduction: অমিল দেখানো একটি বড় এলোমেলো program থেকে ধাপে ধাপে অংশ মুছে দেখা, অমিল টিকে থাকে কি না, যতক্ষণ না ছোটতম program বাকি থাকে। Andreas Zeller-এর delta debugging এর সাধারণ algorithm, আর John Regehr-এর দলের C-Reduce (২০১২) C compiler-এর জন্য বিশেষ রূপ। উপরের তিন লাইনের unit_share ঠিক এমন একটি “ছোট করা” program-এর মতো।

Compiler কোনো error না দিয়ে ভুল code বানালে তাকে বলে miscompilation: সবচেয়ে বিপজ্জনক bug, কারণ program-লেখক নিজের কোডে ভুল খুঁজবেন। এর উৎস প্রায়ই একটি optimization যা একটি সূক্ষ্ম শর্ত ভুলে গেছে: এখানে “ভাজক শূন্য হতে পারে”, বাস্তবে প্রায়ই overflow, aliasing বা evaluation order. পর্ব ৬৫-এর স্থায়ী নিয়ম: যে / বা % শূন্য দিয়ে ভাগ করতে পারে, তা কখনো fold, মোছা বা সরানো হয় না।

৮ · আপনার প্রজেক্ট — Haat-এ একটি feature, শুরু থেকে শেষ

এবার আপনার পালা। ক্যাপস্টোনের প্রজেক্ট: Haat-এ একটি নতুন feature যোগ করা, যা নিজের বানানো toolchain-এর প্রতিটি দরকারি ধাপ দিয়ে যায়, আর প্রতিটি ধাপে test থাকে। প্রথমে একটি গুরুত্বপূর্ণ সিদ্ধান্ত: feature-টি কি অন্য Haat-এ অনুবাদ করা যায় (desugaring), নাকি এর জন্য নতুন runtime ক্ষমতা লাগে? দুটি উদাহরণ দুই প্রান্তের।

for i in a..b { … }

Haat-এর বর্ধিত রূপ, পর্ব ৫৫-এ নিয়ম ৫৫.২ দিয়ে সংজ্ঞায়িত: a আগে, তারপর b, দুটিই একবার; i নেয় a থেকে b − 1; প্রতি round-এ নতুন let. Desugaring-এর পরে এটি শুধু var, let আর while. বদলায় lexer আর parser, আর যোগ হয় একটি desugar pass. Back end: কিছুই না।

[Int], [e1, e2], a[i]

Haat-এর বর্ধিত রূপ, পর্ব ২২-এর প্রস্তাব: array-র type, literal আর index; সীমার বাইরে runtime error: index 2 out of bounds for length 2. এটি অন্য Haat-এ লেখা যায় না, কারণ v1-এ কোনো মেমরি-কাঠামো নেই। তাই প্রতিটি ধাপ বদলায়, প্রতিটি back end-এ heap আর সীমা-পরীক্ষা লাগে।

for-এর দাবিটি ল্যাবে সত্যিকারের run দিয়ে যাচাই করা। stock.haat-এর while লুপকে লেখা হলো for item in 1..9 { … } দিয়ে, আর worth += … (পর্ব ৫৫-এর আরেকটি বর্ধিত রূপ) দিয়ে। পর্ব ৫৫-এর পাতার desugarer (haat_sugar.py আর দুটি ব্লক, হুবহু) সেটিকে core Haat-এ নামাল, তারপর core program গেল প্রতিটি back end-এ:

~/haat/cap $ python for_demo.py
reference on the sugar file: ["21:14: error: unexpected character '.'"]
var worth = 0;
{
    var __i1 = 1;
    let __end1 = 9;
    while __i1 < __end1 {
        let item = __i1;
        {
            let q = stock(item);
            ...
            worth = worth + q * (item * 5 + 20);
        }
        __i1 = __i1 + 1;
    }
}
ref run                3004 4005 7004 8005 4 8620 true
ref vm                 3004 4005 7004 8005 4 8620 true
56 interpreter         3004 4005 7004 8005 4 8620 true
   ... (মোট ১৩টি সারি, সবগুলো এই লাইনের মতো)
LLVM clang -O2         3004 4005 7004 8005 4 8620 true
identical: True 13

প্রথম লাইন: reference নিজে .. চেনে না (লাইন ২১-এর 1..9-এ lexer-এর error). তবু desugaring-এর পরে তেরোটি run হুবহু এক, আর কোনো back end-এর এক লাইনও বদলাতে হয়নি: পর্ব ৫৫-এর কৌশলের শক্তি। দাম: error message, formatter আর debugger-এ for হারায়, দেখা যায় __i1-এর মতো নাম। নিচের stepper দুই প্রজেক্ট মেলায়।

1অর্থ (spec)2lexer3parser, AST4resolver, checker5desugar / lower6interpreter, VM7IR আর native8test
এই ধাপে
for (desugar)
array (নতুন)
  1. অর্থ আগে. কোড লেখার আগে spec-এর ভাষায় লিখুন: কী আগে হিসাব হয়, কয়বার, কোন error, কোন অবস্থানে। for-এর জন্য পর্ব ৫৫ তা করেছে; array-র জন্য পর্ব ২২-এর typing rule আর runtime error-এর লেখা।
  2. Lexer. for আর in keyword, .. একটি নতুন token (দুই অক্ষরের, তাই longest match-এ .-এর আগে)। Array-র জন্য [ আর ]. Reference-এ আজ [ লিখলেই unexpected character '['.
  3. Parser আর AST. for একটি statement; a..b-এর .. কোনো expression operator নয়, তাই lo পড়া ..-তে থামে। Array literal একটি prefix রূপ, a[i] একটি postfix (call-এর মতো, lbp 80). Printer-এও দুটি নতুন রূপ।
  4. Resolver আর checker. for-এর জন্য কিছু লাগে না, কারণ desugar আগে চলে আর core-এর নিয়মই যথেষ্ট। Array-র জন্য নতুন typing rule (T-Arr, T-Index), খালি []-এর জন্য annotation বাধ্যতামূলক।
  5. Desugar বা lower. for এখানে core-এ নেমে যায়, gensym-এর নতুন নামসহ (hygiene, পর্ব ৫৫ আর ৭৮)। Array-র কোনো সহজ অনুবাদ নেই।
  6. Interpreter আর VM. for: কোনো বদল নেই। Array: নতুন runtime মান (Python list), VM-এ নতুন opcode (যেমন array বানানো, index পড়া), সীমা-পরীক্ষা আর ঠিক অবস্থানসহ error.
  7. IR আর native. for: কোনো বদল নেই, তেরোটি run তার প্রমাণ। Array: IR-এ load/store, RISC-V-এ runtime-এর একটি allocator আর মেমরি থেকে পড়া, Wasm-এ linear memory; আর কোনো back end-এ heap মানেই একদিন GC-এর প্রশ্ন (পর্ব ৭৫)।
  8. Test. দুটিতেই: golden file (ঠিক আউটপুট আর ঠিক error), differential test (সব back end একই), আর নতুন error-এর অবস্থান। for-এর বাড়তি test: desugar-এর আগে আর পরের program একই ফল দেয় কি না, a ≥ b হলে একবারও না চলে কি না।

প্রজেক্টের নির্দেশনা

  1. Feature বেছে নিন: x += e (সবচেয়ে সহজ), for, একটি ternary expression, অথবা array. প্রথমবার হলে desugaring-যোগ্য একটি নিন।
  2. এক পাতার spec লিখুন: বাক্যগঠন (EBNF), অর্থ (কী কোন ক্রমে, কয়বার), type rule, প্রতিটি নতুন error-এর লেখা আর অবস্থান, অন্তত তিনটি উদাহরণ ও প্রত্যাশিত আউটপুট; reference-এর “Spec decisions”-এর ধাঁচে।
  3. Test আগে: উদাহরণগুলো golden file (.haat আর .out), নতুন error-এর আলাদা ফাইল। এখন সব test ব্যর্থ হবে, আর হওয়া উচিত।
  4. ধাপে ধাপে: lexer, parser আর printer (round-trip: fmt দুবার চালালে একই), checker বা desugar, তারপর প্রতিটি back end; প্রতি ধাপে পুরোনো সব test আবার।
  5. Differential test: haat_gen.py-কে নতুন feature-সহ program বানাতে শেখান; desugaring হলে বাড়তি oracle হলো হাতে-লেখা core সংস্করণ।
  6. লিখে জানান: কোন ফাইলে কী আর কত লাইন বদলাল, কোন back end feature নেয় না আর কেন।

মূল্যায়নের চেকলিস্ট

৯ · বাস্তবের compiler আর কী যোগ করে

Haat-এর toolchain সম্পূর্ণ, কিন্তু খেলনা-আকারের। একটি production compiler একই কাঠামোর ওপর আরও অনেক কিছু রাখে। নিচের টেবিলে প্রধান ফাঁকগুলো, আর এই কোর্সে কোথায় তাদের ধারণা আছে:

বিষয়Haat-এর এই toolchainবাস্তব compiler (যেমন GCC, Clang)
Registerপ্রতিটি মান stack-এর ঘরে (পর্ব ৭২)Graph colouring বা linear scan (পর্ব ৭০)
OptimizationFold, CSE, DCE, একটি function-এর ভেতরেশত শত pass, loop আর inlining (পর্ব ৬৬, ৬৭), পুরো program জুড়ে
Program ভাগএক ফাইল, একবারেআলাদা compile, object file, linker (পর্ব ৭৪)
Heap আর GCNative back end-এ closure আর Str নেইAllocator, GC বা ownership (পর্ব ৭৫, ৭৬)
Errorপাতার front end প্রথম error-এ থামেRecovery, অনেক error, fix-it (পর্ব ৫০)
Toolশিক্ষার fmt, ছোট language serverDebug info, LSP, incremental (পর্ব ৮০)
চালানোর কৌশলInterpreter, VM, AOT আলাদাঅনেক runtime-এ interpreter + JIT একসাথে (পর্ব ৬১)

তবু কাঠামো একই। Clang-এর ভেতরেও lexer, parser, AST, semantic analysis, LLVM IR, pass-এর তালিকা, instruction selection, register allocation আর assembly লেখা আছে (পর্ব ৬৮)। পার্থক্য আকারে আর খুঁটিনাটিতে: লাখ লাখ লাইন, হাজারো test, আর বহু বছরের ব্যবহারে পাওয়া কোণার নিয়ম। Haat-এর ২১৮৮ লাইনের reference সেই বিশাল কাঠামোর একটি পরিষ্কার নকশা-চিত্র।

আরও গভীরে: “ছোট ভাষা, পুরো pipeline” পদ্ধতিতে compiler শেখানোর দুটি প্রভাবশালী ধারা আছে। Abdulaziz Ghuloum-এর ২০০৬ সালের প্রবন্ধ “An Incremental Approach to Compiler Construction” প্রথম দিন থেকেই একটি চালানো যায় এমন compiler রাখে, যা প্রথমে শুধু একটি সংখ্যা ফেরত দেয়, তারপর প্রতি ধাপে ভাষা একটু বাড়ে, আর প্রতি ধাপে পুরো test আবার চলে। Dipanwita Sarkar, Oscar Waddell আর R. Kent Dybvig-এর ২০০৪ সালের nanopass ধারা compiler-কে অনেক ছোট pass-এ ভাগ করে, প্রতিটির নিজের ছোট মধ্যবর্তী ভাষাসহ; পরে Andrew Keep আর Dybvig জানান, এই ধারায় একটি বাণিজ্যিক Scheme compiler (Chez Scheme) নতুন করে লেখা হয়েছে (২০১৩)। এই কোর্সের Haat-এর পথ দুটির মিশ্রণ: প্রতিটি পর্ব একটি pass, আর প্রতিটি pass reference-এর সঙ্গে মেলানো।

পরীক্ষা ও ইন্টারভিউতে: (১) একটি compiler-এর ধাপগুলো কী, প্রতিটির আউটপুট কী? Lexer → token, parser → AST, semantic analysis → যাচাই-করা ও type-যুক্ত AST, IR generation → three-address code/CFG, optimization → ছোট IR, code generation → assembly, assembler ও linker → executable. (২) Interpreter আর compiler-এর আউটপুট এক হলে কী প্রমাণ হয়? শুধু সেই ইনপুটে মিল; সঠিকতা নয়। (৩) Differential testing-এ oracle কে? যে বাস্তবায়নকে মাপকাঠি ধরা হয়, এখানে reference run; দুটির মধ্যে কে ভুল, তা অমিল একা বলে না। (৪) কেন optimizer x / x-কে 1 বানাতে পারে না? x = 0 হলে আসল program error দেয় (বা C-তে undefined behaviour); rewrite সেই আচরণ বদলায়। (৫) নতুন loop-কে desugar করলে কী লাভ, কী ক্ষতি? লাভ: back end বদলায় না; ক্ষতি: error message, formatter আর debugger-এ মূল রূপ হারায়।

১০ · AI-এর যুগে নিজের compiler

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

AI-এর সাধারণ ভুলকীভাবে ধরবেন
Parser-এ precedence বা associativity ভুল (a - b - c, -a * b, chained comparison)Reference-এর ast-এর সঙ্গে S-expression মেলানো; সিদ্ধান্ত ১০-এর উদাহরণ
এক ভাষার নিয়ম চাপানো: Python-এর floor division, unbounded int, বা C-র “overflow UB”-7 / 2, -7 % 2, INT_MIN / −1 পরীক্ষা (সিদ্ধান্ত ১৩)
“Optimization” যা অর্থ বদলায়: শূন্য দিয়ে ভাগ fold বা মোছা, call-এর ক্রম বদলআগে আর পরে চালিয়ে differential test; planted-bug পরীক্ষা
বানানো LLVM pass, Clang flag বা Wasm instructionসত্যিকারের Clang বা Node-এ চালানো; specification-এ নাম খোঁজা
Assembly বা bytecode যা আসল tool-এর আউটপুটের সঙ্গে মেলে না-S, dis, আসল assembler দিয়ে assemble করে চালানো
Runtime error-এর অবস্থান বা বার্তা ভুল, বা error-এর আগের আউটপুট হারানোGolden file-এ পুরো আউটপুট, error লাইনসহ, অক্ষরে অক্ষরে

AI-কে কাজে লাগানোর ভালো উপায়: নির্দিষ্ট spec দেওয়া, ছোট ধাপে কোড চাওয়া, আর test নিজে চালানো।

আমি Haat নামের একটি ছোট শিক্ষার ভাষায় for i in a..b { … } loop যোগ করছি। অর্থ: a আগে, তারপর b, দুটিই একবার হিসাব হয়; i নেয় a থেকে b − 1; প্রতি round-এ i একটি নতুন অপরিবর্তনীয় binding; body নিজের scope. Int 64-bit, overflow-এ wrap করে। ১. এই loop-কে var, let আর while দিয়ে লেখা core Haat-এ নামানোর একটি desugaring নিয়ম দাও, লুকোনো নাম কীভাবে বানাবে (hygiene) তা-সহ। ২. b সবচেয়ে বড় Int হলে তোমার নিয়মে overflow হয় কি না, ধাপে ধাপে দেখাও। ৩. আমার parser recursive descent + Pratt; lexer-এ .. token কোথায় আর কীভাবে যোগ করব, বলো। ৪. অন্তত ছয়টি test দাও: a ≥ b, b-তে side effect, body-তে shadowing, loop-এ বানানো closure, সবচেয়ে বড় Int, আর একটি type error-এর প্রত্যাশিত বার্তা। প্রত্যাশিত আউটপুট অনুমান করে লিখবে না; কোনগুলো আমাকে চালিয়ে দেখতে হবে, আলাদা করে বলো।

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

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

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

প্র ০১একই ভাষার জন্য interpreter, VM আর native compiler — বাস্তবে কেউ কি সবগুলো রাখে? কেন?

রাখে, আর খুব পুরোনো কাল থেকে। ১৯৭০-এর দশকে Niklaus Wirth-এর দল Pascal-এর একটি বহনযোগ্য compiler বানায় যা একটি কাল্পনিক stack-যন্ত্রের “P-code” লিখত; নতুন কম্পিউটারে Pascal আনতে শুধু P-code-এর একটি ছোট interpreter লিখলেই চলত। পরে UCSD Pascal এই ধারণাকে ছোট কম্পিউটারে জনপ্রিয় করে। Java-র JVM (১৯৯৫) আর CPython-এর bytecode একই সিদ্ধান্তের উত্তরসূরি: compile একবার, বহনযোগ্য একটি মধ্যবর্তী রূপে, তারপর প্রতিটি যন্ত্রে একটি VM.

একই ভাষার একাধিক কৌশল একসাথে থাকারও উদাহরণ অনেক। আধুনিক JavaScript engine-গুলো একটি interpreter দিয়ে শুরু করে, আর যে function বারবার চলে, তাকে ধাপে ধাপে বেশি optimize করা JIT-এ পাঠায় (পর্ব ৬১; engine-ভেদে বিবরণ আলাদা)। HotSpot JVM-এর ক্ষেত্রেও interpreter আর একাধিক JIT স্তর পাশাপাশি থাকে। কারণ একটি দ্বন্দ্ব: interpreter তাৎক্ষণিক শুরু হয়, debug করা সহজ, কিন্তু ধীর; native code দ্রুত, কিন্তু বানাতে সময় লাগে আর প্রতিটি যন্ত্রের জন্য আলাদা।

শিক্ষার দিক থেকে একাধিক back end-এর আরেকটি সুবিধা এই পর্বে দেখেছেন: তারা একে অপরের পরীক্ষক। Interpreter-টি সবচেয়ে সরল, প্রায় অর্থের সংজ্ঞার কাছাকাছি (পর্ব ৪০-এর big-step semantics-এর মতো দেখতে), তাই তাকে oracle ধরা স্বাভাবিক। জটিল back end-এর প্রতিটি ভুল সেই সরল সংস্করণের সঙ্গে অমিল হয়ে ধরা পড়ে। অনেক বাস্তব প্রকল্প ঠিক এই কারণে একটি “ধীর কিন্তু সরল” reference বাস্তবায়ন রাখে।

অসুবিধাও আছে: প্রতিটি নতুন feature এখন তিন জায়গায় লিখতে হয়, আর সূক্ষ্ম অমিল (যেমন evaluation order, overflow) তিনগুণ জায়গায় লুকাতে পারে। এই খরচ কমাতে অনেক ভাষা একটি সাধারণ IR বা bytecode-এ সব পথ এক করে।

মূল উপলব্ধি: একাধিক বাস্তবায়ন খরচ বাড়ায়, কিন্তু বহনযোগ্যতা, দ্রুত শুরু আর পারস্পরিক পরীক্ষার সুবিধা দেয়; সরলতমটি প্রায়ই অন্যদের মাপকাঠি হয়।

প্র ০২Compiler-এর differential testing আর fuzzing কীভাবে শিল্পে এল, আর এর সীমা কোথায়?

William McKeeman ১৯৯৮ সালে “Differential Testing for Software” প্রবন্ধে নামটি জনপ্রিয় করেন, C compiler-গুলোকে এলোমেলো program দিয়ে পরস্পরের সঙ্গে মিলিয়ে। ধারণাটি সরল: কোন উত্তর ঠিক, তা জানার দরকার নেই (test oracle সমস্যা এড়ানো); শুধু দেখতে হবে, একাধিক বাস্তবায়ন একমত কি না। অমিল মানে অন্তত একটিতে ভুল।

বড় মোড় আসে ২০১১ সালে, Utah বিশ্ববিদ্যালয়ের Xuejun Yang, Yang Chen, Eric Eide আর John Regehr-এর Csmith দিয়ে। Csmith এমন এলোমেলো C program বানায় যাতে undefined behaviour নেই, কারণ UB থাকলে compiler-গুলোর অমিল bug নয়, বৈধ। এই শর্ত রক্ষা করাই ছিল প্রধান কৌশল; Haat-এর ক্ষেত্রে সমস্যাটি নেই, কারণ Haat-এ UB নেই (wrap আর runtime error সংজ্ঞায়িত)। তাদের প্রবন্ধে GCC আর LLVM-এ কয়েকশো আগে-অজানা bug-এর কথা বলা হয়েছে। তিন বছর পরে Vu Le, Mehrdad Afshari আর Zhendong Su “equivalence modulo inputs” (EMI) দেখান: একটি program-এর যে অংশ কোনো নির্দিষ্ট ইনপুটে চলে না, তা বদলালে আউটপুট বদলানো উচিত নয়, তাই একটি compiler-কেই নিজের সঙ্গে মেলানো যায়। এটি metamorphic testing-এর একটি রূপ।

সীমাগুলো এই পর্বেই দেখেছেন। Generator-এর পক্ষপাত: যা সে বানায় না, তা পরীক্ষাও হয় না। সব বাস্তবায়ন একই ভুল করলে অমিল আসে না (যেমন সবাই একই ভুল spec পড়লে)। আর অমিল থেকে ছোট, পড়ার মতো উদাহরণে আসতে test-case reduction লাগে; Regehr-এর দলের C-Reduce সেই কাজের জন্যই। ফলে fuzzing প্রমাণের বিকল্প নয়: CompCert-এর মতো verified compiler (পর্ব ৪৪) অন্য পথে যায়, সঠিকতা গাণিতিকভাবে প্রমাণ করে। Csmith-এর প্রবন্ধে এমন উল্লেখ আছে যে CompCert-এর প্রমাণিত অংশে তারা ভুল code বানানোর bug পায়নি, যদিও প্রমাণের বাইরের অংশে পেয়েছিল।

মূল উপলব্ধি: Differential testing সস্তা আর শক্তিশালী, কারণ ঠিক উত্তর জানতে হয় না; কিন্তু এটি শুধু ততটুকু দেখে যতটুকু generator ছোঁয়, আর সবাই একই ভুল করলে চুপ থাকে।

প্র ০৩Haat-এর compiler কি Haat-এ লেখা উচিত? Self-hosting-এর লাভ আর ফাঁদ কী?

একটি compiler যখন নিজের ভাষাতেই লেখা হয়, তাকে বলে self-hosting. C, Go, Rust, OCaml সহ অনেক ভাষার প্রধান compiler নিজের ভাষায়। প্রথম সংস্করণটি অবশ্য অন্য ভাষায় লিখতে হয়, অথবা আগের একটি সংস্করণ দিয়ে compile করতে হয়: এই প্রক্রিয়ার নাম bootstrapping, আর পর্ব ০৪-এর T-diagram ঠিক এটিই আঁকে।

লাভ তিনটি। প্রথমত, compiler নিজেই ভাষার সবচেয়ে বড় আর কঠিন test: ভাষাটি দিয়ে একটি জটিল program লেখা যায় কি না, তা নিজের ঘরেই প্রমাণ। দ্বিতীয়ত, ভাষার নির্মাতারা প্রতিদিন নিজের ভাষা ব্যবহার করেন, তাই অসুবিধাগুলো আগে টের পান। তৃতীয়ত, contributor-দের অন্য ভাষা শিখতে হয় না।

Haat v1-এ এটি আজ অসম্ভব, আর কেন অসম্ভব তা শিক্ষণীয়। একটি lexer-এর জন্য string থেকে অক্ষর আলাদা করা লাগে, Haat-এর Str-এ তা নেই (শুধু যোগ আর তুলনা)। AST রাখতে record বা algebraic data type লাগে (পর্ব ২৪), token-এর তালিকা রাখতে array বা list, symbol table-এর জন্য map. ফাইল পড়ার উপায়ও নেই। অর্থাৎ self-hosting-এর পথ মানে অংশ ৮-এর মতো অনেকগুলো feature-প্রজেক্ট পরপর।

ফাঁদও আছে। Ken Thompson ১৯৮৪ সালের Turing Award বক্তৃতা “Reflections on Trusting Trust”-এ দেখান, একটি self-hosting compiler-এর binary-তে এমন কিছু লুকানো থাকতে পারে যা source পড়ে ধরা যায় না, কারণ compiler নিজেকে compile করার সময় সেটি আবার ঢুকিয়ে দেয়। প্রতিরক্ষার একটি পরিচিত উপায় হলো স্বাধীন দুটি compiler দিয়ে bootstrapping করে ফল মেলানো, যা David A. Wheeler “diverse double-compiling” নামে বিশ্লেষণ করেছেন: এটিও আসলে differential testing-এর একটি রূপ। সাম্প্রতিক কিছু প্রকল্প একটি খুব ছোট, হাতে যাচাই করা বীজ থেকে পুরো toolchain গড়ে তোলার চেষ্টা করে।

মূল উপলব্ধি: Self-hosting একটি ভাষার পরিণত হওয়ার চিহ্ন, কারণ তার জন্য string, data structure আর IO লাগে; আর এর বিশ্বাসযোগ্যতার প্রশ্নের উত্তরও শেষ পর্যন্ত স্বাধীন বাস্তবায়নের তুলনা।

প্র ০৪নতুন feature: front end-এ desugar করবেন, নাকি back end পর্যন্ত আলাদা রূপে নেবেন?

অংশ ৮-এ দেখেছেন, for-কে desugar করলে তেরোটি back end এক লাইন না বদলে কাজ করে। এটি আকর্ষণীয়, কারণ back end যত বেশি, প্রতিটি নতুন রূপের খরচ তত বেশি। Scheme-এর ঐতিহ্য এর চরম রূপ: খুব ছোট core, বাকি সব macro বা desugaring. Haskell-এর compiler GHC-ও বড় source ভাষাকে একটি ছোট typed core ভাষায় নামায় বলে পরিচিত।

কিন্তু মূল রূপ বেশিদিন রাখার কারণও আছে। প্রথম, error message: desugar করার পরে checker যদি __i1-এর কথা বলে, ব্যবহারকারী বুঝবেন না। পর্ব ৫৫-এ তাই f-string-এর জন্য উৎসের অবস্থান মনে রাখার কৌশল দেখেছেন। দ্বিতীয়, tool: formatter, language server আর debugger-এর দরকার ব্যবহারকারীর লেখা রূপ (পর্ব ৮০)। তৃতীয়, optimization: for জানলে compiler সহজেই জানে লুপ কতবার চলবে, যা loop optimization-এর জন্য মূল্যবান তথ্য (পর্ব ৬৬); while-এ নামানোর পরে সেই তথ্য আবার খুঁজে বের করতে হয়।

বাস্তবের compiler তাই সাধারণত মাঝের পথ নেয়: কয়েক স্তরের IR, প্রতিটিতে একটু করে নামানো। CPython for-কে AST-এ রাখে আর bytecode বানানোর সময় নামায় (পর্ব ৫৫, অংশ ৬)। Rust-এর compiler বলে জানা যায় AST থেকে HIR, তারপর MIR, তারপর LLVM IR-এ যায়; borrow checking-এর মতো বিশ্লেষণ MIR-এর মতো নিচের স্তরে হয়, আর ব্যবহারকারীর লেখা রূপ উঁচু স্তরে থাকে বার্তার জন্য (বিবরণ সংস্করণভেদে বদলায়)। Nanopass ধারা এই ভাবনার আরও সূক্ষ্ম রূপ: প্রতিটি pass শুধু একটি জিনিস নামায়।

একটি ব্যবহারিক নিয়ম: যে feature-এর অর্থ পুরোপুরি পুরোনো feature দিয়ে লেখা যায়, তাকে আগে desugar করুন, কিন্তু উৎসের অবস্থান সঙ্গে রাখুন; যে feature নতুন runtime ক্ষমতা চায় (array, exception, closure), তাকে নিজের রূপে নামাতে হবে যতদূর না পর্যন্ত কোনো নিচের IR তা প্রকাশ করতে পারে।

মূল উপলব্ধি: Desugaring back end-এর কাজ বাঁচায়, কিন্তু তথ্য হারায়; কোথায় নামাবেন, তা নির্ভর করে error message, tool আর optimization-এর কোন তথ্য কোন স্তরে লাগবে তার ওপর।

প্র ০৫Haat-এর toolchain থেকে একটি “আসল” ভাষার বাস্তবায়নে পৌঁছাতে কোন কাজগুলো সবচেয়ে বড়?

প্রথম বড় কাজ মেমরি। আজ native back end-গুলো শুধু Int আর Bool নেয়, কারণ এদের মান একটি register বা stack-এর ঘরে ধরে। Closure, string বা array মানে heap, আর heap মানে কে কখন মেমরি ফেরত দেবে: reference counting, tracing GC (পর্ব ৭৫) বা Rust-এর মতো ownership (পর্ব ৭৬)। সঙ্গে আসে GC-কে stack-এর কোন ঘরে pointer আছে তা জানানো, যা native code-এ সহজ নয়।

দ্বিতীয় কাজ গতি। পর্ব ৭২-এ fact(20) Haat-এর back end-এ ৬৮৯টি নির্দেশ নিয়েছে, একই হিসাব Clang -O0-এ ৪৬৮টি আর -O2-এ ৯০টি। পার্থক্যের বড় অংশ register allocation (পর্ব ৭০, যা ৭২-এ ব্যবহার করা হয়নি), call-এর বাড়তি পরীক্ষা, আর loop ও inlining-এর optimization. এগুলো যোগ করলে প্রতিটির সঙ্গে নতুন miscompilation-এর সুযোগও আসে, তাই differential test আরও জরুরি হয়।

তৃতীয় কাজ বড় program-এর ব্যবস্থা: module আর আলাদা compile (পর্ব ১৮, ৭৪), একটি standard library, অন্য ভাষার function ডাকার উপায় (FFI, যা ABI-এর ওপর দাঁড়ায়, পর্ব ৭১), আর package manager. চতুর্থ কাজ মানুষের অভিজ্ঞতা: একসাথে অনেক error দেখানো (পর্ব ৫০), debug info, language server, incremental compile (পর্ব ৮০)।

শেষে আস্থা। একটি ভাষাকে মানুষ তখনই ব্যবহার করে যখন তার বাস্তবায়নে আস্থা আসে: একটি লেখা specification, বড় conformance test suite, আর বহু বছর ধরে নানা program-এ চলার ইতিহাস। কিছু প্রকল্প আরও এক ধাপ যায়: CompCert-এর মতো compiler-এর সঠিকতা যন্ত্রে-যাচাই করা প্রমাণে (পর্ব ৪৪)। Haat-এর reference আর তার ৩২টি test এই আস্থার ক্ষুদ্র সংস্করণ; এই পর্বের ৩৬,০৮৮টি তুলনা তার পরের ধাপ।

মূল উপলব্ধি: একটি কার্যকর toolchain থেকে একটি ব্যবহারযোগ্য ভাষায় যাওয়ার পথ মূলত মেমরি, গতি, বড় program-এর ব্যবস্থা আর আস্থা; প্রতিটির ধারণা এই কোর্সে আছে, বাকিটা প্রকৌশলের পরিশ্রম।

অনুশীলন

প্রথমে নিজে করুন, তারপর উত্তর খুলে মেলান। আউটপুটগুলো এই পাতার module, Haat reference আর ল্যাবের সত্যিকারের run-এ মেলানো।

  1. বাস্তবায়ন — desugar ছাড়া for: ধরুন for-কে desugar না করে AST-এ একটি For(name, lo, hi, body) node রাখলেন, আর পর্ব ৬২-এর Lower-কে সরাসরি Haat IR বানাতে শেখাতে চান। for i in 1..4 { print(i); }-এর জন্য কোন IR বানাবেন? নিয়ম ৫৫.২-এর কোন শর্ত IR-এ কোথায় রক্ষা পায়, আর কীভাবে যাচাই করবেন যে আপনার নতুন lowering আর desugaring-এর পথ একই কাজ করে?

    লক্ষ্য হলো desugaring-এর পথে যা আসে, ঠিক সেই আকার। ল্যাবে পর্ব ৫৫-এর desugarer আর পর্ব ৬২-এর compile_ir চালিয়ে পাওয়া আসল IR:

    fn <main>():
    B0:
      __i1 = const 1
      __end1 = const 4
      jump B1
    B1:
      t1 = __i1 < __end1
      branch t1 B2 B3
    B2:
      i = __i1
      print i
      t2 = const 1
      __i1 = __i1 + t2
      jump B1
    B3:
      t3 = const ()
      return t3

    আউটপুট 1, 2, 3. শর্তগুলো: (ক) lo আর hi একবার, B0-তে, লুপের বাইরে; hi যদি একটি call হতো, call-টি B0-তে একবার থাকত। (খ) half-open: B1-এর <. (গ) প্রতি round-এ নতুন i: B2-এর i = __i1; IR-এ closure নেই বলে “নতুন binding” আর “একই নামে কপি” এক জিনিস, কিন্তু closure-সহ back end-এ (৫৬, ৫৯) এটি প্রতি round-এ নতুন ঘর হতে হবে। (ঘ) counter বাড়ে body-র পরে, body i বদলাতে পারে না। Lower-এ কাজটি তাই চারটি label আর পাঁচ-ছয়টি নির্দেশ, while-এর lowering-এর প্রায় কপি। যাচাই: একই program দুই পথে IR বানিয়ে IR interpreter-এ চালানো আর আউটপুট মেলানো, আর এলোমেলো for-ওয়ালা program দিয়ে differential test; সঙ্গে a ≥ b, hi-তে side effect আর hi = সবচেয়ে বড় Int-এর বিশেষ test. লক্ষ করুন optimiser এখানে i-এর copy মুছে দেয় (print __i1), কারণ কোনো closure নেই।

  2. ভুল খুঁজুন: একজন differential test-এর তুলনা লিখলেন এভাবে: same = set(out_a) == set(out_b), আর শুধু stdout ধরলেন, stderr নয়। এতে কোন দুই ধরনের bug ফসকে যাবে? প্রতিটির জন্য একটি ছোট Haat program দিন, আর ঠিক তুলনাটি লিখুন।

    (১) ক্রমের bug. Set ক্রম আর পুনরাবৃত্তি ভুলে যায়। ধরুন একটি back end call-এর argument ডান থেকে বাঁয়ে হিসাব করে (সিদ্ধান্ত ১২ ভাঙে):

    fn show(n: Int) -> Int { print(n); return n; }
    fn pair(a: Int, b: Int) -> Int { return a - b; }
    print(pair(show(1), show(2)));

    Reference-এর সত্যিকারের run ছাপে 1, 2, -1. ভুল back end ছাপত 2, 1, -1: set একই, তাই তুলনা “মিল” বলে। আরও খারাপ: যে back end print দুবার করে, তার set-ও একই। (২) runtime error-এর bug. Reference error-কে stderr-এ লেখে। যে back end division by zero-তে চুপচাপ 0 ধরে এগিয়ে যায়, বা ভুল অবস্থান দেয়, তার stdout হয়তো একই, বা শুধু একটি লাইন কম; stderr না দেখলে অবস্থানের ভুল ধরা পড়বেই না। উদাহরণ: print(1); print(7 / (3 - 3)); print(2);, যেখানে reference-এর সত্যিকারের উত্তর 1, তারপর 1:19: runtime error: division by zero, আর 2 কখনো নয়। ঠিক তুলনা: stdout-এর লাইন, তারপর stderr-এর লাইন, এক তালিকায়, ক্রমসহ: out_a == out_b (list, set নয়)। এই পাতার capstone.py আর ল্যাবের ref_cli ঠিক এটাই করে, আর digest-ও পুরো ক্রমিক লেখার ওপর।

  3. Trace — VM আর IR পাশাপাশি: stock.haat-এর লাইন ১৯-এর bytecode: 14 LOAD_GLOBAL 5 ; shelf, 15 CONST 7 ; 2, 16 DIV, 17 CONST 8 ; 5, 18 SUB, 19 DEFINE_GLOBAL 7 ; min. ধরুন global 5-এ আছে 60. (ক) প্রতিটি নির্দেশের পরে operand stack লিখুন। (খ) Optimise না করা Haat IR-এ এই লাইনের জন্য কয়টি নির্দেশ চলে, optimise করার পরে কয়টি? (গ) shelf-এর মান 0 হলে কোনটি বদলাবে?

    (ক) 14-এর পরে [60]; 15-এর পরে [60, 2]; 16-এর পরে [30]; 17-এর পরে [30, 5]; 18-এর পরে [25]; 19-এর পরে [], আর global 7 = 25. (খ) আগে চারটি (t2 = const 2, t3 = shelf / t2, t4 = const 5, min = t3 - t4), পরে একটি (min = const 25); তাই অংশ ৫-এ মোট চলা নির্দেশ ৪৬৯ থেকে ৪৬৬. (গ) shelf = 0 হলে ভাগফল 0, min = −5; ভাজক তখনো 2, তাই কোনো error নয়, আর optimiser তখনো fold করতে পারে (−5). সাবধান: লাইনটি যদি হতো let min = 2 / shelf - 5; আর shelf = 0, তাহলে reference দিত 19:13: runtime error: division by zero (/-এর অবস্থানে; ল্যাবে চালিয়ে দেখা), আর optimiser-কে ভাগটি রেখে দিতে হতো, কারণ ভাজক 0 জানা থাকলেও fold করা নিষেধ: error-টিই program-এর আচরণ।

  4. নকশা — array, শুরু থেকে শেষ: পর্ব ২২-এর প্রস্তাবিত array ([Int], [e1, e2], a[i]) Haat-এ যোগ করার পরিকল্পনা লিখুন: প্রতিটি ধাপে কী বদলাবে, নতুন runtime error কোথায় ধরা হবে, আর কোন back end প্রথম সংস্করণে Unsupported রাখা যুক্তিসঙ্গত। অন্তত পাঁচটি test-এর তালিকা দিন।

    Lexer: [ আর ]. Parser/AST: ArrayLit(items) prefix অবস্থানে, Index(target, index) postfix (call-এর মতো, lbp 80), printer-এ দুটি রূপ; type-এর ভাষায় [T]. Assignment-এর লক্ষ্য (a[i] = e;) চাইলে সিদ্ধান্ত ৯ বদলাতে হবে, তাই প্রথম সংস্করণে array অপরিবর্তনীয় রাখা সহজ। Checker: T-Arr (সব উপাদান এক type, n ≥ 1), T-Index (target [T], index Int, ফল T), খালি []-এ annotation বাধ্যতামূলক; == array-তে নিষেধ রাখা যায় (সিদ্ধান্ত ১১-এর মতো)। Interpreter/VM: মান হিসেবে Python list; VM-এ নতুন opcode, যেমন MAKE_ARRAY n আর INDEX; সীমা-পরীক্ষা, বার্তা index 2 out of bounds for length 2, অবস্থান [-এ (সিদ্ধান্ত ২৪-এর ধাঁচে: যে operator ব্যর্থ, তার অবস্থানে)। IR: নতুন নির্দেশ (alloc, load, store) বা runtime call; optimiser-কে শেখাতে হবে যে load-এর ক্রম store-এর সঙ্গে বদলানো যায় না। RISC-V: runtime-এ একটি সরল allocator (পর্ব ৭২-এর C runtime-এ), header-এ দৈর্ঘ্য (পর্ব ২২-এর নকশা), ld দিয়ে পড়া, সীমা-পরীক্ষার পথে haat_div_zero-এর মতো একটি runtime function. Wasm: linear memory আর একটি bump allocator. প্রথম সংস্করণে native back end-গুলোকে Unsupported রাখা যুক্তিসঙ্গত, যদি interpreter আর VM পুরো feature নেয় আর differential test সেগুলোর ওপর চলে; GC ছাড়া heap কখনো ফেরত আসবে না, সেটি README-তে লিখে রাখুন।

    Test: (১) let xs = [2, 1]; print(xs[0] + xs[1]); → 3. (২) সীমার বাইরে xs[2]: আগে ছাপা লাইন থাকে, তারপর ঠিক অবস্থানে error. (৩) ঋণাত্মক index. (৪) let e: [Int] = []; বৈধ, annotation ছাড়া [] type error. (৫) [1, true] type mismatch, দ্বিতীয় উপাদানের অবস্থানে। (৬) index-এ side effect আর evaluation order: target আগে, index পরে (সিদ্ধান্ত ১২)। (৭) সব back end-এ differential test, Unsupported আলাদা গোনা।

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

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

ক্রমএকটি Haat program-কে RISC-V-এ চালানোর জন্য ধাপগুলো কোন ক্রমে চলে, সাজান (▲▼ চেপে সরান):

  1. Lexer: অক্ষর থেকে token
  2. Parser: token থেকে AST
  3. Resolver আর type checker: নাম আর type যাচাই
  4. Lowering: AST থেকে Haat IR আর CFG
  5. Optimiser: IR-এর ওপর pass
  6. Instruction selection, frame আর assemble ও link

একটি compiler-এর differential test-এ একটি program interpreter, VM, optimise না করা IR আর SSA-তে একই আউটপুট দেয়, কিন্তু optimised IR-এ আলাদা। Bug সবচেয়ে সম্ভবত কোথায়?

  • Lexer বা parser-এ
  • AST থেকে IR-এ নামানোর ধাপে
  • Optimiser-এর কোনো pass-এ
  • Interpreter-এ, কারণ সে oracle

Haat-এ let min = shelf / 2 - 5; লাইনের জন্য একটি RISC-V back end div নির্দেশের আগে শূন্যের কোনো পরীক্ষা বসায়নি। এটি কেন ঠিক?

  • RISC-V-এর div শূন্যে নিজেই trap করে
  • ভাজক ধ্রুবক 2, যা কখনো শূন্য হতে পারে না
  • Haat-এ শূন্য দিয়ে ভাগ undefined behaviour, তাই যা খুশি হতে পারে
  • Type checker আগেই প্রমাণ করেছে কোনো ভাজক শূন্য নয়

একটি ভাষায় for i in a..b { … } যোগ করা হলো, আর front end-এ desugar করে var, let আর while-এ নামানো হলো। কোন অংশগুলোকে বদলাতে হবে না?

  • Desugaring-এর পরের সব ধাপ: interpreter, VM, IR আর native back end
  • Lexer
  • Parser
  • Test suite

দুটি back end-এর আউটপুট তুলনা করা হলো ছাপা লাইনের set দিয়ে (ক্রম বাদ দিয়ে)। কোন ধরনের bug এই তুলনায় সবচেয়ে সহজে ফসকে যায়?

  • Wrap না করা overflow, যাতে একটি সংখ্যা ভুল ছাপা হয়
  • একটি print একেবারে বাদ পড়া
  • Type checker-এর ভুল
  • Evaluation order-এর bug, যাতে একই লাইন অন্য ক্রমে ছাপা হয়

Haat-এর (৬৪-bit wrap, শূন্য দিয়ে ভাগ = runtime error) একটি optimiser x / x-কে 1 বানায়। fn f(x: Int) -> Int { return x / x; }-এর জন্য কোনটি ঠিক?

  • Rewrite ঠিক, কারণ Int-এ সব হিসাব wrap করে
  • Rewrite ভুল, কারণ f(0)-এ আসল program runtime error দেয়
  • Rewrite ভুল, কারণ INT_MIN / INT_MIN-এর ফল আলাদা
  • Rewrite ঠিক, তবে শুধু x ধ্রুবক হলে কাজে লাগে

একটি এলোমেলো program generator শুধু এমন program বানায় যা type check পাস করে আর closure ব্যবহার করে না। হাজার program-এ সব back end একমত হলো। কোনটি এই test-এ যাচাই হয়নি?

  • Runtime error-এর অবস্থান
  • If আর while-এর অনুবাদ
  • Type error আর syntax error-এর বার্তা
  • Function থেকে global বদলানো

শব্দকোষ

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

মনে রাখুন

  1. এক কাঠামো, তিন শাখা: একই front end থেকে interpreter, bytecode VM আর IR-এর পথ; IR থেকে LLVM IR, RISC-V আর WebAssembly. Reference-এ ২১৮৮ লাইন, যার অর্ধেকের বেশি front end আর test.
  2. একই আউটপুট: stock.haat পনেরোটি run-এ হুবহু একই সাত লাইন দেয়, কিন্তু কাজের পরিমাণ আলাদা (IR-এ ৪৬৯ নির্দেশ, RISC-V-এ ১৬১৮)।
  3. Differential test: ৩০১০টি program, ১২টি বাস্তবায়ন, ৩৬,০৮৮টি তুলনা, শূন্য অমিল; Unsupported আলাদা গোনা। এটি bug-এর অনুপস্থিতির প্রমাণ নয়, generator যা ছোঁয় শুধু তার নমুনা।
  4. অমিলই ঠিকানা: কোন back end আলাদা, তা দেখে দায়ী ধাপ; pass bisection আর test-case reduction দিয়ে দায়ী pass আর ছোটতম program.
  5. Feature যোগ: আগে অর্থ আর test, তারপর কোড। Desugaring-যোগ্য feature (for) back end ছোঁয় না; নতুন runtime ক্ষমতার feature (array) প্রতিটি ধাপ ছোঁয়।

পরের পর্বে: মডিউল ১৪ শুরু, পরীক্ষা আর ইন্টারভিউর প্রস্তুতি। পর্ব ৮২-এ compiler-এর হাতে-কলমে সমস্যা: three-address code, activation record, SSA আর register allocation, ধাপে ধাপে সমাধানসহ।

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

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