এই পর্বে যা শিখবেন
- কেন গদ্যে লেখা ভাষার spec যথেষ্ট নয়, আর operational semantics কোন প্রশ্নের নিশ্চিত উত্তর দেয়
- Haat-core-এর পূর্ণ small-step আর big-step নিয়ম পড়া ও লেখা, আর হাতে trace ও derivation গাছ বানানো
- Stuck configuration, runtime error আর non-termination-এর পার্থক্য দুই ধরনের semantics-এ দেখা
- Determinism induction দিয়ে প্রমাণ করা, আর small-step ও big-step-এর সমতুল্যতার প্রমাণের কাঠামো বোঝা
- Evaluation context থেকে abstract machine হয়ে interpreter পর্যন্ত পথটি চেনা, আর নিজের interpreter-কে reference-এর সঙ্গে মিলিয়ে যাচাই করা
১ · কেন formal semantics — গদ্যের spec কোথায় ফাঁক রাখে
মায়ের হাতের রান্নার রেসিপিতে লেখা থাকে “লবণ পরিমাণমতো”। অভিজ্ঞ রাঁধুনির কাছে এটুকুই যথেষ্ট, কিন্তু বড় রেস্তোরাঁয় পাঁচজন রাঁধুনি একই পদ রাঁধলে স্বাদ এক রাখতে লাগে গ্রাম আর মিনিটের হিসাব। প্রোগ্রামিং ভাষার অবস্থাও তাই। একটিমাত্র বাস্তবায়ন থাকলে “compiler যা করে, সেটাই নিয়ম” বলে কাজ চলে। কিন্তু কয়েকটি compiler, একটি interpreter আর একটি optimizer থাকলে সবাইকে একই প্রশ্নের একই উত্তর দিতে হয়: এই program চালালে ঠিক কী ঘটবে?
পর্ব ০৩-এ (Syntax, semantics আর pragmatics) দেখেছেন, semantics মানে একটি বৈধ program-এর অর্থ, আর dynamic semantics মানে চালানোর সময় কী ঘটে তার নিয়ম। গদ্যে লেখা নিয়মে ফাঁক থাকে খুব সহজে। কয়েকটি উদাহরণ:
- C17-এ argument-এর ক্রম।
f(a(), b())-এa()আগে চলবে নাb(), standard তা বলে না: এটি unspecified behavior. দুটি compiler দুই রকম ক্রম বেছে নিতে পারে, আর দুটিই “সঠিক”। আরi = i++ + 1;C-তে সরাসরি undefined behavior, অর্থাৎ standard কোনো অর্থই দেয় না। - Python 3.14-এ ক্রম লেখা আছে। Python-এর Language Reference স্পষ্ট বলে, expression বাঁ থেকে ডানে হিসাব হয় (assignment-এ ডান পাশ আগে)। পর্ব ২৬-এ (Expression আর evaluation order) এই পার্থক্য চালিয়ে দেখেছেন।
- Haat spec v1-এর নীরবতা। Spec বলে “
/শূন্যের দিকে কাটে” আর “overflow wrap করে”। কিন্তুINT_MIN / -1-এর ফল কী? দুটি বাক্যই এখানে খাটে, অথচ C-তে এটি UB. Reference implementation-এর README-এর spec decision ১৩ উত্তরটি ঠিক করেছে: ফল INT_MIN. Operand-এর evaluation order-ও spec-এ ছিল না; সিদ্ধান্ত ১২ বলে বাঁ থেকে ডানে।
README-এর ২৮টি সিদ্ধান্তের তালিকাই দেখায়, গদ্যের spec-এ প্রশ্ন থেকে যায়। Formal semantics উত্তরগুলো এমনভাবে লেখে, যা যন্ত্রে চালানো আর প্রমাণ করা যায়। প্রধান রীতি তিনটি:
| রীতি | অর্থ বলে যেভাবে | Haat-এ একটি নমুনা | কোথায় |
|---|---|---|---|
| Operational | একটি কাল্পনিক যন্ত্র কীভাবে ধাপে ধাপে চলে | ⟨x = 14;, σ⟩ ⟶ ⟨skip, σ[x ↦ 14]⟩ | এই পর্ব |
| Denotational | প্রতিটি অংশ একটি গাণিতিক function | ⟦x = e;⟧σ = σ[x ↦ ⟦e⟧σ] | পর্ব ৪১ |
| Axiomatic | আগে-পরের শর্তের সম্পর্ক | {x = 0} x = x + 1; {x = 1} | পর্ব ৪২ |
Operational রীতিটি programmer-এর মনের ছবির সবচেয়ে কাছে, কারণ সে বলে “যন্ত্র কী করে”, আর interpreter লেখার সময় আপনি ঠিক এটাই ভাবেন। এর আগেও আপনি এই নোটেশনের টুকরো দেখেছেন: পর্ব ০৭-এ state σ আর ⟨S, σ⟩ ⇓ σ′, পর্ব ২৭-এ if আর while-এর big-step নিয়ম, পর্ব ১৯-এ strict আর lazy evaluation-এর নিয়ম। এই পর্বে টুকরোগুলো জুড়ে একটি পূর্ণ, যাচাই-করা semantics বানানো হবে, দুই রূপে।
ক্রিকেটের দুই রকম বিবরণ। রেডিওর ধারাভাষ্য বল-বাই-বল চলে: “প্রথম বল, এক রান; দ্বিতীয় বল, ডট”। খেলা যতক্ষণ চলে, ধারাভাষ্যও চলে, আর বৃষ্টিতে খেলা থেমে গেলে ঠিক কোন বলে থামল তা জানা যায়। পত্রিকার স্কোরকার্ড দেয় শুধু ফল, আর ফলের পেছনের হিসাব: কে কত রান, কোন ওভারে কত। Small-step semantics ধারাভাষ্য, big-step semantics স্কোরকার্ড। দুটি একই খেলার বিবরণ, কিন্তু কিছু প্রশ্নের উত্তর একটিতেই পাওয়া যায়।
২ · Haat-core — নিয়ম লেখার জন্য ছোট একটি ভাষা
পুরো Haat-এর semantics একবারে লিখলে নিয়মের সংখ্যা অনেক: function, closure, string, block scope, return. শেখার সময় তাই একটি ছোট core নেওয়া হয়, যাতে আসল ভাবনাগুলো পরিষ্কার দেখা যায়। এই মডিউলের সব পর্বে একই core চলবে; নাম Haat-core:
e ::= n | true | false | x | e ⊕ e | e && e | e || e
⊕ ∈ { + - * / % < <= > >= == != }
S ::= x = e; | print(e); | S S | if e { S } else { S } | while e { S } | skip
v ::= n | true | false (value: যার আর হিসাব বাকি নেই)
প্রতিটি অংশ Haat v1-এর অংশ, দুটি ছাড় ছাড়া। প্রথম, skip Haat-এ লেখা যায় না; এটি semantics-এর সহায়ক, অর্থ “আর কিছু করার নেই”, আর if e { S } মানে if e { S } else { skip }. দ্বিতীয়, সব variable program-এর শুরুতে var দিয়ে ঘোষিত, ভেতরের block-এ নতুন ঘোষণা নেই; তাই block scope-এর প্রশ্ন ওঠে না। Function, string আর unary - ! বাদ; শেষ দুটি অনুশীলন ১-এ যোগ করবেন, আর function-এর semantics পর্ব ৫৭-এ (Environment আর closure-এর বাস্তবায়ন) আসবে।
State আর configuration
State σ পর্ব ০৭-এর মতোই: নাম থেকে মানের একটি টেবিল, যেমন σ = {qty ↦ 2, unit ↦ 520, p ↦ 0}. σ(x) মানে x-এর মান, আর σ[x ↦ v] মানে “σ-এর মতোই টেবিল, শুধু x-এর ঘরে v”. print-এর লেখাও state-এর অংশ: σ-এর ভেতরে একটি বিশেষ ঘর out থাকে, যেখানে ছাপা লেখাগুলো ক্রমে জমা হয়।
যন্ত্রের পূর্ণ তাৎক্ষণিক অবস্থা হলো একটি configuration: বাকি থাকা program আর বর্তমান state একসঙ্গে, লেখা হয় ⟨e, σ⟩ বা ⟨S, σ⟩. শেষ অবস্থা তিন রকম: ⟨v, σ⟩ (expression-এর মান পাওয়া গেছে), ⟨skip, σ⟩ (statement-এর কাজ শেষ), আর error (runtime error, অংশ ৪-এ)।
নিয়মগুলো reference implementation-এর README-এর “Spec decisions” মেনে লেখা: সিদ্ধান্ত ১২ (বাঁ operand আগে, তারপর ডান), সিদ্ধান্ত ১৩ (প্রতিটি Int ফল ৬৪ বিটে wrap, wrapping arithmetic), সিদ্ধান্ত ২৬ (runtime error program থামায়, তার আগে ছাপা লেখা থেকে যায়)। Spec v1 নিজে বলে / শূন্যের দিকে কাটে আর % dividend-এর চিহ্ন নেয় (C-র মতো), শূন্য দিয়ে ভাগ একটি runtime error, আর &&, || short-circuit করে। নিয়মে ⊕̂ লিখলে বোঝাবে “Haat-এর নিয়মে গণিতের কাজটি”: যেমন 7 /̂ 2 = 3, −7 /̂ 2 = −3, −7 %̂ 2 = −1.
৩ · Small-step semantics — এক ধাপ করে
Small-step semantics-এর মূল judgment একটি ধাপ:
পড়ুন: “state σ-তে S-এর ঠিক একটি ধাপ চালালে বাকি থাকে S′, আর state হয় σ′”। Expression-এর জন্যও একই আকার, ⟨e, σ⟩ ⟶ ⟨e′, σ⟩; Haat-core-এর expression state বদলায় না (function call নেই), তাই ডানে আবার σ. নিয়মগুলো পর্ব ৩৪-এর typing rule-এর মতোই inference rule: দাগের ওপরে premise, নিচে conclusion, ডানে নাম। প্রথমে expression:
||-এর তিনটি নিয়ম একই আকারের: E-Or1, E-OrTrue (⟨true || e2, σ⟩ ⟶ ⟨true, σ⟩) আর E-OrFalse (⟨false || e2, σ⟩ ⟶ ⟨e2, σ⟩)। নিয়মে লেখা e1, v1, x আসল কোড নয়; এগুলো metavariable, অর্থাৎ ফাঁকা ঘর। একটি বিশেষ নিয়ম খেয়াল করুন: v1 মানে “একটি value”, যেকোনো expression নয়।
নিয়মগুলো দুই জাতের। E-Op1, E-Op2, E-And1 নিজে কিছু হিসাব করে না; তারা ভেতরের একটি অংশের এক ধাপকে পুরো expression-এর এক ধাপে তুলে আনে। এদের বলে congruence rule. আসল কাজ করে বাকিগুলো (E-Var, E-Op, E-AndTrue …), যাদের দাগের ওপরে কোনো ধাপ নেই, বড়জোর একটি সাধারণ শর্ত। E-Op2-এর বাঁ পাশে v1 লেখাটিই সিদ্ধান্ত ১২-কে নিয়মে বেঁধেছে: বাঁ পাশ value না হওয়া পর্যন্ত E-Op2 খাটেই না, তাই ডান পাশের হিসাব শুরু হতে পারে না। আর E-AndFalse-এ e2 সোজা ফেলে দেওয়া হয়: short-circuit একটি নিয়মের আকারেই লেখা।
এবার statement. লক্ষ করুন while-এর নিয়মে কোনো premise নেই; সে নিজেকে একটি if-এ খুলে দেয়, যার ভেতরে আবার সেই while:
print(e);-এর congruence নিয়ম E-Print1 হুবহু E-Assign1-এর মতো। “out · v” মানে out-এর শেষে v-এর লেখা জোড়া। E-Seq1-এর ডানে σ′, কারণ ভেতরের S1 state বদলাতে পারে।
Program থামে যখন ⟨skip, σ′⟩-এ পৌঁছায়। শূন্য বা তার বেশি ধাপকে একসঙ্গে লেখা হয় ⟶* দিয়ে: c ⟶* c′ মানে “c থেকে কয়েকটি (শূন্যও হতে পারে) ধাপে c′”. গণিতের ভাষায় ⟶* হলো ⟶-এর reflexive-transitive closure. একটি program-এর “অর্থ”: ⟨S, σ⟩ ⟶* ⟨skip, σ′⟩ হলে শেষ state σ′.
একটি ধাপের ভেতরে একটি ছোট প্রমাণ
নিচের stepper-এ x = 2 + 3 * 4; চলে σ = {x ↦ 0} থেকে। প্রতিটি ধাপ একটি ছোট derivation: ভেতরে একটি computation rule, বাইরে congruence rule-এর মোড়ক; নাম লেখা হয়েছে বাইরে থেকে ভেতরে, যেমন E-Assign1(E-Op2(E-Op)).
0⟨x = 2 + 3 * 4;, σ⟩1⟨x = 2 + 12;, σ⟩2⟨x = 14;, σ⟩3⟨skip, σ[x ↦ 14]⟩
| বাকি | |
| σ | |
| নিয়ম |
- শুরুর configuration. σ = {x ↦ 0}. পুরো statement একটি assignment, কিন্তু ডান পাশ এখনও value নয়, তাই E-Assign খাটে না; খাটতে পারে শুধু E-Assign1, যা চায় ভেতরের expression
2 + 3 * 4-এর একটি ধাপ। সেখানে বাঁ operand2আগেই value, তাই E-Op1 নয়, E-Op2: ডান পাশ3 * 4-এর একটি ধাপ চাই। - প্রথম ধাপ, তিন স্তরের প্রমাণ। সবার ভেতরে
3 * 4: দুটিই value, তাই E-Op দেয় 12. E-Op2 সেটিকে2 + 12-এ তোলে, E-Assign1 তোলে পুরো statement-এ। নাম: E-Assign1(E-Op2(E-Op)). State বদলায়নি। - দ্বিতীয় ধাপ। এবার
2 + 12-এর দুই পাশই value, তাই সরাসরি E-Op: ফল 14. একটিমাত্র congruence, E-Assign1. Configuration: ⟨x = 14;, σ⟩. - তৃতীয় ধাপ, state বদলায়। ডান পাশ এখন value 14, তাই E-Assign: বাকি থাকে skip, আর σ[x ↦ 14] = {x ↦ 14}. পুরো যাত্রায় এই একটিমাত্র ধাপ state ছুঁয়েছে।
- মোট হিসাব। ⟨x = 2 + 3 * 4;, {x ↦ 0}⟩ ⟶* ⟨skip, {x ↦ 14}⟩, ঠিক ৩টি ধাপে। প্রতিটি ধাপে ঠিক একটি নিয়ম-শৃঙ্খল খেটেছে; অংশ ৬-এ দেখবেন এটি কাকতালীয় নয়। Reference-এ
var x = 0; x = 2 + 3 * 4; print(x);চালালে সত্যিকারের run-এ আসে14.
নিচের block-এ নিয়মগুলো সরাসরি Python-এ। প্রতিটি নিয়ম step()-এর একটি শাখা; congruence নিয়মের কাজ একটি ছোট সহায়ক sub() করে, যা ভেতরের অংশে step() ডাকে আর নামটি মোড়কে জড়ায়। AST tuple আকারে (পর্ব ৩৪-এর মতো); পূর্ণ Haat-এর রূপ reference-এর interp.py-এ। পরের তিনটি block এর ওপর দাঁড়িয়ে।
# Haat-core-এর small-step semantics: step() একটি নিয়ম খাটিয়ে ঠিক এক ধাপ এগোয়
# AST: 5, True, "x", (op, a, b) · ("=", x, e) ("print", e) ("seq", S1, S2) ("if", e, S1, S2) ("while", e, S) "skip"
import operator as O
def wrap(n): return (n + 2**63) % 2**64 - 2**63 # সিদ্ধান্ত ১৩
def cdiv(a, b): q = abs(a) // abs(b); return q if (a < 0) == (b < 0) else -q
OPS = {"+": O.add, "-": O.sub, "*": O.mul, "/": cdiv, "%": lambda a, b: a - b * cdiv(a, b),
"<": O.lt, "<=": O.le, ">": O.gt, ">=": O.ge, "==": O.eq, "!=": O.ne}
class Err(Exception): pass # runtime error কনফিগারেশন
DIVZERO = True # E-DivZero নিয়মটি আছে কি না
def isv(t): return isinstance(t, (bool, int)) # value: আর হিসাবের কিছু নেই
def sub(t, i, s, name): # congruence নিয়ম: t-এর i-তম অংশকে এক ধাপ এগোনো
x, s2, r = step(t[i], s); return t[:i] + (x,) + t[i + 1:], s2, f"{name}({r})"
def step(t, s): # ⟨t, σ⟩ ⟶ ⟨t′, σ′⟩ : ফেরত (t′, σ′, নিয়মের নাম)
if isinstance(t, str): return s[t], s, "E-Var"
k = t[0]
if k in OPS:
if not isv(t[1]): return sub(t, 1, s, "E-Op1") # আগে বাঁ দিক (সিদ্ধান্ত ১২)
if not isv(t[2]): return sub(t, 2, s, "E-Op2")
if k in "/%" and t[2] == 0: # E-DivZero, না থাকলে stuck
raise Err("division by zero") if DIVZERO else LookupError("কোনো নিয়ম খাটে না")
r = OPS[k](t[1], t[2]); return (r if isinstance(r, bool) else wrap(r)), s, "E-Op"
if k in ("&&", "||"):
if not isv(t[1]): return sub(t, 1, s, "E-And1" if k == "&&" else "E-Or1")
if k == "&&": return (t[2], s, "E-AndTrue") if t[1] else (False, s, "E-AndFalse")
return (True, s, "E-OrTrue") if t[1] else (t[2], s, "E-OrFalse")
if k in ("=", "print") and not isv(t[-1]): # E-Assign1, E-Print1
return sub(t, len(t) - 1, s, "E-Assign1" if k == "=" else "E-Print1")
if k == "=": return "skip", {**s, t[1]: t[2]}, "E-Assign"
if k == "print": return "skip", {**s, "out": s["out"] + (str(t[1]).lower(),)}, "E-Print"
if k == "seq": return (t[2], s, "E-SeqSkip") if t[1] == "skip" else sub(t, 1, s, "E-Seq1")
if k == "if" and not isv(t[1]): return sub(t, 1, s, "E-If")
if k == "if": return (t[2], s, "E-IfTrue") if t[1] else (t[3], s, "E-IfFalse")
return ("if", t[1], ("seq", t[2], t), "skip"), s, "E-While" # while খুলে if বানানো
t, s = ("=", "x", ("+", 2, ("*", 3, 4))), {"x": 0, "out": ()}
while t != "skip": t, s, r = step(t, s); print(f"⟶ {r:<24}", t, {"x": s.get("x")})আসল আউটপুট (ব্রাউজারের Python):
⟶ E-Assign1(E-Op2(E-Op)) ('=', 'x', ('+', 2, 12)) {'x': 0}
⟶ E-Assign1(E-Op) ('=', 'x', 14) {'x': 0}
⟶ E-Assign skip {'x': 14}
তিনটি লাইন stepper-এর তিনটি ধাপ, একই নিয়মের নাম আর একই σ. দ্বিতীয় কলামে configuration-এর বাকি অংশ AST আকারে: ('=', 'x', ('+', 2, 12)) মানে x = 2 + 12;. কোডে একটি জিনিস লক্ষ করুন: step() কখনো একাধিক নিয়ম চেষ্টা করে না, প্রতিটি if একটি শর্ত দেখে একটি শাখায় ঢোকে। যেমন E-Op2-এর শাখায় ঢোকার আগে কোড আগে নিশ্চিত করে বাঁ পাশ value (isv(t[1])). নিয়মের “v1” আর কোডের এই শর্ত একই জিনিস।
৪ · আটকে যাওয়া, runtime error আর অসীম loop
অংশ ৩-এর নিয়মে একটি program তিনভাবে চলতে পারে: কয়েকটি ধাপে ⟨skip, σ′⟩-এ পৌঁছানো (স্বাভাবিক শেষ); এমন configuration-এ পৌঁছানো, যা শেষ অবস্থা নয় অথচ কোনো নিয়মও খাটে না; অথবা কখনো না থামা। ভাষা নকশার অনেক সিদ্ধান্ত এই তিনটির পার্থক্যের ওপর দাঁড়িয়ে।
Stuck — নিয়মের বইয়ে উত্তর নেই
একটি configuration c stuck, যদি c শেষ অবস্থা না হয় (⟨v, σ⟩ বা ⟨skip, σ⟩ নয়), আর কোনো c′-এর জন্য c ⟶ c′ নিয়মে প্রমাণ করা না যায়।
Haat-core-এ তিন রকম stuck configuration তৈরি হতে পারে, যদি আমরা নিয়মে কিছু না জুড়ি:
- ⟨true + 1, σ⟩: E-Op চায় v = v1 ⊕̂ v2, কিন্তু Bool আর Int-এর যোগ গণিতে সংজ্ঞায়িতই নয়। এটি একটি type ভুল।
- ⟨y, σ⟩, যখন y σ-তে নেই: E-Var চায় σ(y), যা নেই। এটি একটি নামের ভুল।
- ⟨1000 / 0, σ⟩: E-Op-এর শর্ত v2 ≠ 0 ভাঙে, আর অন্য কোনো নিয়ম নেই।
প্রথম দুটি Haat-এর type checker আর resolver আগেই বাতিল করে, type mismatch আর undefined variable বার্তা দিয়ে। Checker-এর প্রতিশ্রুতি এই ভাষায় নিখুঁতভাবে লেখা যায়: “well-typed program কখনো stuck হয় না”। এটিই type soundness; এর দুই অংশ progress (well-typed অশেষ configuration-এর অন্তত একটি ধাপ আছে) আর preservation (ধাপের পরেও type একই থাকে) পর্ব ৩৮-এ (Type soundness) small-step নিয়মের ওপরেই প্রমাণিত।
তৃতীয়টি আলাদা। ভাজক শূন্য হবে কি না, তা সাধারণভাবে চালানোর আগে জানা যায় না (ভাজক হয়তো ইনপুট থেকে আসে)। তাই ভাষার নকশাকার এখানে একটি স্পষ্ট নিয়ম জোড়েন, যা এই অবস্থাকে “ঘোষিত runtime error” বানায়:
দ্বিতীয় নিয়মটি দেখায় error কীভাবে বাইরে ছড়ায়: ভেতরে error হলে পুরো statement-ও error. প্রতিটি congruence নিয়মের (E-Op1, E-Op2, E-And1, E-Or1, E-Assign1, E-Print1, E-Seq1, E-If) এমন একটি সঙ্গী লাগে, মোট ৮টি; অংশ ৭-এর evaluation context এগুলোকে একটি নিয়মে গুটিয়ে আনবে। error একটি শেষ অবস্থা: তার পরে আর কোনো ধাপ নেই। আর error-এর ঠিক আগের configuration-এর σ-তে out-এর লেখা থেকে যায়, যা সিদ্ধান্ত ২৬-এর “output printed before the error stays”.
নিচের stepper-এ বাজারঘরের একটি ভুল হিসাব: মোট ১০০০ টাকা জনপ্রতি ভাগ করতে গিয়ে লেখক লিখেছেন people - people, যা সবসময় শূন্য। σ = {people ↦ 4}.
0print(1000 / (people - people));1print(1000 / (4 - people));2print(1000 / (4 - 4));3print(1000 / 0);
| নিয়ম | |
| অবস্থা | |
| out |
- শুরু। বাকি program একটি
print, যার ভেতরে1000 / (people - people). বাইরের/-এর বাঁ পাশ 1000 আগেই value, তাই কাজ ডান পাশে। - বাঁ people আগে। ভেতরের
--এ বাঁ পাশ একটি নাম, তাই E-Op1 আর তার ভেতরে E-Var: σ(people) = 4. চারটি নিয়মের শিকল একটিমাত্র ধাপ। - তারপর ডান people. এখন বাঁ পাশ value 4, তাই E-Op2 দিয়ে ডান পাশ: আবার E-Var. সিদ্ধান্ত ১২-এর ক্রম নিয়ম থেকেই এল, কোডে আলাদা করে লেখা লাগেনি।
- শূন্য তৈরি। 4 - 4 = 0, E-Op দিয়ে। Configuration এখন ⟨print(1000 / 0);, σ⟩. দুই পাশই value, তাই এবার সিদ্ধান্ত বাইরের
/-এর। - E-DivZero ছাড়া: stuck. E-Op চায় v2 ≠ 0, যা মিথ্যা; আর কোনো নিয়ম নেই। Configuration শেষ অবস্থাও নয়। যন্ত্র “জানে না কী করবে”: semantics এখানে চুপ, ঠিক যেমন C standard শূন্য দিয়ে integer ভাগে UB বলে চুপ থাকে।
- E-DivZero সহ: ঘোষিত error. এবার নিয়ম আছে: ⟨1000 / 0, σ⟩ ⟶ error, আর E-Print1-Err তাকে পুরো statement-এ তোলে। out ফাঁকা, কারণ কিছু ছাপা হয়নি। Reference-এ
var people = 4;আর এই লাইন চালালে সত্যিকারের run-এ আসে2:12: runtime error: division by zero; কলাম ১২ হলো/চিহ্নের অবস্থান (সিদ্ধান্ত ২৪)।
পার্থক্যটি ব্যবহারিক। Stuck মানে ভাষা এই অবস্থার কোনো অর্থ দেয়নি, তাই বাস্তবায়ন যা খুশি করতে পারে (C-র undefined behavior এমনই); error মানে ভাষা ঠিক করে দিয়েছে কী হবে, আর প্রতিটি সঠিক বাস্তবায়ন একই কাজ করবে, যেমন Java-র ArithmeticException বা Python-এর ZeroDivisionError দেয়।
অসীম loop — ধাপের শেষ নেই
while true { n = n + 1; } চালালে E-While, E-IfTrue, assignment-এর তিনটি ধাপ, একটি E-SeqSkip, তারপর আবার E-While: প্রতি ঘোরায় ৬টি ধাপ, চিরকাল। Small-step-এ এটি একটি অসীম সারি c0 ⟶ c1 ⟶ c2 ⟶ …, যার প্রতিটি configuration দেখা যায়। একে বলে divergence. কোনো configuration থেকে কখনো skip-এ পৌঁছানো যাবে কি না, তা সব program-এর জন্য বলে দেওয়ার কোনো algorithm নেই: এটি halting problem, যা গণনার তত্ত্বের পর্ব ৫১-এ প্রমাণিত। তাই interpreter বা test harness একটি ব্যবহারিক পথ নেয়: ধাপের একটি বাজেট (fuel). বাজেট শেষ হলে উত্তর “এখনও চলছে”, যার মানে “অসীম” নয়, শুধু “এতক্ষণে শেষ হয়নি”।
নিচের block-এ step()-এর ওপর একটি ছোট চালক trace(): প্রতিটি configuration Haat-এর লেখায় ছাপে, error আর stuck আলাদা করে ধরে, আর fuel শেষ হলে থামে। তারপর চলে বাজারঘরের অর্ডারের হিসাব (২টি পণ্য, প্রতিটি ৫২০ টাকা, ১০০০ বা বেশি হলে ১০% ছাড়, তারপর ৬০ টাকা ডেলিভারি), stepper-এর ভাগের ভুল দুই রকম নিয়মে, আর একটি অসীম loop.
# আগের block-এর step() দিয়ে পুরো program চালানো: প্রতিটি configuration ছাপা
def show(v): return str(v).lower() # Int → 996, Bool → true
P = {"||": 1, "&&": 2, "==": 3, "!=": 3, "<": 4, "<=": 4, ">": 4, ">=": 4,
"+": 5, "-": 5, "*": 6, "/": 6, "%": 6}
def pe(e, p=0): # expression → Haat লেখা (দরকার হলে বন্ধনী)
if not isinstance(e, tuple): return show(e)
q = P[e[0]]; x = f"{pe(e[1], q)} {e[0]} {pe(e[2], q + 1)}"
return f"({x})" if q < p else x
def ps(t): # statement → Haat লেখা
if t == "skip": return "skip"
k = t[0]
if k == "=": return f"{t[1]} = {pe(t[2])};"
if k == "print": return f"print({pe(t[1])});"
if k == "seq": return f"{ps(t[1])} {ps(t[2])}"
if k == "while": return f"while {pe(t[1])} {{ {ps(t[2])} }}"
return f"if {pe(t[1])} {{ {ps(t[2])} }}" + ("" if t[3] == "skip" else f" else {{ {ps(t[3])} }}")
def sg(s): return "{" + ", ".join(f"{k} ↦ {show(v)}" for k, v in s.items() if k != "out") + "}"
def seq(*ss): return ss[0] if len(ss) == 1 else ("seq", ss[0], seq(*ss[1:]))
def trace(t, s, fuel=60, quiet=False): # ⟨t, σ⟩ ⟶ … যতক্ষণ না skip
n = 0
while t != "skip" and n < fuel:
try: t, s, r = step(t, s)
except Err as e: print(f"{n + 1:>2} ⟶ error: {e} (out: {list(s['out'])})"); return
except LookupError: print(f"{n + 1:>2} আটকে গেছে (stuck): {ps(t)}"); return
n += 1
if not quiet: print(f"{n:>2} {r:<22} ⟨{ps(t)}, {sg(s)}⟩")
print(f"{n} ধাপ পরে:", "শেষ" if t == "skip" else "এখনও চলছে", sg(s), "out:", list(s["out"]))
order = seq(("=", "p", ("*", "qty", "unit")),
("if", (">=", "p", 1000), ("=", "p", ("-", "p", ("/", "p", 10))), "skip"),
("print", ("+", "p", 60)))
trace(order, {"qty": 2, "unit": 520, "p": 0, "out": ()})
share = ("print", ("/", 1000, ("-", "people", "people")))
DIVZERO = False; trace(share, {"people": 4, "out": ()}) # নিয়ম ছাড়া
DIVZERO = True; trace(share, {"people": 4, "out": ()}) # E-DivZero সহ
trace(("while", True, ("=", "n", ("+", "n", 1))), {"n": 0, "out": ()}, fuel=3000, quiet=True)আসল আউটপুট (ব্রাউজারের Python; লম্বা লাইন পাশে সরিয়ে পড়ুন):
1 E-Seq1(E-Assign1(E-Op1(E-Var))) ⟨p = 2 * unit; if p >= 1000 { p = p - p / 10; } print(p + 60);, {qty ↦ 2, unit ↦ 520, p ↦ 0}⟩
2 E-Seq1(E-Assign1(E-Op2(E-Var))) ⟨p = 2 * 520; if p >= 1000 { p = p - p / 10; } print(p + 60);, {qty ↦ 2, unit ↦ 520, p ↦ 0}⟩
3 E-Seq1(E-Assign1(E-Op)) ⟨p = 1040; if p >= 1000 { p = p - p / 10; } print(p + 60);, {qty ↦ 2, unit ↦ 520, p ↦ 0}⟩
4 E-Seq1(E-Assign) ⟨skip if p >= 1000 { p = p - p / 10; } print(p + 60);, {qty ↦ 2, unit ↦ 520, p ↦ 1040}⟩
5 E-SeqSkip ⟨if p >= 1000 { p = p - p / 10; } print(p + 60);, {qty ↦ 2, unit ↦ 520, p ↦ 1040}⟩
6 E-Seq1(E-If(E-Op1(E-Var))) ⟨if 1040 >= 1000 { p = p - p / 10; } print(p + 60);, {qty ↦ 2, unit ↦ 520, p ↦ 1040}⟩
7 E-Seq1(E-If(E-Op)) ⟨if true { p = p - p / 10; } print(p + 60);, {qty ↦ 2, unit ↦ 520, p ↦ 1040}⟩
8 E-Seq1(E-IfTrue) ⟨p = p - p / 10; print(p + 60);, {qty ↦ 2, unit ↦ 520, p ↦ 1040}⟩
9 E-Seq1(E-Assign1(E-Op1(E-Var))) ⟨p = 1040 - p / 10; print(p + 60);, {qty ↦ 2, unit ↦ 520, p ↦ 1040}⟩
10 E-Seq1(E-Assign1(E-Op2(E-Op1(E-Var)))) ⟨p = 1040 - 1040 / 10; print(p + 60);, {qty ↦ 2, unit ↦ 520, p ↦ 1040}⟩
11 E-Seq1(E-Assign1(E-Op2(E-Op))) ⟨p = 1040 - 104; print(p + 60);, {qty ↦ 2, unit ↦ 520, p ↦ 1040}⟩
12 E-Seq1(E-Assign1(E-Op)) ⟨p = 936; print(p + 60);, {qty ↦ 2, unit ↦ 520, p ↦ 1040}⟩
13 E-Seq1(E-Assign) ⟨skip print(p + 60);, {qty ↦ 2, unit ↦ 520, p ↦ 936}⟩
14 E-SeqSkip ⟨print(p + 60);, {qty ↦ 2, unit ↦ 520, p ↦ 936}⟩
15 E-Print1(E-Op1(E-Var)) ⟨print(936 + 60);, {qty ↦ 2, unit ↦ 520, p ↦ 936}⟩
16 E-Print1(E-Op) ⟨print(996);, {qty ↦ 2, unit ↦ 520, p ↦ 936}⟩
17 E-Print ⟨skip, {qty ↦ 2, unit ↦ 520, p ↦ 936}⟩
17 ধাপ পরে: শেষ {qty ↦ 2, unit ↦ 520, p ↦ 936} out: ['996']
1 E-Print1(E-Op2(E-Op1(E-Var))) ⟨print(1000 / (4 - people));, {people ↦ 4}⟩
2 E-Print1(E-Op2(E-Op2(E-Var))) ⟨print(1000 / (4 - 4));, {people ↦ 4}⟩
3 E-Print1(E-Op2(E-Op)) ⟨print(1000 / 0);, {people ↦ 4}⟩
4 আটকে গেছে (stuck): print(1000 / 0);
1 E-Print1(E-Op2(E-Op1(E-Var))) ⟨print(1000 / (4 - people));, {people ↦ 4}⟩
2 E-Print1(E-Op2(E-Op2(E-Var))) ⟨print(1000 / (4 - 4));, {people ↦ 4}⟩
3 E-Print1(E-Op2(E-Op)) ⟨print(1000 / 0);, {people ↦ 4}⟩
4 ⟶ error: division by zero (out: [])
3000 ধাপ পরে: এখনও চলছে {n ↦ 500} out: []
প্রথম তিনটি লাইন আগের block-এর। তারপর অর্ডারের হিসাব ১৭টি ধাপে: ৯৩৬ + ৬০ = ৯৯৬, bazar.haat-এর প্রথম লাইনের মতো। ধাপ ৪-এ বাকি অংশ skip if …, আর ধাপ ৫-এ E-SeqSkip সেই skip সরায়। ধাপ ৮-এ E-IfTrue পুরো if-কে তার then-শাখা দিয়ে বদলে দেয়। ধাপ ১০-এর নিয়মের নামে পাঁচটি স্তর: পরের কাজটি খুঁজতে যন্ত্র program-এর ভেতরে পাঁচ স্তর নামছে; এই খরচ অংশ ৭-এ আবার আসবে।
ভাগের ভুলটি নিয়ম ছাড়া (DIVZERO = False) ৪র্থ চেষ্টায় stuck, আর নিয়মসহ ৪র্থ চেষ্টায় error, out ফাঁকা। শেষ লাইন: ৩০০০ ধাপে loop ৫০০ বার ঘুরেছে (৩০০০ ÷ ৬), আর যন্ত্র এখনও চলছে।
৫ · Big-step semantics — একবারে পুরো ফল
Big-step semantics (একে natural semantics-ও বলে) মাঝের ধাপ দেখায় না। তার judgment সরাসরি শেষ ফলের দাবি:
পড়ুন: “σ-তে e হিসাব করলে মান v”, আর “σ থেকে S চালালে শেষে state σ′”. পর্ব ০৭ আর ২৭-এ এই রূপটিই দেখেছেন। এই পর্বে দুই ধরনের নিয়ম পাশাপাশি থাকায় big-step নিয়মের নামের আগে B- লেখা হলো (Benjamin Pierce-এর Types and Programming Languages বইয়ের রীতি); পর্ব ২৭-এর E-IfT, E-IfF, E-WhileT, E-WhileF এখানে B-IfT, B-IfF, B-WhileT, B-WhileF, আর পর্ব ০৭-এর Assign, Seq এখানে B-Assign, B-Seq. নিয়মের আকার হুবহু এক।
বাকি নিয়মগুলো একই ছাঁচে: B-IfF (শর্ত false হলে S2), B-Print (⟨e, σ⟩ ⇓ v হলে ⟨print(e);, σ⟩ ⇓ σ[out ↦ out · v]), আর ||-এর B-OrT ও B-OrF. B-Op-এর দুটি premise-এর ক্রম গণিতে কোনো অর্থ বহন করে না (expression-এ side effect নেই বলে), কিন্তু interpreter এগুলো বাঁ থেকে ডানে প্রমাণ করে, যেমন সিদ্ধান্ত ১২ বলে। দুই semantics-এর পার্থক্য একটি ছবিতে:
ছবি ৪০.১ — একই x = 2 + 3 * 4;, দুই দৃষ্টিতে
ওপরে small-step: configuration-এর শিকল, প্রতিটি তিরে একটি ধাপের নিয়ম। নিচে big-step: একটি derivation গাছ, পাতা ওপরে আর মূল দাবি নিচে। σ0 = {x ↦ 0}, σ1 = {x ↦ 14}; দুটিই চালানো কোডের আউটপুট থেকে।
দুই ছবির শেষ কথা একই (σ1-এ x ↦ 14), কিন্তু গঠন আলাদা। শিকলে প্রতিটি ধাপের পরে পুরো program আবার লেখা হয়; গাছে প্রতিটি sub-expression-এর মান একবারই আসে, আর কোনো “মাঝের অবস্থা” নেই।
একটি loop-এর derivation
B-WhileT-এর তৃতীয় premise আবার সেই while, নতুন state থেকে (পর্ব ২৭); তাই প্রতিটি ঘোরায় গাছে একটি B-WhileT, আর চূড়ায় একটি B-WhileF. নিচের stepper-এ while total < 2500 { total = total + 1250; } চলে σ0 = {total ↦ 0} থেকে; loop দুবার ঘোরে। W লিখলে বোঝাবে পুরো while statement-টি; B-Var আর B-Val-এর ১২টি পাতা লেখা হয়নি, পরের Python block সেগুলোসহ পুরো গাছ ছাপে।
1⟨W, σ0⟩ ⇓ σ22 ⟨total < 2500, σ0⟩ ⇓ true3 ⟨total = total + 1250;, σ0⟩ ⇓ σ14 ⟨W, σ1⟩ ⇓ σ25 ⟨total < 2500, σ1⟩ ⇓ true6 ⟨total = total + 1250;, σ1⟩ ⇓ σ27 ⟨W, σ2⟩ ⇓ σ28 ⟨total < 2500, σ2⟩ ⇓ false
| লক্ষ্য | |
| নিয়ম | |
| নতুন σ |
- গোড়ার লক্ষ্য। প্রশ্ন: ⟨W, σ0⟩ ⇓ ? while-এর দুটি নিয়ম, B-WhileT আর B-WhileF; কোনটি খাটবে তা ঠিক হবে শর্তের মান দেখে।
- শর্ত। σ0-এ total = 0, তাই B-Op (premise দুটি পাতা: B-Var দেয় 0, B-Val দেয় 2500) দেয় ⟨total < 2500, σ0⟩ ⇓ true. ফলে B-WhileF বাদ, B-WhileT-এর প্রথম premise প্রমাণিত।
- শরীর একবার। B-WhileT-এর দ্বিতীয় premise: ⟨total = total + 1250;, σ0⟩ ⇓ σ1, নিয়ম B-Assign. 0 + 1250 = 1250, তাই σ1 = {total ↦ 1250}.
- তৃতীয় premise আবার W. এবার σ1 থেকে: ⟨W, σ1⟩ ⇓ ? শর্ত 1250 < 2500 সত্য, তাই আবার B-WhileT, গাছের এক স্তর ওপরে।
- শরীর দ্বিতীয়বার। ⟨total = total + 1250;, σ1⟩ ⇓ σ2, যেখানে σ2 = {total ↦ 2500}.
- B-WhileF, গাছের চূড়া। ⟨W, σ2⟩: শর্ত 2500 < 2500 মিথ্যা, তাই B-WhileF, আর state বদলায় না: ⟨W, σ2⟩ ⇓ σ2. এর ওপরে আর কোনো W নেই, তাই গাছ এখানে শেষ। Loop থামে বলেই গাছ সসীম।
- নিচে ফেরা। লাইন ৭-এর ফল σ2 লাইন ৪-এর B-WhileT-এর σ″ হয়, আর সেটি আবার লাইন ১-এর σ″: ⟨W, σ0⟩ ⇓ σ2. পুরো গাছে ২০টি judgment: এখানে দেখানো ৮টি আর ১২টি পাতা। Reference-এ এই loop-এর পরে
print(total);দিলে সত্যিকারের run-এ আসে2500.
গাছ আঁকা হয় নিচ থেকে ওপরে (লক্ষ্য থেকে premise), কিন্তু σ1, σ2 জানা যায় premise প্রমাণ হওয়ার পর। তাই big-step-এর algorithm একটি recursive function: premise মানে recursive call, আর তার ফেরত মান পরের premise-এর input. নিচের ev() আর ex() ঠিক এটি করে, আর প্রতিটি judgment গাছ আকারে জমায়।
# Big-step semantics: ev() দেয় ⟨e, σ⟩ ⇓ v, ex() দেয় ⟨S, σ⟩ ⇓ σ′, সঙ্গে পুরো derivation গাছ
names = {} # প্রতিটি নতুন σ-কে σ0, σ1, … নাম দেওয়া
def nm(s): return f"σ{names.setdefault(tuple(sorted(s.items())), len(names))}"
def ev(e, s): # ফেরত: (v, গাছ); গাছ = (judgment, নিয়ম, premise-গুলো)
J = lambda v: f"⟨{pe(e)}, {nm(s)}⟩ ⇓ {show(v)}"
if isv(e): return e, (J(e), "B-Val", [])
if isinstance(e, str): return s[e], (J(s[e]), "B-Var", [])
a, d1 = ev(e[1], s)
SC = {"&&": ("B-AndF", "B-AndT"), "||": ("B-OrT", "B-OrF")}.get(e[0]) # short-circuit
if SC and a == (e[0] == "||"): return a, (J(a), SC[0], [d1])
b, d2 = ev(e[2], s)
if SC: return b, (J(b), SC[1], [d1, d2])
if e[0] in "/%" and b == 0: raise Err("division by zero") # B-DivZero
v, _, _ = step((e[0], a, b), s); return v, (J(v), "B-Op", [d1, d2])
def ex(t, s, depth=0): # depth: গাছের উচ্চতার সীমা (অসীম loop ধরতে)
if depth > 200: raise RecursionError("২০০ স্তরেও derivation শেষ হয়নি")
J = lambda s2: f"⟨{ps(t)}, {nm(s)}⟩ ⇓ {nm(s2)}"
k = "skip" if t == "skip" else t[0]
if k == "skip": return s, (J(s), "B-Skip", [])
if k in ("=", "print"):
v, d = ev(t[-1], s)
s2 = {**s, t[1]: v} if k == "=" else {**s, "out": s["out"] + (show(v),)}
return s2, (J(s2), "B-Assign" if k == "=" else "B-Print", [d])
if k == "seq":
s1, d1 = ex(t[1], s, depth + 1); s2, d2 = ex(t[2], s1, depth + 1)
return s2, (J(s2), "B-Seq", [d1, d2])
c, d0 = ev(t[1], s)
if k == "if": s2, d1 = ex(t[2] if c else t[3], s, depth + 1); return s2, (J(s2), "B-IfT" if c else "B-IfF", [d0, d1])
if not c: return s, (J(s), "B-WhileF", [d0])
s1, d1 = ex(t[2], s, depth + 1); s2, d2 = ex(t, s1, depth + 1)
return s2, (J(s2), "B-WhileT", [d0, d1, d2])
def tree(d, pad=""): print(f"{pad}{d[0]} [{d[1]}]"); [tree(k, pad + " ") for k in d[2]]
loop = ("while", ("<", "total", 2500), ("=", "total", ("+", "total", 1250)))
s_end, d = ex(loop, {"total": 0, "out": ()}); tree(d)
for k, i in names.items(): print(f"σ{i} = {sg(dict(k))}")আসল আউটপুট (ব্রাউজারের Python):
⟨while total < 2500 { total = total + 1250; }, σ0⟩ ⇓ σ2 [B-WhileT]
⟨total < 2500, σ0⟩ ⇓ true [B-Op]
⟨total, σ0⟩ ⇓ 0 [B-Var]
⟨2500, σ0⟩ ⇓ 2500 [B-Val]
⟨total = total + 1250;, σ0⟩ ⇓ σ1 [B-Assign]
⟨total + 1250, σ0⟩ ⇓ 1250 [B-Op]
⟨total, σ0⟩ ⇓ 0 [B-Var]
⟨1250, σ0⟩ ⇓ 1250 [B-Val]
⟨while total < 2500 { total = total + 1250; }, σ1⟩ ⇓ σ2 [B-WhileT]
⟨total < 2500, σ1⟩ ⇓ true [B-Op]
⟨total, σ1⟩ ⇓ 1250 [B-Var]
⟨2500, σ1⟩ ⇓ 2500 [B-Val]
⟨total = total + 1250;, σ1⟩ ⇓ σ2 [B-Assign]
⟨total + 1250, σ1⟩ ⇓ 2500 [B-Op]
⟨total, σ1⟩ ⇓ 1250 [B-Var]
⟨1250, σ1⟩ ⇓ 1250 [B-Val]
⟨while total < 2500 { total = total + 1250; }, σ2⟩ ⇓ σ2 [B-WhileF]
⟨total < 2500, σ2⟩ ⇓ false [B-Op]
⟨total, σ2⟩ ⇓ 2500 [B-Var]
⟨2500, σ2⟩ ⇓ 2500 [B-Val]
σ0 = {total ↦ 0}
σ1 = {total ↦ 1250}
σ2 = {total ↦ 2500}
২০টি লাইন, ২০টি judgment: stepper-এর ৮টি আর B-Var/B-Val-এর ১২টি পাতা। গাছের উচ্চতা ৫ (গোড়া থেকে সবচেয়ে দূরের পাতা পর্যন্ত ৫টি স্তর)। কোডে প্রতিটি নিয়ম একটি return; B-WhileT-এর শাখায় তিনটি premise তিনটি call, আর তৃতীয় call হলো ex(t, s1, …), অর্থাৎ নিজেকেই নতুন state দিয়ে ডাকা। B-Op-এর হিসাব প্রথম block-এর step()-কে দিয়ে করানো হয়েছে, যাতে দুই semantics-এর গণিত (wrap, C-ধাঁচের ভাগ) হুবহু এক থাকে। depth-এর সীমা কেন দরকার, নিচে দেখবেন।
Big-step-এ error আর অসীম loop
Big-step-এ error লিখতে একটি নতুন ফল লাগে: ⟨e, σ⟩ ⇓ error. শূন্য দিয়ে ভাগের নিয়ম পর্ব ০৩-এর E-DivZero-এর এই পর্বের নাম:
কিন্তু এটুকু যথেষ্ট নয়। Error যেকোনো premise-এ ঘটতে পারে, আর প্রতিটি জায়গার জন্য একটি প্রচার-নিয়ম লাগে: B-Seq-এর দুটি premise-এর জন্য দুটি, B-WhileT-এর তিনটির জন্য তিনটি। আমাদের গোনায় Haat-core-এ এমন বাড়তি নিয়ম ১৬টি, যেখানে small-step-এ লেগেছিল ৮টি। তা ছাড়া B-DivZero-এর ফলে কোনো σ নেই, তাই error-এর আগে কী ছাপা হয়েছিল তা গাছে হারিয়ে যায়, যদি না প্রতিটি error-নিয়মে state-ও বয়ে নেওয়া হয়।
অসীম loop-এ ব্যাপারটি আরও মৌলিক। while true { n = n + 1; }-এর জন্য B-WhileT-এর তৃতীয় premise সবসময় আবার নিজেকে চায়, তাই কোনো সসীম derivation গাছ নেই। কিন্তু stuck program-এরও কোনো গাছ নেই! Big-step তাই “চিরকাল চলে” আর “আটকে গেছে”-কে আলাদা করতে পারে না; দুটিই শুধু “derivation নেই”। এই কারণেই type soundness-এর প্রমাণে (পর্ব ৩৮) small-step লাগে। কোডে এর ছায়া স্পষ্ট: অসীম loop-এ ex() কখনো ফেরে না, শুধু নিজেকে আরও গভীরে ডাকে, তাই depth-এর সীমা না থাকলে Python-এর নিজের stack ফুরিয়ে যেত।
৬ · দুই semantics কি একই কথা বলে? — determinism আর equivalence
একই ভাষার জন্য দুটি সংজ্ঞা লেখা হলো। এখন দুটি প্রশ্ন, যার উত্তর প্রমাণ দিয়ে দিতে হয়: একটি program কি একাধিক ফল দিতে পারে? আর small-step ও big-step কি কোনো program-এ আলাদা ফল দেয়? প্রমাণের ভিত্তি structural induction (Discrete Mathematics-এর পর্ব ১০-এর induction-এর গাছ-রূপ)।
Determinism
কোনো value v আর skip-এর জন্য ⟨v, σ⟩ ⟶ c বা ⟨skip, σ⟩ ⟶ c প্রমাণ করা যায় না। কারণ: কোনো নিয়মের conclusion-এর বাঁ পাশে একা একটি value বা একা skip নেই (প্রতিটি নিয়মের তালিকা দেখে মেলানো যায়)।
যেকোনো configuration c-এর জন্য, c ⟶ c1 আর c ⟶ c2 হলে c1 = c2.
প্রমাণ c ⟶ c1-এর derivation-এর ওপর induction; প্রতিটি case-এ c-এর গঠন দেখে দেখানো হবে যে ঠিক একটি নিয়মই খাটতে পারে, আর তার ফল অনন্য। Induction hypothesis (IH): ছোট derivation-এর জন্য দাবিটি সত্য।
- c = ⟨x, σ⟩. শুধু E-Var-এর conclusion এই আকারের; ফল σ(x), যা টেবিলে একটিই।
- c = ⟨e1 ⊕ e2, σ⟩, e1 value নয়. E-Op2 চায় বাঁ পাশ value, E-Op চায় দুই পাশই value, E-DivZero-ও; তাই শুধু E-Op1. দুই ধাপেরই premise ⟨e1, σ⟩ ⟶ …, যার derivation ছোট; IH দিয়ে e1′ একই, তাই c1 = c2.
- e1 = v1, e2 value নয়. E-Op1 চাইত ⟨v1, σ⟩-এর একটি ধাপ, যা Lemma ৪০.১ অনুযায়ী অসম্ভব; E-Op আর E-DivZero চায় e2 value. বাকি শুধু E-Op2, আর IH.
- দুই পাশই value. E-Op1, E-Op2 Lemma দিয়ে বাদ। E-Op-এর শর্ত (/ আর %-এ v2 ≠ 0) আর E-DivZero-এর শর্ত (v2 = 0) একসঙ্গে সত্য হয় না, তাই একটিই খাটে। E-Op-এর ফল v1 ⊕̂ v2 একটি গাণিতিক function, তাই অনন্য।
- && আর ||. একই যুক্তি: বাঁ পাশ value না হলে শুধু E-And1 (IH); value হলে তার মান true না false, সেই অনুযায়ী E-AndTrue বা E-AndFalse, একটিই।
- x = e; আর print(e);. e value না হলে শুধু congruence নিয়ম (IH); value হলে শুধু E-Assign বা E-Print, যার ফল σ[x ↦ v] অনন্য।
- S1 S2. S1 = skip হলে E-Seq1 চাইত skip-এর একটি ধাপ (Lemma দিয়ে অসম্ভব), তাই শুধু E-SeqSkip. নইলে শুধু E-Seq1, আর IH.
- if আর while. if-এ শর্ত value না হলে E-If (IH), value হলে E-IfTrue বা E-IfFalse, একটিই। while-এর নিয়ম একটিই, E-While. ∎
প্রমাণের ভার কোথায় ছিল খেয়াল করুন: case ২ আর ৩-এ E-Op2-এর “v1”, আর case ৪-এ দুটি নিয়মের পরস্পরবিরোধী শর্ত। “v1” সরিয়ে দিলে ⟨a + b, σ⟩ থেকে দুটি আলাদা ধাপ সম্ভব হতো, আর theorem ভেঙে যেত (অনুশীলন ২)। একটি deterministic semantics-এর সরাসরি ফল: ⟶* দিয়ে পৌঁছানো শেষ অবস্থা অনন্য, তাই “এই program-এর আউটপুট” কথাটির একটিই অর্থ।
Small-step আর big-step-এর সমতুল্যতা
যেকোনো Haat-core statement S আর state σ, σ′-এর জন্য: ⟨S, σ⟩ ⟶* ⟨skip, σ′⟩ যদি এবং কেবল যদি ⟨S, σ⟩ ⇓ σ′. Expression-এর জন্যও: ⟨e, σ⟩ ⟶* ⟨v, σ⟩ যদি এবং কেবল যদি ⟨e, σ⟩ ⇓ v.
প্রমাণের রূপরেখা। দুই দিক আলাদা।
- ⇐ (big-step থেকে small-step): ⇓-এর derivation-এর ওপর induction. একটি সহায়ক lemma লাগে, “ধাপকে প্রেক্ষাপটে তোলা”: ⟨S1, σ⟩ ⟶* ⟨S1′, σ′⟩ হলে ⟨S1 S2, σ⟩ ⟶* ⟨S1′ S2, σ′⟩ (ধাপের সংখ্যার ওপর induction, প্রতিবার E-Seq1); একইভাবে x = □; আর if □-এর জন্য। এর পর প্রতিটি big-step নিয়ম একটি ধাপের সারিতে বদলায়। কঠিনতম case B-WhileT: ⟨W, σ⟩ ⟶ ⟨if e {S W} else {skip}, σ⟩ (E-While) ⟶* ⟨if true {…}, σ⟩ (শর্তের IH, E-If দিয়ে তোলা) ⟶ ⟨S W, σ⟩ (E-IfTrue) ⟶* ⟨skip W, σ′⟩ (শরীরের IH আর lemma) ⟶ ⟨W, σ′⟩ (E-SeqSkip) ⟶* ⟨skip, σ″⟩ (তৃতীয় premise-এর IH দিয়ে)।
- ⇒ (small-step থেকে big-step): ধাপের সংখ্যা n-এর ওপর induction. n = 0 হলে S = skip, আর B-Skip. মূল lemma: c ⟶ c′ আর c′ ⇓ σ″ হলে c ⇓ σ″, অর্থাৎ “একটি ধাপ পিছিয়ে গেলেও big-step-এর ফল একই থাকে”। এটি c ⟶ c′-এর derivation-এর ওপর induction. যেমন E-While case: c′ = ⟨if e {S W} else {skip}, σ⟩-এর ⇓-derivation হয় B-IfT (তখন ভেতরে B-Seq দেয় ⟨S, σ⟩ ⇓ σ′ আর ⟨W, σ′⟩ ⇓ σ″, যা জুড়ে B-WhileT) অথবা B-IfF (তখন ফল σ, আর খাটে B-WhileF নিয়মটি)। এরপর n ধাপের সারির শেষ থেকে এক এক করে পিছিয়ে এসে c0 ⇓ σ′ পাওয়া যায়। ∎
Theorem-টি শুধু থামে এমন program-এর কথা বলে: অসীম loop-এ দুই দিকেই কিছু নেই, কিন্তু small-step-এর অসীম সারিটি big-step দেখতে পায় না। Error-এর জন্য একই ধাঁচের theorem চলে, যদি দুই দিকেই error-এর নিয়ম যোগ করা হয়।
প্রমাণ কাগজে, কিন্তু কোড দিয়ে তার একটি শক্ত পরীক্ষা চালানো যায়: অনেক এলোমেলো program দুই semantics-এ চালিয়ে মেলানো। এটি differential testing; প্রমাণের বদলি নয়, কিন্তু কোডে একটি নিয়ম ভুল লেখা হলে প্রায়ই ধরে ফেলে।
# দুই semantics কি একই কথা বলে? ⟶* আর ⇓ মেলানো, তারপর reference-এর আসল আউটপুটের সঙ্গে
import random, collections
def small(t, s, fuel=4000): # ⟨t, σ⟩ ⟶* ⟨skip, σ′⟩ ?
for _ in range(fuel):
if t == "skip": return "ok", s
try: t, s, _ = step(t, s)
except Err: return "error", s["out"] # error-এর আগে পর্যন্ত ছাপা লেখা
return "limit", None
def big(t, s): # ⟨t, σ⟩ ⇓ σ′ ?
names.clear()
try: return "ok", ex(t, s)[0]
except Err: return "error", None # big-step-এর ফলে আংশিক আউটপুট নেই
except RecursionError: return "limit", None
R = random.Random(40)
def gi(d): return R.choice(["a", "b", R.randint(-3, 9)]) if d == 0 or R.random() < .3 \
else (R.choice("+-*/%"), gi(d - 1), gi(d - 1))
def gb(d): return (R.choice(["<", "==", "!="]), gi(1), gi(1)) if d == 0 or R.random() < .4 \
else (R.choice(["&&", "||"]), gb(d - 1), gb(d - 1))
def gs(d):
c = R.randint(0, 4 if d else 1)
if c < 2: return ("=", R.choice("ab"), gi(2)) if c == 0 else ("print", gi(2))
if c == 2: return ("seq", gs(d - 1), gs(d - 1))
if c == 3: return ("if", gb(1), gs(d - 1), gs(d - 1))
return ("while", ("<", "a", 4), seq(gs(d - 1), ("=", "a", ("+", "a", 1))))
tally = collections.Counter()
for _ in range(400):
t, s = gs(3), {"a": R.randint(-2, 2), "b": R.randint(-2, 2), "out": ()}
r1, r2 = small(t, s), big(t, s)
tally[r1[0] if r1[0] == r2[0] and (r1[0] != "ok" or r1[1] == r2[1]) else "অমিল!"] += 1
print("৪০০টি এলোমেলো program:", dict(tally))
loop = seq(("while", ("<", "total", 5000), seq(("=", "total", ("+", "total", 1250)),
("=", "rounds", ("+", "rounds", 1)))), ("print", "total"), ("print", ("-", "rounds", 1)))
share = seq(("print", ("/", 1000, 4)), ("print", ("/", 1000, 0)), ("print", 7))
for t, s in [(loop, {"total": 0, "rounds": 0, "out": ()}), (share, {"out": ()})]:
r = small(t, s); print(r[0], list(r[1]["out"] if r[0] == "ok" else r[1]))আসল আউটপুট (ব্রাউজারের Python):
৪০০টি এলোমেলো program: {'ok': 296, 'limit': 14, 'error': 90}
ok ['5000', '3']
error ['250']
৪০০টি এলোমেলো program (seed 40; প্রতিটিতে দুটি Int variable, assignment, print, if আর while মিশিয়ে) দুই semantics-এ চালানো হলো। ২৯৬টি স্বাভাবিকভাবে শেষ হয়েছে, আর প্রতিটিতে শেষ state (out-সহ) দুই দিকে হুবহু এক; ৯০টিতে দুই দিকেই division by zero; ১৪টি দুই দিকেই সীমায় পৌঁছেছে (small-step-এ ৪০০০ ধাপ, big-step-এ গাছের ২০০ স্তর)। “অমিল!” একবারও আসেনি। শেষ দুই লাইনে bazar.haat-এর loop অংশ (5000, 3) আর অংশ ৪-এর ভাগের ভুলের এক রূপ, যেখানে error-এর আগে 250 ছাপা হয়েছে, small-step-এ।
নিজের বানানো দুটি interpreter মিললেও দুটিতে একই ভুল ধারণা থাকতে পারে, তাই তৃতীয় একটি স্বাধীন বাস্তবায়ন, Haat-এর reference, দিয়েও মেলানো হয়েছে। লেখকের lab-এ একটি script প্রতিটি tuple-program-কে Haat-এর লেখায় ছেপে (শুরুর σ-কে var ঘোষণা বানিয়ে) haat.py run-এ চালিয়েছে। সত্যিকারের run (CPython 3.14.4, Haat reference implementation):
~/haat$ cat order.haat
var qty = 2;
var unit = 520;
var p = 0;
p = qty * unit;
if p >= 1000 {
p = p - p / 10;
}
print(p + 60);
~/haat$ python -B haat.py run order.haat
996
~/haat$ python -B haat.py run share.haat # print(1000 / 4); print(1000 / 0); print(7);
250
2:12: runtime error: division by zero
~/haat$ python -B haat.py run wrap.haat # big = INT_MAX; big + 1, (-7) / 2, (-7) % 2
-9223372036854775808
-3
-1
আটটি নির্দিষ্ট program-এ (অর্ডার, x = 2 + 3 * 4, দুই-ঘোরার loop, bazar-এর loop, দুই রকম ভাগের ভুল, short-circuit, wrap) small-step, big-step আর reference-এর আউটপুট হুবহু এক। তারপর আলাদা seed 7 দিয়ে ২৫০টি এলোমেলো program: ১৮৮টিতে তিনটির আউটপুট এক, ৫০টিতে তিনটিই একই লেখার পরে division by zero, আর ১২টি তিনটিতেই শেষ হয়নি (reference ৫ সেকেন্ডেও থামেনি)। অমিল ০টি। Reference-এ print(7); চলেনি, কারণ সিদ্ধান্ত ২৬ অনুযায়ী runtime error program থামায়, ঠিক যেমন small-step-এ error একটি শেষ অবস্থা।
৭ · Evaluation context, abstract machine আর interpreter
Small-step নিয়মের অর্ধেকই congruence: E-Op1, E-Op2, E-And1, E-Assign1, E-Print1, E-Seq1, E-If. সবগুলো একই কথা বলে, “পরের কাজটি এই অংশের ভেতরে”। এদের একটি ছাঁচে গুটিয়ে আনার কৌশল হলো evaluation context: একটি program, যার ঠিক এক জায়গায় একটি ফাঁকা ঘর □. Haat-core-এর জন্য:
E ::= □ | E ⊕ e | v ⊕ E | E && e | E || e
| x = E; | print(E); | E S | if E { S } else { S }
E[r] মানে ঘরে r বসানো। তখন সব congruence নিয়ম মিলে একটি নিয়ম, আর error-এর ৮টি প্রচার-নিয়ম মিলে আরেকটি:
⟶h মানে শুধু “মাথার” (head) নিয়মগুলো: E-Var, E-Op, E-AndTrue/False, E-OrTrue/False, E-Assign, E-Print, E-SeqSkip, E-IfTrue/False, E-While. যে অংশে head নিয়ম খাটে, তাকে বলে redex (reducible expression). ব্যাকরণটি ভালো করে দেখুন, এতে দুটি সিদ্ধান্ত লুকানো। v ⊕ E আছে, কিন্তু e ⊕ E নেই: ডান পাশের ঘর খোলা যায় শুধু বাঁ পাশ value হলে, অর্থাৎ সিদ্ধান্ত ১২-এর বাঁ-থেকে-ডান। আর E && e আছে, কিন্তু v && E নেই: ডান পাশ কখনো আলাদাভাবে হিসাব হয় না, E-AndTrue তাকে পুরোটা তুলে আনে; এটাই short-circuit. Determinism-এর প্রমাণ এখানে একটি lemma-য় নেমে আসে: প্রতিটি অশেষ configuration-কে E[r] আকারে ভাঙার পথ ঠিক একটি; এর নাম unique decomposition. অর্ডারের হিসাবের ছাড়ের লাইনটি দিয়ে দেখুন; প্রতিটি সারি অংশ ৪-এর trace-এর ধাপ ৯–১৩-এর সঙ্গে মেলানো (পরের print অংশটি বাদ রেখে):
| Configuration (σ = {p ↦ 1040}) | Context E | Redex r | Head নিয়ম |
|---|---|---|---|
p = p - p / 10; | p = □ - p / 10; | p | E-Var |
p = 1040 - p / 10; | p = 1040 - □ / 10; | p | E-Var |
p = 1040 - 1040 / 10; | p = 1040 - □; | 1040 / 10 | E-Op |
p = 1040 - 104; | p = □; | 1040 - 104 | E-Op |
p = 936; | □ | p = 936; | E-Assign |
এই ধারণা সাধারণত Matthias Felleisen আর সহকর্মীদের ১৯৮০-এর দশকের শেষ ভাগের কাজের সঙ্গে যুক্ত (পরিণত রূপ Felleisen–Hieb, ১৯৯২); Wright আর Felleisen ১৯৯৪ সালে type soundness-এর syntactic প্রমাণ এই রীতিতে লেখেন।
Context থেকে abstract machine
অংশ ৪-এর trace-এ দেখেছেন, প্রতিটি ধাপে যন্ত্র program-এর গোড়া থেকে আবার নেমে redex খোঁজে (ধাপ ১০-এ পাঁচ স্তর)। ধাপের পরে আবার গোড়ায় ফেরে, আবার নামে। এটি অপচয়: পরের redex প্রায় সবসময় আগেরটির ঠিক পাশেই। Abstract machine এই অপচয় দূর করে: context E-কে সে প্রতিবার নতুন করে খোঁজে না, একটি stack হিসেবে হাতে রাখে। পরিচিত কয়েকটি:
- SECD machine (Peter Landin, ১৯৬৪): Stack, Environment, Control, Dump, এই চারটি অংশ দিয়ে lambda-expression হিসাব করার প্রথম দিকের যন্ত্র।
- CEK machine (Felleisen আর Friedman, ১৯৮৬–৮৭-এর প্রবন্ধে): Control (এখন যে term হিসাব হচ্ছে), Environment (নাম থেকে মান), আর K, যা হুবহু ওপরের evaluation context, তবে ভেতর থেকে বাইরে একটি stack আকারে, যাকে বলে continuation. প্রতিটি ধাপ এই তিনটির একটি ছোট বদল, কোনো খোঁজ নেই।
এখান থেকে পুরো কোর্সের একটি মানচিত্র দেখা যায়। Big-step নিয়মের সরাসরি কোড-রূপ হলো tree-walking interpreter: reference-এর interp.py-এ eval()-এর Binary শাখা প্রায় হুবহু B-Op (আগে self.eval(e.left, env), তারপর ডান, তারপর arith()), আর while-এর শাখা B-WhileT/B-WhileF, শুধু recursion-এর বদলে Python-এর নিজের loop দিয়ে। পর্ব ৫৬-এ (Tree-walking interpreter) এটি পুরো Haat-এর জন্য বানাবেন। Abstract machine-এর পথ ধরে আরেক ধাপ নামলে আসে bytecode আর virtual machine: পর্ব ৫৮–৫৯-এর Haat VM-এ “পরের কাজ” একটি instruction pointer আর context একটি operand stack, অর্থাৎ CEK-এর K আরও নিচু স্তরে।
আরও গভীরে। “Structural operational semantics” নামটি সাধারণত Gordon Plotkin-এর ১৯৮১ সালের Aarhus বিশ্ববিদ্যালয়ের lecture notes (DAIMI FN-19) থেকে ধরা হয়, যা ২০০৪ সালে একটি journal-এ পুনঃপ্রকাশিত হয়; “natural semantics” নামটি Gilles Kahn-এর ১৯৮৭ সালের প্রবন্ধ থেকে। Big-step-এর অসীম loop-এর দুর্বলতা দূর করতে Xavier Leroy আর Hervé Grall ২০০৯ সালের দিকে coinductive big-step semantics নিয়ে কাজ করেন, যা অসীম derivation-কেও গ্রহণ করে; এর কিছু ধারণা CompCert-এর মতো verified compiler-এর প্রসঙ্গে এসেছে (পর্ব ৪৪)। বাস্তব ভাষার পূর্ণ operational semantics-ও লেখা হয়েছে: The Definition of Standard ML (১৯৯০) পুরোটা natural semantics-এ, WebAssembly-র আনুষ্ঠানিক spec small-step reduction নিয়মে, আর K framework দিয়ে C-র একটি চালানো যায় এমন semantics (Ellison ও Roşu, ২০১২-র দিকে)।
পরীক্ষা ও ইন্টারভিউতে। বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন সাধারণ:
- “Small-step আর big-step-এর পার্থক্য লিখুন।” Small-step: ⟨S, σ⟩ ⟶ ⟨S′, σ′⟩, মাঝের সব অবস্থা দেখা যায়, অসীম loop আর stuck আলাদা করা যায়; big-step: ⟨S, σ⟩ ⇓ σ′, ফল একটি derivation গাছ, interpreter-এর কাছাকাছি, কিন্তু divergence আর stuck দুটিই “গাছ নেই”।
- “এই statement-এর small-step trace লিখুন।” প্রতিটি ধাপে বাইরে থেকে redex খুঁজুন, নিয়মের শিকল লিখুন (যেমন E-Assign1(E-Op2(E-Op))), আর প্রতিটি ধাপের পরে পুরো configuration আবার লিখুন।
- “এই while loop-এর big-step derivation আঁকুন।” প্রতিটি ঘোরায় একটি B-WhileT (শর্ত, শরীর, বাকি loop), শেষে একটি B-WhileF; state-গুলোর নাম দিন σ0, σ1, …
- “Stuck configuration কী, উদাহরণ দিন।” শেষ অবস্থা নয় অথচ কোনো নিয়ম খাটে না, যেমন ⟨true + 1, σ⟩; type soundness প্রমাণ করে well-typed program এখানে পৌঁছায় না।
- “Semantics deterministic, প্রমাণ করুন।” Derivation-এর ওপর induction; প্রতিটি গঠনে ঠিক একটি নিয়ম খাটে (value আর skip নড়ে না), IH দিয়ে ভেতরের ধাপ অনন্য।
৮ · AI-এর যুগে operational semantics
AI assistant-এর কাছে একটি ভাষার semantics বা একটি expression-এর trace চাইলে সে দ্রুত সুন্দর উত্তর দেয়। সমস্যা হলো, ভুল নিয়মও দেখতে নিয়মের মতো, ভুল trace-ও trace-এর মতো। সাধারণ ভুলগুলো:
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| এক ভাষার নিয়ম সব ভাষায়: “argument সবসময় বাঁ থেকে ডানে হিসাব হয়” (C17-এ unspecified), বা “শূন্য দিয়ে ভাগে exception হয়” (C-তে UB) | ভাষার নাম আর version-সহ spec পড়া; ছোট program আসল compiler বা interpreter-এ চালানো |
| E-Op2-এর মতো congruence নিয়মে “v1” শর্ত বাদ দেওয়া, ফলে নিয়ম non-deterministic হয়ে যায়, অথচ সঙ্গে দাবি “semantics deterministic” | প্রতিটি নিয়মের বাঁ পাশ মিলিয়ে দেখা: একই configuration-এ দুটি নিয়ম খাটে কি না |
| ⟶ আর ⇓ গুলিয়ে ফেলা, বা দাবি করা “big-step দিয়ে অসীম loop আর stuck আলাদা করা যায়” | Judgment-এর আকার পড়া: ⇓-এর ডানে শেষ ফল, মাঝের অবস্থা নেই |
হাতে লেখা trace, যেখানে ধাপের সংখ্যা ভুল বা দুটি ধাপ একসঙ্গে জোড়া (যেমন 2 + 3 * 4 এক ধাপে 14) | নিজের ছোট step() চালিয়ে প্রতিটি configuration মেলানো |
| ইতিহাসের ভুল নাম বা সাল (SOS, natural semantics, CEK কার, কবে), বা অস্তিত্বহীন paper | প্রাথমিক উৎস খোঁজা; নিশ্চিত না হলে “সাধারণত বলা হয়” লেখা |
| প্রমাণে case বাদ দেওয়া (যেমন determinism-এ E-Op বনাম E-DivZero) | প্রতিটি নিয়মের জন্য একটি case আছে কি না গুনে দেখা; differential test চালানো |
AI-কে কাজে লাগাতে ভাষার নিয়ম আর আপনার নোটেশন স্পষ্ট বলে দিন, আর প্রতিটি দাবির যাচাইয়ের উপায় চান:
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১বেশিরভাগ জনপ্রিয় ভাষার spec গদ্যে লেখা। তাহলে কি তাদের কোনো operational semantics নেই?
আছে, তবে প্রায়ই ছদ্মবেশে। JavaScript-এর spec, ECMA-262, পড়লে দেখবেন প্রতিটি operator আর statement-এর অর্থ লেখা আছে সংখ্যা দেওয়া ধাপের তালিকায়: “১. lref হলো বাঁ পাশের expression-এর হিসাবের ফল। ২. lval হলো GetValue(lref) …”। এটি একটি কাল্পনিক যন্ত্রের ধাপে ধাপে চলা, অর্থাৎ গদ্যে লেখা operational semantics, অনেকটা big-step ধাঁচের, কারণ প্রতিটি “হিসাব করা” একটি recursive call. বাঁ থেকে ডানে ক্রম তাই ধাপের ক্রম থেকেই আসে। ২০১০ সালে Guha, Saftoiu ও Krishnamurthi “The Essence of JavaScript” প্রবন্ধে JavaScript-এর মূল অংশ একটি ছোট core ভাষায় (λJS) নামিয়ে তার small-step semantics লেখেন, বাকিটা desugaring দিয়ে সেই core-এ আনা হয়; এই পর্বের Haat-core ঠিক সেই কৌশলের শিক্ষা-রূপ।
Python-এর Language Reference বেশি ঢিলে গদ্যে লেখা, আর অনেক প্রশ্নের চূড়ান্ত উত্তর আসলে CPython-এর আচরণ। C-র standard আবার ভিন্ন পথ নেয়: সে একটি “abstract machine” বর্ণনা করে, যার আচরণের সঙ্গে প্রোগ্রামের দৃশ্যমান ফল মিলতে হবে, কিন্তু অনেক জায়গায় ইচ্ছা করে ফলটিকে “unspecified” বা “undefined” রেখে দেয়। অর্থাৎ C-র semantics একটি অ-নির্ধারিত (non-deterministic) আর আংশিক semantics: কিছু program-এর একাধিক বৈধ ফল, কিছুর কোনো অর্থই নেই।
অন্য প্রান্তে আছে পুরোপুরি গাণিতিক spec. Standard ML-এর সংজ্ঞা (১৯৯০, সংশোধিত ১৯৯৭) পুরো ভাষার dynamic semantics natural semantics-এ লিখেছে, আর WebAssembly-র spec প্রতিটি instruction-এর অর্থ small-step reduction নিয়মে দেয়, পাশে একটি reference interpreter-সহ। এর ফল চোখে পড়ার মতো: নতুন engine বানানো দল জানে প্রতিটি কোণার case-এ কী করতে হবে, আর নিয়মগুলো proof assistant-এ তুলে ধর্ম প্রমাণ করা যায়। দাম হলো পাঠযোগ্যতা: অধিকাংশ programmer নিয়মের দাগ পড়তে অভ্যস্ত নন।
মূল উপলব্ধি: গদ্যের spec-ও প্রায়ই operational semantics, শুধু অনানুষ্ঠানিক; পার্থক্য হলো ফাঁকগুলো খুঁজে পাওয়া, যন্ত্রে চালানো আর প্রমাণ করার সহজতায়, আর এই কারণেই নিরাপত্তা-সংবেদনশীল নতুন ভাষাগুলো formal spec-এর দিকে ঝুঁকছে।
প্র ০২Small-step আর big-step দুটিই যদি একই ফল দেয়, তাহলে দুটি রাখার দরকার কী? কখন কোনটি বেছে নেবেন?
Theorem ৪০.৩ বলে থামে এমন program-এ দুটি একই কথা বলে। কিন্তু যেখানে দুটির ক্ষমতা আলাদা, সেখানেই বাছাইয়ের প্রশ্ন। Big-step-এর পক্ষে প্রথম যুক্তি সরলতা: নিয়ম কম, derivation গাছ program-এর গঠনের সঙ্গে মেলে, আর interpreter লেখা প্রায় নিয়ম থেকে কপি করা। এই পর্বের ex() আর reference-এর interp.py দুটিই তার প্রমাণ। Compiler-এর সঠিকতা প্রমাণেও big-step প্রায়ই সুবিধাজনক, কারণ “source আর target একই শেষ state দেয়” কথাটি সরাসরি লেখা যায়।
Small-step-এর পক্ষে তিনটি বড় যুক্তি। প্রথম, অসীম loop আর stuck আলাদা করা (অংশ ৫): type soundness-এর আধুনিক প্রমাণ (progress আর preservation) পুরোটাই small-step-এর ওপর দাঁড়ানো, কারণ “কখনো আটকায় না, যদিও চিরকাল চলতে পারে” বলতে মাঝের অবস্থা লাগে। দ্বিতীয়, concurrency: দুটি thread একসঙ্গে চললে তাদের ধাপগুলো পরস্পরের মাঝে ঢুকে যায়, যাকে বলে interleaving. Small-step-এ এটি সহজে লেখা যায়, “যেকোনো একটি thread-এর একটি ধাপ নেওয়া”; big-step-এ প্রতিটি thread-এর পুরো ফল একবারে আসে, তাই মাঝের মিশ্রণ বলার জায়গাই নেই। পর্ব ৭৭-এর memory model-এর আলোচনা তাই ধাপ-ভিত্তিক। তৃতীয়, error-এর সূক্ষ্মতা: কতটুকু output হয়ে গেছে, কোন অবস্থায় থেমেছে, small-step স্বাভাবিকভাবেই রাখে।
বাস্তবে গবেষকেরা প্রায়ই দুটিই লেখেন আর সমতুল্যতা প্রমাণ করেন, তারপর যেটি যে কাজে সুবিধার, সেটি ব্যবহার করেন। Big-step-এর অসীম loop-এর দুর্বলতা সারাতে coinductive big-step-ও প্রস্তাবিত হয়েছে (Leroy আর Grall, ২০০৯-এর দিকে), যেখানে অসীম গাছও বৈধ derivation. আবার উল্টো দিকে, প্রমাণ-সহায়ক যন্ত্রে বড় ভাষার semantics লেখার সময় অনেকে “functional big-step” পছন্দ করেন: একটি fuel-সহ interpreter function, যা এই পর্বের depth-সীমার গাণিতিক রূপ।
মূল উপলব্ধি: big-step সরল আর interpreter-ঘনিষ্ঠ, small-step সূক্ষ্ম আর প্রমাণ-বান্ধব; non-termination, concurrency আর type soundness-এর প্রশ্নে small-step প্রায় অপরিহার্য, তাই গুরুত্বপূর্ণ ভাষায় প্রায়ই দুটিই লেখা হয় আর মেলানো হয়।
প্র ০৩Haat ইচ্ছা করে deterministic: সিদ্ধান্ত ১২ বাঁ-থেকে-ডান ক্রম বেঁধে দেয়। C কেন ক্রম খোলা রেখেছে, আর এর দাম কে দেয়?
C-র নকশাকারদের দৃষ্টিতে ক্রম খোলা রাখলে compiler স্বাধীনভাবে register আর instruction সাজাতে পারে। f(a(), b())-এ কোনো CPU-র calling convention-এ ডানের argument আগে stack-এ ঠেলা সুবিধার, অন্যটিতে বাঁয়ের। Standard সেই স্বাধীনতা দেয়, আর বিনিময়ে বলে: যে program-এর ফল এই ক্রমের ওপর নির্ভর করে, তার ফল unspecified, আর একই variable-এ ক্রমহীন দুটি লেখা undefined. Semantics-এর ভাষায় C-র ধাপ-সম্পর্ক non-deterministic: একটি configuration থেকে কয়েকটি বৈধ ধাপ।
দাম দেয় তিন পক্ষ। Programmer: একই কোড এক compiler-এ ঠিক, আরেকটিতে ভুল, অথচ দুটিই “standard মানে”। Tester: differential testing-এ দুই compiler-এর আউটপুট না মিললে বোঝা যায় না সেটি bug, নাকি দুটিই বৈধ পছন্দ। এই কারণেই Csmith নামের বিখ্যাত C compiler testing tool (Yang, Chen, Eide আর Regehr, PLDI ২০১১) এমন program বানায়, যাতে কোনো undefined বা unspecified আচরণ না থাকে; নইলে অমিল থেকে কিছু শেখা যেত না। আর verification: non-deterministic semantics-এ “এই program সঠিক” মানে প্রতিটি সম্ভাব্য পথে সঠিক, যা প্রমাণে অনেক বেশি case আনে।
Java আর JavaScript এই দাম দিতে রাজি হয়নি: দুটিই বাঁ-থেকে-ডান ক্রম spec-এ বেঁধে দিয়েছে, আর optimizer যা খুশি সাজাতে পারে শুধু যতক্ষণ দৃশ্যমান ফল একই থাকে। Haat শেখার ভাষা হিসেবে আরও এক ধাপ এগিয়েছে: deterministic semantics থাকায় Theorem ৪০.২ প্রমাণ করা গেল, আর অংশ ৬-এর differential test-এ প্রতিটি অমিল নিশ্চিতভাবে একটি bug হতো।
তবে একটি জায়গায় non-determinism এড়ানো যায় না: concurrency. দুটি thread-এর ধাপ কোন ক্রমে মিশবে, তা scheduler ঠিক করে, ভাষা নয়। সেখানে semantics-এর কাজ হলো সব বৈধ মিশ্রণের সেট নির্ধারণ করা, আর data race-এর মতো বিপজ্জনক অবস্থা চিহ্নিত করা (পর্ব ৭৭)।
মূল উপলব্ধি: ক্রম খোলা রাখা compiler-কে সামান্য স্বাধীনতা দেয়, কিন্তু programmer, tester আর prover-এর ঘাড়ে বড় বোঝা চাপায়; তাই নতুন ভাষাগুলো sequential অংশে determinism বেছে নেয়, আর non-determinism রাখে শুধু যেখানে তা বাস্তব, যেমন concurrency.
প্র ০৪Haat-এ শূন্য দিয়ে ভাগ একটি ঘোষিত runtime error, আর C-তে তা undefined behavior; semantics-এর ভাষায় এই দুটি সিদ্ধান্তের পার্থক্য কী, আর type system কোথায় ঢোকে?
অংশ ৪-এর ভাষায়: C-তে ⟨1000 / 0, σ⟩ একটি stuck configuration, যার জন্য standard কোনো নিয়ম দেয় না। “Undefined” মানে এটাই, “কোনো সংজ্ঞা নেই”। এর বাস্তব ফল ভয়ের: optimizer ধরে নিতে পারে এমন অবস্থা কখনো আসে না, তাই if (d == 0) জাতীয় পরীক্ষাকে কখনো কখনো এমনভাবে সাজিয়ে ফেলে, যা programmer ভাবেননি। Haat E-DivZero নিয়ম যোগ করে অবস্থাটিকে একটি শেষ অবস্থা, error, বানিয়েছে: প্রতিটি বাস্তবায়ন থামবে, একই বার্তা দেবে, একই অবস্থান জানাবে, যেমন 2:12: runtime error: division by zero লাইনটি। Java-র ArithmeticException আর Python-এর ZeroDivisionError-ও একই জাতের সিদ্ধান্ত।
Type system এই ছবিতে খুব নির্দিষ্ট একটি ভূমিকা নেয়। Robin Milner ১৯৭৮ সালের প্রবন্ধে লেখেন, “well-typed programs cannot go wrong”, যেখানে “wrong” একটি বিশেষ ফল, অর্থহীন অবস্থা। আধুনিক ভাষায়: well-typed program কখনো stuck হয় না। কিন্তু খেয়াল করুন, সব খারাপ জিনিস stuck নয়। Haat-এর type checker শূন্য দিয়ে ভাগ ঠেকাতে পারে না, কারণ ভাজকের মান চালানোর আগে সাধারণভাবে জানা যায় না। তাই নকশাকার একটি ভাগ করে দেন: কিছু ভুল “type error”, যা stuck অবস্থা আর type system যা অসম্ভব করে; বাকিগুলো “অনুমোদিত runtime error”, যার জন্য স্পষ্ট নিয়ম আছে। Type soundness theorem তখন বলে: well-typed program হয় থামে, হয় অনুমোদিত error দেয়, হয় চিরকাল চলে; কিন্তু কখনো stuck হয় না।
কোন ভুল কোন দিকে পড়বে, তা একটি নকশার সিদ্ধান্ত। Array-র সীমার বাইরে পড়া Java-তে অনুমোদিত runtime error (exception), C-তে UB, আর dependent type-ওয়ালা ভাষায় (পর্ব ৩৯) এটিকে type error বানানো সম্ভব। Rust-এর safe অংশ ঠিক এই রেখা টেনেছে: memory-র ভুল stuck-জাতীয় হতে দেয় না, তাই type আর borrow checker সেগুলো আগেই ঠেকায়, আর বাকি সমস্যা (যেমন overflow-এ debug build-এ panic) ঘোষিত runtime আচরণ।
মূল উপলব্ধি: stuck মানে ভাষা নীরব, error মানে ভাষা নিয়ম দিয়েছে; type soundness প্রতিশ্রুতি দেয় যে well-typed program নীরব অবস্থায় পৌঁছায় না, আর কোন ভুল কোন শ্রেণিতে পড়বে, সেটিই ভাষা নকশার একটি কেন্দ্রীয় সিদ্ধান্ত।
প্র ০৫Interpreter কি নিজেই একটি semantics? একটি ভাষার অর্থ বলতে তার reference interpreter-কে নিলে ক্ষতি কী?
John Reynolds ১৯৭২ সালের “Definitional interpreters for higher-order programming languages” প্রবন্ধে ঠিক এই প্রশ্ন তোলেন। একটি ভাষার অর্থ বোঝাতে আরেকটি ভাষায় তার interpreter লেখা, যাকে বলে definitional interpreter, খুব পুরনো কৌশল: John McCarthy-র LISP-এর eval (১৯৬০-এর দিকে) LISP-এ লেখা LISP-এর অর্থ। Reynolds দেখান, এর একটি গোপন ফাঁদ আছে: যে ভাষায় interpreter লেখা, তার নিজের semantics ঢুকে পড়ে। যেমন এই পর্বের ev()-এ B-Op-এর দুই premise বাঁ থেকে ডানে চলে শুধু এই কারণে যে Python বাঁ থেকে ডানে চলে; যদি interpreter-এর ভাষা lazy হতো, Haat-ও অজান্তে lazy হয়ে যেত। Reynolds এই নির্ভরতা কাটানোর পথ দেখান continuation-passing style আর defunctionalization দিয়ে, যা পরে abstract machine-এর সঙ্গে সরাসরি সম্পর্ক পায়; Olivier Danvy ও সহকর্মীরা ২০০০-এর দশকে দেখান, একটি সাধারণ interpreter থেকে এই রূপান্তরগুলো চালিয়ে CEK-এর মতো machine যান্ত্রিকভাবে পাওয়া যায়।
Reference interpreter-কে spec বানানোর বাস্তব সুবিধা অনেক: তা চালানো যায়, test করা যায়, আর গদ্যের ফাঁক রাখে না। কিন্তু অসুবিধাও গুরুতর। এক, কোডের প্রতিটি দুর্ঘটনা (একটি bug, একটি অদ্ভুত error-বার্তার ক্রম) “spec” হয়ে যায়। দুই, কোড থেকে ধর্ম প্রমাণ করা কঠিন: determinism বা type soundness প্রমাণ করতে কোডকে আগে নিয়মে অনুবাদ করতে হয়। তিন, কোড ইচ্ছাকৃত non-determinism বলতে পারে না; সে সবসময় একটি পছন্দ বেছে নেয়।
এই কারণে ভালো চর্চা হলো দুটিই রাখা আর মেলানো: আনুষ্ঠানিক নিয়ম আর চালানো যায় এমন reference. WebAssembly এই পথে চলে (spec-এর নিয়ম আর একটি reference interpreter, সঙ্গে বড় test suite); এই পর্বও ছোট আকারে তাই করেছে: নিয়ম, দুটি স্বাধীন interpreter আর reference, আর তিনটির মধ্যে differential test. কোথাও অমিল পেলে প্রশ্ন ওঠে, ভুল নিয়মে না কোডে, আর সেই প্রশ্নই spec-কে ধারালো করে।
মূল উপলব্ধি: interpreter একটি চালানো যায় এমন semantics, কিন্তু সে নিজের host ভাষার অর্থ আর নিজের দুর্ঘটনা বহন করে; আনুষ্ঠানিক নিয়ম আর reference interpreter পাশাপাশি রেখে মেলানোই সবচেয়ে নির্ভরযোগ্য পথ।
অনুশীলন
প্রথমে নিজে লিখুন বা হিসাব করুন, তারপর উত্তর খুলুন। প্রতিটি উত্তর চালানো কোড বা reference দিয়ে যাচাই করা।
-
নকশা ও বাস্তবায়ন — unary
-আর!: Haat-core-এ unary-eআর!eযোগ করুন। (ক) Small-step-এর চারটি নিয়ম (E-Neg1, E-Neg, E-Not1, E-Not) আর big-step-এর দুটি (B-Neg, B-Not) লিখুন; সিদ্ধান্ত ১৩ মনে রাখুন। (খ) অংশ ৩-এরstep()-কে না বদলে একটি মোড়ক function লিখুন, যা AST-এ("neg", e)আর("not", e)বোঝে। (গ)print(-(-9223372036854775807 - 1));আরprint(!(1 < 2) || 3 >= 3 && 2 != 2);-এ কয়টি ধাপ, কী ছাপা হবে?(ক) E-Neg1: ⟨e, σ⟩ ⟶ ⟨e′, σ⟩ হলে ⟨-e, σ⟩ ⟶ ⟨-e′, σ⟩; E-Neg: ⟨-n, σ⟩ ⟶ ⟨wrap(−n), σ⟩, যেখানে wrap মানে ৬৪ বিটে ফেরানো (সিদ্ধান্ত ১৩)। E-Not1 একই আকারের, E-Not: ⟨!true, σ⟩ ⟶ ⟨false, σ⟩ আর ⟨!false, σ⟩ ⟶ ⟨true, σ⟩. Big-step: ⟨e, σ⟩ ⇓ n হলে ⟨-e, σ⟩ ⇓ wrap(−n) (B-Neg); ⟨e, σ⟩ ⇓ b হলে ⟨!e, σ⟩ ⇓ ¬b (B-Not). (খ) পুরনো
step-কে একটি নামে রেখে নতুনstepসংজ্ঞায়িত করলেই চলে, কারণsub()নামটি চলার সময় খোঁজে:old_step = step def step(t, s): # Haat-এর বর্ধিত core: ("neg", e) আর ("not", e) if isinstance(t, tuple) and t[0] in ("neg", "not"): if not isv(t[1]): return sub(t, 1, s, "E-Neg1" if t[0] == "neg" else "E-Not1") return (wrap(-t[1]), s, "E-Neg") if t[0] == "neg" else (not t[1], s, "E-Not") return old_step(t, s)(গ) লেখকের lab-এ চালানো (CPython 3.14.4; ছাপার জন্য
pe()-তেও দুটি শাখা যোগ করে): প্রথমটি ৪ ধাপে, নিয়ম E-Print1(E-Neg1(E-Op1(E-Neg))), E-Print1(E-Neg1(E-Op)), E-Print1(E-Neg), E-Print; ছাপে-9223372036854775808. Literal9223372036854775807-এর আগের--ও একটি unary operator, তাই প্রথম ধাপটিই E-Neg. শেষ E-Neg-এ −(INT_MIN) wrap হয়ে আবার INT_MIN, ঠিক সিদ্ধান্ত ১৩ যা বলে। দ্বিতীয়টি ৭ ধাপে: E-Op (1 < 2), E-Not, E-OrFalse, E-Op (3 >= 3), E-AndTrue, E-Op (2 != 2), E-Print; ছাপেfalse. Reference-এ দুটি লাইন একসঙ্গে চালিয়ে সত্যিকারের run-এ এসেছে-9223372036854775808আরfalse. -
ভুল খুঁজুন — একটি “সরল” নিয়ম: একজন সহকর্মী বললেন, E-Op2-এ v1 লেখা অপ্রয়োজনীয় জটিলতা, আর লিখলেন: ⟨e2, σ⟩ ⟶ ⟨e2′, σ⟩ হলে ⟨e1 ⊕ e2, σ⟩ ⟶ ⟨e1 ⊕ e2′, σ⟩ (E-Op2′). তাঁর যুক্তি: “Haat-core-এর expression-এ side effect নেই, তাই শেষ ফল তো একই।” (ক) কোন theorem ভাঙে, একটি configuration দিয়ে দেখান। (খ) পুরো Haat-এ, যেখানে function call print করতে পারে, নিচের program-এ কী পার্থক্য হতো?
fn tag(s: Str, n: Int) -> Int { print(s); return n; } print(tag("left", 1000) + tag("right", 0)); print(tag("left", 1000) / tag("right", 0));(ক) Determinism (Theorem ৪০.২) ভাঙে। σ = {a ↦ 1, b ↦ 2} হলে ⟨a + b, σ⟩ থেকে এখন দুটি ধাপ: E-Op1 দিয়ে ⟨1 + b, σ⟩, আর E-Op2′ দিয়ে ⟨a + 2, σ⟩. দুটি আলাদা configuration. প্রমাণের case ২-এ আমরা বলেছিলাম “E-Op2 চায় বাঁ পাশ value”, এই যুক্তিটিই আর খাটে না। সহকর্মীর কথাও আংশিক সত্য: side effect না থাকলে দুই পথ শেষে একই মানে পৌঁছায় (এই গুণের নাম confluence), কিন্তু ধাপ-স্তরে semantics আর deterministic নয়, আর সিদ্ধান্ত ১২-এর ক্রম নিয়ম থেকে হারিয়ে যায়।
(খ) Reference-এ সত্যিকারের run:
left,right,1000, তারপর আবারleft,right, আর শেষে6:25: runtime error: division by zero(কলাম ২৫ হলো/)। সিদ্ধান্ত ১২ অনুযায়ী বাঁ call আগে, তাই প্রতিবারleftআগে ছাপে। E-Op2′ থাকলে ডান call আগে চলার পথও বৈধ হতো, অর্থাৎrightআগে ছাপতে পারত: একই program-এর দুটি ভিন্ন আউটপুট, ঠিক C-র unspecified argument order-এর সমস্যা। শিক্ষা: “ফল তো একই” যুক্তি side effect-হীন core-এ সত্য হলেও পুরো ভাষায় ছড়িয়ে দিলে ভাঙে; নিয়ম লিখতে হয় পুরো ভাষার কথা ভেবে। -
হিসাব — trace আর ফল আন্দাজ: σ = {a ↦ 0, b ↦ 7, m ↦ 0} থেকে নিচের Haat-core program-এর small-step trace লিখুন। মোট কয়টি ধাপ, কী ছাপা হবে, আর শূন্য দিয়ে ভাগ কেন হয় না? তারপর a ↦ 2 নিয়ে একই প্রশ্ন।
if a != 0 && b / a > 2 { m = b; } else { m = a; } print(m);অংশ ৪-এর
trace()দিয়ে চালানো (লেখকের lab, CPython 3.14.4). a ↦ 0: ৯টি ধাপ। ১: E-Seq1(E-If(E-And1(E-Op1(E-Var)))) →0 != 0 && …; ২: E-Op দিয়েfalse && b / a > 2; ৩: E-AndFalse →if false { … }, ডান পাশ ছোঁয়াই হয়নি; ৪: E-IfFalse →m = a; print(m);; ৫: E-Var →m = 0;; ৬: E-Assign; ৭: E-SeqSkip; ৮: E-Print1(E-Var) →print(0);; ৯: E-Print. ছাপে0.b / aকখনো redex হয়নি, কারণ E-AndFalse পুরো ডান পাশটি ফেলে দেয়; এটাই short-circuit-কে “পাহারা” হিসেবে ব্যবহার।a ↦ 2: ১৩টি ধাপ। শর্ত true হয় (ধাপ ২), E-AndTrue ডান পাশ তুলে আনে (ধাপ ৩), তারপর
7 / a,7 / 2,3 > 2(ধাপ ৪–৬; 7 / 2 = 3, শূন্যের দিকে কাটা),true(ধাপ ৭), E-IfTrue,m = 7;, E-Assign, E-SeqSkip, E-Print1, E-Print. ছাপে7. Reference-এ দুটি সংস্করণইvarদিয়ে লিখে চালালে একই0আর7আসে। Big-step-এ a ↦ 0-এর গাছে B-AndF-এর premise একটিই (⟨a != 0, σ0⟩ ⇓ false);b / a-এর কোনো judgment গাছে নেই। -
প্রমাণ — loop খোলা: Big-step নিয়ম দিয়ে প্রমাণ করুন: যেকোনো e, S, σ, σ′-এর জন্য ⟨while e {S}, σ⟩ ⇓ σ′ যদি এবং কেবল যদি ⟨if e {S while e {S}} else {skip}, σ⟩ ⇓ σ′. Small-step-এ একই কথা এক লাইনে কেন?
W = while e {S}, আর U = if e {S W} else {skip}. (⇒) ⟨W, σ⟩ ⇓ σ′-এর derivation-এর শেষ নিয়ম দুটির একটি।
- B-WhileF: তখন ⟨e, σ⟩ ⇓ false আর σ′ = σ. B-Skip দেয় ⟨skip, σ⟩ ⇓ σ, তাই B-IfF দিয়ে ⟨U, σ⟩ ⇓ σ.
- B-WhileT: তখন ⟨e, σ⟩ ⇓ true, ⟨S, σ⟩ ⇓ σ1, ⟨W, σ1⟩ ⇓ σ′. শেষ দুটি থেকে B-Seq দেয় ⟨S W, σ⟩ ⇓ σ′, আর প্রথমটির সঙ্গে B-IfT দেয় ⟨U, σ⟩ ⇓ σ′.
(⇐) ⟨U, σ⟩ ⇓ σ′-এর শেষ নিয়ম B-IfT বা B-IfF.
- B-IfF: ⟨e, σ⟩ ⇓ false আর ⟨skip, σ⟩ ⇓ σ′; skip-এর একমাত্র নিয়ম B-Skip, তাই σ′ = σ, আর B-WhileF দেয় ⟨W, σ⟩ ⇓ σ.
- B-IfT: ⟨e, σ⟩ ⇓ true আর ⟨S W, σ⟩ ⇓ σ′. Sequencing-এর একমাত্র নিয়ম B-Seq, তাই কোনো σ1-এর জন্য ⟨S, σ⟩ ⇓ σ1 আর ⟨W, σ1⟩ ⇓ σ′. তিনটি জুড়ে B-WhileT. ∎
এখানে induction লাগেনি, শুধু “শেষ নিয়ম কোনটি হতে পারে” বিশ্লেষণ, যার নাম inversion. Small-step-এ E-While নিজেই বলে ⟨W, σ⟩ ⟶ ⟨U, σ⟩, আর determinism আছে বলে W থেকে যেকোনো সারি এই ধাপ দিয়েই শুরু হয়; তাই দুটির ⟶*-ফল একই, এক লাইনে। পর্ব ৪১-এ (Denotational semantics) একই সমতা ⟦W⟧ = ⟦U⟧ আকারে আসবে, আর সেখান থেকে loop-এর অর্থ fixpoint হিসেবে।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমHaat-core-এর small-step semantics-এ (বাঁ operand আগে) σ = {p ↦ 1040} থেকে p = p - p / 10; চলছে। Configuration-গুলো যে ক্রমে আসে, সেভাবে সাজান (▲▼ চেপে সরান)
- ⟨p = p - p / 10;, σ⟩
- ⟨p = 1040 - p / 10;, σ⟩
- ⟨p = 1040 - 1040 / 10;, σ⟩
- ⟨p = 1040 - 104;, σ⟩
- ⟨p = 936;, σ⟩
- ⟨skip, {p ↦ 936}⟩
Haat-core-এর small-step semantics-এ (বাঁ operand আগে, E-Op1/E-Op2/E-Op আর E-Assign1/E-Assign নিয়ম) σ = {x ↦ 0} থেকে x = 2 + 3 * 4;-এর প্রথম ধাপে কোন নিয়মের শিকল খাটে?
- E-Assign
- E-Assign1(E-Op2(E-Op))
- E-Assign1(E-Op1(E-Op))
- E-Assign1(E-Op), সরাসরি 14
কোন প্রশ্নের উত্তর small-step semantics দিতে পারে, কিন্তু সাধারণ (inductive) big-step semantics পারে না?
- একটি থামা program-এর শেষ state কী
- শূন্য দিয়ে ভাগে program error দেয় কি না
- &&-এর ডান পাশ হিসাব হয় কি না
- একটি program চিরকাল চলছে, নাকি আটকে গেছে
Small-step নিয়ম E-Op2: “⟨e₂, σ⟩ ⟶ ⟨e₂′, σ⟩ হলে ⟨v₁ ⊕ e₂, σ⟩ ⟶ ⟨v₁ ⊕ e₂′, σ⟩”. বাঁ পাশে e₁ না লিখে v₁ (একটি value) লেখার মূল কাজ কী?
- বাঁ operand আগে হিসাব হওয়া নিশ্চিত করা, আর তাতে semantics deterministic রাখা
- Int overflow-এ wrap নিশ্চিত করা
- Short-circuit চালু করা
- শূন্য দিয়ে ভাগ ধরা
Short-circuit নিয়মসহ (E-AndFalse: ⟨false && e₂, σ⟩ ⟶ ⟨false, σ⟩) Haat-core-এ σ = {stock ↦ 0} থেকে print(stock != 0 && 100 / stock > 2); চালালে কী হয়?
- division by zero runtime error
- true ছাপা হয়
- false ছাপা হয়
- configuration stuck হয়
Big-step নিয়মে (B-WhileT: শর্ত true, শরীর, তারপর আবার while; B-WhileF: শর্ত false) σ₀ = {total ↦ 0} থেকে while total < 2500 { total = total + 1250; }-এর derivation-এ কয়টি B-WhileT আর কয়টি B-WhileF থাকে?
- ১টি B-WhileT, ১টি B-WhileF
- ২টি B-WhileT, ১টি B-WhileF
- ৩টি B-WhileT, ১টি B-WhileF
- ২টি B-WhileT, ২টি B-WhileF
Operational semantics-এ একটি configuration-কে “stuck” বলা হয় কখন?
- যখন বাকি program skip
- যখন program একটি অসীম loop-এ ঢোকে
- যখন E-DivZero খেটে error হয়
- যখন configuration শেষ অবস্থা নয়, অথচ কোনো নিয়ম খাটে না
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Configuration আর ধাপ: ⟨S, σ⟩ = বাকি program + state. Small-step ⟨S, σ⟩ ⟶ ⟨S′, σ′⟩ এক ধাপ, ⟶* অনেক ধাপ; congruence নিয়ম কাজ খুঁজে দেয়, computation নিয়ম কাজটি করে।
- Big-step: ⟨e, σ⟩ ⇓ v আর ⟨S, σ⟩ ⇓ σ′; প্রমাণ একটি derivation গাছ, প্রতিটি loop-ঘোরায় একটি B-WhileT, চূড়ায় B-WhileF. এটিই tree-walking interpreter-এর নকশা।
- তিন রকম শেষ: skip (স্বাভাবিক), error (ঘোষিত, যেমন E-DivZero), আর stuck (নিয়মহীন, type soundness যা ঠেকায়); অসীম loop small-step-এ অসীম সারি, big-step-এ শুধু “গাছ নেই”।
- দুটি theorem: Haat-core deterministic (E-Op2-এর v1 আর পরস্পরবিরোধী শর্তের জোরে), আর থামা program-এ ⟶* ও ⇓ একই σ′ দেয়; ৪০০টি এলোমেলো program আর reference-এর সঙ্গে মিলিয়ে অমিল ০।
- Context থেকে machine: evaluation context সব congruence নিয়মকে এক নিয়মে আনে আর evaluation order লিখে রাখে; তাকে stack হিসেবে রাখলে abstract machine (SECD, CEK), যা VM-এর পূর্বসূরি।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৪১ · Denotational semantics — program-এর গাণিতিক অর্থপরবর্তী পর্বএকই Haat-core, এবার function আর fixpoint দিয়ে।
- প্রোগ্রামিং ভাষা ও কম্পাইলার · কোর্স হোম৮৬টি পর্বপুরো কোর্সের মানচিত্র আর Haat প্রজেক্টের পথ।
- পর্ব ২৭ · Control flow — selection, iteration, goto আর structured programmingএই কোর্সেif আর while-এর big-step নিয়মের প্রথম দেখা, আর compiler তাদের কীভাবে লাফে নামায়।
- গণনার অন্য মডেল — lambda calculus, register machine আর cellular automatonপাশের ট্র্যাকযন্ত্রের ধাপ দিয়ে গণনার সংজ্ঞা, আরেক দিক থেকে।
- Program-এর সঠিকতা — loop invariant আর Hoare logic-এর ধারণাপাশের ট্র্যাকপর্ব ৪২-এর axiomatic semantics-এর প্রস্তুতি।
- Mathematical induction — এক ধাপ থেকে অসীম পর্যন্তপাশের ট্র্যাকdeterminism আর সমতুল্যতার প্রমাণের ভিত্তি।