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

Program analysis-এর সীমা — abstract interpretation আর type system

Limits of Program Analysis — Dataflow Analysis, Lattices and Fixpoints, Abstract Interpretation, Widening, Type Inference and Symbolic Execution

Taught in Bangla, this lesson starts from Rice's theorem: an analyzer cannot be sound, complete and always terminating at once. It builds dataflow analysis on lattices and fixpoints, abstract interpretation with sign and interval domains, widening and narrowing, type inference by unification and symbolic execution. In-page Python (Pyodide) runs liveness and interval analyses checked against 101 concrete runs, and real mypy 2.4.1 and pyright 1.1.414 runs catch a real bug, warn on a harmless line and miss a crash.

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

  • Control-flow graph, lattice, transfer function আর fixpoint দিয়ে dataflow analysis লেখা, আর liveness analysis হাতে ও code-এ চালানো
  • Abstract domain, α আর γ, Galois connection-এর ধারণা, আর একটি abstract operation sound কি না পরীক্ষা করা
  • Interval domain-এ widening আর narrowing দিয়ে loop-এর invariant বের করা, আর কেন widening ছাড়া analysis থামে না তার প্রমাণ
  • Sound, complete আর থামার আপসকে সত্যিকারের tool-এর false positive আর false negative দিয়ে চেনা
  • Type checking কেন decidable, type inference কীভাবে কাজ করে, আর symbolic execution, testing ও verification কোথায় বসে

১ · Rice-এর পরে — বাজারঘরের analyzer-এর তিন চাওয়া

মডিউল ৯-এ দেয়ালটি দেখেছেন। পর্ব ৫১-এ halting problem undecidable, পর্ব ৫৩-এ Rice-এর theorem বলেছে program-এর আচরণ নিয়ে প্রতিটি non-trivial প্রশ্ন undecidable, আর পর্ব ৫৫-এ দেখেছেন এর ফল: প্রতিটি সবসময়-থামা static analysis tool কিছু program-এ false positive বা false negative দেয়। পর্ব ৫৫ প্রশ্ন করেছিল “কেন”; এই পর্বের প্রশ্ন “কীভাবে”: এই সীমার ভেতরে থেকে প্রকৌশলীরা কোন গণিত দিয়ে কাজের analyzer বানান, আর প্রতিটি নকশা ঠিক কোথায় দাম দেয়।

বাজারঘরের হিসাবরক্ষক মাসের বাজারের ফর্দ বানান, কিন্তু প্রতিটি জিনিসের ঠিক দাম জানেন না। তাই লেখেন “চাল ৬০০ থেকে ৮০০ টাকা, ডাল ১৫০ থেকে ২০০ টাকা”, আর range-গুলো যোগ করে বলেন “মোট খরচ ৭৫০ থেকে ১,০০০ টাকার মধ্যে”। বাজেট ১,২০০ টাকা হলে তিনি নিশ্চিত: বাজেট ছাড়াবে না। এটি sound সিদ্ধান্ত, যদিও কেউ একটিও আসল দাম বলেনি। কিন্তু বাজেট ৯০০ হলে তিনি বলবেন “ছাড়াতে পারে”, যদিও এ মাসে হয়তো আসলে ৮০০-তেই হয়ে যেত। এই সতর্কতা হয়তো ভুল, কিন্তু কখনো বিপজ্জনক নয়। Abstract interpretation ঠিক এই হিসাবরক্ষক: আসল মানের বদলে মানের একটি নিরাপদ “ঘের” নিয়ে হিসাব।

পর্ব ৫৫-এর সংজ্ঞা মনে রাখুন। একটি “খারাপ” আচরণ P (যেমন শূন্য দিয়ে ভাগ) খুঁজতে analyzer প্রতিটি program-এ “warn” বা “ok” বলে। Sound মানে আসল bug কখনো মিস হয় না, complete মানে প্রতিটি সতর্কতা আসল। তৃতীয় চাওয়া হলো থামা: প্রতিটি program-এ analyzer নিজে সসীম সময়ে উত্তর দেয়। পর্ব ৫৫-এর উপপাদ্য ২.২ বলে, তিনটি একসঙ্গে অসম্ভব। তাই প্রতিটি tool একটি ছাড়ে।

পদ্ধতিযা রাখেযা ছাড়ে
Abstract interpretation, dataflow analysis, type checkingsound, থামাcomplete: ভুল সতর্কতা আসে
Testing, fuzzing, bounded symbolic executioncomplete (প্রতিটি crash আসল), থামাsound: যা চেষ্টা হয়নি তা মিস
পূর্ণ symbolic execution, প্রমাণ খোঁজাsound আর complete (উত্তর দিলে ঠিক)থামা: কিছু program-এ চিরকাল চলে বা “জানি না”
বাস্তব শিল্প-tool (যেমন mypy)থামা, কম ভুল সতর্কতাইচ্ছে করে কিছু sound-ness, কিছু complete-ness দুটিই

২ · Dataflow analysis — lattice, transfer function আর fixpoint

Compiler বা analyzer প্রথমে program-কে একটি control-flow graph (CFG) বানায়: প্রতিটি statement একটি node, আর “এরপর কোনটি চলতে পারে” একটি directed edge. Loop মানে graph-এ একটি চক্র। প্রশ্নটি হয় এমন: “লাইন k-এর ঠিক আগে কোন variable-গুলোর মান পরে কাজে লাগবে?” এটি liveness analysis. যে variable-এর মান আর কখনো পড়া হবে না, তার register খালি করা যায়, আর তাতে লেখা একটি assignment অপ্রয়োজনীয় (dead store).

বাজারঘরের একটি ছোট function ধরুন, যা একটি order-এর n-টি জিনিসের দাম যোগ করে। লাইন ২-এর tax কেউ পরে পড়ে না।

1  total = 0
2  tax = 15
3  i = 0
4  while i < n:
5      price = read(i)
6      total = total + price
7      i = i + 1
8  print(total)

প্রতিটি লাইন ℓ-এর জন্য দুটি জিনিস লেখা যায়: def(ℓ), লাইনটি যে variable লেখে, আর use(ℓ), যে variable পড়ে। তারপর দুটি সমীকরণ, যেখানে succ(ℓ) মানে ℓ-এর পরে যে লাইনগুলো চলতে পারে:

out(ℓ) = ⋃s ∈ succ(ℓ) in(s)     in(ℓ) = use(ℓ) ∪ (out(ℓ) − def(ℓ))

প্রথম সমীকরণ বলে: কোনো পরের লাইনে কোনো পথে দরকার হলেই variable-টি এখান থেকে বের হওয়ার সময় live. দ্বিতীয়টি: লাইনটি নিজে যা পড়ে তা live, আর পরে যা দরকার তা-ও, যদি না এই লাইনই সেটি নতুন করে লেখে। তথ্য প্রবাহিত হয় শেষ থেকে শুরুর দিকে, তাই liveness একটি backward analysis. Loop থাকায় in(৪) নির্ভর করে in(৭)-এর ওপর, আর in(৭) আবার in(৪)-এর ওপর: সমীকরণগুলো চক্রাকার। সমাধানের উপায়: সব in = ∅ দিয়ে শুরু করে বারবার হিসাব, যতক্ষণ না কিছু বদলায়।

1total = 02tax = 153i = 04while i < n:5    price = read(i)6    total = total + price7    i = i + 18print(total)
হিসাবের অবস্থা
লাইন
out
in
  1. শুরু. সব in আর out ফাঁকা set ∅, অর্থাৎ lattice-এর সবচেয়ে নিচের উপাদান। Backward analysis, তাই প্রতিটি round-এ লাইন ৮ থেকে ১-এর দিকে যাওয়া হয়।
  2. লাইন ৮. এরপর কিছু নেই, out = ∅. লাইনটি total পড়ে, তাই in(৮) = {total}.
  3. লাইন ৭. পরের লাইন ৪, যার in এখনো ∅. in(৭) = {i} ∪ (∅ − {i}) = {i}. এই মান অসম্পূর্ণ; loop-এর পথটি পরের round-এ ধরা পড়বে।
  4. লাইন ৬. out(৬) = in(৭) = {i}. in(৬) = {total, price} ∪ ({i} − {total}) = {i, price, total}.
  5. লাইন ৫. out(৫) = {i, price, total}. লাইনটি price লেখে, তাই সেটি বাদ যায়, আর i পড়ে: in(৫) = {i} ∪ {i, total} = {i, total}.
  6. লাইন ৪. দুটি উত্তরসূরি, ৫ আর ৮: out(৪) = {i, total} ∪ {total} = {i, total}. শর্ত i আর n পড়ে, তাই in(৪) = {i, n, total}.
  7. লাইন ৩, ২, ১. in(৩) = in(৪) − {i} = {n, total}; in(২) = {n, total}; in(১) = {n}. লাইন ২ tax লেখে, কিন্তু out(২) = {n, total}-এ tax নেই: এই assignment-এর মান কেউ কখনো পড়ে না, এটি dead store.
  8. Round ২. এবার লাইন ৭-এর out = in(৪) = {i, n, total}, তাই in(৭) = {i, n, total}; তার প্রভাবে in(৬) = {i, n, price, total} আর in(৫) = {i, n, total}. লাইন ৪ বদলায় না।
  9. Round ৩. কোনো set বদলায় না, অর্থাৎ সমীকরণগুলোর একটি সমাধান, একটি fixpoint, পাওয়া গেছে। নিচের code ঠিক এই তিন round ছাপে।

এই হিসাবের পেছনের গাণিতিক কাঠামো তিন টুকরো। প্রথম, তথ্যের একটি partial order: variable-এর set-গুলো ⊆ দিয়ে সাজানো। দ্বিতীয়, দুটি তথ্য মেলানোর নিয়ম, এখানে ∪. তৃতীয়, প্রতিটি লাইনের একটি transfer function, যেমন fℓ(X) = use(ℓ) ∪ (X − def(ℓ)). ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৫৬-এ partial order আর lattice বিস্তারিত আছে; এখানে যা লাগবে, শুধু সেটুকু।

সংজ্ঞা ২.১ (Lattice, উচ্চতা, monotone function)
  • একটি lattice (L, ⊑) হলো একটি partial order, যেখানে প্রতিটি জোড়া a, b-এর একটি সবচেয়ে ছোট ঊর্ধ্বসীমা a ⊔ b (join) আর সবচেয়ে বড় নিম্নসীমা a ⊓ b (meet) আছে। সবচেয়ে নিচের উপাদান ⊥ (“কোনো তথ্য এখনো নেই”), সবচেয়ে ওপরের ⊤ (“কিছুই নিশ্চিত নয়”)।
  • L-এর উচ্চতা h হলো x0 ⊏ x1 ⊏ … ⊏ xh ধরনের সবচেয়ে লম্বা কঠোরভাবে বাড়তে-থাকা শিকলের ধাপ-সংখ্যা। V-টি variable-এর সব subset নিয়ে (P(V), ⊆)-এর উচ্চতা |V|.
  • f: L → L monotone, যদি x ⊑ y হলে f(x) ⊑ f(y). অর্থাৎ বেশি তথ্য ঢোকালে বেশি (বা সমান) তথ্য বের হয়। x = f(x) হলে x একটি fixpoint.

পুরো program-এর জন্য সব লাইনের in-set একসঙ্গে একটি vector, আর সব সমীকরণ একসঙ্গে একটি function F: LN → LN, যেখানে N লাইনের সংখ্যা। এই কাঠামোকে monotone framework বলা হয়; Gary Kildall ১৯৭৩ সালে এবং Kam আর Ullman ১৯৭৭ সালে এর ভিত্তি দেন বলে পরিচিত।

উপপাদ্য ২.২ (সবচেয়ে ছোট fixpoint আর থামা)

L-এর উচ্চতা h সসীম আর F monotone হলে ধারা ⊥, F(⊥), F(F(⊥)), … বড়জোর N·h ধাপে স্থির হয়, আর যে মানে স্থির হয়, সেটি F-এর সবচেয়ে ছোট fixpoint.

প্রমাণ: লিখুন x0 = ⊥ আর xk+1 = F(xk).

  1. x0 ⊑ x1, কারণ ⊥ সবকিছুর নিচে। যদি xk ⊑ xk+1, তবে monotone-তার জন্য F(xk) ⊑ F(xk+1), অর্থাৎ xk+1 ⊑ xk+2. তাই ধারাটি বাড়তে থাকে। — k-এর ওপর induction
  2. যতক্ষণ xk ≠ xk+1, অন্তত একটি লাইনের মান কঠোরভাবে ওপরে ওঠে। প্রতিটি লাইনের মান বড়জোর h বার উঠতে পারে, তাই বড়জোর N·h বার পরিবর্তন সম্ভব। এরপর xk = xk+1 = F(xk): একটি fixpoint. — সসীম উচ্চতা
  3. ধরুন p যেকোনো fixpoint. x0 = ⊥ ⊑ p. যদি xk ⊑ p, তবে xk+1 = F(xk) ⊑ F(p) = p. তাই প্রতিটি xk ⊑ p, পাওয়া fixpoint-ও। — আবার induction আর monotone-তা
  4. অতএব পাওয়া মানটি একটি fixpoint আর অন্য সব fixpoint-এর নিচে: সবচেয়ে ছোট fixpoint. ∎

উদাহরণে V = {total, tax, i, n, price}, তাই h = ৫ আর N = ৮; উপপাদ্য বলে বড়জোর ৪০টি পরিবর্তন, আর আসলে লাগল তিনটি round. Stepper-এ লাইনগুলো একটির পর একটি হালনাগাদ হয়েছে (round-robin); প্রমাণটি সব লাইন একসঙ্গে হালনাগাদের জন্য লেখা, তবে round-robin-ও একই সবচেয়ে ছোট fixpoint-এ পৌঁছায় বলে প্রমাণ করা যায় (এখানে প্রমাণ বাদ)। সবচেয়ে ছোট কেন চাই? Liveness-এ বড় set মানে বেশি variable-কে “হয়তো দরকার” ধরা: sound কিন্তু অকেজো। সবচেয়ে ছোট সমাধানটি সবচেয়ে নিখুঁত sound উত্তর। এই ধারণার সাধারণ রূপ Tarski-র fixpoint theorem (১৯৫৫ সালে প্রকাশিত বলে পরিচিত), যা প্রতিটি complete lattice-এ monotone function-এর সবচেয়ে ছোট fixpoint-এর অস্তিত্ব দেয়; পর্ব ২৮-এ grammar-এর nullable variable খোঁজাতেও একই ধাঁচ দেখেছেন।

prog = {  # line: (text, defs, uses, successors)
    1: ("total = 0",             {"total"}, set(),              [2]),
    2: ("tax = 15",              {"tax"},   set(),              [3]),
    3: ("i = 0",                 {"i"},     set(),              [4]),
    4: ("while i < n:",          set(),     {"i", "n"},         [5, 8]),
    5: ("  price = read(i)",     {"price"}, {"i"},              [6]),
    6: ("  total = total+price", {"total"}, {"total", "price"}, [7]),
    7: ("  i = i + 1",           {"i"},     {"i"},              [4]),
    8: ("print(total)",          set(),     {"total"},          []),
}
live_in = {n: set() for n in prog}            # start at the bottom of the lattice
live_out = {n: set() for n in prog}
fmt = lambda s: "{" + ",".join(sorted(s)) + "}"
for rnd in range(1, 10):
    changed = []
    for n in sorted(prog, reverse=True):       # backward analysis: walk upwards
        text, d, u, succ = prog[n]
        live_out[n] = set().union(*(live_in[s] for s in succ))
        new_in = u | (live_out[n] - d)         # in = use ∪ (out − def)
        if new_in != live_in[n]:
            live_in[n] = new_in; changed.append(f"{n}:{fmt(new_in)}")
    print(f"round {rnd}: " + ("  ".join(changed) if changed else "no change, fixpoint"))
    if not changed:
        break
print()
for n, (text, d, u, succ) in prog.items():
    dead = [v for v in d if v not in live_out[n]]
    note = "   <- dead store" if dead else ""
    print(f"{n} {text:22} in={fmt(live_in[n])}{note}")

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

round 1: 8:{total}  7:{i}  6:{i,price,total}  5:{i,total}  4:{i,n,total}  3:{n,total}  2:{n,total}  1:{n}
round 2: 7:{i,n,total}  6:{i,n,price,total}  5:{i,n,total}
round 3: no change, fixpoint

1 total = 0              in={n}
2 tax = 15               in={n,total}   <- dead store
3 i = 0                  in={n,total}
4 while i < n:           in={i,n,total}
5   price = read(i)      in={i,n,total}
6   total = total+price  in={i,n,price,total}
7   i = i + 1            in={i,n,total}
8 print(total)           in={total}

তিনটি round, stepper-এর সঙ্গে হুবহু মেলে। লক্ষ করুন, in(১) = {n}: function শুরুর সময় শুধু n-এর মান দরকার, total বা i-এর পুরোনো মান নয়। লাইন ২ চিহ্নিত হয়েছে dead store হিসেবে, যা একটি compiler নিরাপদে মুছতে পারে। এটি নিরাপদ কারণ liveness একটি may analysis: কোনো একটি পথেও দরকার হলে variable live, তাই “live নয়” একটি নিশ্চিত দাবি। আর যে পথ আসলে কখনো চলে না, তার জন্যও variable live থেকে যেতে পারে: এটিই এখানকার over-approximation.

Analysisদিকমেলানোপ্রশ্ন
Livenessbackward∪ (may)এই মান পরে কোনো পথে পড়া হবে কি?
Reaching definitionsforward∪ (may)কোন কোন assignment এখানে পৌঁছাতে পারে?
Available expressionsforward∩ (must)কোন হিসাব সব পথে আগেই হয়ে আছে?
Very busy expressionsbackward∩ (must)কোন হিসাব সব পথে পরে অবশ্যই হবে?

চারটিই একই উপপাদ্যে চলে, শুধু দিক আর join বদলায়। Python-এ “variable হয়তো assign হয়নি” সতর্কতাও একটি forward, must-ধাঁচের প্রশ্ন, যা অংশ ৬-এ একটি ভুল সতর্কতা দেবে।

৩ · Abstract interpretation — আসল মানের বদলে মানের ছায়া

Dataflow analysis-এ তথ্য ছিল variable-এর set. Abstract interpretation একই কাঠামো মানের ওপর খাটায়: “x কত?” না জিজ্ঞেস করে “x-এর চিহ্ন কী?” বা “x কোন range-এ?” Patrick আর Radhia Cousot ১৯৭৭ সালের একটি গবেষণাপত্রে এই তত্ত্ব lattice-এর ভাষায় দাঁড় করান বলে পরিচিত: program-এর আসল (concrete) অর্থ আর একটি সরল (abstract) অর্থের মধ্যে একটি গাণিতিক সেতু, যাতে abstract হিসাব সবসময় আসলটিকে ঢেকে রাখে।

সবচেয়ে সরল উদাহরণ sign domain: পাঁচটি abstract মান ⊥ (কোনো মান নেই, যেমন অগম্য কোড), − (ঋণাত্মক), 0, + (ধনাত্মক), আর ⊤ (চিহ্ন অজানা)। দুটি function জগৎ দুটিকে জোড়ে।

সংজ্ঞা ৩.১ (Abstraction, concretisation, Galois connection)
  • Abstraction α: P(ℤ) → Sign, পূর্ণসংখ্যার একটি set-কে সবচেয়ে নিখুঁত চিহ্নে নেয়: α({3, 8}) = +, α({0}) = 0, α({−1, 4}) = ⊤, α(∅) = ⊥.
  • Concretisation γ: Sign → P(ℤ), একটি চিহ্ন যত পূর্ণসংখ্যা বোঝায়: γ(+) = {1, 2, 3, …}, γ(⊤) = ℤ, γ(⊥) = ∅.
  • (α, γ) একটি Galois connection, যদি সব S ⊆ ℤ আর সব abstract a-এর জন্য α(S) ⊑ a ⇔ S ⊆ γ(a). অর্থাৎ “S-এর abstraction a-এর নিচে” আর “a যা বোঝায় তার মধ্যে S আছে” একই কথা।

দুই জগৎ: concrete set আর sign lattice

ওপরে আসল মানের set, নিচে sign domain-এর Hasse diagram; তীর হলো α.

Abstraction from integer sets to the sign lattice Concrete: পূর্ণসংখ্যার set {−7, −2} {−1, 4} {3, 8} α α α ⊤ − 0 + ⊥ চিহ্ন অজানা কোনো মান নেই γ(+) = {1, 2, 3, …} ওপরে উঠলে তথ্য কমে, ঘের বড় হয়
ছবি ৭৮.১ — α প্রতিটি set-কে তাকে ঢেকে রাখা সবচেয়ে নিচের চিহ্নে নেয়। {−1, 4}-এ দুই চিহ্নই আছে, তাই একমাত্র ঘের ⊤: এখানেই তথ্য হারায়।

এখন একটি abstract যোগ +# বা গুণ ×# সংজ্ঞায়িত করতে হবে, আর প্রশ্ন একটিই: এটি কি sound? অর্থাৎ a আর b যে মানগুলো বোঝায়, তাদের প্রতিটি আসল যোগফল কি a +# b-এর ঘেরের ভেতরে পড়ে?

সংজ্ঞা ৩.২ (Sound abstract operation)

op# sound, যদি সব a, b-এর জন্য {x op y : x ∈ γ(a), y ∈ γ(b)} ⊆ γ(a op# b). সবচেয়ে নিখুঁত sound সংস্করণ হলো α(op(γ(a), γ(b))), যাকে best abstraction বলা হয়।

নিচের code দুটি টেবিল বানায় আর প্রতিটি ঘর −6 থেকে 6-এর জানালায় brute force দিয়ে পরীক্ষা করে। জানালা সসীম, তাই এটি প্রমাণ নয়, কিন্তু টেবিলের একটি ভুলও এতে ধরা পড়ত; সাধারণ প্রমাণ চিহ্নের নিয়ম থেকে সরাসরি আসে (দুটি ধনাত্মক সংখ্যার যোগফল ধনাত্মক, ইত্যাদি)।

def alpha(xs):                         # abstraction α: set of ints -> one sign
    s = {"-" if x < 0 else "0" if x == 0 else "+" for x in xs}
    return "⊥" if not s else s.pop() if len(s) == 1 else "⊤"
def gamma(a, window=range(-6, 7)):     # concretisation γ, cut to a window
    return {x for x in window if a == "⊤" or alpha({x}) == a}
def add(a, b):                         # abstract +
    if "⊥" in (a, b): return "⊥"
    if a == "0": return b
    if b == "0": return a
    return a if a == b else "⊤"
def mul(a, b):                         # abstract ×
    if "⊥" in (a, b): return "⊥"
    if "0" in (a, b): return "0"
    if "⊤" in (a, b): return "⊤"
    return "+" if a == b else "-"
D = ["-", "0", "+", "⊤"]
for name, f, op in (("+", add, lambda x, y: x + y), ("×", mul, lambda x, y: x * y)):
    print(f"  {name} │ " + "  ".join(D))
    for a in D:
        row = []
        for b in D:
            r = f(a, b)
            exact = alpha({op(x, y) for x in gamma(a) for y in gamma(b)})
            assert r == "⊤" or r == exact, (a, name, b)   # γ(r) covers every result
            row.append(r)
        print(f"  {a} │ " + "  ".join(row))
    print()
neg = {"-": "+", "0": "0", "+": "-", "⊤": "⊤", "⊥": "⊥"}
x = "+"
print("y = x - x with x positive:")
print("  sign analysis says", add(x, neg[x]))
print("  concrete results  ", sorted({v - v for v in gamma(x)}))

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

  + │ -  0  +  ⊤
  - │ -  -  ⊤  ⊤
  0 │ -  0  +  ⊤
  + │ ⊤  +  +  ⊤
  ⊤ │ ⊤  ⊤  ⊤  ⊤

  × │ -  0  +  ⊤
  - │ +  0  -  ⊤
  0 │ 0  0  0  0
  + │ -  0  +  ⊤
  ⊤ │ ⊤  0  ⊤  ⊤

y = x - x with x positive:
  sign analysis says ⊤
  concrete results   [0]

কোনো assert ভাঙেনি, তাই দুটি টেবিল জানালার ভেতরে sound. দুটি ঘর লক্ষ করুন। (+) + (−) = ⊤: একটি ধনাত্মক আর একটি ঋণাত্মক সংখ্যার যোগফলের চিহ্ন সত্যিই যেকোনো হতে পারে, তাই এটি sign domain-এ সবচেয়ে ভালো উত্তর। কিন্তু শেষ পরীক্ষায় y = x − x: প্রতিটি আসল মান 0, অথচ analysis বলে ⊤. কারণ abstract জগতে দুটি x-এর মধ্যের সম্পর্ক (“একই সংখ্যা”) হারিয়ে গেছে; analyzer শুধু দেখে “একটি ধনাত্মক থেকে একটি ধনাত্মক বিয়োগ”। প্রতিটি operation আলাদাভাবে best হলেও তাদের যোগফল best নয়। Abstract interpretation-এর বেশিরভাগ ভুল সতর্কতা ঠিক এই পথে আসে। আর 0 × ⊤ = 0 ঘরটি দেখায়, অজানা মান থেকেও কখনো নিশ্চিত তথ্য পাওয়া যায়।

পাঁচ উপাদানের sign domain-এ “x ≥ 0” লেখার উপায় নেই; {0, 5} ধরলে উত্তর ⊤. উপাদান বাড়িয়ে আট উপাদানের lattice বানানো যায়: {−, 0, +}-এর প্রতিটি subset একটি abstract মান, যেমন ≥0 = {0, +}. নিচের JavaScript এই lattice-এর স্তর, join টেবিল আর একটি বাড়তে-থাকা শিকল দেখায়, আর ৫১২টি triple পরীক্ষা করে নিশ্চিত হয় যে set-এর union-ই সবচেয়ে ছোট ঊর্ধ্বসীমা।

// Sign lattice as subsets of {neg, zero, pos}: bit 1 = neg, 2 = zero, 4 = pos
const NAME = { 0: "⊥", 1: "−", 2: "0", 4: "+", 3: "≤0", 5: "≠0", 6: "≥0", 7: "⊤" };
const ELS = [0, 1, 2, 4, 3, 5, 6, 7];
const size = x => (x & 1) + ((x >> 1) & 1) + ((x >> 2) & 1);
const pad = s => s.padEnd(3);

console.log("Hasse diagram, level by level (bottom first):");
for (let h = 0; h <= 3; h++)
  console.log(`  level ${h}: ` + ELS.filter(x => size(x) === h).map(x => NAME[x]).join("  "));

console.log("\nJoin table a ⊔ b (least upper bound = set union):");
const cols = [1, 2, 4, 3, 5, 6];
console.log(("  " + pad("") + "│ " + cols.map(b => pad(NAME[b])).join("")).trimEnd());
for (const a of cols)
  console.log(("  " + pad(NAME[a]) + "│ " + cols.map(b => pad(NAME[a | b])).join("")).trimEnd());

// check: a | b is an upper bound, and below every other upper bound
let ok = true;
for (const a of ELS) for (const b of ELS) for (const c of ELS) {
  const upper = (a & ~c) === 0 && (b & ~c) === 0;
  if (upper && ((a | b) & ~c) !== 0) ok = false;
}
console.log("\nunion is the least upper bound for all 512 triples:", ok);

let acc = 0;                      // values a loop variable takes, joined one by one
for (const v of [7, 3, 0, -2, 5]) {
  const s = v < 0 ? 1 : v === 0 ? 2 : 4;
  console.log(`see ${String(v).padStart(2)}: ${pad(NAME[acc])}⊔ ${NAME[s]} = ${NAME[acc | s]}`);
  acc |= s;
}
console.log("height 3: any strictly rising chain has at most 4 elements");

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

Hasse diagram, level by level (bottom first):
  level 0: ⊥
  level 1: −  0  +
  level 2: ≤0  ≠0  ≥0
  level 3: ⊤

Join table a ⊔ b (least upper bound = set union):
     │ −  0  +  ≤0 ≠0 ≥0
  −  │ −  ≤0 ≠0 ≤0 ≠0 ⊤
  0  │ ≤0 0  ≥0 ≤0 ⊤  ≥0
  +  │ ≠0 ≥0 +  ⊤  ≠0 ≥0
  ≤0 │ ≤0 ≤0 ⊤  ≤0 ⊤  ⊤
  ≠0 │ ≠0 ⊤  ≠0 ⊤  ≠0 ⊤
  ≥0 │ ⊤  ≥0 ≥0 ⊤  ⊤  ≥0

union is the least upper bound for all 512 triples: true
see  7: ⊥  ⊔ + = +
see  3: +  ⊔ + = +
see  0: +  ⊔ 0 = ≥0
see -2: ≥0 ⊔ − = ⊤
see  5: ⊤  ⊔ + = ⊤
height 3: any strictly rising chain has at most 4 elements

আটটি উপাদান চারটি স্তরে, তাই উচ্চতা ৩: যেকোনো কঠোরভাবে বাড়তে-থাকা শিকলে বড়জোর চারটি উপাদান, যা শেষ লাইনও বলে। শেষ পাঁচ লাইন একটি loop variable-এর দেখা মানগুলো একে একে join করে: + থেকে ≥0, তারপর ⊤, তারপর আর বদলায় না। উপপাদ্য ২.২-এর থামার নিশ্চয়তা এখান থেকেই: lattice-এর উচ্চতা সসীম হলে join-এর শিকল একসময় থামতে বাধ্য। এই lattice একটি নতুন জিনিসও দেয়: ≠0, অর্থাৎ “শূন্য নয়”, যা ভাগের আগে খুব কাজের তথ্য; পরের অংশের interval domain-এ এটি প্রকাশ করা যায় না।

৪ · Interval domain আর widening — অসীম উচ্চতায় থামার কৌশল

Sign যথেষ্ট নয় যখন প্রশ্ন “array-এর index 0 থেকে 99-এর মধ্যে কি?” তখন লাগে interval domain: প্রতিটি variable-এর জন্য একটি [a, b], যেখানে a ≤ b আর a, b পূর্ণসংখ্যা বা −∞, +∞. ক্রম হলো অন্তর্ভুক্তি ([1, 3] ⊑ [0, 5]), join হলো দুটিকে ঢাকা সবচেয়ে ছোট interval ([1, 3] ⊔ [7, 9] = [1, 9], মাঝের 4–6-ও ঢুকে যায়), আর ⊥ খালি interval. যোগের নিয়ম সরল: [a, b] + [c, d] = [a + c, b + d].

সমস্যা উচ্চতায়। শিকল [0, 0] ⊏ [0, 1] ⊏ [0, 2] ⊏ … কখনো শেষ হয় না, তাই এই lattice-এর উচ্চতা অসীম, আর উপপাদ্য ২.২ খাটে না। i = 0; while i < n: i = i + 1 loop-টি n অজানা হলে সাধারণ fixpoint হিসাব প্রতিটি round-এ ঊর্ধ্বসীমা একটি করে বাড়ায়, চিরকাল। সমাধান Cousot-দের: একটি “লাফ”।

সংজ্ঞা ৪.১ (Widening আর narrowing)

একটি widening ∇ এমন operator, যাতে (ক) a ⊔ b ⊑ a ∇ b, আর (খ) যেকোনো বাড়তে-থাকা ধারা x0, x1, … থেকে y0 = x0, yk+1 = yk ∇ xk+1 ধারাটি সসীম ধাপে স্থির হয়। Interval-এর প্রচলিত widening:

[a, b] ∇ [c, d] = [ c < a হলে −∞, নইলে a ;  d > b হলে +∞, নইলে b ]

অর্থাৎ যে সীমা নড়েছে, সেটি সোজা অসীমে চলে যায়। এরপর একটি narrowing Δ ধাপ শুধু অসীম সীমাগুলো আবার এক round-এর হিসাব দিয়ে ছেঁটে আনে: [a, b] Δ [c, d] = [a = −∞ হলে c, নইলে a ; b = +∞ হলে d, নইলে b].

উপপাদ্য ৪.২ (Widening দিয়ে থামা আর sound-ness)

Loop-এর মাথায় Xk+1 = Xk ∇ F(Xk) হিসাব করলে (F monotone, X0 = loop-এ ঢোকার মান) ধারাটি সসীম ধাপে একটি X* -এ স্থির হয়, যেখানে F(X*) ⊑ X*. এমন X* loop-এর সব আসল run-এর মানকে ঢেকে রাখে।

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

  1. প্রতিটি variable-এর interval-এ দুটি সীমা। ∇-এর সংজ্ঞায় একটি সীমা হয় অপরিবর্তিত থাকে, নয় একবারে ±∞-এ যায়, আর ±∞ থেকে আর নড়তে পারে না। তাই v-টি variable থাকলে বড়জোর 2v বার কিছু বদলায়, আর তারপর Xk+1 = Xk. — থামা
  2. স্থির হলে X* = X* ∇ F(X*) ⊒ X* ⊔ F(X*) ⊒ F(X*), শর্ত (ক) থেকে। এমন X*-কে post-fixpoint বলে। — post-fixpoint
  3. আসল run-এর মানের set Ck (loop k বার ঘোরার পরে) induction-এ γ(X*)-এর ভেতরে থাকে: C0 ঢোকার মান, আর Ck ⊆ γ(X*) হলে এক ঘোরার পরে Ck+1 ⊆ γ(F(X*)) ⊆ γ(X*), কারণ transfer function-গুলো sound. ∎

দাম কোথায়? ধাপ ২-এ পাওয়া X* হয়তো সবচেয়ে ছোট fixpoint নয়, বড় একটি; ঘের দরকারের চেয়ে মোটা। Narrowing সেই দামের কিছুটা ফেরত আনে। নিচের stepper n ∈ [0, 100] ধরে loop-টি এক round এক round করে দেখায়।

1i = 02while i < n:      # n ∈ [0, 100]3    i = i + 1
loop-এর মাথায় i
ধাপ
body-তে i
হিসাব
  1. ঢোকা. লাইন ১-এর পরে i = [0, 0]. Loop-এর মাথার প্রথম অনুমান এটিই।
  2. Round ১, body. শর্ত i < n দিয়ে ঘের কাটা হয়: [0, 0]-এর সব মান 99-এর নিচে, তাই [0, 0] থাকে। i = i + 1-এর পরে [1, 1].
  3. Round ১, join আর widen. মাথায় দুটি পথ মেলে: ঢোকার [0, 0] আর body-র [1, 1], join [0, 1]. ঊর্ধ্বসীমা 0 থেকে 1-এ নড়েছে, তাই widening সেটি +∞-এ পাঠায়: [0, +∞]. widening না থাকলে এখান থেকে [0, 2], [0, 3], … করে ১০১টি round লাগত।
  4. Round ২, body আর join. শর্ত i < n, আর n বড়জোর 100, তাই body-তে i ∈ [0, 99]; যোগের পরে [1, 100]. Join: [0, 0] ⊔ [1, 100] = [0, 100].
  5. Round ২, widen. [0, +∞] ∇ [0, 100]: কোনো সীমা বাইরে নড়েনি, তাই [0, +∞] অপরিবর্তিত। ধারা স্থির, একটি post-fixpoint পাওয়া গেল। এটি sound, কিন্তু +∞ বাড়াবাড়ি।
  6. Narrowing. আরও এক round-এর হিসাব আবার [0, 100] দেয়। Δ শুধু অসীম সীমা বদলায়: [0, +∞] Δ [0, 100] = [0, 100].
  7. বের হওয়া. Loop থেকে বের হতে i ≥ n লাগে, ফল i ∈ [0, 100]. আসল run-এ বের হওয়ার সময় i = n, আর n-এর সব মান 0 থেকে 100: ঠিক একই range. এখানে analysis নিখুঁত হয়েছে। অংশ ৫-এর সত্যিকারের run এই সংখ্যাগুলোই দেয়।

নিচের ছোট code তিনটি পরিস্থিতি পাশাপাশি চালায়: widening ছাড়া, widening দিয়ে, আর n সম্পূর্ণ অজানা হলে।

INF = float("inf")
def show(v):
    return "[" + ", ".join("+∞" if x == INF else "-∞" if x == -INF else str(int(x)) for x in v) + "]"
def join(a, b):   return (min(a[0], b[0]), max(a[1], b[1]))
def widen(a, b):  return (a[0] if b[0] >= a[0] else -INF, a[1] if b[1] <= a[1] else INF)
def narrow(a, b): return (b[0] if a[0] == -INF else a[0], b[1] if a[1] == INF else a[1])

def step(head, n_hi):              # program: i = 0; while i < n: i = i + 1
    lo, hi = head[0], min(head[1], n_hi - 1)       # inside the loop i < n holds
    if lo > hi:
        return (0, 0)                              # body unreachable
    return join((0, 0), (lo + 1, hi + 1))          # entry ⊔ (after i = i + 1)

def analyse(n_hi, use_widen, cap=8):
    head, trail = (0, 0), [show((0, 0))]
    for r in range(1, cap + 1):
        new = step(head, n_hi)
        nxt = widen(head, new) if use_widen else new
        trail.append(show(nxt))
        if nxt == head:
            break
        head = nxt
    else:
        print("  " + " → ".join(trail) + f" … not stable after {cap} rounds")
        return
    print("  " + " → ".join(trail) + f"  (stable after {r} rounds)")
    if use_widen:
        print("  narrowing:", show(narrow(head, step(head, n_hi))))

print("n in [0, 100], plain Kleene iteration:"); analyse(100, False)
print("n in [0, 100], with widening:");          analyse(100, True)
print("n unknown, with widening:");              analyse(INF, True)

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

n in [0, 100], plain Kleene iteration:
  [0, 0] → [0, 1] → [0, 2] → [0, 3] → [0, 4] → [0, 5] → [0, 6] → [0, 7] → [0, 8] … not stable after 8 rounds
n in [0, 100], with widening:
  [0, 0] → [0, +∞] → [0, +∞]  (stable after 2 rounds)
  narrowing: [0, 100]
n unknown, with widening:
  [0, 0] → [0, +∞] → [0, +∞]  (stable after 2 rounds)
  narrowing: [0, +∞]

প্রথম লাইনে সাধারণ fixpoint হিসাব (Kleene iteration) প্রতি round-এ এক করে বাড়ছে; n ∈ [0, 100]-এ এটি ১০১ round-এ থামত, কিন্তু n অজানা হলে কখনো নয়। Widening দুই round-এ থামে, আর narrowing [0, 100] ফেরত আনে। n অজানা হলে narrowing-এর পরেও [0, +∞]: এটি ভুল নয়, কারণ n যত বড়, i তত বড় হতে পারে। বাস্তব tool প্রায়ই code-এর ধ্রুবকগুলোকে (যেমন 100) মধ্যবর্তী “সিঁড়ি” হিসেবে ব্যবহার করে বলে জানা যায়, যাতে লাফটি অসীমের আগে সেখানে থামে।

৫ · সত্যিকারের run ১ — নিজের interval analyzer বনাম concrete execution

Page-এর ছোট code একটি নির্দিষ্ট loop-এর জন্য লেখা। এবার একটি সাধারণ যন্ত্র: একটি ছোট while-ভাষা (assignment, যোগ, বিয়োগ, পূর্ণসংখ্যার ভাগ //, if, while, assert) আর তার জন্য দুটি interpreter, প্রায় ১৬০ লাইনে। একটি abstract: interval নিয়ে চলে, loop-এ widening আর এক ধাপ narrowing করে, ভাগের আগে ভাজক-এর interval-এ 0 থাকলে সতর্ক করে, আর assert প্রমাণ করতে না পারলে বলে। অন্যটি concrete: সাধারণ Python-এ program চালায়। তারপর input-এর পুরো range-এ প্রতিটি মান দিয়ে concrete run, আর পরীক্ষা: প্রতিটি আসল মান কি abstract ঘেরের ভেতরে (sound=True)? চারটি বাজারঘর-ধাঁচের program:

P1 count : i = 0; while i < n: i = i + 1                       (n in [0, 100])
P2 pairs : i = 0; s = 0; while i < n: s = s + 2; i = i + 1
           assert s <= 200                                      (n in [0, 100])
P3 guard : y = 0; if x != 5: y = 100 // (x - 5)                 (x in [0, 10])
P4 bug   : y = 100 // (x - 10)                                  (x in [0, 10])

সত্যিকারের run (ডেস্কটপ, uv-এর একটি project-এ Python 3.14.4, শুধু standard library; নিজের লেখা intervals.py):

~/bazarghar-toc$ uv run python intervals.py
== P1 count   input n in [0, 100]
   round 1: join [0, 1] -> widen [0, +∞]
   round 2: join [0, 100] -> widen [0, +∞]
   narrow:  i = [0, 100]
   i: abstract [0, 100]     concrete [0, 100]   sound=True
   warnings: none;  concrete failures: 0 of 101 inputs
== P2 pairs   input n in [0, 100]
   round 1: join [0, 1] -> widen [0, +∞]
   round 2: join [0, 100] -> widen [0, +∞]
   narrow:  i = [0, 100]
   i: abstract [0, 100]     concrete [0, 100]   sound=True
   s: abstract [0, +∞]      concrete [0, 200]   sound=True
   warnings: ['cannot prove s <= 200'];  concrete failures: 0 of 101 inputs
== P3 guard   input x in [0, 10]
   y: abstract [-∞, +∞]     concrete [-100, 100] sound=True
   warnings: ['possible division by zero'];  concrete failures: 0 of 11 inputs
== P4 bug   input x in [0, 10]
   y: abstract [-∞, +∞]     concrete [-100, -10] sound=True
   warnings: ['possible division by zero'];  concrete failures: 1 of 11 inputs
== P1 without widening
   round 1: join [0, 1] | round 2: join [0, 2] | ... | round 101: join [0, 100]
   rounds: 101
   n unknown: round 1000: join [0, 1000] | ... still growing after 1000 rounds

প্রতিটি সারিতে sound=True: কোনো concrete মান abstract ঘেরের বাইরে যায়নি, সব ২২৪টি input-এ। এবার চারটি ফল চার রকম শিক্ষা দেয়। P1 নিখুঁত: stepper-এর সংখ্যাই, আর concrete range হুবহু মেলে। P2-তে false positive: আসলে s = 2i, আর s সর্বোচ্চ 200, assert কখনো ভাঙে না (১০১-এর মধ্যে ০)। কিন্তু interval domain প্রতিটি variable আলাদাভাবে দেখে (non-relational); s আর i-এর সম্পর্ক রাখার জায়গা নেই, তাই s-এর জন্য শুধু [0, +∞], আর analyzer বলে “প্রমাণ করতে পারছি না”। P3-তে false positive: কোনো input-এ শূন্য দিয়ে ভাগ হয় না, তবু সতর্কতা; কারণটি নিচের stepper-এ। P4-এ true positive: x = 10-এ সত্যিই ZeroDivisionError, ১১-এর মধ্যে ১টি input. শেষ দুই লাইন উপপাদ্য ৪.২-এর পেছনের কারণ দেখায়: widening ছাড়া P1-এ ১০১ round, আর n অজানা হলে ১০০০ round পরেও থামার লক্ষণ নেই। (ভাগের ফল y-কে analyzer ইচ্ছে করে [−∞, +∞] রাখে, সরলতার জন্য।)

1x = input()        # x ∈ [0, 10]2if x != 5:3    y = 100 // (x - 5)
দুই দৃষ্টিকোণ
analyzer জানে
আসলে
রায়
  1. Input. x-এর ঘের [0, 10]; concrete জগতে ১১টি সম্ভাব্য মান।
  2. শর্ত x != 5. আসল মানের set থেকে 5 বাদ যায়: {0–4, 6–10}. কিন্তু interval একটানা হতে হয়, মাঝখানে ফুটো রাখা যায় না; এই set-কে ঢাকা সবচেয়ে ছোট interval আবার [0, 10]. এই ধাপেই তথ্য হারায়।
  3. x − 5. Interval বিয়োগ: [0 − 5, 10 − 5] = [−5, 5].
  4. ভাগের পরীক্ষা. ভাজকের ঘের [−5, 5]-এ 0 আছে, তাই sound analyzer-কে সতর্ক করতেই হবে: “possible division by zero”.
  5. Concrete. লাইন ৩-এ পৌঁছানো ১০টি input-এ x − 5 কখনো 0 নয়; ১১টি run-এ একটিও crash নেই। সতর্কতাটি false positive, আর এর উৎস domain-এর সীমা, program-এর কোনো দোষ নয়।
  6. প্রতিকার. একই শর্ত দুই ভাগে লিখলে (if x < 5 … elif x > 5 …) দুটি শাখায় ঘের [0, 4] আর [6, 10], ভাজক [−5, −1] আর [1, 5]: কোনোটিতে 0 নেই, intervals.py এই রূপে কোনো সতর্কতা দেয় না। আরেক প্রতিকার domain বদলানো, যেমন অংশ ৩-এর ≠0 উপাদান যোগ করা।

P2-এর মতো ভুল সতর্কতা কমাতে আছে relational domain, যা variable-এর মধ্যের সম্পর্ক রাখে: octagon (±x ± y ≤ c ধরনের শর্ত; Antoine Miné ২০০০-এর দশকের শুরুতে, বলে পরিচিত) আর polyhedra (যেকোনো রৈখিক অসমতা; Cousot আর Halbwachs ১৯৭৮, বলে পরিচিত)। Polyhedra-য় s = 2i ধরা যায়, assert প্রমাণ হয়; দাম হলো অনেক ধীর operation. কোনো সসীম কৌশল সব ভুল সতর্কতা মুছতে পারে না; Rice-এর theorem তা নিশ্চিত করে।

৬ · সত্যিকারের run ২ — mypy আর pyright: dataflow-এর চোখে type

পর্ব ৫৫-এ mypy একটি না-চলা লাইনে error আর Any-এর পেছনে লুকানো crash দেখিয়েছিল। এবার আরও গভীরে: আধুনিক Python type checker ভেতরে একটি dataflow analysis চালায়, যাকে type narrowing বলে। str | None ধরনের একটি variable if c is not None:-এর ভেতরে শুধু str হয়ে যায়; প্রতিটি শাখা আর মিলনবিন্দুতে type-এর একটি lattice-এ join হয়। দুটি স্বাধীন type checker নেওয়া হলো, দুটিই MIT licence: mypy (Python-এ লেখা) আর pyright (TypeScript-এ লেখা, Node.js-এ চলে)। mypy-এর ব্যবহার Python কোর্সের পর্ব ৪০-এ আছে।

class Cart:
    def __init__(self, coupon: str | None) -> None:
        self.coupon = coupon


def code_of(coupons: dict[str, str], user: str) -> str:
    c = coupons.get(user)           # inferred: str | None
    return c.upper()                # 1. no check for None


def fee(n: int) -> int:
    if n > 0:
        per = 100 // n
    if n > 0:                       # same test, so per is always set
        return per                  # 2. the two ifs are linked
    return 0


def drop(cart: Cart) -> None:
    cart.coupon = None


def pay(cart: Cart) -> str:
    if cart.coupon is not None:     # narrowed to str here
        drop(cart)                  # a call that resets it
        return cart.coupon.upper()  # 3. narrowing kept after call
    return "-"


print(fee(4), fee(0))
print(code_of({"rafi": "eid10"}, "rafi"))
try:
    print(code_of({"rafi": "eid10"}, "mina"))
except AttributeError as e:
    print("crash 1:", e)
try:
    print(pay(Cart("eid10")))
except AttributeError as e:
    print("crash 3:", e)

সত্যিকারের run (একই uv project-এ mypy 2.4.1, আর npm দিয়ে project-এর ভেতরে বসানো pyright 1.1.414, Node.js 24; দুটি tool-এর code খুঁজে দেখা হয়েছে: mypy-তে কোনো usage-reporting নেই, আর pyright-এর command-line অংশ কোনো network module লোড করে না। pyright-এর লম্বা path ছোট করে দেখানো):

~/bazarghar-toc$ uv run python -m mypy cart.py
cart.py:8: error: Item "None" of "str | None" has no attribute "upper"  [union-attr]
Found 1 error in 1 file (checked 1 source file)

~/bazarghar-toc$ uv run python -m mypy --enable-error-code possibly-undefined cart.py
cart.py:8: error: Item "None" of "str | None" has no attribute "upper"  [union-attr]
cart.py:15: error: Name "per" may be undefined  [possibly-undefined]
Found 2 errors in 1 file (checked 1 source file)

~/bazarghar-toc$ node node_modules/pyright/index.js cart.py
~/bazarghar-toc/cart.py
  ~/bazarghar-toc/cart.py:8:14 - error: "upper" is not a known attribute of "None" (reportOptionalMemberAccess)
  ~/bazarghar-toc/cart.py:15:16 - error: "per" is possibly unbound (reportPossiblyUnboundVariable)
2 errors, 0 warnings, 0 informations

~/bazarghar-toc$ uv run python cart.py
25 0
EID10
crash 1: 'NoneType' object has no attribute 'upper'
crash 3: 'NoneType' object has no attribute 'upper'

লাইন ৮, true positive: dict.get না পেলে None দেয়; দুটি tool-ই type str | None অনুমান করে সতর্ক করে, আর “mina”-র জন্য সত্যিই crash. লাইন ১৫, false positive: দুটি if-এর শর্ত একই, তাই per সবসময় assign হয়ে থাকে (fee(4) = 25, fee(0) = 0, কোনো crash নেই)। কিন্তু “সব পথে কি per assign হয়েছে?” প্রশ্নটি একটি path-insensitive dataflow analysis দিয়ে হিসাব হয়: প্রথম if-এর পরে দুটি পথ (assign হয়েছে, হয়নি) join হয়ে “হয়তো”, আর দ্বিতীয় if-এর শর্তের সঙ্গে আগের শর্তের সম্পর্ক হারিয়ে যায়। এটি অংশ ৫-এর P3-এর একই রোগ। mypy এই পরীক্ষা শুধু চাইলে চালায়, pyright নিজে থেকেই। লাইন ২৬, false negative: দুটি tool-ই চুপ, অথচ crash 3 সত্যিকারের। drop(cart) call-টি coupon-কে None করে দেয়, কিন্তু narrowing call-এর পরেও টিকে থাকে। প্রতিটি function call-এর পরে সব attribute-এর narrowing বাতিল করলে sound হতো, কিন্তু বাস্তব code-এ ভুল সতর্কতার বন্যা আসত; তাই দুটি tool-ই এখানে ইচ্ছে করে unsound বলে ব্যাখ্যা করা হয়।

দুটি tool সবসময় একমত নয়, আর তাদের পার্থক্য দেখায় যে “precision” একটি নকশার সিদ্ধান্ত। নিচের ছোট ফাইলে একই দুই tool:

def tag(c: str | None) -> str:
    ok = c is not None
    if ok:
        return c.upper()
    return "-"


def total(xs: list[int]) -> None:
    s = 0
    for x in xs:
        s = s + x
    reveal_type(s)
    acc = []
    acc.append(5)
    reveal_type(acc)

সত্যিকারের run (একই version):

~/bazarghar-toc$ uv run python -m mypy alias.py
alias.py:4: error: Item "None" of "str | None" has no attribute "upper"  [union-attr]
alias.py:12: note: Revealed type is "int"
alias.py:15: note: Revealed type is "list[int]"
Found 1 error in 1 file (checked 1 source file)

~/bazarghar-toc$ node node_modules/pyright/index.js alias.py
  ~/bazarghar-toc/alias.py:12:17 - information: Type of "s" is "int"
  ~/bazarghar-toc/alias.py:15:17 - information: Type of "acc" is "list[Unknown]"
0 errors, 0 warnings, 0 informations

লাইন ৪: শর্তটি একটি আলাদা variable ok-এ রাখা। mypy এই যোগসূত্র অনুসরণ করে না, তাই আরেকটি false positive; pyright এমন “aliased condition” অনুসরণ করে বলে তার documentation-এ বলা আছে, তাই চুপ। লাইন ১৩–১৫: খালি list-এর type কী? mypy পরের append(5) দেখে list[int] অনুমান করে; pyright এখানে list[Unknown] রাখে। দুটি tool একই ভাষার জন্য আলাদা type inference নিয়ম বেছেছে। কোনোটি “ভুল” নয়; দুটিই undecidable প্রশ্নের দুটি আলাদা decidable আনুমানিক উত্তর।

৭ · Type system — ইচ্ছে করে বানানো decidable আনুমানিক যাচাই

পর্ব ৫৫-এর অংশ ৪ বলেছিল, type checking সাধারণত decidable কারণ এটি একটি syntactic নিয়ম যাচাই, আর একটি আলাদা theorem সেই নিয়মকে আচরণের সঙ্গে জোড়ে। এখানে সেই theorem আর type inference-এর যন্ত্রটি।

উপপাদ্য ৭.১ (Type soundness, progress আর preservation রূপে)

একটি নির্দিষ্ট ভাষা আর তার type নিয়মের জন্য যদি প্রমাণ করা যায়:

  • Progress: একটি well-typed program হয় শেষ মান, নয় আরও এক ধাপ চলতে পারে (আটকে যায় না);
  • Preservation: well-typed program এক ধাপ চললে ফলও একই type-এর well-typed program,

তবে induction-এ, well-typed program কখনো “আটকে যাওয়া” অবস্থায় (যেমন সংখ্যার সঙ্গে string যোগ) পৌঁছায় না।

এই রূপটি Andrew Wright আর Matthias Felleisen ১৯৯৪ সালে জনপ্রিয় করেন বলে পরিচিত; Robin Milner-এর ১৯৭৮ সালের গবেষণাপত্রের স্লোগান “well-typed programs cannot go wrong”. লক্ষ করুন উপপাদ্যের দিক: type-check পাস মানে নিরাপদ (sound), কিন্তু নিরাপদ মানে type-check পাস নয়। Well-typed program-এর set নিরাপদ program-এর set-এর একটি decidable অংশ, ঠিক ছবি ৫৫.১-এর sound analyzer-এর মতো। Python-এর mypy বা pyright এই উপপাদ্য দাবি করে না: অংশ ৬-এর false negative তার প্রমাণ।

Type inference. Programmer type না লিখলে compiler তা বের করতে পারে কি? ML-পরিবারের ভাষায় পারে। কৌশলটি হলো প্রতিটি অজানা type-এর জন্য একটি চলক (t1, t2, …) বসানো, code থেকে সমীকরণ বের করা, আর সমীকরণগুলো unification দিয়ে সমাধান করা। twice(f, x) = f(f(x))-এর উদাহরণ:

ধাপcode থেকেসমীকরণunification-এর ফল
১f : t1, x : t2——
২f(x) : t3t1 = t2 → t3t1 := t2 → t3
৩f(f(x)) : t4t1 = t3 → t4t2 → t3 = t3 → t4, তাই t2 := t3, t3 := t4
৪twicet1 → t2 → t4(α → α) → α → α

ফলে twice যেকোনো type α-এর জন্য কাজ করে, যদি f একটি α থেকে α-এ নেওয়া function হয়: twice(len, "BG-0042") অচল, কারণ len string থেকে int-এ নেয়। একটি ছোট Python unifier দিয়ে এই ফল যাচাই করা হয়েছে। পুরো পদ্ধতিটি Hindley–Milner নামে পরিচিত (Roger Hindley ১৯৬৯, Robin Milner ১৯৭৮, পূর্ণাঙ্গ প্রমাণ Luis Damas-এর সঙ্গে ১৯৮২ সালে বলে জানা যায়)। এটি decidable আর প্রতিটি typable program-এর জন্য সবচেয়ে সাধারণ type দেয়। চমকপ্রদ তথ্য: সবচেয়ে খারাপ ক্ষেত্রে এর সময় সূচকীয়, কারণ let দিয়ে বারবার নকল করা function-এর type-এর আকার সূচকীয় হারে বাড়তে পারে (Mairson এবং Kfoury, Tiuryn আর Urzyczyn ১৯৯০ সালের দিকে এই নিম্নসীমা দেখান বলে পরিচিত); বাস্তব program-এ এমন হয় না বললেই চলে।

Type system আরও শক্তিশালী করলে decidability হারানোর ঝুঁকি আসে; পর্ব ৫৫-এর টেবিলে System F আর Java generics-এর উদাহরণ দেখেছেন। অন্যদিকে Python আর TypeScript-এর মতো ভাষা gradual typing নেয়: যেখানে type নেই বা Any, সেখানে checker চুপ থাকে। Jeremy Siek আর Walid Taha ২০০৬ সালে এই ধারণাটিকে এই নামে আনুষ্ঠানিক রূপ দেন বলে পরিচিত। এটি sound-ness ছেড়ে ব্যবহারযোগ্যতা কেনার আরেকটি উদাহরণ।

৮ · Symbolic execution, SMT আর testing বনাম verification

Abstract interpretation মান “মোটা” করে; symbolic execution উল্টো পথে যায়: input-কে একটি প্রতীক ধরে প্রতিটি পথ আলাদাভাবে অনুসরণ করে, আর প্রতিটি পথের শর্ত একটি সূত্রে জমায়। James King ১৯৭৬ সালে এই ধারণা নিয়ে লেখেন বলে পরিচিত। বাজারঘরের একটি কৃত্রিম bug ধরুন:

def apply(code: int) -> int:
    if 3 * code + 7 == 52:
        return 100 // (code - 15)    # crash when code == 15
    return code

Input-কে প্রতীক c ধরলে দুটি পথ: প্রথমটির path condition 3c + 7 = 52, দ্বিতীয়টির 3c + 7 ≠ 52. প্রথম পথে ভাগের আগে প্রশ্ন: “3c + 7 = 52 আর c − 15 = 0 একসঙ্গে সত্য হতে পারে কি?” এটি একটি SMT solver-এর প্রশ্ন, আর উত্তর: হ্যাঁ, c = 15. এলোমেলো testing-এ ৩২-bit পূর্ণসংখ্যার মধ্যে ঠিক এই একটি মান খুঁজে পাওয়া কার্যত অসম্ভব; symbolic execution সরাসরি crash-এর input দেয়, আর সেই input দিয়ে চালালে crash সত্যিকারের। SAT আর SMT solver কীভাবে কাজ করে, তা ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৭৭ আর এই কোর্সের পর্ব ৭৩-এ আছে।

তবে সীমা এখানেও। n-টি পরপর if থাকলে পথ 2n-টি (path explosion), আর অজানা সংখ্যক বার ঘোরা loop-এ পথ অসীম; তাই tool loop-কে k বার পর্যন্ত খোলে, যা bounded এবং ফলে unsound. তার ওপর SMT নিজেও কিছু তত্ত্বে undecidable: পূর্ণসংখ্যার ওপর অরৈখিক (গুণ-সহ) সমীকরণ মানে Hilbert-এর দশম সমস্যা (পর্ব ৫৫), তাই solver সেখানে কখনো “unknown” বলে। বাস্তবে symbolic আর concrete run মেশানো হয় (concolic testing; DART ২০০৫ আর KLEE ২০০৮ এই ধারার পরিচিত গবেষণা-tool বলে জানা যায়)।

Edsger Dijkstra-র একটি বহুল উদ্ধৃত কথা (১৯৬৯–৭০ সালের লেখায় বলে পরিচিত): “Program testing দিয়ে bug-এর উপস্থিতি দেখানো যায়, অনুপস্থিতি কখনো নয়।” এই পর্বের ভাষায়: testing complete, sound নয়; verification sound হতে পারে, কিন্তু থামা বা complete-ness-এর দাম দিয়ে। তাই বাস্তবে দুটিই চলে, স্তরে স্তরে।

Tool-এর পরিবারকখনস্বভাবউদাহরণ
Linterনা চালিয়েনকশার নিয়ম, অনেকটা syntactic; sound-ness দাবি নেইruff, pylint
Type checkerনা চালিয়েdataflow + type lattice; আংশিক soundmypy, pyright
Abstract interpreterনা চালিয়েsound, ভুল সতর্কতা আসেintervals.py-এর মতো, শিল্পে বড় সংস্করণ
Sanitizerচালানোর সময়শুধু আসলে-ঘটা ভুল ধরে: complete-ধাঁচেরAddressSanitizer, UBSan
Fuzzer, property-based testingচালানোর সময়অনেক input বানায়; পাওয়া bug আসলHypothesis, coverage-guided fuzzer
Symbolic execution, model checkingপথ বা অবস্থা খুঁজেসীমার মধ্যে নিখুঁত, সীমার বাইরে চুপKLEE-ধাঁচের tool; পর্ব ৭৭

এদের ব্যবহারিক দিক Software testing কোর্সের পর্ব ০৬ (static analysis) আর পর্ব ৫৮ (property-based testing)-এ আছে। Model checking, অর্থাৎ সসীম অবস্থার ব্যবস্থায় সব reachable অবস্থা খোঁজা, পর্ব ৭৭ (Model checking — Büchi automaton আর temporal logic)-এর বিষয়। আর একটি ভাষার compiler কীভাবে এই analysis-গুলো ধাপে ধাপে বসায়, তা ভবিষ্যতের “Programming Languages ও Compilers” কোর্সে বিস্তারিত আসবে।

সাধারণ ভুল ধারণা: “Analyzer কোনো সতর্কতা দেয়নি, তাই program নিরাপদ।” এটি সত্য শুধু তখন, যখন analyzer সেই নির্দিষ্ট ধরনের ভুলের জন্য sound বলে প্রমাণিত, আর তার অনুমানগুলো (যেমন “কোনো Any নেই”) আপনার code-এ খাটে। অংশ ৬-এর লাইন ২৬ দেখিয়েছে, জনপ্রিয় type checker-ও চুপ থেকে crash মিস করে। উল্টো ভুলটিও আছে: “সতর্কতা এসেছে, তাই bug আছে।” P3 আর লাইন ১৫ দেখিয়েছে, sound tool-এর সতর্কতা প্রায়ই domain-এর সীমা।

আরও গভীরে: Abstract interpretation-এর একটি গভীর ফল: প্রতিটি sound analysis-কে একটি abstract domain আর Galois connection হিসেবে লেখা যায়, তাই dataflow analysis, type inference এমনকি model checking-ও একই কাঠামোর বিশেষ রূপ বলে Cousot-রা দেখান। “Complete” abstract domain নিয়েও গবেষণা আছে: কোন domain-এ কোনো operation-এর best abstraction-ও নিখুঁত হয় (অনুশীলন ১-এর parity domain-এ যোগ আর গুণ নিখুঁত)। আর Rice-এর theorem সব প্রশ্ন বন্ধ করে না: termination-এর মতো undecidable প্রশ্নেও ranking function খুঁজে অনেক বাস্তব loop-এর থামা প্রমাণ করা যায়, শুধু সবগুলোর নয়।

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

  • Liveness analysis forward না backward, may না must? Backward আর may: in = use ∪ (out − def), out = উত্তরসূরিদের in-এর union.
  • Dataflow analysis থামে কেন? Lattice-এর উচ্চতা সসীম আর transfer function monotone, তাই ⊥ থেকে বাড়তে-থাকা ধারা বড়জোর N·h ধাপে সবচেয়ে ছোট fixpoint-এ পৌঁছায়।
  • Widening কেন লাগে? Interval lattice-এর উচ্চতা অসীম; [a, b] ∇ [c, d] নড়া সীমাকে ±∞-এ পাঠিয়ে থামা নিশ্চিত করে, বিনিময়ে নিখুঁততা হারায়, যা narrowing আংশিক ফেরত আনে।
  • Sound analysis-এর false positive কোথা থেকে আসে? Abstraction-এ তথ্য হারানো থেকে: পথের join, variable-এর সম্পর্ক না রাখা (x − x), interval-এ ফুটো না থাকা।
  • Type checking decidable হলে Rice ভাঙে কি? না: type checking একটি syntactic নিয়ম যাচাই, যা নিরাপদ program-এর একটি অংশ মাত্র গ্রহণ করে; type soundness শুধু এক দিকের নিশ্চয়তা।

৯ · AI-এর যুগে program analysis

AI coding assistant নিজেই একটি analyzer: code পড়ে বলে “এখানে None আসতে পারে” বা “এই loop নিরাপদ”, কিন্তু কোনো sound-ness নিশ্চয়তা ছাড়া। তার দাবিকে একটি যাচাইযোগ্য রূপে বদলান: একটি concrete input, একটি invariant, বা একটি tool-এর আউটপুট। এই বিষয়ে কয়েকটি ভুল AI-এর উত্তরে প্রায়ই দেখা যায়।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
Liveness-কে forward analysis বলা, বা in আর out-এর সমীকরণ উল্টে লেখাঅংশ ২-এর liveness.py-তে তার সমীকরণ বসিয়ে চালান; dead store ঠিক লাইনে আসে কি না দেখুন
Widening-এর ফলকে “সবচেয়ে ছোট fixpoint” বলাWidening শুধু post-fixpoint দেয়; P1-এ narrowing-এর আগে [0, +∞] দেখুন
Abstract operation-এর টেবিলে ভুল ঘর (যেমন (−) × (−) = −)signs.py-এর মতো brute force-এ প্রতিটি ঘর concrete মানের সঙ্গে মেলান
“mypy পাস করেছে, তাই crash হবে না”Code চালিয়ে দেখুন; narrowing-এর পরে call, Any, cast খুঁজুন
Sound আর complete উল্টো অর্থে, বা তিনটিই একসঙ্গে দাবিজিজ্ঞেস করুন: কোন ভুল বাদ গেল, আর analyzer কি সবসময় থামে?
বানানো ইতিহাস বা রেফারেন্স (“Cousot ১৯৯০ সালে widening আবিষ্কার করেন”)প্রাথমিক উৎস বা Nielson–Nielson–Hankin, Sipser-এর মতো বইয়ে খুঁজুন

AI-কে কাজে লাগানোর ভালো উপায়: তাকে দিয়ে analysis-এর একটি ছোট নমুনা হাতে করানো, আর প্রতিটি সংখ্যা নিজে চালিয়ে মেলানো।

আমি গণনার তত্ত্ব শিখছি, এখন abstract interpretation আর dataflow analysis নিয়ে কাজ করছি। ১. এই program-এ interval analysis করো: x = 10; while x > 0: x = x - 3. প্রতিটি round-এ loop-এর মাথায় join আর widening-এর ফল লেখো, তারপর এক ধাপ narrowing, তারপর loop থেকে বের হওয়ার পরে x-এর interval. ২. Concrete run-এ x-এর শেষ মান কত, আর তা কি তোমার interval-এর ভেতরে? না হলে কোন ধাপে ভুল হয়েছে খুঁজে বলো। ৩. এই program-এ liveness analysis-এর in আর out set প্রতিটি লাইনের জন্য লেখো: a = 1; b = a + 2; a = 5; print(b). কোনটি dead store? ৪. কোনো সাল, নাম বা theorem নিয়ে নিশ্চিত না হলে স্পষ্ট বলো; বানানো রেফারেন্স দিও না।

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

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

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

প্র ০১Abstract interpretation কেন lattice আর fixpoint-এর ভাষায় লেখা হলো? ১৯৭০-এর দশকের একটি তাত্ত্বিক কাঠামো কীভাবে শিল্পের analyzer-এর ভিত্তি হলো?

১৯৭০-এর দশকের শুরুতে compiler optimisation-এর জন্য অনেক আলাদা আলাদা analysis ছিল: কোন variable live, কোন হিসাব আগে হয়ে আছে, কোন constant কোথায় পৌঁছায়। প্রতিটির নিজস্ব algorithm আর নিজস্ব সঠিকতার যুক্তি। Gary Kildall ১৯৭৩ সালে দেখান বলে পরিচিত যে এদের অনেকগুলো একই ধাঁচের: একটি lattice, প্রতিটি statement-এ একটি function, আর বারবার হিসাব করে fixpoint. Kam আর Ullman ১৯৭৭ সালে monotone framework-এর শর্তগুলো স্পষ্ট করেন বলে জানা যায়। অংশ ২-এর উপপাদ্য এই ঐক্যেরই ফল: একবার প্রমাণ, সব analysis-এ খাটে।

Patrick আর Radhia Cousot আরও এক ধাপ যান। তাঁদের প্রশ্ন ছিল: “এই analysis-এর ফল আসল program-এর সঙ্গে কী সম্পর্কে?” উত্তর হিসেবে তাঁরা program-এর আসল অর্থকেও একটি lattice-এর fixpoint হিসেবে লেখেন (সব সম্ভাব্য অবস্থার set), আর abstract অর্থকে আরেকটি, মাঝে α আর γ. ফলে sound-ness আর “কতটা হারাল” দুটিই গাণিতিক প্রশ্ন হয়ে যায়। Widening-ও এই কাজের অংশ বলে পরিচিত, যা অসীম উচ্চতার domain-এ, যেমন interval-এ, থামার সমস্যা মেটায়।

শিল্পে যাওয়ার পথ সহজ ছিল না। প্রথম দিকের analyzer-গুলোর ভুল সতর্কতা এত বেশি ছিল যে বড় code-এ সেগুলো কাজের ছিল না। অগ্রগতি এসেছে সূক্ষ্মতর domain (octagon, polyhedra), নির্দিষ্ট ক্ষেত্রের জন্য বানানো domain (যেমন floating-point হিসাবের জন্য), আর একটি সীমিত লক্ষ্য বেছে নেওয়া থেকে: “এই ধরনের code-এ runtime error নেই” প্রমাণ করা। বিমান, মহাকাশ বা পারমাণবিক নিয়ন্ত্রণের মতো নিরাপত্তা-সংবেদনশীল ক্ষেত্রে এমন sound analyzer ব্যবহারের কথা প্রকাশিত অভিজ্ঞতায় বর্ণিত বলে জানা যায়, যেখানে কয়েক লক্ষ লাইনের code-এ ভুল সতর্কতা প্রায় শূন্যে নামানো সম্ভব হয়েছে; কারণ code-এর ধরন সীমিত আর domain তার জন্যই বানানো।

শিক্ষাটি হলো: Rice-এর theorem সার্বিক প্রশ্ন বন্ধ করে, কিন্তু একটি নির্দিষ্ট শ্রেণির program আর একটি নির্দিষ্ট ভুলের জন্য প্রায়-নিখুঁত sound analysis সম্ভব।

মূল উপলব্ধি: Lattice আর fixpoint-এর ভাষা সব analysis-কে এক কাঠামোয় এনে sound-ness প্রমাণযোগ্য করেছে; শিল্পে সাফল্য এসেছে সাধারণ সমাধানের বদলে নির্দিষ্ট ক্ষেত্রের জন্য সূক্ষ্ম domain বানিয়ে।

প্র ০২Python আর TypeScript-এর type checker ইচ্ছে করে unsound কেন? একটি ভাষায় sound type system আনার দাম কী?

Python আর JavaScript দুটিই type ছাড়া জন্মেছে, আর তাদের কোটি কোটি লাইনের পুরোনো code আছে। পরে type যোগ করতে হলে দুটি পথ: পুরোনো code বাতিল করা, নয় ধাপে ধাপে type যোগের সুযোগ দেওয়া। দ্বিতীয় পথই gradual typing: যেখানে type নেই বা Any, সেখানে checker কিছু দাবি করে না। এখানেই প্রথম sound-ness হারায়, কারণ একটি Any মান যেকোনো typed জায়গায় ঢুকে পড়তে পারে; পর্ব ৫৫-এর json.loads উদাহরণ ঠিক তাই দেখিয়েছিল।

দ্বিতীয় কারণ এই পর্বের অংশ ৬: narrowing. প্রতিটি function call-এর পরে সব attribute-এর narrowing বাতিল করলে sound হতো, কারণ call-টি যেকোনো object বদলাতে পারে। কিন্তু তাহলে if cart.coupon is not None:-এর পরে প্রায় প্রতিটি লাইনে আবার None পরীক্ষা লাগত। Developer-রা তখন সতর্কতা উপেক্ষা করতে শিখতেন, আর tool-এর মূল্য কমত। TypeScript-এর নকশা-দলিলে “sound type system” স্পষ্টভাবে লক্ষ্য হিসেবে রাখা হয়নি বলে জানা যায়; তাঁরা ব্যবহারযোগ্যতা আর JavaScript-এর বাস্তব ধাঁচকে অগ্রাধিকার দেন।

অন্যদিকে ML বা Haskell-এর মতো ভাষা শুরু থেকেই type-সহ নকশা করা, তাই সেখানে type soundness (অংশ ৭-এর উপপাদ্য) প্রমাণ করা যায়, যদিও কিছু “পালানোর দরজা” (যেমন unsafe operation) থাকে। দাম হলো প্রকাশক্ষমতা: কিছু নির্দোষ program লিখতে ঘুরপথ নিতে হয়, যেমন P3-এর মতো শর্ত দুই ভাগে লেখা। Rust আরেকটি উদাহরণ, যেখানে memory-নিরাপত্তার একটি sound নিয়ম বজায় রাখতে borrow checker কিছু নির্দোষ program-ও বাতিল করে বলে পরিচিত, আর developer-কে সেই নিয়মে লিখতে শিখতে হয়।

কোনটি ভালো, তার সার্বিক উত্তর নেই। বাজারঘরের checkout code-এ একটি false negative-এর দাম হয়তো একটি ভুল receipt; চিকিৎসা-যন্ত্রে তা জীবন। Tool আর ভাষা বেছে নেওয়া মানে এই দামের হিসাব।

মূল উপলব্ধি: পুরোনো untyped code আর developer-এর ধৈর্য রক্ষা করতে Python ও TypeScript-এর checker ইচ্ছে করে unsound; sound type system সম্ভব, কিন্তু তার দাম কিছু নির্দোষ program বাতিল আর লেখার স্বাধীনতা কমানো।

প্র ০৩Hindley–Milner type inference decidable, অথচ সামান্য বড় type system-এ inference undecidable হয়ে যায়। কোন বৈশিষ্ট্যটি সীমা পার করায়, আর ভাষা-নকশাকারীরা কীভাবে এর সঙ্গে বাঁচেন?

Hindley–Milner-এর সাফল্যের চাবি একটি সীমাবদ্ধতা: polymorphism শুধু let-এর স্তরে। twice-এর type (α → α) → α → α-এ α সবার বাইরে, পুরো type-এর জন্য একবার বাছা হয়। একটি function-এর argument নিজে polymorphic হতে পারে না; অর্থাৎ “f-কে একই body-তে একবার int-এ আর একবার str-এ লাগাও” লেখা যায় না, যদি f একটি argument হয়। এই সীমার জন্যই সমীকরণগুলো সাধারণ first-order unification দিয়ে মেটে, যা decidable আর যার একটি সবচেয়ে সাধারণ সমাধান থাকে (Robinson-এর ১৯৬৫ সালের unification algorithm-এর ধারায়, বলে পরিচিত)।

সীমাটি তুলে দিলে, অর্থাৎ যেকোনো জায়গায় ∀ বসাতে দিলে, পাওয়া যায় System F (Girard ১৯৭২ আর Reynolds ১৯৭৪ স্বাধীনভাবে, বলে পরিচিত)। সেখানে annotation ছাড়া type inference undecidable, যা J. B. Wells ১৯৯০-এর দশকে প্রমাণ করেন বলে পরিচিত (পর্ব ৫৫-এর টেবিল)। প্রমাণটি একটি reduction: একটি undecidable unification-ধাঁচের সমস্যাকে type inference-এ রূপান্তর, ঠিক পর্ব ৫২-এর কৌশল। Polymorphic recursion (একটি function নিজেকে ভিন্ন type-এ ডাকে) inference-ও undecidable বলে জানা যায়।

ভাষা-নকশাকারীরা মাঝামাঝি পথ নেন। Haskell আর OCaml-এ HM ভিত্তি, কিন্তু বাড়তি ক্ষমতা ব্যবহার করলে programmer-কে type annotation লিখতে হয়: তখন inference-এর বদলে checking, যা অনেক সহজ। “Bidirectional type checking” নামের কৌশলে type কিছু জায়গায় ওপর থেকে নিচে নামে, কিছু জায়গায় নিচ থেকে ওপরে ওঠে, যাতে সামান্য annotation-এ অনেক কিছু অনুমান করা যায়। Python-এর checker-রাও একই ধাঁচে: function-এর signature লিখতে হয়, ভেতরের local variable-এর type অনুমান হয়; অংশ ৬-এর acc = [] দেখিয়েছে, অনুমানের নিয়ম tool ভেদে আলাদা।

আরও একটি সূক্ষ্মতা: HM decidable হলেও সবচেয়ে খারাপ ক্ষেত্রে সূচকীয় সময় নেয় বলে প্রমাণিত। তবু বাস্তবে এটি দ্রুত, কারণ সেই খারাপ program-গুলো কৃত্রিম। এটি পর্ব ৫০-এর শিক্ষার প্রতিধ্বনি: decidable মানেই ব্যবহারিক নয়, আবার সবচেয়ে খারাপ ক্ষেত্র কঠিন মানেই বাস্তবে অচল নয়।

মূল উপলব্ধি: HM-এর decidability আসে polymorphism-কে let-এর স্তরে সীমিত রাখা থেকে; সীমা তুললে inference undecidable হয়, তাই ভাষাগুলো বাড়তি ক্ষমতার জায়গায় annotation চেয়ে inference-কে checking-এ নামিয়ে আনে।

প্র ০৪Dijkstra বলেছিলেন testing bug-এর অনুপস্থিতি দেখাতে পারে না। তাহলে আধুনিক software-এ verification কতটা বাস্তব, আর testing-এর জায়গা কোথায়?

Dijkstra-র কথা যুক্তিগতভাবে নির্ভুল: সসীম সংখ্যক test অসীম input-এর সামান্য অংশ দেখে। কিন্তু তিনি যে বিকল্প চেয়েছিলেন, অর্থাৎ program-এর সঙ্গে তার সঠিকতার প্রমাণ একসঙ্গে লেখা, তা দীর্ঘদিন বড় software-এ অবাস্তব মনে হতো। গত দুই দশকে এই ছবি কিছুটা বদলেছে। seL4 নামের একটি operating system kernel-এর সঠিকতা proof assistant-এ যন্ত্রে-যাচাই করা প্রমাণে প্রতিষ্ঠিত হয় (২০০৯ সালে প্রকাশিত বলে পরিচিত), আর CompCert নামের একটি C compiler-এর অনুবাদের সঠিকতা Xavier Leroy-র নেতৃত্বে Coq-এ প্রমাণিত হয় বলে জানা যায়।

এর একটি সুন্দর পরোক্ষ প্রমাণ এসেছিল testing থেকেই। ২০১১ সালের একটি গবেষণায় (Csmith নামের একটি এলোমেলো C program জেনারেটর দিয়ে) বহুল ব্যবহৃত compiler-গুলোতে শত শত bug পাওয়া যায় বলে প্রকাশিত, কিন্তু CompCert-এর প্রমাণিত অংশে কোনো ভুল-অনুবাদের bug পাওয়া যায়নি বলে জানানো হয়; যা পাওয়া গিয়েছিল, তা প্রমাণের বাইরের অংশে। অর্থাৎ testing আর verification একে অন্যকে যাচাই করে।

তবু verification-এর দাম বিশাল: seL4-এর মতো প্রকল্পে প্রমাণ লিখতে code লেখার চেয়ে অনেক গুণ বেশি শ্রম লেগেছে বলে বর্ণিত। আর প্রমাণ শুধু ততটুকুই নিশ্চিত করে, যতটুকু specification বলে; specification-এ ভুল থাকলে প্রমাণিত program-ও ভুল কাজ করবে। Rice-এর theorem এখানে বাধা নয়, কারণ মানুষ (proof assistant-এর সাহায্যে) প্রতিটি program-এর জন্য আলাদা প্রমাণ লেখে; কোনো সার্বিক algorithm দাবি করা হয় না।

তাই বাস্তব কৌশল স্তরভিত্তিক: সবচেয়ে গুরুত্বপূর্ণ ছোট অংশে verification (যেমন একটি encryption library বা একটি kernel), বাকিতে type checker আর linter (সস্তা, আংশিক sound), তার ওপর property-based testing আর fuzzing (complete-ধাঁচের, আসল bug খোঁজে), আর চালানোর সময় sanitizer. বাজারঘরের মতো একটি দোকানের জন্য শেষ তিনটিই যথেষ্ট লাভজনক; payment-এর মতো একটি ছোট মূল অংশে হয়তো আরও কড়া যাচাই।

মূল উপলব্ধি: Verification বড় পরিসরে সম্ভব প্রমাণিত, কিন্তু দামি আর specification-নির্ভর; তাই বাস্তবে verification, sound analysis আর testing স্তরে স্তরে চলে, আর একটি অন্যটির ফাঁক ধরে।

প্র ০৫Symbolic execution-এর ধারণা ১৯৭০-এর দশকের, কিন্তু ব্যবহারিক হয়েছে অনেক পরে। কী বদলেছিল, আর এর মৌলিক সীমা কোথায়?

১৯৭৬ সালের দিকে King এবং প্রায় একই সময়ে আরও কয়েকজন গবেষক symbolic execution-এর ধারণা প্রকাশ করেন বলে পরিচিত। ধারণাটি সরল ছিল, কিন্তু প্রতিটি পথের শর্ত satisfiable কি না যাচাই করার যন্ত্র ছিল দুর্বল। SAT নিজেই NP-complete (পর্ব ৬০), আর পূর্ণসংখ্যার হিসাব-সহ শর্ত আরও কঠিন। তাই কয়েক দশক এটি মূলত একটি তাত্ত্বিক কৌশল ছিল।

পরিবর্তন এসেছে SAT solver-এর বিপ্লব থেকে। ১৯৯০-এর দশকের শেষ আর ২০০০-এর দশকের শুরুতে conflict-driven clause learning আর ভালো heuristic-এর কারণে solver-গুলো লক্ষ লক্ষ চলকের বাস্তব সূত্রও সমাধান করতে শুরু করে (পর্ব ৭৩-এ বিস্তারিত)। তার ওপর SMT solver যোগ করে পূর্ণসংখ্যা, array আর bit-vector-এর তত্ত্ব। এরপর ২০০৫ সালের DART আর ২০০৮ সালের KLEE-এর মতো গবেষণা-tool concrete আর symbolic run মিশিয়ে দেখায় যে বাস্তব program-এ এমন bug পাওয়া যায়, যা হাতে লেখা test মিস করেছিল বলে প্রকাশিত।

কিন্তু মৌলিক সীমা তিনটি, আর তিনটিই এই কোর্সের theorem থেকে আসে। প্রথম, path explosion: n-টি if-এ 2n পথ, loop-এ অসীম। তাই tool loop খোলার সীমা রাখে, যা এটিকে unsound করে; পর্ব ৫৫-এর timeout-এর মতোই। দ্বিতীয়, solver-এর undecidability: পূর্ণসংখ্যার ওপর অরৈখিক শর্ত (যেমন x · y = z) Hilbert-এর দশম সমস্যার মতো, তাই সাধারণভাবে undecidable; solver সেখানে “unknown” বলতে পারে বা সীমাহীন সময় নিতে পারে। তৃতীয়, NP-hardness: সিদ্ধান্তযোগ্য তত্ত্বেও (যেমন bit-vector) সবচেয়ে খারাপ ক্ষেত্রে সূচকীয় সময়।

তাই symbolic execution কোনো সর্বজনীন সমাধান নয়, কিন্তু অংশ ৮-এর 3 * code + 7 == 52-এর মতো “সুঁচ খোঁজা” bug-এ এটি এলোমেলো testing-এর চেয়ে অনেক কার্যকর। আধুনিক fuzzer-গুলো এজন্য প্রায়ই একটি ছোট symbolic বা solver-চালিত অংশ রাখে, যা আটকে যাওয়া শর্ত ভাঙতে সাহায্য করে।

মূল উপলব্ধি: SAT ও SMT solver-এর অগ্রগতি symbolic execution-কে ব্যবহারিক করেছে, কিন্তু path explosion, অরৈখিক পূর্ণসংখ্যার undecidability আর NP-hardness এর স্থায়ী সীমা টানে।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। liveness.py, signs.py আর widening.py-তে নিজের program বসিয়ে উত্তর যাচাইও করতে পারেন।

  1. নকশা: একটি parity domain নকশা করুন: abstract মান ⊥, E (জোড়), O (বিজোড়), ⊤. (ক) α আর γ লিখুন। (খ) abstract যোগ আর গুণের টেবিল দিন। (গ) প্রমাণ করুন যোগের টেবিল sound. (ঘ) y অজানা (⊤) হলে x = 2 × y + 1-এর parity কী আসে?

    (ক) α(S) = ⊥ যদি S খালি; E যদি S-এর সব সংখ্যা জোড়; O যদি সব বিজোড়; নইলে ⊤. γ(E) = {…, −2, 0, 2, …}, γ(O) = {…, −1, 1, 3, …}, γ(⊤) = ℤ, γ(⊥) = ∅.

    (খ) যোগ: E + E = E, O + O = E, E + O = O + E = O; ⊤ থাকলে ⊤; ⊥ থাকলে ⊥. গুণ: যেকোনো একটি E হলে E (⊤ × E-ও E, কারণ জোড় দিয়ে গুণফল সবসময় জোড়), O × O = O, বাকি ⊤-সহ ঘর ⊤.

    (গ) ধরুন x ∈ γ(a), y ∈ γ(b). a বা b ⊤ হলে ফল ⊤, আর γ(⊤) = ℤ সবকিছু ধরে। নইলে x = 2p + r, y = 2q + s, যেখানে r, s ∈ {0, 1} যথাক্রমে a, b-এর parity. x + y = 2(p + q) + (r + s), যার parity r + s-এর parity: দুটি সমান হলে জোড়, আলাদা হলে বিজোড়। টেবিল ঠিক এটিই বলে, তাই x + y ∈ γ(a +# b). ∎ এই domain-এ যোগ আর গুণ শুধু sound নয়, নিখুঁত (concrete ফল সবসময় ঠিক সেই parity, ⊤ ছাড়া); −9 থেকে 9 পর্যন্ত brute force-এ প্রতিটি ঘর মিলিয়ে দেখা হয়েছে।

    (ঘ) 2 → E; E × ⊤ = E; E + O (1 বিজোড়) = O. তাই x সবসময় বিজোড়, y না জেনেও। Sign domain এখানে কিছু বলতে পারত না (y-এর চিহ্ন অজানা হলে 2y + 1-এর চিহ্নও অজানা): প্রতিটি domain আলাদা ধরনের তথ্য রাখে।

  2. প্রমাণের ভুল খুঁজুন, তারপর সঠিক প্রমাণ দিন: একজন লিখলেন: “দাবি: widening ছাড়াই interval analysis সবসময় থামে। প্রমাণ: প্রতিটি round-এ loop-এর মাথার interval আগের চেয়ে বড় বা সমান হয় (monotone). বাড়তে-থাকা ধারা একসময় থামে, তাই analysis থামে। ∎” ভুলটি কোথায়? তারপর প্রমাণ করুন যে অংশ ৪-এর ∇ দিয়ে এক variable-এর ধারা বড়জোর তিনটি আলাদা মান নেয়।

    ভুল ধাপ: “বাড়তে-থাকা ধারা একসময় থামে।” এটি সত্য শুধু সসীম উচ্চতার lattice-এ (উপপাদ্য ২.২)। Interval lattice-এ [0, 0] ⊏ [0, 1] ⊏ [0, 2] ⊏ … একটি অসীম কঠোরভাবে বাড়তে-থাকা শিকল; n অজানা হলে i = 0; while i < n: i = i + 1-এর Kleene iteration ঠিক এই শিকল ধরে চিরকাল চলে (অংশ ৫-এর run-এ ১০০০ round পরেও থামেনি)। Monotone-তা দিক দেয়, থামার নিশ্চয়তা নয়।

    সঠিক দাবির প্রমাণ: ধরুন y0 = [a, b] আর yk+1 = yk ∇ xk+1. ∇-এর সংজ্ঞায় নিম্নসীমা হয় অপরিবর্তিত থাকে, নয় −∞ হয়; −∞ হলে আর বদলাতে পারে না, কারণ কোনো c < −∞ নেই। ঊর্ধ্বসীমার জন্যও একই কথা +∞ নিয়ে। তাই নিম্নসীমা বড়জোর একবার বদলায়, ঊর্ধ্বসীমাও বড়জোর একবার। যতবার ধারাটি নতুন মান নেয়, অন্তত একটি সীমা বদলায়; তাই নতুন মান বড়জোর দুবার, মোট আলাদা মান বড়জোর তিনটি (যেমন [0, 0], [0, +∞], [−∞, +∞])। ∎

  3. আউটপুট অনুমান: x = 10; while x > 0: x = x - 3. অংশ ৪-এর নিয়মে (widening, তারপর এক ধাপ narrowing) loop-এর মাথায় প্রতিটি round-এর join আর widen-এর ফল লিখুন। Loop থেকে বের হওয়ার পরে x-এর interval কী? Concrete run-এর সঙ্গে মেলান।

    মাথায় শুরু [10, 10]. Round ১: শর্ত x > 0 দিয়ে [10, 10], body-র পরে [7, 7]; join [10, 10] ⊔ [7, 7] = [7, 10]; নিম্নসীমা 10 থেকে 7-এ নেমেছে, তাই widen: [−∞, 10]. Round ২: শর্ত দিয়ে [1, 10], body-র পরে [−2, 7]; join [10, 10] ⊔ [−2, 7] = [−2, 10]; widen [−∞, 10] ∇ [−2, 10] = [−∞, 10], বদলায়নি, স্থির। Narrowing: [−∞, 10] Δ [−2, 10] = [−2, 10].

    বের হওয়া: শর্ত x ≤ 0 দিয়ে [−2, 10] ∩ (−∞, 0] = [−2, 0]. Concrete run: 10 → 7 → 4 → 1 → −2, শেষ মান −2, যা [−2, 0]-এর ভেতরে: sound. Interval ঘের −1 আর 0-ও রাখে, যা কখনো ঘটে না, কারণ domain “3 দিয়ে ভাগশেষ” মনে রাখে না। intervals.py-তে এই program চালিয়ে ঠিক এই সংখ্যাগুলো পাওয়া গেছে: round 1: join [7, 10] → widen [−∞, 10]; round 2: join [−2, 10]; narrow [−2, 10]; বের হওয়ার পরে [−2, 0].

  4. হিসাব — type inference: compose(f, g, x) = f(g(x))-এর type unification দিয়ে বের করুন, প্রতিটি সমীকরণ দেখিয়ে। তারপর বলুন: compose(len, str.upper, "bg") কি well-typed, আর compose(str.upper, len, "bg")?

    চলক: f : t1, g : t2, x : t3. g(x) : t4 থেকে t2 = t3 → t4. f(g(x)) : t5 থেকে t1 = t4 → t5. কোনো দ্বন্দ্ব নেই, আর কোনো চলক আরেকটিতে মেলানোর দরকার হয়নি। ফল: compose : (β → γ) → (α → β) → α → γ, যেখানে α = t3, β = t4, γ = t5.

    compose(len, str.upper, "bg"): α = str, g = str.upper : str → str তাই β = str, f = len : str → int তাই γ = int. সব মেলে: well-typed, ফল 2. compose(str.upper, len, "bg"): g = len দেয় β = int, কিন্তু f = str.upper চায় β = str: int = str unification ব্যর্থ, type error. এটি একটি true positive: চালালে সত্যিই crash হতো (int-এ upper নেই)।

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

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

ক্রমএকটি loop-যুক্ত program-এ interval analysis-এর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. Abstract domain আর α, γ বেছে নেওয়া
  2. প্রতিটি statement-এর sound transfer function লেখা
  3. Loop-এর মাথায় ঢোকার মান দিয়ে শুরু করে এক round-এর হিসাব আর join করা
  4. মাথায় widening খাটিয়ে মান স্থির না হওয়া পর্যন্ত round চালানো
  5. এক ধাপ narrowing দিয়ে অসীম সীমা ছেঁটে আনা
  6. পাওয়া invariant দিয়ে যে দাবি প্রমাণ হয় না, সেখানে সতর্কতা দেওয়া

একটি analyzer প্রতিটি program-এ থামে আর শূন্য দিয়ে ভাগের ব্যাপারে sound (কোনো আসল ভাগ-শূন্য bug মিস করে না); ভাষাটি Turing-complete. নিচের কোনটি অবশ্যই সত্য?

  • এটি কিছু আসল bug মিস করে
  • এমন analyzer বানানোই অসম্ভব
  • কোনো না কোনো নির্দোষ program-এ এটি ভুল সতর্কতা দেয়
  • যথেষ্ট সূক্ষ্ম domain নিলে এটি কখনো ভুল সতর্কতা দেবে না

Liveness analysis (কোন variable-এর মান পরে কোনো পথে পড়া হবে) সম্পর্কে কোনটি সঠিক? এখানে in = use ∪ (out − def).

  • Forward analysis, পথ মেলাতে ∩
  • Backward analysis, পথ মেলাতে ∪
  • Forward analysis, পথ মেলাতে ∪
  • Backward analysis, পথ মেলাতে ∩

Interval domain-এর প্রচলিত widening-এ [a, b] ∇ [c, d]-এ যে সীমা বাইরে নড়ে, সেটি ±∞ হয়। [0, 2] ∇ [0, 3]-এর মান কী?

  • [0, 3]
  • [−∞, +∞]
  • [2, 3]
  • [0, +∞]

পাঁচ উপাদানের sign domain-এ (⊥, −, 0, +, ⊤) x-এর চিহ্ন অজানা (⊤)। y = x × x-এর জন্য best abstract গুণ কী দেয়, আর কেন?

  • ⊤, কারণ abstract গুণ জানে না দুটি গুণক একই সংখ্যা
  • +, কারণ বর্গ সবসময় ধনাত্মক
  • ⊥, কারণ ফল নির্ণয় করা যায় না
  • 0, কারণ ⊤-এর গড় 0

Type checking সাধারণত decidable, অথচ Rice-এর theorem বলে program-এর আচরণ নিয়ে non-trivial প্রশ্ন undecidable. এই দুটি কীভাবে মেলে?

  • Typed ভাষায় Rice-এর theorem খাটে না
  • Type checker ঠিক নিরাপদ program-গুলোই গ্রহণ করে
  • Type checking গঠনের নিয়ম যাচাই করে, যা নিরাপদ program-এর একটি অংশকে গ্রহণ করে; উল্টো দিকের নিশ্চয়তা নেই
  • Type checking আসলে timeout দিয়ে থামানো হয়

Function-এর শর্ত if 3 * code + 7 == 52:-এর ভেতরে 100 // (code - 15). Symbolic execution এই crash কীভাবে খুঁজে পায়?

  • অনেক এলোমেলো code চেষ্টা করে
  • পথের শর্ত আর “ভাজক = 0” একসঙ্গে SMT solver-কে দিয়ে c = 15 বের করে
  • Interval widening দিয়ে code-এর range বের করে
  • এটি খুঁজে পায় না, কারণ symbolic execution undecidable

শব্দকোষ

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

মনে রাখুন

  1. Non-trivial semantic প্রশ্নে কোনো analyzer একসঙ্গে sound, complete আর সবসময় থামা হয় না; abstract interpretation sound আর থামা রাখে, testing complete আর থামা।
  2. Dataflow analysis = lattice + monotone transfer function + fixpoint; সসীম উচ্চতায় ⊥ থেকে হিসাব বড়জোর N·h ধাপে সবচেয়ে ছোট fixpoint দেয়। Liveness backward আর may: in = use ∪ (out − def).
  3. Abstract interpretation α আর γ দিয়ে concrete আর abstract জগৎ জোড়ে; op# sound যদি প্রতিটি আসল ফল γ(op#)-এর ভেতরে থাকে। তথ্য হারায় join-এ, সম্পর্ক না রাখায় (x − x) আর ফুটো না রাখায় (x ≠ 5).
  4. Interval lattice-এর উচ্চতা অসীম; widening নড়া সীমা ±∞-এ পাঠিয়ে থামা নিশ্চিত করে আর post-fixpoint দেয়, narrowing কিছু নিখুঁততা ফেরত আনে।
  5. mypy ও pyright-এর narrowing একটি dataflow analysis, ইচ্ছে করে আংশিক unsound; type checking একটি decidable syntactic আনুমানিক যাচাই, HM inference unification দিয়ে চলে, আর symbolic execution ও SMT পথ-ভিত্তিক bug খোঁজে কিন্তু loop-এ সীমা টানে।

পরের পর্বে: Formal language আর machine learning: RNN আর transformer কোন language শিখতে ও প্রকাশ করতে পারে, Dyck language আর parity কেন কঠিন, প্রশিক্ষিত network থেকে automaton বের করা, আর grammar দিয়ে LLM-এর output বেঁধে দেওয়া।

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

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