এই পর্বে যা শিখবেন
- Strict আর non-strict-এর সংজ্ঞা (⊥ দিয়ে), আর call-by-value, call-by-name ও call-by-need একই program-এ কী ভিন্ন ফল বা খরচ দেয়, তা ধাপে ধাপে হিসাব করা
- Thunk আর memoised thunk কীভাবে কাজ করে, আর Python ও Haat-এ নিজে বানানো
- ALGOL 60-এর call-by-name, Jensen's device আর
swap-এর বিখ্যাত ব্যর্থতা ব্যাখ্যা করা - Lambda calculus-এর normal order আর applicative order-এর সঙ্গে প্রোগ্রামিং ভাষার কৌশলের সম্পর্ক বোঝা
- Short-circuit, generator, অসীম stream, space leak আর strictness analysis দিয়ে laziness-এর লাভ-দাম মাপা
১ · Argument কখন হিসাব হবে — একটি ছোট প্রশ্ন, বড় প্রভাব
পর্ব ১৪ থেকে ১৮ পর্যন্ত আমরা দেখেছি একটি নাম কোন ঘোষণাকে বোঝায় (scope), ঘরটি কতক্ষণ বাঁচে (lifetime), আর একটি function তার পরিবেশ কীভাবে ধরে রাখে (closure). মডিউলের শেষ প্রশ্নটি সময় নিয়ে: twice(price(2, 520)) লিখলে price(2, 520) ঠিক কখন চলবে? twice শুরুর আগেই? twice-এর ভেতরে যখন x দরকার হবে তখন? নাকি যতবার x লেখা আছে, ততবার?
বাজারঘরের রান্নাঘরে একজন রাঁধুনি আছেন, আর আপনি তাঁকে একটি পদ রাঁধতে বলছেন। তিনভাবে কাজটি দেওয়া যায়। এক: আগে বাজার করে সব উপকরণ এনে হাতে দিলেন, তারপর রান্না শুরু। কোনো উপকরণ না লাগলেও কেনা হয়ে গেছে। দুই: শুধু বাজারের ফর্দটি দিলেন। রেসিপিতে যতবার “পেঁয়াজ” লেখা, রাঁধুনি ততবার দোকানে দৌড়ান। তিন: ফর্দ দিলেন, রাঁধুনি প্রথমবার পেঁয়াজ দরকার হলে কিনে এনে তাকে রেখে দেন; পরের বার তাক থেকে নেন, আর যা কখনো লাগে না তা কেনাই হয় না। এই তিনটিই যথাক্রমে call-by-value, call-by-name আর call-by-need.
ভাষার নিয়ম যে অংশে এই প্রশ্নের উত্তর দেয়, তার নাম evaluation strategy. পর্ব ০৯-এ (Functional programming) lazy evaluation-এর একটি ঝলক দেখেছেন: Python-এর generator একটি অসীম তালিকা থেকে ঠিক যতটুকু চাওয়া হয় ততটুকু বানায়। এই পর্বে সেই ঝলককে পুরো কাঠামোয় বসাব: সংজ্ঞা, বাস্তবায়ন, ইতিহাস আর দাম।
⊥ (“bottom”) দিয়ে বোঝানো হয় এমন একটি হিসাব যা কোনো মান দেয় না: চিরকাল চলে, বা error-এ থেমে যায়। একটি function f strict (একটি argument-এ), যদি f(⊥) = ⊥, অর্থাৎ argument-এর হিসাব ভেঙে পড়লে f-ও ভেঙে পড়ে। একটি ভাষা strict (বা eager), যদি তার প্রতিটি function call argument-গুলো call-এর আগেই হিসাব করে; তখন প্রতিটি ব্যবহারকারী-লেখা function আপনা থেকেই strict হয়। Non-strict ভাষায় argument হিসাব হয় শুধু দরকার পড়লে, তাই একটি function ⊥ পেয়েও মান ফেরত দিতে পারে।
Haat একটি strict ভাষা। আর argument-গুলোর ক্রমও নির্দিষ্ট: reference বাস্তবায়নের নকশা-সিদ্ধান্ত ১২ অনুযায়ী বাঁ থেকে ডানে, আগে callee, তারপর argument একটির পর একটি। একটি ছোট program দুটি কথাই দেখায়। tag নিজের argument ছেপে তারপর ফেরত দেয়, তাই ছাপার ক্রমই হিসাবের ক্রম:
// বাজারঘর: argument কখন হিসাব হয়
fn tag(n: Int) -> Int {
print(n);
return n;
}
fn first(a: Int, b: Int) -> Int {
return a;
}
print(first(tag(1), tag(2)));
print(tag(10) + tag(20) * tag(30));
print(first(5, 1 / 0));~/haat $ python haat.py run order.haat
1
2
1
10
20
30
610
11:18: runtime error: division by zero
~/haat $ python haat.py vm order.haat
1
2
1
10
20
30
610
11:18: runtime error: division by zero
সত্যিকারের run (Haat reference, CPython 3.14.4; দুই back end-এর আউটপুট হুবহু এক)। প্রথম call-এ first তার b কখনো ব্যবহার করে না, তবু tag(2) চলেছে: strict ভাষায় সব argument call-এর আগেই হিসাব হয়। দ্বিতীয় লাইনে *-এর precedence বেশি, তবু ছাপা হয়েছে 10, 20, 30: precedence ঠিক করে কোন অপারেশন কার সঙ্গে জোড়া লাগবে, আর evaluation order ঠিক করে কোন operand আগে হিসাব হবে; দুটি আলাদা নিয়ম। শেষ লাইনই আসল পরীক্ষা: first কখনো b ছোঁয় না, তবু 1 / 0 call-এর আগে চলে আর program থামে লাইন ১১, কলাম ১৮-এ, অর্থাৎ / চিহ্নের ওপর। গাণিতিকভাবে first(5, ⊥) = ⊥: Haat-এর first তার দ্বিতীয় argument-এও strict, যদিও সেটি ব্যবহার করে না।
একটি সতর্কতা: evaluation order আর evaluation strategy এক জিনিস নয়। Order বলে strict argument-গুলো কোন ক্রমে হিসাব হবে; সেখানেও ভাষাভেদে নিয়ম আলাদা। Java (JLS §15.7.4) আর JavaScript argument বাঁ থেকে ডানে হিসাব করার নিশ্চয়তা দেয়; C17 ক্রমটি unspecified রেখে দেয়, তাই f(a(), b())-এ কোনটি আগে চলবে তা compiler-এর ইচ্ছা। এই প্রশ্নের পুরো আলোচনা পর্ব ২৬-এ (Expression আর evaluation order). এই পর্বের প্রশ্ন বড়: argument আদৌ হিসাব হবে কি না, আর কতবার।
২ · তিন কৌশল: call-by-value, call-by-name, call-by-need
তিনটি কৌশল সংক্ষেপে:
- Call-by-value: argument-কে আগে একটি মানে নামিয়ে আনা হয়, তারপর function-এর parameter সেই মান পায়। প্রতিটি argument ঠিক একবার হিসাব হয়, ব্যবহার হোক বা না হোক।
- Call-by-name: argument-এর expression-টিই হিসাব ছাড়া পাঠানো হয়। Function-এর ভেতরে parameter যতবার পড়া হয়, ততবার সেই expression ডাকা-পক্ষের পরিবেশে নতুন করে হিসাব হয়। ব্যবহার না হলে কখনোই হিসাব হয় না।
- Call-by-need: call-by-name-এর মতোই দরকার পড়লে হিসাব, কিন্তু প্রথমবারের ফল মনে রাখা হয়; পরের সব ব্যবহার সেই ফল পায়। অর্থাৎ প্রতিটি argument সর্বোচ্চ একবার হিসাব হয়। এটিই সাধারণ অর্থে “lazy evaluation”.
প্রথম দুটির পার্থক্য operational semantics-এর ভাষায় খুব সংক্ষেপে লেখা যায়। নিচে e ⇓ v মানে “expression e হিসাব করলে মান v পাওয়া যায়” (big-step নিয়ম; পূর্ণ পদ্ধতি পর্ব ৪০-এ), fn(x){b} হলো parameter x আর দেহ b-ওয়ালা একটি function-মান, আর b[x := e] মানে b-এর ভেতরে প্রতিটি x-এর জায়গায় e বসানো (substitution). দাগের ওপরের শর্তগুলো সত্য হলে নিচের সিদ্ধান্তটি সত্য:
App-V-তে একটি বাড়তি শর্ত আছে: e2 ⇓ v. তাই e2 যদি ⊥ হয়, App-V প্রয়োগই করা যায় না, পুরো call ⊥. App-N-এ e2 সরাসরি দেহে ঢুকে যায়; দেহ যদি x না ছোঁয়, e2-এর কোনো ভূমিকাই নেই। আর দেহে x দুবার থাকলে e2 দুবার হিসাব হবে। Call-by-need এই substitution-এর নিয়মে লেখা যায় না, কারণ “মনে রাখা” মানে একটি ভাগ করা ঘর লাগে; তার জন্য একটি heap-ওয়ালা semantics দরকার (“আরও গভীরে” বাক্সে দেখুন)।
এবার একই program তিন নিয়মে চালিয়ে দেখি। twice তার argument দুবার পড়ে, pick একবারও পড়ে না (flag false হলে)। লেখা Haat-এর মতো, কিন্তু Haat নিজে শুধু call-by-value; বাকি দুটি কল্পিত ভাষার নিয়মে।
1fn twice(x: Int) -> Int {2 return x + x;3}4fn pick(flag: Bool, x: Int) -> Int {5 if flag { return x; }6 return 0;7}8print(twice(price(2, 520)));9print(pick(false, 1 / 0));
| by value: x | |
| by name: x | |
| by need: x | |
| argument হিসাব value│name│need |
- Call. Call-by-value-এ
price(2, 520)আগে চলে, 936 নিয়ে তবেtwice-এ ঢোকে। বাকি দুই কৌশলে কিছুই হিসাব হয়নি: x পায় একটি thunk, অর্থাৎ “পরে হিসাব করার” একটি প্রতিশ্রুতি। - বাঁ পাশের x. By value: ঘরে 936 আছেই। By name আর by need দুজনেই এখন thunk খোলে,
priceচলে, 936. By need ফলটি thunk-এর ভেতরেই লিখে রাখে। - ডান পাশের x. এখানেই পার্থক্য। By name আবার
priceচালায় (মোট ২ বার); by need লিখে রাখা 936 নেয় (মোট ১ বার)। - যোগ। তিন কৌশলেই 936 + 936 = 1872. ফল এক, খরচ আলাদা:
priceচলেছে ১, ২ আর ১ বার। ফল এক হলো কারণpricepure; side effect থাকলে by name-এর দুবার চলা চোখে পড়ত। - pick(false, 1 / 0). By value-তে
1 / 0call-এর আগেই চলে আর error. By name আর by need-এ x শুধু একটি thunk, এখনো কিছু ভাঙেনি। - দেহ।
flagfalse, তাইreturn 0;. Non-strict দুই কৌশলে x কখনো খোলা হয়নি, ফল 0; by value-তে দেহে পৌঁছানোই যায়নি। একই program, কৌশলভেদে একটি ভাঙে, দুটি চলে: termination-ও কৌশলের ওপর নির্ভর করে।
Stepper-এর দুটি শিক্ষা মনে রাখার মতো। এক: যে program call-by-value-এ একটি মান দেয়, সেটি call-by-name বা call-by-need-এও একই মান দেয়, যদি argument-গুলোর side effect না থাকে; উল্টোটা সত্য নয়, কারণ non-strict কৌশল কিছু program-কে বাঁচিয়ে দেয় (ধাপ ৬)। দুই: খরচের দিক থেকে call-by-need কখনো call-by-name-এর চেয়ে বেশি হিসাব করে না, আর call-by-value-এর চেয়েও বেশি নয়, শুধু thunk বানানো আর খোলার বাড়তি হিসাবটুকু বাদে। পুরো পরিবারটি এক ছবিতে:
ছবি ১৯.১ — Evaluation strategy-র পরিবার
বাঁ দিকে strict: call-এর আগে হিসাব। ডান দিকে non-strict: দরকার হলে তবেই। নিচে বাঁয়ে, strict ভাষার ভেতরের lazy ফাঁকগুলো।
=> Int লিখলে সেটি by-name; Haskell lazy, কিন্তু seq দিয়ে আগে হিসাব জোর করা যায়। R ভাষায় function-এর argument একটি “promise”, যা প্রথম ব্যবহারে একবার হিসাব হয়।৩ · Thunk — “পরে হিসাব করব” প্রতিশ্রুতির বাস্তবায়ন
Non-strict কৌশল বাস্তবায়নের প্রশ্নটি হলো: হিসাব না করা একটি expression-কে function-এর কাছে পাঠাব কী করে? শুধু লেখাটি (text) পাঠালে চলবে না, কারণ expression-এর নামগুলো ডাকা-পক্ষের পরিবেশের; twice-এর ভেতরে হিসাব করলে ভুল variable পাওয়া যেতে পারে, ঠিক পর্ব ১৫-এর dynamic scope-এর ফাঁদের মতো। সমাধান: expression-এর code আর ডাকা-পক্ষের environment একসঙ্গে বেঁধে একটি ছোট বস্তু বানানো। এই বস্তুর নাম thunk. শব্দটি এসেছে Peter Ingerman-এর ১৯৬১ সালের প্রবন্ধ থেকে, যেখানে তিনি ALGOL 60-এর call-by-name compile করার এই কৌশল বর্ণনা করেন।
খেয়াল করুন, “code + environment” আমাদের পরিচিত জিনিস: এটি একটি parameter-হীন closure. পর্ব ১৭-এর ভাষায়, thunk হলো এমন একটি closure যাকে কোনো argument ছাড়া ডাকলে argument-এর মান পাওয়া যায়। Thunk-কে চালিয়ে মান বের করাকে বলে force করা। নিচের Python কোডে একটি Thunk class তিন কৌশলকেই চালায়: call-by-value-এ আগে হিসাব, call-by-name-এ memo ছাড়া thunk, call-by-need-এ memo-সহ thunk.
calls = 0
def price(qty, unit): # the expensive argument
global calls; calls += 1
p = qty * unit
return p - p // 10 if p >= 1000 else p
class Thunk: # a promise: code to run later
def __init__(self, code, memo):
self.code, self.memo, self.done, self.value = code, memo, False, None
def force(self):
if self.done:
return self.value # call-by-need: reuse the answer
v = self.code()
if self.memo: # remember it, and drop the code
self.done, self.value, self.code = True, v, None
return v
def twice(get_x): # body: x + x
return get_x() + get_x()
def pick(flag, get_x): # body: if flag then x else 0
return get_x() if flag else 0
def call(strategy, body, arg, *rest):
global calls
calls = 0
try:
if strategy == "value":
v = arg() # evaluate first, then call
r = body(*rest, lambda: v)
else:
r = body(*rest, Thunk(arg, memo=strategy == "need").force)
except ZeroDivisionError:
r = "error: division by zero"
print(f"{strategy:5} {body.__name__:5} -> {r!s:23} price calls = {calls}")
for s in ("value", "name", "need"):
call(s, twice, lambda: price(2, 520))
for s in ("value", "name", "need"):
call(s, pick, lambda: 1 // 0, False)আসল আউটপুট (ব্রাউজারের Python):
value twice -> 1872 price calls = 1
name twice -> 1872 price calls = 2
need twice -> 1872 price calls = 1
value pick -> error: division by zero price calls = 0
name pick -> 0 price calls = 0
need pick -> 0 price calls = 0
Stepper-এর প্রতিটি সংখ্যা এখানে সত্যিকারের run থেকে মিলল। Function-এর দেহ x-কে সরাসরি পায় না, পায় get_x, যাকে ডাকলে মান আসে: call-by-value-এ সেটি আগে-হিসাব-করা মান ফেরত দেয়, অন্য দুটিতে thunk-এর force. pick-এর তিন লাইনে price calls = 0, কারণ সেখানে argument 1 // 0, price নয়; আসল পার্থক্য ফলের ঘরে: by value-তে error, বাকি দুটিতে 0. খেয়াল করুন force-এর একটি সূক্ষ্ম কাজ: মান মনে রাখার সময় self.code = None. Thunk-এর code তার পরিবেশকে ধরে রাখে; মান পাওয়ার পরে সেটি ছেড়ে দিলে পরিবেশের বাকি অংশ garbage collector নিতে পারে। এই ছোট লাইনটি না থাকলে কী হয়, তা অংশ ৮-এর space leak-এর গল্প।
এবার memo-সহ thunk-এর জীবন ধাপে ধাপে দেখুন। কোডটি উপরের Thunk.force, আর ডাক twice(t.force), যেখানে t একটি call-by-need thunk:
1t = Thunk(lambda: price(2, 520), memo=True)2def force(self):3 if self.done:4 return self.value5 v = self.code()6 if self.memo:7 self.done, self.value, self.code = True, v, None8 return v
| t.code | |
| t.done | |
| t.value | |
| price ডাকা | |
| twice-এর হাতে |
- তৈরি। Thunk-এর ভেতরে শুধু code (একটি lambda) আর তার ধরা পরিবেশ।
priceএখনো চলেনি,doneFalse. - প্রথম force.
twiceবাঁ পাশের x চায়, তাইforce().doneFalse, তাই মনে রাখা কিছু নেই। - Code চলে।
self.code()মানেprice(2, 520): প্রথম আর একমাত্র বার, v = 936. - মনে রাখা।
doneTrue,value936, আরcodeNone: lambda আর তার পরিবেশের ওপর thunk-এর দাবি শেষ। একে বলে thunk-কে তার মান দিয়ে “update” করা। - প্রথম ফেরত। 936 ফেরত যায়,
twice-এর বাঁ পাশ পূর্ণ। - দ্বিতীয় force. ডান পাশের x আবার
force()ডাকে। এবারdoneTrue, তাই লাইন ৪ থেকেই 936 ফেরত;priceআর চলে না, গণনা ১-এই থাকে। - ফল। 936 + 936 = 1872, আর
priceচলেছে ঠিক একবার: call-by-value-এর সমান খরচ, অথচ argument ব্যবহার না হলে খরচ শূন্য হতো।
Haat-এ হাতে বানানো thunk
Haat v1 strict, কিন্তু তার function first-class, আর parameter-হীন function-এর type () -> Int লেখা যায়। তাই call-by-name নিজের হাতে বানানো যায়: argument-এর জায়গায় একটি anonymous function পাঠান, আর দেহে x-এর জায়গায় x() লিখুন। এই কৌশলের পোশাকি নাম “thunking”, আর পর্ব ৫৫-এ (Desugaring) দেখবেন compiler নিজেও এভাবে বড় বৈশিষ্ট্যকে ছোট core-এ নামায়।
// বাজারঘর: thunk হাতে বানানো
fn price(qty: Int, unit: Int) -> Int {
print("price computed");
let p = qty * unit;
if p >= 1000 { return p - p / 10; }
return p;
}
fn twice_val(x: Int) -> Int { return x + x; }
fn twice_name(x: () -> Int) -> Int { return x() + x(); }
fn pick(flag: Bool, x: () -> Int) -> Int {
if flag { return x(); }
return 0;
}
print(twice_val(price(2, 520)));
print(twice_name(fn() -> Int { return price(2, 520); }));
print(pick(false, fn() -> Int { return 1 / 0; }));~/haat $ python haat.py run thunk.haat
price computed
1872
price computed
price computed
1872
0
সত্যিকারের run (vm-এও হুবহু এক)। এবার price-এর একটি side effect আছে, “price computed” ছাপা, তাই খরচ চোখে দেখা যায়: twice_val-এ একবার, twice_name-এ দুবার। শেষ লাইনে 1 / 0 একটি function-এর দেহে বন্দি; pick সেটি কখনো ডাকে না, তাই কোনো error নেই, ফল 0. অংশ ১-এর first(5, 1 / 0) ভেঙে পড়েছিল; একই ভাষায়, শুধু argument-কে thunk-এ মুড়ে, আমরা non-strict আচরণ পেলাম। Call-by-need-এর জন্য দরকার শুধু একটি memoization-এর মোড়ক, যা অনুশীলন ১-এ আপনি নিজেই বানাবেন।
৪ · ALGOL 60-এর call-by-name আর Jensen's device
Call-by-name কোনো তাত্ত্বিক খেলনা নয়; এটি ছিল ALGOL 60-এর ডিফল্ট parameter নিয়ম। ALGOL 60-এর report একটি “copy rule” দিয়ে procedure call-এর অর্থ দেয়: call-টিকে procedure-এর দেহের একটি কপি দিয়ে বদলে দিন, যেখানে প্রতিটি formal parameter-এর জায়গায় actual parameter-এর লেখা বসানো (দরকারে নাম বদলে, যাতে সংঘর্ষ না হয়)। কোনো parameter-কে by value চাইলে আলাদা করে value লিখতে হতো। এই নিয়মের সবচেয়ে বিখ্যাত ব্যবহার হলো Jensen's device, যার নাম Regnecentralen-এ Peter Naur-এর সহকর্মী ডেনিশ প্রোগ্রামার Jørn Jensen-এর নামে (মোটামুটি ১৯৬০ সালের কথা)।
কৌশলটি হলো একটি “সাধারণ যোগফল” procedure, যা গণিতের Σ-এর মতো কাজ করে। Procedure-টি একটি index variable k আর একটি expression term দুটোই by name নেয়; loop-এ k বদলায়, আর প্রতিবার term নতুন করে হিসাব হয় ডাকা-পক্ষের পরিবেশে, যেখানে k আসলে ডাকা-পক্ষের i. ফলে sum(i, 1, 3, x[i]) হয় x[1] + x[2] + x[3]. ধাপে ধাপে দেখুন (x = 936, 990, 200; বাজারঘরের তিনটি অর্ডার):
1real procedure sum(k, lo, hi, term);2 value lo, hi;3 integer k, lo, hi; real term;4begin real s;5 s := 0;6 for k := lo step 1 until hi do7 s := s + term;8 sum := s9end;10total := sum(i, 1, 3, x[i])
| ডাকা-পক্ষের i | |
| term এখন | |
| s | |
| term হিসাব হয়েছে |
- Call.
loআরhiby value: 1 আর 3.kহলো ডাকা-পক্ষেরi-এর আরেক নাম,termহলো “x[i]” লেখাটির thunk. s = 0. - k := 1.
k-তে লেখা মানে আসলে ডাকা-পক্ষেরi-তে লেখা: i = 1. By-name parameter-এ লেখা যায়, কারণ তার thunk একটি ঘরের ঠিকানাও দিতে পারে। - s := s + term.
termখোলা হয় ডাকা-পক্ষের পরিবেশে: x[i] = x[1] = 936. s = 936. - k := 2. ডাকা-পক্ষের i = 2.
term-এর ভেতরের লেখা বদলায়নি, কিন্তু তার মান এখন অন্য হবে। - আবার term. এবার x[2] = 990, s = 1926. একই নাম
term, দ্বিতীয়বার খোলা, ভিন্ন মান: call-by-name-এর মূল শক্তি এখানেই। - k := 3. i = 3.
- শেষবার term. x[3] = 200, s = 2126.
- শেষ। k = 4 > hi, loop থামে,
sum := s, তাই total = 2126 = 936 + 990 + 200. Call-by-need হলেtermপ্রথমবারের 936 মনে রাখত, আর ফল হতো 3 × 936 = 2808: ভুল যোগফল।
নিচের Python অনুকরণে প্রতিটি by-name parameter হলো দুটি thunk-এর জোড়া: একটি মান পড়ে (get), একটি মান লেখে (set). একই total procedure দিয়ে তিনটি ভিন্ন যোগফল, তারপর by value-তে কী হয়, আর শেষে একটি বিখ্যাত ব্যর্থতা:
class Name: # a by-name parameter: get and set thunks
def __init__(self, get, set=None): self.get, self.set = get, set
env = {"i": 0} # the caller's variable i
x = [None, 936, 990, 200] # 1-based, as in ALGOL
q = [None, 2, 1, 3]
evals = 0
def total(k, lo, hi, term): # ALGOL: real procedure sum(k, lo, hi, term)
global evals
s = 0
k.set(lo)
while k.get() <= hi:
evals += 1
s = s + term.get() # term is re-evaluated in the CALLER's env
k.set(k.get() + 1)
return s
i = Name(lambda: env["i"], lambda v: env.__setitem__("i", v))
print("sum x[i] =", total(i, 1, 3, Name(lambda: x[env["i"]])))
print("sum x[i]*q[i] =", total(i, 1, 3, Name(lambda: x[env["i"]] * q[env["i"]])))
print("sum 60/i =", total(i, 1, 4, Name(lambda: 60 // env["i"])))
print("term evaluated", evals, "times; caller's i is now", env["i"])
env["i"] = 1
v = x[env["i"]] # by value: term computed once, before the call
print("by value, sum x[i] =", total(i, 1, 3, Name(lambda: v)))
a = [None, 3, 1, 2]; env["i"] = 1 # swap(i, a[i]) under call-by-name
A = Name(lambda: a[env["i"]], lambda val: a.__setitem__(env["i"], val))
def swap(p, r):
t = p.get(); p.set(r.get()); r.set(t)
swap(i, A)
print("after swap(i, a[i]): i =", env["i"], " a =", a[1:])আসল আউটপুট (ব্রাউজারের Python):
sum x[i] = 2126
sum x[i]*q[i] = 3462
sum 60/i = 125
term evaluated 10 times; caller's i is now 5
by value, sum x[i] = 2808
after swap(i, a[i]): i = 3 a = [3, 1, 1]
একটি procedure, কোনো বদল ছাড়া: Σx[i] = 2126, Σx[i]·q[i] = 936·2 + 990·1 + 200·3 = 3462 (একটি ডট প্রোডাক্ট), আর Σ 60/i = 60 + 30 + 20 + 15 = 125. সব মিলিয়ে term ১০ বার খোলা হয়েছে (৩ + ৩ + ৪)। By value-তে x[i] call-এর আগে একবার হিসাব হয় (i = 1, তাই 936), আর যোগফল 3 × 936 = 2808: কৌশলটি ভেঙে পড়ে। শেষ লাইনটি ইতিহাসের বিখ্যাত সমস্যা। swap(p, r) লেখা হয়েছে সাধারণভাবে: t := p; p := r; r := t. কিন্তু swap(i, a[i])-এ দ্বিতীয় ধাপে i = a[1] = 3 হয়ে যায়, আর তৃতীয় ধাপে r মানে a[i], যা এখন a[3]; তাই 1 বসে a[3]-এ, a[1] অপরিবর্তিত থাকে 3. প্রত্যাশিত ফল ছিল i = 3, a[1] = 1. Call-by-name-এ parameter-এর “পরিচয়” প্রতিবার নতুন করে ঠিক হয়, আর সেটাই এখানে কাল হলো।
এই অনিশ্চয়তা, আর প্রতিটি ব্যবহারে thunk ডাকার খরচ, এই দুই কারণে পরের প্রায় সব imperative ভাষা call-by-name ছেড়ে দেয়। Pascal (১৯৭০) value আর var (by reference) parameter নেয়; C শুধু by value. তবে ধারণাটি অন্য রূপে বেঁচে আছে। C-র macro আসলে লেখা-বসানো: #define TWICE(x) ((x) + (x))-এ TWICE(next_id()) লিখলে preprocessor সেটিকে ((next_id()) + (next_id())) বানায়, অর্থাৎ next_id দুবার চলে, call-by-name-এর মতো (বিস্তারিত C কোর্সের পর্ব ২৭-এ)। পার্থক্য হলো macro নামের পরিবেশ ধরে না, ALGOL-এর thunk ধরে। Scala-তে parameter-এর type => Int লিখলে সেটি by-name, যা দিয়ে নিজের while-এর মতো control structure লেখা যায়। Parameter পাঠানোর সব নিয়মের (by value, by reference, by sharing, by name) পাশাপাশি তুলনা আসবে পর্ব ২৯-এ।
৫ · Normal order আর applicative order — lambda calculus-এর চোখে
Evaluation strategy-র প্রশ্নটি প্রোগ্রামিং ভাষার চেয়েও পুরোনো। Lambda calculus-এ হিসাবের একটিই ধাপ, β-reduction: (λx. M) N-কে M[x := N]-এ বদলানো। একটি term-এ এমন একাধিক অংশ (redex) থাকলে কোনটি আগে কমাবেন? এর তত্ত্ব আছে গণনার তত্ত্ব কোর্সের পর্ব ৪৯-এ; এখানে শুধু দুটি নীতি আর প্রোগ্রামিং ভাষার সঙ্গে তাদের যোগ।
- Normal order: সবসময় সবচেয়ে বাঁয়ের, সবচেয়ে বাইরের redex. Argument হিসাব না করেই function-এর দেহে বসানো হয়: call-by-name-এর আত্মীয়।
- Applicative order: সবচেয়ে বাঁয়ের, সবচেয়ে ভেতরের redex. Function প্রয়োগের আগে argument কমানো হয়: call-by-value-এর আত্মীয়।
দুটি ছোট term-এ লেখকের যন্ত্রে একটি ছোট Python reducer দিয়ে সত্যিকারের run করা ধাপ গণনা (Ω = (λw. w w)(λw. w w), যে term নিজেকে নিজের মধ্যেই ফিরিয়ে আনে আর কখনো শেষ হয় না):
| Term | Normal order | Applicative order |
|---|---|---|
| (λx. λy. x) z Ω | ২ ধাপে z | Ω কমাতে গিয়ে আটকে যায় (৮ ধাপের সীমায় থামানো, প্রতিটি ধাপে একই term) |
| (λx. x x) ((λy. y) z) | ৩ ধাপে z z: argument দুবার কপি হয়ে দুবার কমে | ২ ধাপে z z: argument আগে একবার কমে |
প্রথম সারি দেখায় normal order-এর শক্তি: যে argument লাগে না, তার হিসাবও লাগে না। এর একটি প্রমাণিত রূপ আছে, standardization theorem (Curry আর Feys, ১৯৫৮): কোনো term-এর normal form থাকলে normal order সেখানে পৌঁছাবেই। দ্বিতীয় সারি দেখায় তার দাম: কপি করা argument বারবার কমে, ঠিক call-by-name-এর মতো। আর Church–Rosser theorem নিশ্চিত করে, দুই পথই যদি শেষ হয়, ফল একই। সমস্যা শুধু খরচ আর শেষ হওয়া নিয়ে। Call-by-need এই দুইয়ের সেরা মিলন: normal order-এর মতো দরকার হলে তবেই হিসাব, কিন্তু কপির বদলে একটি ভাগ করা thunk, তাই একবারই কমে। Christopher Wadsworth ১৯৭১ সালের থিসিসে এই “ভাগ করা” কমানোকে graph reduction হিসেবে বর্ণনা করেন; এটিই আধুনিক lazy ভাষার শিকড়।
একটি সূক্ষ্ম পার্থক্য পরীক্ষায় প্রায়ই গুলিয়ে যায়। Normal আর applicative order λ-এর ভেতরেও কমায়, অর্থাৎ পুরো normal form চায়। প্রোগ্রামিং ভাষার call-by-value আর call-by-name কখনো function-এর দেহের ভেতরে হিসাব করে না, যতক্ষণ না function ডাকা হয়: fn() -> Int { return 1 / 0; } একটি বৈধ মান, যদিও ভেতরে ⊥. তাই ভাষার কৌশলগুলো থামে একটি দুর্বল রূপে, যার নাম weak head normal form. Gordon Plotkin ১৯৭৫ সালে “Call-by-name, call-by-value and the λ-calculus” প্রবন্ধে এই দুই ভাষা-কৌশলকে আলাদা দুটি calculus হিসেবে দাঁড় করান। Lambda calculus-কে প্রোগ্রামিং ভাষার ভিত্তি হিসেবে আরও দেখবেন পর্ব ৪৩-এ।
৬ · Strict ভাষার ভেতরে laziness: short-circuit, if আর default
সম্পূর্ণ strict ভাষা প্রায় নেই। প্রতিটি strict ভাষায় কিছু জায়গা থাকে যেখানে একটি অংশ ইচ্ছা করে হিসাব করা হয় না। সবচেয়ে পরিচিত উদাহরণ if: শর্ত সত্য হলে else-এর অংশ চলে না। যদি if একটি সাধারণ strict function হতো, দুটি শাখাই আগে চলত, আর if n != 0 { … total / n … }-এর পাহারা অর্থহীন হতো। একই কারণে && আর || সাধারণ operator নয়: Haat-এর নিয়মে এরা short-circuit করে, বাঁ পাশ দেখেই ফল নিশ্চিত হলে ডান পাশ ছোঁয় না। সত্যিকারের run:
fn noisy(b: Bool) -> Bool {
print("checked");
return b;
}
fn big_avg(total: Int, n: Int) -> Bool {
return n != 0 && total / n > 500;
}
print(big_avg(1200, 0));
print(big_avg(1200, 2));
print(false && noisy(true));
print(true || noisy(false));
print(true && noisy(false));~/haat $ python haat.py run short.haat
false
true
false
true
checked
false
~/haat $ python haat.py dis short.haat # only big_avg shown
== big_avg (arity 2, locals 2) ==
0 LOAD_LOCAL 1 ; n
1 CONST 0 ; 0
2 NE
3 JUMP_IF_FALSE 10
4 LOAD_LOCAL 0 ; total
5 LOAD_LOCAL 1 ; n
6 DIV
7 CONST 1 ; 500
8 GT
9 JUMP 11
10 CONST 2 ; false
11 RETURN
সত্যিকারের run (vm-এও একই ছয় লাইন)। big_avg(1200, 0) division by zero দেয়নি: n != 0 false, তাই ডান পাশ চলেনি। “checked” ছাপা হয়েছে শুধু একবার, শেষ লাইনে, কারণ সেখানেই প্রথমবার বাঁ পাশ ফল ঠিক করতে পারেনি (true && …)। Bytecode দেখায় কৌশলটি কীভাবে বাস্তবায়িত: &&-এর জন্য কোনো আলাদা opcode নেই। নির্দেশ ৩-এর JUMP_IF_FALSE 10 বাঁ পাশ false হলে ৪–৯ (পুরো ডান পাশ, DIV-সহ) লাফিয়ে সোজা ১০-এ গিয়ে false বসায়। অর্থাৎ short-circuit হলো compiler-এর বানানো control flow; পর্ব ৫৮-এ (Bytecode নকশা) এই অনুবাদ নিজে লিখবেন। গাণিতিক ভাষায়: false && ⊥ = false, তাই && তার দ্বিতীয় argument-এ strict নয়; Haat-এর কোনো ব্যবহারকারী-লেখা function এমন হতে পারে না, কারণ ভাষাটি strict.
শেষ কথাটির একটি মজার পরিণতি আছে। Haat-এ fn my_and(a: Bool, b: Bool) -> Bool লিখে &&-এর সমান কিছু বানানো যায় না: call-এর আগেই b হিসাব হয়ে যাবে। Swift ভাষা এর সমাধান করেছে @autoclosure দিয়ে: parameter-এর আগে এটি লিখলে ডাকা-পক্ষের expression আপনা থেকে একটি closure-এ মোড়া হয়, আর Swift-এর standard library-তে && নিজেই এভাবে সাধারণ function হিসেবে লেখা। অর্থাৎ ভাষার ভেতরে নির্বাচিত জায়গায় call-by-name.
JavaScript-এ আরও কয়েকটি lazy ফাঁক আছে। নিচের কোড দেখায় &&, ?. আর ??-এর short-circuit, argument-এর eager বাঁ-থেকে-ডান হিসাব, default parameter কখন হিসাব হয়, আর হাতে বানানো একটি memoised thunk:
const log = [];
function t(name, v) { log.push(name); return v; }
const order = null;
console.log(order && order.total, order?.total); // no TypeError
console.log(t("A", false) && t("B", true), "|", log.join(","));
log.length = 0;
console.log(t("A", null) ?? t("B", "BG-1001"), "|", log.join(","));
log.length = 0;
function first(a, b) { return a; }
first(t("arg1", 1), t("arg2", 2)); // eager, left to right
console.log("args evaluated:", log.join(","));
let made = 0;
function ship(id, fee = (made++, 60)) { return id + ":" + fee; }
console.log(ship("BG-1", 0), ship("BG-2"), ship("BG-3"), "defaults made:", made);
function lazy(f) { // a memoised thunk
let done = false, v;
return () => (done ? v : (done = true, v = f()));
}
let runs = 0;
const price = lazy(() => { runs++; return 2 * 520 - 104; });
console.log(price() + price(), "computed", runs, "time(s)");আসল আউটপুট (ব্রাউজারের JavaScript; লেখকের যন্ত্রে Node 24-এও হুবহু এক):
null undefined
false | A
BG-1001 | A,B
args evaluated: arg1,arg2
BG-1:0 BG-2:60 BG-3:60 defaults made: 2
1872 computed 1 time(s)
প্রথম লাইন: order null, তাই order.total কখনো পড়া হয়নি, TypeError-ও হয়নি। দ্বিতীয়: log-এ শুধু A, B-এর হিসাব বাদ। তৃতীয়: ?? ডান পাশে যায় শুধু বাঁ পাশ null বা undefined হলে; এখানে গেছে, তাই A,B. চতুর্থ: first b ব্যবহার করে না, তবু arg2 হিসাব হয়েছে, আর arg1-এর পরে: JavaScript strict, আর তার spec argument বাঁ থেকে ডানে হিসাবের নিশ্চয়তা দেয়। পঞ্চম: default parameter-এর expression প্রতিটি call-এ নতুন করে চলে, কিন্তু শুধু argument না থাকলে: তিন call-এ দুবার। এটি একটি ছোট call-by-name: লেখাটি function-এর সঙ্গে থাকে, হিসাব হয় দরকারের মুহূর্তে। ষষ্ঠ: lazy হলো Python-এর Thunk-এর JavaScript রূপ: দুটি ব্যবহার, একটি হিসাব।
Python-এও একই ছবি: and, or আর x if c else y short-circuit করে। আর Python 3.14 একটি নতুন lazy ফাঁক যোগ করেছে: PEP 649 অনুযায়ী function-এর type annotation আর def চলার সময় হিসাব হয় না, প্রথমবার পড়া হলে তবেই। সত্যিকারের run:
import sys
print(sys.version.split()[0])
def ship(order: Order) -> Receipt: # Order, Receipt not defined yet
return None
print("def ran; no NameError")
try:
print(ship.__annotations__)
except NameError as e:
print("NameError:", e)
class Order: pass
class Receipt: pass
print(ship.__annotations__)~/haat $ python ann.py
3.14.4
def ran; no NameError
NameError: name 'Order' is not defined
{'order': <class '__main__.Order'>, 'return': <class '__main__.Receipt'>}
লেখকের যন্ত্রে CPython 3.14.4-এ সত্যিকারের run. def নির্বিঘ্নে চলেছে, যদিও Order তখনো নেই; প্রথম পড়ায় NameError, কারণ তখনো class দুটি তৈরি হয়নি; আর class তৈরির পরে পড়লে annotation ঠিকঠাক আসে। অর্থাৎ annotation এখন একটি thunk-এর মতো আচরণ করে, যা প্রতিবার ব্যর্থ হলে আবার চেষ্টা করে। পুরোনো Python (3.13 পর্যন্ত, from __future__ import annotations ছাড়া) def-এর সময়েই NameError দিত। Annotation-এর type-দিক নিয়ে আরও আছে Python কোর্সের পর্ব ৪০-এ।
৭ · Lazy sequence আর অসীম কাঠামো
Laziness-এর সবচেয়ে সুন্দর ফল হলো অসীম ডেটা কাঠামো। Lazy ভাষায় “সব স্বাভাবিক সংখ্যার তালিকা” একটি সাধারণ মান, কারণ তালিকার লেজ (tail) একটি thunk; যতটুকু পড়া হয়, ঠিক ততটুকু তৈরি হয়। Haskell-এ, উদাহরণ (চালানো হয়নি; ফল ভাষার সংজ্ঞা থেকে):
-- উদাহরণ (Haskell), চালানো হয়নি
orderIds = [1001 ..] -- অসীম তালিকা
firstEven = take 3 (filter even orderIds) -- [1002,1004,1006]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
-- take 8 fibs হলো [0,1,1,2,3,5,8,13]fibs নিজেকেই নিজের সংজ্ঞায় ব্যবহার করে, আর তবু কাজ করে, কারণ প্রতিটি নতুন ঘর তৈরির সময় আগের ঘরগুলো একবারই হিসাব হয়ে মনে থাকে (call-by-need). Call-by-name হলে প্রতিটি ঘর আগের সব ঘর আবার হিসাব করত, আর খরচ ঘাতের হারে বাড়ত। Strict ভাষায় একই ধারণা আসে library বা বিশেষ বৈশিষ্ট্য হয়ে। Python-এর generator হলো একটি function যা yield-এ থেমে থাকে আর পরের মান চাইলে আবার চলে (বিস্তারিত Python কোর্সের পর্ব ৩৬-এ; generator কীভাবে বাস্তবায়িত হয়, তা পর্ব ৩১-এ)। নিচের কোডে তিনটি জিনিস: একটি অসীম অর্ডার-ID generator, memo-সহ thunk দিয়ে বানানো একটি lazy তালিকা, আর একটি জমে থাকা thunk-শিকল।
from itertools import count, islice
def order_ids(): # an endless, lazy stream of order IDs
for n in count(1001):
print(" made", n)
yield f"BG-{n}"
print(list(islice(order_ids(), 3)))
class Stream: # lazy cons cell: head now, tail later
def __init__(self, head, tail_thunk):
self.head, self._tail, self._done = head, tail_thunk, False
@property
def tail(self): # forced once, then remembered
if not self._done:
self._tail, self._done = self._tail(), True
return self._tail
built = 0
def from_n(n):
global built; built += 1
return Stream(n, lambda: from_n(n + 1))
def take(k, s):
out = []
for _ in range(k):
out.append(s.head); s = s.tail
return out
nats = from_n(1) # "all" natural numbers
print(take(5, nats), "cells built:", built)
print(take(5, nats), "cells built:", built, "(shared, not rebuilt)")
def lazy_sum(n): # foldl without strictness: a thunk chain
acc, made = (lambda: 0), 0
for k in range(1, n + 1):
acc, made = (lambda prev, k: lambda: prev() + k)(acc, k), made + 1
return acc, made
t, made = lazy_sum(300)
print("thunks waiting:", made, "| forced value:", t())আসল আউটপুট (ব্রাউজারের Python):
made 1001
made 1002
made 1003
['BG-1001', 'BG-1002', 'BG-1003']
[1, 2, 3, 4, 5] cells built: 6
[1, 2, 3, 4, 5] cells built: 6 (shared, not rebuilt)
thunks waiting: 300 | forced value: 45150
Generator: অসীম loop, তবু ঠিক তিনটি ID তৈরি, কারণ islice তিনটিই চেয়েছে। Stream: nats “সব” স্বাভাবিক সংখ্যা, কিন্তু তৈরি হয়েছে ৬টি ঘর। পাঁচটি নয় কেন? আমাদের take পঞ্চম head নেওয়ার পরেও একবার s.tail চেয়েছে, তাই ষষ্ঠ ঘরটি অকারণে তৈরি হলো। Lazy কোডে এমন “একটি বেশি” হিসাব খুব সাধারণ ভুল; Haskell-এর take শেষ উপাদানের পরে লেজ ছোঁয় না। দ্বিতীয় take-এ গণনা বাড়েনি: memo-সহ thunk ঘরগুলো ভাগ করে দিয়েছে, call-by-need-এর আসল লাভ। Thunk-শিকল: lazy_sum কোনো যোগ করেনি; সে ৩০০টি thunk বানিয়েছে, প্রতিটি আগেরটিকে ধরে রাখে, আর শেষে force করলে তবে 1 + 2 + … + 300 = 45150. যে কাজের জন্য একটি সংখ্যার ঘর যথেষ্ট, তার জন্য ৩০০টি বস্তু মেমরিতে বসে আছে। এটিই পরের অংশের সমস্যা।
৮ · Laziness-এর দাম: space leak, side effect আর strictness analysis
অংশ ৭-এর thunk-শিকল একটি বাস্তব সমস্যার ছোট মডেল, যার নাম space leak: program-এর যতটুকু মেমরি লাগার কথা, laziness-এর কারণে তার চেয়ে অনেক বেশি ধরে রাখা। Haskell-এর পরিচিত উদাহরণ (চালানো হয়নি):
-- উদাহরণ (Haskell), চালানো হয়নি
import Data.List (foldl')
total = foldl (+) 0 [1 .. 10000000] -- (((0+1)+2)+3)… thunk জমতে পারে
total' = foldl' (+) 0 [1 .. 10000000] -- প্রতিটি ধাপে যোগফল আগেই হিসাবLazy foldl প্রতিটি ধাপে যোগ না করে “আগের ফল + k” নামের একটি thunk বানায়, ঠিক আমাদের lazy_sum-এর মতো; শেষে সেই বিশাল শিকল খোলার সময় অনেক মেমরি আর গভীর stack লাগতে পারে। foldl' প্রতিটি ধাপে accumulator-কে seq দিয়ে আগেই হিসাব করে। বাস্তবে GHC optimization চালু থাকলে প্রায়ই নিজেই এই সমস্যা সরিয়ে দেয়, কিন্তু সবসময় নয়, আর কখন দেবে তা compiler-এর version আর flag-এর ওপর নির্ভর করে; তাই অভিজ্ঞ Haskell প্রোগ্রামাররা সাধারণত সরাসরি foldl' লেখেন। Space leak-এর আরেক উৎস হলো যে thunk ব্যবহারই হয় না অথচ বড় কোনো ডেটা ধরে রাখে; অংশ ৩-এর self.code = None লাইন ঠিক এই ঝুঁকি কমায়।
দ্বিতীয় দাম side effect-এর সঙ্গে বিরোধ। Lazy ভাষায় একটি expression কখন, এমনকি আদৌ চলবে কি না, তা নির্ভর করে কে কখন তার মান চায় তার ওপর; ছাপা, ফাইলে লেখা বা variable বদলানোর ক্রম তাই আন্দাজ করা কঠিন। Jensen's device-এ দেখেছেন, mutable variable থাকলে by-name আর by-need ভিন্ন উত্তর দেয়। এই কারণেই lazy ভাষাগুলো pure function-এর দিকে ঝুঁকেছে: side effect না থাকলে হিসাবের ক্রমে ফল বদলায় না, আর referential transparency বজায় থাকে। Haskell I/O-কে আলাদা type-এ (IO) বেঁধে রাখে, যার কথা পর্ব ০৯-এর ভাবনার প্রশ্নে আছে। তৃতীয় দাম গতি: প্রতিটি thunk একটি heap-বস্তু, প্রতিটি ব্যবহারে “এটি কি এখনো thunk?” পরীক্ষা লাগে, আর profiler-এ খরচ দেখা যায় যেখানে মান চাওয়া হলো সেখানে, যেখানে লেখা হলো সেখানে নয়।
Strictness analysis — compiler যখন আগেই হিসাব করতে পারে
Lazy ভাষার compiler-এর সবচেয়ে বড় অস্ত্র হলো strictness analysis: প্রমাণ করা যে একটি function তার কোনো argument-এ strict, অর্থাৎ f(⊥) = ⊥. তাহলে argument-টি call-এর আগেই হিসাব করা নিরাপদ, কারণ কোনো program-এর অর্থ বদলাবে না: যে program argument-টি না খুলে শেষ হতো, সে strict function-এ এমনিতেও argument খুলত। লাভ: thunk বানানো লাগে না, মান সরাসরি register-এ যেতে পারে। Alan Mycroft ১৯৮০ সালের প্রবন্ধে abstract interpretation দিয়ে এই বিশ্লেষণের একটি প্রভাবশালী পদ্ধতি দেন: মানগুলোকে শুধু দুই ভাগে দেখা হয়, “⊥ হতে পারে” (0) আর “নিশ্চিত মান” (1). যেমন f(x, y) = x + y-এর জন্য f#(0, 1) = 0, কারণ + দুই পাশই চায়; তাই f দুই argument-এই strict. কিন্তু g(x, y) = if x == 0 then 0 else y-এ g#(1, 0) = 1 হতে পারে, তাই g y-তে strict নয়।
নিখুঁত strictness analysis অসম্ভব: “এই function কি সবসময় এই argument খোলে?” প্রশ্নটি program-এর একটি অ-তুচ্ছ আচরণগত বৈশিষ্ট্য, তাই Rice-এর উপপাদ্য অনুযায়ী সাধারণভাবে নির্ণয়যোগ্য নয় (গণনার তত্ত্ব কোর্সের পর্ব ৫৩)। Compiler তাই নিরাপদ দিকে ভুল করে: “নিশ্চিত strict” বললে তবেই আগে হিসাব করে; সন্দেহ থাকলে thunk রেখে দেয়। Abstract interpretation-এর সাধারণ তত্ত্ব আছে একই কোর্সের পর্ব ৭৮-এ, আর এই কোর্সে dataflow analysis-এর একই ধাঁচের fixpoint হিসাব আসবে পর্ব ৬৪-এ।
| বৈশিষ্ট্য | Call-by-value | Call-by-name | Call-by-need |
|---|---|---|---|
| অব্যবহৃত argument | তবু হিসাব হয় (⊥ হলে পুরো call ⊥) | কখনো হিসাব হয় না | কখনো হিসাব হয় না |
| দুবার ব্যবহৃত argument | একবার | দুবার | একবার |
| Side effect-এর ক্রম | সহজে আন্দাজযোগ্য | প্রতিটি ব্যবহারে আবার ঘটে | প্রথম ব্যবহারের মুহূর্তে, একবার |
| বাস্তবায়ন | মান পাঠানো; সবচেয়ে সস্তা | Memo-হীন thunk | Memo-সহ thunk, update |
| প্রধান ঝুঁকি | অপ্রয়োজনীয় কাজ, অসীম কাঠামো অসম্ভব | একই কাজ বারবার, অদ্ভুত alias | Space leak, অনিশ্চিত খরচ |
| উদাহরণ | C, Java, Python, JavaScript, Haat | ALGOL 60, Scala-র => T | Haskell, R-এর promise |
আরও গভীরে: Call-by-need-এর একটি পরিষ্কার formal semantics দেন John Launchbury, ১৯৯৩ সালের “A Natural Semantics for Lazy Evaluation” প্রবন্ধে: big-step নিয়মের সঙ্গে একটি heap, যেখানে প্রতিটি thunk একটি ঘর আর force করার পরে ঘরটি তার মান দিয়ে বদলে যায়, ঠিক অংশ ৩-এর stepper-এর ধাপ ৪-এর মতো। GHC-র ভেতরের যন্ত্র, Simon Peyton Jones-এর ১৯৯২ সালের প্রবন্ধে বর্ণিত STG machine, এই update-কে দক্ষ করে: thunk-এর code নিজেই তার জায়গায় মান লিখে দেয়, পরের পাঠক কোনো শর্ত না দেখে সরাসরি মান পায়। আর ১৯৭৬ সালে দুটি আলাদা দল (Henderson ও Morris, এবং Friedman ও Wise) প্রায় একই সময়ে lazy evaluator-এর ধারণা প্রকাশ করে; শেষোক্তদের প্রবন্ধের নামটিই একটি স্লোগান: “CONS should not evaluate its arguments”.
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- Call-by-name আর call-by-need-এর পার্থক্য? দুটিই দরকার হলে হিসাব করে; by-name প্রতিটি ব্যবহারে আবার, by-need প্রথমবারের ফল মনে রাখে।
- “এই program call-by-name-এ কী ছাপবে?” প্রতিটি parameter-ব্যবহারে argument-এর expression ডাকা-পক্ষের পরিবেশে নতুন করে হিসাব করুন, side effect-সহ; ক্রম ধরে লিখে যান।
- Jensen's device কী? By-name index আর by-name term নিয়ে একটি যোগফল procedure, যেখানে loop index বদলালে term-এর মানও বদলায়; Σ লেখার সাধারণ উপায়।
- Thunk কী? হিসাব না করা argument-এর code আর পরিবেশ মিলে একটি parameter-হীন closure; memo-সহ হলে প্রথম force-এর পরে মান দিয়ে বদলে যায়।
- Short-circuit কেন সাধারণ function দিয়ে লেখা যায় না? Strict ভাষায় function call-এর আগে দুই argument-ই হিসাব হয়; তাই compiler একে jump দিয়ে বিশেষভাবে বাস্তবায়ন করে।
৯ · AI-এর যুগে evaluation strategy
Evaluation strategy নিয়ে প্রশ্ন করলে AI assistant প্রায়ই আত্মবিশ্বাসী আর আংশিক ভুল উত্তর দেয়, কারণ শব্দগুলো (lazy, eager, by name, by reference) ভাষাভেদে ভিন্ন অর্থে ব্যবহৃত হয়। এই বিষয়ে বারবার দেখা ভুল:
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
| Call-by-name আর call-by-reference এক বলা, বা “Python call-by-name” | Argument-এ side effect রেখে (যেমন counter বাড়ানো) দুই ব্যবহারে কতবার চলে, নিজে চালিয়ে দেখা |
| এক ভাষার evaluation order সব ভাষায় চাপানো, যেমন “C-তে argument বাঁ থেকে ডানে হিসাব হয়” | C standard-এ ক্রম unspecified; ভাষা আর version ধরে spec পড়া, দুটি compiler-এ তুলনা |
| “Lazy মানে সবসময় দ্রুত” বা “Haskell-এ space leak হয় না” | Thunk-এর সংখ্যা আর মেমরি মেপে দেখা; strict সংস্করণের সঙ্গে আউটপুট আর খরচ তুলনা |
| Short-circuit-কে সাধারণ function দিয়ে “সমান” বলে বদলে দেওয়া | ডান পাশে ⊥ (যেমন 1 / 0) রেখে দুই সংস্করণ চালানো |
| Memoisation যোগ করে “অর্থ বদলায় না” দাবি, যখন code-এ side effect বা mutable state আছে | Jensen's device-এর মতো পরীক্ষা: by-name আর by-need-এর আউটপুট পাশাপাশি |
| বানানো compiler flag বা optimization-এর নাম, যেমন GHC-র নেই এমন strictness flag | নিজের compiler-এর documentation আর --help; flag চালিয়ে আসল আউটপুট দেখা |
AI-কে ভালোভাবে কাজে লাগানোর উপায়: ভাষা, version আর কৌশল স্পষ্ট বলে দেওয়া, প্রতিটি ধাপে কোন expression হিসাব হলো তার trace চাওয়া, আর যে দাবি চালিয়ে যাচাই করা যায় তা আলাদা করে চিহ্নিত করতে বলা।
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১ALGOL 60 call-by-name-কে ডিফল্ট করল কেন, আর পরের ভাষাগুলো সেটি ছেড়ে দিল কেন?
ALGOL 60-এর নকশাকারীরা ভাষাটিকে গাণিতিকভাবে পরিষ্কার রাখতে চেয়েছিলেন, আর procedure call-এর অর্থ দিয়েছিলেন একটি সরল নিয়মে: “copy rule”. Call-টিকে procedure-এর দেহ দিয়ে বদলে দিন, যেখানে প্রতিটি formal parameter-এর জায়গায় actual parameter-এর লেখা বসানো। এই নিয়মে আলাদা কোনো “parameter passing mechanism” বোঝাতে হয় না; গণিতে একটি সূত্রে x-এর জায়গায় একটি expression বসানোর মতোই স্বাভাবিক। By-value-কে দেখা হয়েছিল একটি অপ্টিমাইজেশন হিসেবে, যা প্রোগ্রামার value লিখে চাইবেন। Jensen's device দেখাল নিয়মটি কত শক্তিশালী: একটি procedure দিয়েই Σ, ডট প্রোডাক্ট বা যেকোনো সাধারণ যোগফল লেখা যায়।
কিন্তু বাস্তবায়ন আর ব্যবহারে দুটি বড় সমস্যা দেখা দিল। প্রথমত খরচ: প্রতিটি by-name parameter-এর প্রতিটি ব্যবহার মানে একটি thunk ডাকা, অর্থাৎ একটি ছোট subroutine call. Ingerman-এর ১৯৬১ সালের thunk কৌশল এটি সম্ভব করেছিল, কিন্তু সস্তা করেনি। দ্বিতীয়ত বোঝার কষ্ট: parameter-এর “পরিচয়” প্রতিবার নতুন করে ঠিক হয়, তাই swap(i, a[i])-এর মতো সরল কাজও ভুল হয়। পরে দেখানো হয় যে call-by-name দিয়ে সব ক্ষেত্রে ঠিক কাজ করে এমন একটি সাধারণ swap procedure লেখাই যায় না; ১৯৭০-এর দশকের একটি প্রবন্ধে এর প্রমাণ দেওয়া হয় বলে জানা যায়। একজন পাঠককে procedure-এর দেহ পড়ে বুঝতে হয় প্রতিটি parameter কতবার আর কোন অবস্থায় পড়া হবে; local reasoning ভেঙে যায়।
তাই উত্তরসূরিরা সতর্ক পথ নিল। Pascal (১৯৭০) by value আর var (by reference) রাখল; C শুধু by value, আর ঠিকানা লাগলে pointer; Ada parameter-কে in, out, in out হিসেবে চিহ্নিত করল, যেখানে প্রোগ্রামার বলেন কী চান, আর বাস্তবায়ন ঠিক করে কীভাবে। Call-by-name ফিরে এল ভিন্ন রূপে, যেখানে তার সুবিধা স্পষ্ট আর খরচ ইচ্ছাকৃত: Scala-র => T, Swift-এর @autoclosure, আর lazy ভাষার call-by-need. শিক্ষাটি ভাষা নকশার একটি স্থায়ী সূত্র: গাণিতিক সৌন্দর্য আর বাস্তবায়নের খরচ ও মানুষের বোঝার ক্ষমতা, তিনটিই ওজন করতে হয়।
মূল উপলব্ধি: call-by-name ছিল একটি সুন্দর সংজ্ঞা থেকে আসা স্বাভাবিক নিয়ম, কিন্তু তার খরচ আর অপ্রত্যাশিত alias তাকে ডিফল্ট হওয়ার অযোগ্য করেছে; আজ সেটি বেঁচে আছে শুধু যেখানে প্রোগ্রামার নিজে চেয়ে নেন।
প্র ০২Haskell ডিফল্টে lazy কেন, আর এই সিদ্ধান্তের দাম কী দাঁড়াল?
১৯৮০-এর দশকে lazy functional ভাষা নিয়ে গবেষণা চলছিল অনেক দলে, প্রত্যেকে নিজের ভাষা নিয়ে। David Turner-এর Miranda (১৯৮৫) সবচেয়ে পরিচিত ছিল, কিন্তু সেটি ছিল একটি বাণিজ্যিক পণ্য। ১৯৮৭ সালে একটি সম্মেলনে গবেষকেরা একটি সাধারণ, মুক্ত lazy ভাষা বানানোর জন্য কমিটি গঠন করেন, আর ১৯৯০ সালে Haskell 1.0-এর report প্রকাশিত হয়। অর্থাৎ laziness Haskell-এর পরে যোগ করা কোনো বৈশিষ্ট্য নয়; ভাষাটি জন্মেছিলই একটি lazy ভাষার মান (standard) হিসেবে।
Laziness-এর পক্ষে সবচেয়ে প্রভাবশালী যুক্তি দেন John Hughes, তাঁর “Why Functional Programming Matters” প্রবন্ধে (১৯৮৯ সালে প্রকাশিত)। তাঁর কথা: laziness program-কে টুকরো করার একটি নতুন “আঠা” দেয়। একটি অংশ সম্ভাব্য সব উত্তরের একটি (হয়তো অসীম) তালিকা বানাবে, আরেকটি অংশ ঠিক করবে কতগুলো লাগবে; lazy ভাষায় দুটিকে আলাদা লেখা যায় অথচ অপ্রয়োজনীয় কাজ হয় না। Strict ভাষায় এই দুই অংশকে একটি loop-এর ভেতরে জড়িয়ে লিখতে হয়। অংশ ৭-এর take 3 (filter even orderIds) এই ধারণার ক্ষুদ্র রূপ।
দাম ছিল তিনটি। এক, I/O: কখন কোন expression চলবে তা আন্দাজ করা যায় না, তাই side effect ভাষার ভেতরে সরাসরি রাখা গেল না; বহু বছরের পরীক্ষার পরে monadic IO এই সমস্যার মান্য সমাধান হয়। দুই, space leak আর অনিশ্চিত খরচ: অংশ ৮-এর foldl সমস্যা, আর profiling-এ খরচ যেখানে লেখা নয় সেখানে দেখা যাওয়া। তিন, বাস্তবায়নের জটিলতা: thunk, update আর strictness analysis ছাড়া lazy কোড ধীর। Haskell-এর অন্যতম প্রধান নকশাকার Simon Peyton Jones পরে একটি পর্যালোচনায় বলেন, laziness-এর সবচেয়ে বড় উপহার হয়তো গতি নয়, বরং এটি ভাষাটিকে purity-তে অটল রেখেছে: lazy ভাষায় লুকিয়ে side effect ঢোকানো অসম্ভব, তাই নকশাকারীরা সৎ থাকতে বাধ্য হয়েছিলেন। পরের অনেক ভাষা (যেমন PureScript, Idris) pure কিন্তু strict পথ বেছে নিয়েছে।
মূল উপলব্ধি: Haskell-এর laziness একটি গবেষণা-সম্প্রদায়ের সচেতন সিদ্ধান্ত, যা modularity দিল কিন্তু I/O, মেমরি আর গতির দাম চাইল; তার সবচেয়ে টেকসই ফল হয়তো purity-র প্রতি দায়বদ্ধতা।
প্র ০৩Strict ভাষায় laziness দরকার হলে সেটি library দিয়ে দেওয়া ভালো, নাকি ভাষার বৈশিষ্ট্য দিয়ে?
প্রায় প্রতিটি আধুনিক strict ভাষা কোনো না কোনোভাবে laziness দেয়, কিন্তু পথ আলাদা। Library-র পথ: Java-র Supplier<T> আর Stream API, Rust-এর iterator adapter (map, filter কিছুই করে না যতক্ষণ না কেউ collect বা next ডাকে), C#-এর LINQ-এর “deferred execution”. এখানে ভাষার নিয়ম বদলায় না; laziness একটি সাধারণ object, যার type দেখেই বোঝা যায় সেটি lazy. সুবিধা: পাঠক কোড দেখে খরচ আন্দাজ করতে পারেন, আর বাকি ভাষা সরল থাকে। অসুবিধা: লেখা একটু লম্বা (() -> মোড়ক, .get()), আর ভুল করে দুবার খোলা যায়।
ভাষার বৈশিষ্ট্যের পথ: Python-এর generator (yield), Scala-র lazy val আর by-name parameter, Kotlin-এর by lazy, Swift-এর @autoclosure আর lazy var, OCaml-এর lazy keyword আর Lazy.force. এখানে compiler নিজে thunk বানায়, আর কখনো কখনো ডাকা-পক্ষের কোডে কোনো চিহ্নই থাকে না। Swift-এর && এর ভালো উদাহরণ: সাধারণ function, কিন্তু ডান parameter @autoclosure, তাই ব্যবহারকারী লেখেন a && b, আর short-circuit নিজে থেকেই হয়। ঝুঁকিও এখানে: call site দেখে বোঝা যায় না argument আদৌ চলবে কি না। এজন্য Swift-এর নির্দেশিকা @autoclosure সংযত ব্যবহারের পরামর্শ দেয়।
একটি মাঝামাঝি নীতি কাজে লাগে: laziness যত বেশি দৃশ্যমান হবে (type-এ বা call site-এ চিহ্ন), তত কম অবাক হবেন পাঠক। Haat-এর বর্ধিত রূপে যদি lazy parameter যোগ করতে চান (অনুশীলন ১), প্রশ্ন উঠবে: call site-এ কি কিছু লিখতে হবে? Type-এ কি পার্থক্য থাকবে (Int বনাম Lazy Int)? Kotlin আর OCaml type-এ পার্থক্য রাখে; Scala-র by-name রাখে parameter-এর type-এ (=> Int) কিন্তু call site-এ নয়। আরেকটি বিবেচনা: compiler-এর পক্ষে কোনটি সহজ? ভাষার বৈশিষ্ট্য হলে compiler জানে এটি thunk, তাই optimize করতে পারে (যেমন strict প্রমাণ হলে মোড়ক বাদ); library হলে সেটি সাধারণ closure, বিশেষ কিছু নয়।
মূল উপলব্ধি: strict ভাষায় laziness সবচেয়ে নিরাপদ যখন তা ইচ্ছাকৃত আর চোখে পড়ে; ভাষার বৈশিষ্ট্য সুবিধা আর optimization দেয়, library স্পষ্টতা দেয়, আর ভালো নকশা দুটির মাঝে type দিয়ে সেতু বাঁধে।
প্র ০৪Strictness analysis কেন একটি lazy ভাষার compiler-এর জন্য এত গুরুত্বপূর্ণ, আর তার সীমা কোথায়?
একটি সরল lazy বাস্তবায়নে প্রতিটি argument একটি thunk: heap-এ একটি বস্তু, ভেতরে code-এর ঠিকানা আর ধরা variable-গুলো। পরে সেটি খুলতে একটি indirect call, তারপর update. x + y-এর মতো সাধারণ যোগেও এই খরচ যোগ হলে program strict সংস্করণের চেয়ে বহু গুণ ধীর হতে পারে, আর garbage collector-এর ওপর চাপ বাড়ে। Strictness analysis এই খরচ সরায়: যদি প্রমাণ হয় f তার argument সবসময় খোলে, তাহলে argument আগে হিসাব করে সরাসরি মান পাঠানো যায়। মান তখন register-এ যেতে পারে, এমনকি “unboxed” হতে পারে (একটি পূর্ণসংখ্যা নিজেই, heap-বস্তুর ভেতরে নয়)। GHC এই বিশ্লেষণকে “demand analysis” নামে আরও সূক্ষ্ম করেছে, আর worker/wrapper রূপান্তরে function-কে দুই ভাগ করে: বাইরের wrapper আগের interface রাখে, ভেতরের worker strict মান নেয়।
প্রথম প্রভাবশালী পদ্ধতি Alan Mycroft-এর (১৯৮০), abstract interpretation দিয়ে। প্রতিটি মানকে মাত্র দুটি abstract মানে নামানো হয়: 0 (“⊥ হতে পারে”) আর 1 (“নিশ্চিত মান”), আর প্রতিটি function-এর জন্য একটি abstract রূপ f# হিসাব হয়। Recursive function-এর ক্ষেত্রে f#-কে একটি fixpoint হিসেবে বের করতে হয়: সব 0 থেকে শুরু করে বারবার হিসাব যতক্ষণ না বদলায়। এই কৌশল পর্ব ৬৪-এর dataflow analysis-এর একই পরিবারের।
সীমা দুই দিক থেকে। তাত্ত্বিক দিক: “f কি সবসময় x খোলে?” program-এর আচরণ নিয়ে একটি অ-তুচ্ছ প্রশ্ন, আর Rice-এর উপপাদ্য অনুযায়ী এমন প্রশ্ন সাধারণভাবে নির্ণয়যোগ্য নয়। তাই বিশ্লেষণ অবশ্যই আনুমানিক, আর নিরাপদ হতে হলে একদিকে ভুল করতে হয়: “strict নয়” বলা সবসময় নিরাপদ (thunk থেকে যায়, শুধু ধীর), কিন্তু ভুল করে “strict” বললে program-এর অর্থ বদলে যেতে পারে, যেমন একটি অব্যবহৃত ⊥ argument-কে আগে খুলে program ভেঙে ফেলা। ব্যবহারিক দিক: higher-order function, যেখানে কোন function ডাকা হবে তা আগে জানা নেই, আর আলাদা module-এ সংকলিত কোড বিশ্লেষণকে দুর্বল করে। এজন্য প্রোগ্রামারের হাতেও উপায় রাখা হয়: seq, bang pattern (!x), আর strict data field.
মূল উপলব্ধি: strictness analysis lazy ভাষাকে ব্যবহারযোগ্য গতিতে আনে, কিন্তু এটি একটি নিরাপদ আনুমানিক বিশ্লেষণ, যার নিখুঁত রূপ গণনাযোগ্যই নয়; তাই compiler আর প্রোগ্রামার মিলে কাজটি করেন।
প্র ০৫C কেন argument-এর evaluation order নির্দিষ্ট করে না, যখন Java, JavaScript আর Haat করে? এর সঙ্গে evaluation strategy-র সম্পর্ক কী?
C-র নকশার মূল দর্শন হলো compiler-কে যতটা সম্ভব স্বাধীনতা দেওয়া, যাতে বিভিন্ন যন্ত্রে দক্ষ code তৈরি হয়। ১৯৭০ আর ১৯৮০-এর দশকের যন্ত্রগুলোর calling convention আলাদা ছিল: কিছুতে argument stack-এ ডান থেকে বাঁয়ে push করা স্বাভাবিক, কিছুতে register-এ। ক্রম বাঁধা থাকলে কিছু যন্ত্রে compiler-কে মান হিসাব করে কোথাও রেখে আবার সাজাতে হতো। তাই C standard (C17-এর §6.5.2.2 আর §6.5) argument-এর হিসাবের ক্রম unspecified রাখে, আর একই object-কে sequence point ছাড়া দুবার বদলালে সেটি undefined behavior. f(i++, i++) তাই C-তে একটি ভুল program, শুধু অনির্দিষ্ট ফলের program নয়।
Java (১৯৯৫) উল্টো সিদ্ধান্ত নিয়েছিল: “write once, run anywhere”-এর প্রতিশ্রুতি রাখতে প্রতিটি JVM-এ একই আচরণ দরকার, তাই JLS বাঁ থেকে ডানে হিসাব বাধ্যতামূলক করে। JavaScript-এর spec-ও ক্রম নির্দিষ্ট করে, কারণ বিভিন্ন browser-এ একই page একইভাবে চলা জরুরি। Haat-এর reference একই পথে (নকশা-সিদ্ধান্ত ১২), কারণ শিক্ষার ভাষায় নির্ধারিত আচরণ বেশি মূল্যবান, আর অংশ ১-এর tag program প্রতিটি back end-এ একই ক্রম দেখায়। এই নির্দিষ্টতার দাম সামান্য: আধুনিক compiler side effect নেই এমন অংশ তবু ইচ্ছামতো সাজাতে পারে, কারণ তাতে দৃশ্যমান আচরণ বদলায় না।
Evaluation strategy-র সঙ্গে সম্পর্কটি হলো: দুটিই “কখন” প্রশ্নের উত্তর, কিন্তু ভিন্ন মাত্রায়। Strategy বলে argument আদৌ আর কতবার হিসাব হবে; order বলে strict argument-গুলোর মধ্যে কোনটি আগে। দুটিই গুরুত্বপূর্ণ হয় একই কারণে: side effect. সব expression pure হলে order অপ্রাসঙ্গিক (Church–Rosser-এর আত্মা), আর strategy শুধু খরচ আর termination-এ প্রভাব ফেলে। Side effect থাকলেই দুটি প্রশ্ন program-এর অর্থের অংশ হয়ে যায়। এজন্য lazy ভাষা purity চায়, আর C-র মতো ভাষা প্রোগ্রামারকে বলে: একটি expression-এ একই জিনিস দুবার বদলাবেন না।
মূল উপলব্ধি: order আর strategy দুটিই side effect-এর সঙ্গে দেখা হলে অর্থের প্রশ্ন হয়ে ওঠে; C স্বাধীনতা দিয়ে দায় প্রোগ্রামারের ঘাড়ে রাখে, Java, JavaScript আর Haat নিশ্চয়তা দিয়ে সামান্য optimization-স্বাধীনতা ছাড়ে।
অনুশীলন
প্রথমে নিজে করুন, তারপর উত্তর খুলে মেলান। Haat-এর প্রতিটি আউটপুট সত্যিকারের Haat reference-এ, আর বাকি হিসাব ছোট Python অনুকরণে চালিয়ে মেলানো।
-
নকশা ও বাস্তবায়ন — Haat-এ call-by-need: (ক) Haat v1-এ
fn memo(th: () -> Int) -> () -> Intলিখুন, যা একটি thunk নিয়ে তার memo-সহ রূপ ফেরত দেয়: প্রথম ডাকেthচালায়, পরে মনে রাখা মান দেয়। অংশ ৩-এরpriceআরtwice_nameদিয়ে পরীক্ষা করুন। (খ) Haat-এর বর্ধিত রূপেfn f(lazy x: Int)লেখা যাবে ধরুন। এটিকে Haat v1-এ desugar করার নিয়ম দিন।(ক) দুটি
var(একটি “হয়েছে কি না”, একটি মান) আর একটি ভেতরের function, যা দুটিকেই ধরে রাখে:fn memo(th: () -> Int) -> () -> Int { var done = false; var val = 0; fn force() -> Int { if !done { val = th(); done = true; } return val; } return force; } let need = memo(fn() -> Int { return price(2, 520); }); print(twice_name(need)); print(need()); ~/haat $ python haat.py run memo.haat price computed 1872 936সত্যিকারের run (
vm-এও একই)। “price computed” মাত্র একবার:twice_name-এর দুই ব্যবহার আর পরেরneed(), তিনটি force, একটি হিসাব।disদেখায়memo-র তিনটি local (th,done,val)MAKE_CELLদিয়ে cell-এ গেছে, আরforceতাদেরLOAD_FREE/STORE_FREEদিয়ে পড়ে-লেখে, পর্ব ১৭-এর counter-এর মতোই। একটি পার্থক্য খেয়াল করুন: অংশ ৩-এর PythonThunkমান পাওয়ার পরে code ছেড়ে দিত; এখানেth-এর cell চিরকালforce-এর হাতে থাকে। Haat v1-এ “কিছু না” বোঝানোর মান নেই, তাই ছাড়া যায় না: একটি ছোট space leak.(খ) Desugar নিয়ম: (১) parameter
lazy x: T-এর type হবে() -> T. (২) দেহে x-এর প্রতিটি ব্যবহার হবেx(). (৩) প্রতিটি call-এ সেই জায়গার argument e হবেmemo(fn() -> T { return e; }), যেখানে প্রতিটি T-এর জন্য একটিmemoলাগবে (Haat v1-এ generic নেই)। (৪)lazy x-এ assignment নিষিদ্ধ, যা Haat-এ parameter-এর জন্য এমনিতেই সত্য (নকশা-সিদ্ধান্ত ১৯)। নিয়ম ৩-এmemoবাদ দিলে ফল call-by-name. এক জায়গায় সতর্কতা: e-এর নামগুলো ডাকা-পক্ষের scope-এ খোঁজা হবে, কারণ anonymous function সেখানেই লেখা, আর Haat-এর closure lexical; তাই ALGOL-এর “নাম বদল” সমস্যা আপনা থেকেই এড়ানো যায়। -
ভুল খুঁজুন ও প্রমাণ: একজন দাবি করেন, “call-by-need শুধু call-by-name-এর একটি optimization; দুটি সবসময় একই ফল দেয়।” (ক) Jensen's device দিয়ে দাবিটির একটি পাল্টা উদাহরণ দিন। (খ) কোন শর্তে দাবিটি সত্য, তার প্রমাণের রূপরেখা দিন।
(ক)
sum(i, 1, 3, x[i]), x = 936, 990, 200. Call-by-name-এ term প্রতিবার নতুন i দিয়ে খোলে: 936 + 990 + 200 = 2126. Call-by-need-এ term প্রথম force-এ (i = 1) 936 হয়ে মনে থাকে, তাই 936 × 3 = 2808. একটি ছোট Python অনুকরণে সত্যিকারের run দুটি সংখ্যাই দেয়। দাবিটি ভুল, কারণ term-এর মান i-এর ওপর নির্ভর করে, আর i দুই force-এর মাঝে বদলেছে। আরেকটি পাল্টা উদাহরণ side effect: argument যদি কিছু ছাপে, by-name দুবার ছাপবে, by-need একবার (অংশ ৩-এর Haat run).(খ) দাবি: যদি argument-এর হিসাব একটি pure expression হয় (কোনো side effect নেই) আর তার পরিবেশের কোনো variable দুই force-এর মাঝে বদলাতে না পারে, তাহলে by-name আর by-need একই ফল দেয়। প্রমাণের রূপরেখা:
- একটি thunk = (expression e, পরিবেশ ρ)। by-name-এ k-তম force হিসাব করে e-কে পরিবেশ ρ-এর সেই মুহূর্তের অবস্থায়।
- শর্ত অনুযায়ী ρ-এর কোনো ঘর বদলায় না, আর e-এর হিসাব নিজেও কিছু বদলায় না। তাই প্রতিটি force একই অবস্থা থেকে শুরু হয়।
- হিসাব deterministic (একই অবস্থা থেকে একই e একই ফল দেয়), তাই সব force একই মান v দেয়, বা সবগুলোই ⊥ হয়।
- By-need প্রথম force-এ v পায় আর পরেরগুলোতে v ফেরত দেয়: by-name-এর প্রতিটি force-এর ফলের সমান। Side effect নেই, তাই force-এর সংখ্যা বাদে বাইরে থেকে কোনো পার্থক্য দেখা যায় না। ∎
Haskell-এ শর্তটি ভাষাই নিশ্চিত করে (pure expression, অপরিবর্তনীয় variable), তাই সেখানে call-by-need সত্যিই call-by-name-এর একটি নিরাপদ optimization. ALGOL 60-এ শর্তটি নেই, তাই সেখানে নয়।
-
আউটপুট অনুমান করুন: একটি কল্পিত ভাষা Haat-এর মতো, কিন্তু evaluation strategy বদলানো যায়।
next()একটি global counter (শুরুতে 0) এক বাড়িয়ে নতুন মান ফেরত দেয়।fn f(a: Int, b: Int) -> Int { return a + a + b; }. তিন কৌশলে (call-by-value বাঁ থেকে ডানে, call-by-name, call-by-need) নিচের দুটি call-এর ফল আর শেষে counter-এর মান কী? (ক)f(next(), 10)(খ)f(next(), next()); প্রতিটি call-এর আগে counter আবার 0.কৌশল (ক) ফল, counter (খ) ফল, counter Call-by-value 12, 1 4, 2 Call-by-name 13, 2 6, 3 Call-by-need 12, 1 4, 2 ছোট Python অনুকরণে সত্যিকারের run-এ ঠিক এই সংখ্যাগুলো। (ক) by value: a = next() = 1, b = 10; 1 + 1 + 10 = 12. By name: প্রথম a → next() = 1, দ্বিতীয় a → next() = 2, b = 10; 1 + 2 + 10 = 13, counter 2. By need: a প্রথমবার 1, তারপর মনে রাখা 1; 12. (খ) by value: বাঁ থেকে ডানে a = 1, b = 2; 1 + 1 + 2 = 4. By name: a → 1, a → 2, b → 3; 6. By need: a → 1 (মনে রাখা), আবার 1, তারপর b → 2; 4. এখানে by value আর by need-এর ফল মিলেছে, কিন্তু কারণ আলাদা: by need-এ b-এর হিসাব হয়েছে দেহের ভেতরে, a-এর পরে। দেহ যদি
return b + a + a;হতো, by value তবু 4 দিত (b = 2, a = 1), কিন্তু by need দিত b = 1, a = 2, অর্থাৎ 1 + 2 + 2 = 5: side effect থাকলে ব্যবহারের ক্রমই হিসাবের ক্রম। -
Trace — normal বনাম applicative order: নিচের দুটি λ-term দুই নীতিতে ধাপে ধাপে কমান, আর ধাপ গুনুন। Ω = (λw. w w)(λw. w w). (ক) (λx. λy. x) z Ω (খ) (λx. x x) ((λy. y) z). কোনটি থেকে call-by-need-এর প্রয়োজন বোঝা যায়?
লেখকের ছোট Python reducer-এ সত্যিকারের run-এর ধাপ:
(ক) normal: (λx.λy.x) z Ω → (λy.z) Ω → z ২ ধাপ applicative: (λx.λy.x) z Ω → (λy.z) Ω → (λy.z) Ω → … শেষ হয় না (খ) normal: (λx.x x) ((λy.y) z) → ((λy.y) z) ((λy.y) z) → z ((λy.y) z) → z z ৩ ধাপ applicative: (λx.x x) ((λy.y) z) → (λx.x x) z → z z ২ ধাপ(ক)-তে applicative order প্রথম ধাপে বাঁয়ের redex কমায় (কারণ z আর λ দুটিই আগেই normal form), তারপর argument Ω-কে কমাতে চায়, আর Ω প্রতিবার নিজেকেই ফেরত দেয়। Normal order Ω-কে কখনো ছোঁয় না, কারণ λy. z তার argument ফেলে দেয়। (খ) উল্টো শিক্ষা দেয়: normal order argument
(λy.y) z-কে দুই জায়গায় কপি করে, আর দুবার কমায়; applicative একবার। Call-by-need-এর প্রয়োজন বোঝা যায় দুটি মিলিয়ে: (ক)-এর মতো অপ্রয়োজনীয় argument এড়াতে normal order দরকার, আর (খ)-এর মতো কপি এড়াতে sharing দরকার। Call-by-need দুটিই দেয়: (খ)-তে একটি ভাগ করা thunk একবার কমে z হতো, মোট ২ ধাপ।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমCall-by-need ভাষায় twice(price(2, 520)) চলার সময় argument-এর thunk-এর জীবনের ঘটনাগুলো সঠিক ক্রমে সাজান (twice-এর দেহ x + x; ▲▼ চেপে সরান)
- Argument-এর code আর ডাকা-পক্ষের পরিবেশ মিলে একটি thunk তৈরি হয়
- twice-এর দেহ শুরু হয়, তখনো price চলেনি
- বাঁ পাশের x thunk-টিকে force করে, price একবার চলে
- Thunk তার মান 936 মনে রাখে আর code ছেড়ে দেয়
- ডান পাশের x মনে রাখা 936 পায়, ফল 1872
Haat-এ fn first(a: Int, b: Int) -> Int { return a; } ঘোষিত থাকলে print(first(5, 1 / 0)); চালালে কী হয়?
- 5 ছাপা হয়, কারণ b ব্যবহারই হয় না
- Type error, কারণ 1 / 0 Int নয়
- Runtime error: division by zero, first ডাকার আগেই
- 0 ছাপা হয়, কারণ শূন্য দিয়ে ভাগের ফল 0 ধরা হয়
একটি ভাষায় next() একটি global counter (শুরুতে 0) এক বাড়িয়ে নতুন মান ফেরত দেয়, আর fn twice(x: Int) -> Int { return x + x; }. ভাষাটি call-by-name হলে twice(next())-এর ফল কী?
- 2
- 3
- 4
- 0
Lazy ভাষার বাস্তবায়নে “thunk” বলতে কী বোঝায়?
- হিসাব না করা expression-এর code আর পরিবেশ মিলে একটি বস্তু, যা দরকার হলে force করে মান পাওয়া যায়
- Function-এ পাঠানো argument-এর মানের একটি কপি
- Argument-এর source code-এর লেখা, যা পরে আবার parse করা হয়
- একটি function call-এর stack frame
ALGOL 60-এ sum(i, 1, 3, x[i]) দিয়ে x[1] + x[2] + x[3] পাওয়ার কৌশলটি (Jensen's device) কোন বৈশিষ্ট্যের ওপর নির্ভর করে?
- term by value পাঠানো
- term call-by-need-এ পাঠানো
- ALGOL 60-এর একটি বিশেষ array-যোগ নির্দেশ
- Index আর term দুটিই by name, তাই term প্রতিবার বদলানো i দিয়ে নতুন করে হিসাব হয়
Lambda calculus-এ একটি term-এর normal form থাকলে কোন reduction নীতি নিশ্চিতভাবে সেখানে পৌঁছায়?
- Applicative order
- Normal order
- সবসময় সবচেয়ে ডানের redex আগে
- যেকোনো নীতি, কারণ Church–Rosser theorem সব পথকে সমান করে
Haskell-এ foldl (+) 0 [1 .. 10000000] optimization ছাড়া চালালে অনেক মেমরি লাগতে পারে। এর সবচেয়ে সঠিক কারণ আর প্রতিকার কোনটি?
- পুরো তালিকা আগে মেমরিতে তৈরি হয়; প্রতিকার ছোট তালিকা
- Integer overflow; প্রতিকার Integer type
- Accumulator-এ thunk-এর শিকল জমে (space leak); প্রতিকার strict foldl'
- Garbage collector বন্ধ থাকে; প্রতিকার GC চালু করা
Haat-এর reference compiler n != 0 && total / n > 500-কে bytecode-এ কীভাবে বাস্তবায়ন করে?
- বাঁ পাশ হিসাবের পরে JUMP_IF_FALSE দিয়ে ডান পাশ লাফিয়ে যায়; আলাদা AND opcode নেই
- দুই পাশ আগে হিসাব করে একটি AND opcode চালায়
- ডান পাশ আগে হিসাব করে, তারপর বাঁ পাশ
- &&-কে একটি built-in function হিসেবে CALL করে
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Strict (call-by-value): argument আগে, একবার; f(⊥) = ⊥. Non-strict: call-by-name (প্রতি ব্যবহারে আবার) আর call-by-need (প্রথমবার, তারপর মনে রাখা)। Haat strict আর বাঁ থেকে ডানে:
first(5, 1 / 0)division by zero দেয়। - Thunk = code + পরিবেশ, একটি parameter-হীন closure. Memo-সহ thunk মানেই call-by-need; Haat-এ
() -> Intআর একটিmemoদিয়ে হাতে বানানো যায়। - ALGOL 60 ডিফল্টে by-name: Jensen's device একটি procedure দিয়ে Σ লেখে (2126), কিন্তু
swap(i, a[i])ভুল করে; খরচ আর অনিশ্চয়তায় পরের ভাষাগুলো by value নিল। - Normal order normal form থাকলে পৌঁছায় কিন্তু কপি করা argument বারবার কমায়; applicative order একবার কমায় কিন্তু অব্যবহৃত Ω-তে আটকে যায়; call-by-need দুটির লাভ মেলায়।
- Strict ভাষার lazy ফাঁক:
if,&&/||(Haat-এJUMP_IF_FALSE), generator, default parameter, CPython 3.14-এর annotation. Laziness-এর দাম space leak আর অনিশ্চিত খরচ; strictness analysis নিরাপদ জায়গায় আগেই হিসাব করে।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ২০ · Primitive type — integer, floating-point (IEEE 754), boolean আর characterপরবর্তী পর্বমডিউল ৪-এর শুরু: মানের ভেতরের গঠন।
- প্রোগ্রামিং ভাষা ও কম্পাইলার · কোর্স হোম৮৬টি পর্বপুরো কোর্সের মানচিত্র আর Haat প্রজেক্টের পথ।
- গণনার মডেল — lambda calculus আর Turing machineপাশের ট্র্যাকβ-reduction, normal আর applicative order-এর তত্ত্ব।
- Python-এর iterator আর generatorপাশের ট্র্যাকLazy sequence হাতে-কলমে,
yieldথেকে pipeline. - C-র preprocessor আর macroপাশের ট্র্যাকলেখা-বসানো macro আর তার ফাঁদ, call-by-name-এর আত্মীয়।