Lambdakalkyyli (engl. lambda calculus) on formaalin laskennan malli. Sen avulla voidaan käsitellä matemaattisia ja laskennallisia ongelmia.
Lambdakalkyyli on Turing-täydellinen, eli sillä voidaan ilmaista mitä tahansa matemaattisia laskennan ongelmia.
Lambdakalkyyliä voidaan myös itsessään pitää ohjelmointikielenä.[1]
Alonzo Church kehitti lambdakalkyylin kollegoineen 1920 ja 30-luvulla.[1]
Korjattuaan ensiversionsa ongelmia Church julkisti vuonna 1936 tietojenkäsittelyyn sopivan osion, tyypittömän lambdakalkyylin. Myöhemmin 1940-luvulla Church julkisti yksinkertaisesti tyypitetyn lambdakalkyylin.
Funktionaaliset ohjelmointikielet perustuvat pitkälti lambda-kalkyyliin.[1]
Lambdakalkyylin ilmaisu koostuu termeistä. Termit ovat muuttujat, lambda-abstraktiot, ja sovellukset. Muuttujia määritellään abstraktioilla, ja niitä käytetään sovelluksilla.[1]
Termit
- muuttuja, esim.
i, x, v - abstraktio, käyttää symboleita
.jaλ, esim. lambdaλx.i - sovellus, esim. lambdojen y ja i sovellus:
yi
Lambda
Lambda-abstraktiota symboloi kreikkalaisen aakkosten kirjain λ.
Churchin numeraalit
Numerot voidaan ilmaista monilla eri tavoin. Yksi tapa on Churchin numeraalit.
*0 := λfx. x *1 := λfx. fx *2 := λfx. f( fx ) *3 := λfx. f( f( fx )) *jne.
Tyypitetty ja tyypittämätön
Tyypittämättömässä lambdakalkyylissä ei ole lainkaan valmiiksi määriteltyjä vakioita tai operaattoreita kuten numerot, aritmeettiset operaatiot tai ehtolauseet. Tarvittaessa ne määritellään, kuten esim. numerot Churchin numeraaleilla.[1]
Tyypitetyssä lambdakalkyylissä jokaiselle termille tulee olla yksi tyyppi.
- Churchin-Turingin teesi
- Lisp-ohjelmointikieli
- Haskell-ohjelmointikieli
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
