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

Denotational semantics — program-এর গাণিতিক অর্থ

Denotational Semantics — the Mathematical Meaning of Programs

Taught in Bangla, this lesson gives programs a mathematical meaning: the semantic function ⟦e⟧ maps states to values and ⟦S⟧ maps states to states, with runtime errors kept distinct from non-termination (⊥). It explains compositionality, defines while loops as least fixpoints, computes Kleene approximants step by step, states the Kleene and Knaster–Tarski theorems, proves program equivalences, and runs a denotational interpreter and a bounded equivalence checker in in-page Python (Pyodide).

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

  • Semantic function ⟦·⟧ লেখা আর পড়া: Haat-core-এর প্রতিটি expression আর statement-এর সমীকরণ, wrapping, C-ধাঁচের ভাগ, short-circuit আর runtime error-সহ
  • Compositionality কেন গুরুত্বপূর্ণ, আর একটি AST থেকে একবারে function গড়ে নেওয়া interpreter বানানো
  • While loop-এর সমীকরণ, partial function-এর ক্রম, least fixpoint, আর Kleene iteration-এ ধাপে ধাপে তার হিসাব
  • Kleene আর Knaster–Tarski-এর fixpoint theorem পড়া, আর Kleene-এর প্রমাণের রূপরেখা
  • Denotation দিয়ে দুটি program-এর সমতা প্রমাণ করা, আর bounded checker দিয়ে একটি ভুল optimization-এর পাল্টা উদাহরণ খোঁজা

১ · অর্থ মানে একটি গাণিতিক বস্তু — কেন আরেক রকম semantics

বাজারঘরের হিসাবরক্ষক দুই রকমভাবে একটি ছাড়ের নিয়ম বোঝাতে পারেন। প্রথম রকম: “খাতা খুলুন, দাম গুণ করুন, ১০০০ টাকা পার হলে দশ ভাগের এক ভাগ বাদ দিন, তারপর ৬০ যোগ করে লিখুন।” এটি কাজের ধাপ। দ্বিতীয় রকম: একটি দামের তালিকা, যার বাঁ কলামে “কয়টি, প্রতিটি কত”, ডান কলামে “মোট কত”। তালিকা দেখে বোঝা যায় না হিসাব কীভাবে হলো, কিন্তু ঠিক কী হিসাব হয়, তা পুরোপুরি বোঝা যায়। দুটি তালিকা হুবহু এক হলে দুটি নিয়মও একই, যত আলাদাভাবেই লেখা থাকুক।

প্রথম রকমটি operational semantics: পর্ব ৪০-এ (Operational semantics — small-step আর big-step) দেখা যন্ত্রের ধাপ ⟨S, σ⟩ ⟶ ⟨S′, σ′⟩ আর ⟨S, σ⟩ ⇓ σ′. দ্বিতীয় রকমটি এই পর্বের বিষয়, denotational semantics: প্রতিটি program অংশকে একটি গাণিতিক বস্তু দেওয়া, তার “denotation”. Imperative ভাষায় সেই বস্তু সাধারণত একটি function, যা program state নিয়ে নতুন state দেয়। পর্ব ০৭-এ (Imperative আর procedural programming) এর প্রথম রূপ দেখেছেন: ⟦x = e⟧(σ) = σ[x ↦ ⟦e⟧σ]. সেখানে while loop-এর সমীকরণ লিখে একটি প্রশ্ন রেখে আসা হয়েছিল: এর সমাধান আছে কি, আর থাকলে কোনটি? এই পর্বের বড় অংশ সেই প্রশ্নের উত্তর।

চিহ্নটি পড়ার নিয়ম: ⟦ ⟧ (দুই-দাগের বন্ধনী, “semantic bracket”) একটি function, যার ইনপুট program-এর একটি টুকরো (আসলে তার AST), আর আউটপুট গণিতের একটি বস্তু। ভেতরে যা লেখা, তা syntax; বাইরে যা আসে, তা অর্থ। σ (সিগমা) একটি state: নাম থেকে মানের টেবিল, যেমন σ = {qty ↦ 2, unit ↦ 520}. Σ (বড় সিগমা) সব সম্ভাব্য state-এর সেট।

ছবি ৪১.১ — syntax-এর গাছ থেকে অর্থের function

ওপরে p = qty * unit; print(p + 60);-এর AST, নিচে প্রতিটি অংশের denotation. ⟦·⟧ প্রতিটি node-কে একটি function-এ নেয়, আর পুরোটার অর্থ অংশগুলোর অর্থ জুড়ে তৈরি হয়

Syntax tree mapped by the semantic function to state transformers; the meaning of a sequence is the composition f2 after f1 Syntax (AST) seq p = qty * unit; print(p + 60); ⟦·⟧ ⟦·⟧ ⟦·⟧ f₁ = ⟦S₁⟧ Σ → Σ f₂ = ⟦S₂⟧ Σ → Σ ⟦S₁ S₂⟧ = f₂ ∘ f₁ অংশের অর্থ জুড়ে পুরোটার অর্থ

কেন আরেকটি semantics দরকার, যখন operational semantics আছে? তিনটি কারণে। প্রথম, সমতার প্রশ্ন: দুটি program একই কাজ করে কি না, operational দৃষ্টিতে জানতে হলে সব state থেকে দুটির ধাপের ক্রম তুলনা করতে হয়, যদিও ধাপের সংখ্যা আলাদা। Denotational দৃষ্টিতে প্রশ্নটি সরল: দুটি function কি সমান? দ্বিতীয়, যুক্তি দেওয়ার সুবিধা: অর্থ সাধারণ গণিতের বস্তু, তাই function-এর পরিচিত নিয়ম (সমানে সমান বসানো, composition, induction) সরাসরি খাটে। তৃতীয়, নকশার পরীক্ষা: কোনো নতুন feature-এর একটি পরিষ্কার গাণিতিক অর্থ খুঁজে না পেলে প্রায়ই বোঝা যায় নকশায় কিছু গোলমাল আছে।

ইতিহাস। Christopher Strachey ১৯৬০-এর দশকে ভাষার অর্থকে lambda calculus-এর ভাষায় লিখতে চেয়েছিলেন, কিন্তু তখন untyped lambda calculus-এর কোনো গাণিতিক মডেল জানা ছিল না। Dana Scott ১৯৬৯–৭০ সালের দিকে continuous function আর ক্রমের ওপর দাঁড়ানো একটি মডেল খুঁজে পান, যা পরে domain theory নামে পরিচিত হয়। দুজনের যৌথ লেখা “Toward a Mathematical Semantics for Computer Languages” সাধারণত ১৯৭১ সালের বলে উল্লেখ করা হয় (Oxford-এর Programming Research Group-এর একটি monograph). এই কারণে পদ্ধতিটিকে অনেক সময় Scott–Strachey approach বলা হয়।

২ · Haat-core আর expression-এর অর্থ ⟦e⟧σ

পুরো Haat-এর denotation লিখতে function, closure আর call-এর গণিত লাগে; সেটি বড় কাজ। এই মডিউলে তাই Haat-এর একটি ছোট কেন্দ্রীয় অংশ নেওয়া হয়, Haat-core: Int আর Bool-এর expression, var-এ assignment, if, while, statement-এর ক্রম আর print. পর্ব ৪০-এর operational semantics ঠিক এই grammar-এর ওপর, তাই দুটি তুলনা করা যায়; এখানে শুধু unary -e আর !e যোগ করা হলো (পর্ব ৪০-এর অনুশীলন ১-এর মতো)। skip Haat-এ লেখা যায় না, এটি “কিছু না করা”-র সহায়ক চিহ্ন, আর else ছাড়া if মানে else { skip }. শুরুর var ঘোষণাগুলো শুরুর state σ বানায়, আর ধরে নেওয়া হয় program আগেই type check পার হয়েছে (পর্ব ৩৪)।

e ::= n | true | false | x | -e | !e | e ⊕ e | e && e | e || e
      (⊕ হলো + - * / % < <= > >= == != এর যেকোনো একটি)
S ::= x = e; | print(e); | S S | if e { S } else { S }
    | while e { S } | skip

Haat-core-এ expression কোনো state বদলায় না (call নেই, assignment statement), তাই একটি expression-এর অর্থ state থেকে মানে একটি function, যার ফল একটি মান বা runtime error (লেখা হবে err):

⟦e⟧ : Σ → V ∪ {err}    যেখানে V = Int ∪ Bool
সংজ্ঞা ৪১.১ — Haat-core expression-এর semantic function

⟦n⟧σ = n  ·  ⟦true⟧σ = true  ·  ⟦false⟧σ = false  ·  ⟦x⟧σ = σ(x)

⟦e1 + e2⟧σ = wrap(⟦e1⟧σ + ⟦e2⟧σ); - আর * একই রকম, আর ⟦-e⟧σ = wrap(−⟦e⟧σ). wrap মানে ফলকে ৬৪-বিটের পরিসরে ঘুরিয়ে আনা (সিদ্ধান্ত ১৩)।

⟦e1 / e2⟧σ = err যদি ⟦e2⟧σ = 0, নইলে wrap(⟦e1⟧σ ÷ ⟦e2⟧σ, শূন্যের দিকে কেটে); %-এর ফলের চিহ্ন ভাজ্যের মতো (spec-এর C-ধাঁচের নিয়ম)।

⟦e1 && e2⟧σ = false যদি ⟦e1⟧σ = false; ⟦e2⟧σ যদি ⟦e1⟧σ = true. ⟦e1 || e2⟧σ = true যদি ⟦e1⟧σ = true; ⟦e2⟧σ যদি false.

তুলনা (< == …) দুই পাশের মান তুলনা করে true বা false দেয়। সবখানে নিয়ম: কোনো অংশের ফল err হলে পুরোটার ফলও err (শুধু &&/||-এর না-দেখা ডান পাশ বাদে)।

লক্ষ করুন, প্রতিটি সমীকরণের ডান পাশে শুধু সরাসরি অংশগুলোর অর্থ আছে: ⟦e1⟧σ আর ⟦e2⟧σ, অংশগুলোর লেখা বা গঠন নয়। এই গুণের নাম compositionality, আর এটিই denotational semantics-এর মূল নিয়ম। ফল: অর্থের সংজ্ঞা AST-এর ওপর একটি structural recursion, তাই অর্থ সম্পর্কে প্রমাণ চলে structural induction দিয়ে, আর একই অর্থের দুটি expression যেকোনো বড় expression-এর ভেতরে বদলাবদলি করা যায়।

দুটি সূক্ষ্ম বিষয়। প্রথম, short-circuit এখানে সমীকরণেই লেখা: ⟦e1⟧σ = false হলে ⟦e2⟧σ-এর দরকারই নেই, এমনকি সেটি err হলেও। দ্বিতীয়, Haat-এর বাঁ-থেকে-ডানে হিসাবের নিয়ম (সিদ্ধান্ত ১২) এখানে দেখা যায় না। Haat-core-এর expression কোনো side effect ঘটায় না, আর err একটিই রকম, তাই কোন পাশ আগে হিসাব হলো তাতে ফল বদলায় না। Call যোগ হলে আর তা থাকে না: তখন expression-এর অর্থ হতে হয় Σ → V × Σ, কারণ call state বদলাতে পারে, আর ক্রম তখন সমীকরণের অংশ।

নিচের stepper-এ σ = {total ↦ 60, qty ↦ 2}-তে total + qty * 520-এর অর্থ ধাপে ধাপে বের করা হলো। প্রতিটি ধাপে একটি সমীকরণ খাটানো হয়, আর অংশের অর্থ জানা হলে তা ওপরে ফেরত যায়।

1⟦total + qty * 520⟧σ2 = wrap(⟦total⟧σ + ⟦qty * 520⟧σ)3⟦total⟧σ = σ(total)4⟦qty * 520⟧σ5 = wrap(⟦qty⟧σ × ⟦520⟧σ)6⟦qty⟧σ = σ(qty), ⟦520⟧σ = 520
হিসাবের অবস্থা
এখন যে অংশ
সমীকরণ
জানা অর্থ
  1. গঠন দেখে সমীকরণ। বাইরের গঠন e1 + e2, যেখানে e1 = total আর e2 = qty * 520 (গুণের অগ্রাধিকার বেশি, তাই parser এভাবেই গাছ বানায়)।
  2. + এর সমীকরণ। ⟦e1 + e2⟧σ = wrap(⟦e1⟧σ + ⟦e2⟧σ). ডান পাশে শুধু দুই অংশের অর্থ; এখন সেগুলো লাগবে।
  3. প্রথম পাতা। total একটি নাম, তাই ⟦total⟧σ = σ(total) = 60. এখানে আর ভাঙার কিছু নেই।
  4. ভেতরের গঠন। qty * 520-এর জন্য * এর সমীকরণ: wrap(⟦qty⟧σ × ⟦520⟧σ). আবার দুটি অংশের অর্থ চাই।
  5. আরও দুটি পাতা। ⟦qty⟧σ = σ(qty) = 2, আর literal-এর অর্থ নিজেই: ⟦520⟧σ = 520.
  6. ফেরার পথ। 2 × 520 = 1040, যা ৬৪-বিটের পরিসরের অনেক ভেতরে, তাই wrap কিছু বদলায় না: ⟦qty * 520⟧σ = 1040.
  7. পুরো অর্থ। 60 + 1040 = 1100. পরের Python block ঠিক এই সংখ্যাই ছাপে। প্রতিটি ধাপে শুধু সরাসরি অংশের অর্থ লেগেছে: এটাই compositionality.

নিচের block সংজ্ঞা ৪১.১-কে সরাসরি Python-এ লেখে। একটি পার্থক্য খেয়াল করুন: E(e) সাথে সাথে কোনো মান দেয় না, একটি function ফেরত দেয়, যা পরে যেকোনো σ-তে খাটানো যায়। ⟦e⟧ আসলেই একটি function, আর Python-এর closure দিয়ে তা হুবহু লেখা যায় (পর্ব ১৭)। পূর্ণ Haat-এর অনুরূপ হিসাব reference-এর runtime.py (wrap, ভাগ) আর interp.py-তে।

# Haat-core expression-এর denotation: E(e) একটি Python function ফেরত দেয়, σ → মান
# AST: 520, True, "qty", (op, a, b), ("neg", a), ("!", a)   (op: + - * / % < … && ||)
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
class Err(Exception): pass                                 # runtime error
AR = {"+": lambda a, b: a + b, "-": lambda a, b: a - b, "*": lambda a, b: a * b,
      "/": cdiv, "%": lambda a, b: a - b * cdiv(a, b)}
CMP = {"<": lambda a, b: a < b, "<=": lambda a, b: a <= b, ">": lambda a, b: a > b,
       ">=": lambda a, b: a >= b, "==": lambda a, b: a == b, "!=": lambda a, b: a != b}
def E(e):                         # ⟦e⟧ : Σ → V, শুধু অংশের ⟦·⟧ থেকে গড়া
    if isinstance(e, (bool, int)): return lambda s: e
    if isinstance(e, str): return lambda s: s[e]
    if e[0] == "neg": f = E(e[1]); return lambda s: wrap(-f(s))
    if e[0] == "!": f = E(e[1]); return lambda s: not f(s)
    op, f, g = e[0], E(e[1]), E(e[2])
    if op == "&&": return lambda s: g(s) if f(s) else False   # short-circuit
    if op == "||": return lambda s: True if f(s) else g(s)
    if op in CMP: return lambda s: CMP[op](f(s), g(s))
    def arith(s):
        a, b = f(s), g(s)                                  # বাঁ দিক আগে
        if op in ("/", "%") and b == 0: raise Err("division by zero")
        return wrap(AR[op](a, b))
    return arith
def show(v): return str(v).lower()
s = {"total": 60, "qty": 2, "a": 10, "b": 0}
d = E(("+", "total", ("*", "qty", 520)))   # একবার গড়া অর্থ, তারপর যেকোনো σ-তে
print("⟦total + qty * 520⟧σ =", d(s), "  σ′-তে:", d({**s, "qty": 3}))
safe = E(("&&", ("!=", "b", 0), (">", ("/", "a", "b"), 2)))
print("⟦b != 0 && a / b > 2⟧σ =", show(safe(s)))
try: E(("&&", (">", ("/", "a", "b"), 2), ("!=", "b", 0)))(s)
except Err as x: print("⟦a / b > 2 && b != 0⟧σ → runtime error:", x)
big = {"x": 2**63 - 1}
print("⟦x + 1⟧ (x = INT_MAX) =", E(("+", "x", 1))(big))
print("⟦-7 / 2⟧ =", E(("/", ("neg", 7), 2))({}), "  ⟦-7 % 2⟧ =", E(("%", ("neg", 7), 2))({}))

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

⟦total + qty * 520⟧σ = 1100   σ′-তে: 1620
⟦b != 0 && a / b > 2⟧σ = false
⟦a / b > 2 && b != 0⟧σ → runtime error: division by zero
⟦x + 1⟧ (x = INT_MAX) = -9223372036854775808
⟦-7 / 2⟧ = -3   ⟦-7 % 2⟧ = -1

প্রথম লাইনে stepper-এর 1100. একই function d qty = 3-এর state-এ দেয় 1620: অর্থ একবার গড়া হয়েছে, state বদলালে শুধু প্রয়োগ বদলায়। দ্বিতীয় আর তৃতীয় লাইন একই দুটি শর্ত, শুধু ক্রম উল্টো: b = 0 হলে প্রথমটির অর্থ false, কারণ &&-এর সমীকরণ ডান পাশ দেখে না; দ্বিতীয়টির অর্থ err (block-এ Python exception হিসেবে দেখা যায়)। চতুর্থ লাইনে INT_MAX + 1 ঘুরে সবচেয়ে ছোট Int, আর শেষ লাইনে -7 / 2 = -3, -7 % 2 = -1, C-র মতো। লক্ষ করুন, এই block-এ কোনো eval নেই: প্রতিটি operator-এর অর্থ হাতে লেখা।

৩ · Statement-এর অর্থ — state থেকে state, সঙ্গে error আর ⊥

একটি statement কোনো মান দেয় না, state বদলায়। তাই তার অর্থ একটি state transformer: σ নিয়ে নতুন σ′ দেয়। কিন্তু সব statement-এর ফল একটি সাধারণ state নয়। একটি statement শূন্য দিয়ে ভাগে থেমে যেতে পারে, আর একটি loop কখনো না-ও থামতে পারে। তাই ফল তিন রকম:

  • σ′: স্বাভাবিকভাবে শেষ, নতুন state.
  • err σ′: runtime error-এ থামা (পর্ব ৪০-এর error configuration-এর denotational রূপ)। σ′-এ থাকে থামার মুহূর্ত পর্যন্ত সব, বিশেষ করে ছাপা আউটপুট, কারণ Haat-এ error-এর আগের আউটপুট থেকে যায় (সিদ্ধান্ত ২৬)।
  • ⊥ (“বটম”): কোনো ফল নেই, program চিরকাল চলে। ⊥ একটি মান নয়, “এখানে কোনো উত্তর নেই”-এর চিহ্ন।

print-এর জন্য state-এ একটি বিশেষ ঘর রাখা হয়, σ.out: এ পর্যন্ত ছাপা লাইনের তালিকা। তাহলে print-ও একটি সাধারণ state পরিবর্তন। শেষে program-এর দৃশ্যমান আচরণ হলো ফলের out-তালিকা, সঙ্গে err আছে কি না, বা ফল ⊥ কি না।

সংজ্ঞা ৪১.২ — Haat-core statement-এর semantic function, ⟦S⟧ : Σ → (Σ ∪ err Σ)⊥

⟦x = e;⟧σ = σ[x ↦ ⟦e⟧σ], আর ⟦e⟧σ = err হলে err σ.   ⟦skip⟧σ = σ

⟦print(e);⟧σ = σ[out ↦ σ.out · show(⟦e⟧σ)], আর ⟦e⟧σ = err হলে err σ. (· মানে তালিকার শেষে জোড়া)

⟦if e { S1 } else { S2 }⟧σ = ⟦S1⟧σ যদি ⟦e⟧σ = true; ⟦S2⟧σ যদি false; err σ যদি err.

⟦S1 S2⟧σ = ⟦S2⟧†(⟦S1⟧σ), যেখানে যেকোনো f-এর জন্য f†(σ′) = f(σ′), f†(err σ′) = err σ′, f†(⊥) = ⊥.

শেষ নিয়মের f† (“f dagger”) হলো f-এর strict extension: আগের অংশ error-এ থামলে বা চিরকাল চললে পরের অংশ আর চলে না, ফল যেমন ছিল তেমন যায়। এটি না থাকলে ⟦S1 S2⟧ সরল composition ⟦S2⟧ ∘ ⟦S1⟧ হতো, ছবি ৪১.১-এর মতো; error আর ⊥-কে জায়গা দিতেই এই ছোট সংশোধন। বাস্তব ভাষায় এটি পরিচিত: exception-এর পরের লাইন চলে না, আর অসীম loop-এর পরের লাইনে কখনো পৌঁছানো যায় না।

নিচের block-এ সংজ্ঞা ৪১.২. C(S)-ও একটি function ফেরত দেয়। ⊥ লেখা হয়েছে None দিয়ে, আর err σ লেখা হয়েছে state-এ একটি বাড়তি "err" ঘর দিয়ে, যাতে আউটপুট হারায় না। while-এর লাইনটি পরের block-এ পূর্ণ হবে।

# Command-এর denotation: C(S) একটি function, σ → σ′ (error হলে "err", ⊥ হলে None)
def guard(h):                     # error হলে ফল: σ-তে "err" চিহ্ন (আগের out থাকে)
    def run(s):
        try: return h(s)
        except Err as x: return {**s, "err": str(x)}
    return run
def lift(r, k): return r if r is None or "err" in r else k(r)   # k†: ⊥ আর err পার হয়
def C(S):                         # ⟦S⟧ : Σ → Σ⊥ ; None = ⊥
    if S == "skip": return lambda s: s
    if S[0] == "=": x, f = S[1], E(S[2]); return guard(lambda s: {**s, x: f(s)})
    if S[0] == "print":
        f = E(S[1]); return guard(lambda s: {**s, "out": s["out"] + (show(f(s)),)})
    if S[0] == "seq": c1, c2 = C(S[1]), C(S[2]); return lambda s: lift(c1(s), c2)
    if S[0] == "if":
        b, c1, c2 = E(S[1]), C(S[2]), C(S[3]); return guard(lambda s: c1(s) if b(s) else c2(s))
    return WHILE(E(S[1]), C(S[2]))                     # while: পরের block-এ
def seq(*ss): return ss[0] if len(ss) == 1 else ("seq", ss[0], seq(*ss[1:]))
order = seq(("=", "p", ("*", "qty", "unit")),
            ("if", (">=", "p", 1000), ("=", "p", ("-", "p", ("/", "p", 10))), "skip"),
            ("print", ("+", "p", 60)))
run = C(order)                                # ⟦order⟧: একটিই function
for q in (2, 1, 0):
    r = run({"qty": q, "unit": 520, "p": 0, "out": ()})
    print(f"qty = {q}: p = {r['p']}, out = {list(r['out'])}")
share = seq(("print", "total"), ("=", "each", ("/", "total", "people")), ("print", "each"))
print(C(share)({"total": 996, "people": 0, "each": 0, "out": ()}))

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

qty = 2: p = 936, out = ['996']
qty = 1: p = 520, out = ['580']
qty = 0: p = 0, out = ['60']
{'total': 996, 'people': 0, 'each': 0, 'out': ('996',), 'err': 'division by zero'}

run একটিই function, ⟦order⟧. qty = 2-তে p = 1040 থেকে ছাড় দিয়ে 936, ছাপা হয় 936 + 60 = 996, bazar.haat-এর প্রথম লাইন। qty = 1 আর 0-তে ছাড় নেই। শেষ লাইনে share প্রথমে 996 ছাপে, তারপর ভাগে আটকে যায়: ফলের state-এ 'out': ('996',) আর 'err' দুটিই আছে, আর তৃতীয় statement চলেনি, কারণ f† error-কে পার করে দেয়। লেখকের lab-এ একই program-গুলো Haat source-এ লিখে reference-এর haat.py run-এ চালানো হয়েছে (সত্যিকারের run, CPython 3.14.4): আউটপুট হুবহু এক, আর শেষটিতে reference বলে 5:14: runtime error: division by zero, আগে 996 ছেপে।

৪ · While-এর সমস্যা — নিজের দিকে ফিরে আসা সমীকরণ

এ পর্যন্ত প্রতিটি সমীকরণের ডান পাশে ছিল শুধু ছোট অংশের অর্থ, তাই সংজ্ঞা নিশ্চিতভাবে শেষ হয়। While loop-এ তা হয় না। একটি loop একবার ঘোরার পরে আবার একই loop:

W = ⟦while e { S }⟧,   W(σ) = W†(⟦S⟧σ) যদি ⟦e⟧σ = true; σ যদি false; err σ যদি err

W ডান পাশেও আছে। এটি সংজ্ঞা নয়, একটি সমীকরণ, যার অজানা হলো একটি function. পর্ব ০৭-এ ঠিক এখানেই থেমেছিলাম। সমীকরণটিকে একটি ফাংশনের ভাষায় লেখা সুবিধাজনক। ধরি

F(w) = λσ. w†(⟦S⟧σ) যদি ⟦e⟧σ = true; σ যদি false; err σ যদি err

F-কে বলে loop-এর functional: একটি “loop-এর বাকি অংশের অনুমিত অর্থ” w নিয়ে একবার ঘোরার পরের অর্থ দেয়। (λσ. … মানে “σ নিয়ে … ফেরত দেওয়া function”, lambda calculus-এর লেখা।) তাহলে সমীকরণটি দাঁড়ায় W = F(W): W হলো F-এর একটি fixpoint.

সমাধান অনেক থাকতে পারে

সবচেয়ে ছোট উদাহরণ while true { }. এখানে ⟦e⟧σ সবসময় true, আর ফাঁকা দেহ মানে skip, যার ⟦skip⟧σ = σ; তাই F(w) = λσ. w(σ) = w. প্রতিটি w-ই সমাধান! “সব state-এ ৫০০০ ফেরত দেয়” এমন function-ও, “যেমন ছিল তেমন রাখে” এমন function-ও। অথচ যন্ত্রে চালালে এই loop কখনো শেষ হয় না, কোনো ফলই দেয় না। সঠিক অর্থ তাই ⊥ সবখানে, যা F-এর একটি fixpoint ঠিকই, তবে বিশেষ একটি: যেটি সবচেয়ে কম দাবি করে।

আরেকটি উদাহরণ: while total != 4500 { total = total + 1000; }, শুরুতে total = 0. মান যায় 1000, 2000, …; ৬৪-বিট wrap হয়ে ঘুরে এলেও কখনো 4500 হয় না, কারণ 1000k ≡ 4500 (mod 264)-এর কোনো সমাধান নেই: 264 আর 1000-এর গসাগু 8, আর 4500 আটের গুণিতক নয়। তাই এই state-এ সঠিক অর্থ ⊥. অথচ সমীকরণে “total = 0-তে ফল total ↦ 4500” বসালেও সমীকরণ মিলে যায়, কারণ ডান পাশ শুধু বলে “এখানের ফল = এক ঘোরার পরের state-এর ফল”, আর সব state-এ একই মিথ্যা দাবি করলে দুই পাশ সমান থাকে।

মূল কথা। “সমীকরণের কোনো একটি সমাধান” বললে loop-এর অর্থ ঠিক হয় না। এমন সমাধান বাছতে হবে যা কোনো ফল দাবি করে না, যদি না সেই ফল একটি সসীম সংখ্যক ঘোরার পরে সত্যিই আসে। এর জন্য লাগে “কম দাবি” আর “বেশি দাবি”-র একটি ক্রম, আর সেই ক্রমে সবচেয়ে নিচের fixpoint: least fixpoint.

৫ · Kleene iteration — ⊥ থেকে ধাপে ধাপে least fixpoint

তথ্যের ক্রম

একটি statement-এর অর্থকে একটি partial function হিসেবে দেখুন: যে state-এ program থামে (স্বাভাবিকভাবে বা err-এ), সেখানে একটি ফল আছে; যেখানে চিরকাল চলে, সেখানে ফল নেই (⊥)। দুটি partial function f আর g-এর জন্য লিখি

f ⊑ g  মানে  f যেখানে সংজ্ঞায়িত, g-ও সেখানে সংজ্ঞায়িত, আর একই মান দেয়

পড়ুন “f-এর তথ্য g-তে আছে” বা “g, f-এর চেয়ে বেশি জানে”। এটি একটি partial order: সব জোড়া তুলনীয় নয় (একটি state-এ দুটি আলাদা ফল দেয় এমন f আর g-এর কোনোটিই অপরটির ওপরে নয়)। সবচেয়ে নিচে আছে কোথাও সংজ্ঞায়িত নয় এমন function, যাকেও ⊥ লেখা হয়। Partial order, lub আর lattice-এর মৌলিক কথা Discrete Mathematics-এর পর্ব ৫৬-এ (Partial order আর lattice) আছে; এখানে শুধু এই ক্রমটি লাগবে।

Kleene iteration

এবার F-কে বারবার ⊥-এর ওপর খাটাই: f0 = ⊥, f1 = F(f0), f2 = F(f1), …. fk-এর অর্থ সহজ: যে state থেকে loop k-এর কম বার ঘুরে থামে, সেখানে fk সঠিক ফল দেয়; বাকি state-এ ⊥. প্রতিটি ধাপ আগের তথ্য রাখে আর একটু যোগ করে, তাই f0 ⊑ f1 ⊑ f2 ⊑ …, একটি শিকল (chain). শিকলের সবচেয়ে ছোট ঊর্ধ্বসীমা (least upper bound, lub, লেখা হয় ⊔) হলো সব fk-এর তথ্য একসঙ্গে, আর সেটিই loop-এর অর্থ। এই পদ্ধতির নাম Kleene iteration.

bazar.haat-এর loop while total < 5000 { total = total + 1250; rounds = rounds + 1; } নিন, rounds = 0 আর পাঁচটি আলাদা শুরুর total নিয়ে। নিচের stepper প্রতিটি fk-এর ফল দেখায়, “total/rounds” আকারে; সংখ্যাগুলো পরের Python block-এর আউটপুট থেকে নেওয়া।

1f₀ = ⊥2f₁ = F(f₀)3f₂ = F(f₁)4f₃ = F(f₂)5f₄ = F(f₃)6f₅ = F(f₄)7f₆ = F(f₅)
শুরুর total → ফল (total/rounds)
0
1250
2500
3750
5000
  1. শূন্য তথ্য। f0 = ⊥: কোনো state-এ কোনো ফল দাবি করা হয় না। এটি নিশ্চিতভাবে ভুল কিছু বলে না, শুধু কিছুই বলে না।
  2. এক ধাপ। f1 = F(⊥). শর্ত মিথ্যা হলে F ফল দেয় σ নিজে, তাই total = 5000-এ ফল 5000/0. শর্ত সত্য হলে F চায় ⊥-এর মান, তাই বাকি সব ⊥. অর্থাৎ শূন্য ঘোরায় শেষ হওয়া state-গুলো জানা গেল।
  3. দুই ধাপ। f2 = F(f1). 3750 থেকে এক ঘোরায় যাওয়া হয় 5000/1-এ, যেখানে f1 ফল জানে। এখন এক ঘোরায় শেষ হওয়া state-ও জানা। আগের তথ্য (5000-এ 5000/0) বদলায়নি, শুধু যোগ হয়েছে: f1 ⊑ f2.
  4. তিন ধাপ। 2500 থেকে দুই ঘোরা লাগে, f3-এ জানা গেল 5000/2. নিয়ম: fk জানে k-এর কম ঘোরায় শেষ হওয়া প্রতিটি state.
  5. চার ধাপ। 1250 থেকে তিন ঘোরা, f4-এ 5000/3. কেবল total = 0 এখনো ⊥, কারণ সেখানে চারবার ঘুরতে হয়।
  6. পাঁচ ধাপ। f5-এ total = 0 থেকে 5000/4. bazar.haat ঠিক এই state থেকে শুরু করে, আর ছাপে total = 5000 আর rounds − 1 = 3.
  7. আর বদলায় না। f6 = f5 এই পাঁচটি state-এ। সাবধান: শুধু কয়েকটি state-এ দুটি পরপর approximant মিললেই fixpoint নিশ্চিত হয় না (অনুশীলন ৩ দেখুন)। পুরো অর্থ হলো সব fk-এর lub, অসীম শিকলের সীমা।
# while-এর denotation: functional F-এর least fixpoint, Kleene iteration দিয়ে
def F(b, c):                    # F(w) = λσ. ⟦b⟧σ হলে w†(⟦S⟧σ), নইলে σ
    def step(w):
        def nxt(s):
            try: cond = b(s)
            except Err as x: return {**s, "err": str(x)}
            return lift(c(s), w) if cond else s
        return nxt
    return step
def approx(b, c, k):            # f_k = F^k(⊥), যেখানে ⊥ = কোথাও সংজ্ঞায়িত নয়
    f = lambda s: None
    for _ in range(k): f = F(b, c)(f)
    return f
def WHILE(b, c, limit=300):     # ⟦while⟧σ = ⊔ f_k(σ): যে প্রথম k-তে সংজ্ঞায়িত
    def run(s):
        for k in range(limit + 1):
            r = approx(b, c, k)(s)
            if r is not None: return r
        return None             # limit পর্যন্ত ⊥ (প্রমাণ নয়, শুধু পর্যবেক্ষণ)
    return run
cond = ("<", "total", 5000)
body = seq(("=", "total", ("+", "total", 1250)), ("=", "rounds", ("+", "rounds", 1)))
starts = [0, 1250, 2500, 3750, 5000]
for k in range(7):
    f = approx(E(cond), C(body), k)
    row = [f({"total": t, "rounds": 0, "out": ()}) for t in starts]
    cells = ["⊥" if r is None else f"{r['total']}/{r['rounds']}" for r in row]
    print(f"f{k}:", " ".join(f"{c:>9}" for c in cells), f"  সংজ্ঞায়িত {5 - row.count(None)}টি")
core = seq(("while", cond, body), ("print", "total"), ("print", ("-", "rounds", 1)))
print("bazar-এর শেষ অংশ:", list(C(core)({"total": 0, "rounds": 0, "out": ()})["out"]))
stuck = C(("while", ("!=", "total", 4500), ("=", "total", ("+", "total", 1000))))
print("total != 4500, +1000:", stuck({"total": 0, "out": ()}))
from math import gcd               # 1000k ≡ 4500 (mod 2^64)-এর সমাধান আছে কি?
print("4500 % gcd(1000, 2^64) =", 4500 % gcd(1000, 2**64))

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

f0:         ⊥         ⊥         ⊥         ⊥         ⊥   সংজ্ঞায়িত 0টি
f1:         ⊥         ⊥         ⊥         ⊥    5000/0   সংজ্ঞায়িত 1টি
f2:         ⊥         ⊥         ⊥    5000/1    5000/0   সংজ্ঞায়িত 2টি
f3:         ⊥         ⊥    5000/2    5000/1    5000/0   সংজ্ঞায়িত 3টি
f4:         ⊥    5000/3    5000/2    5000/1    5000/0   সংজ্ঞায়িত 4টি
f5:    5000/4    5000/3    5000/2    5000/1    5000/0   সংজ্ঞায়িত 5টি
f6:    5000/4    5000/3    5000/2    5000/1    5000/0   সংজ্ঞায়িত 5টি
bazar-এর শেষ অংশ: ['5000', '3']
total != 4500, +1000: None
4500 % gcd(1000, 2^64) = 4

টেবিলটি stepper-এর সঙ্গে হুবহু এক: প্রতিটি ধাপে ঠিক একটি নতুন state সংজ্ঞায়িত হয়, আর আগের কোনো ফল বদলায় না। WHILE একটি state-এর জন্য প্রথম যে k-তে fk সংজ্ঞায়িত, সেটির ফল নেয়; ⊔-এর এটিই হিসাবযোগ্য রূপ, কারণ শিকলের প্রতিটি function আগেরটির ফল রাখে। এভাবে bazar.haat-এর শেষ অংশ ছাপে 5000 আর 3, reference-এর মতোই। total != 4500-এর loop ৩০০টি approximant পর্যন্ত ⊥ (None). এটি নিজে প্রমাণ নয়, ৩০১তম ধাপেও কিছু আসতে পারত; প্রমাণ শেষ লাইনের গাণিতিক যুক্তি: ভাগশেষ 4, শূন্য নয়, তাই কোনো k নেই।

Fixpoint theorem দুটি

Theorem ৪১.১ — Kleene-এর fixpoint theorem

ধরুন (D, ⊑) একটি complete partial order (cpo), যার সবচেয়ে নিচে ⊥, আর F : D → D একটি continuous function (প্রতিটি শিকলের lub রক্ষা করে: F(⊔ xn) = ⊔ F(xn)). তাহলে fix F = ⊔n Fn(⊥) হলো F-এর একটি fixpoint, আর F-এর সব fixpoint-এর মধ্যে সবচেয়ে নিচেরটি।

প্রমাণের রূপরেখা।

  1. শিকল: ⊥ ⊑ F(⊥), কারণ ⊥ সবার নিচে। continuous function monotone-ও, তাই x ⊑ y থেকে F(x) ⊑ F(y); n-এর ওপর induction-এ Fn(⊥) ⊑ Fn+1(⊥). cpo বলে শিকলের lub আছে; লিখি d = ⊔n Fn(⊥).
  2. Fixpoint: continuity দিয়ে F(d) = ⊔n Fn+1(⊥). এটি একই শিকল, শুধু প্রথম উপাদান ⊥ বাদ; ⊥ বাদ দিলে lub বদলায় না, তাই F(d) = d.
  3. সবচেয়ে নিচে: ধরুন F(x) = x যেকোনো fixpoint. ⊥ ⊑ x; আর Fn(⊥) ⊑ x হলে monotone বলে Fn+1(⊥) ⊑ F(x) = x. তাই x শিকলের একটি ঊর্ধ্বসীমা, আর d সবচেয়ে ছোট ঊর্ধ্বসীমা বলে d ⊑ x. ∎

Loop-এর বেলায় শর্তগুলো মেলে। State থেকে ফলের partial function-এর সেট ⊑ নিয়ে একটি cpo: শিকলের lub হলো সব function-এর টেবিল একসঙ্গে জোড়া, যা সম্ভব কারণ শিকলে কেউ কারো ফল বদলায় না। F continuous, কারণ F(w)(σ) হিসাবে w-কে শুধু একটি state-এ (⟦S⟧σ-তে) দেখতে হয়; সেই এক জায়গার মান শিকলের কোনো সসীম ধাপেই জানা হয়ে যায়। তাই Kleene-এর theorem বলে, ⟦while e { S }⟧ = fix F ঠিকঠাক সংজ্ঞায়িত, আর এটিই least fixpoint. while true { }-এ F(w) = w, তাই Fn(⊥) = ⊥ সবসময়, আর fix F = ⊥: চিরকাল চলা, যেমন হওয়া উচিত।

আরেকটি বিখ্যাত ফল প্রায়ই একসঙ্গে বলা হয়, Knaster–Tarski theorem: একটি complete lattice-এ (যেখানে যেকোনো উপসেটের lub আর glb আছে) প্রতিটি monotone function-এর fixpoint আছে, আর least fixpoint = ⊓{x | F(x) ⊑ x}. সেট-গণিতের একটি বিশেষ রূপ Knaster আর Tarski-র ১৯২৮ সালের কাজে, আর সাধারণ lattice-এর রূপটি Tarski-র ১৯৫৫ সালের লেখায় প্রকাশিত বলে সাধারণত উল্লেখ করা হয়; “Kleene fixpoint theorem” নামটি পরে প্রচলিত, আর order-theory-র এই রূপটির সঠিক উৎস নিয়ে লেখকভেদে মতভেদ আছে। দুটির পার্থক্য কাজে লাগে: partial function-এর সেট complete lattice নয় (একই state-এ 5000 আর 6000 দেয় এমন দুটি function-এর কোনো সাধারণ ঊর্ধ্বসীমা নেই), কিন্তু cpo. তাই denotational semantics সাধারণত Kleene-এর পথ নেয়, আর বোনাস হিসেবে পায় একটি হিসাবের পদ্ধতি: ⊥ থেকে শুরু করে F খাটাতে থাকা।

৬ · Denotation দিয়ে program-এর সমতা প্রমাণ

দুটি statement S আর T-এর অর্থ সমান, ⟦S⟧ = ⟦T⟧, মানে প্রতিটি σ-তে দুটির ফল এক: একই state, একই আউটপুট, একই err বা একই ⊥. Compositionality থেকে আসে বড় সুবিধা: তাহলে যেকোনো program-এ S-এর জায়গায় T বসালে পুরো program-এর অর্থও বদলায় না, কারণ পুরোটার অর্থ শুধু অংশগুলোর অর্থ থেকে আসে। একে বলে program equivalence, আর compiler-এর প্রতিটি optimization (পর্ব ৬৫) আসলে এমন একটি দাবি: “এই টুকরোর বদলে ওই টুকরো বসালে অর্থ একই থাকে”।

একটি ক্লাসিক উদাহরণ, loop unrolling-এর ভিত্তি: while e { S }-এর অর্থ if e { S while e { S } } else { skip }-এর অর্থের সমান। পর্ব ৪০-এর অনুশীলনে একই সমতা big-step নিয়মে inversion দিয়ে প্রমাণ হয়েছিল; এখানে প্রমাণ শুধু সমীকরণে, ধাপে ধাপে:

1⟦if e { S W } else { skip }⟧σ2 = ⟦S W⟧σ  বা ⟦skip⟧σ3 = W†(⟦S⟧σ)  বা σ4 = F(W)(σ)5 = W(σ)6⟦if …⟧ = ⟦while e { S }⟧ ∎
প্রমাণের অবস্থা
খাটানো নিয়ম
⟦e⟧σ = err হলে
  1. লক্ষ্য। W = ⟦while e { S }⟧ = fix F. দেখাতে হবে প্রতিটি σ-তে ⟦if e { S W } else { skip }⟧σ = W(σ). (এখানে S W মানে “S, তারপর একই while”.)
  2. if-এর সমীকরণ। ⟦e⟧σ = true হলে ফল ⟦S W⟧σ, false হলে ⟦skip⟧σ, আর err হলে err σ. Error-এর case দুই পাশে একই, তাই শেষ পর্যন্ত মিলে যাবে।
  3. Seq আর skip. ⟦S W⟧σ = W†(⟦S⟧σ), আর ⟦skip⟧σ = σ. কোনো অনুমান লাগেনি, শুধু সংজ্ঞা ৪১.২.
  4. F চিনে নেওয়া। “true হলে W†(⟦S⟧σ), false হলে σ, err হলে err σ” হুবহু F(W)(σ)-এর সংজ্ঞা, অংশ ৪-এর functional.
  5. Fixpoint-এর গুণ। W = fix F, আর Kleene-এর theorem বলে fix F একটি fixpoint: F(W) = W. তাই F(W)(σ) = W(σ). এখানে “least” লাগেনি, শুধু “fixpoint”.
  6. সিদ্ধান্ত। প্রতিটি σ-তে দুই পাশ সমান, তাই denotation সমান। Compositionality-র কারণে যেকোনো Haat-core program-এ একটি while-এর বদলে তার এক ধাপ খোলা রূপ বসানো নিরাপদ। ∎

প্রমাণ সব সময় সহজ নয়, আর প্রস্তাবিত সমতা অনেক সময় মিথ্যা। মিথ্যা হলে একটি state-ই যথেষ্ট, যেখানে দুটি অর্থ আলাদা। নিচের block দুটি program-এর denotation সব ছোট state-এ মিলিয়ে দেখে (x, y প্রতিটি −3 থেকে 3, বা wrap-এর সীমার মান)। এটি bounded check: “আলাদা” উত্তর একটি নিশ্চিত পাল্টা উদাহরণ, কিন্তু “সমান” উত্তর শুধু পরীক্ষিত state-গুলোর জন্য, প্রমাণ নয়।

# দুটি program-এর denotation সব ছোট state-এ মিলিয়ে দেখা (bounded equivalence check)
from itertools import product
EDGE = [-2**63, -1, 0, 1, 2**63 - 1]            # wrap-এর সীমাসহ
SMALL = range(-3, 4)                            # loop থাকলে ছোট মান
def fmt(r):
    if r is None: return "⊥"
    return f"x={r['x']} y={r['y']} out={list(r['out'])}" + (" err" if "err" in r else "")
def same(p, q, vals):
    cp, cq = C(p), C(q)
    states = [{"x": x, "y": y, "out": ()} for x, y in product(vals, repeat=2)]
    for s in states:
        a, b = cp(s), cq(s)
        if a != b: return f"আলাদা! x={s['x']} y={s['y']}: {fmt(a)} ∣ {fmt(b)}"
    return f"সমান, {len(states)}টি state-এ"
loop = ("while", (">", "x", 0), ("=", "x", ("-", "x", 1)))
pairs = {
  "while ≡ if + while": (loop, ("if", (">", "x", 0), seq(("=", "x", ("-", "x", 1)), loop), "skip"), SMALL),
  "while ≡ if x > 0 { x = 0; }": (loop, ("if", (">", "x", 0), ("=", "x", 0), "skip"), SMALL),
  "x = x + 1; x = x - 1; ≡ skip": (seq(("=", "x", ("+", "x", 1)), ("=", "x", ("-", "x", 1))), "skip", EDGE),
  "y = 1 / x; y = 0; ≡ y = 0;": (seq(("=", "y", ("/", 1, "x")), ("=", "y", 0)), ("=", "y", 0), SMALL),
  "&& অদলবদল": (("if", ("&&", ("!=", "x", 0), (">", ("/", 10, "x"), 2)), ("=", "y", 1), ("=", "y", 0)),
                ("if", ("&&", (">", ("/", 10, "x"), 2), ("!=", "x", 0)), ("=", "y", 1), ("=", "y", 0)), SMALL),
  "print আর assign অদলবদল": (seq(("print", "x"), ("=", "x", 0)), seq(("=", "x", 0), ("print", "x")), SMALL),
}
for name, (p, q, vals) in pairs.items(): print(f"{name:<30} → {same(p, q, vals)}")

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

while ≡ if + while             → সমান, 49টি state-এ
while ≡ if x > 0 { x = 0; }    → সমান, 49টি state-এ
x = x + 1; x = x - 1; ≡ skip   → সমান, 25টি state-এ
y = 1 / x; y = 0; ≡ y = 0;     → আলাদা! x=0 y=-3: x=0 y=-3 out=[] err ∣ x=0 y=0 out=[]
&& অদলবদল                      → আলাদা! x=0 y=-3: x=0 y=0 out=[] ∣ x=0 y=-3 out=[] err
print আর assign অদলবদল         → আলাদা! x=-3 y=-3: x=0 y=-3 out=['-3'] ∣ x=0 y=-3 out=['0']

প্রথম তিনটি সমতা পরীক্ষায় টিকে গেল। প্রথমটি stepper-এ প্রমাণ করা হয়েছে। দ্বিতীয়টি (loop-এর বদলে একটি সরাসরি assignment) সব Int-এর জন্য সত্য, কারণ x > 0 হলে loop ঠিক x বার ঘুরে 0-তে থামে; এমন রূপান্তর optimizer-এর loop-বিষয়ক কাজের বিষয় (পর্ব ৬৬)। তৃতীয়টি INT_MAX-এও টেকে, কারণ Haat-এ যোগ wrap করে আর বিয়োগ তা ফিরিয়ে আনে; Rust-এর debug build-এ বা C-তে (signed overflow undefined behavior) এই যুক্তি একই রকম খাটে না। শেষ তিনটি মিথ্যা, প্রতিটির জন্য একটি state: y = 1 / x; y = 0; x = 0-তে err দেয়, তাই “অদরকারি assignment মুছে ফেলা” Haat-এ ভুল optimization; &&-এর দুই পাশ অদলবদল x = 0-তে error আনে; আর print আর assignment-এর ক্রম বদলালে আউটপুট বদলায়। লেখকের lab-এ এই উদাহরণগুলো reference-এর haat.py run-এ চালিয়ে মেলানো হয়েছে: x = 0-তে 3:7: runtime error: division by zero আর 2:7: runtime error: division by zero, ঠিক denotation-এর err-এর জায়গায়।

৭ · Operational আর denotational — একই অর্থের দুই ভাষা

একই Haat-core-এর জন্য এখন দুটি সংজ্ঞা আছে: পর্ব ৪০-এর ধাপভিত্তিক ⇓, আর এই পর্বের ⟦·⟧. দুটি যদি আলাদা কথা বলে, তাহলে অন্তত একটি ভুল। তাদের মিলের দাবিটির নাম adequacy:

Theorem ৪১.২ — Haat-core-এর adequacy

প্রতিটি Haat-core statement S আর state σ-এর জন্য: ⟦S⟧σ = σ′ ঠিক তখনই, যখন ⟨S, σ⟩ ⇓ σ′; ⟦S⟧σ = err σ′ ঠিক তখনই, যখন big-step হিসাব σ′-এ error দিয়ে থামে; আর ⟦S⟧σ = ⊥ ঠিক তখনই, যখন কোনো big-step derivation নেই (small-step-এ ধাপ চিরকাল চলে)।

প্রমাণের রূপরেখা। (১) ⇓ থেকে ⟦·⟧: big-step derivation-এর ওপর induction. প্রতিটি নিয়ম একটি সমীকরণের সঙ্গে মেলে; while-এর নিয়মের জন্য অংশ ৬-এর unfolding সমতা কাজে লাগে। (২) ⟦·⟧ থেকে ⇓: S-এর গঠনের ওপর induction, আর while-এর ভেতরে k-এর ওপর আরেকটি induction: fk(σ) = σ′ হলে k-এর কম ঘোরার একটি derivation গড়া যায়। (৩) ⊥-এর দাবি প্রথম দুটি থেকে আসে, কারণ দুই দিকেই “ফল আছে” মিলে গেছে। ∎ লেখকের lab-এ এর একটি ছোট পরীক্ষাও হয়েছে: এই পর্বের denotational interpreter আর reference-এর tree-walking interpreter (সত্যিকারের run, CPython 3.14.4) ২০টি Haat-core program-এ একই আউটপুট দিয়েছে, ৩টি error-এর ক্ষেত্রসহ।

তাহলে দুটি semantics কেন? কাজ ভিন্ন। Operational semantics যন্ত্রের কাছাকাছি: interpreter লেখা (পর্ব ৫৬), ধাপ গোনা, type soundness-এর progress আর preservation (পর্ব ৩৮), আর concurrency-র মতো জায়গায়, যেখানে ধাপের ক্রমই অর্থ। Denotational semantics সমতা আর যুক্তির কাছাকাছি: optimization-এর সঠিকতা, দুটি নকশার তুলনা, আর static analysis-এর ভিত্তি।

Compiler-এর ভেতরে compositionality

অংশ ২–৩-এর code একটি কৌশল দেখিয়েছে: E(e) আর C(S) AST একবার ঘুরে একটি function বানায়, তারপর সেই function বারবার যেকোনো state-এ চলে, AST আর দেখতে হয় না। একে closure compilation বলা হয়, আর সাধারণ tree-walking interpreter-এর চেয়ে এটি প্রায়ই দ্রুত, কারণ “কোন গঠন?” প্রশ্নটি একবারই হয়। এটি সরাসরি compositionality-র ফল: অর্থ যেহেতু অংশের অর্থ থেকে আসে, অংশগুলো আগেই “অনুবাদ” করে রাখা যায়।

Static analysis-ও একই কাঠামো ব্যবহার করে। আসল অর্থের বদলে একটি সরল, সসীম অর্থ নেওয়া হয়, যেমন প্রতিটি variable-এর শুধু চিহ্ন (ঋণাত্মক, শূন্য, ধনাত্মক, অজানা)। তখন loop-এর functional-ও সসীম lattice-এ চলে, আর Kleene iteration সসীম ধাপে থামে। এই ধারণার নাম abstract interpretation (Patrick আর Radhia Cousot, ১৯৭৭), আর পর্ব ৬৪-এর dataflow analysis এর একটি বিশেষ রূপ। আসল অর্থ সাধারণভাবে হিসাব করা যায় না, কারণ “loop থামে কি না” প্রশ্নটি নিজেই halting problem; তাত্ত্বিক সীমা গণনার তত্ত্বের পর্ব ৫৩-এ (Rice’s theorem) আর পর্ব ৭৮-এ (Program analysis-এর সীমা).

আরও গভীরে। Adequacy বলে সমান denotation-এর program বাইরে থেকে আলাদা করা যায় না, কিন্তু উল্টোটা বলে না: হয়তো আলাদা denotation-এর দুটি program কোনো program-এর ভেতরেই আলাদা আচরণ করে না। দুটি দিক একসঙ্গে সত্য হলে মডেলটিকে বলে fully abstract. Gordon Plotkin ১৯৭৭ সালে দেখান, PCF নামের একটি ছোট typed functional ভাষার Scott-মডেলে এটি খাটে না, কারণ মডেলে “parallel or” নামের এমন একটি function আছে, যা ভাষায় লেখা যায় না। এর সমাধান খুঁজতে প্রায় দুই দশক লেগেছে বলে ধরা হয়; ১৯৯০-এর দশকে game semantics (Abramsky, Jagadeesan, Malacaria; Hyland ও Ong; Nickau) PCF-এর fully abstract মডেল দেয়।

পরীক্ষা ও ইন্টারভিউতে। বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন সাধারণ:

  • “Operational আর denotational semantics-এর পার্থক্য?” প্রথমটি যন্ত্রের ধাপ দিয়ে অর্থ দেয় (⟨S, σ⟩ ⇓ σ′), দ্বিতীয়টি গাণিতিক function দিয়ে (⟦S⟧σ = σ′); দ্বিতীয়টি compositional, সমতা প্রমাণে সুবিধাজনক।
  • “Compositionality কী?” একটি গঠনের অর্থ শুধু তার সরাসরি অংশের অর্থ থেকে আসে; ফলে সমান অর্থের অংশ বদলাবদলি করা যায়।
  • “While-এর denotation দিন।” fix F, যেখানে F(w) = λσ. ⟦e⟧σ সত্য হলে w†(⟦S⟧σ), নইলে σ; least fixpoint = ⊔ Fn(⊥).
  • “এই loop-এর Kleene approximant f0…f3 লিখুন।” fk সংজ্ঞায়িত শুধু সেই state-এ, যেখান থেকে loop k-এর কম বার ঘোরে।
  • “⊥ কেন লাগে, least কেন?” না-থামা প্রকাশ করতে; অন্য fixpoint এমন ফল দাবি করে, যা চালিয়ে কখনো পাওয়া যায় না (while true { }-এ সব function-ই fixpoint).

৮ · AI-এর যুগে denotational semantics

Semantics নিয়ে AI assistant সুন্দর সমীকরণ লেখে, আর ভুল সমীকরণও দেখতে ঠিক সমীকরণের মতোই। এই বিষয়ে যে ভুলগুলো বারবার দেখা যায়:

AI-এর সাধারণ ভুলকীভাবে ধরবেন
While-এর অর্থ “সমীকরণের সমাধান” বলে থেমে যাওয়া, least fixpoint আর ⊥-এর কথা বাদwhile true { }-এ তার সংজ্ঞা খাটিয়ে দেখা: সব function সমাধান হলে সংজ্ঞাটি অসম্পূর্ণ
Error আর না-থামাকে এক করা, বা error-এর আগের আউটপুট হারিয়ে ফেলাশূন্য দিয়ে ভাগের আগে print আছে এমন program reference-এ চালিয়ে আউটপুট মেলানো
এক ভাষার নিয়ম সব ভাষায়: “x + 1 − 1 সবসময় x”, “অদরকারি assignment মুছে ফেলা নিরাপদ”সীমার মান (INT_MAX, শূন্য ভাজক) দিয়ে দুই রূপ চালানো; C-তে UB, Haat-এ wrap আর runtime error আলাদা
“কয়েকটি পরীক্ষায় মিলেছে, তাই সমান” ধরনের দাবিকে প্রমাণ বলাBounded check-কে পাল্টা উদাহরণ খোঁজার যন্ত্র হিসেবে দেখা; সমতার জন্য সমীকরণ বা induction-এর প্রমাণ চাওয়া
Knaster–Tarski আর Kleene গুলিয়ে ফেলা, বা ভুল শর্তে theorem খাটানো (partial function-এর সেটকে complete lattice বলা)শর্ত মিলিয়ে দেখা: কোনটিতে complete lattice আর monotone, কোনটিতে cpo আর continuous লাগে; প্রাথমিক উৎস বা পাঠ্যবই
Short-circuit বা evaluation order ভুলভাবে সমীকরণে লেখাb != 0 && a / b > 2-এর মতো উদাহরণ দুই ক্রমে চালানো

AI-কে কাজে লাগাতে ভাষার নিয়ম স্পষ্ট বলুন, আর প্রতিটি দাবির যাচাইযোগ্য রূপ চান:

আমি Haat-core নামের একটি ছোট imperative ভাষার denotational semantics লিখছি। নিয়ম: Int ৬৪-বিট, overflow wrap করে; / আর % C-র মতো শূন্যের দিকে কাটে; শূন্য দিয়ে ভাগ runtime error, আর error-এর আগের print থেকে যায়; && আর || short-circuit. ১. ⟦S⟧ : Σ → (Σ ∪ err Σ)⊥ ধরে assignment, print, if, sequencing আর while-এর সমীকরণ দাও। while-এর জন্য functional F লিখে least fixpoint হিসেবে সংজ্ঞা দাও, আর ⊥ কেন লাগে বলো। ২. while total < 5000 { total = total + 1250; } loop-এর f0, f1, f2, f3 total = 2500, 3750, 5000-এ কী, টেবিলে দেখাও। ৩. "y = 1 / x; y = 0;" আর "y = 0;" কি সমান? একটি নির্দিষ্ট state দিয়ে উত্তর দাও। ৪. Kleene আর Knaster–Tarski theorem-এর শর্তের পার্থক্য বলো। কোথাও নিশ্চিত না হলে স্পষ্ট বলো; আমি প্রতিটি উত্তর চালিয়ে যাচাই করব।

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

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

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

প্র ০১Strachey-র সমস্যা কী ছিল, যার সমাধানে Scott-কে নতুন গণিত বানাতে হলো?

১৯৬০-এর দশকে Christopher Strachey CPL নামের একটি ভাষার নকশায় যুক্ত ছিলেন, আর ভাষার অর্থ লিখতে চাইছিলেন lambda calculus-এ অনুবাদ করে: প্রতিটি গঠনের অর্থ একটি λ-term. পরিকল্পনাটি সুন্দর, কিন্তু একটি ফাঁক ছিল। Untyped lambda calculus-এ একটি term নিজেকেই argument হিসেবে নিতে পারে (যেমন x x), তাই এর মানের সেট D-কে এমন হতে হবে, যাতে D থেকে D-এর function-গুলোও D-এর ভেতরে থাকে। সাধারণ সেট-গণিতে এটি অসম্ভব: D-এর চেয়ে D → D-এর সব function-এর সেট সবসময় বড় (Cantor-এর যুক্তি)। তাহলে λ-term-এর “অর্থ” আসলে কী, তার কোনো গাণিতিক উত্তর ছিল না; অনুবাদটি শুধু এক লেখা থেকে আরেক লেখায় যাওয়া।

Dana Scott প্রথমে এ নিয়ে সন্দিহান ছিলেন বলে বর্ণনা পাওয়া যায়, আর একটি typed বিকল্পের প্রস্তাব করেছিলেন। পরে ১৯৬৯ সালের শেষ দিকে তিনি নিজেই একটি পথ খুঁজে পান: সব function নয়, শুধু continuous function নেওয়া, তথ্যের ক্রমের অর্থে। এমন function-এর সেট যথেষ্ট ছোট, আর তিনি D∞ নামের একটি বস্তু গড়ে দেখান যেখানে D আর [D → D] সমরূপ। এই ক্রম, ⊥, lub আর continuity-ই domain theory-র ভিত্তি, আর এই পর্বের Kleene iteration-এর পেছনে ঠিক এই ধারণাগুলো।

এর একটি দার্শনিক দিকও আছে। Continuity মানে “ফলের প্রতিটি সসীম অংশ ইনপুটের একটি সসীম অংশ থেকে আসে”; এটি গণনার স্বভাবের সঙ্গে মেলে, কারণ কোনো program সসীম সময়ে অসীম ইনপুট পড়তে পারে না। অর্থাৎ গাণিতিক শর্তটি একটি বাস্তব সত্যের প্রতিফলন। ⊥-কে ক্রমের নিচে রাখা, যাকে “কোনো তথ্য নেই” পড়া যায়, তেমনি একটি সত্য প্রকাশ করে: না-থামা program কিছুই জানায় না। Strachey ১৯৭৫ সালে মারা যান; Scott পরে বহু সম্মান পান, যদিও তাঁর ১৯৭৬ সালের Turing Award (Michael Rabin-এর সঙ্গে) মূলত automata-র কাজের জন্য।

মূল উপলব্ধি: denotational semantics-এর প্রথম বাধা ছিল self-application-এর গাণিতিক মডেল না থাকা; Scott-এর সমাধান ছিল সব function নয়, শুধু continuous function নেওয়া, আর সেই ক্রম আর ⊥-ই আজ loop আর recursion-এর অর্থের ভিত্তি।

প্র ০২Least fixpoint না নিয়ে greatest fixpoint নিলে কী হতো? কোনো জায়গায় কি সেটিই ঠিক?

Partial function-এর ক্রমে সাধারণত “greatest” fixpoint থাকেই না, কারণ সেটটি complete lattice নয়: while true { }-এ সব function fixpoint, আর তাদের অনেকগুলো একে অপরের সঙ্গে অসঙ্গত (একটি বলে ফল 5000, আরেকটি বলে 6000). কিন্তু প্রশ্নটির আসল বিষয় হলো “বেশি দাবি করা” fixpoint. সেগুলো এমন ফল দাবি করে যা যন্ত্র কখনো দেয় না। একটি compiler যদি এমন অর্থ মেনে নিত, তাহলে “এই loop শেষে total = 4500” ধরে নিয়ে loop-এর পরের কোড optimize করত, অথচ বাস্তবে সেখানে কখনো পৌঁছানো যায় না। Least fixpoint ঠিক সেই ফলগুলোই দেয়, যাদের পেছনে একটি সসীম হিসাব আছে, কারণ ⊔ Fn(⊥)-এর প্রতিটি ফল কোনো সসীম n-এ এসেছে।

তবে কিছু জায়গায় greatest fixpoint-ই স্বাভাবিক। অসীম ডেটা (যেমন একটি stream, যা কখনো শেষ হয় না) বা চিরকাল চলা server-এর আচরণ বর্ণনায় প্রশ্ন “কী গড়া যায়” নয়, বরং “কী কখনো ভাঙে না”। সেখানে coinduction আর greatest fixpoint কাজে লাগে, আর bisimulation-এর মতো ধারণা (দুটি প্রক্রিয়া চিরকাল ধাপে ধাপে একে অপরকে অনুসরণ করতে পারে) একটি greatest fixpoint হিসেবে সংজ্ঞায়িত হয়। Model checking-এর temporal logic-এও “সবসময় সত্য” ধরনের ধর্ম greatest fixpoint, আর “কখনো না কখনো সত্য হবে” least fixpoint, এমন বর্ণনা প্রচলিত।

Program analysis-এও দুই দিক দেখা যায়। Dataflow analysis-এ (পর্ব ৬৪) কোন lattice-এ কোন দিক “নিরাপদ”, তার ওপর নির্ভর করে least বা greatest fixpoint খোঁজা হয়; যেমন “এই expression সব পথে আগে হিসাব হয়েছে” ধরনের must-analysis-এ শুরু করা হয় “সব সত্য” থেকে আর নিচে নামা হয়। গণিতটি একই, শুধু ক্রমের দিক উল্টো।

মূল উপলব্ধি: least fixpoint কোনো খেয়ালি পছন্দ নয়: এটি ঠিক সেই ফল দেয় যা সসীম হিসাবে পাওয়া যায়; অসীম আচরণ আর “কখনো ভাঙে না” ধরনের ধর্মে greatest fixpoint আর coinduction স্বাভাবিক হাতিয়ার।

প্র ০৩বাস্তব ভাষার spec-এ denotational semantics কতটা ব্যবহৃত হয়েছে, আর কেন বেশিরভাগ spec অন্য পথ নিয়েছে?

সবচেয়ে পরিচিত উদাহরণ Scheme. R5RS (১৯৯৮) রিপোর্টে মূল expression-গুলোর একটি আনুষ্ঠানিক denotational semantics ছিল, continuation-সহ। R6RS (২০০৭) সেটি বদলে একটি operational semantics দেয়, যা PLT Redex নামের tool-এ চালিয়ে পরীক্ষা করা যেত বলে উল্লেখ আছে; আর R7RS-small (২০১৩) আবার R5RS-ধাঁচের denotational অংশ ফিরিয়ে আনে বলে জানা যায়। এই আসা-যাওয়াই একটি শিক্ষা: denotational সংজ্ঞা সংক্ষিপ্ত আর যুক্তির জন্য সুন্দর, কিন্তু কিছু বৈশিষ্ট্যে (যেমন evaluation order unspecified রাখা, বা concurrency) এটি জটিল হয়ে পড়ে, আর চালিয়ে পরীক্ষা করা কঠিন।

অন্য বড় উদাহরণগুলো অন্য পথে। The Definition of Standard ML (১৯৯০, সংশোধিত ১৯৯৭) big-step বা natural semantics-এ লেখা। WebAssembly-র আনুষ্ঠানিক spec small-step reduction আর typing rule ব্যবহার করে। Java, C আর JavaScript-এর spec মূলত গদ্য বা algorithm-ধাঁচের লেখা; ECMAScript-এর spec প্রায় একটি interpreter-এর pseudocode. কারণগুলো ব্যবহারিক: বাস্তব ভাষায় exception, mutable heap, thread আর বিশাল standard library আছে, যাদের denotation লিখতে domain-এর জটিল গঠন লাগে, আর পাঠকের বেশিরভাগ সেই গণিত জানেন না। Operational নিয়ম একজন interpreter-লেখকের কাছে সরাসরি পড়ার মতো।

তবু denotational চিন্তা হারিয়ে যায়নি, অন্য জায়গায় চলে গেছে। Haskell-এর মতো ভাষার আলোচনায় “⊥” সাধারণ শব্দ; monad-এর ধারণা Eugenio Moggi-র ১৯৮৯–৯১ সালের denotational কাজ থেকে প্রোগ্রামিংয়ে আসে বলে ধরা হয়। Compiler verification-এ (পর্ব ৪৪) দুটি program-এর অর্থ সমান কি না প্রশ্নটি কেন্দ্রীয়, আর abstract interpretation সরাসরি denotational কাঠামোর ওপর দাঁড়ানো। অর্থাৎ পূর্ণ ভাষার spec লেখায় না হলেও, ছোট core-এ যুক্তি আর tool বানাতে এটি নিয়মিত ব্যবহৃত।

মূল উপলব্ধি: পূর্ণ বাস্তব ভাষার spec সাধারণত operational বা গদ্যে, কারণ তা পড়া আর চালানো সহজ; denotational semantics বেঁচে আছে ছোট core-এর যুক্তি, optimization-এর সঠিকতা, monad-এর মতো নকশার ধারণা আর static analysis-এর ভিত্তিতে।

প্র ০৪Haat-এ y = 1 / x; y = 0; থেকে প্রথম assignment মোছা যায় না। C-তে একই কাজ compiler করতে পারে কেন?

Haat-এ শূন্য দিয়ে ভাগের অর্থ নির্ধারিত: err, program থামে, আগের আউটপুট থাকে। অংশ ৬-এর checker দেখিয়েছে x = 0-তে দুই রূপের denotation আলাদা, তাই মুছে ফেলা অর্থ বদলায়; Haat-এর একটি সঠিক optimizer এটি করতে পারে না, যদি না সে প্রমাণ করতে পারে x কখনো শূন্য নয়। C-তে (C17) শূন্য দিয়ে integer ভাগ undefined behavior: standard সেই ক্ষেত্রে কোনো আচরণ দাবি করে না। Denotational ভাষায়, C-র অর্থ একটি function নয়, বরং অনুমোদিত আচরণের একটি সেট, আর UB-র ক্ষেত্রে সেটটি “সব কিছু”। তখন compiler-এর প্রতিশ্রুতি সমতা নয়, বরং refinement: অপ্টিমাইজ করা program-এর আচরণ মূলের অনুমোদিত আচরণের মধ্যে থাকলেই চলে। “সব কিছু”-র মধ্যে “কিছু না করে y = 0” পড়ে, তাই ভাগটি মুছে ফেলা বৈধ।

একই যুক্তি loop-এ। C11 (৬.৮.৫) বলে, যে loop-এর শর্ত একটি ধ্রুবক নয় আর যার দেহে input/output, volatile access বা synchronization নেই, implementation ধরে নিতে পারে সেটি শেষ হয়। C++-এ একটি আরও বিস্তৃত “forward progress” নিয়ম আছে, যার ফলে side effect-হীন অসীম loop UB; C++26-এর জন্য while (true) ;-এর মতো trivial অসীম loop-কে এর বাইরে আনার একটি প্রস্তাব (P2809) গৃহীত হয়েছে বলে জানা যায়। Denotational ভাষায় এর মানে: এমন loop-এর ⊥ ফলটিকে compiler “যেকোনো ফল” হিসেবে পড়তে পারে, তাই loop মুছে দিতে পারে। Haat-এ এমন নিয়ম নেই; অংশ ৫-এর total != 4500 loop-এর অর্থ ⊥, আর কোনো optimizer সেটিকে “শেষ হয়” বানাতে পারে না।

নকশার পার্থক্যটি তাই একটি আপস। UB compiler-কে স্বাধীনতা দেয় (বাড়তি পরীক্ষা ছাড়া দ্রুত code), কিন্তু programmer-এর পক্ষে অর্থ বোঝা কঠিন করে, কারণ এক জায়গার UB পুরো program-এর অর্থ নষ্ট করতে পারে। Haat (আর Java, Rust-এর safe অংশ) প্রতিটি ক্ষেত্রে একটি নির্দিষ্ট অর্থ দেয়, আর optimizer-কে তা মেনে চলতে হয়।

মূল উপলব্ধি: optimization-এর সঠিকতা হলো denotation-এর সমতা (বা UB থাকলে refinement); Haat-এ error আর ⊥ নির্দিষ্ট অর্থ, তাই মুছে ফেলা যায় না, আর C/C++-এ UB আর termination-এর অনুমান compiler-কে সেই স্বাধীনতা দেয়।

প্র ০৫প্রতিটি Haat-core program-এর একটি নির্দিষ্ট denotation আছে। তাহলে compiler কেন তা হিসাব করে দুটি program-এর সমতা যাচাই করে না?

“আছে” আর “হিসাব করা যায়” আলাদা কথা। Kleene-এর theorem নিশ্চিত করে fix F একটি নির্দিষ্ট গাণিতিক বস্তু, কিন্তু সেটি অসীম শিকলের সীমা। কোনো একটি state-এ ফল থাকলে সসীম ধাপে তা পাওয়া যায়; ⊥ হলে কোনো সসীম ধাপে “এখানে চিরকাল ⊥” নিশ্চিত হয় না, যেমন অংশ ৫-এ ৩০০ ধাপ পরেও শুধু পর্যবেক্ষণ ছিল, প্রমাণ এসেছে আলাদা গাণিতিক যুক্তি থেকে। সাধারণভাবে “⟦S⟧σ = ⊥ কি না” প্রশ্নটি halting problem, আর Rice-এর theorem আরও বলে যে program-এর অর্থের যেকোনো non-trivial ধর্ম (যেমন “এই দুটি program সমতুল্য”) সাধারণভাবে নির্ধারণযোগ্য নয়।

Haat-core-এ state-এর সংখ্যা সসীম (প্রতিটি variable ৬৪-বিট), তাই তাত্ত্বিকভাবে সব state পরীক্ষা করা যায়, কিন্তু দুটি variable-এই 2128টি state, যা বাস্তবে অসম্ভব। অংশ ৬-এর checker তাই একটি ছোট অংশ দেখে, যা পাল্টা উদাহরণ খুঁজতে ভালো কিন্তু প্রমাণ দেয় না। বাস্তব tool তিনটি পথ নেয়। এক, প্রমাণ: মানুষ বা proof assistant সমীকরণ দিয়ে প্রমাণ লেখে, যেমন অংশ ৬-এর stepper. দুই, symbolic যাচাই: SMT solver সব ৬৪-বিট মান একসঙ্গে প্রতীকীভাবে দেখে, loop-হীন অংশে এটি খুব কার্যকর (পর্ব ৪৪)। তিন, approximation: abstract interpretation আসল অর্থের বদলে একটি সসীম, নিরাপদ অনুমান হিসাব করে, যা কখনো কখনো “জানি না” বলে কিন্তু কখনো ভুল নিশ্চয়তা দেয় না।

Compiler-এর optimizer আসলে তৃতীয় পথের মানুষ: সে প্রতিটি রূপান্তর আগে থেকে (সাধারণ ক্ষেত্রে) সঠিক বলে প্রমাণিত নিয়মে করে, আর নির্দিষ্ট program-এ শুধু নিয়মের শর্ত (যেমন “x এখানে কখনো শূন্য নয়”) একটি নিরাপদ analysis দিয়ে যাচাই করে। Translation validation নামের একটি পদ্ধতিতে প্রতিটি compile-এর পরে মূল আর ফলের সমতা আলাদাভাবে যাচাইয়ের চেষ্টা হয়; এটিও প্রতীকী পদ্ধতির ওপর নির্ভর করে।

মূল উপলব্ধি: denotation সংজ্ঞায়িত হলেও সাধারণভাবে হিসাবযোগ্য নয় (halting problem, Rice); বাস্তবে সমতা আসে হাতে বা যন্ত্রে লেখা প্রমাণ, SMT-ভিত্তিক symbolic যাচাই, আর নিরাপদ approximation থেকে, আর bounded পরীক্ষা শুধু পাল্টা উদাহরণ খোঁজার হাতিয়ার।

অনুশীলন

প্রথমে নিজে লিখুন বা হিসাব করুন, তারপর উত্তর খুলুন। প্রতিটি উত্তর চালানো interpreter দিয়ে যাচাই করা।

  1. নকশা ও বাস্তবায়ন — Haat-এর বর্ধিত রূপে do-while: Haat-এর বর্ধিত রূপে do { S } while e; যোগ করুন (দেহ অন্তত একবার চলে; spec v1-এ এটি নেই)। (ক) এর denotation লিখুন। (খ) প্রমাণ করুন এটি S while e { S }-এর সমান। (গ) অংশ ৩-এর C()-এ এটি যোগ করুন, আর { print(x); x = x - 1; } দেহ নিয়ে x = 3, 0, −2-তে আউটপুট বলুন। x = 0-তে সাধারণ while-এর সঙ্গে পার্থক্য কী?

    (ক) ⟦do { S } while e;⟧σ = W†(⟦S⟧σ), যেখানে W = ⟦while e { S }⟧ = fix F. নতুন কোনো fixpoint লাগে না, পুরোনোটিই কাজে লাগে। (খ) Seq-এর সমীকরণে ⟦S while e { S }⟧σ = W†(⟦S⟧σ), যা (ক)-এর ডান পাশ হুবহু; তাই সব σ-তে সমান। (এটি desugaring-এর সঠিকতার প্রমাণ: বড় গঠনকে ছোট core-এ নামানো অর্থ বদলায় না।) (গ) কোড:

    def DO(c, b):                          # ("do", S, e) — বর্ধিত রূপ
        W = WHILE(b, c)
        return lambda s: lift(c(s), W)     # আগে S, তারপর পুরো while
    # C()-এর শুরুতে: if S[0] == "do": return DO(C(S[1]), E(S[2]))

    লেখকের lab-এ চালানো (CPython 3.14.4): x = 3-তে আউটপুট 3 2 1, x = 0-তে 0, x = −2-তে -2; তিনটিতেই S while …-এর সঙ্গে denotation হুবহু এক (True). x = 0-তে সাধারণ while x > 0 { … } কিছুই ছাপে না (()), আর do-while একবার 0 ছাপে: শর্ত দেখার আগে দেহ চলে।

  2. ভুল খুঁজুন: একজন লিখলেন: “Haat-এ x = x * 2; x = x / 2; আর { } সমান। প্রমাণ: (১) ⟦x = x * 2;⟧σ = σ[x ↦ 2σ(x)]; (২) তার ওপর ⟦x = x / 2;⟧ দেয় σ[x ↦ 2σ(x) / 2]; (৩) 2σ(x) / 2 = σ(x), তাই ফল σ. অংশ ৬-এর checker-এ x, y ∈ −3…3-এর ৪৯টি state-এ সমান এসেছে।” কোন ধাপ ভুল? পাল্টা উদাহরণ দিন।

    ধাপ ১-এ wrap বাদ পড়েছে: সঠিক সমীকরণ σ[x ↦ wrap(2σ(x))] (সিদ্ধান্ত ১৩)। ধাপ ৩ তাই সাধারণ গণিতে সত্য, ৬৪-বিটে নয়: গুণে বিট হারালে ভাগ তা ফেরায় না। অংশ ৬-এর checker সীমার মান দিয়ে চালালে (same(p, "skip", EDGE)) পাওয়া যায় আলাদা! x=-9223372036854775808 …: INT_MIN × 2 wrap হয়ে 0, আর 0 / 2 = 0. আরেকটি: x = 262 = 4611686018427387904 হলে গুণফল wrap হয়ে −263, আর ভাগে −262. Reference-এ সত্যিকারের run: var x = 4611686018427387904; x = x * 2; x = x / 2; print(x); ছাপে -4611686018427387904, আর INT_MIN থেকে শুরু করলে 0. শিক্ষা দুটি: সমীকরণে wrap-এর মতো “ছোট” অংশ বাদ দেওয়া চলে না, আর ছোট মানের bounded check সীমার ভুল ধরে না।

  3. হিসাব — approximant: while x < 10 { x = x + 3; } loop-এর জন্য f0 থেকে f6 হিসাব করুন, শুরুর x = 0, 4, 9, 10-এ। কোন ধাপে কোন state সংজ্ঞায়িত হয়? f3 আর f4 এই চারটি state-এ সমান হলে কি থেমে যাওয়া যায়?
            x=0  x=4  x=9  x=10
    f0:      ⊥    ⊥    ⊥    ⊥
    f1:      ⊥    ⊥    ⊥   10
    f2:      ⊥    ⊥   12   10
    f3:      ⊥   10   12   10
    f4:      ⊥   10   12   10
    f5:     12   10   12   10
    f6:     12   10   12   10

    টেবিলটি লেখকের lab-এ approx() চালিয়ে পাওয়া (CPython 3.14.4). x = 10-এ শূন্য ঘোরা (f1), x = 9-এ এক ঘোরা (f2, ফল 12), x = 4-এ দুই ঘোরা: 4 → 7 → 10 (f3), আর x = 0-তে চার ঘোরা: 0 → 3 → 6 → 9 → 12 (f5). f3 আর f4 এই চারটি state-এ সমান, কারণ ঠিক তিন ঘোরা লাগে এমন কোনো state তালিকায় নেই; কিন্তু f5-এ x = 0 নতুন করে সংজ্ঞায়িত। তাই না, কয়েকটি state-এ দুটি পরপর approximant মিললেই থামা যায় না। পুরো function হিসেবে f3 ≠ f4 (যেমন x = 1-এ: 1 → 4 → 7 → 10, তিন ঘোরা)। Reference-এ var z = 0; while z < 10 { z = z + 3; } print(z); ছাপে 12.

  4. প্রমাণ — দুবার loop: W = ⟦while e { S }⟧ হলে প্রমাণ করুন ⟦while e { S } while e { S }⟧ = W. ইঙ্গিত: প্রথমে k-এর ওপর induction দিয়ে দেখান, fk(σ) = σ′ (একটি স্বাভাবিক state) হলে ⟦e⟧σ′ = false.

    Lemma. প্রতিটি k-এর জন্য: fk(σ) = σ′ হলে ⟦e⟧σ′ = false. k-এর ওপর induction.

    1. k = 0: f0 = ⊥ কোথাও স্বাভাবিক state দেয় না, দাবি শূন্যভাবে সত্য।
    2. k → k + 1: fk+1(σ) = F(fk)(σ). যদি ⟦e⟧σ = false, ফল σ নিজে, আর ⟦e⟧σ = false. যদি true, ফল fk†(⟦S⟧σ); এটি একটি স্বাভাবিক state σ′ হলে ⟦S⟧σ নিজেও স্বাভাবিক state, আর fk(⟦S⟧σ) = σ′, তাই IH থেকে ⟦e⟧σ′ = false. err হলে দাবির কিছু নেই। ∎

    মূল প্রমাণ. ⟦W-এর পরে W⟧σ = W†(W(σ)). তিন case: W(σ) = ⊥ বা err σ′ হলে † সেটিই রাখে, তাই ফল W(σ). W(σ) = σ′ স্বাভাবিক হলে কোনো k-তে fk(σ) = σ′ (lub-এর প্রতিটি ফল কোনো সসীম ধাপে আসে), তাই Lemma থেকে ⟦e⟧σ′ = false, আর W(σ′) = F(W)(σ′) = σ′. তিন case-এই ফল W(σ). ∎ অংশ ৬-এর checker-এ দুটি loop-এ (x > 0 থেকে কমানো, আর x % 3 != 0 থেকে বাড়ানো) এই সমতা ৪৯টি state-এ মিলেছে (লেখকের lab, CPython 3.14.4), যা প্রমাণের সঙ্গে সামঞ্জস্যপূর্ণ, তবে প্রমাণটিই সব state-এর নিশ্চয়তা দেয়।

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

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

ক্রমDenotational semantics-এ while e { S }-এর অর্থ বের করার ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. ⟦e⟧ আর ⟦S⟧ আগে বের করা (compositionality)
  2. Functional F(w) = λσ. ⟦e⟧σ সত্য হলে w†(⟦S⟧σ), নইলে σ লেখা
  3. f0 = ⊥ দিয়ে শুরু করা
  4. fk+1 = F(fk) বারবার হিসাব করা
  5. শিকল f0 ⊑ f1 ⊑ …-এর lub নেওয়া, যা least fixpoint

Denotational semantics-এ “compositionality” বলতে কী বোঝায়?

  • প্রতিটি expression বাঁ থেকে ডানে হিসাব হয়
  • একটি গঠনের অর্থ শুধু তার সরাসরি অংশগুলোর অর্থ থেকে তৈরি হয়
  • Program ছোট ছোট function জুড়ে লিখতে হয়
  • Compiler-এর প্রতিটি ধাপ আলাদা file-এ থাকে

Haat-core-এ while true { } loop-এর denotation কী?

  • প্রতিটি σ-তে σ (state অপরিবর্তিত)
  • প্রতিটি σ-তে err σ (runtime error)
  • অর্থ সংজ্ঞায়িত নয়, কারণ সমীকরণের অনেক সমাধান
  • প্রতিটি σ-তে ⊥

while total < 5000 { total = total + 1250; rounds = rounds + 1; } loop-এর Kleene approximant f0 = ⊥, fk+1 = F(fk). শুরুর state total = 2500, rounds = 0-তে প্রথম কোন approximant সংজ্ঞায়িত, আর ফল কী?

  • f1, ফল total = 2500, rounds = 0
  • f2, ফল total = 3750, rounds = 1
  • f3, ফল total = 5000, rounds = 2
  • f5, ফল total = 5000, rounds = 4

Haat-এ (৬৪-বিট wrap, শূন্য দিয়ে ভাগ runtime error) কোন জোড়া statement-এর denotation সব state-এ সমান নয়?

  • y = 1 / x; y = 0;  আর  y = 0;
  • x = x + 1; x = x - 1;  আর  { }
  • while x > 0 { x = x - 1; }  আর  if x > 0 { x = x - 1; while x > 0 { x = x - 1; } } else { }
  • while x > 0 { x = x - 1; }  আর  if x > 0 { x = 0; } else { }

State থেকে ফলের partial function-এর সেটে (ক্রম ⊑ = “f যেখানে সংজ্ঞায়িত, g-ও সেখানে একই মান দেয়”) loop-এর least fixpoint-এর অস্তিত্ব নিশ্চিত করতে সাধারণত কোন theorem খাটানো হয়, আর কেন?

  • Knaster–Tarski, কারণ partial function-এর সেট একটি complete lattice
  • Kleene, কারণ সেটটি একটি cpo আর F continuous
  • Halting problem, কারণ loop থামে কি না জানা যায় না
  • Rice-এর theorem, কারণ অর্থটি semantic ধর্ম

Haat-core-এ (call নেই, expression কোনো state বদলায় না) σ = {a ↦ 10, b ↦ 0} হলে b != 0 && a / b > 2 আর a / b > 2 && b != 0-এর অর্থ কী?

  • দুটিই false, কারণ && প্রতিসম
  • দুটিই runtime error (err)
  • প্রথমটি false, দ্বিতীয়টি err
  • প্রথমটি err, দ্বিতীয়টি false

শব্দকোষ

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

মনে রাখুন

  1. অর্থ = function: ⟦e⟧ : Σ → V ∪ {err}, ⟦S⟧ : Σ → (Σ ∪ err Σ)⊥. err মানে error-এ থামা (আউটপুট থাকে), ⊥ মানে চিরকাল চলা।
  2. Compositional: প্রতিটি গঠনের অর্থ শুধু সরাসরি অংশের অর্থ থেকে; sequencing-এ strict extension f† error আর ⊥ পার করে দেয়।
  3. While = least fixpoint: F(w) = λσ. ⟦e⟧σ সত্য হলে w†(⟦S⟧σ), নইলে σ; ⟦while⟧ = fix F = ⊔ Fn(⊥). fk জানে k-এর কম ঘোরায় শেষ হওয়া state.
  4. দুই theorem: Kleene (cpo + continuous ⇒ ⊔ Fn(⊥) least fixpoint), Knaster–Tarski (complete lattice + monotone); partial function cpo, lattice নয়।
  5. সমতা: ⟦S⟧ = ⟦T⟧ হলে যেকোনো program-এ বদলানো নিরাপদ; while-এর unfolding সমীকরণে প্রমাণ হয়, আর y = 1 / x; y = 0; ≠ y = 0; একটি state-এই ধরা পড়ে।

পরের পর্বে: পর্ব ৪২ (Axiomatic semantics — Hoare logic আর loop invariant). Program-এর পুরো অর্থ না লিখে শুধু “আগে এটি সত্য হলে পরে ওটি সত্য” প্রমাণ করা: Hoare triple, weakest precondition, আর বাজারঘরের ছাড়ের loop-এর invariant.

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

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