Lambda hesabı - Lambda calculus

Lambda taşı (aynı zamanda yazılı λ-hesabı ) a, resmi bir sistem içinde matematiksel mantık ifade etmek için hesaplama işlevi göre soyut ve uygulama değişkenini kullanarak bağlama ve ikame . Herhangi bir Turing makinesini simüle etmek için kullanılabilen evrensel bir hesaplama modelidir . 1930'larda matematikçi Alonzo Church tarafından matematiğin temelleri üzerine yaptığı araştırmanın bir parçası olarak tanıtıldı .

Lambda hesabı, lambda terimlerinin oluşturulması ve bunlar üzerinde indirgeme işlemlerinin yapılmasından oluşur. Lambda hesabının en basit biçiminde, terimler yalnızca aşağıdaki kurallar kullanılarak oluşturulur:

Sözdizimi İsim Açıklama
x Değişken Bir parametreyi veya matematiksel/mantıksal değeri temsil eden bir karakter veya dize.
x . E ) Soyutlama Fonksiyon tanımı ( M bir lambda terimidir). x değişkeni ifadede bağlı hale gelir .
( M , N ) Başvuru Bir argümana bir fonksiyon uygulama. M ve N lambda terimleridir.

xy .(λ z .(λ x . zx ) (λ y . zy )) ( xy ) gibi ifadeler üretir . İfade açıksa parantezler bırakılabilir. Bazı uygulamalar için mantıksal ve matematiksel sabitler ve işlemler için terimler dahil edilebilir.

Azaltma işlemleri şunları içerir:

Operasyon İsim Açıklama
x . M [ x ]) → (λ y . M [ y ]) α-dönüşüm İfadedeki bağlı değişkenleri yeniden adlandırma. Ad çakışmalarını önlemek için kullanılır .
((λ x . E ) E ) → ( M [ X  : = e ]) β-indirgeme Soyutlamanın gövdesindeki bağımsız değişken ifadesi ile bağlı değişkenlerin değiştirilmesi.

Eğer De Bruijn ve indeksleme kullanılan isim çarpışmalar olacak şekilde, daha sonra α-dönüşüm artık gerekli değildir. Eğer tekrarlanan uygulama azaltma sonunda sona erer adımlar, o zamana kadar kilise-Rosser teoremi bir üretecek β-normal form .

Iota ve Jot gibi , çeşitli kombinasyonlarda kendisini çağırarak herhangi bir işlev davranışı oluşturabilen evrensel bir lambda işlevi kullanılıyorsa, değişken adlarına gerek yoktur .

Açıklama ve uygulamalar

Lambda hesabı Turing tamamlandı , yani herhangi bir Turing makinesini simüle etmek için kullanılabilecek evrensel bir hesaplama modelidir . Onun adaşı olan Yunanca lambda (λ) harfi, lambda ifadelerinde ve lambda terimlerinde bir fonksiyondaki bir değişkenin bağlanmasını belirtmek için kullanılır .

Lambda taşı olabilir Türlenmemiş veya daktilo . Yazılı lambda hesabında, işlevler yalnızca verilen girdinin "tür" verisini kabul edebiliyorlarsa uygulanabilir. Yazılı lambda hesapları, bu makalenin ana konusu olan tipsiz lambda hesaplarından daha zayıftır , şu anlamda tipe lambda hesapları, tipsiz lambda hesaplarından daha az ifade edebilir, ancak diğer yandan yazılan lambda hesapları daha fazla şeyin kanıtlanmasına izin verir. ; örneğin basit yazılan lambda hesabında , her değerlendirme stratejisinin basitçe yazılan her lambda terimi için sona erdiği bir teoremdir, oysa türlenmemiş lambda terimlerinin değerlendirmesinin sonlandırılmasına gerek yoktur. Birçok farklı tipte lambda hesabı olmasının bir nedeni, kalkülüs hakkında güçlü teoremleri kanıtlamaktan vazgeçmeden daha fazlasını (tiplenmemiş hesabın yapabileceklerinden) yapma arzusudur.

Lambda hesabının matematik , felsefe , dilbilim ve bilgisayar bilimlerinde birçok farklı alanda uygulamaları vardır . Lambda hesabı, programlama dilleri teorisinin gelişmesinde önemli bir rol oynamıştır . Fonksiyonel programlama dilleri lambda hesabını uygular. Lambda hesabı da Kategori teorisinde güncel bir araştırma konusudur .

Tarih

Lambda hesabı, 1930'larda matematikçi Alonzo Church tarafından matematiğin temelleri üzerine bir araştırmanın parçası olarak tanıtıldı . Orijinal sistemin mantıksal olarak tutarsız olduğu 1935'te Stephen Kleene ve JB Rosser'ın Kleene-Rosser paradoksunu geliştirmesiyle gösterildi .

Daha sonra, 1936'da Church, şimdi türlenmemiş lambda hesabı olarak adlandırılan hesaplamayla ilgili kısmı izole etti ve yayınladı. 1940'ta, basit yazılan lambda hesabı olarak bilinen, hesaplama açısından daha zayıf, ancak mantıksal olarak tutarlı bir sistem de tanıttı .

1960'lara kadar programlama dilleriyle ilişkisi netlik kazanıncaya kadar lambda hesabı sadece bir formalizmdi. Sayesinde Richard Montague ve doğal dilin semantik diğer dilbilimcilerin uygulamalar, lambda hesabı dilbilim ve bilgisayar bilimleri hem saygın bir yer keyfini başlamıştır.

lambda sembolünün kökeni

Church'ün lambda hesabında fonksiyon-soyutlama gösterimi olarak Yunanca lambda (λ) harfini kullanmasının nedeni konusunda , belki de kısmen Church'ün kendisinin yaptığı çelişkili açıklamalar nedeniyle bazı belirsizlikler vardır . Cardone ve Hindley'e (2006) göre:

Bu arada, Church neden “λ” işaretini seçti? [Harald Dickson'a yayınlanmamış 1964 tarihli bir mektubunda], bunun Whitehead ve Russell tarafından sınıf soyutlaması için kullanılan “ ” notasyonundan geldiğini, ilk önce “ ” yi “∧ ” olarak değiştirerek fonksiyon-soyutlamayı sınıf soyutlamasından ayırt etmek için kullandığını açıkça belirtti. ve ardından yazdırma kolaylığı için “∧” öğesini “λ” olarak değiştirin.

Bu köken de [Rosser, 1984, s.338]'de bildirilmiştir. Öte yandan, daha sonraki yıllarda Church, iki araştırmacıya seçimin daha tesadüfi olduğunu söyledi: bir sembole ihtiyaç vardı ve λ sadece seçildi.

Dana Scott da bu soruyu çeşitli halka açık konferanslarda ele aldı. Scott, bir keresinde Church'ün damadı John Addison'a lambda sembolünün kökeni hakkında bir soru yönelttiğini ve daha sonra kayınpederine bir kartpostal yazdığını anlatıyor:

Sevgili Profesör Kilisesi,

Russell'ın iota operatörü , Hilbert'in epsilon operatörü vardı . Operatörünüz için neden lambda'yı seçtiniz?

Scott'a göre, Church'ün tüm yanıtı, kartpostalın şu açıklamayla birlikte iade edilmesinden ibaretti: " eeny, meeny, miny, moe ".

Resmi olmayan açıklama

Motivasyon

Hesaplanabilir fonksiyonlar , bilgisayar bilimi ve matematikte temel bir kavramdır. Lambda hesabı, hesaplama için basit bir anlambilim sağlar ve hesaplama özelliklerinin resmi olarak çalışılmasını sağlar. Lambda hesabı, bu semantiği basitleştiren iki basitleştirme içerir. İlk basitleştirme, lambda hesabının işlevleri açık adlar vermeden "anonim olarak" ele almasıdır. Örneğin, işlev

olarak anonim biçimde yeniden yazılabilir

(ki olarak okunur "bir başlığın bir x ve y olan eşleştirilmiş için "). Benzer şekilde, fonksiyon

olarak anonim biçimde yeniden yazılabilir

girişin basitçe kendisine eşlendiği yer.

İkinci basitleştirme, lambda hesabının yalnızca tek bir girdinin işlevlerini kullanmasıdır. İki giriş gerektiren sıradan bir işlev, örneğin işlev, tek bir girişi kabul eden eşdeğer bir işleve yeniden işlenebilir ve çıktı olarak, tek bir girişi kabul eden başka bir işlev döndürür . Örneğin,

yeniden işlenebilir

Currying olarak bilinen bu yöntem, birden çok argüman alan bir işlevi, her biri tek bir argüman içeren bir işlevler zincirine dönüştürür.

Fonksiyon uygulaması arasında bağımsız değişken (5, 2), işlev, verimler seferde

,

Körili versiyonun değerlendirilmesi bir adım daha gerektirirken

// tanımı iç ifadede ile kullanılmıştır . Bu β-indirgeme gibidir.
// tanımı ile kullanılmıştır . Yine, β-indirgemeye benzer.

aynı sonuca varmak için.

lambda hesabı

Lambda hesabı, belirli bir biçimsel sözdizimi ile tanımlanan bir lambda terimleri dili ve lambda terimlerinin işlenmesine izin veren bir dizi dönüşüm kuralından oluşur. Bu dönüşüm kuralları bir denklem teorisi veya işlemsel bir tanım olarak görülebilir .

Yukarıda açıklandığı gibi, lambda hesabındaki tüm fonksiyonlar isimsiz, isimsiz fonksiyonlardır. Yalnızca bir girdi değişkenini kabul ederler , birkaç değişkenli işlevleri uygulamak için kullanılan körleme ile.

Lambda terimleri

Lambda hesabının sözdizimi, bazı karakter dizilerinin geçerli C programları olduğu ve bazılarının olmadığı gibi, bazı ifadeleri geçerli lambda hesabı ifadeleri olarak ve bazılarını geçersiz olarak tanımlar . Geçerli bir lambda hesabı ifadesine "lambda terimi" denir.

Aşağıdaki üç kural, sözdizimsel olarak geçerli tüm lambda terimlerini oluşturmak için uygulanabilecek endüktif bir tanım verir :

  • bir değişken, , kendisi geçerli bir lambda terimidir
  • if bir lambda terimiyse ve bir değişkense, o zaman (bazen ASCII'de şu şekilde yazılır ) bir lambda terimidir ( soyutlama olarak adlandırılır );
  • Eğer ve lambda terimleri, daha sonra (bir adlandırılan bir lambda terimdir uygulama ).

Başka hiçbir şey lambda terimi değildir. Dolayısıyla bir lambda terimi, ancak ve ancak bu üç kuralın tekrar tekrar uygulanmasıyla elde edilebiliyorsa geçerlidir. Ancak bazı parantezler belirli kurallara göre atlanabilir. Örneğin, en dıştaki parantezler genellikle yazılmaz. Aşağıdaki Notasyona bakın.

Bir özet tek giriş alma yeteneğine sahip olan bir anonim işlev bir tanımdır ve ifade içine ikame edilerek . Böylece alan ve döndüren anonim bir işlevi tanımlar . Örneğin, bir işlev için bir soyutlama terimini kullanarak için . Bir soyutlama ile bir fonksiyonun tanımı, sadece fonksiyonu "ayarlar", fakat onu çağırmaz. Soyutlama bağlanan değişken vadede .

Bir uygulama , bir işlevin bir girdiye uygulanmasını temsil eder , yani, girdi üzerinde üretmek için işlev çağırma eylemini temsil eder .

Değişken bildiriminin lambda hesabında bir kavram yoktur. (ie ) gibi bir tanımda , lambda hesabı henüz tanımlanmamış bir değişken olarak ele alınır. Soyutlama sözdizimsel olarak geçerlidir ve girdisini henüz bilinmeyene ekleyen bir işlevi temsil eder .

Parantez içine alma kullanılabilir ve terimlerin belirsizliğini gidermek için gerekli olabilir. Örneğin, ve farklı terimleri ifade edin (tesadüfen aynı değere indirgenmelerine rağmen). Burada, ilk örnek, lambda terimi alt işleve x uygulamasının sonucu olan bir işlevi tanımlarken, ikinci örnek, en dıştaki işlevin alt işlevi döndüren x girişine uygulanmasıdır. Bu nedenle, her iki örnek de kimlik işlevini değerlendirir .

Fonksiyonlar üzerinde çalışan fonksiyonlar

Lambda hesabında, işlevler ' birinci sınıf değerler ' olarak alınır, bu nedenle işlevler girdi olarak kullanılabilir veya diğer işlevlerden çıktılar olarak döndürülebilir.

Örneğin, temsil kimlik fonksiyonu , ve uygulanan kimlik fonksiyonunu temsil eder . Ayrıca, giriş ne olursa olsun her zaman döndüren işlevi olan sabit işlevi temsil eder . Lambda hesabı olarak, fonksiyon uygulaması olarak kabul edilir sol birleştirici , böylece aracı .

Lambda terimlerinin "eşdeğer" lambda terimlerine "indirgenmesine" izin veren birkaç "eşdeğerlik" ve "indirgeme" kavramı vardır.

Alfa denkliği

Lambda terimleriyle tanımlanabilen temel bir eşdeğerlik biçimi, alfa denkliğidir. Bir soyutlamada belirli bir bağlı değişken seçiminin (genellikle) önemli olmadığı sezgisini yakalar. Örneğin ve alfa eşdeğeri lambda terimleridir ve her ikisi de aynı işlevi (özdeşlik işlevi) temsil eder. Terimler ve terimleri , bir soyutlamaya bağlı olmadıkları için alfa eşdeğeri değildir. Birçok sunumda, alfa eşdeğeri lambda terimlerini tanımlamak olağandır.

β-indirgenmesini tanımlayabilmek için aşağıdaki tanımlar gereklidir:

Serbest değişkenler

Serbest değişkenler bir terimi bir soyutlama ile bağlı olmayanlar değişkenlerdir. Bir ifadenin serbest değişkenleri kümesi endüktif olarak tanımlanır:

  • serbest değişkenleri sadece
  • Serbest değişkenler kümesi, serbest değişkenler kümesidir , ancak kaldırılmıştır.
  • Serbest değişkenler grubu serbest değişkenlerin kümesinin birliktir ve serbest değişkenlerin seti .

Örneğin, kimliği temsil eden lambda teriminin serbest değişkeni yoktur, ancak fonksiyonun tek bir serbest değişkeni vardır, .

Yakalamadan kaçınan ikameler

Diyelim ki , ve lambda terimleridir ve ve değişkenlerdir. Gösterimde bir ikamesini belirtir için de bir de yakalama kaçınarak şekilde. Bu, şu şekilde tanımlanır:

  • ;
  • eğer ;
  • ;
  • ;
  • if ve 'nin serbest değişkenlerinde değilse . Değişkenin için "taze" olduğu söylenir .

Örneğin , ve .

Tazelik koşulu ( bunun serbest değişkenlerde olmamasını gerektiren ), ikamenin fonksiyonların anlamını değiştirmemesini sağlamak için çok önemlidir. Örneğin, tazelik koşulunu yok sayan bir ikame yapılır: . Bu ikame, sabit fonksiyonu ikame yoluyla özdeşliğe dönüştürür .

Genel olarak, tazelik koşulunun karşılanamaması, uygun bir taze değişkenle alfa yeniden adlandırılarak giderilebilir. Örneğin, doğru ikame kavramımıza geri dönersek , soyutlamada elde etmek için yeni bir değişkenle yeniden adlandırılabilir ve işlevin anlamı ikame ile korunur.

β-indirgeme

β-indirgeme kuralı, formun bir uygulamasının terime indirgendiğini belirtir . Notasyon , β-indirgendiğini belirtmek için kullanılır . Örneğin, her için , . Bu , kimliğin gerçekten bu olduğunu gösterir . Benzer şekilde, bu gösteriyor ki sabit bir fonksiyonudur.

Lambda hesabı, Haskell veya Standard ML gibi işlevsel bir programlama dilinin idealleştirilmiş bir versiyonu olarak görülebilir . Bu görüş altında, β-indirgeme bir hesaplama adımına karşılık gelir. Bu adım, azaltılacak başka uygulama kalmayıncaya kadar ek β-indirgemeleri ile tekrar edilebilir. Burada sunulduğu gibi, türlenmemiş lambda hesabında bu indirgeme işlemi sona ermeyebilir. Örneğin, terimini düşünün . Burada . Yani terim tek bir β-indirgemede kendine indirgenir ve bu nedenle indirgeme süreci asla sona ermeyecektir.

Türlenmemiş lambda hesabının bir başka yönü, farklı veri türleri arasında ayrım yapmamasıdır. Örneğin, sadece sayılar üzerinde çalışan bir fonksiyon yazmak istenebilir. Ancak, türlenmemiş lambda hesabında, bir işlevin doğruluk değerlerine , dizelere veya sayı olmayan diğer nesnelere uygulanmasını engellemenin bir yolu yoktur .

Resmi tanımlama

Tanım

Lambda ifadeleri şunlardan oluşur:

  • değişkenler v 1 , v 2 , ...;
  • soyutlama sembolleri λ (lambda) ve . (nokta);
  • parantez ().

Lambda ifadeleri kümesi, Λ , tümevarımsal olarak tanımlanabilir :

  1. Eğer x bir değişkendir, daha sonra x ∈ Λ.
  2. Eğer x , değişken ve bir E ∈ Λ, daha sonra x . E ) ∈ Λ.
  3. Eğer M , N ∈ Λ, daha sonra ( MN ) ∈ Λ.

Kural 2 örnekleri soyutlamalar olarak bilinir ve kural 3 örnekleri uygulamalar olarak bilinir .

gösterim

Lambda ifadelerinin gösterimini düzenli tutmak için genellikle aşağıdaki kurallar uygulanır:

  • En dış parantez bırakılır: M , N yerine ( E N ).
  • Başvuruların ilişkisel bırakıldığı varsayılır: (( M N ) P ) yerine M N P yazılabilir .
  • Bir soyutlamanın gövdesi mümkün olduğu kadar sağa uzanır : λ x . MN , λ x .( MN ) anlamına gelir ve (λ x . M ) N değildir .
  • Bir soyutlama dizisi daraltılır : λ xyz . N , λ xyz olarak kısaltılır . N .

Serbest ve bağlı değişkenler

Soyutlama operatörünün, λ, değişkenini, soyutlamanın gövdesinde nerede olursa olsun bağladığı söylenir. Bir soyutlamanın kapsamına giren değişkenlere bağlı olduğu söylenir . Bir ifadede λ x . M , bölüm λ x genellikle denir bağlayıcı değişken dair bir ipucu olarak, x λ ekleyerek bağlı oluyor x için M . Diğer tüm değişkenler free olarak adlandırılır . Örneğin, λ y ifadesinde . xxy , y bağlı bir değişkendir ve x serbest bir değişkendir. Ayrıca bir değişken en yakın soyutlamasına bağlıdır. Aşağıdaki örnekte, ifadede x'in tek oluşumu ikinci lambda ile sınırlanmıştır: λ x . Yx . ZX ).

Bir lambda ifadesinin serbest değişkenleri seti , M , FV( M ) olarak gösterilir ve aşağıdaki gibi terimlerin yapısında özyineleme ile tanımlanır:

  1. FV( x ) = { x }, burada x bir değişkendir.
  2. FV (λ x . E ) = FV ( M ) \ { x }.
  3. FV( MN ) = FV( M ) ∪ FV( N ).

Serbest değişken içermeyen bir ifadenin kapalı olduğu söylenir . Kapalı lambda ifadeleri olarak da bilinir , bağdaştırıcılarla ve terimlerin eşdeğerdir kombinatoriyel mantık .

Kesinti

Lambda ifadelerinin anlamı, ifadelerin nasıl azaltılabileceği ile tanımlanır.

Üç tür azalma vardır:

  • α-dönüşüm : bağlı değişkenlerin değiştirilmesi;
  • β-indirgeme : fonksiyonların argümanlarına uygulanması;
  • η-indirgeme : bir genişleme kavramını yakalar.

Ayrıca ortaya çıkan denkliklerden de bahsediyoruz: eğer aynı ifadeye α-dönüştürülebiliyorlarsa, iki ifade α-eşdeğerdir . β-eşdeğerliği ve η-eşdeğerliği benzer şekilde tanımlanır.

Terimi REDEX kısaltması, indirgenebilir ifade indirgeme kuralları tarafından azaltılabilir alt terimleri belirtmektedir. Örneğin, (λ için x . E ) , N ikamesini ifade bir β-REDEX olan N için x de M . Bir REDEX azaltır için sentezlenmesi, adı Redüksiyon ; (λ arasında azltm X . E ) N olan E [ X  : = N ].

Eğer x serbest değildir M , λ x . Mx bir azltm ile, aynı zamanda, bir η-REDEX olan M .

α-dönüşüm

Bazen α-yeniden adlandırma olarak bilinen α-dönüşüm, bağlı değişken adlarının değiştirilmesine izin verir. Örneğin, λ x'in α-dönüşümü . x λ y verebilir . y . Yalnızca α-dönüşümüne göre farklılık gösteren terimlere α-eşdeğeri denir . Sıklıkla, lambda hesabının kullanımlarında, α eşdeğeri terimlerin eşdeğer olduğu kabul edilir.

α-dönüşümünün kesin kuralları tamamen önemsiz değildir. İlk olarak, bir soyutlamayı α-dönüştürürken, yeniden adlandırılan tek değişken oluşumları aynı soyutlamaya bağlı olanlardır. Örneğin, λ xx'in bir α-dönüşümüdür . x , λ yx ile sonuçlanabilir . x , ancak olabilir değil λ neden yx . y . İkincisi, orijinalinden farklı bir anlama sahiptir. Bu, değişken gölgeleme programlama kavramına benzer .

İkincisi, bir değişkenin farklı bir soyutlama tarafından yakalanmasıyla sonuçlanacaksa α-dönüşüm mümkün değildir. Mesela yerine, eğer x ile y λ içinde Xy . x , λ yy elde ederiz . y , ki bu hiç de aynı değil.

Statik kapsamı olan programlama dillerinde, α-dönüşüm, hiçbir değişken adının içeren bir kapsamda bir adı maskelememesini sağlayarak ad çözümlemesini kolaylaştırmak için kullanılabilir ( ad çözümlemesini önemsiz kılmak için α-yeniden adlandırma bölümüne bakın ).

Gelen De Bruijn ve dizin gösterimde, herhangi iki α eşdeğer terimler sözdizimsel aynıdır.

ikame

Değişiklik, yazılı M [ V  : = N ], her değiştirilmesi işlemidir serbest değişken tekrarlarını V ekspresyonunun M ifadesi ile N . Lambda hesabının terimlerinde ikame, aşağıdaki gibi terimlerin yapısında özyineleme ile tanımlanır (not: x ve y yalnızca değişkenlerdir, M ve N ise herhangi bir lambda ifadesidir):

x [ x  := N ] = H
y [ x  := N ] = y , eğer xy
( M 1 M 2 )[ x  := N ] = ( M 1 [ x  := N ]) ( M 2 [ x  := N ])
x . M )[ x  := N ] = λ x . m
y . M )[ x  := N ] = λ y .( M [ x  := N ]), eğer xy ve y ∉ FV( N )

Bir soyutlamayı ikame etmek için bazen ifadeyi α-dönüştürmek gerekir. Örneğin, (λ için doğru değildir X . Y ) [ y  : = X ] λ sonuçlandığı X . x , çünkü ikame edilen x'in serbest olması gerekiyordu ama sonunda bağlı kaldı. Bu durumda doğru ikame λ z'dir . x , α-eşdeğerliğine kadar. İkame, α-eşdeğerliğine kadar benzersiz olarak tanımlanır.

β-indirgeme

β-indirgeme, fonksiyon uygulaması fikrini yakalar. β-indirgeme sübstitüsyon açısından tanımlanmaktadır: (λ ait β-indirgeme V . E ) N olan E [ V  : = N ].

Örneğin, 2, 7, × kodlaması olduğunu varsayarsak, aşağıdaki β-indirgemesine sahibiz: (λ n . n × 2) 7 → 7 × 2.

β-azaltma kavramı aynı olacak şekilde görülebilir yerel indirgenebilirlik içinde doğal kesinti yoluyla, Curry-Howard eşbiçimlilikle .

η-azaltma

η-indirgeme , bu bağlamda iki işlevin ancak ve ancak tüm argümanlar için aynı sonucu vermeleri durumunda aynı olduğu , genişleme fikrini ifade eder . η-indirgemesi λ x arasında dönüştürür . f x ve f , x'in f içinde serbest görünmediği durumlarda .

η azaltma kavramı aynı olacak şekilde görülebilir yerel bütünlük içinde doğal kesinti yoluyla, Curry-Howard eşbiçimlilikle .

Normal formlar ve izdiham

Türlenmemiş lambda hesabı için, bir yeniden yazma kuralı olarak β-indirgeme , ne güçlü bir şekilde normalleştirme ne de zayıf bir şekilde normalleştirmedir .

Bununla birlikte, α-dönüşümüne kadar çalışırken β-indirgemenin birleştiği gösterilebilir (yani, birini diğerine α-dönüştürmek mümkünse, iki normal formun eşit olduğunu düşünüyoruz).

Bu nedenle, hem güçlü normalleştirici terimler hem de zayıf normalleştirici terimler benzersiz bir normal forma sahiptir. Güçlü normalleştirme terimleri için, herhangi bir indirgeme stratejisinin normal formu vermesi garanti edilirken, zayıf normalleştirme terimleri için bazı indirgeme stratejileri onu bulamayabilir.

Veri türlerini kodlama

Temel lambda hesabı , aşağıdaki alt bölümlerde gösterildiği gibi, boolean, aritmetik , veri yapıları ve özyinelemeyi modellemek için kullanılabilir .

Lambda hesabında aritmetik

Lambda hesabında doğal sayıları tanımlamanın birkaç olası yolu vardır , ancak en yaygın olanı aşağıdaki gibi tanımlanabilen Kilise rakamlarıdır :

0 := λ fx . x
1 := λ fx . f x
2 := λ fx . f ( f x )
3 := λ fx . f ( f ( f x ))

ve bunun gibi. Veya yukarıda Notation'da sunulan alternatif sözdizimini kullanarak :

0 := λ fx . x
1 := λ fx . f x
2 := λ fx . f ( f x )
3 := λ fx . f ( f ( f x ))

Kilise rakamı daha yüksek dereceli bir işlevdir ; tek bağımsız değişkenli bir işlev f alır ve başka bir tek bağımsız değişkenli işlev döndürür. Church numarası n bir işlev alan bir fonksiyonudur f bağımsız değişken olarak ve döner n ve inci bileşimi f yani fonksiyonu, f kendisi ile oluşan , n kere. Bu gösterilir f ( n ) ve aslında , n ve inci güç f (operatör olarak kabul edilir); f (0) , kimlik fonksiyonu olarak tanımlanır. Bu tür tekrarlanan bileşimler (tek bir işlev f ) üs yasalarına uyar , bu nedenle bu sayılar aritmetik için kullanılabilir. (Church'in orijinal lambda hesabında, bir lambda ifadesinin biçimsel parametresinin, fonksiyon gövdesinde en az bir kez gerçekleşmesi gerekiyordu, bu da yukarıdaki 0 tanımını imkansız hale getirdi.)

Programları analiz ederken genellikle yararlı olan Kilise rakamı n hakkında düşünmenin bir yolu, bir talimat olarak ' n kez tekrarla'dır . Örneğin, aşağıda tanımlanan PAIR ve NIL işlevlerini kullanarak, boş bir listeden başlayarak ' başka bir x öğesini başa ekle'yi n kez tekrarlayarak tümü x'e eşit n öğeden (bağlantılı) bir liste oluşturan bir işlev tanımlanabilir . lambda terimi

λ nx . n (ÇİFT x ) NIL

Neyin tekrarlandığını değiştirerek ve tekrarlanan işlevin hangi argümana uygulanacağını değiştirerek, çok sayıda farklı etki elde edilebilir.

Bir kilise rakamı alan bir ardıl fonksiyonu tanımlayabilir n ve döner n + 1 bir başka uygulama eklenerek f '(mf) X' araçlar işlevi 'f' 'x' ile 'm' kez uygulanır:

SUCC := λ nfx . f ( n f x )

Çünkü m arasında inci bileşim f ile oluşan N ve inci bileşimin f verir m + n bir inci bileşimi f , aşağıdaki şekilde bir ek tanımlanabilir:

ARTI := λ mnfx . m f ( n f x )

ARTI , iki doğal sayıyı argüman olarak alan ve bir doğal sayı döndüren bir fonksiyon olarak düşünülebilir; bu doğrulanabilir

ARTI 2 3

ve

5

β-eşdeğer lambda ifadeleridir. İlave yana m bir sayı n 1 eklenerek gerçekleştirilebilir m kez alternatif tanımı şöyledir:

ARTI := λ mn . m SUCC n 

Benzer şekilde, çarpma şu şekilde tanımlanabilir:

ÇOKLU := λ mnf . m ( N f )

Alternatif olarak

ÇOKLU := λ mn . m (ARTI n ) 0

çünkü m ve n'yi çarpmak , n fonksiyonunu m kez tekrarlamak ve sonra onu sıfıra uygulamakla aynıdır . Üs, Kilise rakamlarında oldukça basit bir işlemeye sahiptir, yani

POW := λ be . e b

Pozitif bir n tamsayı ve PRED 0 = 0 için PRED n = n − 1 ile tanımlanan öncül fonksiyon çok daha zordur. Formül

PRED := λ nfx . Ngh . h ( g f )) (λ u . X ) (λ u . u )

indüktif olarak göstererek doğrulanabilir durumunda , T O anlamına gelir gh . h ( g f )) , daha sonra , T ( n )u . x ) = (λ h . h ( f ( n -1) ( X ))) için n > 0 . PRED'in diğer iki tanımı aşağıda verilmiştir, biri koşullu ve diğeri çiftleri kullanan . Öncül işleviyle, çıkarma basittir. tanımlama

ALT := λ mn . n PRED m ,

ALT m , n verim m - n, zaman m > n ve 0 , aksi.

Mantık ve yüklemler

Geleneksel olarak, DOĞRU ve YANLIŞ boole değerleri için aşağıdaki iki tanım (Kilise booleanları olarak bilinir) kullanılır :

DOĞRU := λ xy . x
YANLIŞ := λ xy . y
( YANLIŞ'ın yukarıda tanımlanan Kilise rakamı sıfıra eşdeğer olduğuna dikkat edin)

Ardından, bu iki lambda terimiyle bazı mantık operatörleri tanımlayabiliriz (bunlar sadece olası formülasyonlardır; diğer ifadeler de eşit derecede doğrudur):

VE := λ pq . p q p
VEYA := λ pq . p p q
DEĞİL := λ p . p YANLIŞ DOĞRU
İFTHENELSE := λ pab . p bir b

Artık bazı mantık fonksiyonlarını hesaplayabiliyoruz, örneğin:

VE DOĞRU YANLIŞ
≡ (λ sq . S q p ) DOĞRU YANLIŞ → p yanlış doğru doğru
≡ (λ xy . x ) YANLIŞ DOĞRU → β YANLIŞ

ve biz görüyoruz VE DOĞRU YANLIŞ eşdeğerdir YANLıŞ .

Bir yüklem , bir boole değeri döndüren bir işlevdir. En temel yüklem olan sıfır döndürür, DOĞRU onun argümanı Kilisesi rakamı ise 0 ve YANLIŞ onun argümanı başka kilise rakamı ise:

ISZERO := λ n . nx .YANLIŞ) DOĞRU

Aşağıdaki yüklem, ilk argümanın ikinciden küçük veya ona eşit olup olmadığını test eder:

LEQ := λ mn .ISZERO (ALT m n ) ,

ve m = n olduğundan , LEQ m n ve LEQ n m ise , sayısal eşitlik için bir yüklem oluşturmak kolaydır.

Yüklemlerin mevcudiyeti ve yukarıdaki DOĞRU ve YANLIŞ tanımı, lambda hesabında "if-then-else" ifadelerini yazmayı kolaylaştırır. Örneğin, öncül işlev şu şekilde tanımlanabilir:

ÖNCEKİ := λ n . ngk .ISZERO ( g 1) k (ARTI ( g k ) 1)) (λ v .0) 0

bu, ngk .ISZERO ( g 1) k (PLUS ( g k ) 1)) (λ v .0) 'ın n > 0 için toplama n − 1 işlevi olduğu tümevarımsal olarak gösterilerek doğrulanabilir .

çiftler

Bir çift (2-tuple), çiftler için Church kodlaması kullanılarak DOĞRU ve YANLIŞ terimleriyle tanımlanabilir . Örneğin, PAIR ( x , y ) çiftini kapsüller , FIRST çiftin ilk öğesini ve SECOND ikinci öğesini döndürür.

ÇİFT := λ xyf . f x y
BİRİNCİ := λ p . p DOĞRU
İKİNCİ := λ p . p YANLIŞ
NIL := λ x .DOĞRU
NULL := λ p . pxy .YANLIŞ)

Bir bağlanmış liste boş liste ya NIL, ya da tanımlanabilir ÇİFT bir elemanın ve daha küçük bir listesi. NULL yüklemi , NIL değeri için testler yapar . (Alternatif olarak, NIL := FALSE ile , lhtz .deal_with_head_ h _and_tail_ t ) ( deal_with_nil ) yapısı , açık bir NULL testi ihtiyacını ortadan kaldırır .

Çiftlerin kullanımına bir örnek olarak, ( m , n ) ile ( n , n + 1) arasında eşlenen kaydırma ve artırma işlevi şu şekilde tanımlanabilir:

Φ := λ x .ÇİFT (İKİNCİ x ) (SUCC (İKİNCİ x ))

bu, önceki işlevin belki de en şeffaf versiyonunu vermemize izin verir:

PRED := λ n .İLK ( n Φ (ÇİFT 0 0)).

Ek programlama teknikleri

Lambda hesabı için hatırı sayılır sayıda programlama deyimi vardır . Bunların çoğu, başlangıçta , lambda matematiğini, düşük seviyeli bir programlama dili olarak etkin bir şekilde kullanarak, programlama dili semantiği için bir temel olarak lambda matematiğini kullanma bağlamında geliştirilmiştir . Birkaç programlama dili lambda hesabını (veya çok benzer bir şeyi) bir parça olarak içerdiğinden, bu teknikler pratik programlamada da kullanılır, ancak daha sonra belirsiz veya yabancı olarak algılanabilir.

Adlandırılmış sabitler

Lambda hesabında, bir kitaplık , lambda terimleri olarak yalnızca belirli sabitler olan önceden tanımlanmış işlevlerin bir koleksiyonu biçimini alacaktır. Saf lambda hesabı, tüm atomik lambda terimleri değişkenler olduğundan, adlandırılmış sabitler kavramına sahip değildir, ancak bir değişkeni sabitin adı olarak bir kenara bırakarak, bu değişkeni ana gövdeye bağlamak için soyutlama kullanarak, adlandırılmış sabitlere sahip taklit edilebilir. ve bu soyutlamayı amaçlanan tanıma uygulayın. Bu nedenle , N'de (bir başka lambda terimi, "ana program") M'yi (bazı açık lambda terimlerini) ifade etmek için f kullanmak için şunu söyleyebiliriz:

f . K ) M

Yazarlar , yukarıdakilerin daha sezgisel bir sırada yazılmasına izin vermek için genellikle let gibi sözdizimsel şeker kullanırlar.

izin f = K içinde N

Bu tür tanımları zincirleyerek, sıfır veya daha fazla fonksiyon tanımı olarak bir lambda hesabı "programı" yazılabilir, ardından programın ana gövdesini oluşturan bu fonksiyonları kullanan bir lambda terimi yazılabilir.

Bunun önemli bir kısıtlama let adı olmasıdır f tanımlanmamış M , çünkü E bağlama soyutlama kapsamı dışında f ; bu, özyinelemeli bir işlev tanımının let ile M olarak kullanılamayacağı anlamına gelir . Özyinelemeli işlev tanımlarının bu naif tarzda yazılmasına izin veren daha gelişmiş letrec sözdizimsel şeker yapısı, bunun yerine ek olarak sabit nokta birleştiricileri kullanır.

Özyineleme ve sabit noktalar

Özyineleme , işlevin kendisini kullanan bir işlevin tanımıdır. Lambda hesabı bunu diğer bazı gösterimler gibi doğrudan ifade edemez: lambda hesabında tüm fonksiyonlar anonimdir, bu nedenle aynı değeri tanımlayan lambda terimi içinde henüz tanımlanmamış bir değere atıfta bulunamayız. Bununla birlikte, yine de bir lambda ifadesinin kendisini argüman değeri olarak alacak şekilde düzenlenmesiyle özyineleme elde edilebilir, örneğin  x . x x ) E .

F( n ) tarafından özyinelemeli olarak tanımlanan faktöriyel işlevi göz önünde bulundurun :

F( n ) = 1, eğer n = 0 ise; başka n × F( n − 1) .

Bu işlevi temsil edecek olan lambda ifadesinde, bir parametrenin (tipik olarak birincisinin) lambda ifadesinin kendisini değeri olarak aldığı varsayılacaktır, böylece onu çağırmak – onu bir argümana uygulamak – özyineleme anlamına gelecektir. Bu nedenle özyinelemeyi başarmak için, kendine referans olarak amaçlanan argüman ( burada r olarak adlandırılır ) her zaman bir çağrı noktasında işlev gövdesi içinde kendisine iletilmelidir:

G := λ r . λ n .(1, eğer n = 0 ise; yoksa n × ( r r ( n −1)))
ile  r r x = F x = G r x  beklemeye, bu yüzden  , {{{1}}}  ve
F := GG = (λ x . x x ) G

Kendi kendine uygulama, burada çoğaltmayı başarır, işlevin lambda ifadesini bir sonraki çağrıya bir argüman değeri olarak iletir ve orada başvurulmasını ve çağrılmasını sağlar.

Bu sorunu çözer, ancak her özyinelemeli çağrının kendi kendine uygulama olarak yeniden yazılmasını gerektirir. Yeniden yazmaya gerek kalmadan genel bir çözüme sahip olmak istiyoruz:

G := λ r . λ n .(1, eğer n = 0 ise; yoksa n × ( r ( n −1)))
ile  R X = F x = G r x  beklemeye, böylece  R = G r =: Düzeltme G  ve
F := DÜZELT G  burada  FIX g  := ( r burada r = g r ) = g (FIX g )
öyle ki  FIX G = G (FIX G) = (λ n .(1, eğer n = 0 ise; yoksa n × ((FIX G) ( n -1))))

İlk argümanı özyinelemeli çağrıyı temsil eden bir lambda terimi verildiğinde (örneğin burada G ), sabit nokta birleştirici FIX özyinelemeli işlevi (burada, F ) temsil eden kendi kendini kopyalayan bir lambda ifadesi döndürür . İşlevin herhangi bir noktada açıkça kendisine iletilmesi gerekmez, çünkü kendini çoğaltma, oluşturulduğunda, her çağrıldığında yapılacak şekilde önceden düzenlenir. Böylece orijinal lambda ifadesi (FIX G) , çağrı noktasında kendi içinde yeniden yaratılarak öz referans elde edilir .

Aslında, bu FIX operatörü için birçok olası tanım vardır, bunlardan en basiti:

Y  : = λ gr . (Λ x . G ( x x )) (λ x . G ( x x ))

Lambda hesabı olarak, Y, g   bir sabit nokta g Genişlediği olarak:

y g
h . (λ x . * H ( x x )) (λ x . * H ( x x ))) g
x . g ( x x )) (λ x . g ( x x ))
g ((λ x . g ( x x )) (λ x . g ( x x )))
g ( E g )

Şimdi, faktöriyel fonksiyona özyinelemeli çağrımızı gerçekleştirmek için, basitçe ( Y G) n'yi çağırırız , burada n , faktöriyelini hesapladığımız sayıdır. Örneğin n = 4 verildiğinde , bu şunu verir:

( YG ) 4
G ( YG ) 4
rn .(1, eğer n = 0 ise; yoksa n × ( r ( n −1)))) ( Y G) 4
n .(1, eğer n = 0 ise; yoksa n × (( Y G) ( n −1)))) 4
1, eğer 4 = 0 ise; başka 4 × (( Y G) (4−1))
4 × (G ( Y G) (4−1))
4 × ((λ n .(1, eğer n = 0 ise; yoksa n × (( Y G) ( n -1)))) (4−1))
4 × (1, eğer 3 = 0 ise; aksi takdirde 3 × (( Y G) (3−1)))
4 × (3 × (G ( Y G) (3−1)))
4 × (3 × ((λ n .(1, eğer n = 0 ise; yoksa n × (( Y G) ( n −1)))) (3−1)))
4 × (3 × (1, eğer 2 = 0 ise; aksi takdirde 2 × (( Y G) (2−1))))
4 × (3 × (2 × (G ( Y G) (2−1))))
4 × (3 × (2 × ((λ n .(1, eğer n = 0 ise; yoksa n × (( Y G) ( n -1)))) (2−1))))
4 × (3 × (2 × (1, eğer 1 = 0 ise; aksi takdirde 1 × (( Y G) (1−1)))))
4 × (3 × (2 × (1 × (G ( Y G) (1−1)))))
4 × (3 × (2 × (1 × ((λ n .(1, eğer n = 0 ise; aksi halde) n × (( Y G) ( n -1))))) (1−1))))
4 × (3 × (2 × (1 × (1, eğer 0 = 0 ise; aksi takdirde 0 × (( Y G) (0−1))))))
4 × (3 × (2 × (1 × (1))))
24

Özyinelemeli olarak tanımlanan her işlev, özyinelemeli çağrıyı fazladan bir argümanla kapatan uygun şekilde tanımlanmış bir işlevin sabit bir noktası olarak görülebilir ve bu nedenle, Y kullanılarak , özyinelemeli olarak tanımlanan her işlev bir lambda ifadesi olarak ifade edilebilir. Özellikle, artık doğal sayıların çıkarma, çarpma ve karşılaştırma yüklemini özyinelemeli olarak net bir şekilde tanımlayabiliriz.

Standart şartlar

Bazı terimlerin genel olarak kabul edilen adları vardır:

ben  := λ x . x
K  := λ xy . x
S  := λ xyz . x z ( y z )
B  := λ xyz . X ( Y Z )
C  := λ xyz . x z y
W  := λ xy . x y y
U  := λ x . x x
ω  := λ x . x x
Ω  := ω ω
Y  : = λ gr . (Λ x . G ( x x )) (λ x . G ( x x ))

Bunların birçoğu , lambda terimlerini birleştirici hesap terimlerine dönüştüren soyutlamanın ortadan kaldırılmasında doğrudan uygulamalara sahiptir .

soyutlama eliminasyonu

Eğer K bir soyutlama lambda süreli fakat muhtemelen adı içeren sabitleri (olup combinators ), daha sonra bir lambda dönem vardır T ( x , N eşdeğerdir) λ x . N, ancak soyutlamadan yoksundur (atomik olmadığı düşünülürse, adlandırılmış sabitlerin bir parçası olarak hariç). Bu aynı zamanda, anonymising değişkenler olarak izlenebilir T ( x , N tüm oluşumları kaldırır) x gelen N yine bağımsız değişken değerleri pozisyonlara ikame edilmesine izin verirken, N bir içermektedir x . Dönüşüm fonksiyonu T şu şekilde tanımlanabilir:

T ( x , x ) := Ben
T ( x , N ) := K N eğer x , N'de serbest değilse .
T ( x , M N ) := S T ( x , M ) T ( x , N )

Her iki durumda da, T ( x , N ) P biçimindeki bir terim, I , K veya S ilk birleştiricisinin P argümanını almasını sağlayarak indirgenebilir, tıpkı x . N ) P'nin β-indirgenmesi gibi . Bu argümanı iade ediyorum . K gibi, uzak argüman atar x . N ) eğer yapacağını x hiçbir serbest oluşumunu vardır N . S , argümanı uygulamanın her iki alt terimine de iletir ve ardından birincinin sonucunu ikincinin sonucuna uygular.

B ve C birleştiricileri S'ye benzer , ancak argümanı bir uygulamanın yalnızca bir alt terimine iletir ( B "argüman" alt terimine ve C "fonksiyon" alt terimine), böylece herhangi bir oluşum yoksa sonraki K'yi kaydeder ve x bir subterm içinde. B ve C ile karşılaştırıldığında , S birleştiricisi aslında iki işlevi birleştirir: argümanları yeniden düzenlemek ve bir argümanı iki yerde kullanılabilecek şekilde çoğaltmak. Beyaz combinator, sonuçta sadece ikinci yapar B, C, K, G sistem için alternatif bir şekilde SKI combinator hesabı .

Yazılan lambda hesabı

Bir yazılı Lambda taşı isimli bir yazılı biçimselcilik lambda sembolü (kullandığı ) anonim işlev soyutlama göstermek için kullanılır. Bu bağlamda, türler genellikle lambda terimlerine atanan sözdizimsel nitelikteki nesnelerdir; bir türün tam doğası, dikkate alınan hesaplamaya bağlıdır (bkz . Yazılı lambda hesabı çeşitleri ). Belirli bir bakış açısına göre, tiplenmiş lambda hesabı , tiplenmemiş lambda hesabının iyileştirmeleri olarak görülebilir, ancak başka bir bakış açısından, daha temel teori ve tiplenmemiş lambda hesabı , sadece bir tip ile özel bir durum olarak da kabul edilebilir.

Yazılan lambda hesapları, temel programlama dilleridir ve ML ve Haskell gibi yazılan işlevsel programlama dillerinin ve daha dolaylı olarak, yazılan zorunlu programlama dillerinin temelidir . Yazılan lambda hesapları , programlama dilleri için tip sistemlerinin tasarımında önemli bir rol oynar ; burada yazılabilirlik genellikle programın istenen özelliklerini yakalar, örneğin program bir bellek erişim ihlaline neden olmaz.

Yazılan lambda hesapları , Curry-Howard izomorfizmi aracılığıyla matematiksel mantık ve ispat teorisi ile yakından ilişkilidir ve kategori sınıflarının iç dili olarak kabul edilebilirler , örneğin, basitçe yazılan lambda hesabı, Kartezyen kapalı kategorilerin (CCC'ler) dilidir .

Azaltma stratejileri

Bir terimin normalize edilip edilmediği ve normalize ediliyorsa normalleştirilmesi için ne kadar çalışma yapılması gerektiği büyük ölçüde kullanılan azaltma stratejisine bağlıdır. Yaygın lambda hesabı azaltma stratejileri şunları içerir:

Normal düzen
En soldaki, en dıştaki redex her zaman önce azaltılır. Yani, mümkün olduğunda argümanlar, argümanlar indirgenmeden önce bir soyutlamanın gövdesinde değiştirilir.
uygulanabilir sipariş
En soldaki, en içteki redex her zaman önce azaltılır. Sezgisel olarak bu, bir işlevin argümanlarının her zaman işlevin kendisinden önce indirgendiği anlamına gelir. Uygulanabilir düzen, bu mümkün olmadığında bile her zaman işlevleri normal formlara uygulamaya çalışır.
Tam β-indirgemeleri
Herhangi bir redex herhangi bir zamanda azaltılabilir. Bu, esasen herhangi bir özel azaltma stratejisinin olmaması anlamına gelir - indirgenebilirlikle ilgili olarak, "tüm bahisler kapalıdır".

Zayıf azaltma stratejileri lambda soyutlamaları altında azalmaz:

Değere göre çağrı
Bir redex, yalnızca sağ tarafı bir değere (değişken veya soyutlama) indirgendiğinde indirgenir. Yalnızca en dıştaki redex'ler azaltılır.
Ada göre ara
Normal düzende olduğu gibi, ancak soyutlamalar içinde herhangi bir indirgeme yapılmaz. Örneğin, λ X . (Λ x . X ) x Bu REDEX içerir, ancak, bu strateji göre normal formdadır x . X ) x .

Paylaşımlı stratejiler paralel olarak "aynı" olan hesaplamaları azaltır:

Optimum azalma
Normal düzen olarak, ancak aynı etikete sahip hesaplamalar aynı anda azaltılır.
ihtiyaca göre ara
Ada göre çağırma (dolayısıyla zayıf), ancak terimleri çoğaltan işlev uygulamaları bunun yerine argümanı adlandırır, bu daha sonra yalnızca "gerektiğinde" azaltılır.

hesaplanabilirlik

Herhangi iki lambda ifadesini girdi olarak alan ve bir ifadenin diğerine indirgenip indirgenmemesine bağlı olarak DOĞRU veya YANLIŞ çıktı veren bir algoritma yoktur . Daha doğrusu, hiçbir hesaplanabilir fonksiyon olabilir karar soru. Bu, tarihsel olarak, karar verilemezliğinin kanıtlanabileceği ilk sorundu. Böyle bir ispat için her zamanki gibi, hesaplanabilir , Turing'in tam olduğu herhangi bir hesaplama modeli tarafından hesaplanabilen anlamına gelir . Aslında Hesaplanabilirlik olarak kendisini lambda hesabı ile tanımlanabilir: bir fonksiyonu F : NK lambda ifade vardır, ancak ve ancak doğal sayılar hesaplanabilir bir fonksiyonudur f bu şekilde her çifti için , x , y olarak N , F ( x ) = y ancak ve ancak ön x  = β y , x ve y Church rakamları 'e karşılık gelen , x ve y , sırasıyla, ve = β β-azalma ile denklik gelir. Hesaplanabilirliği ve bunların eşdeğerliğini tanımlamaya yönelik diğer yaklaşımlar için Church-Turing tezine bakın .  

Church'ün hesaplanamazlık kanıtı, ilk önce sorunu, verilen bir lambda ifadesinin normal bir forma sahip olup olmadığını belirlemeye indirger . Sonra bu yüklemin hesaplanabilir olduğunu ve dolayısıyla lambda hesabında ifade edilebileceğini varsayar. Kleene'nin daha önceki çalışmalarına dayanarak ve lambda ifadeleri için bir Gödel numaralandırması oluşturarak , Gödel'in ilk eksiklik teoreminin kanıtını yakından takip eden bir lambda ifadesi e oluşturur . Eğer e kendi Gödel sayısı, bir çelişki sonuçlarına uygulanır.

karmaşıklık

Lambda hesabı için hesaplama karmaşıklığı kavramı biraz aldatıcıdır, çünkü bir β-indirgemenin maliyeti, nasıl uygulandığına bağlı olarak değişebilir. Kesin olarak bir şekilde bağlı değişken gerçekleşme tüm yerini bulmak zorundadır V ifadesi içinde E bir zaman maliyetini ima veya bir boşluk maliyeti ima, bir şekilde serbest değişkenlerin yerleri izlemek gerekir. Yerleri için bir naif ara V içinde E bir O ( n ) uzunluğunda , n ve E . Yönetmen dizileri , ikinci dereceden bir alan kullanımı için bu zaman maliyetini değiştiren erken bir yaklaşımdı. Daha genel olarak bu, açık ikame kullanan sistemlerin incelenmesine yol açmıştır .

2014'te, bir terimi azaltmak için normal sıra indirgeme ile atılan β-indirgeme adımlarının sayısının makul bir zaman maliyeti modeli olduğu, yani indirgemenin adım sayısıyla orantılı olarak zaman polinomunda bir Turing makinesinde simüle edilebileceği gösterilmiştir. . Bu, boyut patlaması , her β-azaltma için boyut olarak katlanarak büyüyen lambda terimlerinin varlığı nedeniyle uzun süredir devam eden bir açık problemdi . Sonuç, kompakt bir paylaşılan temsille çalışarak bu sorunu çözer. Sonuç, bir lambda terimini değerlendirmek için gereken alan miktarının, indirgeme sırasında terimin boyutuyla orantılı olmadığını açıkça ortaya koymaktadır. Şu anda, uzay karmaşıklığının ne kadar iyi bir ölçüsü olacağı bilinmiyor.

Mantıksız bir model mutlaka verimsiz anlamına gelmez. Optimal indirgeme , aynı etikete sahip tüm hesaplamaları tek adımda azaltır, yinelenen çalışmayı önler, ancak belirli bir terimi normal forma indirgemek için paralel β-indirgeme adımlarının sayısı, terimin boyutunda yaklaşık olarak doğrusaldır. Bu, makul bir maliyet ölçüsü olamayacak kadar küçüktür, çünkü herhangi bir Turing makinesi, lambda hesabında, Turing makinesinin boyutuyla doğrusal orantılı boyutta kodlanabilir. Lambda terimlerini azaltmanın gerçek maliyeti, kendi başına β-indirgemesinden değil, β-indirgemesi sırasında redekslerin çoğaltılmasının ele alınmasından kaynaklanmaktadır. Normal forma en soldaki en dıştaki adımların sayısı gibi makul bir maliyet modeline göre ölçüldüğünde optimal indirgeme uygulamalarının makul olup olmadığı bilinmemektedir, ancak lambda hesabının parçaları için optimal indirgeme algoritmasının verimli olduğu gösterilmiştir. ve en soldaki en dıştaki ile karşılaştırıldığında en fazla ikinci dereceden bir ek yüke sahiptir. Ayrıca optimum azalma BOHM prototip uygulama hem daha iyi performans Caml Işık ve Haskell saf lamda şartlarda.

Lambda hesabı ve programlama dilleri

Tarafından işaret edildiği gibi Peter Landin , sıralı 'ALGOL 60 ve Church Lambda-gösterimi arasında bir ilişki' 'in 1965 kağıt prosedürel programlama usul soyutlama ve prosedürü (alt program) temel mekanizmalar sağlar lambda hesabı açısından anlaşılabilir diller başvuru.

Anonim işlevler

Örneğin, Lisp'te "kare" işlevi aşağıdaki gibi bir lambda ifadesi olarak ifade edilebilir:

(lambda (x) (* x x))

Yukarıdaki örnek, birinci sınıf bir işlev olarak değerlendirilen bir ifadedir. Sembol lambda, parametre adlarının bir listesi verilen anonim bir işlev oluşturur (x)- bu durumda yalnızca tek bir argüman ve işlevin gövdesi olarak değerlendirilen bir ifade, (* x x). Anonim işlevlere bazen lambda ifadeleri denir.

Örneğin, Pascal ve diğer birçok zorunlu dil, alt programların işlev işaretçileri mekanizması aracılığıyla diğer alt programlara argüman olarak geçirilmesini uzun süredir desteklemektedir . Bununla birlikte, işlev işaretçileri, işlevlerin birinci sınıf veri türleri olması için yeterli bir koşul değildir , çünkü bir işlev, yalnızca ve yalnızca çalışma zamanında işlevin yeni örnekleri oluşturulabiliyorsa birinci sınıf bir veri türüdür. Ve bu çalışma zamanı işlevleri oluşturma, Smalltalk , JavaScript ve Wolfram Language ' de ve daha yakın zamanda Scala , Eiffel ("agents"), C# ("delegates") ve C++11'de desteklenir .

Paralellik ve eşzamanlılık

Church-Rosser değerlendirme (β-azalma) içinde gerçekleştirilebilir ki Lambda taşı aracının özelliği , herhangi bir sırayla , hatta paralel olarak,. Bu, çeşitli deterministik olmayan değerlendirme stratejilerinin alakalı olduğu anlamına gelir . Bununla birlikte, lambda hesabı, paralellik için herhangi bir açık yapı sunmaz . Lambda hesabına Futures gibi yapılar eklenebilir . İletişim ve eşzamanlılığı tanımlamak için başka süreç hesapları geliştirilmiştir.

anlambilim

Lambda hesabı terimlerinin diğer lambda hesabı terimlerinde ve hatta kendilerinde fonksiyon gibi davranması, lambda hesabının semantiği hakkında sorulara yol açtı. Lambda hesabı terimlerine mantıklı bir anlam verilebilir mi? Doğal anlambilim, kendi üzerindeki fonksiyonların DD fonksiyon uzayına eşbiçimli bir D kümesi bulmaktı . Bununla birlikte, herhangi bir aşikar olmayan, örneğin D ile mevcut olabilir önem düzeyi tüm fonksiyonlar kümesi için kısıtlamaları D için D daha büyük önem düzeyi olan D sürece, D a, tekil grubu .

1970'lerde Dana Scott , sadece sürekli fonksiyonlar göz önüne alındığında, gerekli özelliğe sahip bir küme veya D alanı bulunabileceğini gösterdi, böylece lambda hesabı için bir model sağladı.

Bu çalışma aynı zamanda programlama dillerinin düz anlambiliminin temelini oluşturdu .

Varyasyonlar ve uzantılar

Bu uzantılar lambda küpündedir :

Bu biçimsel sistemler , lambda küpünde olmayan lambda hesabının uzantılarıdır:

Bu resmi sistemler lambda hesabının varyasyonlarıdır:

  • Kappa hesabı - lambda hesabının birinci dereceden bir analogu

Bu resmi sistemler lambda hesabı ile ilgilidir:

  • Birleştirici mantık – Değişkensiz matematiksel mantık için bir gösterim
  • SKI birleştirici hesabı - S , K ve I birleştiricilerine dayalı, lambda hesabına eşdeğer, ancak değişken ikameler olmadan indirgenebilen bir hesaplama sistemi

Ayrıca bakınız

Notlar

Referanslar

daha fazla okuma

Lisansüstü öğrenciler için monograflar/ders kitapları:

  • Morten Heine Sørensen, Paweł Urzyczyn, Lectures on the Curry-Howard izomorfizmi , Elsevier, 2006, ISBN  0-444-52077-5 , tipsiz çeşitten en çok yazılan lambdaya kadar lambda hesabının ana konularını kapsayan yeni bir monografidir. kalıkuli gibi daha yeni gelişmeleri içeren saf tip sistemleri ve lambda küp . Alt tipleme uzantılarını kapsamaz .
  • Pierce, Benjamin (2002), Türler ve Programlama Dilleri , MIT Press, ISBN 0-262-16209-1pratik tip sistem perspektifinden lambda taşlarını kapsar; bağımlı tipler gibi bazı konulardan sadece bahsedilmiştir, ancak alt tipleme önemli bir konudur.

Bu makalenin bazı bölümleri izin alınarak kullanılan FOLDOC materyallerine dayanmaktadır .

Dış bağlantılar

  1. ^ Kilise, Alonzo (1941). Lambda-Dönüşüm Hesabı . Princeton: Princeton Üniversitesi Yayınları . 2020-04-14 alındı .
  2. ^ Frink Jr., Orrin (1944). "İnceleme: Alonzo Church tarafından Lambda-Dönüşüm Hesapları " (PDF) . Boğa. Amer. Matematik. Soc . 50 (3): 169-172. doi : 10.1090/s0002-9904-1944-08090-7 .