Lambda hesablaması

Lambda hesablanması(λ-hesablama) —hesablamaanlayışını formalaşdırmaq və təhlil etmək üçünAmerikariyaziyyatçısıAlonzo Çörçtərəfindən hazırlanmış rəsmi birsistem.
Safλ{\displaystyle \lambda }- hesablamasışərtləri həmçinin , obyektləri ("obami")və ya Lambda(hərf-λ)şərtləri adlanan tətbiq vəabstraksiyaistifadə edərək yalnız dəyişənlərdən qurulmuşdur. Əvvəlcə hər hansı bir sabitliyin olmasıehtimaledilmir.
Əsasənλ-hesablamaiki əsas əməliyyata əsaslanır:
Lambda baxımından müəyyən edilən ekvivalentliyin əsas formasıalfaekvivalentliyidir. Məsələn,λx.x{\displaystyle \lambda x.x}vəλy.y{\displaystyle \lambda y.y}: alfa ekvivalent lambda şərtləri və hər ikisi eyni funksiyanıtəmsiledir: alfa ekvivalent lambda terminləri və hər ikisi eyni funksiyanıtəmsiledir. Lambdaabstraksiyasındaolmadığı üçünx{\displaystyle x}vəy{\displaystyle y}şərtləri alfaekvivalentideyildir.
λx.2⋅x+1{\displaystyle \lambda x.2\cdot x+1}ifadəsi bu funksiyanı ifadə edir,qəbulu hər birinə görəx{\displaystyle x}dəyəri2⋅x+1{\displaystyle 2\cdot x+1}, sonra ifadəni hesablamaq üçün
həm tətbiqi,x{\displaystyle x}dəyişən əvəzinə həm də mücərrədliyi ehtiva edən müddətdə 3 sayının dəyişdirilməsini yerinə2⋅x+1{\displaystyle 2\cdot x+1}yetirmək lazımdır. Nəticədə2⋅3+1=7{\displaystyle 2\cdot 3+1=7}alınır. Bu mülahizə ümumi şəkildə
yazılır vəβ-azalmaadlanır. İfadənin növü {\displaystyle (\lambda x.t)\ a}(\lambda x.t)\ a-ya, yəni müəyyən bir müddətə birabstraksiyatətbiq etmək, redex adlanır (redex). Baxmayaraq ki,sonra, oβ-azalmalambda — hesablanmasının əslində çox əsaslı və mürəkkəb bir nəzəriyyəyə səbəb olan yeganə "əsas"aksiomadır{\displaystyle \lambda }\. Onunla birlikdəλ{\displaystyle \lambda }- hesablaması Tyurinq tamlıq xüsusiyyətinə malikdir və buna görə də ən sadəproqramlaşdırmadilidir.
η{\displaystyle \eta }— çevrilməsi iki funksiyanın eyni və yalnız olduqda eyni olduğunu düşüncəsini,nə zaman, hər hansı bir dəlil tətbiq olunanda eyni nəticələri ifadə edir.η{\displaystyle \eta }- dönüşümüλx.fx{\displaystyle \lambda x.f\ x}иf{\displaystyle f}düsturlarınıbir-birinə çevirir(əgər ki,x{\displaystyle x}-ınf{\displaystyle f}-ya sərbəst girişi yoxdursa: əks halda sərbəst dəyişənx{\displaystyle x}çevrilmədən sonra əlaqəli xariciabstraksiyavə ya əksinə olacaq).
İki dəyişənin funksiyasıx{\displaystyle x}иy{\displaystyle y}f(x,y)=x+y{\displaystyle f(x,y)=x+y}x{\displaystyle x}-ın bir dəyişənin funksiyası hesab edilə bilər, bir dəyişən funksiyasını qaytarany{\displaystyle y}, yeni bir ifadəλx.λy.x+y{\displaystyle \ \lambda x.\lambda y.x+y}olur. Bu texnika istənilən ariyanın funksiyaları üçün eyni şəkildə işləyir. Bu göstərir ki, bir çox dəyişənlərin funksiyalarıλ{\displaystyle \lambda }— hesablaması ilə ifadə edilə bilər və "Sintaktik şəkər"dir. Bir çox dəyişkənliyin funksiyalarını bir dəyişənin funksiyasına çevirmək təsvir edilənproses,AmerikariyaziyyatçısıHaskell Kurrinin şərəfinə,karinqadlanır (M.E.Sheinfinkel (1924)).
Bu bir faktdır ki,λ{\displaystyle \lambda }— lambda hesablamasının şərtləri funksiyaları kimi fəaliyyət göstərir,λ{\displaystyle \lambda }— şərtlərə tətbiq olunur(bu bəlkə də,özü-özünə),λ{\displaystyle \lambda }— hesablamasıadekvatsemantikanınqurulmasında çətinliklərə səbəb olur.λ{\displaystyle \lambda }— hesablanmasına hər hansı bir məna vermək üçün,D{\displaystyle D}çoxluğunu almaq zəruridir,hansıki,onunfunksionalməkanınaD→D{\displaystyle D\to D}sərmayə qoyulacaqdı. Bunun ümumi vəziyyətindəD{\displaystyle D}D{\displaystyle D}vəD{\displaystyle D}-danD{\displaystyle D}-yə qədər funksiyalarbu iki çoxluğun gücünün məhdudlaşdırılması səbəbindən mövcud deyildir: ikincisi birincisindən daha çox gücə malikdir.
Bu çətinliyi 1970-ci illərin əvvəllərində Dana Skott aradan qaldırdı,D{\displaystyle D}birdomenanlayışını quraraq (əvvəlcə tam rəflərdə,daha sonra tam bir qismən sifariş edilmiş xüsusi bir topologiya ilə ümumiləşdirərək) və kəsərəkD→D{\displaystyle D\to D}davamlı olaraq bu funksiyasını yaratdı. Bu konstruksiyaların əsasında,bunların köməyi iləproqramlaşdırma dillərininrekursion və məlumat növləri kimiikivacib quruluşa dəqiq məna verə bilməsi üçün xüsusənproqramlaşdırma dillərininDenotasiya semantikasıyaradıldı.
Rekursiya— özü vasitəsilə bir funksiyanın tərifidir; ilk baxışdan lambda hesablaması buna imkan vermir,lakin bu təəssürat yanıldır. Məsələn,faktorialhesablayan bir rekursiv funksiyasını nəzərdən keçirək:
Lambda hesablamasında bir funksiya birbaşa özünəistinadedə bilməz. Bununla birlikdə, bir funksiya funksiyaya ötürülə bilər. Bir qayda olaraq, bumübahisəəvvəlcə gəlir.Bir funksiya ilə əlaqələndirərək yeni, onsuz da təkrarlanan bir funksiya əldə edirik. Bunun üçün özünə istinad edən bir dəlil (buradar{\displaystyle r}olaraq təyin olunur),funksiya orqanına ötürülməlidir.
Bu,faktorialhesablama problemini həll edir, lakin ümumi birhəlldə mümkündür. Rekursiv bir funksiya və ya dövrü təmsil edən bir lambda müddəti alaraq, özünü ilk dəlil olaraq keçərək sabit nöqtəli kombinator lazımi rekursiv funksiyanı və ya dövrü geri qaytaracaqdır. Funksiyaların hər dəfə açıq şəkildə özlərini keçməsinə ehtiyac yoxdur.
Sabitnöqtəli kombinatorların bir neçə tərifi var. Onlardan ən sadəsi:
g (Y g) 4
Bir rekursiv funksiyanın hər tərifi müvafiq funksiyanın sabit bir nöqtəsi kimi göstərilə bilər, buna görə dəY{\displaystyle \operatorname {Y} }istufadə edilərək,hər rekursiv tərif lambda ifadəsi kimi ifadə edilə bilər. Xüsusilə, toplama işlənməsini,vurma,natural ədədlərinmüqayisəsini rekursiv olaraq təyin edə bilərik.
Proqramlaşdırma dillərində "λ{\displaystyle \lambda }-hesablaması" tez-tez " anonim funksiyaların" mexanizmi başa düşülür — callback funksiyaları,hansı ki,istifadə edildikləri yerlərdə və cari funksiyanın (dəyişmə) lokal dəyişənlərinə giriş imkanı olan yerlərdə müəyyən edilə bilər.
Барендрегт X.Ламбда-исчисление. Его синтаксис и семантика. M.: Мир. 1985. səh. 606 .