موضوع مقاله: حساب لامبدا | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # حساب لامبدا | مقدمه: این دستگاه، مدلی محاسباتی است که می‌توان از آن جهت شبیه‌سازی هر نوع ماشین تورینگی استفاده کرد. | ## بخش 1: حساب لامبدا | این دستگاه صوری، توسط آلونزو چرچ در دهه ۱۹۳۰ میلادی، به عنوان بخشی از تحقیقات او بر روی بنیان‌های ریاضیات معرفی گشت. در ساده‌ترین فرم حساب لامبدا، ترم‌ها تنها با استفاده از قواعد زیر ساخته می‌شوند: نحو نام توصیف متغیر کارکتر یا رشته‌ای که نمایش دهنده یک پارامتر یا مقدار ریاضیاتی/منطقی می‌باشد. در برخی از کاربردها، ترم‌های مربوط به ثوابت ریاضیاتی و منطقی، و همچنین عملگرها را نیز می‌توان در چنین عباراتی به کار برد. عملیات کاهنده (تقلیل دهنده) شامل این موارد اند: عمل نام توصیف تبدیل تغییر نام متغیرهای مقید در عبارت. اگر از اندیس گذاری دو برویجن استفاده شود، آنگاه دیگر به تبدیل نیازی نیست، چرا ه تصادم نام دیگر رخ نخواهد داد. اگر به کار بردن مکرر مراحل تقلیل در نهایت به پایان برسد، آنگاه با کمک قضیه چرچ-روسر، فرم نرمال یی را تولید خواهد نمود. اگر از تابع لامبدای جهانی استفاده شود، به نام متغیرهایی چون یوتا و جوت (Iota and Jot)، که قادرند در ترکیبات مختلف، با صدا زدنشان بر روی خودشان، هر نوع رفتار تابع را ایجاد نمایند، دیگر نیاز نخواهد بود. حرف یونانی لاندا (λ)، که در اسم این حساب حضور دارد، در عبارات لاندا و جملات لاندا برای نشان دادن انقیاد یک متغیر در یک تابع استفاده می‌شود. در حساب لاندای نوع‌دار یک تابع درصورتی می‌تواند صدا زده شود که توانایی پذیرش داده‌هایی با آن «نوع» خاص را داشته باشد. جبرهای لاندا نوع‌دار از لحاظ محاسباتی توانایی بیان کردن کمتری از جبرهای لاندای بدون نوع دارند؛ لذا از این جهت ضعیف‌تر هستند. اما از سوی دیگر قابلیت اثبات بالاتری دارند و می‌توانند چیزهای بیشتری را اثبات کنند. برای مثال در حساب لاندای نوع‌دار ساده، تمامی استراتژی‌های محاسبه تمام‌شدنی (terminating) هستند؛ در حالی که در حساب بدون نوع نیازی به تمام شدنی بودن نیست و محاسبه یک عبارت می‌تواند تا بینهایت ادامه پیدا کند. تاریخچه حساب لامبدا به وسیله الونوز چورچ در سال ۱۹۳۰ معرفی شد به عنوان قسمتی از تحقیقات در پایه و اساس ریاضی. در سال ۱۹۳۵ زمانی که‌ای ستفنکلینی و جی بی روسر روی پیشرفت کلنی-روسر پارادوکس کار می‌کردند. در نتیجه در سال ۱۹۳۶ چورچ قسمتی مناسب برای محاسبات را جدا کرد و نشر داد که اکنون به عنوان حساب لامبدا نوشته نشده بیان می‌شود. در سال ۱۹۴۰چورچ محاسبات ضعیف تری را بیان کرد اما به صورت منطقی سیتم فعال و استوار یک نوع ساده از حساب لامبدا را می‌داند انتا سال ۱۹۶۰ زمانی که ارتباط زبان برنامه واضح شد در واقع حساب لامبدا فورمالیته شد. سپاس از ریچارد مونتیج و بقیه زبان‌شناس‌ها در پیدا کردن معنای زبان طبیعی در واقع حساب لامبدا مورد قبول و پذیرش زبان‌شناس ها و هم چنین علوم کامپیوتر شده‌است. خاصیت‌های محاسبات را قادر می‌سازد که به صورت معمول خوانده شود بدون اینکه اسامی را صریح برگرداند. مرحله دوم ساده‌سازی این است که حساب لامبدا تنها برای توابع تک ورودی استفاده شود. توابعی که دو وذودی دارندبه عنوان مثال square-sumمی‌تواند با تابع معادل خود کار کند که تنها یک ورودی داشته باسد و خروجی از یک تابع دیگر حاصل شودو و با تک ورودی قاب قبول است مانند X+y→x2+y2 که با این تابع نیز کار می‌کند و صحیح است. X→(y→x2+y2) این متد به عنوان curringبیان می‌شود که قابل انتقال به توابعی که چندین آرگومان دارند به زنجیره‌ای از توابع که تک آرگومان دارند. برنامه توابع به مانند اسکوور با دو آرگومان این‌گونه است مثلاً (۵و۲) x,y)→x2+y2 2,5) =52+22 =۲۹ زمانی که برا ی تابع کاری نیاز به چندین مرحله می‌باشد. کلیات حساب لامبدا شامل زبانی از عناصر لامبدا است که با عناصر نحوی مشخص بیان می‌شود و هم چنین قانون‌های انتقال که به عناصر لامبدا اجازه دستکاری می‌دهد؛ که این قانون‌های انتقال در قضیه معدله‌ای و بیان عملیاتی استفاده می‌شود. برای توضیح بالا تمام توابع در حساب لامبدا توابع ناشناس هستند؛ که فقط یک ورودی متغیر را می‌پذیرند؛ که با تابع کارینگ می‌توان چندین متغیر را به عنوان ورودی در نظر گرفت عناصر لامبدا نحو حساب لامبدا برای بیان متغیرهای معتبر و نامعتبر است برای رشته‌ای از کاراکترهای معتبر زبان و برنامه سی و نامعتبر آن. سه قانون زیر یک معنای القایی به ما می‌دهد که می‌تواند تمام نحو معتبر حساب لامبدا را شمال شود متغیر xخود به تنهایی یک عناصر معتبر لامبدا است. اگر tوsعناصر لامبدا باشند آنگاه (ts)عناصر لامبدا اسنت هیچ عبارت دیگری عناصر لامبدا نیست؛ بنابراین عناصر لامبدا معتبر هستند اگر شامل تکرار قوانین بالا باشند. به عنوان مثال پرانتز خارج از محدوده به صورت معمول نوشته نمی‌شودبه نشانه‌گذاری پایین دقت کنید مفهوم یا برداشت لامبداx.tتوضیحی از توابع ناشناخته که این توانایی را دارد که ورودی xرا بگیرد و با tجایگزین کند بنابراین یک تابع ناشناخته را بیان می‌کند که xرا می‌گیرد و t را برمی‌گرداند. به عنوان مثال x.x2+2یک مفهوم از تابع f(x)=x2+2که از عناصر x2+2استفاده می‌کند تعریف تابع به همراه مفهوم لامبدا صرفاً تولید و تشکیل تابع است انا نه فراخوانی کردن آن. مفهوم لامبدا x.x+yبه صورت نخوی معتبر است و هم چنین تابعی را تولید می‌کند که ورودی را با yکه هنوز ناشناخته هست جمع می‌کند. λx.x)x) و(λx.(λx.x دو عنصر مختلف را بیان می‌کنند (اگرچه که هر دو اگر گاهش داده شوند به یک آرش و مقدار می‌رسند). اینجا اولین مثال برای معرفی تابع است که این معرفی تابع و برگرداندن نتیجه برای درخواست xاز تابع فرزندان به حساب می‌آید (درخواست تابع و بعد بازگشت) مثال دوم معرفی و تعیین تابع که تابعی را برمی‌گرداند که با هر ورودی کار می‌کند و در آخر برنامهxرا برمی‌گرداند (بازگشت تابع و بعد از درخواست) توابعی روی توابع دیگر کار می‌کنند در حساب لامبدا توابع در واقع همان کلاس اول با ارزش بالا هستند پس ممکن است توابع به عنوان ورودی گرفته شوند یا به عنوان خروجی از بقیه توابع. اگرچه(λx.y)تابع ثابت x=yرا بیان می‌کند تابعی که همیشه yرا برگرداند برای ورودی مشکلی ندارد. در حساب لامبدا برنامه توابع به نوان وابسته چپ در نظر گرفته شده‌است پس stxبه معنای (st)xمی‌باشد. ایده‌های متفاوتی برای همبستگی و کاهش وجود دارد که عناصر لامبدا به عناصر وابسته لامبدا کاهش پیدا کنند. همبستگی آلفا اساس همبستگی که روی عناصر لامبدا قابل تعریف است را همبستگی آلفا گویند. بینشی برای انتخاب مشخص در محدوده متغیر را می‌گیرد که در مفهوم لامبدا مشکلی با این تعریف نیست. به عنوان مثال mx.xوmy.yدو همبستگ=ی آلفا از عناصر لامبدا هستند و هر دو نماینده یک تابع می‌باشند (تابع مشخص شده). در بسیاری از بیانات پیدا کردن همبستگی آلفا با عناصر لامبدا کاری معمول و رایج است. متغیرهای آزاد متغیرهای آزاد برای یک عنصر متغیرهایی است که در محدوده مفهوم لامبدا نباشند. | ## بخش 2: حساب لامبدا | به عنوان مثال نماینده عناصر لامبدا که به این هویت و نشانه استλx.xمتغیر آزادی ندارد اما تابع λx.yxیک متغیر آزاد به نام yدارد. این نشانه‌گذاری t[x:=r]بان جایگزینی rبرایxدر tبا شیوه جلوگیری از گرفتن است؛ که به این شرح است. نو شدن شرایط (به اینکه y از متغیرهای آزاد r نباشد احتیاج دارد) حیاتی تر از اطمینان یافتن است زیرا جایگزینی نباید معنی تابع را تغییر دهد. در کل دیدن شرایط نو که به وسیله تغییر نام آلفا همراه با متغیرهای تازه تصفیه شده باشد با شکست رو به رو می‌شود به عنوان مثال رفتن به عقب برای جایگزینی صحیح در (λx.y y:=x]مفهوم لامبدا با متغیر تازه zتغییر نام داده‌است که شامل(λz.y y:=x]= λz.(y(y:=x = λz.xکه یعنی تابع با جایگزینی حفظ شده‌است. کاهش بتا قانون کاهش بتا برنامه‌ای است برای فرم (λx.t)sکه به t[x:=s]کاهش پیدا کرده‌است. این گام می‌تواند به وسیله تبدیل بتا اضافی تکرار شود تا زمانی که برنامه‌ای برای کاهش وجود نداشته باشد. اگرچه حساب لامبدا نانوشته راهی برای جلوگیری از بیان ارزش درست و رشته هاو شی‌های بدون اعداد ندارد تعریف رسمی تعریف عبارات لامبدا عبارتند از: متغیرهای v1، v2، …، vn، ... پرانتز مجموعه‌ای از عبارات لامبدا، Λ، می‌تواند به صورت القایی تعریف شود: اگر x یک متغیر باشد، پس x ∈ Λ اگر x یک متغیر و M ∈ Λ باشد، (λx.M) ∈ Λ اگر M, N ∈ Λ، و سپس (M N) ∈ Λ نمونه‌هایی از قانون ۲ به عنوان انتزاع و نمونه‌هایی از قانون ۳ به عنوان برنامه‌های کاربردی شناخته می‌شوند نشانه گذاری برای حفظ نشانه‌ای از عبارات لامبدا بدون سر و صدا، معمولاً قراردادهای زیر اعمال می‌شود: پرانتز خارج از محدوده کاهش می‌یابد: M N به جای (M N) فرض می‌شود که برنامه‌های کاربردی باقی می‌مانند: M N P ممکن است به جای M N) P) بدن انتزاع به همان اندازه که ممکن است به سمت راست گسترش می‌یابد: λx.M N معنی λx.(M N) و نه (λx.M) N یک دنباله از انتزاع قرارداد: λx. λz.N به اختصار λxyz.N می‌باشد متغیرهای آزاد و محدود گفته می‌شود که اپراتور انتزاعی، λ، متغیر آن را هر جا که در انتهای انتزاع رخ می‌دهد، مرتبط کند. عبارت lambda بسته نیز به عنوان ترکیبی شناخته می‌شود و معادل آن‌ها در منطق ترکیبی است. ما همچنین از معادلات حاصل می‌گوییم: دو عبارات β-معادل هستند، اگر آن‌ها می‌توانند β-تبدیل به یک عبارت مشابه باشند، و α / η-هم‌ارزی به‌طور مشابه تعریف می‌شوند. بیان که بازده کاهش می‌یابد، کاهش آن نامیده می‌شود؛ با استفاده از مثال قبلی، کاهش این عبارات به ترتیب M [x: = N] و M. α تبدیل تبدیل آلفا، که گاهی اوقات به عنوان تغییر نام آلفا شناخته می‌شود، نام نام متغیر را تغییر می‌دهد. اول، هنگامی که تبدیل آلفا یک انتزاع، تنها رخ داده‌های متغیر که تغییر نام داده‌اند، کسانی هستند که به یک انتزاع متعهد هستند. در زبان‌های برنامه‌نویسی با محدوده استاتیک، تبدیل آلفا می‌تواند برای ایجاد وضوح نام ساده‌تر با اطمینان از اینکه نام متغیر یک نام را در دامنه حاوی مخفی می‌کند (نگاه کنید به تغییر نام آلفا برای ایجاد وضوح نام نامطلوب). جایگزینی تعویض، نوشته شده E [V: = R]، فرایند جایگزینی تمام رخدادهای آزاد متغیر V در عبارت E با بیان R است. تعویض در شرایط λ-calculus توسط بازگشتی بر ساختار اصطلاحات تعریف شده‌است، همان‌طور که به این ترتیب (توجه داشته باشید: x و y فقط متغیر هستند در حالی که M و N هر عبارت λ هستند). به عنوان مثال، برای (λx.y) [y: = x] درست نیست (به خاطر آوردن (λx.x)، زیرا x جایگزین به صورت آزاد بود اما به پایان رسید. به عنوان مثال، با فرض برخی از کدگذاری ۲، ۷، ×، ما کاهش زیر را داریم: λn.n × ۲) ۷) → ۷ × ۲. η-تبدیل Eta-conversion بیان عقلی را بیان می‌کند که در این چارچوب این است که دو توابع یکسان هستند اگر و فقط اگر آن‌ها نتایج مشابهی را برای تمام استدلال‌ها ارائه دهند. (البته، ما به آلفا تبدیل می‌پردازیم، یعنی ما دو عددی معمول را در نظر می‌گیریم، اگر ممکن است به α-تبدیل یک به دیگری تبدیل شود) بنابراین، هر دو اصطلاح به شدت نرمال و شرایط ضعیف عادی، یک فرم طبیعی منحصر به فرد دارند. برای اصطلاحات به شدت نرمال، هر استراتژی کاهش تضمین می‌شود که فرم طبیعی را تولید کند، در حالی که برای اصطلاحات ضعیف نرمال، برخی از استراتژی‌های کاهش می‌توانند آن را پیدا نکنند. انواع داده‌ها کدگذاری مقالات اصلی: رمزگذاریchurch و کدگذاری مگنسن اسکات محاسبات پایه لامبدا ممکن است برای مدل‌سازی بولی‌ها، ریاضیات، ساختار داده‌ها و رکود استفاده شود، که در زیر بخش‌های زیر نشان داده شده‌است. ریاضی در محاسبات لامبدا چندین روش ممکن برای تعریف اعداد طبیعی در محاسبات لامبدا وجود دارد، اما اکثر عبارات church هستند که می‌توانند به صورت زیر تعریف شوند: ۰ := λf. عدد n عنصر کلیسا یک تابع است که یک تابع f را به عنوان علامت می‌گیرد و ترکیب n-th f را به دست می‌دهد، یعنی تابع f با خود برابر n برابر است. چنین ترکیبات تکراری (از یک تابع f) به قوانین مادیات احترام می‌گذارند، به همین دلیل این عددها را می‌توان برای محاسبات استفاده کرد. (در محاسبات لامبدا اصلی کلیسای، پارامتر رسمی بیان لامبدا حداقل یکبار در بدن تابع اتفاق افتاد که تعریف فوق از ۰ غیرممکن بود). λx.m f (n f x) PLUS را می‌توان به عنوان یک تابع در نظر گرفت که دو عدد طبیعی را به عنوان استدلال و بازگشت یک عدد طبیعی؛ می‌توان آن را تأیید کرد PLUS 2 3 و ۵ عبارات لامبدا β معادل هستند. دو تعریف دیگر از PRED در زیر آمده‌است، یکی با استفاده از شرط و دیگری با استفاده از جفت. λy.y (توجه داشته باشید که FALSE برابر با عدد صفر کلیسا است که در بالا تعریف شده‌است) سپس با استفاده از این دو λ-term، می‌توانیم برخی از اپراتورهای منطقی را تعریف کنیم (این فقط فرمول‌های ممکن است؛ عبارات دیگر به همان اندازه صحیح هستند): AND := λp. پیش فرض زیر تست می‌کند که آیا آرگومان اول کمتر از نسبت یا برابر با دوم است: LEQ: = λm. محاسبات لامبدا نمی‌تواند این را به‌طور مستقیم به عنوان برخی از نشانه‌های دیگر بیان کند: تمام توابع در محاسبات لامبدا ناشناس هستند، بنابراین ما نمی‌توانیم به یک مقدار که هنوز تعریف شده‌است، در داخل عبارت لامبدا تعریف کنیم که همان مقدار است. با این وجود، می‌توان از طریق برگزاری یک عبارت لامبدا برای بازگشت خود به عنوان ارزش استدلال خود، به عنوان مثال در (λx.xx) E. تابع فاکتوریل F (n) را به صورت بازگشتی به وسیلهٔ تعریف می‌کنیم F(n) = 1, if n = 0; else n × F(n − ۱) در بیان لامبدا که برای نشان دادن این تابع است، پارامتر (به‌طور پیش‌فرض اول) فرض می‌شود که خودش را به عنوان مقدار خود دریافت می‌کند، به‌طوری‌که فراخوانی آن - استفاده از آن به یک استدلال - به مقدار بازگشتی تبدیل می‌شود؛ بنابراین برای رسیدن به بازگشت، استدلال در نظر گرفته شده به عنوان خود ارجاع (به نام r اینجا) همیشه باید در داخل بدن تابع در یک نقطه تماس منتقل شود: G := λr. این را حل می‌کند اما نیاز به نوشتن هر تماس مجدد را به عنوان خود برنامه کاربردی دارد. این تابع به هیچ وجه نباید صریحاً به خود منتقل شود، زیرا خود تکرار به صورت پیشفرض تنظیم می‌شود، زمانی که آن ایجاد می‌شود، هر بار که آن را فراخوانی می‌شود؛ بنابراین بیان اصلی لامبدا (FIX G) در داخل خود، در نقطه تماس، دستیابی به خود ارجاع ایجاد می‌شود. در حقیقت، بسیاری از تعاریف ممکن برای این اپراتور FIX، ساده‌ترین آن‌ها وجود دارد: Y: = λg. به‌طور خاص، اکنون می‌توانیم تفکیک، ضرب و محاسبه مقادیر عدد طبیعی را به صورت مجزا تعریف کنیم. در این زمینه، انواع معمولاً اشیاء طبیعت نحوی هستند که به شرایط لامبدا اختصاص دارند؛ نوع دقیق یک نوع بستگی به محاسبات دارد (نگاه کنید به انواع زیر). | ## بخش 3: حساب لامبدا | از دیدگاه خاص، محاسبات لامبدا تایپ شده را می‌توان به عنوان اصلاحاتی از محاسبات لامبدا غیرتصویر مشاهده کرد، اما از دیدگاه دیگر، آن‌ها همچنین می‌توانند تئوری بنیادی تر و محاسبات لامبدا با استفاده از یک مورد خاص با تنها یک نوع در نظر گرفته شوند. زبان‌های تایپ شده لامبدا زبان‌های برنامه‌نویسی پایه هستند و پایه زبان‌های برنامه‌نویسی کارکردی مانند ML و Haskell و غیرمستقیم زبان‌های برنامه‌نویسی ضروری را تایپ می‌کنند. محاسبات لامبدا تایپ شده با منطق ریاضی و تئوری اثبات شده از طریق Isomorphism کاری-هوارد مرتبط هستند و می‌توان آن‌ها را به عنوان زبان داخلی کلاس‌های دسته‌بندی، به عنوان مثال محاسبات لامبدا به سادگی تایپ شده‌است زبان رده بسته دکارتی (CCCs). عدم قطعیت برابر بودن هیچ الگوریتمی وجود ندارد که به عنوان ورودی دو علامت لامبدا و خروجی TRUE یا FALSE را در نظر بگیرد که آیا دو عبارت برابر هستند یا نه. همان‌طور که برای اثبات غیرقابل انکار بودن معمول است، اثبات نشان می‌دهد که هیچ تابع قابل محاسبه نمی‌تواند همسان‌سازی را تعیین کند. سپس پایان‌نامه کلیسا به نشان می‌دهد که هیچ الگوریتمی نمی‌تواند این کار را انجام دهد. اثبات کلیسا برای اولین بار مشکل را برای تعیین اینکه آیا یک لامبدا داده شده به شکل نرمال است، کاهش می‌دهد. یک فرم عادی بیان معادل است که نمی‌تواند تحت قوانینی که توسط فرم اعمال می‌شود کاهش یابد. سپس فرض می‌کند که این پیش‌فرض قابل محاسبه است و بنابراین می‌تواند در محاسبات لامبدا بیان شود. بر اساس کار قبلی Kleene و ساخت شماره Gödel برای عبارات لامبدا، او یک عبارت لامبدا را ایجاد می‌کند که دقیقاً به اثبات اولین قضیه ناقص گودل می‌رسد. توابع ناشناس به عنوان مثال، در Lisp تابع 'مربع' می‌تواند به صورت بیان lambda به صورت زیر بیان شود: (لامبدا (x) (* x x مثال فوق یک عبارت است که به یک تابع کلاس اول ارزیابی می‌شود. نماد lambda تابع ناشناس ایجاد می‌کند، با توجه به لیستی از نام‌های پارامتر، (x) - فقط یک آرگومان در این مورد و یک عبارت است که به عنوان بدن تابع (* x x) ارزیابی می‌شود. به عنوان مثال، پاسکال و بسیاری از زبان‌های ضروری دیگر، از طریق مکانیزم اشاره گرهای عملکرد، مدت زمان پشتیبانی از زیر برنامه‌ها را به عنوان استدلال برای دیگر برنامه‌های زیر پشتیبانی می‌کنند. با این حال، دستورالعمل‌های تابع شرایط کافی برای توابع به عنوان نوع داده‌های کلاس اول نیستند، زیرا یک تابع نوع داده کلاس اول است اگر و تنها اگر نمونه‌های جدیدی از تابع در زمان اجرا ایجاد شود؛ و این ایجاد زمان اجرای توابع در Smalltalk، جاوا اسکریپت، و اخیراً در Scala, Eiffel ("عوامل")، C # ("نمایندگان") و C ++ 11 در میان دیگر پشتیبانی می‌شود. استراتژی کاهش برای جزئیات بیشتر در مورد این موضوع، به استراتژی ارزیابی مراجعه کنید. این که آیا یک اصطلاح عادی است یا خیر، و چه مقدار کار باید انجام شود در عادی‌سازی آن، در صورت وجود، به شدت به استراتژی کاهش استفاده بستگی دارد. تمایز بین استراتژی‌های کاهش شامل تمایز در زبان‌های برنامه‌نویسی کاربردی بین ارزیابی مشتاق و ارزیابی تنبل است. این بدان معنی است که اساساً فقدان استراتژی کاهش خاص، با توجه به کاهش پذیری، «تمام شرط‌ها خاموش است». به‌طور مستقیم این به این معنی است که استدلال‌های تابع همیشه قبل از تابع خود کاهش می‌یابد. اکثر زبان‌های برنامه‌نویسی (از جمله Lisp, ML و زبان‌های ضروری مانند C و Java) به عنوان «سخت» توصیف می‌شوند، به این معنی که توابع اعمال شده به استدلال‌های غیرعادی غیرطبیعی هستند. این کار اساساً با استفاده از نظم اعمال انجام می‌شود، با کاهش ارزش تماس بگیرید (نگاه کنید به زیر)، اما معمولاً «ارزیابی مشتاق» نامیده می‌شود. به عبارت دیگر، هر گاه استدلال‌ها قبل از اینکه استدلال‌ها کاهش یابد، به انتزاعی تعویض می‌شوند. با ارزش تماس بگیرید فقط بازخوانی‌های خارج از محدوده کاهش می‌یابد: یک مقدار بازده کاهش می‌یابد تنها زمانی که سمت راست آن به یک مقدار کاهش می‌یابد (انتزاعی متغیر یا لامبدا). با نیاز تماس بگیرید به عنوان مثال عادی، اما عملکرد برنامه‌های کاربردی که اصطلاحات را تکرار می‌کنند، به جای آن آرگومان نامیده می‌شود، که پس از آن فقط «هنگامی که لازم است» کاهش می‌یابد. از آنجا که این تنها کاهش موجود است، Ω دارای فرم عادی نیست (تحت هر استراتژی ارزیابی). λy.x) (λx.x) Ω توسط اولین کاهش از Ω به شکل عادی کاهش می‌یابد (از آنجایی که آن مجذور راست‌ترین است)، اما از آنجا که Ω دارای فرم عادی نیست، نظم اعمال ناکافی است برای پیدا کردن یک فرم عادی برای KIΩ. در مقابل، نظم طبیعی به اصطلاح نامیده می‌شود، زیرا اگر همیشه وجود داشته باشد، همیشه یک کاهش نرمال پیدا می‌کند. یک نقص این است که بازنگری در استدلال ممکن است کپی شود و نتیجه محاسبات تکراری (به عنوان مثال (λx.xx) λx.x) y) به λx.x) y) λx.x) y) با استفاده از این استراتژی؛ در حال حاضر دو بازخوانی وجود دارد، بنابراین ارزیابی کامل نیاز به دو مرحله دارد، اما اگر این استدلال ابتدا کاهش یافته باشد، در حال حاضر هیچ‌کدام وجود ندارد). معامله مثبت استفاده از دستور applicative این است که اگر همه استدلال‌ها مورد استفاده قرار گیرد، محاسبات غیرضروری را ایجاد نمی‌کند، زیرا هرگز استدلال‌هایی را که حاوی redexes است جایگزین نمی‌کند و بنابراین هرگز نیازی به کپی کردن آن‌ها نیست (که کار را کپی می‌کند). بیشتر زبان‌های برنامه‌نویسی کاملاً کاربردی (به ویژه میراندا و نسل‌های آن، از جمله Haskell) و زبان‌های اثبات شده از قضیه‌های پیشین، از ارزیابی تنبل استفاده می‌کنند که اساساً همان چیزی است که نیاز به نیاز دارد. این همانند کاهش نظم طبیعی است، اما نیاز به مدیریت می‌شود تا از تقسیم کار ذاتی در کاهش سفارش معمول با استفاده از اشتراک استفاده شود. در مثال فوق داده شده (λx.xx) λx.x) y) به λx.x) y) λx.x) y) کاهش می‌یابد، که دارای دو بازخوانی است، اما در تماس با نیاز، آن‌ها نماینده با استفاده از همان شیء به جای کپی، بنابراین هنگامی که یکی کاهش می‌یابد دیگر نیز است. یک یادداشت در مورد پیچیدگی در حالی که ایده کاهش بتا به اندازه کافی ساده به نظر می‌رسد، این یک گام اتمی نیست، در حالی که هنگام تخمینی پیچیدگی محاسباتی باید هزینه‌ای بی‌اهمیت داشته باشد. برای دقیق بودن، باید مکان‌یابی هر رخداد متغیر محدود V را در عبارت E پیدا کرد، یعنی یک هزینه زمانی، یا باید مسیری را از این مکان‌ها به نحوی پیگیری کرد، یعنی یک هزینه فضایی است. رشته‌های مدیر سینو، راهی برای ردیابی مکان‌های آزاد متغیر در عبارات ارائه می‌دهد. همزمان‌سازی و هم‌زمان سازی اموال church-rosser از محاسبات لامبدا به معنی آن است که ارزیابی (کاهش بتا) می‌تواند در هر جهت، حتی به صورت موازی انجام شود. معناشناسی این واقعیت که شرایط محاسبات لامبدا در شرایط دیگر محاسبات لامبدا و حتی در خود عمل می‌کند، منجر به سوالاتی در مورد معناشناسی محاسبات لامبدا شد. با این وجود، هیچگونه غیرقطعی مانند D ممکن است با محدودیت‌های قدرتمندی وجود داشته باشد؛ زیرا مجموعه‌ای از همه توابع از D به D دارای قدرت بیشتری نسبت به D است، مگر اینکه D یک مجموعه تک تک باشد. | ## جمع‌بندی | در دهه ۱۹۷۰، دانا اسکات نشان داد که اگر تنها توابع پیوسته در نظر گرفته شوند، یک مجموعه یا دامنه D با ملک مورد نیاز یافت می‌شود، بنابراین یک مدل برای محاسبات لامبدا ارائه می‌شود.