ল্যাম্‌ডা ক্যালকুলাস

ল্যাম্‌ডা ক্যালকুলাস (ইংরেজি Lambda Calculus বা λ-calculus) কম্পিউটারের আচরণ অধ্যয়নের জন্য জনপ্রিয় একটি গাণিতিক ব্যবস্থা। আলোন্‌জো চার্চ তার তাত্ত্বিক গবেষণায় কম্পিউটেবল ফাংশনের ধারণাকে এর মাধ্যমে প্রকাশ করেন। চার্চ-টুরিং প্রকল্প দাবী করে যে, যে কোন কম্পিউটিং সমস্যাকে এর মাধ্যমে (বা টুরিং মেশিনের মাধ্যমে) প্রকাশ করা যায়।

সংজ্ঞা

ল্যাম্‌ডা ক্যালকুলাস হলো ল্যাম্‌ডা রাশিমালার বিজ্ঞান, যেখানে ল্যাম্‌ডা রাশিগুলো মূলত এক প্যারামিটারবিশিষ্ট ফাংশন, যারা প্যারামিটার হিসেবে অপর কোন ল্যাম্‌ডা রাশি নেয়, এবং এর ফলাফল আরেকটি ল্যাম্‌ডা রাশি। গঠনগতভাবে ল্যাম্‌ডা রাশিগুলো হল

• চলক যাকে একটি অক্ষর দিয়ে প্রকাশ করা হয়, যেমন $x$ (আসলে এই চলকটিও একটি ফাংশন (সকল ল্যাম্‌ডা রাশিই যেহেতু ফাংশন) কিন্তু একে কারো উপর প্রয়োগ করা হয় নি)।
• প্রয়োগ একটি ল্যাম্‌ডা রাশিকে আরেকটি ল্যাম্‌ডা রাশির উপর প্রয়োগ করা যায়। প্রয়োগ বুঝাতে যাকে প্রয়োগ করা হচ্ছে এবং যার উপর প্রয়োগ করা হচ্ছে সেই রাশি দুইটিকে পরপর লেখা হয়, যেমন $(MN)$, যেখানে $M$কে $N$এর উপর প্রয়োগ করা হচ্ছে। সম্পূর্ণ রাশিটির মান হল এই প্রয়োগের ফলাফল রাশিটি।
• অ্যাবস্ট্রাকশন একটি ল্যাম্‌ডা রাশি থেকে যখন কোন একটি চলককে সরিয়ে নেয়া হয় তখন এরকম একটি ফাংশন হয় যাকে অন্য কোন রাশির উপর প্রয়োগ করলে রাশিটির মান হবে ঐ চলককে ঐ রাশিটি দিয়ে প্রতিস্থাপন করলে যেই রাশিটি পাওয়া যায়। কোন রাশি $M$ থেকে কোন চলক $x$ কে সরিয়ে নিলে যে ফাংশনটি পাওয়া যায় তাকে লেখা হয় $(\lambda x.\,M$), একে অন্য কোন রাশি $N$ এর উপর প্রয়োগ করলে পাওয়া যায় $M[x:=N]$, অর্থাৎ $M$এ সকল $x$কে $N$ দিয়ে প্রতিস্থাপন করলে যে রাশিটি পাওয়া যায়।

উদাহরণ

• $\lambda x.\,x$ রাশিটিকে যার উপর প্রয়োগ করা হয়, রাশিটির মান তাই হয়। অর্থাৎ $(\lambda x.\,x)\,y\rightarrow _{\beta }y$, ফাংশনটি অভেদ ফাংশন।
• সাধারণভাবে, কোন ফাংশন $f$কে কোন মান $x$এর উপর প্রয়োগ করলে ফলাফল হয় $(f\,x)$, ধরা যাক $f$ হলো ফ্যাকটোরিয়াল ফাংশন, আর $x$এর মান $3$, তাহলে $(f\,x)\rightarrow _{\beta }({\mbox{factorial}}\,3)\rightarrow _{\beta }6$.

বিটা-সংক্ষেপণ

প্রতিস্থাপনের এই পদ্ধতির নাম বিটা-সংক্ষেপণ ($\beta$ reduction), সবসময় যদিও রাশিটি সংক্ষিপ্ত হয় না (আকারে),

$(\lambda x.\,x\,x)\,(\lambda x.\,x\,x)\rightarrow _{\beta }(\lambda x.\,x\,x)\,(\lambda x.\,x\,x)\rightarrow _{\beta }\ldots$

এমনকি আকারে বাড়ে এরকম উদাহরণও খুবই সহজ,

$(\lambda x.\,x\,x\,x)\,(\lambda x.\,x\,x\,x)\rightarrow _{\beta }(\lambda x.\,x\,x\,x)\,(\lambda x.\,x\,x\,x)\,(\lambda x.\,x\,x\,x)\rightarrow _{\beta }\ldots$

তবে কম্পিউটেশনের মূলমন্ত্র যে এই সংক্ষেপনেই নিহিত তাতে কোন সন্দেহ নেই। কোন সংক্ষেপণটি থামবে কোনটি থামবে না তা নির্ণয় করার কোন সাধারণ অ্যালগোরিদম নেই, যার প্রমাণ টুরিং মেশিনের থামা-না-থামা সমস্যা।

স্থির বিন্দু

গণিতে কোন ফাংশন $f$-এর স্থির বিন্দু বলতে বোঝায় এমন কোন বিন্দু $x$ যার জন্য

$f(x)=x$ বা ল্যাম্‌ডা ক্যালকুলাসের রীতিতে, $fx=x$

যেহেতু ল্যাম্‌ডা ক্যালকুলাসে প্রতিটি রাশিই ফাংশন, তাই এখানে কোন ফাংশনের স্থির বিন্দু নিজেও আরেকটি ফাংশন।

যেখানে সাধারণত কোন গাণিতিক ফাংশনের স্থির বিন্দু নাও থাকতে পারে (বা থাকলেও তাকে খুঁজে বের করা একটা গাণিতিক সমস্যা), কিন্তু ল্যামডা ক্যালকুলাসে প্রতিটি রাশিরই স্থির বিন্দু আছে (লক্ষ্যণীয়, এই ক্যালকুলাসে ফাংশন বাদে অন্য কোন গাণিতিক ধারণা নেই, বস্তুত, চার্চের প্রাথমিক লক্ষ্য ছিল ফাংশনের ধারণাকে গণিতের ভিত্তি হিসেবে দাঁড় করানো)।

প্রমাণ: $\mathbf {Y} =\lambda f.\,(\lambda x.\,f\,(x\,x))\,(\lambda x.\,f\,(x\,x))$ একটি স্থির বিন্দু নির্ণায়ক (ইংলিশে, Fixed Point Combinator),

$(\mathbf {Y} \,f)$ রাশিটি $f$-এর স্থির বিন্দু।

দেখা যাক, $(\mathbf {Y} \,f)\rightarrow _{\beta }(\lambda x.\,f\,(x\,x))\,(\lambda x.\,f\,(x\,x))\rightarrow _{\beta }f\,((\lambda x.\,f\,(x\,x))\,(\lambda x.\,f\,(x\,x)))=f(\mathbf {Y} \,f)$

অর্থাৎ $(\mathbf {Y} \,f)$ এমন একটি ফাংশন যার উপর $f$-কে প্রয়োগ করলে আবার ঐ ফাংশনটিই ফেরত পাওয়া যায় (স্থির বিন্দুর সংজ্ঞা)।

লক্ষ্যণীয়, এই প্রমাণটি শুধু যে স্থির বিন্দুর অস্তিত্ত্ব দেখায় তাই না, (একটি) স্থির বিন্দু নির্ণয়ও করে দেয়।

স্থির বিন্দু নির্ণায়কের মাধ্যমে ল্যাম্‌ডা ক্যালকুলাসে পুনরাবৃত্ত ফাংশন (ইংলিশে, w:en:Recursive function) প্রকাশ করা যায়।

কম্পিউটার প্রোগ্রামিং-এ ল্যাম্‌ডা ক্যালকুলাস

প্রোগ্রামিং ভাষা অনেক সময়ই ল্যাম্‌ডা ক্যালকুলাসের বিভিন্ন ধারণা দিয়ে প্রভাবিত হয়। প্রথম দিকের ভাষাগুলোর মধ্যে LISP এর গঠন ল্যাম্‌ডা ক্যালকুলাস প্রভাবিত। পরবর্তীতে Scheme (LISP এর আধুনিক একটি রূপ) এবং ML-পরিবারের ভাষাগুলো ল্যাম্‌ডা ক্যালকুলাস ও টাইপ থিওরীর সম্পর্ককে কাজে লাগায়।

পিটার ল্যানডিন প্রস্তাবিত বিখ্যাত কাল্পনিক প্রোগ্রামিং ভাষা ISWIM ("If you See What I Mean") এর মূল অনুপ্রেরণা ছিল ল্যাম্‌ডা ক্যালকুলাস আর টুরিং মেশিনের তাত্ত্বিক অভিন্নতা।

আরও দেখুন

• জন বাকাসের টুরিং পুরস্কার ভাষণ Can Programming Be Liberated From the von Neumann Style?
• Why Functional Programming Matters, John Hughes এর গবেষণা নিবন্ধ