El càlcul lambda és un sistema formal de lògica matemàtica per expressar càlculs basats en l'abstracció i aplicar funcions mitjançant la substitució d'enllaços i variables. Aquest és un model universal que es pot aplicar al disseny de qualsevol màquina de Turing. El càlcul lambda va ser introduït per primera vegada per Church, un famós matemàtic, a la dècada de 1930.
El sistema consisteix a construir membres lambda i realitzar-hi operacions de reducció.
Explicacions i aplicacions
La lletra grega lambda (λ) s'utilitza en expressions lambda i termes lambda per indicar l'enllaç d'una variable en una funció.
El càlcul lambda es pot escriure sense escriure o escriure. En la primera variant, les funcions només es poden utilitzar si són capaces de rebre dades d'aquest tipus. Els càlculs lambda escrits són més febles, poden expressar un valor més petit. Però, d' altra banda, et permeten demostrar més coses.
Un dels motius pels quals hi ha tants tipus diferents és el desig dels científics de fer més sense renunciar a l'oportunitat de demostrar teoremes de càlcul lambda forts.
El sistema té aplicacions en moltes àrees diferents de les matemàtiques, la filosofia, la lingüística i la informàtica. En primer lloc, el càlcul lambda és un càlcul que ha tingut un paper important en el desenvolupament de la teoria dels llenguatges de programació. Són els estils de creació funcional que implementen els sistemes. També són un tema candent de recerca en la teoria d'aquestes categories.
Per als maniquís
El càlcul lambda va ser introduït pel matemàtic Alonzo Church a la dècada de 1930 com a part de la seva investigació sobre els fonaments de la ciència. Es va demostrar que el sistema original era lògicament inconsistent l'any 1935, quan Stephen Kleen i J. B. Rosser van desenvolupar la paradoxa de Kleene-Rosser.
Més tard, l'any 1936, Church va destacar i va publicar només la part que és rellevant per als càlculs, el que ara s'anomena càlcul lambda no tipificat. El 1940 també va introduir una teoria més feble però lògicament coherent coneguda com el sistema de tipus primer. En el seu treball, explica tota la teoria en termes senzills, de manera que es pot dir que Church va publicar el càlcul lambda per a maniquís.
Fins als anys 60, quan va quedar clara la seva relació amb els llenguatges de programació, λ era només un formalisme. Gràcies a les aplicacions de Richard Montagu i d' altres lingüistes en la semàntica del llenguatge natural, el càlcul ha ocupat un lloc privilegiat tant en lingüística com en informàtica.
Origen del símbol
Lambda no significa cap paraula o acrònim, prové d'una referència a Principal Mathematics de Russell seguida de dos canvis tipogràfics. Exemple de notació: per a una funció f amb f (y)=2y + 1 és 2ŷ + 1. I aquí fem servir un cursor (“barret”) sobre y per etiquetar la variable d'entrada.
L'església originalment tenia la intenció d'utilitzar símbols similars, però els tipògrafs no van poder col·locar el símbol del "barret" a sobre de les lletres. Així, en canvi, el van imprimir originalment com a "/\y.2y+1". Al següent episodi d'edició, els mecanògrafs van substituir "/ \" per un caràcter visualment similar.
Introducció al càlcul lambda
El sistema consta d'un llenguatge de termes, que s'escullen mitjançant una determinada sintaxi formal, i un conjunt de regles de transformació que permeten manipular-los. L'últim punt es pot considerar com una teoria equacional o com una definició operacional.
Totes les funcions del càlcul lambda són anònimes, és a dir, no tenen nom. Només prenen una variable d'entrada i el curry s'utilitza per implementar gràfics amb múltiples variables.
termes Lambda
La sintaxi del càlcul defineix algunes expressions com a vàlides i altres com a no vàlides. Igual que diferents cadenes de caràcters són programes C vàlids i alguns no. L'expressió real del càlcul lambda s'anomena "terme lambda".
Les tres regles següents proporcionen una definició inductiva que pot seraplicar a la construcció de tots els conceptes sintàcticament vàlids:
La variable x en si és un terme lambda vàlid:
- si T és LT i x no és constant, aleshores (lambda xt) s'anomena abstracció.
- si tant T com s són conceptes, aleshores (TS) s'anomena aplicació.
Res més és un terme lambda. Així, un concepte és vàlid si i només si es pot obtenir mitjançant l'aplicació repetida d'aquestes tres regles. Tanmateix, es poden ometre alguns claudàtors segons altres criteris.
Definició
Les expressions lambda consisteixen en:
- variables v 1, v 2, …, v n, …
- símbols d'abstracció 'λ' i punt '.'
- parèntesis ().
El conjunt Λ es pot definir inductivament:
- Si x és una variable, aleshores x ∈ Λ;
- x no és constant i M ∈ Λ, aleshores (λx. M) ∈ Λ;
- M, N ∈ Λ, després (MN) ∈ Λ.
Designació
Per mantenir la notació de les expressions lambda ordenada, s'utilitzen habitualment les convencions següents:
- S'han omès els claudàtors exteriors: MN en lloc de (MN).
- S'assumeix que les aplicacions romanen associatives: es pot escriure MNP en comptes de ((MN) P).
- El cos de l'abstracció s'estén més a la dreta: λx. MN significa λx. (MN), no (λx. M) N.
- La seqüència d'abstraccions es redueix: λx.λy.λz. N pot ser λxyz. N.
Variables lliures i vinculades
L'operador λ connecta la seva no constant allà on sigui en el cos de l'abstracció. Les variables que entren en l'àmbit s'anomenen lligades. En l'expressió λ x. M, la part λ x sovint es coneix com a aglutinant. Com si insinués que les variables es converteixen en un grup amb l'addició de X x a M. Totes les altres inestables s'anomenen lliures.
Per exemple, en l'expressió λ y. x x y, y - lligat no permanent i x - lliure. I també val la pena assenyalar que la variable s'agrupa per la seva abstracció "més propera". A l'exemple següent, la solució del càlcul lambda es representa amb una única ocurrència de x, que està relacionada amb el segon terme:
λ x. y (λ x. z x)
El conjunt de variables lliures M es denota com a FV (M) i es defineix per recursivitat sobre l'estructura de termes de la següent manera:
- FV (x)={x}, on x és una variable.
- FV (λx. M)=FV (M) {x}.
- FV (MN)=FV (M) ∪ FV (N).
Una fórmula que no conté variables lliures s'anomena tancada. Les expressions lambda tancades també es coneixen com a combinadors i són equivalents a termes en lògica combinatòria.
Abreviatura
El significat de les expressions lambda ve determinat per com es poden escurçar.
Hi ha tres tipus de talls:
- α-transformació: canvi de variables lligades (alfa).
- β-reducció: aplicació de funcions als seus arguments (beta).
- η-transformació: cobreix la noció d'extensionalitat.
Aquí també el teniuestem parlant de les equivalències resultants: dues expressions són β-equivalents si es poden transformar en β en el mateix component, i l'equivalència α / η es defineix de manera similar.
El terme redex, abreviatura de rotació reduïble, fa referència a subtemes que es poden reduir amb una de les regles. Càlcul lambda per a maniquís, exemples:
(λ x. M) N és un redex beta en l'expressió per substituir N per x en M. El component al qual es redueix un redex s'anomena reductor. La reducció (λ x. M) N és M [x:=N].
Si x no és lliure a M, λ x. M x també em-REDEX amb regulador M.
α-transformació
Els canvis de nom Alpha us permeten canviar els noms de les variables lligades. Per exemple, x. x pot donar λ y. y. Es diu que els termes que només difereixen en la transformació alfa són α-equivalents. Sovint, quan s'utilitza el càlcul lambda, els equivalents α es consideren recíprocs.
Les regles exactes per a la conversió alfa no són del tot trivials. En primer lloc, amb aquesta abstracció, només es canvien de nom les variables que estan associades al mateix sistema. Per exemple, la transformada alfa λ x.λ x. x pot donar lloc a λ y.λ x. x, però això pot no conduir a λy.λx.y Aquest últim té un significat diferent de l'original. Això és anàleg al concepte de programació d'ombra variable.
En segon lloc, una transformació alfa no és possible si resultaria en ser capturada per una altra abstracció no permanent. Per exemple, si substituïu x per y en λ x.λ y. x, llavors pots obtenirλy.λy. u, que no és el mateix en absolut.
En llenguatges de programació amb abast estàtic, la conversió alfa es pot utilitzar per simplificar la resolució de noms. Al mateix temps, tenint cura que el concepte de variable no emmascara la designació a l'àrea que la conté.
En la notació d'índex de De Bruyne, dos termes alfa equivalents són sintàcticament idèntics.
Reemplaçament
Els canvis escrits per E [V:=R] són el procés de substitució de totes les ocurrències lliures de la variable V a l'expressió E amb la rotació R. La substitució en termes de λ es defineix pel lambda de la recursivitat càlcul sobre l'estructura del concepte de la següent manera (nota: x i y - només variables, i M i N - qualsevol expressió λ).
x [x:=N] ≡ N
y [x:=N] ≡ y si 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]) si x ≠ y, sempre que y ∉ FV (N).
Per a la substitució en una abstracció lambda, de vegades és necessari transformar α una expressió. Per exemple, no és cert que (λ x. Y) [y:=x] resulti en (λ x. X) perquè la x substituïda hauria d'haver estat lliure, però va acabar lligada. La substitució correcta en aquest cas és (λ z. X) fins a α-equivalència. Tingueu en compte que la substitució es defineix de manera única fins a lambda.
β-reducció
La reducció beta reflecteix la idea d'aplicar una funció. El beta-reductor es defineix en termessubstitució: ((X V. E) E ') és E [V:=E'].
Per exemple, suposant alguna codificació 2, 7, ×, hi ha la següent reducció β: ((λ n. N × 2) 7) → 7 × 2.
La reducció beta es pot veure com el mateix concepte de reductibilitat local sota deducció natural mitjançant l'isomorfisme de Curry-Howard.
η-transforma
Aquesta conversió expressa la idea d'extensionalitat, que en aquest context és que dues funcions són iguals quan donen el mateix resultat per a tots els arguments. Aquesta conversió s'intercanvia entre λ x. (F x) i f sempre que x no sembli lliure a f.
Aquesta acció es pot considerar el mateix que el concepte de completesa local en deducció natural mitjançant l'isomorfisme de Curry-Howard.
Formes normals i fusió
Per a un càlcul lambda no tipificat, la regla de reducció β no és generalment ni una normalització forta ni dèbil.
No obstant això, es pot demostrar que la reducció β es fusiona quan s'executa abans de la transformació α (és a dir, dues formes normals es poden considerar iguals si és possible una transformació α d'una a l' altra).
Per tant, tant els termes que es normalitzen fortament com els que s'ajusten feblement tenen una única forma normal. Per als primers termes, es garanteix que qualsevol estratègia de reducció donarà lloc a una configuració típica. Mentre que per a condicions de normalització feble, algunes estratègies de reducció poden no trobar-ho.
Mètodes de programació addicionals
Hi ha molts modismes de creació per al càlcul lambda. Molts d'ells es van desenvolupar originalment en el context d'utilitzar sistemes com a base per a la semàntica d'un llenguatge de programació, aplicant-los de manera efectiva com a constructe de baix nivell. Com que alguns estils inclouen un càlcul lambda (o alguna cosa molt semblant) com a fragment, aquestes tècniques també s'utilitzen en la creació pràctica, però després es poden percebre com a fosques o estranyes.
Constantes anomenades
En el càlcul lambda, una biblioteca pren la forma d'un conjunt de funcions definides prèviament, on els termes són només constants concretes. El càlcul pur no té cap concepte d'immutables anomenats ja que tots els termes lambda atòmics són variables. Però també es poden imitar prenent el mutable com el nom de la constant, utilitzant una abstracció lambda per unir aquest volàtil al cos i aplicant aquesta abstracció a la definició prevista. Per tant, si feu servir f per representar M en N, podríeu dir
(λ f. N) M.
Els autors sovint introdueixen un concepte sintàctic com ara deixar que s'escriguin les coses d'una manera més intuïtiva.
f=M a N
En encadenar aquestes definicions, es pot escriure un "programa" de càlcul lambda com a zero o més definicions de funció seguides d'un únic membre lambda, utilitzant les definicions que constitueixen la major part del programa.
Una limitació notable d'aquest let és que el nom f no està definit a M,ja que M està fora de l'àmbit d'unió de l'abstracció lambda f. Això significa que un atribut de funció recursiva no es pot utilitzar com a M amb let. La sintaxi de letrec més avançada, que us permet escriure definicions de funcions recursives en aquest estil, també utilitza combinadors de punt fix.
Anàlegs impresos
Aquest tipus és un formalisme mecanografiat que utilitza un símbol per representar una abstracció de funció anònima. En aquest context, els tipus solen ser objectes de naturalesa sintàctica que s'assignen a termes lambda. La naturalesa exacta depèn del càlcul en qüestió. Des d'un cert punt de vista, el LI mecanografiat es pot considerar com a perfeccionaments del LI no tipificat. Però, d' altra banda, també es poden considerar una teoria més fonamental, i el càlcul lambda no tipificat és un cas especial amb només un tipus.
Typed LI són la base dels llenguatges de programació i la columna vertebral de llenguatges funcionals com ML i Haskell. I, més indirectament, estils de creació imperatiu. Els càlculs lambda tipificats tenen un paper important en el desenvolupament de sistemes de tipus per a llenguatges de programació. Aquí, la tipabilitat generalment captura les propietats desitjades del programa, per exemple, no provocarà una violació d'accés a la memòria.
Els càlculs lambda tipificats estan estretament relacionats amb la lògica matemàtica i la teoria de la demostració a través de l'isomorfisme de Curry-Howard, i es poden considerar com un llenguatge intern de classes de categories, per exemple, quesimplement és l'estil dels tancaments cartesians.
