Calcul lambda este un sistem formal în logica matematică pentru exprimarea calculelor bazate pe abstractizare și aplicarea funcțiilor folosind legarea și substituția variabilelor. Acesta este un model universal care poate fi aplicat la proiectarea oricărei mașini Turing. Calculul lambda a fost introdus pentru prima dată de Church, un matematician celebru, în anii 1930.
Sistemul constă în construirea de membri lambda și efectuarea de operațiuni de reducere asupra acestora.
Explicații și aplicații
Litera greacă lambda (λ) este folosită în expresiile lambda și termenii lambda pentru a desemna legarea unei variabile într-o funcție.
Calcul lambda poate fi netipizat sau tastat. În prima variantă, funcțiile pot fi utilizate numai dacă sunt capabile să primească date de acest tip. Calculele lambda tipizate sunt mai slabe, pot exprima o valoare mai mică. Dar, pe de altă parte, vă permit să demonstrați mai multe lucruri.
Un motiv pentru care există atât de multe tipuri diferite este dorința oamenilor de știință de a face mai mult fără a renunța la oportunitatea de a demonstra teoreme puternice de calcul lambda.
Sistemul are aplicații în multe domenii diferite ale matematicii, filosofiei, lingvisticii și informaticii. În primul rând, calculul lambda este un calcul care a jucat un rol important în dezvoltarea teoriei limbajelor de programare. Sunt stilurile de creație funcțională pe care sistemele le implementează. Ele sunt, de asemenea, un subiect fierbinte de cercetare în teoria acestor categorii.
Pentru manechin
Calculul lambda a fost introdus de matematicianul Alonzo Church în anii 1930, ca parte a cercetării sale asupra fundamentelor științei. Sistemul original sa dovedit a fi inconsecvent din punct de vedere logic în 1935, când Stephen Kleen și J. B. Rosser au dezvoltat paradoxul Kleene-Rosser.
Mai târziu, în 1936, Church a evidențiat și a publicat doar partea care este relevantă pentru calcule, ceea ce se numește acum calculul lambda netipizat. În 1940, el a introdus și o teorie mai slabă, dar consistentă din punct de vedere logic, cunoscută sub numele de sistemul de tip prim. În lucrarea sa, el explică întreaga teorie în termeni simpli, așa că se poate spune că Church a publicat calculul lambda pentru manechine.
Până în anii 1960, când relația sa cu limbajele de programare a devenit clară, λ era doar un formalism. Datorită aplicațiilor lui Richard Montagu și ale altor lingviști în semantica limbajului natural, calculul a ocupat locul de mândrie atât în lingvistică, cât și în informatică.
Originea simbolului
Lambda nu reprezintă un cuvânt sau un acronim, ea provine dintr-o referință în Matematica principală a lui Russell, urmată de două modificări tipografice. Exemplu de notație: pentru o funcție f cu f (y)=2y + 1 este 2ŷ + 1. Și aici folosim o accent („pălărie”) peste y pentru a eticheta variabila de intrare.
Biserica a intenționat inițial să folosească simboluri similare, dar tipografii nu au putut plasa simbolul „pălărie” deasupra literelor. Deci, în schimb, l-au tipărit inițial ca „/\y.2y+1”. În următorul episod de editare, dactilografele au înlocuit „/ \” cu un caracter similar vizual.
Introducere în calculul lambda
Sistemul constă dintr-un limbaj de termeni, care sunt aleși printr-o anumită sintaxă formală și un set de reguli de transformare care permit manipularea acestora. Ultimul punct poate fi considerat ca o teorie ecuațională sau ca o definiție operațională.
Toate funcțiile din calculul lambda sunt anonime, adică nu au nume. Aceștia iau o singură variabilă de intrare, iar curry este folosit pentru a implementa diagrame cu mai multe variabile.
termeni Lambda
Sintaxa de calcul definește unele expresii ca fiind valide, iar altele ca nevalide. La fel cum diferite șiruri de caractere sunt programe C valide, iar unele nu sunt. Expresia reală a calculului lambda se numește „termen lambda”.
Următoarele trei reguli oferă o definiție inductivă care poate fise aplică la construcția tuturor conceptelor valide sintactic:
Variabila x în sine este un termen lambda valid:
- dacă T este LT și x este neconstant, atunci (lambda xt) se numește abstracție.
- dacă T, precum și s sunt concepte, atunci (TS) se numește aplicație.
Nimic altceva nu este un termen lambda. Astfel, un concept este valabil dacă și numai dacă poate fi obținut prin aplicarea repetată a acestor trei reguli. Cu toate acestea, unele paranteze pot fi omise în funcție de alte criterii.
Definiție
Expresiile lambda constau în:
- variabile v 1, v 2, …, v n, …
- simboluri de abstractizare „λ” și punct „.”
- paranteze ().
Setul Λ poate fi definit inductiv:
- Dacă x este o variabilă, atunci x ∈ Λ;
- x nu este constant și M ∈ Λ, atunci (λx. M) ∈ Λ;
- M, N ∈ Λ, apoi (MN) ∈ Λ.
Desemnare
Pentru a menține notarea expresiilor lambda neaglomerate, se folosesc în mod obișnuit următoarele convenții:
- Paranteze exterioare omise: MN în loc de (MN).
- Se presupune că aplicațiile rămân asociative: se poate scrie MNP în loc de ((MN) P).
- Corpul abstracției se extinde mai spre dreapta: λx. MN înseamnă λx. (MN), nu (λx. M) N.
- Secvența abstracțiilor este redusă: λx.λy.λz. N poate fi λxyz. N.
Variabile libere și legate
Operatorul λ își conectează non-constanta oriunde se află în corpul abstracției. Variabilele care intră în domeniul de aplicare se numesc legate. În expresia λ x. M, partea λ x este adesea denumită un liant. Ca și cum ar sugera că variabilele devin un grup prin adăugarea lui X x la M. Toate celel alte instabile sunt numite libere.
De exemplu, în expresia λ y. x x y, y - legat nepermanent și x - liber. Și este, de asemenea, de remarcat faptul că variabila este grupată după „cea mai apropiată” abstractizare a acesteia. În exemplul următor, soluția de calcul lambda este reprezentată de o singură apariție a lui x, care este legată de al doilea termen:
λ x. y (λ x. z x)
Setul de variabile libere M este notat cu FV (M) și este definit prin recursivitate asupra structurii termenilor, după cum urmează:
- FV (x)={x}, unde x este o variabilă.
- FV (λx. M)=FV (M) {x}.
- FV (MN)=FV (M) ∪ FV (N).
O formulă care nu conține variabile libere se numește închisă. Expresiile lambda închise sunt cunoscute și ca combinatori și sunt echivalente cu termenii din logica combinatorie.
Abreviere
Semnificația expresiilor lambda este determinată de modul în care pot fi scurtate.
Există trei tipuri de tăieturi:
- α-transform: modificarea variabilelor legate (alfa).
- β-reducere: aplicarea de funcții argumentelor lor (beta).
- η-transformă: acoperă noțiunea de extensialitate.
Iată-l șivorbim despre echivalențe rezultate: două expresii sunt β-echivalente dacă pot fi β-transformate în aceeași componentă, iar α / η-echivalența este definită în mod similar.
Termenul redex, prescurtare pentru cifra de afaceri reductibilă, se referă la subiecte secundare care pot fi reduse de una dintre reguli. Calcul lambda pentru manechine, exemple:
(λ x. M) N este un beta redex în expresia pentru înlocuirea lui N cu x în M. Componenta la care se reduce un redex se numește reducție. Reducerea (λ x. M) N este M [x:=N].
Dacă x nu este liber în M, λ x. M x, de asemenea, em-REDEX cu regulator M.
α-transformation
Redenumirile Alpha vă permit să schimbați numele variabilelor legate. De exemplu, x. x poate da λ y. y. Termenii care diferă numai în transformarea alfa se spune că sunt echivalenți în alfa. Adesea, atunci când se utilizează calculul lambda, echivalentele α sunt considerate reciproce.
Regulile exacte pentru conversia alfa nu sunt în întregime banale. În primul rând, cu această abstracție, numai acele variabile care sunt asociate cu același sistem sunt redenumite. De exemplu, transformarea alfa λ x.λ x. x poate duce la λ y.λ x. x, dar acest lucru poate să nu conducă la λy.λx.y Acesta din urmă are un alt sens decât originalul. Acest lucru este analog conceptului de programare a umbrelor variabile.
În al doilea rând, o transformare alfa nu este posibilă dacă ar avea ca rezultat capturarea de către o altă abstracție nepermanentă. De exemplu, dacă înlocuiți x cu y în λ x.λ y. x, atunci poți obțineλy.λy. u, care nu este deloc la fel.
În limbajele de programare cu domeniu static, conversia alfa poate fi utilizată pentru a simplifica rezoluția numelor. În același timp, având grijă ca conceptul de variabilă să nu mascheze desemnarea în zona care o conține.
În notația index De Bruyne, oricare doi termeni alfa echivalent sunt identici din punct de vedere sintactic.
Înlocuire
Modificările scrise de E [V:=R] sunt procesul de substituire a tuturor aparițiilor libere ale variabilei V în expresia E cu cifra de afaceri R. Substituția în termeni de λ este definită de lambda recursiei calcul asupra structurii conceptului după cum urmează (notați: x și y - numai variabile, iar M și N - orice expresie λ).
x [x:=N] ≡ N
y [x:=N] ≡ y dacă 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]) dacă x ≠ y, cu condiția ca y ∉ FV (N).
Pentru substituție într-o abstracție lambda, uneori este necesar să α-transformăm o expresie. De exemplu, nu este adevărat că (λ x. Y) [y:=x] are ca rezultat (λ x. X) deoarece x substituit ar fi trebuit să fie liber, dar a ajuns să fie legat. Înlocuirea corectă în acest caz este (λ z. X) până la α-echivalență. Rețineți că înlocuirea este definită în mod unic până la lambda.
β-reducere
Reducerea beta reflectă ideea de a aplica o funcție. Beta-reductiv este definit în termenisubstituție: ((X V. E) E ') este E [V:=E'].
De exemplu, presupunând o anumită codificare 2, 7, ×, există următoarea β-reducere: ((λ n. N × 2) 7) → 7 × 2.
Reducerea beta poate fi văzută ca fiind aceeași cu conceptul de reducebilitate locală în deducție naturală prin izomorfismul Curry-Howard.
η-transform
Această conversie exprimă ideea de extensialitate, care în acest context este că două funcții sunt egale atunci când dau același rezultat pentru toate argumentele. Această conversie se schimbă între λ x. (F x) și f ori de câte ori x nu pare liber în f.
Această acțiune poate fi considerată la fel ca și conceptul de completitudine locală în deducția naturală prin izomorfismul Curry-Howard.
Forme normale și fuziune
Pentru un calcul lambda netipizat, regula reducerii β nu este, în general, nici o normalizare puternică, nici slabă.
Cu toate acestea, se poate demonstra că β-reducerea se îmbină atunci când rulează înaintea transformării α (adică, două forme normale pot fi considerate egale dacă este posibilă o transformare α de la una la alta).
De aceea, atât termenii care se normalizează puternic, cât și cei care se ajustează slab au o singură formă normală. Pentru primii termeni, orice strategie de reducere este garantată să rezulte într-o configurație tipică. În timp ce pentru condiții de normalizare slabă, este posibil ca unele strategii de reducere să nu le găsească.
Metode suplimentare de programare
Există o mulțime de expresii de creație pentru calculul lambda. Multe dintre ele au fost dezvoltate inițial în contextul utilizării sistemelor ca bază pentru semantica unui limbaj de programare, aplicând efectiv ca un construct de nivel scăzut. Deoarece unele stiluri includ un calcul lambda (sau ceva foarte asemănător) ca fragment, aceste tehnici își găsesc, de asemenea, utilizare în creația practică, dar pot fi apoi percepute ca obscure sau străine.
Constante numite
În calculul lambda, o bibliotecă ia forma unui set de funcții definite anterior, în care termenii sunt doar constante concrete. Calculul pur nu are un concept de imuabil numit, deoarece toți termenii lambda atomici sunt variabile. Dar ele pot fi imitate și luând mutabilul ca nume al constantei, folosind o abstracție lambda pentru a lega acel volatil din corp și aplicând această abstracție la definiția dorită. Deci, dacă folosiți f pentru a reprezenta M în N, ați putea spune
(λ f. N) M.
Autorii introduc adesea un concept sintactic, cum ar fi let to permite ca lucrurile să fie scrise într-un mod mai intuitiv.
f=M la N
Prin înlănțuirea unor astfel de definiții, se poate scrie un „program” de calcul lambda ca zero sau mai multe definiții de funcție urmate de un singur membru lambda, folosind acele definiții care formează cea mai mare parte a programului.
O limitare notabilă a acestei litere este că numele f nu este definit în M,întrucât M este în afara domeniului obligatoriu al abstracției lambda f. Aceasta înseamnă că un atribut de funcție recursiv nu poate fi folosit ca M cu let. Sintaxa letrec mai avansată, care vă permite să scrieți definiții recursive de funcții în acest stil, folosește, în plus, combinatoare cu virgulă fixă.
Analogi tipăriți
Acest tip este un formalism tipizat care folosește un simbol pentru a reprezenta o abstractizare a funcției anonime. În acest context, tipurile sunt de obicei obiecte de natură sintactică care sunt atribuite termenilor lambda. Natura exactă depinde de calculul în cauză. Dintr-un anumit punct de vedere, LI tipizat poate fi considerat ca fiind rafinamente ale LI netipizate. Dar, pe de altă parte, ele pot fi considerate și o teorie mai fundamentală, iar calculul lambda netipizat este un caz special cu un singur tip.
Typed LI reprezintă baza limbajelor de programare și coloana vertebrală a limbajelor funcționale precum ML și Haskell. Și, mai indirect, stiluri imperative de creație. Calculii tip lambda joacă un rol important în dezvoltarea sistemelor de tip pentru limbaje de programare. Aici, tipabilitate captează de obicei proprietățile dorite ale programului, de exemplu, nu va provoca o încălcare a accesului la memorie.
Calculele lambda tipizate sunt strâns legate de logica matematică și teoria demonstrației prin izomorfismul Curry-Howard și pot fi considerate ca un limbaj intern al claselor de categorii, de exemplu, carepur și simplu este stilul închiderilor carteziene.
