Lambdakalkyyli

Wikipediasta
(Ohjattu sivulta Lambda-kalkyyli)
Siirry navigaatioon Siirry hakuun

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]

Historiaa

[muokkaa | muokkaa wikitekstiä]

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]

Peruskäsitteet

[muokkaa | muokkaa wikitekstiä]

Lambdakalkyylin ilmaisu koostuu termeistä. Termit ovat muuttujat, lambda-abstraktiot, ja sovellukset. Muuttujia määritellään abstraktioilla, ja niitä käytetään sovelluksilla.[1]

Termit

[muokkaa | muokkaa wikitekstiä]
  • muuttuja, esim. i, x, v
  • abstraktio, käyttää symboleita . ja λらむだ, esim. lambda λらむだx.i
  • sovellus, esim. lambdojen y ja i sovellus: yi

Lambda

[muokkaa | muokkaa wikitekstiä]

Lambda-abstraktiota symboloi kreikkalaisen aakkosten kirjain λらむだ.

Churchin numeraalit

[muokkaa | muokkaa wikitekstiä]

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

[muokkaa | muokkaa wikitekstiä]

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.

Katso myös

[muokkaa | muokkaa wikitekstiä]

Lähteet

[muokkaa | muokkaa wikitekstiä]
  1. ↑ a b c d e Huovinen, Marja: Lambdakalkyylin perusteita (postscript (.ps)) tyyppiteoria ja ohjelmointikielet – seminaari. Helsinki 30.1.2003. Tietojenkäsittelytieteen laitos, HELSINGIN YLIOPISTO. Viitattu 10.1.2012. (suomeksi)
Noudettu kohteesta ”https://fi.wikipedia.org/w/index.php?title=Lambdakalkyyli&oldid=22163792”