Lambda Calculus
ল্যাম্বডা ক্যালকুলাস
মাত্র তিনটা নিয়মে (variable, abstraction, application) সংজ্ঞায়িত একটা গণনা মডেল — Turing machine-এর সমতুল্য শক্তিশালী, আর প্রতিটা functional programming ভাষার আনুষ্ঠানিক পূর্বপুরুষ।
also: λ-calculus
Syntax: e ::= x | λx.e | e e — variable, abstraction (function
definition), application। একমাত্র computation rule: beta
reduction — (λx.e1) e2 → e1[x := e2] (argument-কে body-তে বসানো)।
Free/bound variable, alpha conversion (নাম পরিবর্তনে অর্থ অপরিবর্তিত) সহ। Church encoding দিয়ে boolean, pair, এমনকি natural number (Church numeral) — সবকিছু function দিয়েই প্রকাশযোগ্য, কোনো built-in data type ছাড়াই।
Church-Turing thesis অনুযায়ী Turing machine-এর সমতুল্য শক্তিশালী।
Lisp/Scheme, Haskell, আর JavaScript-এর closure বা Python-এর lambda
keyword — সবগুলোরই নামকরণ ও সেমান্টিক্স এখান থেকে সরাসরি এসেছে।
Type যোগ করলে (simply-typed lambda calculus) cs-theory/type-theory-and-curry-howard-এ
Curry-Howard correspondence-এ পৌঁছায়।