এই পর্বে যা শিখবেন
- Pure function, side effect আর referential transparency-র সংজ্ঞা দেওয়া, আর একটি function pure কি না তা কোড দেখে বিচার করা
- Map, filter আর fold দিয়ে একটি বাস্তব হিসাব লেখা, আর একই হিসাব loop দিয়ে লেখার সঙ্গে সমান কি না প্রমাণ আর random ডেটায় যাচাই করা
- foldl আর foldr-এর পার্থক্য ধাপে ধাপে হিসাব করা, আর map fusion-এর মতো সূত্র structural induction দিয়ে প্রমাণ করা
- Currying, partial application আর function composition Haat-এর closure দিয়ে বাস্তবায়ন করা
- Immutability, persistent data structure আর laziness-এর খরচ ও লাভ বুঝে AI-এর “functional মানেই দ্রুত” ধরনের দাবি যাচাই করা
১ · Functional ধাঁচ কী — হিসাবের খাতা বনাম রান্নার রেসিপি
বাজারঘরের হিসাবরক্ষক দিনের শেষে একটি খাতা খোলেন। প্রতিটি অর্ডার এলে তিনি “মোট” ঘরের পুরোনো সংখ্যা কেটে নতুন সংখ্যা লেখেন। খাতার প্রতিটি পাতায় একটিই সত্য: এই মুহূর্তের মোট। আগের মোট জানতে চাইলে কাটা দাগের নিচে খুঁজতে হয়। এটি imperative ধাঁচ: একটি অবস্থা (state) আছে, আর একের পর এক আদেশ (command) সেই অবস্থা বদলায়। এই মডিউলের প্রথম পর্ব, পর্ব ০৭ (Imperative আর procedural programming), এই ধাঁচ বিস্তারিত দেখায়, একই বাজারঘরের হিসাব দিয়ে।
এবার রান্নাঘরের রেসিপির কথা ভাবুন: “চাল আর পানি দিলে ভাত; ভাত আর ডাল দিলে খিচুড়ি”। রেসিপি কোনো হাঁড়ির অবস্থা বলে না, বলে কোন উপকরণ থেকে কী তৈরি হয়। একই উপকরণ দিলে যেকোনো রান্নাঘরে, যেকোনো দিন একই খিচুড়ি। Functional programming প্রোগ্রামকে এই রেসিপির মতো দেখে: প্রতিটি অংশ একটি function, যা কিছু মান নিয়ে নতুন মান দেয়, আর কোনো খাতা কাটে না।
Functional programming একটি programming paradigm, যেখানে (১) হিসাবের মূল একক হলো function, যা মান নিয়ে মান ফেরত দেয়; (২) function নিজেও একটি মান (first-class function), তাই তাকে পাঠানো, ফেরত দেওয়া আর জোড়া লাগানো যায়; (৩) অবস্থা বদলানোর বদলে নতুন মান তৈরি করা হয়; (৪) পুনরাবৃত্তি আসে recursion বা map, fold-এর মতো function থেকে, assignment-ভিত্তিক loop থেকে নয়।
এটি একটি declarative ধাঁচ: “কী চাই” বলা বেশি, “কীভাবে, কোন ক্রমে” বলা কম। SQL-এর SELECT … WHERE বা পর্ব ১০-এর (Logic programming) Prolog-ও declarative, তবে তাদের ভিত্তি আলাদা: SQL relational algebra, Prolog যুক্তির নিয়ম, আর functional ভাষা lambda calculus. Lambda calculus-কে গণনার মডেল হিসেবে আছে গণনার তত্ত্ব কোর্সের পর্ব ৪৯-এ; এই কোর্সে ভাষার ভিত্তি হিসেবে আসবে পর্ব ৪৩-এ (Lambda calculus প্রোগ্রামিং ভাষার ভিত্তি হিসেবে)।
ইতিহাসের সারসংক্ষেপ পর্ব ০২-এ আছে: Church-এর lambda calculus (১৯৩০-এর দশক), McCarthy-র LISP (১৯৫৮–৬০), Milner-এর ML (১৯৭৩), আর Haskell (১৯৯০)। আজ প্রায় সব বড় ভাষা এই ধাঁচের অংশবিশেষ নিয়েছে: Python-এর lambda আর functools, JavaScript-এর arrow function আর reduce, Java 8 (২০১৪)-এর lambda আর stream, C++11-এর lambda. তাই এই পর্বের লক্ষ্য একটি নতুন ভাষা শেখানো নয়, বরং পাঁচটি ধারণা বোঝা, যা আপনি যেকোনো ভাষায় চিনতে আর ব্যবহার করতে পারবেন:
🧪 Pure function
ফল শুধু argument-এর ওপর নির্ভর করে; বাইরে কিছু বদলায় না। অংশ ২–৩।
referential transparency🔁 Higher-order function
Function নেয় বা ফেরত দেয়: map, filter, fold. অংশ ৪–৫।
fold = loop-এর সাধারণ রূপ🧩 Currying আর composition
বড় function ছোট টুকরো জুড়ে, আর argument এক এক করে। অংশ ৬–৭।
closure-এর ওপর দাঁড়ানো🧊 Immutability
মান বদলায় না; নতুন সংস্করণ পুরোনোর সঙ্গে অংশ ভাগ করে। অংশ ৮।
persistent data structureপুরো পর্বে একটি কাজই বারবার আসবে, মডিউল ২-এর সব পর্বে যেটি আলাদা paradigm-এ সমাধান করা হচ্ছে: বাজারঘরের অর্ডারের তালিকা; প্রতিটি অর্ডারে কয়েকটি লাইন (পণ্য, পরিমাণ, একক দাম); লাইনের দাম যোগ করে অর্ডারের মোট, মোট ১০০০ টাকা বা বেশি হলে ১০% ছাড়, শুধু একটি জেলার অর্ডার রেখে সব যোগ। ডেটা চারটি অর্ডার: ঢাকা (চাল 2 × 520), রাজশাহী (ডাল 3 × 120, তেল 1 × 180), ঢাকা (চিনি 4 × 150, চা 2 × 250), ঢাকা (লবণ 5 × 40). ঢাকার উত্তর হবে 2126 টাকা; নিচে তিন ভাষায় সত্যিই চালিয়ে মেলাবেন।
২ · Pure function আর side effect
গণিতের function, যেমন f(x) = x², একটি টেবিলের মতো: প্রতিটি x-এর জন্য একটি নির্দিষ্ট উত্তর। আজ f(3) = 9, কাল-ও 9; আর f(3) হিসাব করলে পৃথিবীতে আর কিছু বদলায় না। প্রোগ্রামিং ভাষার “function” অনেক বেশি স্বাধীন: সে ফাইলে লিখতে পারে, global variable বদলাতে পারে, ঘড়ি পড়তে পারে। গণিতের function-এর মতো আচরণ করা function-কে বলে pure.
একটি function f pure, যদি দুটি শর্ত মানে: (১) নির্ধারিত ফল: একই argument-এ f সবসময় একই মান ফেরত দেয়; ফল argument ছাড়া অন্য কোনো বদলাতে পারা অবস্থার ওপর নির্ভর করে না। (২) কোনো side effect নেই: f-কে ডাকলে মান ফেরত দেওয়া ছাড়া বাইরে দেখা যায় এমন কিছু ঘটে না, যেমন variable বা পাওয়া object বদলানো, ছাপা, ফাইল বা নেটওয়ার্কে লেখা, exception ছোড়া।
| Function (Python) | Pure? | কারণ |
|---|---|---|
def line(q, u): return q * u | হ্যাঁ | ফল শুধু q, u থেকে; বাইরে কিছু বদলায় না |
def disc(t): return t - t // 10 if t >= 1000 else t | হ্যাঁ | শাখা থাকলেও ফল নির্ধারিত |
def show(t): print(t); return t | না | ছাপা একটি side effect |
def cut(t): return t - t * rate // 100 | না | rate বাইরের বদলাতে পারা variable |
def add(cart, x): cart.append(x); return cart | না | পাওয়া list বদলায় (caller-এর জিনিস) |
def stamp(): return time.time() | না | একই (শূন্য) argument-এ প্রতিবার আলাদা ফল |
একটি সূক্ষ্ম কথা: function-এর ভেতরে একটি local variable বদলালে function impure হয় না, যদি বাইরে থেকে তা দেখা না যায়। একটু পরের foldl ভেতরে z = f(z, x) লেখে, তবু বাইরে থেকে সে pure. Purity একটি “বাইরের চুক্তি”, ভেতরের লেখার ধরন নয়।
Haat কি pure ভাষা? না — আর কেন
Haat-এ function first-class, কিন্তু Haat একটি pure ভাষা নয়: এতে var, assignment আর print আছে, আর spec v1 বলে closure বাইরের variable “by reference” ধরে রাখে, অর্থাৎ নিজের কপি নয়, একই variable. ফলে একটি anonymous function বাইরের var-এর ওপর নির্ভর করলে তার ফল সময়ের সঙ্গে বদলায়। নিচের program কোর্সের Haat reference বাস্তবায়নে সত্যিকারের run (CPython 3.14.4-এ, haat.py run আর haat.py vm দুটিতেই একই ফল):
var rate = 10;
let cut = fn(t: Int) -> Int { return t - t * rate / 100; };
let a = cut(1040);
rate = 20;
let b = cut(1040);
print(a);
print(b);
print(a == b);~/haat $ python haat.py run rate.haat
936
832
false
একই cut(1040), দুই উত্তর: 936 আর 832. cut শর্ত (১) ভাঙে, কারণ তার ফল rate-এর ওপর নির্ভর করে, যা argument নয়। আর rate = 20; লাইনটি নিজেই একটি side effect. উল্টো দিকে, rate যদি let হতো, Haat-এর checker তাকে বদলাতেই দিত না (reference-এর সত্যিকারের বার্তা: 4:1: error: cannot assign to 'rate': it is declared with 'let'), আর cut pure হয়ে যেত। Haat-এর নকশা তাই “ডিফল্টে immutable নাম (let), দরকার হলে স্পষ্টভাবে var”: ভাষা purity চাপিয়ে দেয় না, কিন্তু সহজ পথটিকে pure পথ বানায়। Haat-এর এই সিদ্ধান্তের যুক্তি দেখেছেন পর্ব ০৬-এ (ভাষা নকশার লক্ষ্য আর আপস).
Purity থেকে কী পাওয়া যায়
- Test সহজ: argument দিন, ফল মেলান; কোনো আগের অবস্থা সাজাতে হয় না।
- Memoization নিরাপদ: একই argument-এর ফল মনে রেখে আবার ব্যবহার করা যায়, কারণ উত্তর বদলাবে না। Impure function-এ এটি ভুল উত্তর দেয় (উপরের
cut-কে memoize করলেrateবদলের পরও 936 আসত)। - Parallel চালানো নিরাপদ: দুটি pure call-এর মধ্যে ভাগ করা অবস্থা নেই, তাই কোনটি আগে চলল তাতে কিছু আসে যায় না। Thread আর data race-এর সমস্যা আসবে পর্ব ১১-এ (Concurrent programming-এর মডেল)।
- Compiler-এর স্বাধীনতা: pure call-এর ফল ব্যবহার না হলে call-টি মুছে ফেলা যায়, একই call দুবার থাকলে একবার হিসাব করা যায়। এগুলো পর্ব ৬৫-এর (Optimization) dead code elimination আর common subexpression elimination; impure call-এ compiler এগুলো করতে পারে না।
৩ · Referential transparency — সমান দিয়ে সমান বদলানো
স্কুলের বীজগণিতে x = 3 হলে 2x + x²-এ সবখানে x-এর জায়গায় 3 বসিয়ে দেন, আর কেউ জিজ্ঞেস করে না “কোন x-টা আগে বসাবেন”। প্রোগ্রামেও এই স্বাধীনতা পাওয়া যায়, যদি expression-গুলো একটি বিশেষ গুণ মানে।
একটি expression e referentially transparent, যদি e-এর মান v হয় আর যেকোনো প্রসঙ্গ (context) C[ ]-এর জন্য ⟦C[e]⟧ = ⟦C[v]⟧. এখানে C[ ] মানে একটি program, যার মধ্যে একটি ফাঁকা ঘর আছে; C[e] মানে ঘরে e বসানো, আর ⟦…⟧ মানে “program-এর অর্থ” (তার আউটপুট আর আচরণ)। সহজ কথায়: e-কে তার মান দিয়ে বদলে দিলে program-এর কোনো পার্থক্য কেউ টের পায় না।
যে ভাষায় সব expression এই গুণ মানে, সেখানে equational reasoning চলে: গণিতের মতো সমান দিয়ে সমান বদলে বদলে program-এর ফল হিসাব বা প্রমাণ করা। কোর্সের নমুনা program bazar.haat-এর প্রথম হিসাব দিয়ে দেখুন; তারপর একটি impure function-এ একই কৌশল কীভাবে ভেঙে পড়ে। শেষ দুটি সংখ্যা (3 আর 2) Haat reference-এর সত্যিকারের run থেকে।
1fn price(qty: Int, unit: Int) -> Int2fn delivery(total: Int) -> Int3price(2, 520) + delivery(price(2, 520))4var n = 0; let next = fn() -> Int5print(next() + next());6n = 0; print(2 * next());
| expression | |
| নিয়ম |
- শুরু।
bazar.haat-এর প্রথম হিসাব।price(2, 520)দুবার আছে।priceআরdeliveryদুটিই pure: শুধু argument পড়ে, কিছু বদলায় না। - Function-এর দেহ বসানো। qty = 2, unit = 520 বসালে p = 1040; 1040 ≥ 1000, তাই ফল 1040 − 1040 / 10 = 936. বাঁ দিকের call-টি এখন শুধু 936.
- একই call, একই মান। ডান দিকের
price(2, 520)আবার হিসাব করার দরকার নেই: referential transparency বলে একে 936 দিয়ে বদলানো যায়। Compiler-ও ঠিক এই যুক্তিতে একই হিসাব একবার করে। - delivery. 936 ≥ 1000 মিথ্যা, তাই
delivery(936)= 60. পুরো expression এখন 936 + 60. - উত্তর 996. Program না চালিয়েই, শুধু সমান দিয়ে সমান বদলে উত্তর বের হলো; reference বাস্তবায়নও প্রথম লাইনে 996 ছাপে।
- Impure function.
nextপ্রতিবারnএক বাড়িয়ে ফেরত দেয়। প্রথম call 1, দ্বিতীয় call 2 (Haat-এ বাঁ থেকে ডানে মূল্যায়ন), তাইnext() + next()= 3. সত্যিকারের run-এ ছাপা হয়েছে 3. - বদলানো ভেঙে পড়ে। বীজগণিতে x + x = 2x. কিন্তু
nআবার 0 করে2 * next()চালালে ফল 2, 3 নয়।next()-কে “তার মান” দিয়ে বদলানো যায় না, কারণ তার কোনো একটি মান নেই। Side effect থাকলে equational reasoning চলে না।
এখান থেকে একটি গুরুত্বপূর্ণ সংযোগ: পর্ব ২৬-এ (Expression আর evaluation order) দেখবেন, C-তে f() + g()-এ কোনটি আগে চলবে তা ভাষা নির্ধারণ করে না। যদি f আর g pure হয়, এই অনিশ্চয়তায় কিছু আসে যায় না; সমস্যা হয় শুধু side effect থাকলে। Pure ভাষায় তাই evaluation order প্রায় অদৃশ্য একটি সিদ্ধান্ত, যা ভাষাকে lazy হওয়ার স্বাধীনতাও দেয় (অংশ ৮)।
৪ · Higher-order function — map, filter আর fold দিয়ে বাজারঘরের হিসাব
একটি higher-order function অন্য function-কে argument হিসেবে নেয়, বা function ফেরত দেয়। তিনটি সবচেয়ে পরিচিত: map (প্রতিটি উপাদানে একই function চালিয়ে নতুন তালিকা), filter (শর্ত মানা উপাদানগুলো রেখে নতুন তালিকা), আর fold বা reduce (একটি accumulator নিয়ে পুরো তালিকাকে একটি মানে নামানো)। LISP-এর mapcar থেকে আজকের Python, JavaScript আর Java-র stream পর্যন্ত এই তিনটি প্রায় অপরিবর্তিত। বাজারঘরের কাজটি তিনটি ধাপের একটি পাইপলাইন হয়ে যায়:
ছবি ৯.১ — বাজারঘরের হিসাব: filter → map → fold
প্রতিটি ধাপ একটি নতুন মান বানায়; আগের তালিকা অপরিবর্তিত থাকে।
প্রথমে Python-এ, ব্রাউজারের ভেতরে (Pyodide). অর্ডার রাখা হয়েছে NamedTuple-এ, যা একটি immutable record: তৈরির পর ঘর বদলানো যায় না। functools.partial একটি function-এর প্রথম কয়েকটি argument আগেই বসিয়ে নতুন function বানায় (partial application). pipe কয়েকটি function বাঁ থেকে ডানে জোড়া লাগায়, আর নিজেও reduce দিয়ে লেখা: function-এর তালিকার ওপর একটি fold!
from functools import reduce, partial
from typing import NamedTuple
class Line(NamedTuple): # an immutable record (a tuple)
item: str; qty: int; unit: int # unit price in taka
class Order(NamedTuple):
district: str; lines: tuple
ORDERS = (Order("Dhaka", (Line("rice", 2, 520),)),
Order("Rajshahi", (Line("lentil", 3, 120), Line("oil", 1, 180))),
Order("Dhaka", (Line("sugar", 4, 150), Line("tea", 2, 250))),
Order("Dhaka", (Line("salt", 5, 40),)))
def line_total(ln): return ln.qty * ln.unit # pure
def discounted(t): return t - t // 10 if t >= 1000 else t # pure (t >= 0)
def order_total(o): return discounted(sum(map(line_total, o.lines)))
def from_district(d, o): return o.district == d
def district_sum(orders, d):
kept = filter(partial(from_district, d), orders) # partial application
return reduce(lambda acc, t: acc + t, map(order_total, kept), 0)
print("order totals:", list(map(order_total, ORDERS)))
print("Dhaka:", district_sum(ORDERS, "Dhaka"), " Rajshahi:", district_sum(ORDERS, "Rajshahi"))
def pipe(*fs): return reduce(lambda f, g: lambda x: g(f(x)), fs) # left to right
dhaka = pipe(partial(filter, partial(from_district, "Dhaka")),
partial(map, order_total), sum)
print("pipe:", dhaka(ORDERS), " same input again:", dhaka(ORDERS))
try:
ORDERS[0].lines[0].qty = 3 # try to mutate
except AttributeError as e:
print("AttributeError:", e)আসল আউটপুট (ব্রাউজারের Python):
order totals: [936, 540, 990, 200]
Dhaka: 2126 Rajshahi: 540
pipe: 2126 same input again: 2126
AttributeError: can't set attribute
চারটি অর্ডারের ছাড়-পরবর্তী মোট 936, 540, 990, 200; ঢাকার যোগফল 2126, ছবি ৯.১-এর সঙ্গে হুবহু। pipe দিয়ে বানানো dhaka একটি নতুন function, যা কোনো অবস্থা রাখে না, তাই একই ইনপুটে দুবার ডাকলেও একই 2126. শেষ লাইনে অর্ডারের একটি ঘর বদলানোর চেষ্টা AttributeError দিয়েছে: tuple-ভিত্তিক record-এ assignment নিষেধ। Haat-এর / আর Python-এর // ঋণাত্মক সংখ্যায় আলাদা, কিন্তু এখানে সব মোট অঋণাত্মক, তাই দুটি একই ফল দেয়। Python-এর map, filter আর functools-এর বিস্তারিত ব্যবহার আছে Python কোর্সের পর্ব ৪১-এ (lambda, functools আর itertools).
এবার একই হিসাব JavaScript-এ (ECMAScript 2025, আপনার ব্রাউজারে)। এখানে fromDistrict curried: fromDistrict("Dhaka") একটি নতুন function ফেরত দেয়, যা একটি অর্ডার নিয়ে true/false বলে। শেষে দুটি পরীক্ষা: reduceRight (JavaScript-এর foldr) আর Object.freeze-এর সীমা।
"use strict";
const orders = Object.freeze([
{ district: "Dhaka", lines: [["rice", 2, 520]] },
{ district: "Rajshahi", lines: [["lentil", 3, 120], ["oil", 1, 180]] },
{ district: "Dhaka", lines: [["sugar", 4, 150], ["tea", 2, 250]] },
{ district: "Dhaka", lines: [["salt", 5, 40]] },
]);
const add = (a, b) => a + b;
const lineTotal = ([, qty, unit]) => qty * unit; // pure
const discounted = t => (t >= 1000 ? t - Math.trunc(t / 10) : t);
const orderTotal = o => discounted(o.lines.map(lineTotal).reduce(add, 0));
const fromDistrict = d => o => o.district === d; // curried
const districtSum = d => os =>
os.filter(fromDistrict(d)).map(orderTotal).reduce(add, 0);
console.log("order totals:", JSON.stringify(orders.map(orderTotal)));
const dhakaSum = districtSum("Dhaka"); // partial application
console.log("Dhaka:", dhakaSum(orders), " Rajshahi:", districtSum("Rajshahi")(orders));
// reduceRight is foldr: compare on a non-associative operation
const sub = (a, b) => a - b;
console.log("reduce (-):", [1, 2, 3].reduce(sub, 0), " reduceRight (-):", [1, 2, 3].reduceRight((a, x) => x - a, 0));
try { orders.push({ district: "Sylhet", lines: [] }); }
catch (e) { console.log(e.constructor.name + ":", e.message); }
orders[0].district = "Sylhet"; // freeze is shallow!
console.log("after shallow change, Dhaka:", dhakaSum(orders));আসল আউটপুট (ব্রাউজারের JavaScript):
order totals: [936,540,990,200]
Dhaka: 2126 Rajshahi: 540
reduce (-): -6 reduceRight (-): 2
TypeError: Cannot add property 4, object is not extensible
after shallow change, Dhaka: 1190
প্রথম দুই লাইন Python-এর সঙ্গে হুবহু মেলে: দুই ভাষা, একই 2126. districtSum("Dhaka") একটি function ফেরত দিয়েছে, যাকে dhakaSum নামে রেখে পরে ডাকা হলো; currying থেকে partial application বিনা খরচে পাওয়া যায়। তৃতীয় লাইন অংশ ৫-এর মূল কথা আগেই দেখিয়ে দেয়: বিয়োগে বাঁ দিক থেকে ভাঁজ −6, ডান দিক থেকে 2. চতুর্থ লাইনে frozen array-তে নতুন অর্ডার ঢোকানো TypeError দিয়েছে (strict mode-এ; strict না হলে চুপচাপ কিছুই হতো না)। কিন্তু শেষ লাইনটি সতর্কবার্তা: Object.freeze শুধু ওপরের স্তর জমায়, ভেতরের object নয়। প্রথম অর্ডারের জেলা বদলে গেল, আর একই dhakaSum(orders) এখন 1190 (990 + 200). JavaScript-এ functional ধাঁচের আরও বিস্তার আছে JavaScript কোর্সের পর্ব ২৩-এ.
Type-এর চোখে higher-order function
Higher-order function-এর type-এ তির (→) একাধিকবার আসে। Haskell বা ML-এর ধাঁচে map-এর type লেখা হয় ∀α β. (α → β) → List α → List β: “যেকোনো type α আর β-এর জন্য, α থেকে β-এর একটি function আর α-এর একটি তালিকা দিলে β-এর একটি তালিকা”। এখানে ∀ (“সব”) বলে map একটি generic function; এই ধরনের type কীভাবে নিজে থেকে বের করা যায়, তা পর্ব ৩৫-এর (Type inference — Hindley–Milner) বিষয়। Haat v1-এ generic নেই, তাই প্রতিটি function type লিখে দিতে হয়, যেমন (Int) -> Int. Haat-এর call-এর typing rule (Γ মানে type environment, Γ ⊢ e : τ পড়ুন “Γ-এর তথ্যে e-এর type τ”):
T-Call-এ f নিজে একটি expression, নাম হওয়া জরুরি নয়; তাই charge(10)(1000)-এর মতো call-এর call বৈধ। T-Fn বলে anonymous function-এর দেহ type check হয় বাইরের Γ-তে parameter-গুলো যোগ করে; দেহ বাইরের নামও দেখতে পায়, আর সেখান থেকেই closure আসে (পর্ব ১৭-এ বিস্তার)।
৫ · Fold — loop-এর সাধারণ রূপ, আর foldl বনাম foldr
Fold-কে কাপড় ভাঁজ করার মতো ভাবুন: একটি লম্বা শাড়ি এক প্রান্ত থেকে ভাঁজ করতে করতে একটি ছোট বান্ডিলে আনা। কোন প্রান্ত থেকে শুরু করছেন, তাতে বান্ডিলের চেহারা আলাদা হতে পারে। তালিকার fold দুই রকম, আর তাদের সংজ্ঞা দুটি সমীকরণে লেখা যায় (Haskell-এর রীতিতে x:xs মানে প্রথম উপাদান x, বাকি তালিকা xs):
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
খুলে লিখলে: foldl f z [x1, x2, x3] = f (f (f z x1) x2) x3, আর foldr f z [x1, x2, x3] = f x1 (f x2 (f x3 z)). Python-এর functools.reduce আর JavaScript-এর reduce হলো foldl; JavaScript-এর reduceRight হলো foldr.
নিচের stepper-এ [1, 2, 3] তালিকায় বিয়োগ দিয়ে দুটি fold পাশাপাশি চালান। খেয়াল করুন foldl কীভাবে একটি loop-এর মতো এগোয়, আর foldr কীভাবে আগে সব কল জমিয়ে তারপর ভেতর থেকে উত্তর নিয়ে ফেরে।
1foldl f z [] = z2foldl f z (x:xs) = foldl f (f z x) xs3foldr f z [] = z4foldr f z (x:xs) = f x (foldr f z xs)
| হিসাব | |
| accumulator | |
| বাকি তালিকা |
- foldl, প্রথম উপাদান। z = 0 থেকে শুরু, f z x = z − x. প্রথম ধাপে 0 − 1 = −1, আর বাকি তালিকা [2, 3]. লক্ষ করুন, এটি সংজ্ঞার দ্বিতীয় সমীকরণ, আর পরের call-ই শেষ কাজ: একটি tail call.
- দ্বিতীয় উপাদান। −1 − 2 = −3. foldl কোনো কিছু জমিয়ে রাখে না; শুধু accumulator বদলে পরের উপাদানে যায়, ঠিক একটি loop-এর মতো।
- তৃতীয় উপাদান। −3 − 3 = −6. বন্ধনী বাঁ দিকে জমে: ((0 − 1) − 2) − 3.
- foldl-এর ফল −6. তালিকা ফাঁকা, তাই প্রথম সমীকরণ: ফল accumulator নিজেই, −6. Python-এর
reduceআর JavaScript-এরreduce-ও −6 দেয়। - foldr: আগে খোলা। এখানে f x a = x − a. দ্বিতীয় সমীকরণ বারবার খুলে পাই 1 − (2 − (3 − foldr f 0 [])). কোনো বিয়োগ এখনো হয়নি; তিনটি call অসমাপ্ত অবস্থায় stack-এ অপেক্ষা করছে।
- সবচেয়ে ভেতরে। foldr f 0 [] = 0, তাই 3 − 0 = 3. এবার জমা call-গুলো একে একে শেষ হবে, ভেতর থেকে বাইরে।
- এক ধাপ বাইরে। 2 − 3 = −1.
- foldr-এর ফল 2. 1 − (−1) = 2. বন্ধনী ডান দিকে জমে, তাই উত্তর foldl-এর −6 থেকে আলাদা। বিয়োগ সংযোজী (associative) নয়, তাই দিকটি গুরুত্বপূর্ণ; যোগ বা গুণে দুই দিকই একই উত্তর দিত।
প্রমাণ — loop আসলে একটি foldl
বাজারঘরের imperative সংস্করণ লেখে s = 0; for x in xs: s = s + g(x). Functional সংস্করণ লেখে reduce(lambda a, x: a + g(x), xs, 0). দুটি কি সবসময় একই? “কয়েকটি ইনপুটে মিলেছে” প্রমাণ নয়; প্রমাণটি ছোট আর সুন্দর।
যেকোনো function f, শুরুর মান z আর সসীম তালিকা xs = [x1, …, xn]-এর জন্য, program acc = z; for x in xs: acc = f(acc, x) শেষে acc = foldl f z xs.
প্রমাণ (loop invariant, k-এর ওপর induction). দাবি I(k): k বার ঘোরার পর acc = foldl f z [x1, …, xk] (প্রথম k উপাদান)। এখানে একটি সহায়ক তথ্য লাগবে, L: foldl f z (ys ++ [y]) = f (foldl f z ys) y, যা ys-এর দৈর্ঘ্যের ওপর induction-এ সংজ্ঞা থেকে সরাসরি আসে।
- ভিত্তি, k = 0: কোনো ঘোরার আগে acc = z, আর foldl f z [] = z (সংজ্ঞার প্রথম সমীকরণ)। I(0) সত্য।
- ধাপ: ধরি I(k) সত্য, অর্থাৎ acc = foldl f z [x1, …, xk]. (k + 1)-তম ঘোরায় acc হয় f(acc, xk+1) = f (foldl f z [x1, …, xk]) xk+1.
- L অনুযায়ী এটি foldl f z [x1, …, xk+1]. তাই I(k + 1) সত্য।
- Loop ঠিক n বার ঘোরে (সসীম তালিকা), তাই শেষে I(n): acc = foldl f z xs. ∎
এই প্রমাণে f সম্পর্কে কিছুই ধরা হয়নি, শুধু এটুকু যে f pure: loop-এর ভেতরের f যদি বাইরের কোনো অবস্থা বদলাত, তাহলে “f(acc, x)”-এর মান একটি নির্দিষ্ট সংখ্যা হতো না, আর ধাপ ২-এর সমীকরণ লেখাই যেত না। Loop invariant নিয়ে বিস্তারিত পদ্ধতি আসবে পর্ব ৪২-এ (Axiomatic semantics — Hoare logic আর loop invariant).
প্রমাণ — map fusion
পরের সূত্রটি functional compiler-এর একটি বাস্তব optimization-এর ভিত্তি: দুটি পরপর map-কে একটি map-এ মেশানো, যাতে মাঝের তালিকা তৈরিই না হয়।
যেকোনো pure function f, g আর সসীম তালিকা xs-এর জন্য map f (map g xs) = map (f ∘ g) xs, যেখানে (f ∘ g)(x) = f(g(x)) আর map-এর সংজ্ঞা: map h [] = [], map h (x:xs) = h x : map h xs.
প্রমাণ (xs-এর ওপর structural induction: আগে ফাঁকা তালিকা, তারপর ধরে নেওয়া যে xs-এর জন্য সত্য, আর দেখানো যে x:xs-এর জন্যও সত্য)।
- ভিত্তি, xs = []: বাঁ দিক map f (map g []) = map f [] = []. ডান দিক map (f ∘ g) [] = []. সমান।
- ধাপ: ধরি map f (map g xs) = map (f ∘ g) xs (induction hypothesis). তাহলে map f (map g (x:xs)) = map f (g x : map g xs) = f (g x) : map f (map g xs).
- Hypothesis বসিয়ে: = f (g x) : map (f ∘ g) xs = (f ∘ g) x : map (f ∘ g) xs = map (f ∘ g) (x:xs). ∎
এই প্রমাণের প্রতিটি “=” সমান দিয়ে সমান বদলানো, অর্থাৎ অংশ ৩-এর equational reasoning. f বা g যদি ছাপত (side effect), তাহলে বাঁ দিকে সব g আগে, তারপর সব f ছাপা হতো, আর ডান দিকে g, f পালা করে; ছাপার ক্রম বদলে যেত, আর “অর্থ একই” দাবিটি মিথ্যা হতো। Structural induction-এর পদ্ধতি নিয়ে বিস্তারিত আছে বিচ্ছিন্ন গণিত কোর্সের পর্ব ১২-এ.
আরেকটি জানা ফল (Bird-এর বইয়ে “first duality theorem” নামে): যদি ⊕ সংযোজী হয় আর e তার একক (e ⊕ x = x ⊕ e = x), তাহলে প্রতিটি সসীম তালিকায় foldr (⊕) e xs = foldl (⊕) e xs. যোগ (একক 0), গুণ (একক 1), max এই শর্ত মানে; বিয়োগ মানে না, তাই stepper-এ দুই উত্তর আলাদা। এবার এসব দাবি random ডেটায় যাচাই করুন:
import random, sys
from functools import reduce
def foldl(f, z, xs): # ((z f x1) f x2) ... — a loop
for x in xs:
z = f(z, x)
return z
def foldr(f, z, xs): # x1 f (x2 f (... f z)) — recursion
return z if not xs else f(xs[0], foldr(f, z, xs[1:]))
print("foldl (-):", foldl(lambda a, x: a - x, 0, [1, 2, 3]))
print("foldr (-):", foldr(lambda x, a: x - a, 0, [1, 2, 3]))
def disc(t): return t - t // 10 if t >= 1000 else t
def loop_sum(orders, d): # imperative version
s = 0
for dist, t in orders:
if dist == d:
s = s + disc(t)
return s
def fold_sum(orders, d): # functional version
return reduce(lambda a, t: a + disc(t), [t for x, t in orders if x == d], 0)
random.seed(2026); same = 0
for trial in range(1000):
orders = [(random.choice(["Dhaka", "Rajshahi", "Khulna"]), random.randint(0, 3000))
for _ in range(random.randint(0, 30))]
r = foldr(lambda o, a: a + (disc(o[1]) if o[0] == "Dhaka" else 0), 0, orders)
same += loop_sum(orders, "Dhaka") == fold_sum(orders, "Dhaka") == r
print("loop == foldl == foldr on", same, "of 1000 random order lists")
xs = list(range(1, 3001))
print("foldl on 3000 items:", foldl(lambda a, x: a + x, 0, xs))
try: foldr(lambda x, a: x + a, 0, xs)
except RecursionError: print(f"foldr on 3000 items: RecursionError (limit {sys.getrecursionlimit()})")আসল আউটপুট (ব্রাউজারের Python):
foldl (-): -6
foldr (-): 2
loop == foldl == foldr on 1000 of 1000 random order lists
foldl on 3000 items: 4501500
foldr on 3000 items: RecursionError (limit 1000)
প্রথম দুই লাইন stepper-এর −6 আর 2. তৃতীয় লাইনে ১০০০টি random অর্ডার-তালিকায় (seed 2026, ০ থেকে ৩০টি অর্ডার, তিন জেলা) loop, foldl আর foldr তিনটিই একই উত্তর দিয়েছে: উপপাদ্য ৯.১ আর duality-র (যোগ সংযোজী, একক 0) একটি পরীক্ষা। পরীক্ষা প্রমাণ নয়, কিন্তু প্রমাণে কোনো ভুল ধারণা থাকলে প্রায়ই এভাবে ধরা পড়ে। শেষ দুই লাইন একটি ব্যবহারিক সত্য: loop-রূপী foldl ৩০০০ উপাদানে নির্বিঘ্নে 4501500 দিয়েছে, কিন্তু recursive foldr প্রতিটি উপাদানের জন্য একটি অসমাপ্ত call জমায়, আর CPython-এর ১০০০-এর recursion সীমা পেরিয়ে RecursionError দিয়েছে।
শেষ লাইনটি একটি বড় প্রশ্ন তোলে: functional ভাষা loop ছাড়া recursion দিয়ে চলে, তাহলে তাদের stack ফুরিয়ে যায় না কেন? উত্তর tail call: foldl-এর recursive রূপে পরের call-ই শেষ কাজ, তাই পুরোনো frame ফেলে দেওয়া যায়, আর recursion কার্যত একটি loop হয়ে যায়। Scheme-এর মানদণ্ড এটি বাধ্যতামূলক করে; OCaml আর Haskell-এর compiler-ও এটি করে। CPython ইচ্ছা করেই করে না (Guido van Rossum-এর ২০০৯ সালের ব্যাখ্যা: traceback-এ সব frame দেখা যাওয়া জরুরি); JavaScript-এর ES2015 মানদণ্ডে proper tail call থাকলেও কার্যত শুধু Safari-র engine এটি চালু করেছে। Haat-ও spec অনুযায়ী ১০০০টি nested call-এর পর stack overflow দেয়। Tail call-এর বাস্তবায়ন আসবে পর্ব ৩২-এ (Recursion আর tail call); recursion-এর মৌলিক ধারণা আছে DSA কোর্সের পর্ব ০৭-এ.
৬ · Currying, partial application আর composition
বাজারঘরে ঈদের সময় একটি ছাড়ের নিয়ম থাকে: “১০% ছাড়, যদি মোট ১০০০ টাকা বা বেশি হয়”। এখানে তিনটি তথ্য: হার (10), সীমা (1000) আর অর্ডারের মোট। প্রথম দুটি পুরো মৌসুমে একই থাকে, শুধু মোট বদলায়। Currying ঠিক এই কাঠামো ধরে: তিনটি argument একসঙ্গে না নিয়ে একটি একটি করে নেওয়া, যাতে প্রথম দুটি বসিয়ে একটি “ঈদের ছাড়” function বানিয়ে রাখা যায়।
Currying: type (A, B, C) -> R-এর একটি function-কে type (A) -> (B) -> (C) -> R-এর function-এ রূপান্তর, অর্থাৎ f(a, b, c)-এর বদলে f(a)(b)(c). Partial application: একটি function-এর কিছু argument বসিয়ে বাকি argument নেওয়া নতুন function পাওয়া, যেমন g = f(a)(b), পরে g(c). Curried function-এ partial application স্বাভাবিকভাবেই আসে; অন্য function-এ এর জন্য সাহায্যকারী লাগে, যেমন Python-এর functools.partial.
নামটি যুক্তিবিদ Haskell Curry-র নামে, যদিও ধারণাটি আগে Moses Schönfinkel-এর ১৯২৪ সালের কাজে আর তারও আগে Gottlob Frege-র লেখায় ছিল বলে ধরা হয়। Lambda calculus-এ প্রতিটি function এক argument-এর, তাই সেখানে currying-ই একাধিক argument পাঠানোর উপায়; Haskell আর OCaml-এ প্রতিটি function ডিফল্টে curried. Haat-এ আমরা নিজে লিখি, closure দিয়ে। নিচের program কোর্সের Haat reference-এ সত্যিকারের run (run আর vm দুটিতেই একই ফল):
fn charge(rate: Int) -> (Int) -> (Int) -> Int {
return fn(limit: Int) -> (Int) -> Int {
return fn(total: Int) -> Int {
if total >= limit { return total - total * rate / 100; }
return total;
};
};
}
let festive = charge(10)(1000);
print(festive(1040));
print(festive(990));
print(charge(20)(500)(600));~/haat $ python haat.py run curry.haat
936
990
480
Return type-এ (Int) -> (Int) -> Int মানে “Int নিয়ে এমন একটি function দেয়, যা Int নিয়ে Int দেয়”; তির ডান দিকে জোড়া লাগে (right-associative), ঠিক reference-এর README-র সিদ্ধান্ত ৭ অনুযায়ী বাড়তি বন্ধনী লাগে না। ভেতরে আসলে কী ঘটে, ধাপে ধাপে দেখুন:
1fn charge(rate: Int) -> …2 return fn(limit: Int) -> …3 return fn(total: Int) -> Int4 if total >= limit { … }5 return total;6let festive = charge(10)(1000);7print(festive(1040));8print(festive(990));9print(charge(20)(500)(600));
| call | |
| environment | |
| ফেরত মান |
- প্রথম argument.
charge(10)চলে, rate = 10 দিয়ে একটি environment frame তৈরি হয়। দেহ কিছু হিসাব করে না, শুধু একটি anonymous function ফেরত দেয়; সেই function আর এই frame মিলে একটি closure, নাম দিই C1. - দ্বিতীয় argument. C1(1000) চলে: নতুন frame {limit=1000}, যার বাইরের দিকে C1-এর ধরে রাখা {rate=10}. আবার একটি closure ফেরত আসে, C2; এটিই
festive. এই মুহূর্তে partial application সম্পূর্ণ: হার আর সীমা বসানো, শুধু মোট বাকি। - তৃতীয় argument.
festive(1040): frame {total=1040}, তার বাইরে {limit=1000}, তার বাইরে {rate=10}. দেহের প্রতিটি নাম এই শিকল ধরে খোঁজা হয় (lexical scoping). - দেহ চলে। 1040 ≥ 1000 সত্য, তাই 1040 − 1040 × 10 / 100 = 1040 − 104 = 936. ফল
bazar.haat-এরprice(2, 520)-এর সঙ্গে মেলে, যা একই নিয়ম ১০% হারে লেখা। - একই closure, নতুন মোট।
festive(990): একই {limit=1000} আর {rate=10}, শুধু নতুন {total=990}. 990 ≥ 1000 মিথ্যা, তাই 990 অপরিবর্তিত। rate আর limit কেউ বদলায় না, তাই festive pure. - আলাদা শিকল।
charge(20)(500)(600)সম্পূর্ণ নতুন frame বানায়: {rate=20}, {limit=500}. 600 − 600 × 20 / 100 = 480.festive-এর শিকল এতে একটুও বদলায়নি; প্রতিটি closure নিজের environment ধরে রাখে।
Closure কীভাবে environment ধরে রাখে, তার ভাষা-স্তরের পুরো আলোচনা পর্ব ১৭-এ (Closure — lexical environment ধরে রাখা function), আর interpreter-এর ভেতরে তার বাস্তবায়ন পর্ব ৫৭-এ। এখানে মনে রাখার কথা: currying কোনো জাদু নয়; এটি নিছক “function ফেরত দেওয়া function”, আর closure ছাড়া এটি সম্ভব নয়। C-তে function pointer আছে, কিন্তু closure নেই, তাই C-তে currying-এর জন্য environment হাতে একটি struct-এ বয়ে নিতে হয়। আর object-oriented ভাষায় একই কাজ করে একটি object, যার field-এ rate আর limit থাকে: closure আর object দুটিই “ডেটা আর আচরণ একসঙ্গে”, শুধু দুই দিক থেকে দেখা (object-এর দিকটি পর্ব ০৮-এ)।
Composition — ছোট function জুড়ে বড় function
গণিতে (f ∘ g)(x) = f(g(x)): আগে g, তারপর f. Haat-এ এটি একটি higher-order function, যা দুটি function নিয়ে একটি নতুন function ফেরত দেয়: fn compose(f: (Int) -> Int, g: (Int) -> Int) -> (Int) -> Int { return fn(x: Int) -> Int { return f(g(x)); }; }. Composition সংযোজী: (f ∘ g) ∘ h = f ∘ (g ∘ h), তাই লম্বা শিকলে বন্ধনী লাগে না; উপরের Python-এর pipe একই ধারণা, শুধু বাঁ থেকে ডানে পড়ার জন্য উল্টো ক্রমে। অনুশীলন ১-এ compose দিয়ে বাজারঘরের ছাড় আর ডেলিভারি চার্জ জুড়বেন। গণিতের দিক থেকে function composition আছে বিচ্ছিন্ন গণিত কোর্সের পর্ব ১৬-এ.
৭ · Haat-এ functional ধাঁচ — array ছাড়া তালিকা, function দিয়ে
Haat v1-এ array বা list নেই। তবু কি functional ধাঁচে বাজারঘরের কাজ লেখা যায়? যায়, আর কৌশলটি শিক্ষণীয়: তালিকাকে ডেটা হিসেবে না রেখে তার fold হিসেবে রাখা। orders একটি function, যা একটি “step” function আর শুরুর accumulator নিয়ে চারটি অর্ডারের প্রতিটিতে step চালায়। তালিকা মানে “আমাকে একটি step দিন, আমি নিজেকে ভাঁজ করে দেব”। Lambda calculus-এ সংখ্যা আর তালিকা এভাবেই শুধু function দিয়ে লেখা হয় (Church encoding).
তারপর দুটি higher-order function: mapping(f, step) প্রতিটি মোটে আগে f চালিয়ে তারপর step-এ পাঠায়, আর keeping(wanted, step) শুধু চাওয়া জেলার অর্ডার step-এ পাঠায়। দুটিই একটি step নিয়ে নতুন step ফেরত দেয়; Clojure ভাষায় এমন জিনিসকে বলে transducer. সুবিধা: map আর filter-এর জন্য কোনো মাঝের তালিকা তৈরি হয় না, সব কাজ একটি fold-এর ভেতরেই। পুরো program, কোনো var বা assignment ছাড়া:
// বাজারঘর, functional ধাঁচে: array নেই, তাই তালিকাটিই একটি fold
fn line(qty: Int, unit: Int) -> Int { return qty * unit; }
fn discounted(t: Int) -> Int {
if t >= 1000 { return t - t / 10; }
return t;
}
// চারটি অর্ডার: প্রতিটিতে step(acc, district, total) চলে
fn orders(step: (Int, Str, Int) -> Int, acc: Int) -> Int {
let a1 = step(acc, "Dhaka", line(2, 520));
let a2 = step(a1, "Rajshahi", line(3, 120) + line(1, 180));
let a3 = step(a2, "Dhaka", line(4, 150) + line(2, 250));
return step(a3, "Dhaka", line(5, 40));
}
fn mapping(f: (Int) -> Int, step: (Int, Str, Int) -> Int) -> (Int, Str, Int) -> Int {
return fn(acc: Int, d: Str, t: Int) -> Int { return step(acc, d, f(t)); };
}
fn keeping(wanted: Str, step: (Int, Str, Int) -> Int) -> (Int, Str, Int) -> Int {
return fn(acc: Int, d: Str, t: Int) -> Int {
if d == wanted { return step(acc, d, t); }
return acc;
};
}
fn add(acc: Int, d: Str, t: Int) -> Int { return acc + t; }
fn count(acc: Int, d: Str, t: Int) -> Int { return acc + 1; }
print(orders(keeping("Dhaka", mapping(discounted, add)), 0));
print(orders(keeping("Rajshahi", mapping(discounted, add)), 0));
print(orders(keeping("Dhaka", count), 0));
print(orders(mapping(discounted, add), 0));সত্যিকারের run, কোর্সের Haat reference বাস্তবায়নে (CPython 3.14.4); check প্রথমে সব type মিলিয়ে ok বলে, তারপর tree-walking interpreter আর bytecode VM হুবহু একই আউটপুট দেয়:
~/haat $ python haat.py check fold.haat
ok
~/haat $ python haat.py run fold.haat
2126
540
3
2666
~/haat $ python haat.py vm fold.haat
2126
540
3
2666
ঢাকা 2126, ঠিক Python আর JavaScript-এর মতো: তিন ভাষা, তিনটি আলাদা বাস্তবায়ন, একই উত্তর। একই orders দিয়ে শুধু step বদলে রাজশাহীর মোট (540), ঢাকার অর্ডারের সংখ্যা (3) আর সব জেলার মোট (2666) পাওয়া গেল: higher-order function-এর আসল শক্তি এই পুনর্ব্যবহার। প্রথম লাইনের হিসাব ভেতরে কীভাবে এগোয়, দেখুন:
1step = keeping("Dhaka", mapping(…))2a1 = step(0, "Dhaka", 1040)3a2 = step(a1, "Rajshahi", 540)4a3 = step(a2, "Dhaka", 1100)5return step(a3, "Dhaka", 200)
| keeping | |
| mapping | |
| acc |
- Step বানানো।
mapping(discounted, add)একটি closure, যা মনে রাখে f = discounted আর step = add.keepingতাকে মুড়ে আরেকটি closure বানায়, যা মনে রাখে wanted = "Dhaka". কোনো অর্ডার এখনো ছোঁয়া হয়নি; acc = 0. - প্রথম অর্ডার। ঢাকা, মোট 2 × 520 = 1040. keeping মিলিয়ে দেখে, জেলা মেলে, তাই ভেতরের step-এ পাঠায়; mapping 1040-কে discounted করে 936; add যোগ করে: acc = 936.
- দ্বিতীয় অর্ডার। রাজশাহী, 3 × 120 + 1 × 180 = 540. keeping-এর শর্ত মিথ্যা, তাই সে acc অপরিবর্তিত ফেরত দেয়: 936. mapping আর add এই অর্ডারে চলেই না; filter এখানে একটি শর্তযুক্ত step.
- তৃতীয় অর্ডার। ঢাকা, 4 × 150 + 2 × 250 = 1100 ≥ 1000, তাই 1100 − 110 = 990. acc = 936 + 990 = 1926.
- চতুর্থ অর্ডার। ঢাকা, 5 × 40 = 200; ছাড় নেই। acc = 1926 + 200 = 2126.
ordersএই মান ফেরত দেয়। - ছাপা।
print2126 ছাপে। প্রতিটি a1, a2, a3 একটিlet, কোনোটি বদলায়নি: accumulator “বদলায়” নতুন নাম দিয়ে, যা functional ধাঁচের loop-এর স্বাভাবিক রূপ।
একটি compiler-এর দৃষ্টিতে লক্ষ করুন: এই program-এ প্রতিটি mapping আর keeping call একটি নতুন closure, অর্থাৎ heap-এ একটি নতুন object, আর প্রতিটি অর্ডারে তিনটি indirect call. Functional ধাঁচের এই খরচ কমাতে বাস্তব compiler inlining (পর্ব ৬৭) আর closure-কে সরল function-এ নামানোর কৌশল ব্যবহার করে; আর ছোট ছোট closure দ্রুত তৈরি-ধ্বংস হয় বলে garbage collector-এর ভূমিকা বড় (পর্ব ৭৫)।
৮ · Immutability, persistent data structure আর laziness
লাইব্রেরির তাকে একটি বইয়ের নতুন সংস্করণ এলে পুরোনোটি ফেলে দেওয়া হয় না; দুটিই পাশাপাশি থাকে, আর যে পাঠক আগের সংস্করণের পৃষ্ঠা নম্বর ধরে নোট লিখেছেন, তাঁর নোট ভুল হয়ে যায় না। Immutable ডেটা এভাবে কাজ করে: “বদল” মানে একটি নতুন সংস্করণ, পুরোনোটি অক্ষত। প্রশ্ন হলো খরচ: প্রতিবার পুরো তালিকা কপি করলে ১০ লাখ অর্ডারের তালিকায় একটি অর্ডার যোগ করতেও ১০ লাখ ঘর কপি করতে হবে।
সমাধান structural sharing: নতুন সংস্করণ পুরোনো সংস্করণের না-বদলানো অংশ কপি না করে সরাসরি ভাগ করে নেয়। ভাগ করা নিরাপদ, কারণ কেউই সেই অংশ বদলাতে পারে না। সবচেয়ে সরল উদাহরণ LISP-এর cons list: প্রতিটি ঘর (cons cell) একটি মান আর পরের ঘরের ঠিকানা।
ছবি ৯.২ — তিনটি সংস্করণ, একটিই শৃঙ্খল
v2 সামনে একটি ঘর যোগ করে; v3 প্রথম ঘর বাদ দেয়। কোনো ঘর কপি হয়নি।
নিচের কোডে Python-এর tuple দিয়ে এই cons list, আর সঙ্গে laziness-এর একটি ঝলক। Lazy evaluation মানে মান দরকার না পড়া পর্যন্ত হিসাব না করা। Haskell ডিফল্টে lazy; Python-এর generator একই ধারণার ছোট রূপ, যা দিয়ে একটি অসীম তালিকাও লেখা যায়, যতক্ষণ আপনি তার সসীম অংশই চান।
import itertools
def cons(head, tail): return (head, tail) # an immutable list cell
def to_list(xs):
out = []
while xs is not None:
out.append(xs[0]); xs = xs[1]
return out
v1 = cons(936, cons(990, cons(200, None))) # Dhaka order totals
v2 = cons(540, v1) # "add" an order in front
v3 = v1[1] # "drop" the first order
print("v1:", to_list(v1), " v2:", to_list(v2), " v3:", to_list(v3))
print("v2's tail is v1:", v2[1] is v1, " v3 is inside v1:", v3 is v1[1])
def order_ids(): # an endless supply, made lazily
n = 0
while True:
n += 1
print(" made id", n)
yield n
even_x100 = (i * 100 for i in order_ids() if i % 2 == 0)
print("first two:", list(itertools.islice(even_x100, 2)))আসল আউটপুট (ব্রাউজারের Python):
v1: [936, 990, 200] v2: [540, 936, 990, 200] v3: [990, 200]
v2's tail is v1: True v3 is inside v1: True
made id 1
made id 2
made id 3
made id 4
first two: [200, 400]
তিনটি সংস্করণ একসঙ্গে বেঁচে আছে, আর is (একই object কি না) প্রমাণ করে কোনো কপি হয়নি: v2-এর লেজ হুবহু v1, আর v3 হুবহু v1-এর ভেতরের ঘর। দ্বিতীয় অংশে order_ids কখনো শেষ হয় না, তবু program থেমেছে: generator শুধু চাওয়া হলে একটি একটি করে মান বানায়। দুটি জোড় id চাওয়া হয়েছে, তাই ঠিক ৪টি id তৈরি হলো, পঞ্চমটি কখনো নয়। এখানে “made id” ছাপা একটি side effect, যা ইচ্ছা করে রাখা হয়েছে যাতে কখন হিসাব হলো দেখা যায়; আর ঠিক এই কারণেই lazy ভাষা side effect-এর সঙ্গে মেলে না: কখন কোন লাইন চলবে, তা আগে থেকে বলা কঠিন। Python-এর generator নিয়ে বিস্তার Python কোর্সের পর্ব ৩৬-এ; strict, lazy আর call-by-need-এর পুরো তুলনা পর্ব ১৯-এ (Evaluation strategy).
তালিকার সামনে যোগ সস্তা হলেও মাঝখানের i-তম ঘর বদলাতে আগের i-টি ঘর নতুন করে বানাতে হয়। তাই বাস্তব persistent ডেটা কাঠামো গাছ ব্যবহার করে: একটি ঘর বদলালে শুধু মূল থেকে সেই পাতা পর্যন্ত পথ (log n-টি ঘর) নতুন হয়, বাকি গাছ ভাগ করা থাকে। এই ধারণার তাত্ত্বিক ভিত্তি Driscoll, Sarnak, Sleator ও Tarjan-এর “Making Data Structures Persistent” (১৯৮৬ সালের সম্মেলনে, ১৯৮৯ সালে জার্নালে); Chris Okasaki-র Purely Functional Data Structures (১৯৯৮) বইটি একে functional ভাষার হাতে তুলে দেয়; আর Clojure (২০০৭) একে ভাষার ডিফল্ট ডেটা কাঠামো বানায়। Immutability-র ভাষা-নকশাগত আপস (Haat-এর let/var, Rust-এর ownership) দেখেছেন পর্ব ০৬-এ।
“Immutable” শব্দের মাত্রা ভাষাভেদে আলাদা। Haat-এর let নামটিকে নতুন মানে বসাতে দেয় না, আর Haat v1-এর সব মান (Int, Bool, Str, function) নিজেই অপরিবর্তনীয়, তাই এখানে নিশ্চয়তা পূর্ণ। Python-এর tuple নিজে বদলায় না, কিন্তু ভেতরে একটি list থাকলে সেই list বদলানো যায়। JavaScript-এর const শুধু নামটিকে আটকায়, object-কে নয়; Object.freeze শুধু ওপরের স্তর আটকায় (উপরের run-এ 1190). Java-র final-ও নামটিকেই আটকায়। AI বা কোনো লেখা “এটি immutable” বললে জিজ্ঞেস করুন: নাম, ওপরের স্তর, নাকি পুরো গভীরতা?
আরও গভীরে: Functional ভাষার compiler দেখায় purity কীভাবে optimization-এর দরজা খোলে। Haskell-এর GHC “rewrite rule” দিয়ে উপপাদ্য ৯.২-এর মতো সূত্র (যেমন foldr/build নিয়মের “short-cut fusion”, Gill, Launchbury ও Peyton Jones, ১৯৯৩) সরাসরি কোডে প্রয়োগ করে, ফলে map আর fold-এর শিকলে মাঝের তালিকা তৈরিই হয় না। উল্টো দিকের কৌশলও আছে: Koka আর Lean 4 ভাষার reference counting-ভিত্তিক “functional but in-place” পদ্ধতি (Perceus, ২০২১ সালের গবেষণাপত্র) চলার সময় দেখে কোনো মান-এর একমাত্র মালিক থাকলে নতুন কপি না বানিয়ে পুরোনো জায়গাতেই বদল করে; বাইরে থেকে program pure থাকে, ভেতরে চলে imperative গতিতে।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- Pure function কী, উদাহরণ দিন। একই argument-এ একই ফল আর কোনো side effect নেই;
line(q, u) = q * upure,printকরা বা global বদলানো function নয়। - Referential transparency কী? একটি expression-কে তার মান দিয়ে বদলালে program-এর অর্থ বদলায় না; side effect থাকলে এটি ভাঙে।
- foldl আর foldr-এর পার্থক্য? বন্ধনী বাঁ বনাম ডান দিকে জমে; [1, 2, 3]-এ বিয়োগে −6 বনাম 2; foldl tail-recursive, foldr নয়।
- Currying আর partial application কি এক? না; currying একটি রূপান্তর (f(a, b) → f(a)(b)), partial application কিছু argument বসিয়ে নতুন function পাওয়া।
- Higher-order function কী? যে function function নেয় বা ফেরত দেয়: map, filter, reduce, compose.
৯ · AI-এর যুগে functional programming
AI assistant-কে “এই loop-টা functional করে দাও” বললে সে প্রায় সবসময় সুন্দর দেখতে একটি map/filter/reduce-এর শিকল দেয়। দেখতে সুন্দর মানেই সঠিক নয়। এই বিষয়ে AI-এর বারবার দেখা ভুল:
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
Loop-কে reduce-এ বদলানোর সময় শুরুর মান বাদ দেওয়া; ফাঁকা তালিকায় তখন Python-এ TypeError, JavaScript-এ “Reduce of empty array with no initial value” | ফাঁকা তালিকা আর এক উপাদানের তালিকা দিয়ে চালানো |
| “reduce আর reduceRight একই উত্তর দেয়” বলা, বা parallel reduce-এ অ-সংযোজী operation (বিয়োগ, float-এর যোগ) দেওয়া | বিয়োগ দিয়ে দুই দিকে চালানো; float-এ যোগের ক্রম বদলে দেখা |
| এক ভাষার নিয়ম সবখানে চাপানো: “Python tail call optimize করে”, “JavaScript-এ tail call সব browser-এ আছে” | ভাষা আর version ধরে documentation দেখা; ১০০০০ গভীর recursion চালিয়ে দেখা |
| “const/freeze/final দিয়ে object immutable হয়ে গেছে” দাবি | ভেতরের স্তরের একটি ঘর বদলে দেখা (উপরের 1190-এর মতো) |
Side effect-ওয়ালা function-কে map-এর ভেতরে রাখা, বা Python-এর map-এর lazy iterator দুবার ব্যবহার করা | Function-টি pure কি না সংজ্ঞা ৯.২ দিয়ে বিচার; iterator দ্বিতীয়বার পড়ে দেখা |
| “Functional সংস্করণ সবসময় দ্রুত” বা “সবসময় ধীর” দাবি, সংখ্যা ছাড়া | নিজের যন্ত্রে, নিজের ডেটায় দুটি সংস্করণ মেপে দেখা |
AI-কে ভালোভাবে কাজে লাগানোর উপায়: refactor চাওয়ার সঙ্গে প্রমাণের উপায়ও চাওয়া, তারপর নিজে চালিয়ে মেলানো।
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১FORTRAN-এর জনক John Backus কেন তাঁর Turing Award বক্তৃতায় functional ধাঁচের পক্ষে কথা বললেন?
John Backus-এর দল ১৯৫৭ সালে FORTRAN দিয়ে প্রথম সফল উচ্চ-স্তরের ভাষা উপহার দিয়েছিল, যা ছিল পুরোদস্তুর imperative: variable, assignment আর loop. তাই ১৯৭৭ সালে Turing Award পাওয়ার পর তাঁর বক্তৃতা অনেককে অবাক করে। শিরোনাম ছিল “Can Programming Be Liberated from the von Neumann Style?”, আর লেখাটি ১৯৭৮ সালে Communications of the ACM-এ প্রকাশিত হয়।
তাঁর যুক্তি: প্রচলিত ভাষাগুলো von Neumann কম্পিউটারের নকশার ছায়া। সেই কম্পিউটারে CPU আর memory-র মাঝে একটি সরু পথ, যার ভেতর দিয়ে একবারে একটি word আসা-যাওয়া করে; Backus একে বললেন “von Neumann bottleneck”. Imperative ভাষার assignment statement এই পথের ভাষাগত রূপ: প্রোগ্রামার একবারে একটি word-এর হিসাব নিয়ে ভাবতে বাধ্য হন। ফলে প্রোগ্রাম বড় কাঠামো (পুরো তালিকা, পুরো matrix) নিয়ে চিন্তা না করে ছোট ছোট অবস্থা-বদলের হিসাব হয়ে যায়, আর গণিতের মতো সূত্র দিয়ে তাদের সম্পর্কে যুক্তি দেওয়া কঠিন হয়।
বিকল্প হিসেবে তিনি “FP” নামের একটি ভাষা প্রস্তাব করেন, যেখানে কোনো variable নেই; প্রোগ্রাম হলো কয়েকটি মৌলিক function আর কয়েকটি “combining form” (যেমন composition আর “apply to all”, যা আজকের map) দিয়ে জোড়া লাগানো function. তিনি দেখান, এমন প্রোগ্রাম সম্পর্কে একটি “algebra of programs” দিয়ে সমীকরণের মতো যুক্তি দেওয়া যায়, ঠিক এই পর্বের উপপাদ্য ৯.২-এর মতো।
FP ভাষাটি নিজে জনপ্রিয় হয়নি, কিন্তু বক্তৃতাটি functional programming গবেষণাকে বড় মর্যাদা দেয়, কারণ কথাটি এসেছিল imperative জগতের সবচেয়ে সম্মানিত মানুষদের একজনের কাছ থেকে। আজকের array programming, data-parallel library আর stream API-তে তাঁর “পুরো কাঠামোর ওপর একবারে কাজ” ধারণার ছাপ স্পষ্ট।
মূল উপলব্ধি: ভাষার নকশা যন্ত্রের নকশার প্রতিফলন হতে পারে, কিন্তু হওয়া বাধ্যতামূলক নয়। Paradigm বেছে নেওয়া মানে চিন্তার একক বেছে নেওয়া: একটি word, নাকি পুরো একটি মান।
প্র ০২Haskell-এর মতো pure ভাষা যদি side effect নিষেধ করে, তাহলে সেটি স্ক্রিনে লেখে বা ফাইল পড়ে কীভাবে?
এটি functional ভাষার ইতিহাসের সবচেয়ে কঠিন প্রশ্নগুলোর একটি ছিল। একটি program যদি কিছুই ছাপতে বা পড়তে না পারে, তবে সেটি শুধু ঘর গরম করে। সমস্যাটি আরও জটিল lazy ভাষায়: অংশ ৮-এ দেখেছেন, lazy ভাষায় কখন কোন হিসাব হবে তা আগে থেকে বলা কঠিন, তাই “এই লাইন ছাপো, তারপর ওটা পড়ো”-এর ক্রম রক্ষা করা কঠিন।
প্রথম দিকের Haskell (১৯৯০-এর Haskell 1.0 report) stream-ভিত্তিক I/O ব্যবহার করত: program একটি function, যা অপারেটিং সিস্টেমের “উত্তরের” একটি lazy তালিকা নিয়ে “অনুরোধের” একটি lazy তালিকা ফেরত দেয়। কাজ চলত, কিন্তু লেখা কঠিন আর ভুলপ্রবণ ছিল। সমাধান এল গণিতের category theory থেকে: Eugenio Moggi (১৯৮৯–৯১) দেখান, side effect-ওয়ালা হিসাবকে “monad” নামের একটি কাঠামো দিয়ে বর্ণনা করা যায়, আর Philip Wadler (১৯৯০-এর দশকের শুরুতে) ধারণাটিকে functional প্রোগ্রামিংয়ে নিয়ে আসেন। Haskell 1.3 (১৯৯৬) monad-ভিত্তিক I/O-কে ভাষার মূল পদ্ধতি বানায় (সাল নিয়ে উৎসভেদে সামান্য পার্থক্য পাওয়া যায়)।
মূল কৌশলটি সরল শোনায়: putStrLn "hello" নিজে কিছু ছাপে না; এটি একটি মান, যার type IO (), অর্থাৎ “একটি কাজের বর্ণনা, যা চালালে ছাপবে”। এই মানগুলো pure ভাবে জোড়া লাগানো যায় (“এটি করো, তারপর ফলটি নিয়ে ওটা করো”), আর পুরো program-টি একটি বিশাল IO মান, যা runtime শেষে একবারই চালায়। putStrLn "hello"-কে তার মান দিয়ে বদলালে কিছুই বদলায় না, কারণ মানটিই বর্ণনা; তাই referential transparency রক্ষা পায়।
এটি অংশ ৭-এর Haat-এর কৌশলের সঙ্গে তুলনীয়: সেখানে তালিকা ছিল “আমাকে step দিন, আমি ভাঁজ হব” ধরনের function; এখানে side effect হলো “আমাকে চালান, আমি কাজ করব” ধরনের মান। Type system নিশ্চিত করে যে IO-ওয়ালা মান pure হিসাবের মাঝে লুকিয়ে ঢুকতে পারে না।
মূল উপলব্ধি: Purity মানে side effect না থাকা নয়, বরং side effect-কে type-এ দৃশ্যমান আর নিয়ন্ত্রিত রাখা। কোন function দুনিয়া ছোঁয়, তা type দেখেই বোঝা যায়।
প্র ০৩Python 3-এ reduce built-in থেকে functools-এ সরানো হলো কেন, আর CPython কেন tail call optimization করে না?
Python শুরু থেকেই multi-paradigm: lambda, map, filter আর reduce অনেক আগেই ভাষায় ছিল। কিন্তু ২০০৫ সালে Guido van Rossum “The fate of reduce() in Python 3000” নামে একটি লেখায় যুক্তি দেন, reduce দিয়ে লেখা কোড প্রায়ই পড়া কঠিন: reduce(lambda a, x: a + x[1], items, 0) দেখে পাঠককে মাথায় accumulator-এর পথ অনুসরণ করতে হয়, যেখানে sum(x[1] for x in items) সরাসরি পড়া যায়। তাঁর পর্যবেক্ষণ ছিল, বাস্তবের বেশির ভাগ reduce আসলে যোগ বা গুণ। তাই Python 3.0 (২০০৮)-এ reduce built-in থেকে সরে functools-এ যায়, আর map/filter list-এর বদলে lazy iterator ফেরত দিতে শুরু করে। Python-এর পছন্দের functional হাতিয়ার হলো comprehension আর generator expression, যা Haskell-এর list comprehension থেকে অনুপ্রাণিত।
Tail call-এর প্রশ্নে Guido ২০০৯ সালে দুটি blog লেখায় স্পষ্ট বলেন, CPython এটি করবে না। কারণ: (১) traceback-এ প্রতিটি call-এর frame দেখা যাওয়া debugging-এর জন্য জরুরি; tail call মুছে দিলে error-এর পথ হারিয়ে যায়। (২) Python-এ কোন call tail call, তা নাম আগে থেকে ঠিক না থাকায় (একটি নাম চলার সময় অন্য function-এ বসানো যায়) compiler নিশ্চিত হতে পারে না। (৩) Python-এ loop স্বাভাবিক, তাই recursion-এর ওপর ভাষার নির্ভরতা কম।
এই সিদ্ধান্তের ফল অংশ ৫-এর run-এ দেখেছেন: recursive foldr ৩০০০ উপাদানে RecursionError. Scheme-এ একই কোড চলত, কারণ Scheme-এর মানদণ্ড proper tail call বাধ্যতামূলক করে; Scheme-এ loop-এর বিশেষ syntax না থাকলেও চলে। দুটি ভাষাই সচেতন নকশা: Scheme বেছে নিয়েছে গাণিতিক সরলতা, Python বেছে নিয়েছে পড়ার সুবিধা আর debugging-এর স্বচ্ছতা।
মূল উপলব্ধি: একটি ভাষা একটি paradigm “সমর্থন করে” মানে সব কৌশল সমান সুবিধায় দেয় না। কোন কৌশল সস্তা আর কোনটি দামি, তা ভাষার নকশাকারীর মূল্যবোধ থেকে আসে; তাই এক ভাষার functional অভ্যাস অন্য ভাষায় হুবহু নিয়ে যাওয়ার আগে সেই ভাষার নিয়ম দেখে নিন।
প্র ০৪Immutability কি সবসময় ধীর? বাস্তব ভাষাগুলো এই খরচ কীভাবে সামলায়?
সরাসরি তুলনায় immutable ডেটার কিছু খরচ সত্যিই আছে। একটি C array-র i-তম ঘর বদলানো একটি নির্দেশ; একটি persistent গাছে একই কাজে মূল থেকে পাতা পর্যন্ত কয়েকটি ঘর নতুন করে বানাতে হয়, অর্থাৎ O(log n) কাজ আর নতুন memory. পুরোনো সংস্করণ কেউ ব্যবহার না করলে garbage collector-কে সেগুলো ফেরত নিতে হয়, তাই GC-র চাপ বাড়ে। আর তালিকার মতো pointer-এর শিকল cache-এর জন্য ভালো নয়, কারণ ঘরগুলো memory-তে ছড়িয়ে থাকে।
কিন্তু “সবসময় ধীর” কথাটি ভুল, তিন কারণে। প্রথমত, কপি এড়ানো: mutable জগতে কোনো ফাংশনকে ডেটা দিলে সে বদলে ফেলবে এই ভয়ে প্রায়ই নিরাপত্তার জন্য পুরো কপি (defensive copy) করা হয়; immutable ডেটায় তার দরকার নেই, structural sharing-ই যথেষ্ট। দ্বিতীয়ত, concurrency: immutable ডেটা একাধিক thread বিনা lock-এ পড়তে পারে, lock-এর খরচ আর data race-এর ভয় দুটোই যায়। তৃতীয়ত, চতুর কাঠামো: Phil Bagwell-এর hash array mapped trie (২০০১)-এর ধারণা থেকে Clojure-এর persistent vector আর map প্রতিটি নোডে ৩২টি সন্তান রাখে, তাই গাছের উচ্চতা খুব কম থাকে; ১০ লাখ উপাদানেও মাত্র কয়েক স্তর।
আর ভাষাগুলো নানা কৌশলে দুই জগতের মাঝামাঝি যায়। Clojure-এর “transient” একটি কাঠামোকে সাময়িকভাবে mutable করে, অনেক বদল দ্রুত সেরে আবার persistent করে। Rust ownership দিয়ে নিশ্চিত করে, একটি মানের একমাত্র মালিক থাকলেই কেবল বদল চলবে; তখন “বদল” কারো চোখে পড়ে না, তাই সেটি নিরাপদ। “আরও গভীরে” বক্সের Perceus একই ধারণা reference count দিয়ে চলার সময় যাচাই করে। Haskell-এ ST monad একটি function-এর ভেতরে সত্যিকারের mutable array ব্যবহার করতে দেয়, যতক্ষণ বাইরে থেকে function pure থাকে, ঠিক অংশ ২-এর “purity একটি বাইরের চুক্তি” কথার মতো।
মূল উপলব্ধি: প্রশ্নটি “immutable না mutable” নয়, বরং “বদল কে দেখতে পায়”। যে বদল কেউ দেখতে পায় না, তা নিরাপদ; ভাষার কাজ সেই অদৃশ্যতা প্রমাণ করা, আর গতির দাবি সবসময় নিজের কাজে মেপে দেখা।
প্র ০৫Map আর reduce কেন বিশাল ডেটার parallel আর distributed হিসাবের ভিত্তি হয়ে উঠল, আর সেখানে associativity কেন জরুরি?
ধরুন বাজারঘরের ১০০ কোটি অর্ডার ১০০০টি কম্পিউটারে ভাগ করে রাখা। Imperative loop s = s + x স্বভাবতই একটি ক্রম চায়: প্রতিটি ধাপ আগের s-এর ওপর নির্ভর করে। কিন্তু map-এ প্রতিটি উপাদানের হিসাব স্বাধীন, আর function pure হলে কোন কম্পিউটারে কোন ক্রমে চলল তাতে কিছু আসে যায় না। তাই map প্রায় বিনা খরচে ভাগ করা যায়।
Reduce-এর ক্ষেত্রে শর্ত লাগে। একটি তালিকাকে টুকরো করে প্রতিটি টুকরোর যোগফল আলাদা কম্পিউটারে বের করে তারপর সেগুলো যোগ করা মানে বন্ধনী নতুন করে বসানো: ((a + b) + c) + d-এর বদলে (a + b) + (c + d). এটি একই উত্তর দেয় শুধু যদি operation সংযোজী হয়, আর ফাঁকা টুকরোর জন্য একটি একক (identity) থাকে। গণিতে এই জোড়াকে বলে monoid: (পূর্ণসংখ্যা, +, 0), (সংখ্যা, max, −∞), (string, জোড়া লাগানো, ফাঁকা string). Operation যদি বিনিময়যোগ্যও (commutative) হয়, তাহলে টুকরোগুলো যেকোনো ক্রমে জোড়া যায়, যা নেটওয়ার্কে দেরিতে আসা ফলের জন্য সুবিধাজনক।
২০০৪ সালে Jeffrey Dean ও Sanjay Ghemawat-এর MapReduce গবেষণাপত্র ঠিক এই ধারণাকে হাজারো কম্পিউটারের ক্লাস্টারে নিয়ে যায়, আর নামটি সরাসরি LISP-এর map আর reduce থেকে নেওয়া বলে তাঁরা উল্লেখ করেন। পরে Apache Hadoop আর Apache Spark-এর মতো open-source ব্যবস্থা একই কাঠামো ছড়িয়ে দেয়।
একটি সূক্ষ্ম ফাঁদ: কম্পিউটারের floating-point যোগ সংযোজী নয়, কারণ প্রতিটি যোগে rounding হয়। তাই একই সংখ্যাগুলো আলাদা টুকরোয় ভাগ করে যোগ করলে শেষ অঙ্কে আলাদা উত্তর আসতে পারে; parallel হিসাবের ফল যন্ত্রভেদে বা চালানোভেদে সামান্য আলাদা হওয়ার এটি একটি পরিচিত কারণ। আর বিয়োগের মতো অ-সংযোজী operation parallel reduce-এ দিলে উত্তর সরাসরি ভুল হয়, যা stepper-এর −6 বনাম 2-তে দেখেছেন। IEEE 754 আর floating-point-এর আচরণ আসবে পর্ব ২০-এ।
মূল উপলব্ধি: Purity কাজকে স্বাধীন করে, associativity টুকরোগুলোকে জোড়া লাগানোর স্বাধীনতা দেয়। এই দুই গাণিতিক গুণই parallel হিসাবের আসল চাবি, কোনো বিশেষ library নয়।
অনুশীলন
প্রথমে নিজে করুন, তারপর উত্তর খুলে মেলান। Haat-এর প্রতিটি আউটপুট কোর্সের reference বাস্তবায়নে, আর Python ও JavaScript-এর আউটপুট সত্যিকারের Python 3.14 আর Node.js-এ চালিয়ে মেলানো।
-
বাস্তবায়ন — Haat-এ max আর compose: অংশ ৭-এর
fold.haat-এ (ক) একটি stepbiggestলিখুন, যাতেorders(keeping("Dhaka", mapping(discounted, biggest)), 0)ঢাকার সবচেয়ে বড় ছাড়-পরবর্তী মোট দেয়। (খ)compose(f, g)লিখুন, আরwith_delivery(মোট ১০০০-এর কম হলে ৬০ টাকা যোগ) দিয়েfinal = compose(with_delivery, discounted)বানিয়ে ঢাকার মোট আর সবচেয়ে বড় অর্ডার বের করুন।final(1040)কত?fn biggest(acc: Int, d: Str, t: Int) -> Int { if t > acc { return t; } return acc; } fn compose(f: (Int) -> Int, g: (Int) -> Int) -> (Int) -> Int { return fn(x: Int) -> Int { return f(g(x)); }; } fn with_delivery(t: Int) -> Int { if t >= 1000 { return t; } return t + 60; } let final = compose(with_delivery, discounted); print(orders(keeping("Dhaka", mapping(discounted, biggest)), 0)); print(orders(keeping("Dhaka", mapping(final, add)), 0)); print(orders(keeping("Dhaka", mapping(final, biggest)), 0)); print(final(1040));Reference-এর
runআরvmদুটিতেই আউটপুট:990,2306,1050,996. ঢাকার ছাড়-পরবর্তী মোট 936, 990, 200; সবচেয়ে বড় 990.final-এ আগে ছাড়, তারপর ডেলিভারি: 1040 → 936 → 996 (ঠিকbazar.haat-এর প্রথম আউটপুট!), 1100 → 990 → 1050, 200 → 200 → 260; যোগ 2306, সবচেয়ে বড় 1050. লক্ষ করুনbiggest-এর শুরুর মান 0 কাজ করে কারণ সব মোট অঋণাত্মক; ঋণাত্মক মান থাকলে max-এর একক হিসেবে সবচেয়ে ছোট Int লাগত। আরcompose-এর ক্রম গুরুত্বপূর্ণ:compose(discounted, with_delivery)আগে ৬০ যোগ করে তারপর ছাড় দিত, যা আলাদা ব্যবসায়িক নিয়ম। -
ভুল খুঁজুন: একজন বললেন, “নিচের function pure, কারণ এতে কোনো global variable নেই”:
def add_line(line, cart=[]): cart.append(line); return sum(q * u for q, u in cart). Python 3.14-এadd_line((2, 520))দুবার ডাকলে কী ছাপবে? দাবিটির ভুল কোথায়, আর কীভাবে pure করবেন?Python 3.14-এ চালানো ফল: প্রথম call
1040, দ্বিতীয় call2080, আরadd_line((1, 60), [])দিলে60. একই argument, দুই উত্তর: শর্ত (১) ভাঙে। কারণ Python-এ default মান[]একবারই তৈরি হয়, function সংজ্ঞায়িত হওয়ার সময়, আর সব call সেই একই list ভাগ করে।appendসেই লুকানো list বদলায়: একটি side effect, যদিও কোনো global নাম নেই। শুধু “global নেই” দেখে purity বিচার করা যায় না; দেখতে হবে বাইরে থেকে দেখা যায় এমন কোনো অবস্থা পড়া বা বদলানো হচ্ছে কি না। Pure রূপ: নতুন tuple ফেরত দিন, পুরোনোটি না বদলে, যেমনdef add_line(line, cart=()): new = cart + (line,); return new, sum(q * u for q, u in new). এখন caller নতুন cart হাতে পায়, আর পুরোনো cart অক্ষত (অংশ ৮-এর persistent ধারণা)। -
আউটপুট অনুমান করুন: (ক)
reduce(lambda a, x: 2 * a + x, [1, 0, 1, 1], 0)(Python) কত? (খ) foldr-এf(x, a) = x + 2 * a, শুরু 0, একই তালিকায় কত? (গ) JavaScript-এ[].reduce((a, b) => a + b)আর[].reduce((a, b) => a + b, 0)কী দেয়?(ক) foldl বাঁ থেকে: 0 → 2·0 + 1 = 1 → 2·1 + 0 = 2 → 2·2 + 1 = 5 → 2·5 + 1 = 11. এটি বাইনারি 1011-কে দশমিকে পড়া, সবচেয়ে বড় অঙ্ক আগে। Python 3.14-এ ফল
11.(খ) foldr ডান থেকে: 1 + 2(0 + 2(1 + 2(1 + 2·0))) = 1 + 2(0 + 2(1 + 2·1)) = 1 + 2(0 + 2·3) = 1 + 2·6 = 13. এখানে তালিকার প্রথম উপাদান সবচেয়ে ছোট অঙ্ক, অর্থাৎ বাইনারি 1101 = 13. চালানো ফলও
13. একই তালিকা, দুই দিকের ভাঁজ, দুই সংখ্যা।(গ) Node.js-এ চালানো ফল: প্রথমটি
TypeError: Reduce of empty array with no initial value, দ্বিতীয়টি0. শুরুর মান না দিলে JavaScript প্রথম উপাদানকে শুরু ধরে, আর ফাঁকা array-তে কোনো প্রথম উপাদান নেই। সংজ্ঞা ৯.৪-এর foldl f z [] = z-এ z সবসময় থাকে; তাই শুরুর মান (একক) দেওয়া অভ্যাস করুন। -
প্রমাণ: সংজ্ঞা sum [] = 0, sum (x:xs) = x + sum xs, আর তালিকা জোড়ার সংজ্ঞা [] ++ ys = ys, (x:xs) ++ ys = x : (xs ++ ys) ধরে প্রমাণ করুন: প্রতিটি সসীম তালিকা xs, ys-এর জন্য sum (xs ++ ys) = sum xs + sum ys. কোন ধাপে যোগের associativity লাগল? এই ফল parallel যোগের জন্য কেন গুরুত্বপূর্ণ?
xs-এর ওপর structural induction (ys স্থির)।
- ভিত্তি, xs = []: বাঁ দিক sum ([] ++ ys) = sum ys. ডান দিক sum [] + sum ys = 0 + sum ys = sum ys. সমান।
- ধাপ: ধরি sum (xs ++ ys) = sum xs + sum ys. তাহলে sum ((x:xs) ++ ys) = sum (x : (xs ++ ys)) = x + sum (xs ++ ys).
- Hypothesis বসিয়ে: = x + (sum xs + sum ys).
- যোগের associativity দিয়ে: = (x + sum xs) + sum ys = sum (x:xs) + sum ys. ∎
ধাপ ৪-এ associativity লেগেছে। ফলটি বলে, একটি তালিকাকে যেকোনো জায়গায় দুই টুকরো করে আলাদা আলাদা যোগ করে তারপর যোগফল দুটি যোগ করলে পুরো তালিকার যোগফলই পাওয়া যায়; বারবার প্রয়োগে যেকোনো সংখ্যক টুকরোয়। এটিই ভাবনার প্রশ্ন ০৫-এর parallel reduce-এর গাণিতিক ভিত্তি; বিয়োগে ধাপ ৪ ভেঙে পড়ে, তাই টুকরো করে বিয়োগ চলে না। Haat-এর Int ৬৪-বিটে wrap করলেও এই প্রমাণ টেকে, কারণ wrap-করা যোগ (264 দিয়ে ভাগশেষের যোগ) সংযোজী; floating-point যোগে টেকে না।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমmap fusion (map f (map g xs) = map (f ∘ g) xs) structural induction দিয়ে প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- map-এর সংজ্ঞা দুটি ক্ষেত্রে লেখা: ফাঁকা তালিকা আর x:xs
- ভিত্তি: xs = []-এ দুই দিকই [] দেখানো
- Induction hypothesis: xs-এর জন্য দাবিটি সত্য ধরা
- x:xs-এ সংজ্ঞা খুলে hypothesis বসিয়ে দুই দিক সমান দেখানো
- সিদ্ধান্ত: প্রতিটি সসীম তালিকায় দাবিটি সত্য
নিচের Python function-গুলোর মধ্যে কোনটি pure?
def f(t): print(t); return tdef f(t): return t * rate(rate একটি global variable)def f(t): return t - t // 10 if t >= 1000 else tdef f(cart, x): cart.append(x); return len(cart)
Haat-এ var n = 0; let next = fn() -> Int { n = n + 1; return n; }; এরপর print(next() + next()); চালালে কী ছাপা হয়, আর এটি কী দেখায়?
- 2; referential transparency রক্ষা পায়
- 3; side effect থাকায় next() কে একটি মান দিয়ে বদলানো যায় না
- Type error, কারণ closure বাইরের var বদলাতে পারে না
- 1; দুটি call একই মান দেয়
তালিকা [1, 2, 3]-এ শুরু 0 নিয়ে foldl (a, x) ↦ a − x আর foldr (x, a) ↦ x − a-এর ফল যথাক্রমে কত?
- −6 আর −6
- 2 আর −6
- 6 আর 6
- −6 আর 2
Haat-এ fn charge(rate: Int) -> (Int) -> (Int) -> Int একটি curried function (rate, তারপর limit, তারপর total; total ≥ limit হলে total − total * rate / 100). let festive = charge(10)(1000); লেখার পর festive কী?
- type
(Int) -> Int-এর একটি closure, যা rate = 10 আর limit = 1000 ধরে রাখে - একটি Int, 900
- Syntax error, কারণ পরপর দুটি call লেখা যায় না
- একটি function, যার rate পরের যেকোনো charge call-এ বদলে যায়
JavaScript-এ const orders = Object.freeze([{ district: "Dhaka" }]); লেখার পর strict mode-এ কোন লাইন কোনো error ছাড়াই data বদলে দেয়?
orders.push({ district: "Sylhet" })orders = []orders[0].district = "Sylhet"orders[0] = { district: "Khulna" }
একটি persistent linked list v1 = [936, 990, 200]-এর সামনে 540 যোগ করে v2 বানানো হলো। Structural sharing থাকলে কী ঘটে?
- v1-এর সামনে 540 বসে যায়, তাই v1 আর v2 একই
- শুধু 540-এর একটি নতুন ঘর তৈরি হয়, যা v1-কে নির্দেশ করে; v1 অক্ষত থাকে
- v1-এর তিনটি ঘর কপি করে চার ঘরের নতুন তালিকা হয়
- তালিকাটি ডিস্কে সেভ হয়, যাতে পরে পড়া যায়
CPython 3.14-এ একটি recursive foldr ৩০০০ উপাদানের তালিকায় RecursionError দেয়, অথচ loop-ভিত্তিক foldl ঠিকঠাক চলে। এর সবচেয়ে সঠিক ব্যাখ্যা কোনটি?
- Python-এ recursion নিষিদ্ধ
- foldr যোগে ভুল উত্তর দেয়, তাই Python থামিয়ে দেয়
- CPython foldl-কে tail call optimize করে, foldr-কে নয়
- foldr প্রতিটি উপাদানে একটি অসমাপ্ত call জমায়, আর CPython-এর recursion সীমা (ডিফল্টে ১০০০) পেরিয়ে যায়
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Pure function: একই argument-এ একই ফল, কোনো side effect নেই। Purity একটি বাইরের চুক্তি; ভেতরের local বদল চলে। Haat pure নয়:
varআর by-reference closure আছে। - Referential transparency: ⟦C[e]⟧ = ⟦C[v]⟧; তাই equational reasoning, memoization আর compiler-এর optimization নিরাপদ।
next() + next()≠2 * next()দেখায় side effect কীভাবে এটি ভাঙে। - Map, filter, fold: loop = foldl (উপপাদ্য ৯.১), map fusion (৯.২)। foldl আর foldr একই শুধু সংযোজী operation আর একক থাকলে; [1, 2, 3]-এ বিয়োগে −6 বনাম 2.
- Currying আর composition: f(a, b, c) → f(a)(b)(c), প্রতিটি ধাপ একটি closure; partial application সেখান থেকে বিনা খরচে। f ∘ g সংযোজী।
- Immutability: persistent data structure structural sharing দিয়ে পুরোনো সংস্করণ রাখে; “immutable”-এর মাত্রা ভাষাভেদে আলাদা (Haat-এর let, Python tuple, JS freeze শুধু ওপরের স্তর)।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ১০ · Logic programming — Prolog, unification আর backtrackingপরবর্তী পর্বতথ্য, নিয়ম আর প্রশ্ন দিয়ে program; ভাষা নিজে উত্তর খোঁজে।
- প্রোগ্রামিং ভাষা ও কম্পাইলার · কোর্স হোম৮৬টি পর্বপুরো কোর্সের মানচিত্র আর Haat প্রজেক্টের পথ।
- JavaScript-এ functional programming — pure function, currying আর compositionপাশের ট্র্যাকJavaScript-এর হাতিয়ার দিয়ে একই ধারণার ব্যবহারিক দিক।
- lambda, functools আর itertools — ফাংশন দিয়ে ডেটার পাইপলাইনপাশের ট্র্যাকPython-এর map, filter, reduce, partial আর itertools.
- Java-র lambda, functional interface আর method referenceপাশের ট্র্যাকJava 8-এর পর থেকে Java-য় functional ধাঁচ।
- গণনার অন্য মডেল — lambda calculus, register machine আর cellular automatonতত্ত্বFunctional ভাষার গাণিতিক শিকড়।