Lambda taşı (veya λ-taşı ) a, resmi bir sistem tarafından icat Alonzo Church içinde 1930 kavramlar kurar, fonksiyon ve uygulama . Bir değişkeni bağlamak için Yunanca λ harfinin kullanıldığı , λ-ifadeleri adı verilen ifadeleri işleriz . Örneğin, M bir λ ifadesiyse, λx.M aynı zamanda bir λ ifadesidir ve x'in M'yi ilişkilendirdiği işlevi temsil eder.
Λ-kalkülüs, özyinelemeli fonksiyonları tanımlayan ve karakterize eden ilk biçimciliktir : bu nedenle, Turing makineleri ve Herbrand-Gödel modeli ile aynı derecede hesaplanabilirlik teorisinde büyük önem taşır . O zamandan beri bir şekilde uygulanmış olan teorik programlama dili ve olarak üstdil için resmi bilgisayar destekli gösteri . Lambda hesabı yazılabilir veya yazılamaz .
Lambda hesabı, Haskell Curry'nin kombinatoryal mantığı ile ilgilidir ve açık ikamelerin hesaplamalarında genelleştirilmiştir .
Lambda-kalkülüsün temel fikri, her şeyin bir fonksiyon olduğudur . Bir işlev, özellikle henüz tanımlanmamış işlevleri içerebilen bir ifade ile ifade edilir: ikincisi daha sonra değişkenlerle değiştirilir. Uygulama adı verilen temel bir işlem vardır :
İfadenin (bir işlevi tanımlayan) ifadeye (bir işlevi açıklayan) uygulanması not edilir .
E bir ifade ise, x ile E ifadesini eşleştiren fonksiyonu oluşturduğumuzu söyleyerek de fonksiyonlar yapabiliriz ; Biz yazmak λx.E bu yeni fonksiyonu.
Değişkenin adı, ∀y P (y) 'ye eşdeğer olan ∀x P (x) gibi bir ifadede olduğundan daha önemli değildir . Bir başka deyişle, eğer E [y / x] ifadesidir E tüm oluşumları hangi x olarak değiştirildi edilmiş y , biz ifadeleri olduğunu düşünecektir λx.E ve λy.E [y / x] eşdeğerdir.
Henüz edindiğimiz araçları kullanarak, uygulamalar ve soyutlamalar yoluyla, basitleştirmek veya değerlendirmek isteyebileceğimiz oldukça karmaşık işlevler elde ederiz. Formu basitleştirilmesi uygulaması (λx.E) p getirileri alternatif sentezleme haline dönüştürmek için E , her cereyan edişinde, burada serbest bir x ile ikame edilir , P . Bu basitleştirme biçimine kasılma (veya lambda-hesabının β kuralını uyguladığımızı hatırlamak istiyorsak bir β- daralması) denir .
Bu temelde, bir başka deyişle işleve uyan işlev olan özdeşlik işlevi gibi bazı ilginç işlevler oluşturabiliriz . Ayrıca sabit fonksiyonu eşit olarak inşa edebiliriz , yani .
Buradan, sabit fonksiyonları yapan fonksiyonu, bir parametre olarak sabit vermemiz şartıyla, diğer bir deyişle fonksiyonu , yani fonksiyonu sürekli olarak karşılık gelen hale getiren fonksiyonu inşa edebiliriz .
Örneğin başka bir fonksiyonun parametrelerinin kullanımına izin veren bir fonksiyon da oluşturabiliriz, daha doğrusu bir ifade ise, bunun gibi çalışmasını isteriz . İşlev işlevdir . Biz fonksiyonunu uygularsanız için elde ederiz biz basitleştirmek anlamına .
Şimdiye kadar oldukça gayri resmi davrandık. Lambda-hesaplama fikri, fonksiyonları tanımlamak ve basitleştirmek için kesin bir dil sağlamaktır.
Lambda hesabı, lambda-terimleri (veya bazen ayrıca lambda ifadeleri ) olarak adlandırılan ve üç kategoriye giren sözdizimsel varlıkları tanımlar :
Haritası ise şu şekildedir: görülebilir u bir işlevdir ve eğer v onun argümanı, daha sonra uv harita sonucudur v fonksiyonunun u .
Soyutlama λ x . v , x ile v'yi ilişkilendiren işlevin biçimlendirilmesi olarak yorumlanabilir , burada v genel olarak x oluşumlarını içerir .
Böylece, fonksiyon f lambda terimi alır x bir parametre olarak ekler ve buna 2 (yani, mevcut bir matematiksel gösterimde fonksiyonu f : X ↦ x + 2 ) ifadesi, lambda-Diferensiyel ifade edilecektir λ x . x +2 . Bu fonksiyonun 3 sayısına uygulanması ( λ x . X +2) 3 yazılır ve 3 + 2 ifadesinde “değerlendirilir” (veya normalize edilir) .
Alonzo Church yaptığı hesabın ile bu ilişkiyi biliyordu ve Russell ve Whitehead ' Principia Mathematica . Şimdi bunlar soyutlamayı belirtmek için gösterimi kullanıyor , ancak Church bunun yerine daha sonra haline gelen gösterimi kullandı . Peano ayrıca Matematiksel Biçiminde soyutlamayı tanımladı , özellikle gösterimi, gibi işlevi not etmek için kullanıyor .
Uygulamaları sınırlandırmak için parantezler kullanılmıştır, ancak anlaşılır olması için bazı parantezler çıkarılmıştır. Örneğin, (( x 1 x 2 ) ... x n ) için x 1 x 2 ... x n yazıyoruz .
Aslında iki kural vardır:
Shönfinkel ve Curry , curryfication'ı tanıttı : Bu, bir fonksiyonu birkaç argümanla temsil etme sürecidir. Örneğin, çift (fonksiyon x , y ) ilişkilendirir u ile, bir fonksiyonu olarak kabul edilir x , bir işlev düzenler ki, ile y , iştirakçi u . Bu nedenle ifade edilir: λx. (Λy.u) . Ayrıca λx.λy.u veya λxλy.u veya sadece λxy.u yazılır . Örneğin, çift (fonksiyon x , y ) ilişkilendirir x + y ifade edilecektir λx.λy.x + y ya da daha basit bir şekilde λxy.x + y .
Genel olarak matematiksel ifadelerde ve özellikle lambda hesabında, iki değişken kategorisi vardır: serbest değişkenler ve bağlantılı (veya aptal ) değişkenler . Lambda-analizinde, bir değişken bir λ ile bağlanır. Bağlı bir değişkenin bir kapsamı vardır ve bu kapsam yereldir. Ek olarak, içinde göründüğü tüm ifadenin genel anlamını değiştirmeden bağlı bir değişkeni yeniden adlandırabilirsiniz. Sınırlı olmayan bir değişkenin serbest olduğu söylenir.
Matematikteki ilgili değişkenlerÖrneğin ifadede değişken serbesttir, ancak değişken bağlantılıdır (ile ). Bu ifade olarak "aynı" olduğunu , çünkü yerel bir isimdi, tıpkı olduğunu . Öte yandan aynı ifadeye karşılık gelmez çünkü özgürdür.
İntegralin, entegrasyon değişkenini bağlaması gibi, onu takip eden değişkeni de bağlar.
Örnekler :
Biz grubu tanımlayan VL (t) arasında serbest değişken bir dönem t indüksiyonu ile:
Herhangi bir serbest değişken içermeyen bir terimin kapalı (veya kapalı) olduğu söylenir. Ayrıca bu lambda teriminin bir birleştirici olduğunu söylüyoruz (ilgili kombinatoryal mantık kavramından ).
Kapalı olmayan bir terimin açık olduğu söylenir.
Lambda-hesabı için en önemli aracı ikame bir terimle, bir dönem içinde, bir değişken yerine sağlar. Bu mekanizma, ifadelerin değerlendirilmesinin, dolayısıyla lambda terimlerinin "hesaplanmasının" temel mekanizması olan indirgemenin temelindedir.
İkame bir lambda terimi içinde t değişken bölgesinin x bir terimle u ifade edilir [: = u x] t . Dikkatli olmazsak, ikame gerçekleşmeden önce serbest olan bir değişkeni bağlayabilecek değişken yakalama olgusundan kaçınmak için ikameyi doğru bir şekilde tanımlamak için bazı önlemler alınmalıdır.
Örneğin, U serbest değişken içeren y ve eğer X görünen t formu bir alt terimi bir olay olarak λy.v , yakalama olgusu görünebilir. İşlem t [x: = u] bir ikamesi olarak adlandırılan t ait x ile u ve ilgili endüksiyon ile tanımlanır t :
Not : son durumda, y'nin u'nun serbest değişkeni olmadığına dikkat edeceğiz . Aslında, daha sonra harici lambda tarafından "yakalanacaktır". Bu durumda ise, biz adlandırmak y ve tüm oluşumları v değişken tarafından z görünmez t veya u .
Α dönüşümü λy.v ve λz.v'yi [y: = z] tanımlar . Yalnızca bağlı değişkenlerinin yeniden adlandırılmasıyla (yakalanmadan) farklılık gösteren iki lambda teriminin α-dönüştürülebilir olduğu söylenir . Α dönüşümü, lambda terimleri arasındaki bir eşdeğerlik ilişkisidir .
Örnekler:
Not: α-dönüşümü, ikameden önce dikkatlice tanımlanmalıdır. Bu nedenle terim olarak λx.λy.xyλz.z , birden adlandırılamıyor x için y (biz yapılacağı λy.λy.yyλz.z biz adlandırmak, diğer yandan) x için z .
Bu şekilde tanımlandığında, ikame lambda-hesabına dışsal bir mekanizmadır, ayrıca meta-teorinin bir parçası olduğu söylenir. Bazı çalışmaların, açık ikame hesaplamaları denen şeylere yol açan lambda-kalkülüsüne dahili bir mekanizma olarak ikameyi sunmayı amaçladığını unutmayın .
Lambda-kalkülüs terimlerine bakmanın bir yolu, onları ikili düğümler (eşlemeler), tek düğümler (λ-soyutlamalar) ve yapraklar (değişkenler) olan ağaçlar olarak düşünmektir. Azalmalar biz onları bu şekilde görürseniz terimler veya ağaçları değiştirmeye yöneliktir; örneğin, indirgeme (λx.xx) (λy.y) verir (λy.y) (λy.y) .
Redex'e (λx.u) v formunda bir terim diyoruz , burada u ve v terimler ve x bir değişkendir. Bu tanımlar , beta-kasılma bölgesinin (ya da β-kasılması) (λx.u) v olarak U [x: = h] . Biz bir terim olduğunu söylemek C [u] için azaltır 'C [u] eğer u bir REDEX içine β-sözleşmeler ise u' , biz o zaman yazma C [u] → C [u '] , ilişki → denir kasılma .
Kasılma örneği :
(λx.xy) a , (xy) [x: = a] = ay verir .
Biz → belirtmek * Geçişli dönüşlü kapatma kasılma ilişkisi → ve biz diyoruz azaltma . Başka bir deyişle, indirgeme, sonlu, muhtemelen boş bir kasılma dizisidir.
Biz = tanımlayan β olarak simetrik ve geçişli dönüşlü kapağın kasılma ve denir beta-dönüşüm , β- dönüşüm daha sık ya da beta-denklik veya β- eşdeğerlik .
Β-denkliği, örneğin, birbirine indirgenemeyen, ancak bir dizi β-kısalmasından sonra aynı sonuca ulaşan terimleri karşılaştırmayı mümkün kılar. Örneğin (λy.y) x = β (λy.x) z çünkü iki ifade x'i verecek şekilde daralır .
Biçimsel olarak, elimizdeki M = β M ancak ve ancak ∃ K 1 , ..., N s , öyle ki m = n 1 , M '= N p tüm ve I den az , p ve daha büyük , 0 , N ı → N ben + 1 veya N i + 1 → N i .
Bu, bir dönüşümde indirgeme veya ters azaltma ilişkilerinin ( genişletmeler olarak adlandırılır ) uygulanabileceği anlamına gelir .
Ayrıca eta-indirgeme adı verilen ve şu şekilde tanımlanan başka bir işlemi de tanımlarız : λx.ux → η u , x u'da serbest görünmediğinde. Aslında ux, u fonksiyonu tarafından x'in görüntüsü olarak yorumlanır . Bu nedenle, λx.ux edilir ve ardından, fonksiyon olarak yorumlanır x , görüntü ilişkilendirir x ile u nedenle fonksiyonu olarak, u kendini.
Lambda terimiyle ilişkili hesaplama, ürettiği indirgeme dizisidir. Terim, hesaplamanın açıklamasıdır ve terimin normal formu (eğer varsa) sonuçtur.
Bir lambda süreli t olduğu söylenmektedir , normal biçimde herhangi bir beta-kasılma buna uygulanabilir eğer yani, t herhangi bir REDEX içeren ya da hiç lambda terimi varsa U öyle ki t u → . Normal formdaki terimlerin sözdizimsel yapısı aşağıda açıklanmaktadır.
Misal:λx.y (λz.z (yz))
Beta-daralmasının uygulanamayacağı ve t = β u olacak şekilde bir u terimi varsa , lambda-terimi t'nin normalleştirilebilir olduğunu söylüyoruz . Bu gibi U olarak adlandırılan normal formu ve t .
Bir lambda vadeli söylemek t olduğunu kuvvetle boylandırılabilir tüm indirimleri eğer t vardır sonlu .
Örnekler:Let Δ ≡ λx.xx be set .
Bir terim güçlü bir şekilde normalleştirilebilirse, normalleştirilebilir.
Kilise-Rosser teoremi: let t ve u olmak iki terimin öyle ki t = β u . Bir dönem söz konusudur v öyle ki t → * v ve u → * v .
Eşkenar dörtgen (veya izdiham) teoremi: izin t , u 1 ve u 2 be lambda terimler, bu T → * u 1 ve t → * u 2 . Sonra bir lambda vadeli vardır v öyle ki u 1 → * v ve u 2 → * v .
Sayesinde Church-Rosser teoremi bir kolaylıkla gösterilebilir normal formun benzersiz olduğu kadar, lamda-taşı tutarlılığı (yani, en az iki farklı olmayan beta dönüştürülebilir terimler vardır).
Seti oluşturan terimlerin yapısını normal biçimde tanımlayabiliriz . Bunun için seti oluşturan sözde tarafsız terimleri açıklıyoruz . Nötr terimler, bir değişkenin (örneğin ) normal formdaki terimlere uygulandığı terimlerdir. Yani, örneğin, eğer ... normal biçimdeyse nötrdür . Normal formdaki terimler, önünde sıfır, bir veya daha fazla λ olan nötr terimlerdir, diğer bir deyişle, normal formdaki terimlerin birbirini izleyen soyutlamalarıdır. Yani normal bir formdadır. Terimleri normal biçimde bir dilbilgisi ile tanımlayabiliriz.
Örnekler : nötrdür, yani normal formdadır. normal formdadır. tarafsızdır. normal formdadır. Öte yandan, normal formda değildir çünkü nötr değildir ve normal formdaki bir terimin soyutlaması değildir, aynı zamanda kendisinin bir β-redeks olması, dolayısıyla β-indirgenebilir olmasıdır.
Sözdizimi ve lambda hesabının indirgenmesi üzerine, terim sınıfını aşağı yukarı sınırlandırarak farklı hesaplamaları uyarlayabiliriz. Böylelikle lambda hesaplamalarının iki ana sınıfını ayırt edebiliriz: türlenmemiş lambda hesabı ve yazılan lambda hesaplamaları. Türler, muhtemelen bir azaltma stratejisi benimseyerek, yalnızca normalleştirilebilen terimleri tutmayı amaçlayan terimlerin ek açıklamalarıdır. Dolayısıyla, Church-Rosser ve normalizasyon özelliklerini karşılayan bir lambda-kalkülüsüne sahip olmayı umuyoruz .
Köri-Howard yazışma doğal kesinti sistemine bir yazılı lambda hesabı ile ilgilidir. Bir türün bir önermeye karşılık geldiğini ve bir terimin bir ispata karşılık geldiğini ve bunun tersinin de geçerli olduğunu belirtir.
Kodlamalar, doğal sayılar, özyinelemeli işlevler ve Turing makineleri dahil olmak üzere yaygın bilgisayar nesnelerini simüle eder. Tersine, lambda hesabı bir Turing makinesi ile simüle edilebilir. Church'ün tezi sayesinde , lambda-hesabının evrensel bir kalkülüs modeli olduğu sonucuna vardık.
Boole'larSözdizimi bölümünde, ilkelleri tanımlamanın pratik olduğunu gördük. Burada yapacağımız şey bu.
true = λab.a
false = λab.b
Bu sadece bir kodlamanın tanımıdır ve diğerlerini tanımlayabiliriz.
Bunu fark ediyoruz: gerçek xy → * x ve : yanlış xy → * y
Daha sonra alternatifi temsil eden bir lambda-terimi tanımlayabiliriz: if-then-else . Bu, boolean b ve iki lambda terimi olan u ve v olmak üzere üç bağımsız değişkeni olan bir işlevdir; bu, boolean doğruysa birinciyi, aksi takdirde ikincisini döndürür.
ifthenelse = λbuv. (buv) .
İşlevimiz doğrulandı: eğer daha sonra gerçek xy = (λbuv. (buv)) doğru xy ; daha sonra gerçek xy → (λuv. (gerçek uv)) xy ; ifthenelse true xy → * (doğru xy) ; daha sonra gerçek xy → * ((λab.a) xy) ; eğer sonra doğru xy → * x .
Aynı şekilde göreceğiz eğer sonra yanlış xy → * y .
Oradan, klasik Boole işlemleri için lambda terimimiz de var: hayır = λb.ifthenelse b yanlış doğru ; ve = λab.ifthenelse ab false (ya da λab.ifthenelse aba ); burada = λab.ifthenelse a true b (veya λab.ifthenelse aab ).
TamsayılarAşağıdaki tam sayı kodlamasına, tasarımcılarından sonra Kilise tamsayıları denir . Biz sorarız: 0 = λfx.x , 1 = λfx.fx , 2 = λfx.f (fx) , 3 = λfx.f (f (fx)) ve genel olarak: n = λfx.f (f (... (fx) ...)) = λfx.f n x ile f n kez yinelenir .
Bu nedenle, n tamsayısı, nf , x pair çiftiyle f n (x) 'i ilişkilendiren fonksiyonel olarak görülür .
Bazı fonksiyonlarArdıl işlevi kodlamanın başına veya sonuna f ekleyerek kodlamanın iki yolu vardır . Başlangıçta n = λfx.f n x var ve λfx.f n + 1 x istiyoruz . Bir eklemek edebilmek için gerekli olan f başında ya f (lambdas "altında") veya sonunda.
Diğer işlevler aynı prensip ile oluşturulmuştur. Örneğin, iki lambda terimini "birleştirerek": λnpfx.nf (pfx) .
Çarpmayı kodlamak için , bir işlevi tüm terim boyunca "yaymak" için f'yi kullanırız: λnpf.n (pf)
Selefi ve çıkarma ya basit değildir. Bunun hakkında daha sonra konuşacağız.
0'daki testi şu şekilde tanımlayabiliriz: if0thenelse = λnab.n (λx.b) a veya boolean λn.n (λx.false) true .
Yineleyicilerİlk önce tamsayılar üzerinde bir yineleme işlevi tanımlayalım: iterates = λnuv.nuv
v temel durumdur ve u bir işlevdir. Eğer n sıfır, biz hesaplamak olduğunu v , aksi takdirde biz hesaplamak u n (v) .
Örneğin aşağıdaki denklemlerden gelen ekleme
aşağıdaki gibi tanımlanabilir. Temel durum v sayısı p ve işlev u olan ardıl fonksiyonu . Toplamın hesaplanmasına karşılık gelen lambda terimi bu nedenle: ekle = λnp. iter n halef s . Not o eklenti np → * n halefi p .
ÇiftlerÇiftleri c = λz.zab ile kodlayabiliriz, burada a birinci element ve b ikinci elementtir . Bu çifti (a, b) göstereceğiz . İki kısma erişmek için π 1 = λc.c (λab.a) ve π 2 = λc.c (λab.b) kullanıyoruz . Biz tanıyacak gerçek ve sahte Boolean bu ifadelerde ve biz azaltmak için okuyucuya bırakacağım π 1 (λz.zab) için bir .
ListelerBir tamsayının, sadece uzunluğu dikkate alarak, elemanlarına bakmadığımız bir liste olduğunu fark edebiliriz. Elemanlara karşılık gelen bilgileri ekleyerek listeleri tamsayılara benzer bir şekilde oluşturabiliriz: [a 1 ; ...; bir n ] = λgy. ga 1 (... (ga n y) ...). Yani : [] = λgy.y; [a 1 ] = Agy.ga 1 y; [a 1 ; a 2 ] = λgy.ga 1 (ga 2 y).
Listelerdeki yineleyicilerTam sayılar üzerinde bir yineleme sunduğumuz gibi, listelere bir yineleme ekliyoruz. function_list tamsayılar için λlxm.lxm tarafından tanımlanır. Kavram hemen hemen aynı, ancak küçük nüanslar var. Bir örnekle göreceğiz.
örnek: Bir listenin uzunluğu şu şekilde tanımlanır:
x :: l, head x ve tail l'in ( ML notasyonu ) listesidir . Bir l listesine uygulanan uzunluk fonksiyonu şu şekilde kodlanır: λl.liste_it l (λym.add (λfx.fx) m) (λfx.x) Ya da sadece λl.l (λym.add 1 m) 0.
İkili ağaçlarTam sayıların, çiftlerin ve listelerin yapım ilkesi ikili ağaçlara genelleştirilmiştir:
Ağaç ya yaprak ya da düğümdür. Bu modelde, düğüm düzeyinde hiçbir bilgi depolanmaz, veriler (veya anahtarlar) yalnızca yaprak düzeyinde tutulur. Daha sonra bir ağacın yaprak sayısını hesaplayan işlevi tanımlayabiliriz: nb_feuilles = λa.arbre_it a (λbc.add bc) (λn.1) veya daha basitçe: nb_feuilles = λa.a add (λn.1)
SelefKilise'nin tam sayıları üzerinde selefi tanımlamak için çiftleri kullanmalıyız. Buradaki fikir, öncülü yinelemeyle yeniden yapılandırmaktır: pred = λn.π 1 ( iterates n (λc. (Π 2 c, halef (π 2 c))) (0,0)). Doğal tamsayılar üzerindeki öncül 0 olarak tanımlanmadığından, bir toplam fonksiyonu tanımlamak için, buradaki kuralı 0'a eşit olarak kabul ettik.
Örneğin pred 3 → * π 1 (iter 3 (λc. (Π 2 c, halef (π 2 c))) (0,0)) → * π 1 (2,3) → * 2 olduğunu kontrol ediyoruz .
Çıkarma işleminin şu şekilde tanımlanabileceğini anlıyoruz: sub = λnp.P pred n'yi, p n'den büyükse alt np'nin 0'a eşit olduğu kuralıyla yineler.
ÖzyinelemeSelefi ve yineleyiciyi birleştirerek, bir imleç elde ederiz . Bu yineleyiciden, argüman olarak iletilen işlevin öncülüne erişimi olması gerçeğiyle farklıdır.
rec = λnfx.π 1 (n (λc. (f (π 2 c) (π 1 c), halef (π 2 c))) (x, 0))
Sabit nokta birleştiriciler
Sabit nokta birleştirici, her F için X = FX denklemine bir çözüm oluşturmayı mümkün kılar . Bu, gcd gibi basitçe yineleme ile ifade edilmeyen işlevleri programlamak için kullanışlıdır ve özellikle kısmi işlevleri programlamak için gereklidir.
Curry nedeniyle en basit sabit nokta birleştirici : Y = λf. (Λx.f (xx)) (λx.f (xx)). Turing başka bir sabit nokta birleştirici önerdi: Θ = (λx. Λy. (Y (xxy))) (λx. Λy. (Y (xxy))).
Her neyse kontrol ediyoruz g. Sabit nokta birleştirici sayesinde, örneğin bağımsız değişken olarak bir işlevi alan ve bu bağımsız değişken işlevinin en az bir tam sayı için doğru olup olmadığını test eden bir işlev tanımlayabiliriz: teste_annulation = λg.Y (λfn.ou (gn) (f (halefi) n))) 0.
Örneğin, doğru ve yanlış boolelerin alternatif sırasını tanımlarsak : alternates = λn.itère n false değil, o zaman şunu kontrol ederiz: teste_annulation alternatifler → * veya (alternatifler 0) (Y (λfn.or (alternates n) ( f halef n)) (halef 0)) → * veya (alternatif 1) (Y (λfn. veya (alternatifler n) (f halef n)) (halef 1)) → * true.
Ayrıca gcd: pgcd = Y (λfnp.if0thenelse (alt pn) (if0thenelse (sub np) p (fp (sub np))) (fn (sub pn))) tanımlayabiliriz.
Özyinelemeli kısmi işlevlerle bağlantıİmleç ve sabit nokta, tamsayılar Kilise tamsayıları tarafından yorumlandığında herhangi bir özyinelemeli kısmi işlevin λ-kalkülüste tanımlanabilir olduğunu gösteren anahtar bileşenlerdir . Tersine, λ terimleri tamsayılarla kodlanabilir ve λ terimlerinin azalması (kısmi) özyinelemeli bir işlev olarak tanımlanabilir. Λ-hesabı bu nedenle bir hesaplanabilirlik modelidir .
Terimleri tür adı verilen ifadelerle açıklıyoruz . Bunu, bir terim yazmanın bir yolunu sağlayarak yapıyoruz. Bu yöntem başarılı olursa, terimin iyi yazılmış olduğunu söyleriz . Bunun, işlevin "ne yaptığına" dair bir gösterge vermesinin yanı sıra, örneğin, belirli bir türdeki nesneleri başka türden nesnelere dönüştürür, güçlü normalizasyonun , yani tüm terimler için tüm indirgemelerin sağlanmasına yardımcı olur normal bir formla sonuçlanır (bu, her bir başlangıç terimi için benzersizdir). Yani bu kapsamda yapılan tüm hesaplamalar sona eriyor. Basit tipleri , özellikleri türleri gibi vb işlevlere fonksiyonlar fonksiyonlar fonksiyonları fonksiyonları fonksiyonları inşa edilir Göründüğü ne olursa olsun, bu analizin ifade gücü çok sınırlıdır (bu nedenle, üstel ne de fonksiyonda tanımlanamaz ).
Daha resmi olarak, basit tipler aşağıdaki gibi oluşturulur:
Sezgisel olarak, ikinci durum, bir tür öğesi alan ve bir tür öğesi döndüren işlevlerin türünü temsil eder .
Bağlam formunun çiftlerinin bir dizi değişken ve bir türüdür. Bir yazım yargısı , aşağıdakilerle özyinelemeli olarak tanımlanan bir üçlüdür (daha sonra bunun iyi yazılmış olduğunu söyleriz ):
Lambda hesaplamasına sabitler eklediysek, onlara bir tür (aracılığıyla ) vermeliyiz .
Basitçe yazılmış lambda hesabı, matematikte ve dolayısıyla bir bilgisayar programında ihtiyaç duyduğumuz tüm hesaplanabilir fonksiyonları ifade edemeyecek kadar kısıtlayıcıdır . Basit bir şekilde yazılmış lambda-hesaplamasının dışavurumunun üstesinden gelmenin bir yolu, F sisteminde veya yapıların hesabında yapıldığı gibi, tip değişkenlerine izin vermek ve bunlar üzerinde nicemlemektir .
Lambda hesabı, fonksiyonel programlamanın teorik temelini oluşturur ve bu nedenle birçok programlama dilini etkilemiştir. Bunlardan ilki olan Lisp Türlenmemiş dildir ki. Daha sonra yazılan diller olan ML ve Haskell geliştirilecektir.
De Bruijn endeksleri, lambda hesabının bir gösterimidir ve bu , a-dönüşümü için her bir eşdeğerlik sınıfını bir terimle temsil etmeyi mümkün kılar . Bunun için de Bruijn , bir değişkenin her oluşumunu doğal bir tamsayı ile değiştirmeyi önerdi. Her doğal sayı, oluşumu bağlayıcısıyla ilişkilendirmek için geçilmesi gereken λ sayısını belirtir.
Böylece λ x terimi . xx , λ 0 0 terimi ile temsil edilirken, λx terimi . λy. λz .xz (yz) , λ λ λ 2 0 (1 0 ) ile temsil edilir , çünkü birinci durumda, x'ten bağlayıcısına giden yol hiçbir λ ile kesişmezken, ikinci durumda, x'in bağlayıcısındaki yol kesişir iki λ (yani λy ve λz ), bağlayıcısındaki y'nin yolu bir λ (yani λz ) ile kesişir ve bağlayıcısındaki z'nin yolu hiçbir λ ile kesişmez .
Başka bir örnek olarak, (λ x λ y λ z λ u. (X (λ x λ y. X))) (λ x. (Λ x. X) x) terimi ve ona α-eşdeğeri olan bir terim yani (λ x λ y λ z λ u. (x (λ v λ w. v))) (λ u. (λ t. t) u) , (λ λ λ λ (3 (λ λ 1 ))) (λ (λ 0) 0) (şekle bakın).