এই পর্বে যা শিখবেন
- Fact, rule আর query দিয়ে একটি বাস্তব হিসাব লেখা, আর একটি clause-এর declarative (যুক্তির) আর procedural (খোঁজার) দুই রকম পড়া বোঝা
- Unification-এর algorithm ধাপে ধাপে চালানো, MGU বের করা, আর occurs check কেন দরকার আর Prolog কেন সাধারণত বাদ দেয় তা ব্যাখ্যা করা
- SLD resolution-এর একটি ধাপ নিয়মে লেখা, একটি query-র search tree আঁকা, আর backtracking কোন ক্রমে উত্তর দেয় তা আগেই বলা
- প্রায় ৭০ লাইনের (দুটি ছোট block) একটি unification + backtracking engine নিজে চালানো, আর একই কৌশল generator আর closure দিয়ে অন্য ভাষায় চেনা
- Cut, negation as failure, constraint আর Datalog-এর fixpoint বুঝে AI-এর লেখা Prolog বা Datalog নিয়ম যাচাই করা
১ · Logic programming কী — নিয়ম লিখুন, উত্তর খুঁজবে ভাষা
বাজারঘরের নতুন ম্যানেজারকে আপনি দুইভাবে কাজ বোঝাতে পারেন। প্রথম উপায়: “খাতার প্রথম অর্ডার থেকে শুরু করুন; জেলা কাছের হলে মোট দেখুন; মোট ১০০০ টাকা বা বেশি হলে পাশে ‘ফ্রি ডেলিভারি’ লিখুন; তারপর পরের অর্ডারে যান।” দ্বিতীয় উপায়: “কাছের জেলার যে অর্ডারের মোট ১০০০ টাকা বা বেশি, তার ডেলিভারি ফ্রি।” প্রথমটি ধাপের তালিকা, যা পর্ব ০৭-এর imperative ধাঁচ. দ্বিতীয়টি শুধু একটি নিয়ম; কোন খাতা আগে খুলবেন, কোন ক্রমে খুঁজবেন, তা ম্যানেজার নিজে ঠিক করবেন।
অভিজ্ঞ ম্যানেজার নিয়ম শুনে প্রশ্নের উত্তর নিজে খুঁজে নেন। “৩ নম্বর অর্ডার কি ফ্রি?” “কোন কোন অর্ডার ফ্রি?” “ফ্রি অর্ডারগুলো কোন জেলার?” তিনটি আলাদা প্রশ্ন, কিন্তু নিয়ম একটিই। Logic programming কম্পিউটারকে এই ম্যানেজার বানায়: আপনি জানান কী সত্য (তথ্য আর নিয়ম), তারপর প্রশ্ন করেন; খোঁজার কৌশল ভাষার নিজের।
Term তিন রকম: constant (dhaka, 1040), logic variable (বড় হাতের অক্ষর বা _ দিয়ে শুরু: I, Total), আর compound term f(t1, …, tn), যেখানে f একটি নাম (functor) আর n তার arity, যেমন l(rice, 2, 520). Variable নেই এমন term-কে বলে ground.
একটি logic program হলো clause-এর তালিকা। Fact: H., যেমন near(dhaka). Rule: H :- B1, …, Bn., পড়ুন “B1 এবং … এবং Bn সত্য হলে H সত্য”। এই দুই রকম clause মিলে Horn clause. Query: ?- G1, …, Gk., অর্থাৎ “এমন কোনো variable-মান আছে কি, যাতে G1 … Gk সব সত্য?”
প্রতিটি rule দুইভাবে পড়া যায়। Declarative পড়া (যুক্তির): ∀I, D, S. order(I, D, S) ∧ near(D) ∧ S ≥ 1000 → free_delivery(I). Procedural পড়া (খোঁজার): “free_delivery(I) প্রমাণ করতে আগে order(I, D, S) খুঁজুন, তারপর near(D), তারপর S ≥ 1000.” Robert Kowalski ১৯৭৪ সালে Horn clause-এর এই দ্বিতীয় পড়াটি স্পষ্ট করেন, আর ১৯৭৯ সালে Communications of the ACM-এর একটি লেখার শিরোনামেই সূত্রটি দেন: Algorithm = Logic + Control. Logic অংশ (কী সত্য) লেখেন প্রোগ্রামার; control অংশ (কোন ক্রমে খোঁজা) দেয় ভাষা।
প্রধান ভাষা Prolog: ১৯৭২ সালের দিকে মার্সেইতে Alain Colmerauer আর Philippe Roussel এটি বানান, আর Kowalski-র ব্যাখ্যা এর তাত্ত্বিক ভিত্তি দেয়; ইতিহাসের সারসংক্ষেপ আছে পর্ব ০২-এ. এটি পর্ব ০৯-এর functional ধাঁচের মতোই declarative, কিন্তু ভিত্তি আলাদা: functional ভাষার ভিত্তি function আর lambda calculus, logic ভাষার ভিত্তি সম্পর্ক (relation) আর predicate logic. First-order logic-এর তত্ত্ব, entailment আর একটি সরল backward chainer আছে AI-এর ভিত্তি কোর্সের পর্ব ৪৬-এ; propositional logic-এ resolution নিয়ম আছে বিচ্ছিন্ন গণিত কোর্সের পর্ব ০৬-এ. এখানে আমরা দেখব ভাষার যন্ত্র হিসেবে: কোন algorithm, কোন ডেটা কাঠামো আর কোন আপস একটি logic ভাষাকে চালায়।
🧩 Unification
দুটি term মেলানো আর variable-এ মান বসানো; Prolog-এর একমাত্র “assignment”. অংশ ৩।
MGU, occurs check🌳 Resolution আর backtracking
লক্ষ্যকে নিয়মের দেহ দিয়ে বদলানো, আর আটকালে পিছিয়ে পরের বিকল্প। অংশ ৪–৫।
search tree, choice point✂️ নিয়ন্ত্রণ
Cut, negation as failure আর constraint: logic-এর বাইরের কিন্তু দরকারি হাতিয়ার। অংশ ৬।
! , \+ , #=🔁 Datalog
Function ছাড়া logic: সবসময় থামে, নিচ থেকে fixpoint পর্যন্ত। অংশ ৭।
program analysis-এর ভাষা২ · Fact, rule আর query — বাজারঘর Prolog-এ
মডিউল ২-এর সব পর্বে একই কাজ আলাদা paradigm-এ সমাধান করা হচ্ছে: বাজারঘরের অর্ডারের তালিকা; প্রতিটি লাইনের পরিমাণ × একক দাম যোগ করে অর্ডারের মোট, মোট ১০০০ টাকা বা বেশি হলে ১০% ছাড়, শুধু একটি জেলার অর্ডার রেখে সব যোগ। ডেটা পর্ব ০৯-এর মতোই: ঢাকা (চাল 2 × 520), রাজশাহী (ডাল 3 × 120, তেল 1 × 180), ঢাকা (চিনি 4 × 150, চা 2 × 250), ঢাকা (লবণ 5 × 40). সেখানে Python, JavaScript আর Haat-এ ঢাকার উত্তর এসেছিল 2126. Prolog-এ কোনো loop বা assignment নেই; আছে শুধু সম্পর্ক:
% bazarghar: orders as facts, totals as rules
order(1, dhaka, [l(rice, 2, 520)]).
order(2, rajshahi, [l(lentil, 3, 120), l(oil, 1, 180)]).
order(3, dhaka, [l(sugar, 4, 150), l(tea, 2, 250)]).
order(4, dhaka, [l(salt, 5, 40)]).
lines_sum([], 0).
lines_sum([l(_, Q, U) | Rest], S) :-
lines_sum(Rest, S0), S is S0 + Q * U.
discounted(T, D) :- T >= 1000, D is T - T // 10.
discounted(T, T) :- T < 1000.
order_total(Id, District, D) :-
order(Id, District, Lines), lines_sum(Lines, T), discounted(T, D).
district_sum(District, Sum) :-
findall(D, order_total(_, District, D), Ds), sum_list(Ds, Sum).পড়ার নিয়ম: ছোট হাতের নাম (dhaka, rice) constant, বড় হাতের নাম variable; :- মানে “যদি”, কমা মানে “এবং”, প্রতিটি clause শেষ হয় বিন্দুতে। [l(_, Q, U) | Rest] একটি তালিকার pattern: প্রথম লাইন l(_, Q, U) (পণ্যের নাম লাগবে না, তাই _), বাকিটা Rest. lines_sum-এর declarative পড়া: “খালি তালিকার যোগফল 0; প্রথম লাইনের Q × U আর বাকি তালিকার যোগফল S0 মিলিয়ে S.” এটি recursion, তবে কোনো variable কখনো বদলায় না: প্রতিটি S একবারই একটি মান পায়।
ফাইলটি সত্যিকারের SWI-Prolog-এ চালানো হয়েছে: SWI-Prolog-এর WebAssembly build (npm প্যাকেজ swipl-wasm 8.3.1, BSD-2-Clause লাইসেন্স; ভেতরের SWI-Prolog-এর version flag বলছে 10.1.21), Node.js 24.15.0-এর ভেতরে। একটি ছোট driver প্রতিটি query-র সব উত্তর পরপর ছাপায়:
~/haat-lp $ node run.js bazar.pl
% SWI-Prolog version flag: 100121
?- order_total(Id, dhaka, T).
Id = 1 T = 936
Id = 3 T = 990
Id = 4 T = 200
?- district_sum(dhaka, S).
S = 2126
?- district_sum(rajshahi, S).
S = 540
?- order_total(Id, D, 990).
Id = 3 D = dhaka
?- discounted(T, 936).
ERROR: error(instantiation_error,context(system:(>=)/2,_5174))
প্রথম query ঢাকার তিনটি অর্ডার আর তাদের ছাড়-পরবর্তী মোট দিয়েছে: 936, 990, 200. district_sum সেগুলো যোগ করে 2126, ঠিক পর্ব ০৯-এর Python, JavaScript আর Haat-এর উত্তর; রাজশাহীর 540-ও মেলে। চতুর্থ query সবচেয়ে মজার: order_total(Id, D, 990) উল্টো দিকের প্রশ্ন, “কোন অর্ডারের মোট 990?” এর জন্য কোনো নতুন কোড লেখা হয়নি; একই সম্পর্ক অন্য দিকে চালানো হয়েছে। Python-এর order_total(o) function শুধু সামনের দিকে চলে।
কিন্তু পঞ্চম query সতর্ক করে: discounted(T, 936), অর্থাৎ “কোন মোটের ছাড়-পরবর্তী মান 936?”, error দেয় (instantiation_error). কারণ >= আর is সম্পর্ক নয়, গণনা: তাদের ডান দিকের সব variable-এ আগে থেকেই মান থাকতে হয়। is ডান দিক হিসাব করে বাঁ দিকের সঙ্গে unify করে; = কিছুই হিসাব করে না (X = 2 + 3 দিলে X পায় term 2+3, সংখ্যা 5 নয়)। findall আর sum_list-ও খাঁটি logic-এর বাইরের হাতিয়ার: “সব উত্তর জড়ো করা” Horn clause দিয়ে লেখা যায় না। অংশ ৬-এ দেখবেন constraint দিয়ে এই সীমা কীভাবে খানিকটা পার হওয়া যায়।
Prolog-এর তালিকা, is আর // নিয়ে এক ভাষার নিয়ম অন্য ভাষায় চাপাবেন না। SWI-Prolog-এ // শূন্যের দিকে কাটে (সত্যিকারের run-এ X is -7 // 2 দিয়েছে −3), যা C আর Haat-এর /-এর মতো, কিন্তু Python-এর //-এর মতো নয় (সেখানে −4). এই পর্বের সব মোট অঋণাত্মক, তাই এখানে পার্থক্য পড়ে না।
৩ · Unification — দুটি term-কে এক করা
সরকারি অফিসে একটি ফর্ম জমা দিয়েছেন, যার কয়েকটি ঘর ফাঁকা; অফিসের খাতায় আপনার রেকর্ডে অন্য কয়েকটি ঘর ফাঁকা। কর্মকর্তা দুটি পাশাপাশি রেখে মেলান: যেখানে একটিতে লেখা আছে আর অন্যটি ফাঁকা, ফাঁকা ঘরটি পূরণ হয়; দুটিতেই লেখা থাকলে লেখা দুটি একই হতে হবে, নইলে মেলে না। Unification ঠিক এই কাজ, term-এর ওপর।
একটি substitution θ হলো variable থেকে term-এর একটি সসীম তালিকা, যেমন θ = {X/dhaka, C/60}; tθ মানে t-এর ভেতরের প্রতিটি variable-কে θ অনুযায়ী বদলানো। θ হলো s আর t-এর unifier, যদি sθ = tθ (হুবহু একই term). θ হলো most general unifier (MGU), যদি প্রতিটি unifier σ-কে θ-এর পরে আরেকটি substitution λ চাপিয়ে পাওয়া যায়: σ = θλ. সহজ কথায়, MGU যতটুকু বাঁধা দরকার, ঠিক ততটুকু বাঁধে।
উদাহরণ: hub(Y, 60) আর hub(Z, C)-এর একটি unifier {Y/gazipur, Z/gazipur, C/60}, আরেকটি {Y/Z, C/60}. দ্বিতীয়টি MGU: প্রথমটি তার ওপর {Z/gazipur} চাপিয়ে পাওয়া যায়, কিন্তু উল্টোটা যায় না। Unification-এর algorithm সমীকরণের একটি তালিকা নিয়ে কয়েকটি নিয়ম বারবার খাটায় (এই রূপে লিখেছিলেন Martelli আর Montanari, ১৯৮২; মূল ধারণা J. A. Robinson-এর ১৯৬৫ সালের resolution-এর গবেষণাপত্র থেকে)। এখানে ≐ মানে “এই দুটি term সমান করতে হবে”:
| নিয়ম | সমীকরণ | কী হয় |
|---|---|---|
| delete | t ≐ t | বাদ দেওয়া, কিছু বাঁধতে হয় না |
| decompose | f(s1, …, sn) ≐ f(t1, …, tn) | n-টি নতুন সমীকরণ si ≐ ti |
| clash | f(…) ≐ g(…), বা arity আলাদা, বা দুটি আলাদা constant | ব্যর্থ: unify হয় না |
| swap | t ≐ X (t variable নয়) | X ≐ t লেখা |
| bind | X ≐ t, আর X t-এর ভেতরে নেই | X/t যোগ; বাকি সব জায়গায় X-এর বদলে t |
| occurs check | X ≐ t, X t-এর ভেতরে আছে (t ≠ X) | ব্যর্থ, যেমন X ≐ f(X) |
নিচের stepper দুটি বাজারঘরের term unify করে: একটি চালানের নিয়ম ship(X, hub(Y, 60), Y) (“X থেকে Y-এর hub হয়ে, ভাড়া 60, Y-তে”) আর একটি প্রশ্ন ship(dhaka, hub(Z, C), gazipur). বাস্তব engine সব জায়গায় X বদলায় না; বরং binding-এর একটি খাতা θ রাখে, আর দরকার হলে বাঁধা variable-এর শিকল ধরে মান খোঁজে (walk). প্রতিটি ধাপ নিচের Python engine-এর সত্যিকারের run-এর সঙ্গে মেলানো।
1decompose: f(s…) ≐ f(t…)2bind: X ≐ t → θ-তে X/t3swap: t ≐ X → X ≐ t4walk: বাঁধা X → তার মান5শেষ: θ থেকে MGU
| এখন | |
| বাকি | |
| θ |
- Decompose. দুই দিকের functor একই (
ship), arity একই (৩)। তাই একটি বড় সমীকরণ ভেঙে তিনটি ছোট সমীকরণ, প্রতিটি argument-জোড়ার জন্য একটি। Functor বা arity না মিললে এখানেই clash. - Bind X. X একটি মুক্ত variable, ডান দিকে constant
dhaka. X-কে বাঁধা হলো: θ = {X/dhaka}. X-এর ভেতরে X নেই, তাই occurs check সহজেই পার। - আবার decompose.
hub(Y, 60) ≐ hub(Z, C): functor আর arity মেলে, তাই দুটি নতুন সমীকরণ Y ≐ Z আর 60 ≐ C বাকি তালিকার সামনে বসে। - দুটি মুক্ত variable. Y ≐ Z-এ দুই দিকই variable. একটিকে অন্যটিতে বাঁধলেই চলে: Y/Z. এখনো কেউ কোনো constant পায়নি; Y আর Z শুধু “একই” বলে চিহ্নিত।
- Swap আর bind. 60 ≐ C-এ variable ডান দিকে, তাই আগে উল্টে C ≐ 60, তারপর C/60. θ-তে এখন তিনটি binding.
- Walk করে bind. শেষ সমীকরণ Y ≐ gazipur. Y আগেই বাঁধা, Y → Z; Z মুক্ত। তাই আসলে Z ≐ gazipur, আর θ-তে Z/gazipur. Python run-এর প্রথম লাইন হুবহু এই খাতা ছাপে:
{X: 'dhaka', Y: Z, C: 60, Z: 'gazipur'}. - MGU. শিকল ধরে প্রতিটি variable-এর শেষ মান: X = dhaka, Y = gazipur, Z = gazipur, C = 60. দুই term এখন হুবহু
ship(dhaka, hub(gazipur, 60), gazipur). লক্ষ করুন Y দুবার আছে বলেই Z আর gazipur জোড়া লাগল: একই নাম মানে একই মান।
এবার algorithm-টি নিজে চালিয়ে দেখুন, ব্রাউজারের ভেতরের Python-এ (Pyodide). Atom হলো Python string, সংখ্যা int, compound term একটি tuple যার প্রথম ঘরে functor, আর variable একটি ছোট class. unify একটি নতুন dictionary ফেরত দেয়, পুরোনোটি বদলায় না; পরের অংশে backtracking-এর জন্য এটি জরুরি।
class Var: # a logic variable; atoms are str, compounds are tuples
def __init__(self, name): self.name = name
def __repr__(self): return self.name
def walk(t, s): # follow bindings X -> Y -> value
while isinstance(t, Var) and t in s: t = s[t]
return t
def occurs(v, t, s):
t = walk(t, s)
return t is v or (isinstance(t, tuple) and any(occurs(v, a, s) for a in t[1:]))
def unify(a, b, s, check=True): # returns a bigger substitution, or None
a, b = walk(a, s), walk(b, s)
if a is b or (not isinstance(a, (Var, tuple)) and a == b): return s
if isinstance(a, Var):
return None if check and occurs(a, b, s) else {**s, a: b}
if isinstance(b, Var): return unify(b, a, s, check)
if isinstance(a, tuple) and isinstance(b, tuple) and a[0] == b[0] and len(a) == len(b):
for x, y in zip(a[1:], b[1:]):
s = unify(x, y, s, check)
if s is None: return None
return s
return None # clash: other functor, arity or constant
def show(t, s, depth=0):
t = walk(t, s)
if depth > 3: return "..."
if isinstance(t, tuple): return f"{t[0]}({', '.join(show(a, s, depth + 1) for a in t[1:])})"
return str(t)
X, Y, Z, C = map(Var, "XYZC")
t1, t2 = ("ship", X, ("hub", Y, 60), Y), ("ship", "dhaka", ("hub", Z, C), "gazipur")
s = unify(t1, t2, {})
print("bindings:", s)
print("MGU:", ", ".join(f"{v} = {show(v, s)}" for v in (X, Y, Z, C)), "| both:", show(t1, s))
print("clash:", unify(("hub", "dhaka"), ("hub", "sylhet"), {}), unify(("l", X), ("l", 1, 2), {}))
print("X = f(X) with occurs check:", unify(X, ("f", X), {}))
print("without occurs check: X =", show(X, unify(X, ("f", X), {}, check=False)))আসল আউটপুট (ব্রাউজারের Python):
bindings: {X: 'dhaka', Y: Z, C: 60, Z: 'gazipur'}
MGU: X = dhaka, Y = gazipur, Z = gazipur, C = 60 | both: ship(dhaka, hub(gazipur, 60), gazipur)
clash: None None
X = f(X) with occurs check: None
without occurs check: X = f(f(f(f(...))))
প্রথম দুই লাইন stepper-এর ধাপ ৬ আর ৭: খাতায় Y → Z → gazipur শিকল, আর walk শেষে MGU. তৃতীয় লাইনে দুটি clash: আলাদা constant (dhaka বনাম sylhet) আর আলাদা arity (l/1 বনাম l/2); দুটিতেই None. শেষ দুই লাইন occurs check-এর গল্প। চালু থাকলে X ≐ f(X) ব্যর্থ, কারণ কোনো সসীম term নিজের ভেতরে নিজেকে রাখতে পারে না। বন্ধ থাকলে X বাঁধা পড়ে f(X)-এ, আর walk করলে শেষ হয় না: f(f(f(f(…)))) ছাপা হয়েছে শুধু কারণ show চার স্তরের পর থামে।
Prolog-এর = সাধারণত occurs check করে না; সত্যিকারের SWI-Prolog run-এ current_prolog_flag(occurs_check, F) দিয়েছে F = false. কারণ খরচ: প্রতিটি binding-এর আগে পুরো term ঘুরে দেখতে হয়, আর বাস্তব program-এ সমস্যাটি কদাচিৎ আসে। SWI-Prolog occurs check-সহ unify_with_occurs_check/2 দেয়, আর X = f(X)-এ একটি চক্রাকার term বানায়; সেই run দেখানো আছে AI কোর্সের পর্ব ৪৬-এ। এর দাম ভাবনার প্রশ্ন ০২-এ।
সমীকরণের যেকোনো সসীম তালিকার জন্য উপরের নিয়মগুলো (occurs check-সহ) থামে। দুই term unify হলে ফলের θ একটি MGU; না হলে algorithm clash বা occurs check-এ ব্যর্থ হয়।
প্রমাণের রূপরেখা।
- থামা: তিনটি সংখ্যা দেখুন, ক্রমানুসারে তুলনা করে: (ক) এখনো বাঁধা হয়নি এমন variable-এর সংখ্যা, (খ) সব সমীকরণের মোট আকার (symbol-সংখ্যা), (গ) ডান দিকে variable আছে এমন সমীকরণের সংখ্যা। bind (ক) কমায়, কারণ occurs check নিশ্চিত করে X আর কোথাও ফিরে আসে না। delete আর decompose (ক) না বাড়িয়ে (খ) কমায়। swap (ক) আর (খ) একই রেখে (গ) কমায়। এমন ক্রমের তিন সংখ্যা চিরকাল কমতে পারে না।
- অর্থ রক্ষা: প্রতিটি নিয়ম unifier-এর সেট বদলায় না। যেমন decompose-এ f(s̄) আর f(t̄)-কে সমান করে এমন σ ঠিক সেগুলো, যা প্রতিটি si, ti-কে সমান করে।
- Clash বা occurs check-এ ব্যর্থ হলে কোনো unifier নেই: আলাদা functor কোনো substitution-এ এক হয় না, আর X ≐ f(…X…)-এ দুই দিকের আকার কখনো সমান হয় না।
- সফল শেষে তালিকা X1 ≐ t1, …, Xk ≐ tk রূপে, যেখানে কোনো Xi কোনো tj-তে নেই; এই θ নিজেই একটি unifier, আর যেকোনো unifier σ-এর ক্ষেত্রে σ = θσ, তাই θ সবচেয়ে সাধারণ। ∎
একটি ব্যবহারিক সতর্কতা: সরল algorithm-এ term-এর আকার সূচকীয় হারে বাড়তে পারে (X1 ≐ f(X0, X0), X2 ≐ f(X1, X1), …-এ Xn-এর পূর্ণ রূপে 2n-এর কাছাকাছি পাতা)। Paterson আর Wegman (১৯৭০-এর দশকের শেষে) term-কে ভাগ করা graph হিসেবে রেখে রৈখিক সময়ের algorithm দেখান। এই একই unification পর্ব ৩৫-এ (Type inference — Hindley–Milner) type-এর ওপর চলবে: সেখানে term হলো (Int) -> α ধরনের type, আর variable হলো অজানা type.
৪ · Resolution আর backtracking — উত্তর খোঁজার যন্ত্র
Unification দুটি term মেলায়; কিন্তু query-র উত্তর খুঁজতে কোন clause কখন ব্যবহার হবে? Prolog-এর উত্তর একটি নির্দিষ্ট ধরনের resolution: লক্ষ্যের তালিকার বাঁ দিকের লক্ষ্যটি বেছে নিয়ে তাকে কোনো clause-এর মাথার সঙ্গে unify করা, তারপর লক্ষ্যটির জায়গায় সেই clause-এর দেহ বসানো। একে বলে SLD resolution (Selective Linear Definite clause resolution); পদ্ধতিটি Kowalski আর Kuehner-এর ১৯৭১ সালের SL-resolution থেকে আসে, আর “SLD” নামটি ১৯৮০-এর দশকের শুরুতে Apt ও van Emden-এর লেখায় প্রচলিত হয় বলে সাধারণত উল্লেখ করা হয়। এটি backward chaining: লক্ষ্য থেকে পেছনের দিকে তথ্যের দিকে যাওয়া।
রেখার ওপরে শর্ত, নিচে ফল। “নতুন নামে” মানে clause ব্যবহারের আগে তার সব variable-এর নাম বদলানো (Q থেকে Q_7), যাতে একই নিয়মের দুই ব্যবহারের Q গুলিয়ে না যায়। লক্ষ্যের তালিকা খালি হলে একটি উত্তর পাওয়া গেল: পথে জমা সব θ মিলিয়ে query-র variable-এর মান। প্রতিটি লক্ষ্যের জন্য একাধিক clause মিলতে পারে, তাই সব সম্ভাবনা মিলে একটি গাছ: SLD tree বা search tree. Prolog-এর control এই গাছ হাঁটার একটি নির্দিষ্ট কৌশল: clause ওপর থেকে নিচে, গভীরে আগে (depth-first). যে node-এ এখনো চেষ্টা না করা clause বাকি, সেটি একটি choice point; কোনো পথ ব্যর্থ হলে Prolog সবচেয়ে সাম্প্রতিক choice point-এ ফিরে যায়, সেখানে পরে তৈরি binding মুছে পরের clause চেষ্টা করে।
নিচের stepper-এ অর্ডারের ছাড়ের আগের মোট সরাসরি fact হিসেবে দেওয়া (1040, 540, 1100, 200), যাতে গাছটি ছোট থাকে। Program আর query (অংশ ১-এর নিয়মটি, এবার Prolog-এ):
order(1, dhaka, 1040). order(2, rajshahi, 540).
order(3, dhaka, 1100). order(4, dhaka, 200).
near(dhaka). near(gazipur).
free_delivery(I) :- order(I, D, S), near(D), S >= 1000.
?- free_delivery(I).
| লক্ষ্যের তালিকা | |
| choice point |
- প্রথম resolution. Query
free_delivery(I)rule-এর মাথার সঙ্গে unify হয় (নতুন নামে I_1, D_1, S_1). লক্ষ্যের জায়গায় এখন তিনটি লক্ষ্য, বাঁ থেকে ডানে চেষ্টা হবে। এই লক্ষ্যের জন্য clause একটিই, তাই এখানে কোনো choice point নেই। - order-এর প্রথম clause. বাঁ দিকের লক্ষ্য
order(I, D, S)প্রথম fact-এর সঙ্গে unify: I = 1, D = dhaka, S = 1040. আরও তিনটি order fact বাকি, তাই এই node একটি choice point. বাকি দুই লক্ষ্যে θ বসে:near(dhaka),1040 >= 1000. - প্রথম উত্তর।
near(dhaka)প্রথম near fact-এর সঙ্গে মেলে (দ্বিতীয় near clause বাকি থাকায় নতুন choice point). তারপর built-in তুলনা 1040 ≥ 1000 সত্য। তালিকা খালি: উত্তর I = 1. আপনি আরও উত্তর চাইলে (Prolog-এর toplevel-এ;চেপে) খোঁজা চলবে। - Backtracking. সবচেয়ে সাম্প্রতিক choice point: near-এর দ্বিতীয় clause,
near(gazipur), যাnear(dhaka)-র সঙ্গে clash. তারপর order-এ ফিরে binding মুছে দ্বিতীয় fact: I = 2, D = rajshahi.near(rajshahi)কোনো near clause-এর সঙ্গে মেলে না: শাখাটি ব্যর্থ। - দ্বিতীয় উত্তর। order-এর তৃতীয় fact: I = 3, ঢাকা, 1100. near ✓, 1100 ≥ 1000 ✓: উত্তর I = 3.
- শেষ শাখা। near-এর দ্বিতীয় clause আবার ব্যর্থ; order-এর চতুর্থ fact: I = 4, ঢাকা, 200. near ✓, কিন্তু 200 ≥ 1000 মিথ্যা। এরপর near ২ চেষ্টা করেও ব্যর্থ।
- শেষ। আর কোনো choice point নেই। দুই উত্তর, ক্রমে I = 1, তারপর I = 3; অংশ ৬-এর সত্যিকারের SWI-Prolog run-ও ঠিক এই ক্রম দেয়। সব মিলিয়ে একই নামের clause-এর মাথার সঙ্গে ১৩ বার unify চেষ্টা আর ৩টি তুলনা হয়েছে; সংখ্যাগুলো Python engine-এ trace চালিয়ে গোনা।
এবার পুরো engine. আগের block-এর Var, walk আর unify এখানে আবার ব্যবহার হয় (দুটি block একই namespace ভাগ করে, তাই আগেরটি আগে চালান)। solve একটি Python generator: প্রতিটি উত্তর yield করে থেমে থাকে, পরের উত্তর চাইলে আবার চলে। for loop-এর প্রতিটি পরের clause-ই একটি choice point, আর ব্যর্থ পথ থেকে ফেরা মানে শুধু loop-এর পরের ঘরে যাওয়া: পুরোনো θ dictionary অক্ষত থাকে বলে binding “মোছা”-র আলাদা কাজ লাগে না। Program হলো bazar.pl-এর হুবহু Python রূপ।
import itertools; uses = itertools.count(1) # Var, walk, unify come from the block above
def L(*xs): return ("[|]", xs[0], L(*xs[1:])) if xs else "[]" # Prolog list cells
OPS = {"+": int.__add__, "-": int.__sub__, "*": int.__mul__, "//": int.__floordiv__, ">=": int.__ge__, "<": int.__lt__}
def ev(t, s): # evaluate an arithmetic term (all numbers >= 0 here)
t = walk(t, s)
if isinstance(t, Var): raise ValueError(f"instantiation error: {t} is unbound")
return t if isinstance(t, int) else OPS[t[0]](ev(t[1], s), ev(t[2], s))
def builtin(g, s): return unify(g[1], ev(g[2], s), s) if g[0] == "is" else (s if ev(g, s) else None)
def rename(t, m, n): # fresh copy of a clause: Q -> Q_7
if isinstance(t, Var): return m.setdefault(t, Var(f"{t.name}_{n}"))
return (t[0], *(rename(a, m, n) for a in t[1:])) if isinstance(t, tuple) else t
def solve(goals, s): # SLD: leftmost goal, clauses top to bottom
if not goals: yield s; return
g = walk(goals[0], s)
if g[0] in ("is", ">=", "<"): # built-ins: no clauses, no choice point
if (s2 := builtin(g, s)) is not None: yield from solve(goals[1:], s2)
return
for head, body in DB: # every matching clause is a choice point
n, m = next(uses), {}
s2 = unify(g, rename(head, m, n), s)
if s2 is not None: yield from solve([rename(b, m, n) for b in body] + goals[1:], s2)
I, D, T, S, S0, Q, U, R, W, Ls = map(Var, "I D T S S0 Q U R W Ls".split())
DB = [(("order", 1, "dhaka", L(("l", "rice", 2, 520))), []),
(("order", 2, "rajshahi", L(("l", "lentil", 3, 120), ("l", "oil", 1, 180))), []),
(("order", 3, "dhaka", L(("l", "sugar", 4, 150), ("l", "tea", 2, 250))), []),
(("order", 4, "dhaka", L(("l", "salt", 5, 40))), []),
(("lines_sum", "[]", 0), []),
(("lines_sum", ("[|]", ("l", W, Q, U), R), S), [("lines_sum", R, S0), ("is", S, ("+", S0, ("*", Q, U)))]),
(("discounted", T, D), [(">=", T, 1000), ("is", D, ("-", T, ("//", T, 10)))]),
(("discounted", T, T), [("<", T, 1000)]),
(("order_total", I, D, W), [("order", I, D, Ls), ("lines_sum", Ls, T), ("discounted", T, W)])]
ts = [(walk(I, s), walk(T, s)) for s in solve([("order_total", I, "dhaka", T)], {})]
print("dhaka orders:", ts, "| findall + sum_list:", sum(t for _, t in ts))
print("which order is 990?", [(walk(I, s), walk(D, s)) for s in solve([("order_total", I, D, 990)], {})])
print("uses of clauses so far:", next(uses) - 1)আসল আউটপুট (ব্রাউজারের Python, আগের block চালানোর পরে):
dhaka orders: [(1, 936), (3, 990), (4, 200)] | findall + sum_list: 2126
which order is 990? [(3, 'dhaka')]
uses of clauses so far: 252
তিনটি উত্তরই SWI-Prolog-এর সঙ্গে হুবহু: ঢাকার তিন অর্ডার 936, 990, 200 একই ক্রমে, যোগফল 2126, আর উল্টো প্রশ্নে অর্ডার ৩, ঢাকা। দুটি স্বাধীন বাস্তবায়ন একই উত্তর দিলে তা একটি differential test; পর্ব ০৯-এর Python, JavaScript আর Haat মিলিয়ে একই 2126 এখন পাঁচটি বাস্তবায়নে। শেষ লাইন engine-এর সরলতা দেখায়: তিনটি query-তে ২৫২ বার clause নতুন নামে কপি করে unify চেষ্টা হয়েছে, কারণ প্রতিটি লক্ষ্যের জন্য ৯টি clause-এর সবগুলো দেখা হয়। বাস্তব Prolog প্রথম argument দেখে clause বাছাই করে (indexing), তাই order(3, …) খুঁজতে বাকি clause ছুঁয়েও দেখে না।
Definite clause-এর program-এর জন্য SLD resolution sound: পাওয়া প্রতিটি উত্তর program-এর যৌক্তিক ফল (logical consequence). আর complete: প্রতিটি সঠিক উত্তরের জন্য SLD tree-তে কোথাও একটি সফল শাখা আছে, লক্ষ্য বাছাইয়ের নিয়ম যা-ই হোক (ফলগুলো ১৯৭০-এর দশকের শেষ আর ১৯৮০-এর দশকের শুরুর কাজে, যেমন Clark আর Apt–van Emden-এর লেখায়, প্রতিষ্ঠিত)। কিন্তু Prolog গাছটি depth-first হাঁটে; বাঁ দিকে একটি অসীম শাখা থাকলে ডান দিকের সফল শাখায় কখনো পৌঁছায় না। তাই Prolog-এর খোঁজার কৌশল complete নয়, যদিও SLD নিজে complete. অংশ ৭-এ সত্যিকারের run-এ এই অসীম শাখা দেখবেন।
এর ব্যবহারিক মানে: Prolog-এ clause আর লক্ষ্যের ক্রম program-এর যৌক্তিক অর্থ বদলায় না, কিন্তু program থামবে কি না, কত দ্রুত চলবে, আর উত্তর কোন ক্রমে আসবে, তা বদলায়। যেমন near(D), order(I, D, S) আর order(I, D, S), near(D) একই উত্তরের সেট দেয়, কিন্তু আলাদা গাছ হাঁটে।
৫ · Backtracking অন্য ভাষায় — generator আর Haat-এর closure
উপরের Python engine-এ একটি গোপন কথা আছে: backtracking-এর পুরো ভার বহন করেছে yield from. এটি কাকতালীয় নয়। Backtracking মানে একটি করে উত্তর দেওয়া, আর পরের উত্তর চাইলে যেখানে থেমেছিল সেখান থেকে আবার চলা; ঠিক এই কাজটিই generator করে। JavaScript-এর function*-ও একই রকম। নিচের block-এ একটি ছোট ধাঁধা: ডাল 120 টাকা কেজি, তেল 180 টাকা লিটার; কোন (ডাল, তেল) পরিমাণে মোট ঠিক 1080 টাকা? Prolog-এ লিখলে হতো between(0, 9, X), between(0, 9, Y), 120*X + 180*Y =:= 1080; এখানে প্রতিটি between একটি generator, অর্থাৎ একটি choice point.
// Backtracking with generators: each "goal" yields its answers one at a time
function* between(lo, hi) { for (let i = lo; i <= hi; i++) yield i; }
let tries = 0;
function* pairs(total, maxX = 9) { // lentil 120 taka, oil 180 taka
for (const x of between(0, maxX)) // choice point 1
for (const y of between(0, 9)) { // choice point 2
tries++;
if (120 * x + 180 * y === total) yield [x, y];
}
}
console.log("all answers:", JSON.stringify([...pairs(1080)]), "tries:", tries);
tries = 0;
for (const [x, y] of pairs(1080)) { // stop after the first answer (like a cut)
console.log("first answer:", x, y, "tries:", tries);
break; // break calls the generator's return(): search ends
}
tries = 0;
console.log("1081 answers:", [...pairs(1081)].length, "tries:", tries);
// the same extra condition (x <= 6) tested late or early: same answers, different work
tries = 0;
const late = [...pairs(1080)].filter(([x]) => x <= 6);
console.log("x <= 6, tested late: ", JSON.stringify(late), "tries:", tries);
tries = 0;
console.log("x <= 6, tested early:", JSON.stringify([...pairs(1080, 6)]), "tries:", tries);আসল আউটপুট (ব্রাউজারের JavaScript):
all answers: [[0,6],[3,4],[6,2],[9,0]] tries: 100
first answer: 0 6 tries: 7
1081 answers: 0 tries: 100
x <= 6, tested late: [[0,6],[3,4],[6,2]] tries: 100
x <= 6, tested early: [[0,6],[3,4],[6,2]] tries: 70
চারটি উত্তর, আর সেগুলো আসে Prolog-এর ক্রমেই: বাইরের choice point (x) ধীরে বদলায়, ভেতরেরটি (y) দ্রুত। পুরো গাছে 10 × 10 = 100টি পাতা, তাই সব উত্তর খুঁজতে 100 চেষ্টা। প্রথম উত্তরের পরে break করলে মাত্র ৭টি চেষ্টা হয়েছে: generator অলস (lazy), পরের মান না চাইলে হিসাবই করে না, আর break generator-এর return() ডেকে খোঁজা বন্ধ করে, অনেকটা অংশ ৬-এর cut-এর মতো। 1081 টাকায় কোনো উত্তর নেই, কিন্তু সেটি জানতে পুরো 100টি পাতা দেখতে হয়েছে: “নেই” প্রমাণ করা সবচেয়ে দামি। শেষ দুই লাইন একটি পুরোনো Prolog পরামর্শ সংখ্যায় দেখায়: একই শর্ত (x ≤ 6) দেরিতে পরীক্ষা করলে 100 চেষ্টা, আগে পরীক্ষা করে গাছের ডাল ছেঁটে দিলে 70; উত্তর একই, কাজ আলাদা।
Haat-এ backtracking — generator নেই, তবু closure আছে
Haat v1-এ তালিকা নেই, generator নেই। কিন্তু function first-class, আর closure বাইরের variable by reference ধরে রাখে। এটুকুই যথেষ্ট: খোঁজার function-কে আরেকটি function পাঠিয়ে দিলেই হয়, যাকে প্রতিটি উত্তর পেলে ডাকা হবে। এই পাঠানো function-কে বলে success continuation: “বাকি হিসাবটুকু”, যা একটি উত্তর পাওয়ার পর চলবে। between প্রতিটি সংখ্যার জন্য continuation k ডাকে; k ফিরে এলে loop পরের সংখ্যায় যায়, আর সেটিই backtracking. নিচের program কোর্সের Haat reference বাস্তবায়নে সত্যিকারের run (run আর vm দুটিতেই একই আউটপুট):
// ডাল 120 টাকা, তেল 180 টাকা: ঠিক 1080 টাকার সব (ডাল, তেল) জোড়া
var tries = 0;
var found = 0;
fn between(lo: Int, hi: Int, k: (Int) -> Unit) {
var i = lo;
while i <= hi { k(i); i = i + 1; }
}
fn pair(k: (Int, Int) -> Unit) {
between(0, 9, fn(x: Int) {
between(0, 9, fn(y: Int) {
tries = tries + 1;
if 120 * x + 180 * y == 1080 { k(x, y); }
});
});
}
pair(fn(x: Int, y: Int) { found = found + 1; print(x); print(y); });
print(found);
print(tries);~/haat $ python haat.py run pairs.haat
0
6
3
4
6
2
9
0
4
100
প্রতি উত্তরে দুটি লাইন ছাপা হয়েছে (ডাল, তারপর তেল): (0, 6), (3, 4), (6, 2), (9, 0); তারপর উত্তরের সংখ্যা 4 আর চেষ্টার সংখ্যা 100, JavaScript-এর সঙ্গে হুবহু। দুই স্তরের anonymous function দুটি nested choice point; ভেতরের function বাইরের x দেখতে পায়, কারণ সে একটি closure. tries আর found বদলানো যায়, কারণ Haat-এর closure বাইরের var-কে কপি নয়, একই variable হিসেবে ধরে। প্রথম উত্তরেই থামানো (cut) Haat-এ কীভাবে লিখবেন, তা অনুশীলন ১-এ। Closure-এর বাস্তবায়ন আসবে পর্ব ১৭-এ (Closure — lexical environment ধরে রাখা function), আর থেমে আবার চলা function পর্ব ৩১-এ (Generator, coroutine আর async/await).
৬ · নিয়ন্ত্রণের হাতিয়ার — cut, negation as failure আর constraint
খাঁটি Horn clause দিয়ে অনেক কিছু লেখা যায়, কিন্তু বাস্তব Prolog-এ তিনটি অতিরিক্ত হাতিয়ার প্রায় সবখানে দেখবেন। তিনটিই logic আর control-এর সীমানায় দাঁড়িয়ে, তাই তিনটিতেই ভুলের সুযোগ বেশি। সত্যিকারের SWI-Prolog run, অংশ ৪-এর ফাইলের সঙ্গে দুটি নতুন নিয়ম যোগ করে:
first_free(I) :- order(I, D, S), near(D), S >= 1000, !.
paid_delivery(I) :- order(I, _, _), \+ free_delivery(I).
~/haat-lp $ node run.js free.pl
% SWI-Prolog version flag: 100121
?- free_delivery(I).
I = 1
I = 3
?- first_free(I).
I = 1
?- paid_delivery(I).
I = 2
I = 4
?- \+ free_delivery(I).
false.
Cut (!) একটি লক্ষ্য, যা প্রথমবার সবসময় সফল হয়, কিন্তু সাথে সাথে একটি প্রতিশ্রুতি দেয়: এই rule-এর মাথা ডাকার পর থেকে তৈরি সব choice point মুছে ফেলা। তাই first_free প্রথম ফ্রি অর্ডার I = 1 পেয়েই থামে; I = 3 আর খোঁজা হয় না। Search tree-র ভাষায়, cut গাছের ডাল কেটে দেয়। যে cut শুধু অপ্রয়োজনীয় খোঁজা বাঁচায় আর উত্তরের সেট বদলায় না, তাকে প্রচলিতভাবে “green cut” বলে; যে cut উত্তর বদলায় (যেমন এখানে, I = 3 হারিয়ে গেল), তাকে “red cut”. Red cut-ওয়ালা program-এর declarative পড়া আর সত্য নয়: clause পড়ে আর বোঝা যায় না কী উত্তর আসবে, ক্রমও জানতে হয়।
Negation as failure (\+): \+ G সফল হয় যদি G প্রমাণ করার সব চেষ্টা ব্যর্থ হয়। এটি closed-world assumption-এর ওপর দাঁড়ানো: যা প্রমাণ করা যায় না, তা মিথ্যা ধরা (Keith Clark ১৯৭৮ সালে এর যৌক্তিক অর্থ ব্যাখ্যা করেন; open আর closed world-এর পার্থক্য AI কোর্সের পর্ব ৪৬-এ)। paid_delivery ঠিক উত্তর দিয়েছে: অর্ডার ২ আর ৪. কিন্তু শেষ query-টি একটি ফাঁদ: \+ free_delivery(I)-এর উত্তর false, যদিও দুটি অর্ডার সত্যিই ফ্রি নয়। কারণ I মুক্ত অবস্থায় প্রশ্নটির মানে দাঁড়ায় “কোনো ফ্রি অর্ডারই কি নেই?”, যার উত্তর না। \+ কখনো variable-এ মান বসায় না। নিয়ম: \+-এর ভেতরের লক্ষ্য ডাকার আগে তার সব variable-এ মান থাকা চাই (paid_delivery-এ আগে order(I, _, _) I-কে বাঁধে, সেজন্যই ঠিক চলে)।
Constraint. অংশ ২-এ discounted(T, 936) error দিয়েছিল, কারণ is আর >= এক দিকের গণনা। Constraint logic programming (Jaffar আর Lassez, ১৯৮৭) এই গণনাকে সত্যিকারের সম্পর্ক বানায়: সমীকরণটি তখনই হিসাব হয় না, একটি শর্ত হিসেবে জমা থাকে, আর একটি solver সেগুলো মিলিয়ে উত্তর খোঁজে। SWI-Prolog-এর clpfd library-তে #>=, #= এমন শর্ত:
:- use_module(library(clpfd)).
cdisc(T, D) :- T #>= 1000, D #= T - T // 10.
cdisc(T, T) :- T #< 1000.
~/haat-lp $ node run.js clp.pl
% SWI-Prolog version flag: 100121
?- cdisc(1040, D).
D = 936
?- T in 0..5000, cdisc(T, 936), label([T]).
T = 1039
T = 1040
T = 936
?- T in 0..5000, cdisc(T, 900), label([T]).
T = 1000
T = 900
সামনের দিকে আগের মতোই 1040 → 936. কিন্তু এবার উল্টো প্রশ্নও চলে, আর উত্তরগুলো চমকপ্রদ: 936 টাকা ছাড়-পরবর্তী মান হয় তিনটি মোট থেকে, 1039 (1039 − 103), 1040 (1040 − 104) আর 936 (ছাড়ই নেই)। 900 আসে 1000 থেকে আর 900 থেকে। এই ধরনের অপ্রত্যাশিত উত্তর ব্যবসায়িক নিয়মের ফাঁক খুঁজতে কাজে লাগে: কাছাকাছি দুটি মোটে একই ছাড়-পরবর্তী মান, কারণ // নিচের দিকে কাটে। (label সম্ভাব্য মানগুলো একে একে বসিয়ে দেখে; তাই আগে T in 0..5000 দিয়ে সীমা দিতে হয়।)
৭ · Datalog — সবসময় থামে এমন logic, আর program analysis
বাজারঘরের ডেলিভারি ভ্যান এক hub থেকে অন্য hub-এ একমুখী রাস্তায় যায়। ঢাকার গুদাম থেকে কোন কোন hub-এ পৌঁছানো যায়? নিয়মটি দুই লাইনের: ঢাকায় পৌঁছানো যায়; X-এ পৌঁছানো গেলে আর X থেকে Y-এ রাস্তা থাকলে Y-তেও। গাজীপুর আর ময়মনসিংহের মধ্যে দুই দিকেই রাস্তা আছে, অর্থাৎ একটি চক্র (cycle); আর সিলেট থেকে ঢাকায় রাস্তা আছে, ঢাকা থেকে সিলেটে নয়।
link(dhaka, gazipur). link(dhaka, narayanganj).
link(gazipur, mymensingh). link(mymensingh, gazipur).
link(narayanganj, cumilla). link(cumilla, chattogram).
link(sylhet, dhaka).
reachable(dhaka).
reachable(Y) :- reachable(X), link(X, Y). % left recursion
:- table treach/1. % same rule, tabled
treach(dhaka).
treach(Y) :- treach(X), link(X, Y).
~/haat-lp $ node run.js hubs.pl
% SWI-Prolog version flag: 100121
?- findall(H, treach(H), Hs).
Hs = [dhaka,gazipur,narayanganj,cumilla,mymensingh,chattogram]
?- treach(sylhet).
false.
?- findnsols(9, H, reachable(H), L), !.
L = [dhaka,gazipur,narayanganj,mymensingh,cumilla,gazipur,chattogram,mymensingh,gazipur]
?- call_with_inference_limit(findall(H, reachable(H), Hs), 1000000, R).
R = inference_limit_exceeded
Prolog-এর depth-first খোঁজায় reachable দুইভাবে বিপদে পড়ে। প্রথমত, rule-এর প্রথম লক্ষ্যই আবার reachable (left recursion), আর চক্রের কারণে একই hub বারবার আসে: প্রথম ৯টি উত্তরে গাজীপুর তিনবার। দ্বিতীয়ত, উত্তরগুলো শেষ হওয়ার পরও খোঁজা থামে না; সব উত্তর জড়ো করতে চাইলে findall দশ লাখ inference-এর সীমা পেরিয়ে যায়। reachable(sylhet) জিজ্ঞেস করলে Prolog কখনো “না” বলত না। একই নিয়ম tabling-সহ (:- table) ঠিক ছয়টি hub দিয়ে থেমেছে, আর treach(sylhet)-এ সঠিক false. Tabling মানে প্রতিটি লক্ষ্যের উত্তর একটি টেবিলে জমা রাখা, আর একই লক্ষ্য আবার এলে টেবিল থেকে উত্তর নেওয়া; ধারণাটি Tamaki আর Sato-র ১৯৮৬ সালের কাজ থেকে শুরু হয়ে XSB Prolog-এ (১৯৯০-এর দশক) পরিণত রূপ পায়।
Datalog program হলো এমন Horn clause-এর তালিকা, যেখানে (১) কোনো compound term নেই, শুধু constant আর variable; (২) মাথার প্রতিটি variable দেহেও আছে (safety). Program P-এর immediate consequence operator TP একটি fact-এর সেট I নিয়ে নতুন সেট দেয়: TP(I) = { Hθ : (H :- B1, …, Bn) ∈ P, θ ground, আর প্রতিটি Biθ ∈ I }. অর্থাৎ “I-এর তথ্য থেকে এক ধাপে যা যা বের করা যায়”। এটি forward chaining-এর এক ধাপ।
Definite program P-এর সবচেয়ে ছোট model (যত কম fact সত্য ধরলে সব clause মানা হয়) ঠিক TP-এর least fixpoint: ∅ থেকে শুরু করে TP বারবার খাটালে পাওয়া সেটগুলোর মিলন, ⋃k TPk(∅). আর P Datalog হলে এই খাটানো সসীম ধাপে থামে: ধাপের সংখ্যা ≤ |BP| + 1, যেখানে BP হলো P-এর predicate আর constant দিয়ে বানানো সম্ভাব্য সব ground fact.
প্রমাণ (Datalog-এ থামার অংশ)।
- TP monotone: I ⊆ J হলে TP(I) ⊆ TP(J), কারণ I-তে দেহের সব fact থাকলে J-তেও থাকে। তাই ∅ ⊆ TP(∅) থেকে আরোহ দিয়ে I0 = ∅ ⊆ I1 ⊆ I2 ⊆ …, যেখানে Ik+1 = TP(Ik).
- কোনো compound term নেই, তাই প্রতিটি Ik ⊆ BP, আর BP সসীম: arity a-এর একটি predicate বড়জোর ca-টি fact দিতে পারে, যেখানে c constant-এর সংখ্যা।
- যতক্ষণ Ik+1 ≠ Ik, ততক্ষণ প্রতি ধাপে অন্তত একটি নতুন fact আসে। BP-এর বাইরে কিছু আসতে পারে না, তাই বড়জোর |BP| ধাপের পর Ik+1 = Ik: একটি fixpoint, আর শেষের পরীক্ষাসহ ধাপ ≤ |BP| + 1. ∎
হাবের উদাহরণে constant ৭টি, আর reachable একটি arity-১ predicate, তাই reachable-এর বড়জোর ৭টি fact; খোঁজা কখনো ৮ ধাপের বেশি যেতে পারে না, চক্র থাকুক বা না থাকুক। Prolog-এর তালিকা ([H | T]) একটি compound term, তাই Datalog-এ নেই; ঠিক এজন্যই Datalog-এ lines_sum লেখা যায় না, আর ঠিক এজন্যই Datalog সবসময় থামে। বাস্তবে প্রতি ধাপে সব কিছু আবার হিসাব না করে শুধু আগের ধাপের নতুন fact (Δ) নিয়ে join করা হয়: semi-naive evaluation. SQL-এর WITH RECURSIVE-ও একই কৌশলে চলে; বিস্তার আছে DBMS কোর্সের পর্ব ২৫-এ (CTE আর recursive query).
1reachable(dhaka).2reachable(Y) :-3 reachable(X),4 link(X, Y).
| রাউন্ড | |
| Δ (আগের নতুন) | |
| নতুন fact | |
| জানা মোট |
- শুরু: fact. প্রথম clause-এর দেহ নেই, তাই TP-এর প্রথম খাটানোতেই
reachable(dhaka). এটিই প্রথম Δ, অর্থাৎ “সবচেয়ে নতুন তথ্য”। - রাউন্ড ১। Rule-এর
reachable(X)-এ শুধু Δ-এর dhaka বসিয়ে link খোঁজা: dhaka → gazipur, dhaka → narayanganj. দুটি নতুন fact; জানা মোট ৩. - রাউন্ড ২। Δ = {gazipur, narayanganj}. gazipur → mymensingh, narayanganj → cumilla. Semi-naive কৌশল dhaka-কে আবার join করে না, কারণ dhaka থেকে যা আসার, তা রাউন্ড ১-এই এসেছে।
- রাউন্ড ৩। Δ = {mymensingh, cumilla}. cumilla → chattogram নতুন। mymensingh → gazipur চক্রটি gazipur দেয়, কিন্তু সেটি আগেই জানা, তাই বাদ। এখানেই Prolog-এর অসীম loop Datalog-এ একটি সাধারণ “আগেই আছে” পরীক্ষা হয়ে গেল।
- রাউন্ড ৪: fixpoint. Δ = {chattogram}, কিন্তু chattogram থেকে কোনো link নেই। নতুন fact শূন্য: TP(I) = I. ছয়টি hub, Python run-এর “round 4: new = []”-এর সঙ্গে মেলে।
- ফল আর খরচ। sylhet নেই, কারণ রাস্তা সিলেট থেকে ঢাকায়, উল্টো নয়। প্রতি রাউন্ডে Δ-এর প্রতিটি hub-কে ৭টি link-এর সঙ্গে মেলানোকে “কাজ” ধরলে semi-naive-এ মোট (1 + 2 + 2 + 1) × 7 = 42, আর প্রতিবার সব জানা hub আবার মেলালে (naive) (1 + 3 + 5 + 6) × 7 = 105.
# Datalog, bottom-up: reachable(dhaka). reachable(Y) :- reachable(X), link(X, Y).
LINK = {("dhaka", "gazipur"), ("dhaka", "narayanganj"), ("gazipur", "mymensingh"),
("mymensingh", "gazipur"), ("narayanganj", "cumilla"),
("cumilla", "chattogram"), ("sylhet", "dhaka")}
def naive(start): # every round joins ALL known facts again
known, rnd, work = {start}, 0, 0
while True:
rnd += 1; work += len(known) * len(LINK)
new = {y for (x, y) in LINK if x in known} - known
if not new: return known, rnd, work
known |= new
def semi_naive(start): # every round joins only LAST round's new facts
known, delta, rnd, work = {start}, {start}, 0, 0
while delta:
rnd += 1; work += len(delta) * len(LINK)
delta = {y for (x, y) in LINK if x in delta} - known
print(f"round {rnd}: new = {sorted(delta)}")
known |= delta
return known, rnd, work
known, r1, w1 = semi_naive("dhaka")
print("reachable:", sorted(known), "| sylhet?", "sylhet" in known)
print("semi-naive: rounds", r1, "join work", w1, "| naive: rounds", naive("dhaka")[1], "join work", naive("dhaka")[2])
# all pairs: path(X, Y) :- link(X, Y). path(X, Z) :- path(X, Y), link(Y, Z).
path, delta, rnd = set(LINK), set(LINK), 0
while delta:
rnd += 1
delta = {(x, z) for (x, y) in delta for (y2, z) in LINK if y == y2} - path
path |= delta
print("path facts:", len(path), "after", rnd, "rounds | cycles:", sorted(x for (x, y) in path if x == y))আসল আউটপুট (ব্রাউজারের Python):
round 1: new = ['gazipur', 'narayanganj']
round 2: new = ['cumilla', 'mymensingh']
round 3: new = ['chattogram']
round 4: new = []
reachable: ['chattogram', 'cumilla', 'dhaka', 'gazipur', 'mymensingh', 'narayanganj'] | sylhet? False
semi-naive: rounds 4 join work 42 | naive: rounds 4 join work 105
path facts: 18 after 4 rounds | cycles: ['gazipur', 'mymensingh']
প্রথম চার লাইন stepper-এর চার রাউন্ড; তালিকা SWI-Prolog-এর tabling-এর ছয়টি hub-এর সঙ্গে মেলে (ক্রম আলাদা, কারণ এখানে বর্ণানুক্রমে সাজানো)। Semi-naive আর naive দুটিই ৪ রাউন্ডে থামে; পার্থক্য প্রতি রাউন্ডের কাজে, 42 বনাম 105. শেষ অংশে দুই-argument-এর path (সব hub-জোড়ার transitive closure): ৭টি link থেকে ১৮টি path fact, আর gazipur ও mymensingh নিজের কাছে ফিরে আসে, অর্থাৎ চক্রে আছে। এই “চক্র খোঁজা” প্রশ্নটি Prolog-এর সরল left-recursive নিয়মে থামত না।
Program analysis-এর ভাষা হিসেবে Datalog
Compiler-এর অনেক প্রশ্ন ঠিক এই আকারের: “কোন function কোন function-কে পরোক্ষে ডাকে?”, “এই pointer কোন কোন object-কে নির্দেশ করতে পারে?”, “এই variable-এর কোন সংজ্ঞা এই লাইনে পৌঁছায়?” প্রতিটির উত্তর কিছু মৌলিক fact (program-এর লাইনগুলো থেকে বের করা) আর কয়েকটি recursive নিয়ম থেকে আসা একটি fixpoint. যেমন একটি সরল points-to analysis: pts(V, O) :- new(V, O). আর pts(V, O) :- assign(V, W), pts(W, O). Java-র জন্য Doop (Bravenboer আর Smaragdakis, ২০০৯) এমন কয়েকশো নিয়মে sophisticated points-to analysis লেখে; Soufflé (২০১৬) একটি open-source Datalog engine, যা নিয়মগুলোকে দ্রুত C++ কোডে compile করে। পর্ব ৬৪-এ (Dataflow analysis — liveness, reaching definition আর fixpoint) একই fixpoint ধারণা liveness আর reaching definition-এ দেখবেন; আর “সব প্রশ্নের নিখুঁত উত্তর কেন অসম্ভব” তার তত্ত্ব আছে গণনার তত্ত্ব কোর্সের পর্ব ৭৮-এ.
আরও গভীরে: আমাদের engine প্রতিটি clause tuple হিসেবে ঘুরে দেখে; বাস্তব Prolog compiler clause-কে একটি বিমূর্ত যন্ত্রের নির্দেশে নামায়। David H. D. Warren ১৯৮৩ সালে এর নকশা প্রকাশ করেন, যা এখন Warren Abstract Machine (WAM) নামে পরিচিত: সেখানে unification বিশেষ নির্দেশে ভাঙা (get_structure, unify_variable), choice point একটি আলাদা stack-এ, আর backtracking-এর সময় কোন binding মুছতে হবে তা একটি “trail”-এ লেখা থাকে। আমাদের Python engine trail-এর কাজটি persistent dictionary দিয়ে সারে: পুরোনো θ কখনো বদলায় না, তাই মোছার দরকারই পড়ে না, কিন্তু প্রতিটি binding-এ নতুন dictionary বানানোর দাম দেয়।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- Logic programming-এর তিন উপাদান? Fact, rule আর query; উত্তর খোঁজে unification আর resolution (Prolog-এ depth-first backtracking).
- p(X, f(Y), Y) আর p(a, f(b), Z)-এর MGU? {X/a, Y/b, Z/b}: decompose করে X ≐ a, f(Y) ≐ f(b) থেকে Y ≐ b, তারপর Y ≐ Z থেকে Z = b.
- Occurs check কী, Prolog কেন বাদ দেয়? X ≐ f(X)-এর মতো সমীকরণে ব্যর্থ করার পরীক্ষা; প্রতিটি binding-এ term ঘুরে দেখার খরচ বাঁচাতে Prolog সাধারণত করে না।
- Cut আর negation as failure কী?
!তার পরের choice point মুছে দেয়;\+ Gসফল হয় G প্রমাণ না হলে, closed-world ধরে। - Prolog আর Datalog-এর পার্থক্য? Datalog-এ compound term নেই, মূল্যায়ন সাধারণত নিচ থেকে ওপরে fixpoint পর্যন্ত, আর সবসময় থামে।
৮ · AI-এর যুগে logic programming
AI assistant Prolog লিখতে পারে, আর তার লেখা নিয়ম প্রায়ই পড়তে সুন্দর। কিন্তু Prolog-এ “পড়তে সুন্দর” আর “চালালে থামে” দুটি আলাদা কথা, কারণ declarative পড়ার আড়ালে একটি নির্দিষ্ট খোঁজার কৌশল লুকিয়ে আছে। এই বিষয়ে বারবার দেখা ভুল:
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
Left-recursive নিয়ম (reachable(Y) :- reachable(X), link(X, Y).) লিখে বলা “এটি সব hub দেবে” | সব উত্তর জড়ো করে চালানো, চক্রসহ ডেটায়; call_with_inference_limit দিয়ে সীমা বেঁধে দেখা |
X = 2 + 3-কে গণনা ভাবা, বা is-কে উল্টো দিকে চালানো | Query চালিয়ে দেখা: = term 2+3 দেয়, অমুক্ত variable-এ is instantiation error দেয় |
\+-কে যৌক্তিক “না” ভাবা, আর মুক্ত variable নিয়ে ডাকা | লক্ষ্যের আগে variable বাঁধা হয়েছে কি না দেখা; একই প্রশ্ন ground মান দিয়ে আবার চালানো |
অস্তিত্বহীন built-in বানানো, যেমন SWI-Prolog-এ sum/2 (সত্যিকারের run-এ existence_error(procedure,sum/2); আছে sum_list/2) | নিজের Prolog-এর manual-এ predicate-টি খোঁজা, আর চালিয়ে দেখা |
| “Prolog-এর unification সবসময় যৌক্তিকভাবে নিখুঁত” বা “Datalog-এ তালিকা লেখা যায়” দাবি | occurs_check flag দেখা; Datalog engine-এর documentation-এ compound term সমর্থন দেখা |
| উত্তরের ক্রম বা উত্তরের সংখ্যা অনুমানে বলা | Search tree নিজে আঁকা, তারপর সত্যিকারের Prolog-এ সব উত্তর ছাপিয়ে মেলানো |
AI-কে ভালোভাবে কাজে লাগানোর উপায়: নিয়মের সঙ্গে খোঁজার আচরণও জিজ্ঞেস করা, আর একটি দ্বিতীয় বাস্তবায়ন দিয়ে উত্তর মেলানো।
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Prolog একটি গবেষণার ধারণা থেকে কীভাবে দ্রুত চলা একটি ভাষা হয়ে উঠল?
Prolog-এর জন্ম ১৯৭২ সালের দিকে মার্সেইতে, Alain Colmerauer আর Philippe Roussel-এর হাতে, আর প্রথম লক্ষ্য ছিল প্রাকৃতিক ভাষা (ফরাসি বাক্য) প্রক্রিয়া করা। প্রথম বাস্তবায়ন ছিল একটি interpreter, যা সরাসরি clause ঘুরে দেখত, অনেকটা এই পর্বের Python engine-এর মতো। তাত্ত্বিক দিকটি আসে Edinburgh থেকে: Robert Kowalski দেখান, Horn clause-কে “H প্রমাণ করতে B1, …, Bn প্রমাণ করুন” হিসেবে পড়লে একটি যুক্তির বাক্যই একটি procedure হয়ে যায় (১৯৭৪)। ১৯৭৬ সালে van Emden আর Kowalski এর গাণিতিক অর্থ দেন: least model, আর TP-এর fixpoint, যা অংশ ৭-এর উপপাদ্য।
তবে Prolog-কে গুরুত্বপূর্ণ ভাষা বানায় গতি। ১৯৭০-এর দশকের শেষে Edinburgh-এ David H. D. Warren (Luís আর Fernando Pereira-র সঙ্গে) DEC-10 Prolog-এর compiler তৈরি করেন; ১৯৭৭ সালে তাঁদের একটি লেখা এর compile করা কোডকে সেই সময়ের Lisp বাস্তবায়নের সঙ্গে তুলনা করে দেখায় যে logic ভাষাও গতিতে প্রতিযোগিতা করতে পারে। মূল কৌশল ছিল unification-কে আগে থেকে বিশেষায়িত করা: একটি clause-এর মাথা order(1, dhaka, L) জানা থাকলে compiler “প্রথম argument কি 1, দ্বিতীয়টি কি dhaka” যাচাইয়ের নির্দিষ্ট কোড বানাতে পারে, সাধারণ unify-এর বদলে। এর পরিণত রূপ ১৯৮৩ সালের Warren Abstract Machine, যা আজও অনেক Prolog বাস্তবায়নের ভিত্তি বা অনুপ্রেরণা।
এরপর ভাষাটির মানদণ্ড আসে: ISO Prolog-এর প্রথম অংশ ১৯৯৫ সালে প্রকাশিত হয়। SWI-Prolog (Jan Wielemaker, ১৯৮৭ থেকে) আজ সবচেয়ে প্রচলিত open-source বাস্তবায়নগুলোর একটি, আর এই পর্বের সত্যিকারের run তারই WebAssembly build-এ। ১৯৮০-এর দশকে জাপানের Fifth Generation প্রকল্পের কেন্দ্রেও logic programming ছিল; সেই গল্প AI কোর্সের পর্ব ৪৬-এ।
মূল উপলব্ধি: একটি declarative ভাষাকে বাস্তবে ব্যবহারযোগ্য করে তার compiler. “কী” লেখার স্বাধীনতা তখনই টেকে, যখন ভাষার বাস্তবায়নকারী “কীভাবে” অংশটি যথেষ্ট দ্রুত করে দেন; এই পর্বের প্রায় ৭০ লাইনের engine আর WAM-এর দূরত্বই সেই কাজ।
প্র ০২Occurs check বাদ দেওয়া কি একটি নিরাপদ আপস? না হলে বাস্তব ভাষাগুলো কী করে?
Robinson-এর ১৯৬৫ সালের algorithm-এ occurs check অপরিহার্য: এটি ছাড়া X ≐ f(X) “সফল” হয়, অথচ কোনো সসীম term-এ এটি সত্য নয়। Prolog-এর প্রথম বাস্তবায়নগুলো তবু এটি বাদ দেয়, আর ISO মানদণ্ডও এমন unification-এর ফল নির্দিষ্ট করে না, যেখানে occurs check লাগত। কারণ খরচ: X = BigTerm করার আগে পুরো BigTerm ঘুরে দেখতে হয়, তাই প্রতিটি binding-এর খরচ term-এর আকারের সমানুপাতিক হয়ে যায়, যেখানে occurs check ছাড়া binding একটি pointer বসানোর মতো সস্তা। বাস্তব program-এ X ≐ f(X) কদাচিৎ আসে, তাই সিদ্ধান্তটি ছিল গতির পক্ষে।
দাম কোথায়? প্রথমত, যুক্তি ভুল হতে পারে। একটি মাত্র fact p(Y, f(Y)). থেকে p(X, X) যৌক্তিকভাবে আসে না, কারণ কোনো সসীম X নিজের f(X)-এর সমান নয়। কিন্তু সত্যিকারের SWI-Prolog run-এ ?- p(X, X). সফল হয়েছে, উত্তর X = @(S_1,[S_1=f(S_1)]): একটি চক্রাকার term. Theorem prover বা verification-এর কাজে এমন “প্রমাণ” মারাত্মক। দ্বিতীয়ত, চক্রাকার term ছাপাতে বা তুলনা করতে গেলে সরল কোড অসীম loop-এ পড়ে, যা এই পর্বের Python engine-এ show-এর গভীরতার সীমা না থাকলে ঘটত।
ভাষাগুলো তিন পথ নিয়েছে। কেউ চক্রাকার term-কেই বৈধ মান বানিয়েছে: Colmerauer-এর Prolog II (১৯৮০-এর দশকের শুরু) “rational tree”, অর্থাৎ অসীম কিন্তু নিয়মিত term-এর ওপর unification সংজ্ঞায়িত করে; SWI-Prolog-ও চক্রাকার term সমর্থন করে আর নিরাপদে ছাপায় (AI কোর্সের run-এ @(S_1,[S_1=f(S_1)])). কেউ পছন্দের সুযোগ দেয়: SWI-Prolog-এর occurs_check flag (আমাদের run-এ ডিফল্ট false) চালু করলে প্রতিটি unification পরীক্ষা করে, আর unify_with_occurs_check/2 শুধু দরকারি জায়গায়। আর type inference-এর মতো জায়গায় occurs check বাধ্যতামূলক: পর্ব ৩৫-এ দেখবেন α ≐ (α) -> Int ধরনের সমীকরণ ধরা না পড়লে type checker একটি অসম্ভব type “প্রমাণ” করে ফেলত।
মূল উপলব্ধি: একই algorithm-এর একটি পরীক্ষা এক ক্ষেত্রে বিলাসিতা, অন্য ক্ষেত্রে নিরাপত্তার শর্ত। কোন ভাষা কোন আপস করেছে, তা জেনে তবেই তার উত্তরকে “প্রমাণ” বলা যায়।
প্র ০৩Datalog কেন compiler-এর program analysis-এর জনপ্রিয় ভাষা হয়ে উঠল?
Datalog-এর ধারণা ১৯৭০–৮০-এর দশকের database গবেষণা থেকে: relational database-এর প্রশ্নে recursion যোগ করা, কিন্তু Prolog-এর অসীম loop আর আংশিক উত্তর ছাড়া। নামটি ১৯৮০-এর দশকে প্রচলিত হয়; Abiteboul, Hull আর Vianu-র Foundations of Databases (১৯৯৫) বইটি এর তত্ত্ব গুছিয়ে দেয়। অংশ ৭-এর উপপাদ্য তিনটি নিশ্চয়তা দেয়, যা program analysis-এর জন্য সোনার মতো: উত্তর সবসময় থামে, উত্তর একক (least model), আর নিয়মের ক্রম উত্তর বদলায় না।
Program analysis-এর প্রশ্নগুলো প্রায় সবই “এক ধাপের নিয়ম, বারবার, যতক্ষণ নতুন কিছু আসে”: call graph-এ পরোক্ষ ডাক, pointer-এর সম্ভাব্য লক্ষ্য, পৌঁছানো সংজ্ঞা। ১৯৯০-এর দশকে Thomas Reps-এর মতো গবেষকেরা interprocedural analysis-কে logic database-এর প্রশ্ন হিসেবে লেখার কথা দেখান। ২০০৪ সালে Whaley আর Lam-এর bddbddb Java-র context-sensitive pointer analysis-কে Datalog-এ লেখে আর BDD নামের একটি সংক্ষিপ্ত ডেটা কাঠামোয় চালায়। ২০০৯ সালে Bravenboer আর Smaragdakis-এর Doop দেখায়, সম্পূর্ণ declarative নিয়মে লেখা points-to analysis হাতে লেখা বাস্তবায়নের চেয়েও দ্রুত হতে পারে, যদি Datalog engine ভালোভাবে optimize করা হয়। এরপর Soufflé (২০১৬) Datalog নিয়মকে সমান্তরাল C++ কোডে compile করে, আর কয়েকটি বাণিজ্যিক code-scanning tool-এর query ভাষাও Datalog-এর ধাঁচে তৈরি।
সুবিধার মূলে একটি প্রকৌশল-বিভাজন: analysis-এর লেখক শুধু নিয়ম লেখেন (“কী সত্য”), আর engine-এর লেখক semi-naive evaluation, index, join-এর ক্রম আর সমান্তরাল চালানো দেখেন (“কীভাবে”)। ঠিক Kowalski-র algorithm = logic + control, এবার এমন একটি সীমিত ভাষায়, যেখানে control পুরোপুরি engine-এর হাতে ছেড়ে দেওয়া নিরাপদ। সীমাও আছে: function symbol নেই বলে ইচ্ছামতো গভীর ডেটা কাঠামো আঁকা যায় না, তাই context-এর গভীরতার মতো জিনিস আগে থেকে সীমিত করে দিতে হয়।
মূল উপলব্ধি: একটি ভাষার ক্ষমতা কমিয়ে কখনো কখনো তার মূল্য বাড়ে। Datalog Prolog-এর চেয়ে কম প্রকাশক্ষম, কিন্তু সেজন্যই তার প্রতিটি program থামে আর দ্রুত চালানো যায়।
প্র ০৪Cut-কে কেন কেউ কেউ Prolog-এর “goto” বলেন? বিকল্প কী?
Cut Prolog-এর প্রথম দিকের বাস্তবায়ন থেকেই আছে, কারণ বাস্তব program-এ খোঁজা থামানো দরকার: একটি নিশ্চিত উত্তর পেলে বাকি বিকল্প দেখে সময় নষ্ট করার মানে নেই, আর কিছু ক্ষেত্রে অপ্রয়োজনীয় choice point memory-ও খায়। সমস্যা হলো cut-এর অর্থ শুধু খোঁজার ক্রম দিয়ে বোঝা যায়। first_free-এর দুটি clause-এর ক্রম বদলালে, বা order fact-গুলোর ক্রম বদলালে, উত্তর বদলে যায়; যুক্তির ভাষায় পড়লে এমন হওয়ার কথা নয়। পর্ব ০৭-এ দেখেছেন Dijkstra-র সময়ে goto নিয়ে আপত্তি ছিল যে এটি program-এর গঠন থেকে আচরণ বোঝা কঠিন করে; cut-এর ক্ষেত্রেও আপত্তি একই রকম: declarative পড়া থেকে আচরণ বোঝা যায় না।
Prolog সম্প্রদায় তাই cut-কে দুই ভাগে দেখে। “Green cut” শুধু অপ্রয়োজনীয় খোঁজা কাটে; cut মুছে দিলেও উত্তরের সেট একই থাকে। “Red cut” উত্তর বদলায়, যেমন first_free. Sterling আর Shapiro-র The Art of Prolog (১৯৮৬) এর মতো বইয়ে এই পার্থক্য জনপ্রিয় হয়। পরামর্শ হলো red cut সরাসরি না লিখে উদ্দেশ্য প্রকাশ করা ছোট built-in ব্যবহার করা: once(G) (“G-এর প্রথম উত্তরই যথেষ্ট”), ( If -> Then ; Else ) (শর্ত-শাখা), আর \+; এগুলোর ভেতরে cut থাকলেও তার প্রভাব সীমিত আর পড়ে বোঝা যায়।
কিছু ভাষা আরও এগিয়েছে। ১৯৯৫ সালের দিকে মেলবোর্নে তৈরি Mercury প্রতিটি predicate-এর জন্য mode (কোন argument ইনপুট, কোনটি আউটপুট) আর determinism (একটি উত্তর, বড়জোর একটি, নাকি অনেক) ঘোষণা করতে বলে, আর compiler সেটি যাচাই করে; ফলে cut ছাড়াই দক্ষ কোড পাওয়া যায়, আর discounted(T, 936)-এর মতো ভুল mode-এর call compile করার সময়েই ধরা পড়ে। এটি পর্ব ৩৩-এর (Type system) static যাচাইয়ের ধারণা, এবার খোঁজার আচরণের ওপর।
মূল উপলব্ধি: নিয়ন্ত্রণের প্রতিটি হাতিয়ার যত বেশি স্থানীয় আর ঘোষিত, program তত সহজে বোঝা যায়। Cut-এর সমস্যা ক্ষমতা নয়, অদৃশ্যতা।
প্র ০৫একই unification কীভাবে logic programming, type inference আর pattern matching তিন জায়গায় কাজ করে?
Robinson ১৯৬৫ সালে unification দিয়েছিলেন যন্ত্র দিয়ে theorem প্রমাণের জন্য। কয়েক বছরের মধ্যে একই algorithm তিনটি আলাদা ভাষা-যন্ত্রের হৃদয় হয়ে ওঠে, কারণ তিনটিতেই প্রশ্নটি একই: “কয়েকটি অজানাসহ দুটি গঠন সমান হতে হলে অজানাগুলো কী?”
Logic programming-এ অজানা হলো logic variable, গঠন হলো term; এই পর্বের পুরো engine-টাই তার ওপর। Type inference-এ অজানা হলো type variable: Haskell বা ML-এ \x -> x + 1-এর type খুঁজতে compiler x-কে একটি নতুন type α দেয়, তারপর +-এর type থেকে α ≐ Int সমীকরণ পায়; Milner-এর ১৯৭৮ সালের Algorithm W এমন সমীকরণ Robinson-এর unification দিয়েই সমাধান করে। পর্ব ৩৫-এ এটি Haat-এর মতো একটি ভাষার জন্য বানাবেন। Pattern matching (Haskell, OCaml, Rust-এর match) unification-এর একমুখী রূপ: শুধু pattern-এ variable থাকে, মানটি সবসময় ground, তাই algorithm অনেক সরল আর দ্রুত, আর কোনো occurs check লাগে না। এর বিস্তার পর্ব ২৪-এ (Algebraic data type আর pattern matching).
ভাষার ইতিহাসেও এই আত্মীয়তা দেখা যায়। Erlang-এর প্রথম বাস্তবায়ন ১৯৮০-এর দশকের মাঝামাঝি Prolog-এ লেখা হয়েছিল বলে এর নকশাকারীরা জানিয়েছেন, আর Erlang-এর syntax আর pattern matching-এ ({ok, X} = f()) Prolog-এর ছাপ স্পষ্ট; তবে Erlang-এর = একমুখী match, দুই দিকের unification নয়। আধুনিক compiler-এর type checker, যেমন Rust-এর, এখনো ভেতরে unification-ভিত্তিক সমীকরণ সমাধান করে, বহু উন্নতিসহ।
মূল উপলব্ধি: ভালো algorithm একটি নির্দিষ্ট সমস্যার নয়, একটি প্রশ্নের আকারের সমাধান। “অজানাসহ দুটি গাছ সমান করা” আকারটি চিনতে পারলে logic engine, type checker আর pattern matcher-কে একই পরিবারের সদস্য হিসেবে দেখা যায়।
অনুশীলন
প্রথমে নিজে করুন, তারপর উত্তর খুলে মেলান। Haat-এর আউটপুট কোর্সের reference বাস্তবায়নে, আর Prolog-এর আউটপুট সত্যিকারের SWI-Prolog 10.1.21-এ চালিয়ে মেলানো।
-
বাস্তবায়ন — Haat-এ cut: অংশ ৫-এর
pairs.haat-এ এমন পরিবর্তন করুন, যাতে প্রথম উত্তর পাওয়ার সঙ্গে সঙ্গে সব খোঁজা থেমে যায় (Prolog-এরonceবা cut-এর মতো)। শুধুbetweenআর শেষের continuation বদলাতে পারবেন। কী ছাপা হবে, আরtriesকত হবে?// প্রথম উত্তর পেলেই খোঁজা বন্ধ: Prolog-এর cut-এর মতো var tries = 0; var stop = false; fn between(lo: Int, hi: Int, k: (Int) -> Unit) { var i = lo; while i <= hi && !stop { k(i); i = i + 1; } } fn pair(k: (Int, Int) -> Unit) { between(0, 9, fn(x: Int) { between(0, 9, fn(y: Int) { tries = tries + 1; if 120 * x + 180 * y == 1080 { k(x, y); } }); }); } pair(fn(x: Int, y: Int) { print(x); print(y); stop = true; }); print(tries);Reference-এর
runআরvmদুটিতেই আউটপুট:0,6,7. একটি ভাগ করাvar stopএকটি “cut পতাকা”: continuation উত্তর পেয়ে এটিtrueকরে, আর প্রতিটিbetweenloop পরের মান নেওয়ার আগে পতাকা দেখে। ভেতরের loop y = 6-এ থামে, তারপর বাইরের loop-ও x = 1-এ ঢোকার আগে থামে; চেষ্টা মোট ৭টি, JavaScript-এরbreak-এর সঙ্গে হুবহু। লক্ষ করুন, cut-এর প্রভাব এখানে সব choice point-এর ওপর, কারণ পতাকাটি সবাই দেখে; Prolog-এর cut শুধু নিজের clause-এর মাথা ডাকার পরের choice point মোছে। সূক্ষ্মভাবে কাটতে চাইলে প্রতিটি স্তরের জন্য আলাদা পতাকা লাগত। -
ভুল খুঁজুন: একজন লিখলেন: “
f(X, b)আরf(a, X)unify হয়, MGU {X/a, X/b}; আর Prolog occurs check ছাড়াX = f(X)-এ সবসময়falseদেয়।” দুটি দাবির ভুল কোথায়?প্রথম দাবি: একটি substitution-এ একটি variable-এর একটিই মান থাকে, তাই {X/a, X/b} কোনো substitution-ই নয়। Algorithm চালালে decompose করে X ≐ a আর b ≐ X; প্রথমটিতে X/a, তারপর দ্বিতীয়টিতে walk করে b ≐ a, যা দুটি আলাদা constant-এর clash. সুতরাং দুই term unify হয় না; সত্যিকারের SWI-Prolog run-এ
f(X, b) = f(a, X)-এর উত্তরfalse.দ্বিতীয় দাবি উল্টো: occurs check থাকলে X ≐ f(X) ব্যর্থ হয়। Occurs check ছাড়া (Prolog-এর ডিফল্ট) X-কে f(X)-এ বাঁধা হয়ে যায়, আর SWI-Prolog একটি চক্রাকার term বানায়; আমাদের driver-এর run-এ উত্তর এসেছিলX = @(S_1,[S_1=f(S_1)]), আর Python engine-এcheck=Falseদিলে f(f(f(f(…)))).falseপেতেunify_with_occurs_check(X, f(X))লাগে, যার run-এ উত্তর সত্যিইfalse. -
আউটপুট অনুমান করুন: অংশ ৪-এর program-এ (order-এর চারটি fact,
near(dhaka),near(gazipur)) (ক)?- near(D), order(I, D, S).কয়টি উত্তর দেবে, কোন ক্রমে? (খ)?- order(I, dhaka, S), S < 1000.? (গ) (ক)-এর লক্ষ্য দুটির ক্রম উল্টালে উত্তরের সেট বা ক্রম বদলাবে কি?(ক) প্রথম লক্ষ্য
near(D), প্রথম clause-এ D = dhaka. তারপরorder(I, dhaka, S)ঢাকার তিনটি fact-এর সঙ্গে ক্রমে মেলে: (1, 1040), (3, 1100), (4, 200). Backtracking-এ D = gazipur, কিন্তু gazipur-এর কোনো অর্ডার নেই, শাখাটি ব্যর্থ। সত্যিকারের run:D = dhaka I = 1 S = 1040,D = dhaka I = 3 S = 1100,D = dhaka I = 4 S = 200; মোট ৩টি।(খ) ঢাকার তিনটি fact-এর মধ্যে শুধু 200 < 1000. Run-এ উত্তর একটিই:
I = 4 S = 200.(গ) সেট বদলাবে না: যৌক্তিক অর্থে দুটি একই (“এবং” বিনিময়যোগ্য)। এখানে ক্রমও একই থাকে (1, 3, 4), কারণ order-এর fact-গুলোই ক্রম ঠিক করে। কিন্তু গাছ বদলায়:
orderআগে হলে চারটি শাখা খুলে রাজশাহীর শাখায়near(rajshahi)ব্যর্থ হয়;nearআগে হলে গাজীপুরের জন্য order-এর চারটি fact আবার ঘুরে দেখা হয়। কাজের পরিমাণ লক্ষ্যের ক্রমের ওপর নির্ভর করে, অংশ ৫-এর 100 বনাম 70-এর মতো। -
প্রমাণ: সংজ্ঞা ১০.৩-এর TP ধরে প্রমাণ করুন: (ক) TP monotone; (খ) I0 = ∅, Ik+1 = TP(Ik) হলে Ik ⊆ Ik+1 সব k-এর জন্য। (গ) Prolog-এর
\+-ওয়ালা একটি নিয়ম, যেমনp :- \+ q.q :- \+ p., TP-কে monotone রাখে না কেন?- (ক) ধরি I ⊆ J আর h ∈ TP(I). তাহলে কোনো clause H :- B1, …, Bn আর ground θ আছে, যেখানে h = Hθ আর প্রতিটি Biθ ∈ I ⊆ J. একই clause আর θ দেখায় h ∈ TP(J).
- (খ) k-এর ওপর আরোহ। ভিত্তি: I0 = ∅ ⊆ I1, কারণ ফাঁকা সেট সব সেটের উপসেট। ধাপ: Ik ⊆ Ik+1 ধরে, (ক) থেকে TP(Ik) ⊆ TP(Ik+1), অর্থাৎ Ik+1 ⊆ Ik+2. ∎
- (গ) নেতিবাচক শর্তে “I-তে q নেই” দেখতে হয়। I = ∅ হলে q নেই, তাই p ∈ TP(∅); কিন্তু J = {q} ⊇ I-তে q আছে, তাই p ∉ TP(J). বড় সেট ছোট ফল দিল: monotonicity ভাঙল, আর উপপাদ্য ১০.২-এর যুক্তি আর খাটে না। এই program-এর দুটি ছোট model আছে ({p} আর {q}), কোনোটি “সবচেয়ে ছোট” নয়। এজন্যই Datalog engine নেতিবাচক শর্ত শুধু stratified রূপে দেয়: নিজের ওপর নেতিবাচকভাবে নির্ভর করা নিয়ম নিষেধ।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমProlog-এর SLD resolution-এর একটি ধাপের কাজগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- লক্ষ্যের তালিকার সবচেয়ে বাঁ দিকের লক্ষ্যটি বেছে নেওয়া
- ওপর থেকে নিচে পরের চেষ্টা না করা clause বেছে নেওয়া
- Clause-এর সব variable নতুন নামে কপি করা
- লক্ষ্য আর clause-এর মাথা unify করে MGU θ বের করা
- লক্ষ্যের জায়গায় clause-এর দেহ বসিয়ে পুরো তালিকায় θ খাটানো
p(X, f(Y), Y) আর p(a, f(b), Z)-এর most general unifier কোনটি?
- {X/a, Y/b}, Z মুক্ত থাকে
- {X/a, Y/b, Z/b}
- {X/b, Y/b, Z/b}
- unify হয় না
Occurs check-সহ unification-এ X ≐ f(X)-এর ফল কী, আর SWI-Prolog-এর ডিফল্ট = কী করে?
- দুটিতেই X = f(a) ধরনের একটি সসীম উত্তর
- Occurs check-সহ সফল হয়, ডিফল্ট = ব্যর্থ হয়
- দুটিতেই ব্যর্থ, কারণ SWI-Prolog সবসময় occurs check করে
- Occurs check-সহ ব্যর্থ; ডিফল্ট = একটি চক্রাকার term বানায়
Fact order(1, dhaka, 1040). order(2, rajshahi, 540). order(3, dhaka, 1100). আর near(dhaka). থাকলে, f(I) :- order(I, D, S), near(D), S >= 1000, !. নিয়মে ?- f(I).-এর সব উত্তর কী?
- শুধু I = 1
- I = 1, তারপর I = 3
- শুধু I = 3
- কোনো উত্তর নেই
SWI-Prolog-এ T মুক্ত অবস্থায় ?- X = T - 10. আর ?- X is T - 10. চালালে কী হয়?
- দুটিতেই instantiation error
- দুটিতেই T-এর জন্য সব সম্ভাব্য মান খোঁজে
- প্রথমটিতে X পায় term
T-10; দ্বিতীয়টি instantiation error দেয় - প্রথমটি একটি সংখ্যা দেয়, দ্বিতীয়টি false
Datalog-এর প্রতিটি program নিচ থেকে ওপরে (bottom-up) মূল্যায়নে কেন সসীম ধাপে থামে?
- কারণ Datalog-এ recursion নিষেধ
- Compound term নেই, তাই সম্ভাব্য fact সসীম, আর প্রতি ধাপে fact শুধু বাড়ে
- কারণ engine একটি নির্দিষ্ট সময় পরে খোঁজা বন্ধ করে
- কারণ Datalog depth-first খোঁজে আর চক্র এড়িয়ে চলে
চক্রসহ link fact-এ reach(dhaka). আর তার পরে reach(Y) :- reach(X), link(X, Y). লিখে সাধারণ Prolog-এ findall(H, reach(H), L) চাইলে কী হয়, আর সমাধান কী?
- সব hub একবার করে আসে, কারণ Prolog চক্র নিজেই ধরে
- প্রথম লক্ষ্যেই error, কারণ reach এখনো সংজ্ঞায়িত নয়
- দুটি clause-এর ক্রম উল্টালেই সমস্যা পুরো মিটে যায়
- খোঁজা থামে না (উত্তর বারবার আসে);
:- table reach/1.দিলে থামে
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Logic program: fact, rule আর query; প্রতিটি rule-এর declarative আর procedural দুই পড়া। Algorithm = logic + control: logic আপনার, control ভাষার।
- Unification: decompose, bind, swap, clash আর occurs check; ফল MGU. Prolog-এর ডিফল্ট
=occurs check করে না। - SLD resolution আর backtracking: বাঁ দিকের লক্ষ্য, ওপরের clause, গভীরে আগে; ব্যর্থ হলে শেষ choice point-এ ফেরা। SLD complete, Prolog-এর depth-first কৌশল নয়।
- বাজারঘর: SWI-Prolog আর প্রায় ৭০ লাইনের Python engine দুটিতেই ঢাকা 2126; সম্পর্ক উল্টো দিকেও চলে, কিন্তু
isচলে না (constraint চলে)। Cut আর\+logic-এর বাইরের নিয়ন্ত্রণ। - Datalog: compound term নেই, TP-এর least fixpoint, সবসময় থামে; semi-naive শুধু Δ নিয়ে join করে। Program analysis-এর অনেক tool এর ওপর দাঁড়ানো।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ১১ · Concurrent programming-এর মডেল — thread, actor, CSP আর dataflowপরবর্তী পর্বএকাধিক কাজ একসাথে চালানোর paradigm.
- প্রোগ্রামিং ভাষা ও কম্পাইলার · কোর্স হোম৮৬টি পর্বপুরো কোর্সের মানচিত্র আর Haat প্রজেক্টের পথ।
- First-order logic — বস্তু, সম্পর্ক আর quantifierপাশের ট্র্যাকLogic-এর তত্ত্ব, entailment, closed আর open world.
- অনুমানের নিয়ম — modus ponens থেকে resolutionগণিতResolution নিয়মের যুক্তির ভিত্তি।
- CTE আর recursive queryপাশের ট্র্যাকSQL-এর WITH RECURSIVE, fixpoint আর semi-naive.
- Program analysis-এর সীমা — abstract interpretation আর type systemতত্ত্বFixpoint-ভিত্তিক analysis-এর তাত্ত্বিক সীমা।