حساب لامبدا
کلیات

اکثر زبان‌های برنامه‌نویسی (از جمله Lisp, ML و زبان‌های ضروری مانند C و Java) به عنوان «سخت» توصیف می‌شوند، به این معنی که توابع اعمال شده به استدلال‌های غیرعادی غیرطبیعی هستند. این کار اساساً با استفاده از نظم اعمال انجام می‌شود، با کاهش ارزش تماس بگیرید (نگاه کنید به زیر)، اما معمولاً «ارزیابی مشتاق» نامیده می‌شود.
سفارش عادی
اولیای چپ و راست، خارج از محدوده همیشه اول کاهش می‌یابد. به عبارت دیگر، هر گاه استدلال‌ها قبل از اینکه استدلال‌ها کاهش یابد، به انتزاعی تعویض می‌شوند.
تماس با نام
به عنوان منظور عادی، اما در انتساب‌ها هیچ کاهشی انجام نمی‌شود. به عنوان مثال، λx (λx.x) x طبق این استراتژی در فرم عادی است، هرچند که حاوی redex (λx.x) x می‌باشد.
با ارزش تماس بگیرید
فقط بازخوانی‌های خارج از محدوده کاهش می‌یابد: یک مقدار بازده کاهش می‌یابد تنها زمانی که سمت راست آن به یک مقدار کاهش می‌یابد (انتزاعی متغیر یا لامبدا).
با نیاز تماس بگیرید
به عنوان مثال عادی، اما عملکرد برنامه‌های کاربردی که اصطلاحات را تکرار می‌کنند، به جای آن آرگومان نامیده می‌شود، که پس از آن فقط «هنگامی که لازم است» کاهش می‌یابد. در زمینه‌های عملی «ارزیابی تنبل» نامیده می‌شود. در پیاده‌سازی این «نام» به صورت یک اشاره گر به دست می‌آید، با استفاده از redex توسط Thunk نشان داده می‌شود.
منظور کاربردی یک استراتژی عادی نیست. مثال نمونه معمولی به شرح زیر است: تعریف Ω = ωω که در آن ω = λx.xx. این کل عبارت شامل تنها یک redex است یعنی کل عبارت؛ کاهش آن دوباره Ω است. از آنجا که این تنها کاهش موجود است، Ω دارای فرم عادی نیست (تحت هر استراتژی ارزیابی). با استفاده از نظم اعمال، بیان KIΩ = (λx. λy.x) (λx.x) Ω توسط اولین کاهش از Ω به شکل عادی کاهش می‌یابد (از آنجایی که آن مجذور راست‌ترین است)، اما از آنجا که Ω دارای فرم عادی نیست، نظم اعمال ناکافی است برای پیدا کردن یک فرم عادی برای KIΩ.
در مقابل، نظم طبیعی به اصطلاح نامیده می‌شود، زیرا اگر همیشه وجود داشته باشد، همیشه یک کاهش نرمال پیدا می‌کند. در مثال بالا، KIΩ طبق معمول به I، یک فرم عادی کاهش می‌یابد. یک نقص این است که بازنگری در استدلال ممکن است کپی شود و نتیجه محاسبات تکراری (به عنوان مثال (λx.xx) ((λx.x) y) به ((λx.x) y) ((λx.x) y) با استفاده از این استراتژی؛ در حال حاضر دو بازخوانی وجود دارد، بنابراین ارزیابی کامل نیاز به دو مرحله دارد، اما اگر این استدلال ابتدا کاهش یافته باشد، در حال حاضر هیچ‌کدام وجود ندارد).
معامله مثبت استفاده از دستور applicative این است که اگر همه استدلال‌ها مورد استفاده قرار گیرد، محاسبات غیرضروری را ایجاد نمی‌کند، زیرا هرگز استدلال‌هایی را که حاوی redexes است جایگزین نمی‌کند و بنابراین هرگز نیازی به کپی کردن آن‌ها نیست (که کار را کپی می‌کند). در مثال فوق، در برنامه کاربردی (λx.xx) ((λx.x) y) ابتدا به (λx.xx) y و سپس به حالت عادی yy کاهش می‌یابد، و به جای آن سه مرحله را می‌گیرد.
بیشتر زبان‌های برنامه‌نویسی کاملاً کاربردی (به ویژه میراندا و نسل‌های آن، از جمله Haskell) و زبان‌های اثبات شده از قضیه‌های پیشین، از ارزیابی تنبل استفاده می‌کنند که اساساً همان چیزی است که نیاز به نیاز دارد. این همانند کاهش نظم طبیعی است، اما نیاز به مدیریت می‌شود تا از تقسیم کار ذاتی در کاهش سفارش معمول با استفاده از اشتراک استفاده شود. در مثال فوق داده شده (λx.xx) ((λx.x) y) به ((λx.x) y) ((λx.x) y) کاهش می‌یابد، که دارای دو بازخوانی است، اما در تماس با نیاز، آن‌ها نماینده با استفاده از همان شیء به جای کپی، بنابراین هنگامی که یکی کاهش می‌یابد دیگر نیز است.
یک یادداشت در مورد پیچیدگی
در حالی که ایده کاهش بتا به اندازه کافی ساده به نظر می‌رسد، این یک گام اتمی نیست، در حالی که هنگام تخمینی پیچیدگی محاسباتی باید هزینه‌ای بی‌اهمیت داشته باشد. برای دقیق بودن، باید مکان‌یابی هر رخداد متغیر محدود V را در عبارت E پیدا کرد، یعنی یک هزینه زمانی، یا باید مسیری را از این مکان‌ها به نحوی پیگیری کرد، یعنی یک هزینه فضایی است. جستجوی ساده‌ای برای مکان‌های V در E برابر O (n) در طول n از E. این منجر به مطالعه سیستم‌هایی که از جایگزینی صریح استفاده می‌کنند. رشته‌های مدیر سینو، راهی برای ردیابی مکان‌های آزاد متغیر در عبارات ارائه می‌دهد.
همزمان‌سازی و هم‌زمان سازی
اموال church-rosser از محاسبات لامبدا به معنی آن است که ارزیابی (کاهش بتا) می‌تواند در هر جهت، حتی به صورت موازی انجام شود. این به این معنی است که استراتژی‌های ارزیابی غیرمتمرکز متفاوت هستند. با این حال، محاسبات لامبدا هیچ ساختاری صریح برای موازی ارائه نمی‌دهد. می‌توانید سازه‌هایی مانند Futures را به محاسبات لامبدا اضافه کنید. دیگر محاسبات فرایند برای توصیف ارتباطات و همگام‌سازی توسعه داده شده‌است.
معناشناسی
این واقعیت که شرایط محاسبات لامبدا در شرایط دیگر محاسبات لامبدا و حتی در خود عمل می‌کند، منجر به سوالاتی در مورد معناشناسی محاسبات لامبدا شد. آیا معنای منطقی به شرایط محاسبات لامبدا اختصاص دارد؟ معناشناسی طبیعی یافتن مجموعه‌ای D است که به صورت فضای تابع D → D عمل می‌کند. با این وجود، هیچگونه غیرقطعی مانند D ممکن است با محدودیت‌های قدرتمندی وجود داشته باشد؛ زیرا مجموعه‌ای از همه توابع از D به D دارای قدرت بیشتری نسبت به D است، مگر اینکه D یک مجموعه تک تک باشد.
در دهه ۱۹۷۰، دانا اسکات نشان داد که اگر تنها توابع پیوسته در نظر گرفته شوند، یک مجموعه یا دامنه D با ملک مورد نیاز یافت می‌شود، بنابراین یک مدل برای محاسبات لامبدا ارائه می‌شود.
این کار همچنین پایه و اساس معانی معانی زبان‌های برنامه‌نویسی را تشکیل می‌دهد.
شبیه‌سازی ماشین تورینگ