Lambdalaskenta on muodollinen matemaattisen logiikan järjestelmä abstraktioon perustuvien laskutoimitusten ilmaisemiseen ja funktioiden soveltamiseen sidonta- ja muuttujakorvaustoimintojen avulla. Tämä on universaali malli, jota voidaan soveltaa minkä tahansa Turingin koneen suunnitteluun. Church, kuuluisa matemaatikko, esitteli lambda-laskennan ensimmäisen kerran 1930-luvulla.
Järjestelmä koostuu lambda-osien rakentamisesta ja niille tehtyjen pelkistystoimenpiteiden suorittamisesta.
Selitykset ja sovellukset
Kreikkalaista kirjainta lambda (λ) käytetään lambda-lausekkeissa ja lambda-termeissä osoittamaan muuttujan sitoutumista funktiossa.
Lambda-laskennassa voi olla kirjoittamaton tai kirjoitettu. Ensimmäisessä versiossa toimintoja voidaan käyttää vain, jos ne pystyvät vastaanottamaan tämän tyyppistä dataa. Tyypilliset lambda-kivet ovat heikompia, voivat ilmaista pienemmän arvon. Mutta toisa alta niiden avulla voit todistaa enemmän asioita.
Yksi syy siihen, että erilaisia tyyppejä on niin monia, on tutkijoiden halu tehdä enemmän luopumatta mahdollisuudesta todistaa vahvoja lambda-laskennan lauseita.
Järjestelmässä on sovelluksia monilla eri matematiikan, filosofian, kielitieteen ja tietojenkäsittelytieteen aloilla. Ensinnäkin lambda-laskenta on laskenta, jolla on ollut tärkeä rooli ohjelmointikielten teorian kehityksessä. Järjestelmät toteuttavat toiminnallisen luomisen tyylejä. Ne ovat myös kuuma tutkimusaihe näiden kategorioiden teoriassa.
Nukeille
Matemaatiko Alonzo Church esitteli lambda-laskennan 1930-luvulla osana tieteen perusteita koskevaa tutkimustaan. Alkuperäinen järjestelmä osoitettiin loogisesti epäjohdonmukaiseksi vuonna 1935, kun Stephen Kleen ja J. B. Rosser kehittivät Kleene-Rosserin paradoksin.
Myöhemmin, vuonna 1936, Church valitsi ja julkaisi vain laskelmien kann alta merkityksellisen osan, jota nykyään kutsutaan tyypittämättömäksi lambda-laskemiseksi. Vuonna 1940 hän esitteli myös heikomman mutta loogisesti johdonmukaisen teorian, joka tunnetaan alkutyypin järjestelmänä. Työssään hän selittää koko teorian yksinkertaisin sanoin, joten voidaan sanoa, että Church julkaisi calculus lambda tutteja varten.
1960-luvulle asti, jolloin sen suhde ohjelmointikieliin tuli selväksi, λ oli vain formalismia. Richard Montagun ja muiden kielitieteilijöiden luonnollisen kielen semantiikan sovellusten ansiosta laskenta on saavuttanut ylpeyden sekä kielitieteen että tietojenkäsittelytieteen alalla.
Symbolin alkuperä
Lambda ei tarkoita sanaa tai lyhennettä, se tulee Russellin päämatematiikan viittauksesta, jota seuraa kaksi typografista muutosta. Merkintäesimerkki: funktiolle f, jonka f (y)=2y + 1, on 2ŷ + 1. Ja tässä käytämme caret-merkkiä ("hattu") y:n päälle syötteen muuttujan merkitsemiseen.
Kirkon tarkoituksena oli alun perin käyttää samanlaisia symboleja, mutta ladontalaitteet eivät pystyneet sijoittamaan "hattu" -symbolia kirjainten yläpuolelle. Joten sen sijaan he painoivat sen alun perin muodossa "/\y.2y+1". Seuraavassa editointijaksossa konekirjoittajat korvasivat "/\" visuaalisesti samank altaisella merkillä.
Johdatus lambda-laskentaan
Järjestelmä koostuu termien kielestä, jotka valitaan tietyn muodollisen syntaksin mukaan, ja joukosta muunnossääntöjä, jotka mahdollistavat niiden manipuloinnin. Viimeistä kohtaa voidaan pitää yhtälöteoriana tai operatiivisena määritelmänä.
Kaikki lambda-laskimen funktiot ovat anonyymejä, eli niillä ei ole nimiä. Ne ottavat vain yhden syöttömuuttujan, ja curryusta käytetään useiden muuttujien sisältävien kaavioiden toteuttamiseen.
Lambdaehdot
Lasken syntaksi määrittelee jotkin lausekkeet kelvollisiksi ja toiset virheellisiksi. Aivan kuten eri merkkijonot ovat kelvollisia C-ohjelmia ja jotkut eivät. Lambda-laskimen varsinaista lauseketta kutsutaan "lambdatermiksi".
Seuraavat kolme sääntöä tarjoavat induktiivisen määritelmän, joka voi ollasovelletaan kaikkien syntaktisesti kelvollisten käsitteiden rakentamiseen:
X-muuttuja itsessään on kelvollinen lambda-termi:
- jos T on LT ja x ei-vakio, niin (lambda xt) kutsutaan abstraktioksi.
- jos T sekä s ovat käsitteitä, niin (TS) kutsutaan sovellukseksi.
Mikään muu ei ole lambda-termi. Siten käsite on pätevä silloin ja vain, jos se voidaan saada soveltamalla näitä kolmea sääntöä toistuvasti. Jotkut sulut voidaan kuitenkin jättää pois muiden kriteerien mukaan.
Määritelmä
Lambda-lausekkeet koostuvat seuraavista:
- muuttujat v 1, v 2, …, v n, …
- abstraktion 'λ' ja pisteen symbolit.'
- sulut ().
Joukko Λ voidaan määrittää induktiivisesti:
- Jos x on muuttuja, niin x ∈ Λ;
- x ei ole vakio ja M ∈ Λ, sitten (λx. M) ∈ Λ;
- M, N ∈ Λ, sitten (MN) ∈ Λ.
Nimittely
Jotta lambda-lausekkeiden merkintätapa pysyy epäselvänä, käytetään yleisesti seuraavia käytäntöjä:
- Ulkoiset sulut jätetty pois: MN (MN) sijaan.
- Sovellusten oletetaan pysyvän assosiatiivisina: ((MN) P:n sijaan voidaan kirjoittaa MNP).
- Abstraktiokappale ulottuu edelleen oikealle: λx. MN tarkoittaa λx. (MN), ei (λx. M) N.
- Abstraktioiden järjestystä pienennetään: λx.λy.λz. N voi olla λxyz. N.
Vapaat ja sidotut muuttujat
Operaattori λ yhdistää ei-vakionsa missä tahansa abstraktiokappaleessa. Muuttujia, jotka kuuluvat soveltamisalaan, kutsutaan sidotuiksi. Lausekkeessa λ x. M, λ x -osaa kutsutaan usein sideaineeksi. Ihan kuin vihjaisi, että muuttujista tulee ryhmä lisäämällä X x M:ään. Kaikkia muita epävakaita kutsutaan vapaiksi.
Esimerkiksi lausekkeessa λ y. x x y, y - sidottu ei-pysyvä ja x - vapaa. Ja on myös syytä huomata, että muuttuja on ryhmitelty sen "lähimmän" abstraktion mukaan. Seuraavassa esimerkissä lambda-laskennan ratkaisua edustaa yksi x:n esiintymä, joka liittyy toiseen termiin:
λ x. y (λ x. z x)
Vapaiden muuttujien joukkoa M merkitään FV (M) ja se määritellään termien rakenteen rekursiolla seuraavasti:
- FV (x)={x}, missä x on muuttuja.
- FV (λx. M)=FV (M) {x}.
- FV (MN)=FV (M) ∪ FV (N).
Kaavaa, joka ei sisällä vapaita muuttujia, kutsutaan suljetuksi. Suljetut lambda-lausekkeet tunnetaan myös kombinaattoreina, ja ne vastaavat kombinatorisen logiikan termejä.
Lyhenne
Lambda-lausekkeiden merkitys määräytyy sen mukaan, kuinka niitä voidaan lyhentää.
Leikkauksia on kolmenlaisia:
- α-muunnos: sidottujen muuttujien muuttaminen (alfa).
- β-pelkistys: funktioiden käyttäminen argumenteissaan (beta).
- η-muunnos: kattaa ulottuvuuden käsitteen.
Tässä se myös onpuhumme tuloksena olevista ekvivalensseista: kaksi lauseketta ovat β-ekvivalentteja, jos ne voidaan β-muuntaa samaksi komponentiksi, ja α / η-ekvivalenssi määritellään samalla tavalla.
Termi redex, lyhenne sanoista vähennettävä liikevaihto, viittaa ala-aiheisiin, joita voidaan vähentää jollakin säännöistä. Lambda-laskenta nukkeille, esimerkkejä:
(λ x. M) N on beeta-redex lausekkeessa, jolla N korvataan x:llä M:ssä. Komponenttia, johon redeksi pelkistää, kutsutaan sen reduktiksi. Vähennys (λ x. M) N on M [x:=N].
Jos x ei ole vapaa M:ssä, λ x. M x myös em-REDEX säätimellä M.
α-muunnos
Alfa-uudelleennimeämisellä voit muuttaa sidottujen muuttujien nimiä. Esimerkiksi x. x voi antaa λ y:n. y. Termien, jotka eroavat vain alfa-muunnoksessa, sanotaan olevan α-ekvivalentteja. Usein lambda-laskentaa käytettäessä α-ekvivalentteja pidetään vastavuoroisina.
Tarkat alfamuunnoksen säännöt eivät ole täysin triviaaleja. Ensinnäkin tällä abstraktilla vain ne muuttujat, jotka liittyvät samaan järjestelmään, nimetään uudelleen. Esimerkiksi alfamuunnos λ x.λ x. x voi johtaa arvoon λ y.λ x. x, mutta tämä ei välttämättä johda arvoon λy.λx.y. Jälkimmäisellä on eri merkitys kuin alkuperäisellä. Tämä on analoginen muuttuvan varjostusohjelmoinnin käsitteen kanssa.
Toiseksi alfamuunnos ei ole mahdollinen, jos se johtaisi ei-pysyvän muun abstraktion kaappaamiseen. Jos esimerkiksi korvaat x:n y:llä kohdassa λ x.λ y. x, niin saatλy.λy. u, joka ei ole ollenkaan sama.
Staattisilla ohjelmointikielillä alfamuunnoksia voidaan käyttää nimenselvityksen yksinkertaistamiseen. Samalla on huolehdittava siitä, että muuttujan käsite ei peitä nimitystä sisältävällä alueella.
De Bruynen indeksimerkinnöissä mitkä tahansa kaksi alfa-ekvivalenttia termiä ovat syntaktisesti identtisiä.
Vaihto
E:n kirjoittamat muutokset [V:=R] ovat prosessi, jossa kaikki muuttujan V vapaat esiintymät lausekkeessa E korvataan liikevaihdolla R. Korvaus λ:n suhteen määritellään rekursion lambdalla. laskenta käsiterakenteesta seuraavasti (huomaa: x ja y - vain muuttujat ja M ja N - mikä tahansa λ-lauseke).
x [x:=N] ≡ N
y [x:=N] ≡ y jos x ≠ y
(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 λ y. (M [x:=N]), jos x ≠ y, edellyttäen että y ∉ FV (N).
Lambda-abstraktion korvaamiseksi joskus on tarpeen α-muuntaa lauseke. Ei esimerkiksi ole totta, että (λ x. Y) [y:=x] johtaa tulokseen (λ x. X), koska substituoidun x:n olisi pitänyt olla vapaa, mutta se päätyi sidotuksi. Oikea korvaus tässä tapauksessa on (λ z. X) α-ekvivalenssiin asti. Huomaa, että substituutio on yksilöllisesti määritelty lambdaan asti.
β-alennus
Beta-alennus heijastaa ajatusta funktion käyttämisestä. Beeta-pelkistävä määritellään termeilläkorvaus: ((X V. E) E ') on E [V:=E'].
Esimerkiksi jos jokin koodaus 2, 7, × on olemassa seuraava β-pelkistys: ((λ n. N × 2) 7) → 7 × 2.
Beta-pelkistys voidaan nähdä samana kuin paikallisen pelkistymisen käsite luonnollisessa deduktiossa Curry-Howard-isomorfismin kautta.
η-muunnos
Tämä muunnos ilmaisee ajatusta laajennuksesta, joka tässä yhteydessä tarkoittaa, että kaksi funktiota ovat samanarvoisia, kun ne antavat saman tuloksen kaikille argumenteille. Tämä muunnos vaihtuu välillä λ x. (F x) ja f aina, kun x ei vaikuta vapa alta f:ssä.
Tätä toimintoa voidaan pitää samana kuin paikallisen täydellisyyden käsite luonnollisessa päättelyssä Curry-Howard-isomorfismin kautta.
Normaalit muodot ja fuusio
Typistämättömässä lambda-laskennassa β-pelkistyssääntö ei yleensä ole vahva eikä heikko normalisoiva.
Voidaan kuitenkin osoittaa, että β-pelkistys sulautuu ajettaessa ennen α-muunnosta (eli kahta normaalimuotoa voidaan pitää yhtäläisinä, jos α-muunnos toisesta on mahdollista).
Siksi sekä voimakkaasti normalisoivilla termeillä että heikosti mukautuvilla termeillä on yksi normaalimuoto. Ensimmäisillä termeillä kaikki vähennysstrategiat johtavat tyypilliseen kokoonpanoon. Sitä vastoin heikosti normalisoituvissa olosuhteissa jotkin vähennysstrategiat eivät välttämättä löydä sitä.
Lisäohjelmointimenetelmät
Lambda-laskennassa on monia luomisidioomeja. Monet niistä kehitettiin alun perin järjestelmien käytön yhteydessä ohjelmointikielen semantiikan perustana soveltaen niitä tehokkaasti matalan tason konstruktiona. Koska jotkin tyylit sisältävät lambda-laskennan (tai jotain hyvin samank altaista) katkelmana, näitä tekniikoita voidaan käyttää myös käytännön luomisessa, mutta ne voidaan sitten pitää epäselvänä tai vieraana.
Nimetyt vakiot
Lambda-laskennassa kirjasto muodostuu aiemmin määriteltyjen funktioiden joukosta, jossa termit ovat vain konkreettisia vakioita. Puhtaalla laskennalla ei ole käsitettä nimetyistä muuttumattomista, koska kaikki atomi lambdatermit ovat muuttujia. Mutta niitä voidaan myös jäljitellä ottamalla muuttuva vakion nimeksi, käyttämällä lambda-abstraktia sitomaan tämä haihtuva aine kehossa ja soveltamalla tätä abstraktiota tarkoitettuun määritelmään. Joten jos käytät f edustamaan M:tä N:ssä, voit sanoa
(λ f. N) M.
Tekijät ottavat usein käyttöön syntaktisen käsitteen, kuten anna, jotta asiat voidaan kirjoittaa intuitiivisemmalla tavalla.
f=M - N
Ketjuttamalla tällaisia määritelmiä voidaan kirjoittaa lambdalaskennan "ohjelma" nollaksi tai useammaksi funktiomääritelmäksi, jota seuraa yksi lambda-jäsen, käyttämällä määritelmiä, jotka muodostavat suurimman osan ohjelmasta.
Tämän oletuksen merkittävä rajoitus on, että nimeä f ei ole määritelty kirjaimessa M,koska M on lambda-abstraktion f sitovan alueen ulkopuolella. Tämä tarkoittaa, että rekursiivisen funktion attribuuttia ei voi käyttää M:nä letillä. Edistyneempi letrec-syntaksi, jonka avulla voit kirjoittaa rekursiivisia funktiomääritelmiä tähän tyyliin, käyttää lisäksi kiinteän pisteen kombinaattoreita.
Painetut analogit
Tämä tyyppi on kirjoitettu formalismi, joka käyttää symbolia edustamaan anonyymiä funktion abstraktiota. Tässä yhteydessä tyypit ovat yleensä syntaktisia objekteja, jotka on liitetty lambda-termeihin. Tarkka luonne riippuu kyseessä olevasta laskusta. Tietystä näkökulmasta kirjoitettua LI voidaan pitää tyypittämättömän LI:n tarkennuksina. Mutta toisa alta niitä voidaan pitää myös perustavanlaatuisempana teoriana, ja tyypittämätön lambda-laskenta on erikoistapaus, jossa on vain yksi tyyppi.
Typed LI ovat ohjelmointikielten perusta ja toiminnallisten kielten, kuten ML ja Haskell, selkäranka. Ja välillisemmin pakolliset luomistyylit. Tyydytetyillä lambda-laskuilla on tärkeä rooli ohjelmointikielten tyyppijärjestelmien kehittämisessä. Tässä tyypitys yleensä kaappaa ohjelman halutut ominaisuudet, esimerkiksi se ei aiheuta muistirikkomusta.
Tydetyt lambda-laskokset liittyvät läheisesti matemaattiseen logiikkaan ja todistusteoriaan Curry–Howard-isomorfismin kautta, ja niitä voidaan pitää esimerkiksi luokkaluokkien sisäisenä kielenä.on yksinkertaisesti karteesisten sulkujen tyyli.
