Payamvdn/NorthPersian_fa_wiki huggingface dataset:
عنصر لامبدا است. اگر tوsعناصر لامبدا باشند آنگاه (ts)عناصر لامبدا اسنت هیچ عبارت دیگری عناصر لامبدا نیست؛ بنابراین عناصر لامبدا معتبر هستند اگر شامل تکرار قوانین بالا باشند. اگرچه بعضی از پرانتزگذاری ها با استفاده از این قوانین حذف شده است. به عنوان مثال پرانتز خارج از محدوده به صورت معمول نوشته نمی شودبه نشانه گذاری پایین دقت کنید مفهوم یا برداشت لامبداx.tتوضیحی از توابع ناشناخته که این توانایی را دارد که ورودی xرا بگیرد و با tجایگزین کند بنابراین یک تابع ناشناخته را بیان می کند که xرا می گیرد و t را برمی گرداند. به عنوان مثال x.x2+2یک مفهوم از تابع f(x)=x2+2که از عناصر x2+2استفاده می کند تعریف تابع به همراه مفهوم لامبدا صرفاً تولید و تشکیل تابع است انا نه فراخوانی کردن آن. در کل پیوند متغیر xدر عنصر t. برنامه ts بیان گر برنامه ای از تابع tبا ورودی sاست. باعث صدا زدن تابع tبا ورودی sبرای تولید t(s) می شود. هیچ نظر و جنبه ای در حساب لامبدا برای اعلام متغیر نیست. با این تعریف مانند x.x+y(i.e. f(x)=x+y)می توان عنوان کرد. حساب لامبدا yرا متغیری عنوان می کند که هنوز مشخص و قابل تعریف نیست. مفهوم لامبدا x.x+yبه صو
رت نخوی معتبر است و هم چنین تابعی را تولید می کند که ورودی را با yکه هنوز ناشناخته هست جمع می کند. Bracketingهم استفاده می شود و هم برای عناصر غیرضروری مورد نیاز است. به عنوان مثالλx.((λx.x)x) و(λx.(λx.x)) دو عنصر مختلف را بیان می کنند (اگرچه که هر دو اگر گاهش داده شوند به یک آرش و مقدار می رسند). اینجا اولین مثال برای معرفی تابع است که این معرفی تابع و برگرداندن نتیجه برای درخواست xاز تابع فرزندان به حساب می آید (درخواست تابع و بعد بازگشت) مثال دوم معرفی و تعیین تابع که تابعی را برمی گرداند که با هر ورودی کار می کند و در آخر برنامهxرا برمی گرداند (بازگشت تابع و بعد از درخواست) توابعی روی توابع دیگر کار می کنند در حساب لامبدا توابع در واقع همان کلاس اول با ارزش بالا هستند پس ممکن است توابع به عنوان ورودی گرفته شوند یا به عنوان خروجی از بقیه توابع. به عنوان مثال λx.x نماینده ای برای معرفی تابع x=xو (λx.x)yنماینده تابعی کهyرا درخواست می کند. اگرچه(λx.y)تابع ثابت x=yرا بیان می کند تابعی که همیشه yرا برگرداند برای ورودی مشکلی ندارد. در حساب لامبدا برنامه توابع به نوان وابسته چپ در نظر گرفته شده است پس stxبه معنای
(st)xمی باشد. ایده های متفاوتی برای همبستگی و کاهش وجود دارد که عناصر لامبدا به عناصر وابسته لامبدا کاهش پیدا کنند. همبستگی آلفا اساس همبستگی که روی عناصر لامبدا قابل تعریف است را همبستگی آلفا گویند. بینشی برای انتخاب مشخص در محدوده متغیر را می گیرد که در مفهوم لامبدا مشکلی با این تعریف نیست. به عنوان مثال mx.xوmy.yدو همبستگ=ی آلفا از عناصر لامبدا هستند و هر دو نماینده یک تابع می باشند (تابع مشخص شده). دو عنصر xوyهمبستگی آلفا ندارند زیرا در محدوده مفهوم لامبدا قرار نگرفته اند. در بسیاری از بیانات پیدا کردن همبستگی آلفا با عناصر لامبدا کاری معمول و رایج است. پیدا کردن بسیار مهم تر از پیدا کردن کاهش بتا است. متغیرهای آزاد متغیرهای آزاد برای یک عنصر متغیرهایی است که در محدوده مفهوم لامبدا نباشند. متغیرهای آزاد این گونه معرفی می شوند متغیر آزاد xهمان x است. متغیر آزاد λx.tهمان متغیر آزاد t است اما زمانی که xحذف شود. متغیر آزاد tsدر واقع همان متغیر آزاد tو متغیر آزاد s است. به عنوان مثال نماینده عناصر لامبدا که به این هویت و نشانه استλx.xمتغیر آزادی ندارد اما تابع λx.yxیک متغیر آزاد به نام yدارد. جلوگیری از جایگز
ینی کردن فرض کنید tوsوrعناصر لامبدا باشند و xوyمتغیر باشند. این نشانه گذاری t[x:=r]بان جایگزینی rبرایxدر tبا شیوه جلوگیری از گرفتن است؛ که به این شرح است. X[x:=r]=r Y[x:=r]=y if x≠y (mx.t)[x:=r]=mx.t (my.t)[x:=r]=my.(t[x:=r]) if x≠y و هم چنین yجز متغیر آزاد rبه حساب نمی آید.. متغیر yبه r درخواست نو شدن می دهد. به عنوان مثال (mx.x)[y:=y]=mx.(x[y:=y])=mx.x و((mx.y)[x:=y])=((mx.y)(x[x:=y])=(mx.y)y. نو شدن شرایط (به اینکه y از متغیرهای آزاد r نباشد احتیاج دارد) حیاتی تر از اطمینان یافتن است زیرا جایگزینی نباید معنی تابع را تغییر دهد. به عنوان مثال جایگزینی از شرایط نو چشم پوشی می کند(λx.y) [y:=x]= λx.(y[y:=x])= λx.xکه این جایگزینی تابع ثابت λx.yبه λx.xاست. در کل دیدن شرایط نو که به وسیله تغییر نام آلفا همراه با متغیرهای تازه تصفیه شده باشد با شکست رو به رو می شود به عنوان مثال رفتن به عقب برای جایگزینی صحیح در (λx.y)[y:=x]مفهوم لامبدا با متغیر تازه zتغییر نام داده است که شامل(λz.y)[y:=x]= λz.(y(y:=x])= λz.xکه یعنی تابع با جایگزینی حفظ شده است. کاهش بتا قانون کاهش بتا برنامه ای است برای فرم (λx.t)sکه به t[x:=s]کاه
ش پیدا کرده است. نشانه گذاری (λx.t)s=t[x:=s]که استفاده می شود تا نشان دهد (λx.t)sکاهش بتا در t[x:=s]به عنوان مثال برای تمام s(λx.x)s=x[x:=s]=sکه این عبارت نشان می دهد که λx.xشناخته شده است. هم چنین (λx.y)sy[x:=s]=y نشان می دهد که λx.yیک تابع ثابت است. حساب لامبدا در واقع یک ورژن ایدئال از یک زبان برنامه نویسی تابعی است به مانند Haskellیاstandard ML. علاوه بر این کاهش بتا با محاسبات تطابق دارد. این گام می تواند به وسیله تبدیل بتا اضافی تکرار شود تا زمانی که برنامه ای برای کاهش وجود نداشته باشد. در حساب لامبدا نانوشته که در این جا وجود دارد که این کار کاهش را خاتمه نمی دهد. برای مثال فرض کنید عنصرλx.xx)(λx.xx))=Ωکه در اینجا(λx.xx)(λx.xx)=(xx)[x:= λ x.xx]=(x[x:= λx.xx])(x[x:= λx.xx])=(λx.xx)(λx.xx)در اینجا نصر به خودش کاهش پیدا می کند با استفاده از کاهش بتا و هم چنین عمل کاهش هیچ وقت خاتمه پیدا نمی کند. جنبه دیگر حساب لامبدا نانوشته تشخیص داده های مختلف را نمی دهد. به عنوان مثال مطلوب است که که تابعی که فقط با اعداد کار دارد نوشته شود. اگرچه حساب لامبدا نانوشته راهی برای جلوگیری از بیان ارزش درست و رشته هاو شی ه
ای بدون اعداد ندارد تعریف رسمی تعریف عبارات لامبدا عبارتند از: متغیرهای v1، v2، …، vn، ... نمادهای انتزاعی lambda ،' λ 'و نقطه '.' است. پرانتز () مجموعه ای از عبارات لامبدا، Λ، می تواند به صورت القایی تعریف شود: اگر 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. λy. λz.N به اختصار λxyz.N می باشد متغیرهای آزاد و محدود گفته می شود که اپراتور انتزاعی، λ، متغیر آن را هر جا که در انتهای انتزاع رخ می دهد، مرتبط کند. گفته می شود متغیرهایی که در محدوده یک انتزاع قرار می گیرند محدود می شوند. همه متغیرهای دیگر
نامیده می شوند. به عنوان مثال، در عبارت زیر، یک متغیر محدود و x آزاد است: λy.x x y. همچنین توجه داشته باشید که یک متغیر با انتزاع «نزدیکترین» آن محدود شده است. در مثال زیر، وقفه تک x در بیان توسط لامبدا دوم محدود می شود: λx.y (λx.z x) مجموعه ای از متغیرهای آزاد بیان Lambda, M، به عنوان FV (M) تعریف شده است و توسط بازگشتی بر ساختار اصطلاحات تعریف شده است، به شرح زیر است: 3. FV(M N) = FV(M) ∪ FV(N) گفته می شود که عبارت ای که حاوی هیچ متغیر آزاد نیست بسته می شود. عبارت lambda بسته نیز به عنوان ترکیبی شناخته می شود و معادل آن ها در منطق ترکیبی است. کاهش معنای عبارات لامبدا به این معناست که چگونه عبارات را می توان کاهش داد. سه نوع کاهش وجود دارد: α تبدیل: تغییر متغیرهای متناوب (آلفا). β-reduction: اعمال توابع به استدلال های آن ها (بتا). η-conversion: که مفهوم گسترش (eta) را ترسیم می کند. ما همچنین از معادلات حاصل می گوییم: دو عبارات β-معادل هستند، اگر آن ها می توانند β-تبدیل به یک عبارت مشابه باشند، و α / η-هم ارزی به طور مشابه تعریف می شوند. اصطلاح redex، کوتاهی برای عبارت reducible refers to subterms که می توان
د توسط یکی از قوانین کاهش کاهش یابد. به عنوان مثال (λx.M) N یک بتا-redex در بیان جایگزینی N برای x در M است؛ اگر x در M آزاد نباشد، λx.M x نیز eta-redex است. بیان که بازده کاهش می یابد، کاهش آن نامیده می شود؛ با استفاده از مثال قبلی، کاهش این عبارات به ترتیب M [x: = N] و M. α تبدیل تبدیل آلفا، که گاهی اوقات به عنوان تغییر نام آلفا شناخته می شود، نام نام متغیر را تغییر می دهد. به عنوان مثال، تبدیل آلفا λx.x ممکن است λy.y. شرایطی که فقط با تبدیل آلفا متفاوت هستند، معادل α نامیده می شوند. اغلب، در استفاده از محاسبات لامبدا، معادلات معادل α معادل است. قوانین دقیق برای تبدیل آلفا کاملاً بی اهمیت نیستند. اول، هنگامی که تبدیل آلفا یک انتزاع، تنها رخ داده های متغیر که تغییر نام داده اند، کسانی هستند که به یک انتزاع متعهد هستند. به عنوان مثال، تبدیل آلفا λx. λx.x می تواند به λy. λx.x منجر شود، اما نمی تواند نتیجه λy. λx.y. این دومین معنای متفاوت از اصل دارد. دوم، تبدیل آلفا امکان پذیر نیست اگر یک متغیر با یک انتزاع متفاوت گرفته شود. برای مثال، اگر x را با y در λx. λy.x جایگزین کنیم، می توانیم λy. λy.y را به دست آوریم
که کاملاً متفاوت نیست. در زبان های برنامه نویسی با محدوده استاتیک، تبدیل آلفا می تواند برای ایجاد وضوح نام ساده تر با اطمینان از اینکه نام متغیر یک نام را در دامنه حاوی مخفی می کند (نگاه کنید به تغییر نام آلفا برای ایجاد وضوح نام نامطلوب). در نماد شاخص De Bruijn، هر دو اصطلاح معادل آلفای معادل به صورت همگانی یکسان هستند. جایگزینی تعویض، نوشته شده E [V: = R]، فرایند جایگزینی تمام رخدادهای آزاد متغیر V در عبارت E با بیان R است. تعویض در شرایط λ-calculus توسط بازگشتی بر ساختار اصطلاحات تعریف شده است، همان طور که به این ترتیب (توجه داشته باشید: x و y فقط متغیر هستند در حالی که M و N هر عبارت λ هستند). x[x := N] ≡ N y[x := N] ≡ y, if x ≠ y (λx.M)[x := N] ≡ λx.M برای جایگزینی به یک انتزاع لامبدا، گاهی لازم است که بیان α تبدیل شود. به عنوان مثال، برای (λx.y) [y: = x] درست نیست (به خاطر آوردن (λx.x)، زیرا x جایگزین به صورت آزاد بود اما به پایان رسید. جایگزینی صحیح در این مورد (λz.x)، تا α-هم ارزی است. توجه داشته باشید که تعویض به صورت منحصر به فرد به α-هم ارزی تعریف شده است. β-کاهش کاهش بتا ایده برنامه کاربردی را ضبط
می کند. بتا-کاهش از نظر جایگزینی تعریف می شود: کاهش بتا ((λV.E) E ') E [V: E] است. به عنوان مثال، با فرض برخی از کدگذاری ۲، ۷، ×، ما کاهش زیر را داریم: ((λn.n × ۲) ۷) → ۷ × ۲. η-تبدیل Eta-conversion بیان عقلی را بیان می کند که در این چارچوب این است که دو توابع یکسان هستند اگر و فقط اگر آن ها نتایج مشابهی را برای تمام استدلال ها ارائه دهند. Eta-conversion بین λx (fx) و f تبدیل می کند هر زمان که x در فضای آزاد ظاهر نشود. اشکال طبیعی و همپوشانی برای محاسبه لامبدا ty، β-reduction به عنوان یک قانون بازنویسی نه به شدت نرمال و نه ضعیف نرمال کردن است. با این حال، می توان نشان داد که β-reduction با هم مخلوط است. (البته، ما به آلفا تبدیل می پردازیم، یعنی ما دو عددی معمول را در نظر می گیریم، اگر ممکن است به α-تبدیل یک به دیگری تبدیل شود) بنابراین، هر دو اصطلاح به شدت نرمال و شرایط ضعیف عادی، یک فرم طبیعی منحصر به فرد دارند. برای اصطلاحات به شدت نرمال، هر استراتژی کاهش تضمین می شود که فرم طبیعی را تولید کند، در حالی که برای اصطلاحات ضعیف نرمال، برخی از استراتژی های کاهش می توانند آن را پیدا نکنند. انواع داده ها کدگذاری
مقالات اصلی: رمزگذاریchurch و کدگذاری مگنسن اسکات محاسبات پایه لامبدا ممکن است برای مدل سازی بولی ها، ریاضیات، ساختار داده ها و رکود استفاده شود، که در زیر بخش های زیر نشان داده شده است. ریاضی در محاسبات لامبدا چندین روش ممکن برای تعریف اعداد طبیعی در محاسبات لامبدا وجود دارد، اما اکثر عبارات church هستند که می توانند به صورت زیر تعریف شوند: ۰ := λf. λx.x ۱ := λf. λx.f x ۲ := λf. λx.f (f x) ۳ := λf. λx.f (f (f x)) و غیره یا با استفاده از نحوه جایگزین ارائه شده در بالا در نماد: ۰ := λfx.x ۱ := λfx.f x ۲ := λfx.f (f x) ۳ := λfx.f (f (f x)) یک عدد church یک تابع مرتبه بالاتر است - یک تابع یک پارامتر تابع f را می گیرد و یک تابع تک استدلالی را بازمی گرداند. عدد n عنصر کلیسا یک تابع است که یک تابع f را به عنوان علامت می گیرد و ترکیب n-th f را به دست می دهد، یعنی تابع f با خود برابر n برابر است. این نشان دهنده f (n) است و در واقع n-th power f است (در نظر گرفته شده به عنوان یک اپراتور)؛ f (0) به عنوان تابع هویت تعریف می شود. چنین ترکیبات تکراری (از یک تابع f) به قوانین مادیات احترام می گذارند، به همین دلیل این عددها
را می توان برای محاسبات استفاده کرد. (در محاسبات لامبدا اصلی کلیسای، پارامتر رسمی بیان لامبدا حداقل یکبار در بدن تابع اتفاق افتاد که تعریف فوق از ۰ غیرممکن بود). ما می توانیم یک تابع جانشین را تعریف کنیم که یک عدد n را می گیرد و n + 1 را با اضافه کردن یک برنامه دیگر از f تعریف می کند، where '(mf) x' به معنی تابع 'f' است 'm' بار در 'x' اعمال می شود: SUCC: = λn. λf. λx.f (n f x) از آنجا که ترکیب m-th f با ترکیب n-th f به ترکیب m + n-th f می دهد، افزودن می تواند به صورت زیر تعریف شود: PLUS: = λm. λn. λf. λx.m f (n f x) PLUS را می توان به عنوان یک تابع در نظر گرفت که دو عدد طبیعی را به عنوان استدلال و بازگشت یک عدد طبیعی؛ می توان آن را تأیید کرد PLUS 2 3 و ۵ عبارات لامبدا β معادل هستند. از آنجا که اضافه کردن m به عدد n می توان با اضافه کردن 1 m بار، تعریف معادل آن است: PLUS: = λm. λn.m SUCC n به طور مشابه، ضرب می تواند به صورت زیر تعریف شود MULT: = λm. λn. λf.m (n f) متناوباً MULT: = λm. λn.m (PLUS n) 0 از آنجا که ضرب m و n همانند تکرار تابع add n تابع m است و سپس آن را به صفر اعمال می کند. انحراف در عبارات churc
h نسبتاً پیچیده است. POW: = λb. λe.e b عملکرد پیشینی تعریف شده توسط PRED n = n-1 برای یک عدد صحیح مثبت n و PRED 0 = ۰ به مراتب سخت تر است. فرمول PRED: = λn. λf. λx.n (λg. λh.h (g f)) (λu.x) (λu.u) می توان با نشان دادن الگویی که اگر T نامیده می شود (λg. λh.h (gf)), T (n) (λu.x) = (λh.h (f (n-1) (x))) برای n&gt; 0. دو تعریف دیگر از PRED در زیر آمده است، یکی با استفاده از شرط و دیگری با استفاده از جفت. با عملکرد پیشین، تفریق ساده است. تعریف کردن SUB: = λm. λn.n PRED m، SUB m n بازده m - n زمانی که m&gt; n و ۰ در غیر این صورت. منطق و پیش فرض ها به طور مشترک، دو تعریف زیر (به نام کلیسای booleans) برای مقادیر بولین TRUE و FALSE استفاده می شود: TRUE: = λx. λy.x FALSE: = λx. λy.y سپس با استفاده از این دو λ-term، می توانیم برخی از اپراتورهای منطقی را تعریف کنیم (این فقط فرمول های ممکن است؛ عبارات دیگر به همان اندازه صحیح هستند): AND := λp. λq.p q p OR := λp. λq.p p q NOT := λp.p FALSE TRUE IFTHENELSE := λp. λa. λb.p a b اکنون می توانیم برخی از توابع منطقی را محاسبه کنیم، مثلاً: و TRUE FALSE ≡ (λp. λq.p q p) TRUE FALSE
→β TRUE FALSE TRUE ≡ (λx. λy.x) FALSE TRUE →β FALSE و ما می بینیم که عدد درست عدد برابر با FALSE است. یک پیش فرض یک تابع است که مقدار boolean را بازمی گرداند. اساسی ترین اساسی ISZERO است، که اگر علامت آن عدد کلیسای عدد ۰ باشد، عدد را درست می کند، و علامت FALSE اگر علامت دیگری باشد، عدد کلیسای دیگری است: ISZERO: = λn.n (λx.FALSE) درست است. پیش فرض زیر تست می کند که آیا آرگومان اول کمتر از نسبت یا برابر با دوم است: LEQ: = λm. λn.ISZERO (SUB m n)، و از آنجا که m = n، اگر LEQ m n و LEQ n m باشد، ساختن پیش فرض برای برابری عددی ساده است. در دسترس بودن پیش فرض ها و تعریف بالا از TRUE و FALSE، آن را مناسب برای بیان عبارات "if-then-else" در محاسبات لامبدا ایجاد کنید. برای مثال، تابع پیشینی را می توان به صورت زیر تعریف کرد: PRED: = λn.n (λg. λk.ISZERO (g 1) k (PLUS (g k) 1)) (λv 0) 0 که می تواند با نشان دادن القاء الگویی که n (λg. λk.ISZERO (g 1) k (PLUS (g k) 1)) (λv.0) تابع افزودن n - 1 برای n&gt; 0 است. جفت یک جفت (2-tuple) را می توان از نظر TRUE و FALSE تعریف کرد، با استفاده از کلیسای رمزگذاری برای جفت ها. به عنوا
ن مثال، PAIR جفت (x, y) را محاسبه می کند، FIRST اولین عنصر جفت را باز می کند و SECOND دوم را بازمی گرداند. PAIR := λx. λy. λf.f x y FIRST := λp.p TRUE SECOND := λp.p FALSE NIL := λx.TRUE NULL := λp.p (λx. λy.FALSE) یک لیست مرتبط را می توان به عنوان NIL برای لیست خالی یا PAIR یک عنصر و یک لیست کوچکتر تعریف کرد. آزمون NULL پیش فرض برای مقدار NIL. (به جای آن، با NIL: = FALSE، ساختار l (λh. λt. λz.deal_with_head_h_and_tail_t) (deal_with_nil) نیاز به یک آزمون NULL صریح را از بین می برد). به عنوان مثال استفاده از جفت، تابع shift و increment کهm,n))به(n,n+1) می توان تعریف کرد به عنوان Φ: = λx.PAIR (SECOND x) (SUCC (SECOND x)) که به ما اجازه می دهد تا شاید نسخه شفاف تابع سلف: PRED: = λn.FIRST (n Φ (PAIR 0)). ر کوردها و نقاط ثابت همچنین نگاه کنید به: SKI حساب کاربری ترکیبی § خود برنامه ریزی و بازپخش Recursion تعریف یک تابع با استفاده از تابع خود است. محاسبات لامبدا نمی تواند این را به طور مستقیم به عنوان برخی از نشانه های دیگر بیان کند: تمام توابع در محاسبات لامبدا ناشناس هستند، بنابراین ما نمی توانیم به یک مقدار که ه
نوز تعریف شده است، در داخل عبارت لامبدا تعریف کنیم که همان مقدار است. با این وجود، می توان از طریق برگزاری یک عبارت لامبدا برای بازگشت خود به عنوان ارزش استدلال خود، به عنوان مثال در (λx.xx) E. دریافت کرد. تابع فاکتوریل F (n) را به صورت بازگشتی به وسیلهٔ تعریف می کنیم F(n) = 1, if n = 0; else n × F(n − ۱) در بیان لامبدا که برای نشان دادن این تابع است، پارامتر (به طور پیش فرض اول) فرض می شود که خودش را به عنوان مقدار خود دریافت می کند، به طوری که فراخوانی آن - استفاده از آن به یک استدلال - به مقدار بازگشتی تبدیل می شود؛ بنابراین برای رسیدن به بازگشت، استدلال در نظر گرفته شده به عنوان خود ارجاع (به نام r اینجا) همیشه باید در داخل بدن تابع در یک نقطه تماس منتقل شود: G := λr. λn.(1, if n = 0; else n × (r r (n−۱))) with r r x = F x = G r x to hold, so r = G and F := G G = (λx.x x) G خود نرم افزار در اینجا تکرار می کند، بیانگر لامبدا تابع را به فراخوانی بعدی به عنوان یک مقدار استدلال انتقال می دهد، و آن را در دسترس برای ارجاع و فراخوانی در آنجا قرار می دهد. این را حل می کند اما نیاز به نوشتن هر تماس مجدد را به عنوا
ن خود برنامه کاربردی دارد. ما می خواهیم یک راه حل عمومی بدون نیاز به نوشتن مجدد داشته باشیم: G := λr. λn.(1, if n = 0; else n × (r (n−۱))) with r x = F x = G r x to hold, so r = G r =: FIX G and F := FIX G where FIX g := (r where r = g r) = g (FIX g) so that FIX G = G (FIX G) = (λn.(1, if n = 0; else n × ((FIX G) (n−۱)))) با توجه به یک اصطلاح لامبدا با اولین آرگومان که نشانگر فراخوانی بازگشتی است (به عنوان مثال G در اینجا)، ترکیبی FIX نقطه ثابت یک بیان لامبدا خود تکراری را نشان می دهد که نشانگر تابع بازگشتی (در اینجا، F) است. این تابع به هیچ وجه نباید صریحاً به خود منتقل شود، زیرا خود تکرار به صورت پیشفرض تنظیم می شود، زمانی که آن ایجاد می شود، هر بار که آن را فراخوانی می شود؛ بنابراین بیان اصلی لامبدا (FIX G) در داخل خود، در نقطه تماس، دستیابی به خود ارجاع ایجاد می شود. در حقیقت، بسیاری از تعاریف ممکن برای این اپراتور FIX، ساده ترین آن ها وجود دارد: Y: = λg. (λx.g (xx)) (λx.g (xx)) در محاسبات لامبدا، Yg یک نقطه ثابت از g است، به عنوان گسترش به: codice_1 codice_2 codice_3 codice_4 codice_5 codice_4 codice_7 c
odice_2 codice_9 codice_4 codice_11 codice_4 codice_13 codice_2 codice_15 codice_4 codice_11 codice_4 codice_7 codice_2 codice_21 codice_22 حالا، برای فراخوانی بازگشتی ما به تابع فاکتوریل، ما به سادگی می توانیم (Y G) n, where n تعدادی است که فاکتوریل را محاسبه می کنیم. به عنوان مثال، با توجه به n = ۴، این می دهد: (Y G) 4 G (Y G) 4 (λr. λn.(1, if n = 0; else n × (r (n−1)))) (Y G) ۴ (λn.(1, if n = 0; else n × ((Y G) (n−۱)))) ۴ 1, if ۴ = 0; else ۴ × ((Y G) (4−۱)) ۴ × (G (Y G) (4−۱)) ۴ × ((λn.(1, if n = 0; else n × ((Y G) (n−۱)))) (۴−۱)) ۴ × (1, if ۳ = 0; else ۳ × ((Y G) (3−۱))) ۴ × (۳ × (G (Y G) (3−۱))) ۴ × (۳ × ((λn.(1, if n = 0; else n × ((Y G) (n−۱)))) (۳−۱))) ۴ × (۳ × (1, if ۲ = 0; else ۲ × ((Y G) (2−۱)))) ۴ × (۳ × (۲ × (G (Y G) (2−۱)))) ۴ × (۳ × (۲ × ((λn.(1, if n = 0; else n × ((Y G) (n−۱)))) (۲−۱)))) ۴ × (۳ × (۲ × (1, if ۱ = 0; else ۱ × ((Y G) (1−۱))))) ۴ × (۳ × (۲ × (۱ × (G (Y G) (1−۱))))) ۴ × (۳ × (۲ × (۱ × ((λn.(1, if n = 0; else n × ((Y G) (n−۱)))) (۱−۱))))) ۴ × (۳ × (۲ × (۱ × (1, if ۰ = 0; else ۰ × (
(Y G) (0−۱)))))) ۴ × (۳ × (۲ × (۱ × (۱)))) ۲۴ هر تابع تعریف بازگشتی را می توان به عنوان یک نقطه ثابت از برخی از تابع تعریف شده مناسب تعریف شده در تماس فراخوان با یک استدلال اضافی دیده می شود و بنابراین، با استفاده از Y، هر تابع تعریف بازگشتی را می توان به عنوان بیان لامبدا بیان کرد. به طور خاص، اکنون می توانیم تفکیک، ضرب و محاسبه مقادیر عدد طبیعی را به صورت مجزا تعریف کنیم. شرایط استاندارد اصطلاحات خاصی نام های رایج دارند: I: = λx.x K: = λx. λy.x S: = λx. λy. λz.x z (y z) B: = λx. λy. λz.x (y z) C: = λx. λy. λz.x z y W: = λx. λy.x y y U: = λx. λy.y (x x y) ω: = λx.x x Ω: = ω ω Y: = λg. (λx.g (xx)) (λx.g (xx)) محاسبات لامبدا تایپ شده یک محاسبات لامبدا تایپ شده یک فرمالیسم تایپی است که از نماد لامبدا ({ displaystyle lambda} lambda) برای انتساب تابع ناشناس استفاده می کند. در این زمینه، انواع معمولاً اشیاء طبیعت نحوی هستند که به شرایط لامبدا اختصاص دارند؛ نوع دقیق یک نوع بستگی به محاسبات دارد (نگاه کنید به انواع زیر). از دیدگاه خاص، محاسبات لامبدا تایپ شده را می توان به عنوان اصلاحاتی از محاسبات لامبدا غیرتصویر م
شاهده کرد، اما از دیدگاه دیگر، آن ها همچنین می توانند تئوری بنیادی تر و محاسبات لامبدا با استفاده از یک مورد خاص با تنها یک نوع در نظر گرفته شوند. زبان های تایپ شده لامبدا زبان های برنامه نویسی پایه هستند و پایه زبان های برنامه نویسی کارکردی مانند ML و Haskell و غیرمستقیم زبان های برنامه نویسی ضروری را تایپ می کنند. Calibles lambda تایپ شده نقش مهمی در طراحی سیستم های نوع زبان های برنامه نویسی بازی می کند. در اینجا typability معمولاً ویژگی های مطلوب برنامه را ضبط می کند، برای مثال برنامه باعث نقض دسترسی به حافظه نمی شود. محاسبات لامبدا تایپ شده با منطق ریاضی و تئوری اثبات شده از طریق Isomorphism کاری-هوارد مرتبط هستند و می توان آن ها را به عنوان زبان داخلی کلاس های دسته بندی، به عنوان مثال محاسبات لامبدا به سادگی تایپ شده است زبان رده بسته دکارتی (CCCs). توابع قابل محاسبه و محاسبات لامبدا یک تابع F: N → N از اعداد طبیعی یک تابع قابل محاسبه است اگر و فقط اگر یک عبارت lambda f وجود دارد به طوری که برای هر جفت x, y در N, F (x) = y اگر و فقط اگر fx = β y، جایی که x و y عددهای church مربوط به x و y هستند و به ترتی
ب β = β معادل بودن با کاهش بتا است. این یکی از روش های بسیاری برای تعریف محاسبات است. دیدگاه کلیسون تورینگ را برای بحث در مورد رویکردهای دیگر و همسانیشان ببینید. عدم قطعیت برابر بودن هیچ الگوریتمی وجود ندارد که به عنوان ورودی دو علامت لامبدا و خروجی TRUE یا FALSE را در نظر بگیرد که آیا دو عبارت برابر هستند یا نه. این مسئله از لحاظ تاریخی اولین مشکل بود که قابل اثبات نیست. همان طور که برای اثبات غیرقابل انکار بودن معمول است، اثبات نشان می دهد که هیچ تابع قابل محاسبه نمی تواند همسان سازی را تعیین کند. سپس پایان نامه کلیسا به نشان می دهد که هیچ الگوریتمی نمی تواند این کار را انجام دهد. اثبات کلیسا برای اولین بار مشکل را برای تعیین اینکه آیا یک لامبدا داده شده به شکل نرمال است، کاهش می دهد. یک فرم عادی بیان معادل است که نمی تواند تحت قوانینی که توسط فرم اعمال می شود کاهش یابد. سپس فرض می کند که این پیش فرض قابل محاسبه است و بنابراین می تواند در محاسبات لامبدا بیان شود. بر اساس کار قبلی Kleene و ساخت شماره Gödel برای عبارات لامبدا، او یک عبارت لامبدا را ایجاد می کند که دقیقاً به اثبات اولین قضیه ناقص گودل می رسد.
اگر e به شماره Gödel خود اعمال شود، یک تضاد حاصل می شود. محاسبات لامبدا و زبان های برنامه نویسی همان طور که توسط مقاله پیتر لندن در سال ۱۹۶۵ ذکر شده است A Correspondence between ALGOL 60 and Lambda-notation کلیسا، زبان برنامه نویسی رویه های متوالی را می توان از طریق محاسبات لامبدا، که مکانیسم اولیه برای انتزاع رویه و برنامه (زیر برنامه) کاربرد را فراهم می کند. توابع ناشناس به عنوان مثال، در Lisp تابع 'مربع' می تواند به صورت بیان lambda به صورت زیر بیان شود: مثال فوق یک عبارت است که به یک تابع کلاس اول ارزیابی می شود. نماد lambda تابع ناشناس ایجاد می کند، با توجه به لیستی از نام های پارامتر، (x) - فقط یک آرگومان در این مورد و یک عبارت است که به عنوان بدن تابع (* x x) ارزیابی می شود. توابع ناشناس گاهی اوقات عبارات لامبدا نامیده می شود. به عنوان مثال، پاسکال و بسیاری از زبان های ضروری دیگر، از طریق مکانیزم اشاره گرهای عملکرد، مدت زمان پشتیبانی از زیر برنامه ها را به عنوان استدلال برای دیگر برنامه های زیر پشتیبانی می کنند. با این حال، دستورالعمل های تابع شرایط کافی برای توابع به عنوان نوع داده های کلاس اول نیستند
، زیرا یک تابع نوع داده کلاس اول است اگر و تنها اگر نمونه های جدیدی از تابع در زمان اجرا ایجاد شود؛ و این ایجاد زمان اجرای توابع در Smalltalk، جاوا اسکریپت، و اخیراً در Scala, Eiffel ("عوامل")، C # ("نمایندگان") و C ++ 11 در میان دیگر پشتیبانی می شود. استراتژی کاهش برای جزئیات بیشتر در مورد این موضوع، به استراتژی ارزیابی مراجعه کنید. این که آیا یک اصطلاح عادی است یا خیر، و چه مقدار کار باید انجام شود در عادی سازی آن، در صورت وجود، به شدت به استراتژی کاهش استفاده بستگی دارد. تمایز بین استراتژی های کاهش شامل تمایز در زبان های برنامه نویسی کاربردی بین ارزیابی مشتاق و ارزیابی تنبل است. کاهش بتا کامل هر گونه بازدهی می تواند در هر زمان کاهش یابد. این بدان معنی است که اساساً فقدان استراتژی کاهش خاص، با توجه به کاهش پذیری، «تمام شرط ها خاموش است». سفارش کاربردی راست ترین، بازخورد بیرونی همیشه اولین بار کاهش می یابد. به طور مستقیم این به این معنی است که استدلال های تابع همیشه قبل از تابع خود کاهش می یابد. دستور Applicatory همیشه تلاش می کند تا توابع را به فرم های معمول اعمال کند، حتی اگر این امکان پذیر نباشد. اکثر زبا