Lambda skaičiavimas yra formali matematinės logikos sistema, skirta abstrakcijomis pagrįstiems skaičiavimams išreikšti ir funkcijoms taikyti naudojant įrišimą ir kintamąjį pakeitimą. Tai universalus modelis, kurį galima pritaikyti kuriant bet kurią Tiuringo mašiną. Lambda skaičiavimą XX a. ketvirtajame dešimtmetyje pirmą kartą pristatė Church, žinomas matematikas.
Sistemą sudaro lambda elementų sukūrimas ir su jais mažinimo operacijos.
Paaiškinimai ir taikymas
Graikiška raidė lambda (λ) naudojama lambda išraiškose ir lambda terminuose, nurodant kintamojo susiejimą funkcijoje.
Lambda skaičiavimas gali būti nespausdinamas arba įvestas. Pirmajame variante funkcijos gali būti naudojamos tik tuo atveju, jei jos gali priimti tokio tipo duomenis. Tipiniai lambda akmenys yra silpnesni, gali išreikšti mažesnę reikšmę. Tačiau, kita vertus, jie leidžia įrodyti daugiau dalykų.
Viena iš priežasčių, kodėl yra tiek daug skirtingų tipų, yra mokslininkų noras nuveikti daugiau, neatsisakant galimybės įrodyti stiprių lambda skaičiavimo teoremų.
Sistema pritaikyta įvairiose matematikos, filosofijos, kalbotyros ir informatikos srityse. Visų pirma, lambda skaičiavimas yra skaičiavimas, suvaidinęs svarbų vaidmenį programavimo kalbų teorijos raidoje. Tai yra funkcinės kūrimo stiliai, kuriuos įgyvendina sistemos. Jie taip pat yra aktuali šių kategorijų teorijos tyrimų tema.
Manekenams
Lambda skaičiavimą XX amžiaus ketvirtajame dešimtmetyje pristatė matematikas Alonzo Church, tyrinėdamas mokslo pagrindus. Pirminė sistema buvo logiškai nenuosekli 1935 m., kai Stephenas Kleenas ir J. B. Rosseris sukūrė Kleene-Rosser paradoksą.
Vėliau, 1936 m., Church išskyrė ir paskelbė tik tą dalį, kuri yra svarbi skaičiavimams, tai dabar vadinama netipuotu lambda skaičiavimu. 1940 m. jis taip pat pristatė silpnesnę, bet logiškai nuoseklią teoriją, žinomą kaip pirminio tipo sistema. Savo darbe jis visą teoriją paaiškina paprastais žodžiais, todėl galima sakyti, kad Church paskelbė manekenų lambda skaičiavimą.
Iki septintojo dešimtmečio, kai išaiškėjo jo ryšys su programavimo kalbomis, λ buvo tik formalizmas. Ričardo Montagu ir kitų kalbininkų pritaikymų natūralios kalbos semantikoje dėka skaičiavimas užėmė didžiulę vietą tiek kalbotyroje, tiek kompiuterių moksle.
Simbolio kilmė
Lambda nereiškia žodžio ar akronimo, ji kilusi iš nuorodos Russell's Principal Mathematics ir du spausdinimo pakeitimai. Žymėjimo pavyzdys: funkcijai f, kurios f (y)=2y + 1, yra 2ŷ + 1. Ir čia mes naudojame cet ("kepurę") virš y, norėdami pažymėti įvesties kintamąjį.
Bažnyčia iš pradžių ketino naudoti panašius simbolius, tačiau rinkėjai negalėjo įdėti „skrybėlės“simbolio virš raidžių. Taigi jie iš pradžių išspausdino kaip „/\y.2y+1“. Kitoje redagavimo serijoje spausdintojai „/ \“pakeitė vizualiai panašiu simboliu.
Lambda skaičiavimo įvadas
Sistemą sudaro terminų kalba, kurią pasirenka tam tikra formali sintaksė, ir transformacijos taisyklių rinkinys, leidžiantis jais manipuliuoti. Paskutinis taškas gali būti laikomas lygčių teorija arba operatyviniu apibrėžimu.
Visos lambda skaičiavimo funkcijos yra anoniminės, tai reiškia, kad jos neturi pavadinimų. Jie naudoja tik vieną įvesties kintamąjį, o currying naudojamas brėžiniams su keliais kintamaisiais įgyvendinti.
Lambda sąlygos
Skaičiavimo sintaksė apibrėžia kai kurias išraiškas kaip galiojančias, o kitas - kaip netinkamas. Kaip ir skirtingos simbolių eilutės galioja C programose, o kai kurios ne. Tikroji lambda skaičiavimo išraiška vadinama "lambda terminu".
Šios trys taisyklės pateikia indukcinį apibrėžimą, kuris gali būtitaikoma visoms sintaksiškai galiojančioms sąvokoms kurti:
Pats x kintamasis yra galiojantis lambda terminas:
- jei T yra LT, o x yra nepastovi, tada (lambda xt) vadinama abstrakcija.
- jei T ir s yra sąvokos, tada (TS) vadinama programa.
Niekas kitas nėra lambda terminas. Taigi sąvoka galioja tada ir tik tada, kai ją galima gauti pakartotinai taikant šias tris taisykles. Tačiau kai kurie skliaustai gali būti praleisti pagal kitus kriterijus.
Apibrėžimas
Lambda išraiškas sudaro:
- kintamieji v 1, v 2, …, v n, …
- abstrakcijos simboliai 'λ' ir taškas '.'
- skliausteliai ().
Aibė Λ gali būti apibrėžta indukciniu būdu:
- Jei x yra kintamasis, tada x ∈ Λ;
- x nėra pastovus ir M ∈ Λ, tada (λx. M) ∈ Λ;
- M, N ∈ Λ, tada (MN) ∈ Λ.
Pavadinimas
Kad lambda išraiškų žymėjimas nebūtų perkrautas, dažniausiai naudojami šie susitarimai:
- Išoriniai skliaustai praleisti: MN vietoj (MN).
- Manoma, kad programos išlieka asociatyvios: vietoj ((MN) P galima rašyti MNP).
- Abstrakcijos kūnas tęsiasi toliau į dešinę: λx. MN reiškia λx. (MN), o ne (λx. M) N.
- Abstrakcijų seka sumažinama: λx.λy.λz. N gali būti λxyz. N.
Laisvi ir susieti kintamieji
Operatorius λ sujungia savo nekonstantą, kad ir kur ji būtų abstrakcijos kūno vietoje. Kintamieji, kurie patenka į taikymo sritį, vadinami surištais. Išraiškoje λ x. M, λ x dalis dažnai vadinama rišikliu. Tarsi užuomina, kad kintamieji tampa grupe, prie M pridėjus X x. Visi kiti nestabilūs vadinami laisvais.
Pavyzdžiui, reiškinyje λ y. x x y, y – surištas nenuolatinis, o x – laisvas. Taip pat verta paminėti, kad kintamasis yra sugrupuotas pagal „artimiausią“abstrakciją. Šiame pavyzdyje lambda skaičiavimo sprendimas pavaizduotas vienu x įvykiu, kuris yra susijęs su antruoju nariu:
λ x. y (λ x. z x)
Laisvųjų kintamųjų rinkinys M žymimas kaip FV (M) ir apibrėžiamas terminų struktūros rekursija taip:
- FV (x)={x}, kur x yra kintamasis.
- FV (λx. M)=FV (M) {x}.
- FV (MN)=FV (M) ∪ FV (N).
Formulė, kurioje nėra laisvųjų kintamųjų, vadinama uždara. Uždarosios lambda išraiškos taip pat žinomos kaip kombinatoriai ir yra lygiavertės kombinatorinės logikos terminams.
Santrumpa
Lambda posakių reikšmė nustatoma pagal tai, kaip jas galima sutrumpinti.
Yra trijų tipų pjūviai:
- α-transformacija: susietųjų kintamųjų keitimas (alfa).
- β sumažinimas: funkcijų taikymas jų argumentams (beta).
- η-transformacija: apima ekstensyvumo sąvoką.
Čia irgimes kalbame apie gautus ekvivalentus: dvi išraiškos yra β-ekvivalentės, jei jas galima β-paversti į tą patį komponentą, o α / η-ekvivalentiškumas apibrėžiamas panašiai.
Terminas redex, sutrumpintai reiškiantis sumažinamą apyvartą, reiškia potemes, kurias galima sumažinti pagal vieną iš taisyklių. Lambda skaičiavimas manekenams, pavyzdžiai:
(λ x. M) N yra beta redeksas išraiškoje, skirtoje N pakeitimui x M. Komponentas, iki kurio reduktorius redukuoja, vadinamas jo redukcija. Sumažėjimas (λ x. M) N yra M [x:=N].
Jei x nėra laisvas M, λ x. M x taip pat em-REDEX su reguliatoriumi M.
α-transformacija
Alfa pervadinimas leidžia keisti susietų kintamųjų pavadinimus. Pavyzdžiui, x. x gali duoti λ y. y. Sakoma, kad terminai, kurie skiriasi tik alfa transformacija, yra α ekvivalentai. Dažnai, naudojant lambda skaičiavimą, α ekvivalentai laikomi abipusiais.
Tikslios alfa konvertavimo taisyklės nėra visiškai nereikšmingos. Pirma, naudojant šią abstrakciją, pervardyti tik tie kintamieji, kurie yra susieti su ta pačia sistema. Pavyzdžiui, alfa transformacija λ x.λ x. x gali sukelti λ y.λ x. x, bet tai negali sukelti λy.λx.y Pastarasis turi kitokią reikšmę nei originalas. Tai yra analogiška kintamojo šešėlinio programavimo koncepcijai.
Antra, alfa transformacija neįmanoma, jei ją užfiksuotų nepastovi kita abstrakcija. Pavyzdžiui, jei λ x.λ y pakeisite x į y. x, tada galite gautiλy.λy. u, kuris visai ne tas pats.
Programavimo kalbose su statine apimtimi alfa konvertavimas gali būti naudojamas siekiant supaprastinti vardų skyrimą. Tuo pat metu pasirūpinkite, kad kintamojo sąvoka neužmaskuotų pavadinimo srityje, kurioje yra.
De Bruyne indekso žymėjime bet kurie du alfa lygiaverčiai terminai yra sintaksiškai identiški.
Pakeitimas
Pakeitimai, kuriuos rašo E [V:=R], yra procesas, kai visi laisvi kintamojo V atvejai išraiškoje E pakeičiami apyvarta R. Pakeitimas λ apibrėžiamas rekursijos lambda sąvokos struktūros skaičiavimas taip (pastaba: x ir y – tik kintamieji, o M ir N – bet kokia λ išraiška).
x [x:=N] ≡ N
y [x:=N] ≡ y, jei 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]), jei x ≠ y, su sąlyga, kad y ∉ FV (N).
Norint pakeisti lambda abstrakciją, kartais reikia raišką transformuoti α. Pavyzdžiui, netiesa, kad (λ x. Y) [y:=x] rezultatas (λ x. X), nes pakeistas x turėjo būti laisvas, bet galiausiai buvo susietas. Šiuo atveju teisingas pakeitimas yra (λ z. X) iki α ekvivalento. Atminkite, kad pakeitimas yra unikaliai apibrėžtas iki lambda.
β-sumažinimas
Beta sumažinimas atspindi funkcijos taikymo idėją. Beta redukcinis yra apibrėžiamas terminaispakeitimas: ((X V. E) E ') yra E [V:=E'].
Pavyzdžiui, darant prielaidą, kad tam tikra koduota 2, 7, ×, gaunama tokia β redukcija: ((λ n. N × 2) 7) → 7 × 2.
Beta redukcija gali būti vertinama kaip ta pati vietinio redukavimo koncepcija taikant natūralią dedukciją pagal Curry-Howard izomorfizmą.
η-transformuoti
Šis konvertavimas išreiškia išplėtimo idėją, kuri šiame kontekste reiškia, kad dvi funkcijos yra lygios, kai duoda tą patį rezultatą visiems argumentams. Ši konversija keičiasi tarp λ x. (F x) ir f, kai x neatrodo laisvas f.
Šis veiksmas gali būti laikomas tuo pačiu, kaip vietinio užbaigtumo sąvoka natūralioje dedukcijoje pagal Curry-Howard izomorfizmą.
Įprastos formos ir susiliejimas
Netipuotam lambda skaičiavimui β redukcijos taisyklė paprastai nėra nei stipri, nei silpna normalizuojanti.
Vis dėlto galima parodyti, kad β redukcija susilieja, kai vykdoma prieš α transformaciją (t. y. dvi normaliosios formos gali būti laikomos lygiomis, jei įmanoma α transformacija iš vienos į kitą).
Todėl tiek stipriai normalizuojantys, tiek silpnai koreguojantys terminai turi vieną normaliąją formą. Pirmosiomis sąlygomis garantuojama, kad bet kokia mažinimo strategija bus tipiška konfigūracija. Tuo tarpu esant silpnai normalizuojančioms sąlygoms, kai kurios mažinimo strategijos gali to nerasti.
Papildomi programavimo metodai
Yra daug lambda skaičiavimo kūrimo idiomų. Daugelis jų iš pradžių buvo sukurti naudojant sistemas kaip programavimo kalbos semantikos pagrindą, efektyviai pritaikant jas kaip žemo lygio konstrukciją. Kadangi kai kuriuose stiliuose kaip fragmentas yra lambda skaičiavimas (ar kažkas labai panašaus), šie metodai taip pat pritaikomi praktikoje kūryboje, tačiau vėliau gali būti suvokiami kaip neaiškūs arba svetimi.
Pavadintos konstantos
Lambda skaičiavime biblioteka yra anksčiau apibrėžtų funkcijų rinkinio forma, kur terminai yra tik konkrečios konstantos. Gryni skaičiavimai neturi įvardintų nekintančių sąvokos, nes visi atominiai lambda terminai yra kintamieji. Tačiau jas taip pat galima imituoti keičiant konstantos pavadinimą, naudojant lambda abstrakciją, kad surištų tą lakią medžiagą kūne, ir taikant tą abstrakciją numatytam apibrėžimui. Taigi, jei naudojate f, nurodydami M N, galite pasakyti
(λ f. N) M.
Autoriai dažnai pristato sintaksinę koncepciją, pvz., leisti, kad būtų galima rašyti intuityviau.
f=M iki N
Sujungus tokius apibrėžimus, lambda skaičiavimo „programą“galima parašyti kaip nulį ar daugiau funkcijų apibrėžimų, po kurių seka vienas lambda narys, naudojant tuos apibrėžimus, kurie sudaro didžiąją programos dalį.
Pažymėtinas šio teiginio apribojimas yra tas, kad vardas f nėra apibrėžtas M,kadangi M nepatenka į privalomą lambda abstrakcijos f sritį. Tai reiškia, kad rekursinės funkcijos atributas negali būti naudojamas kaip M su let. Pažangesnė „letrec“sintaksė, leidžianti šiuo stiliumi rašyti rekursyvių funkcijų apibrėžimus, vietoj to papildomai naudoja fiksuoto taško kombinatorius.
Spausdinti analogai
Šis tipas yra spausdintas formalizmas, kuriame naudojamas simbolis anoniminės funkcijos abstrakcijai pavaizduoti. Šiame kontekste tipai dažniausiai yra sintaksinio pobūdžio objektai, priskiriami lambda terminams. Tikslus pobūdis priklauso nuo nagrinėjamo skaičiavimo. Tam tikru požiūriu įvestas LI gali būti laikomas netipuoto LI patobulinimais. Tačiau, kita vertus, jie taip pat gali būti laikomi fundamentalesne teorija, o netipinis lambda skaičiavimas yra ypatingas atvejis, kai naudojamas tik vienas tipas.
Typed LI yra programavimo kalbų pagrindas ir funkcinių kalbų, tokių kaip ML ir Haskell, pagrindas. Ir, dar netiesiogiai, imperatyvūs kūrybos stiliai. Tipiniai lambda skaičiavimai vaidina svarbų vaidmenį kuriant programavimo kalbų tipų sistemas. Čia tipiškumas paprastai užfiksuoja norimas programos savybes, pavyzdžiui, nesukels prieigos prie atminties pažeidimo.
Įrašyti lambda skaičiavimai yra glaudžiai susiję su matematine logika ir įrodymų teorija per Curry-Howard izomorfizmą ir gali būti laikomi, pavyzdžiui, vidine kategorijų klasių kalba, kuriTai tiesiog Dekarto uždarymo stilius.
