Lambda -kalkyl - Lambda calculus

Lambdakalkyl (även skrivet som λ-kalkyl ) är ett formellt system i matematisk logik för att uttrycka beräkning utifrån funktion abstraktion och tillämpning med användning av variabel bindning och substitution . Det är en universell beräkningsmodell som kan användas för att simulera vilken Turing -maskin som helst . Den introducerades av matematikern Alonzo Church på 1930 -talet som en del av hans forskning om matematikens grunder .

Lambda -kalkyl består av att konstruera lambda -termer och utföra reduktionsoperationer på dem. I den enklaste formen av lambda -beräkning är termer byggda med endast följande regler:

producerar uttryck som: (λ x .λ y . (λ z . (λ x . zx ) (λ y . zy )) ( xy )). Parenteser kan släppas om uttrycket är entydigt. För vissa applikationer kan termer för logiska och matematiska konstanter och operationer inkluderas.

Reduktionsverksamheten inkluderar:

Om De Bruijn-indexering används krävs ingen α-konvertering längre, eftersom det inte blir några namnkollisioner. Om upprepad tillämpning av reduceringsstegen så småningom upphör, kommer det enligt Church-Rosser-satsen att ge en β-normal form .

Variabelnamn behövs inte om man använder en universell lambda -funktion, till exempel Iota och Jot , som kan skapa vilket funktionsbeteende som helst genom att anropa det i sig själv i olika kombinationer.

Förklaring och tillämpningar

Lambda calculus är Turing komplett , det vill säga det är en universell beräkningsmodell som kan användas för att simulera vilken Turing -maskin som helst . Dess namne, den grekiska bokstaven lambda (λ), används i lambdauttryck och lambda -termer för att beteckna bindning av en variabel i en funktion .

Lambda -kalkyl kan vara otypad eller maskinskriven . I den typade lambda -kalkylen kan funktioner endast tillämpas om de kan acceptera den angivna ingångens "typ" av data. Typade lambda -beräkningar är svagare än den otypade lambda -kalkylen, som är huvudämnet för den här artikeln, i den meningen att maskinskrivna lambda -beräkningar kan uttrycka mindre än de oskrivade beräkningarna kan, men å andra sidan kan maskinskrivna lambda -beräkningar göra det möjligt att bevisa fler saker ; i den enkelt maskinskrivna lambda-beräkningen är det till exempel ett teorem som varje utvärderingsstrategi avslutar för varje enkelt maskinskrivet lambda-term, medan utvärdering av oskrivade lambda-termer inte behöver avslutas. En anledning till att det finns många olika typade lambda -beräkningar har varit önskan att göra mer (av vad den oskrivna kalkylen kan göra) utan att ge upp att kunna bevisa starka satser om kalkylen.

Lambda calculus har tillämpningar inom många olika områden inom matematik , filosofi , lingvistik och datavetenskap . Lambda calculus har spelat en viktig roll i utvecklingen av teorin om programmeringsspråk . Funktionella programmeringsspråk implementerar lambda -kalkyl. Lambda calculus är också ett aktuellt forskningsämne inom kategoriteori .

Historia

Lambda -kalkylen introducerades av matematikern Alonzo Church på 1930 -talet som en del av en undersökning av matematikens grunder . Det ursprungliga systemet visade sig vara logiskt inkonsekvent 1935 när Stephen Kleene och JB Rosser utvecklade Kleene – Rosser -paradoxen .

Därefter isolerade och publicerade kyrkan 1936 bara den del som är relevant för beräkning, det som nu kallas den oskrivna lambda -kalkylen. År 1940 introducerade han också ett beräkningsmässigt svagare, men logiskt konsekvent system, känt som den enkelt skrivna lambda -kalkylen .

Fram till 1960 -talet när dess relation till programmeringsspråk klargjordes var lambda -beräkningen bara en formalism. Tack vare Richard Montague och andra lingvisters tillämpningar inom naturligt språk semantik har lambda -kalkylen börjat njuta av en respektabel plats i både lingvistik och datavetenskap.

Lambda -symbolens ursprung

Det råder viss osäkerhet om anledningen till att Church använde den grekiska bokstaven lambda (λ) som beteckningen för funktionsabstraktion i lambda-kalkylen, kanske delvis på grund av motstridiga förklaringar av kyrkan själv. Enligt Cardone och Hindley (2006):

Förresten, varför valde kyrkan beteckningen "λ"? I [ett opublicerat brev från 1964 till Harald Dickson] uttalade han tydligt att det kom från notationen " " som används för klass-abstraktion av Whitehead och Russell , genom att först ändra " " till "∧ " för att skilja funktion-abstraktion från klass-abstraktion, och sedan ändra “∧” till “λ” för enkel utskrift. ${\ displaystyle {\ hatt {x}}}$${\ displaystyle {\ hatt {x}}}$${\ displaystyle x}$

Detta ursprung rapporterades också i [Rosser, 1984, s.338]. Å andra sidan sa kyrkan under hans senare år till två frågande att valet var mer av en slump: en symbol behövdes och λ råkade bara väljas ut.

Dana Scott har också tagit upp denna fråga i olika offentliga föreläsningar. Scott berättar att han en gång ställde en fråga om ursprunget till lambda-symbolen till kyrkans svärson John Addison, som sedan skrev sin svärfar ett vykort:

Kära professorskyrkan,

Russell hade jota -operatören , Hilbert hade epsilon -operatören . Varför valde du lambda för din operatör?

Enligt Scott bestod hela Churchs svar i att returnera vykortet med följande kommentar: " eeny, meeny, miny, moe ".

Informell beskrivning

Motivering

Beräkningsbara funktioner är ett grundläggande begrepp inom datavetenskap och matematik. Lambda -beräkningen ger en enkel semantik för beräkning, vilket gör det möjligt att formellt studera beräkningsegenskaper. Lambda -kalkylen innehåller två förenklingar som gör denna semantik enkel. Den första förenklingen är att lambda calculus behandlar funktioner "anonymt", utan att ge dem uttryckliga namn. Till exempel funktionen

${\ displaystyle \ operatorname {square \ _sum} (x, y) = x^{2}+y^{2}}$

kan skrivas om i anonym form som

${\ displaystyle (x, y) \ mapsto x^{2}+y^{2}}$

(som läses som "en tuppel av x och y är mappad till "). På samma sätt funktionen ${\ textstil x^{2}+y^{2}}$

${\ displaystyle \ operatorname {id} (x) = x}$

kan skrivas om i anonym form som

${\ displaystyle x \ mapsto x}$

där ingången helt enkelt mappas till sig själv.

Den andra förenklingen är att lambda -beräkningen endast använder funktioner för en enda ingång. En vanlig funktion som kräver två ingångar, till exempel funktionen, kan omarbetas till en motsvarande funktion som accepterar en enda ingång, och när utgången returnerar en annan funktion, som i sin tur accepterar en enda ingång. Till exempel, ${\ textstyle \ operatorname {square \ _sum}}$

${\ displaystyle (x, y) \ mapsto x^{2}+y^{2}}$

kan omarbetas till

${\ displaystyle x \ mapsto (y \ mapsto x^{2}+y^{2})}$

Denna metod, känd som currying , omvandlar en funktion som tar flera argument till en funktionskedja med ett enda argument.

Funktionens tillämpning av funktionen på argumenten (5, 2) ger direkt ${\ textstyle \ operatorname {square \ _sum}}$

${\ textstil ((x, y) \ mapsto x^{2}+y^{2}) (5,2)}$

${\ textstyle = 5^{2}+2^{2}}$

${\ textstyle = 29}$,

utvärdering av den curried version kräver ytterligare ett steg

${\ textstil {\ Bigl (} {\ bigl (} x \ mapsto (y \ mapsto x^{2}+y^{2}) {\ bigr)} (5) {\ Bigr)} (2)}$

${\ textstyle = (y \ mapsto 5^{2}+y^{2}) (2)}$// definitionen av har använts med i det inre uttrycket. Detta är som β-reduktion.${\ displaystyle x}$${\ displaystyle 5}$

${\ textstyle = 5^{2}+2^{2}}$// definitionen av har använts med . Återigen, liknande p-reduktion.${\ displaystyle y}$${\ displaystyle 2}$

${\ textstyle = 29}$

att komma fram till samma resultat.

Lambda -kalkylen

Lambda -kalkylen består av ett språk för lambda -termer , som definieras av en viss formell syntax, och en uppsättning transformationsregler, som tillåter manipulation av lambda -termerna. Dessa omvandlingsregler kan ses som en ekvationsteori eller som en operativ definition .

Som beskrivits ovan är alla funktioner i lambda -kalkylen anonyma funktioner utan namn. De accepterar bara en ingångsvariabel, med currying som används för att implementera funktioner med flera variabler.

Lambda -termer

Syntaxen för lambda -beräkningen definierar vissa uttryck som giltiga lambda -beräkningsuttryck och vissa som ogiltiga, precis som vissa teckensträngar är giltiga C -program och vissa inte. Ett giltigt lambda -beräkningsuttryck kallas en "lambda -term".

Följande tre regler ger en induktiv definition som kan tillämpas för att bygga alla syntaktiskt giltiga lambda -termer:

• en variabel,, är i sig en giltig lambda -term${\ displaystyle x}$
• om är en lambda -term och är en variabel, då (ibland skriven i ASCII som ) är en lambda -term (kallas en abstraktion );${\ displaystyle t}$${\ displaystyle x}$${\ displaystyle (\ lambda xt)}$${\ displaystyle ({\ text {L}} xt)}$
• om och är lambda -termer, så är det en lambda -term (kallas en applikation ).${\ displaystyle t}$${\ displaystyle s}$${\ displaystyle (ts)}$

Inget annat är en lambda -term. Således är en lambda -term giltig om och bara om den kan erhållas genom upprepad tillämpning av dessa tre regler. Vissa parenteser kan dock utelämnas enligt vissa regler. Till exempel brukar de yttersta parenteserna inte skrivas. Se Notation nedan.

En abstraktion är en definition av en anonym funktion som kan ta en enda ingång och ersätta den med uttrycket . Den definierar således en anonym funktion som tar och returnerar . Till exempel är en abstraktion för funktionen som använder termen för . Definitionen av en funktion med en abstraktion "ställer bara upp" funktionen men åberopar den inte. Abstraktionen binder variabeln i termen . ${\ displaystyle \ lambda xt}$${\ displaystyle x}$${\ displaystyle t}$${\ displaystyle x}$${\ displaystyle t}$${\ displaystyle \ lambda xx^{2} +2}$${\ displaystyle f (x) = x^{2} +2}$${\ displaystyle x^{2} +2}$${\ displaystyle t}$${\ displaystyle x}$${\ displaystyle t}$

En applikation representerar tillämpningen av en funktion på en ingång , det vill säga den representerar funktionen att ringa funktion på ingång för att producera . ${\ displaystyle ts}$${\ displaystyle t}$${\ displaystyle s}$${\ displaystyle t}$${\ displaystyle s}$${\ displaystyle t (s)}$

Det finns inget begrepp i lambda -kalkylen om variabel deklaration. I en definition som (dvs. ) behandlar lambda -kalkylen som en variabel som ännu inte är definierad. Abstraktionen är syntaktiskt giltig och representerar en funktion som lägger sin input till det ännu okända . ${\ displaystyle \ lambda x.x+y}$${\ displaystyle f (x) = x+y}$${\ displaystyle y}$${\ displaystyle \ lambda x.x+y}$${\ displaystyle y}$

Bracketing kan användas och kan behövas för att tydliggöra villkor. Till exempel och beteckna olika termer (även om de av misstag minskar till samma värde). Här definierar det första exemplet en funktion vars lambda -term är resultatet av applicering av x på barnfunktionen, medan det andra exemplet är tillämpningen av den yttersta funktionen på ingången x, som returnerar barnfunktionen. Därför utvärderar båda exemplen identitetsfunktionen . ${\ displaystyle \ lambda x. ((\ lambda xx) x)}$${\ displaystyle (\ lambda x. (\ lambda xx)) x}$ ${\ displaystyle \ lambda xx}$

Funktioner som fungerar på funktioner

I lambda -kalkyl anses funktioner vara " förstklassiga värden ", så funktioner kan användas som ingångar eller returneras som utdata från andra funktioner.

Till exempel representerar identitetsfunktionen , och representerar den identitetsfunktion som tillämpas på . Vidare representerar den konstanta funktionen , funktionen som alltid returnerar , oavsett ingång. I lambda-kalkyl betraktas funktionsapplikation som vänsterassociativ , så det betyder . ${\ displaystyle \ lambda xx}$${\ displaystyle x \ mapsto x}$${\ displaystyle (\ lambda xx) y}$${\ displaystyle y}$${\ displaystyle (\ lambda xy)}$ ${\ displaystyle x \ mapsto y}$${\ displaystyle y}$${\ displaystyle stx}$${\ displaystyle (st) x}$

Det finns flera begrepp om "ekvivalens" och "reduktion" som gör att lambda -termer kan "reduceras" till "ekvivalenta" lambda -termer.

Alfa ekvivalens

En grundläggande form av ekvivalens, definierbar på lambda -termer, är alfaekvivalens. Det fångar intuitionen att det särskilda valet av en bunden variabel, i en abstraktion, inte (vanligtvis) spelar någon roll. Till exempel och är alfaekvivalenta lambda-termer, och de representerar båda samma funktion (identitetsfunktionen). Termerna och är inte alfa-ekvivalenta, eftersom de inte är bundna i en abstraktion. I många presentationer är det vanligt att identifiera alfa-ekvivalenta lambda-termer. ${\ displaystyle \ lambda xx}$${\ displaystyle \ lambda åå}$${\ displaystyle x}$${\ displaystyle y}$

Följande definitioner är nödvändiga för att kunna definiera β-reduktion:

Gratis variabler

De fria variablerna för en term är de variabler som inte är bundna av en abstraktion. Uppsättningen av fria variabler för ett uttryck definieras induktivt:

• De fria variablerna är bara${\ displaystyle x}$${\ displaystyle x}$
• Uppsättningen fria variabler av är uppsättningen fria variabler av , men med borttagna${\ displaystyle \ lambda xt}$${\ displaystyle t}$${\ displaystyle x}$
• Uppsättningen fria variabler av är föreningen av uppsättningen fria variabler av och uppsättningen fria variabler av .${\ displaystyle ts}$${\ displaystyle t}$${\ displaystyle s}$

Till exempel lambda term som representerar identiteten har inga fria variabler, men funktionen har en enda fri variabel . ${\ displaystyle \ lambda xx}$${\ displaystyle \ lambda x.yx}$${\ displaystyle y}$

Ersättningsundvikande byten

Antag , och är lambda -termer och och är variabler. Beteckningen indikerar substitution av för i i en capture-undvikande sätt. Detta definieras så att: ${\ displaystyle t}$${\ displaystyle s}$${\ displaystyle r}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle t [x: = r]}$${\ displaystyle r}$${\ displaystyle x}$${\ displaystyle t}$

• ${\ displaystyle x [x: = r] = r}$;
• ${\ displaystyle y [x: = r] = y}$om ;${\ displaystyle x \ neq y}$
• ${\ displaystyle (ts) [x: = r] = (t [x: = r]) (s [x: = r])}$;
• ${\ displaystyle (\ lambda xt) [x: = r] = \ lambda xt}$;
• ${\ displaystyle (\ lambda yt) [x: = r] = \ lambda y. (t [x: = r])}$om och inte är i de fria variablerna av . Variabeln sägs vara "färsk" för .${\ displaystyle x \ neq y}$${\ displaystyle y}$${\ displaystyle r}$${\ displaystyle y}$${\ displaystyle r}$

Till exempel , och . ${\ displaystyle (\ lambda xx) [y: = y] = \ lambda x. (x [y: = y]) = \ lambda xx}$${\ displaystyle ((\ lambda xy) x) [x: = y] = ((\ lambda xy) [x: = y]) (x [x: = y]) = (\ lambda xy) y}$

Friskhetstillståndet (kräver att det inte finns i de fria variablerna av ) är avgörande för att säkerställa att substitution inte ändrar betydelsen av funktioner. Till exempel är en substitution görs som ignorerar färskhet villkor: . Denna substitution förvandlar den konstanta funktionen till identiteten genom substitution. ${\ displaystyle y}$${\ displaystyle r}$${\ displaystyle (\ lambda xy) [y: = x] = \ lambda x. (y [y: = x]) = \ lambda xx}$${\ displaystyle \ lambda xy}$${\ displaystyle \ lambda xx}$

I allmänhet kan underlåtenhet att uppfylla friskhetstillståndet åtgärdas genom alfa-namnbyte med en lämplig färsk variabel. Till exempel kan man byta tillbaka till vår korrekta uppfattning om substitution, i abstraktionen byta namn med en ny variabel , för att erhålla , och betydelsen av funktionen bevaras genom substitution. ${\ displaystyle (\ lambda xy) [y: = x]}$${\ displaystyle z}$${\ displaystyle (\ lambda zy) [y: = x] = \ lambda z. (y [y: = x]) = \ lambda zx}$

β-reduktion

P-reduktionsregeln säger att en tillämpning av formuläret reduceras till termen . Notationen används för att indikera att β-reduceras till . Till exempel för varje , . Detta visar att det verkligen är identiteten. På samma sätt, vilket visar att det är en konstant funktion. ${\ displaystyle (\ lambda xt) s}$${\ displaystyle t [x: = s]}$${\ displaystyle (\ lambda xt) s \ to t [x: = s]}$${\ displaystyle (\ lambda xt) s}$${\ displaystyle t [x: = s]}$${\ displaystyle s}$${\ displaystyle (\ lambda xx) s \ till x [x: = s] = s}$${\ displaystyle \ lambda xx}$${\ displaystyle (\ lambda xy) s \ till y [x: = s] = y}$${\ displaystyle \ lambda xy}$

Lambda -kalkylen kan ses som en idealiserad version av ett funktionellt programmeringsspråk, som Haskell eller Standard ML . Enligt denna uppfattning motsvarar β-reduktion ett beräkningssteg. Detta steg kan upprepas med ytterligare β-reduktioner tills det inte finns fler applikationer kvar att minska. I den otecknade lambda -kalkylen, som presenteras här, kan denna reduceringsprocess inte avslutas. Tänk till exempel på termen . Här . Det vill säga att termen reducerar sig själv i en enda β-reduktion, och därför kommer reduktionsprocessen aldrig att avslutas. ${\ displaystyle \ Omega = (\ lambda x.xx) (\ lambda x.xx)}$${\ displaystyle (\ lambda x.xx) (\ lambda x.xx) \ to (xx) [x: = \ lambda x.xx] = (x [x: = \ lambda x.xx]) (x [x : = \ lambda x.xx]) = (\ lambda x.xx) (\ lambda x.xx)}$

En annan aspekt av den otypade lambda -kalkylen är att den inte skiljer mellan olika typer av data. Till exempel kan det vara önskvärt att skriva en funktion som bara fungerar på tal. Men i den oskrivna lambda-kalkylen finns det inget sätt att förhindra att en funktion appliceras på sanningvärden , strängar eller andra icke-nummerobjekt.

Formell definition

Definition

Lambda -uttryck består av:

• variabler v ₁ , v ₂ , ...;
• abstraktionssymbolerna λ (lambda) och. (punkt);
• parentes ().

Uppsättningen lambdauttryck, Λ , kan definieras induktivt :

1. Om x är en variabel, då x ∈ Λ.
2. Om x är en variabel och M ∈ Λ, då (λ x . M ) ∈ Λ.
3. Om M , N ∈ Λ, sedan ( MN ) ∈ Λ.

Instanser av regel 2 är kända som abstraktioner och instanser av regel 3 är kända som applikationer .

Notation

För att hålla noteringen av lambda -uttryck oroliga tillämpas vanligtvis följande konventioner:

• De yttersta parenteserna tappas: M N istället för ( M N ).
• Ansökningar antas lämnas associerade: M N P kan skrivas istället för (( M N ) P ).
• Abstraktionens kropp sträcker sig så långt till höger som möjligt : λ x . MN betyder λ x . ( MN ) och inte (λ x . M ) N .
• En sekvens av abstraktioner dras ihop: λ x .λ y .λ z . N förkortas som λ xyz . N .

Fria och bundna variabler

Abstraktionsoperatören, λ, sägs binda sin variabel varhelst den förekommer i abstraktionens kropp. Variabler som faller inom ramen för en abstraktion sägs vara bundna . I ett uttryck λ x . M , den del λ x kallas ofta bindemedel , som en antydan att variabeln x är att få bunden genom att lägga λ x till M . Alla andra variabler kallas gratis . Till exempel i uttrycket λ y . xxy , y är en bunden variabel och x är en ledig variabel. Även en variabel är bunden av sin närmaste abstraktion. I följande exempel är den enda förekomsten av x i uttrycket bunden av den andra lambda: λ x . y (λ x . zx ).

Uppsättningen av fria variabler för ett lambda -uttryck, M , betecknas som FV ( M ) och definieras genom rekursion på termernas struktur, enligt följande:

1. FV ( x ) = { x }, där x är en variabel.
2. FV (λ x . M ) = FV ( M ) \ { x }.
3. FV ( MN ) = FV ( M ) ∪ FV ( N ).

Ett uttryck som inte innehåller några fria variabler sägs vara stängt . Stängda lambdauttryck är också kända som kombinatorer och motsvarar termer i kombinatorisk logik .

Minskning

Betydelsen av lambda uttryck definieras av hur uttryck kan reduceras.

Det finns tre typer av minskning:

• α-omvandling : ändring av bundna variabler;
• β-reduktion : tillämpa funktioner på sina argument;
• η-reduktion : som fångar en föreställning om extensionalitet.

Vi talar också om de resulterande ekvivalenserna: två uttryck är α-ekvivalenta , om de kan α-konverteras till samma uttryck. β-ekvivalens och η-ekvivalens definieras på samma sätt.

Termen redex , förkortning för reducerbart uttryck , avser subtermer som kan reduceras med en av reduceringsreglerna. Till exempel, (λ x . M ) N är en β-redex uttrycka substitution av N för x i M . Uttrycket till vilket en redex minskar kallas dess redukt ; reduktionen av (λ x . M ) N är M [ x  : = N ].

Om x inte är fritt i M , λ x . M x är också en η-redex, med en reduct av M .

α-omvandling

α-omvandling, ibland känd som α-omdöpning, gör att bundna variabelnamn kan ändras. Till exempel α-omvandling av λ x . x kan ge λ y . y . Termer som endast skiljer sig genom α-konvertering kallas α-ekvivalent . Ofta anses α-ekvivalenta termer vid användning av lambda calculus vara ekvivalenta.

De exakta reglerna för α-konvertering är inte helt triviala. För det första, när α-konverterar en abstraktion, är de enda variabla förekomster som byter namn de som är bundna till samma abstraktion. Till exempel en a-omvandling av X x. X x . x kan resultera i λ y .λ x . x , men det kunde inte resultera i λ y .λ x . y . Den senare har en annan betydelse än originalet. Detta är analogt med programmeringsbegreppet variabel skuggning .

För det andra är α-konvertering inte möjlig om det skulle resultera i att en variabel fångas upp av en annan abstraktion. Till exempel, om vi ersätter x med y i λ x .λ y . x får vi λ y .λ y . y , vilket inte alls är detsamma.

På programmeringsspråk med statiskt omfång kan α-konvertering användas för att göra namnupplösning enklare genom att se till att inget variabelnamn maskerar ett namn i ett innehållande omfång (se α-byta namn för att göra namnupplösning trivial ).

I De Bruijn- indexnotationen är två α-ekvivalenta termer syntaktiskt identiska.

Utbyte

Substitution skrivna M [ V  : = N ], är processen att ersätta alla fria förekomster av den variabla V i uttrycket M med uttrycket N . Substitution på termer i lambda -beräkningen definieras av rekursion på termernas struktur, enligt följande (notera: x och y är bara variabler medan M och N är något lambda -uttryck):

x [ x  : = N ] = N

y [ x  : = N ] = y , om x ≠ y

( M ₁ M ₂ ) [ x  : = N ] = ( M ₁ [ x  : = N ]) ( M ₂ [ x  : = N ])

(λ x . M ) [ x  : = N ] = λ x . M

(λ y . M ) [ x  : = N ] = λ y . ( M [ x  : = N ]), om x ≠ y och y ∉ FV ( N )

För att ersätta en abstraktion är det ibland nödvändigt att a-konvertera uttrycket. Till exempel är det inte korrekt att (λ x . Y ) [ y  : = x ] resulterar i λ x . x , eftersom det ersatta xet var tänkt att vara fritt men slutade vara bundet. Den korrekta substitutionen i detta fall är λ z . x , upp till α-ekvivalens. Substitution definieras unikt upp till α-ekvivalens.

β-reduktion

β-reduktion fångar idén om funktionsapplikation. β-reduktion definieras i termer av substitution: den β-reduktion av (λ V . M ) N är M [ V  : = N ].

Om vi ​​till exempel antar en viss kodning av 2, 7, ×, har vi följande β-reduktion: (λ n . N × 2) 7 → 7 × 2.

β-reduktion kan ses vara densamma som begreppet lokal reducerbarhet i naturligt avdrag , via Curry-Howard-isomorfismen .

η-reduktion

η-reduktion uttrycker tanken på extensionalitet , vilket i detta sammanhang är att två funktioner är samma om och bara om de ger samma resultat för alla argument. η-reduktion konverterar mellan λ x . f x och f när x inte visas ledigt i f .

η-reduktion kan ses vara densamma som begreppet lokal fullständighet i naturligt avdrag , via Curry-Howard-isomorfismen .

Normala former och sammanflöde

För den oskrivna lambda-kalkylen är β-reduktion som omskrivningsregel varken starkt normaliserande eller svagt normaliserande .

Det kan dock visas att β-reduktion är konfluent när man arbetar upp till α-omvandling (dvs vi anser att två normala former är lika om det är möjligt att α-omvandla den ena till den andra).

Därför har både starkt normaliserande termer och svagt normaliserande termer en unik normal form. För starkt normaliserande termer garanteras varje reduceringsstrategi den normala formen, medan för svagt normaliserande termer kan vissa reduktionsstrategier misslyckas med att hitta den.

Kodning av datatyper

Den grundläggande lambda-kalkylen kan användas för att modellera booleaner, aritmetik , datastrukturer och rekursion, såsom illustreras i följande underavsnitt.

Aritmetik i lambda -kalkyl

Det finns flera möjliga sätt att definiera de naturliga siffrorna i lambda -kalkylen, men de vanligaste är kyrkans siffror , som kan definieras enligt följande:

0: = λ f .λ x . x

1: = λ f .λ x . f x

2: = λ f .λ x . f ( f x )

3: = λ f .λ x . f ( f ( f x ))

och så vidare. Eller använda den alternativa syntaxen som presenteras ovan i Notation :

0: = λ fx . x

1: = λ fx . f x

2: = λ fx . f ( f x )

3: = λ fx . f ( f ( f x ))

En kyrkosiffra är en funktion av högre ordning-den tar en enda argumentfunktion f och returnerar en annan enda-argument-funktion. Kyrksiffran n är en funktion som tar en funktion f som argument och returnerar den n: e kompositionen av f , det vill säga funktionen f komponerad med sig själv n gånger. Detta betecknas f ^{( n )} och är i själva verket n: s kraft av f (betraktas som en operatör); f ⁽⁰⁾ definieras som identitetsfunktionen. Sådana upprepade kompositioner (av en enda funktion f ) följer exponentlagarna , varför dessa siffror kan användas för aritmetik. (I kyrkans ursprungliga lambda -beräkning krävdes att den formella parametern för ett lambdauttryck förekom minst en gång i funktionskroppen, vilket gjorde ovanstående definition av 0 omöjlig.)

Ett sätt att tänka på kyrkans siffra n , som ofta är användbar vid analys av program, är som en instruktion 'upprepa n gånger'. Till exempel, med hjälp av PAIR- och NIL -funktionerna som definieras nedan, kan man definiera en funktion som konstruerar en (länkad) lista med n -element som alla är lika med x genom att upprepa 'förbered ett annat x -element' n gånger, utgående från en tom lista. Lambda -termen är

λ n .λ x . n (PAIR x ) NIL

Genom att variera vad som upprepas och variera vilket argument som funktionen som upprepas tillämpas på kan många olika effekter uppnås.

Vi kan definiera en efterföljande funktion, som tar en kyrkans siffra n och returnerar n + 1 genom att lägga till en annan tillämpning av f , där '(mf) x' betyder att funktionen 'f' tillämpas 'm' gånger på 'x':

SUCC: = λ n .λ f .λ x . f ( n f x )

Eftersom m -th -kompositionen av f komponerad med n -th -kompositionen av f ger m + n -th -kompositionen av f , kan addition definieras enligt följande:

PLUS: = λ m .λ n .λ f .λ x . m f ( n f x )

PLUS kan ses som en funktion som tar två naturliga tal som argument och returnerar ett naturligt tal; det kan verifieras att

PLUS 2 3

och

5

är β-ekvivalenta lambdauttryck. Eftersom man kan lägga till m till ett nummer n genom att lägga till 1 m gånger, är en alternativ definition:

PLUS: = λ m .λ n . m SUCC n 

På samma sätt kan multiplikation definieras som

MULT: = λ m .λ n .λ f . m ( n f )

Alternativt

MULT: = λ m .λ n . m (PLUS n ) 0

eftersom multiplicering av m och n är detsamma som att upprepa funktionen add n m gånger och sedan tillämpa den till noll. Exponentiering har en ganska enkel återgivning i kyrkliga siffror, nämligen

POW: = λ b .λ e . e b

Föregångarfunktionen definierad av PRED n = n - 1 för ett positivt heltal n och PRED 0 = 0 är betydligt svårare. Formeln

PRED: = λ n .λ f .λ x . n (λ g .λ h . h ( g f )) (λ u . x ) (λ u . u )

kan valideras genom att visa induktivt att om T betecknar (λ g .λ h . h ( g f )) , då T ^{( n )} (λ u . x ) = (λ h . h ( f ^{( n −1)} ( x ))) för n > 0 . Två andra definitioner av PRED ges nedan, en med villkor och den andra med par . Med föregångarfunktionen är subtraktion enkelt. Definiera

SUB: = λ m .λ n . n PRED m ,

SUB m n ger m - n när m > n och 0 annars.

Logik och predikat

Enligt konvention används följande två definitioner (kända som kyrkliga booleaner) för de booleska värdena SANT och FALSKT :

SANT: = λ x .λ y . x

FALSKT: = λ x .λ y . y

(Observera att FALSE är ekvivalent med kyrkans siffror noll definierad ovan)

Sedan kan vi med dessa två lambda -termer definiera några logiska operatorer (det här är bara möjliga formuleringar; andra uttryck är lika korrekta):

OCH: = λ p .λ q . p q p

ELLER: = λ p .λ q . p p q

INTE: = λ s . p FALSKT SANT

IFTHENELSE: = λ p .λ a .λ b . p a b

Vi kan nu beräkna några logiska funktioner, till exempel:

OCH SANT FALSKT

≡ (λ p .λ q . P q p ) TRUE FALSE → _β TRUE FALSE TRUE

≡ (λ x .λ y . X ) FALSE TRUE → _β FALSE

och vi ser att AND TRUE FALSE motsvarar FALSE .

Ett predikat är en funktion som returnerar ett booleskt värde. Det mest grundläggande predikatet är ISZERO , som returnerar SANT om dess argument är kyrkans siffra 0 och FALSKT om dess argument är någon annan kyrkans siffra:

ISZERO: = λ n . n (λ x .FALSE) SANT

Följande predikat testar om det första argumentet är mindre än eller lika med det andra:

LEQ: = λ m .λ n. ISZERO (SUB m n ) ,

och eftersom m = n , om LEQ m n och LEQ n m , är det enkelt att bygga ett predikat för numerisk jämlikhet.

Tillgängligheten av predikat och ovanstående definition av SANT och FALSK gör det bekvämt att skriva "if-then-else" -uttryck i lambda-kalkyl. Till exempel kan föregångarfunktionen definieras som:

PRED: = λ n . n (λ g .λ k. ISZERO ( g 1) k (PLUS ( g k ) 1)) (λ v .0) 0

som kan verifieras genom att induktivt visa att n (λ g .λ k. ISZERO ( g 1) k (PLUS ( g k ) 1)) (λ v .0) är add n - 1 -funktionen för n > 0.

Par

Ett par (2-tupel) kan definieras i termer av SANT och FALSKT , genom att använda kyrkans kodning för par . Till exempel inkapslar PAIR paret ( x , y ), FIRST returnerar det första elementet i paret och SECOND returnerar det andra.

PAAR: = λ x .λ y .λ f . f x y

FÖRSTA: = λ s . p SANT

ANDRA: = λ s . p FALSKT

NIL: = λ x. SANT

NULL: = λ s . p (λ x .λ y. FALSE)

En länkad lista kan definieras som antingen NIL för den tomma listan eller PAIR för ett element och en mindre lista. Predikatet NULL testar värdet NIL . (Alternativt, med NIL: = FALSE , undanröjer konstruktionen l (λ h .λ t .λ z .deal_with_head_ h _and_tail_ t ) (deal_with_nil) behovet av ett explicit NULL -test).

Som ett exempel på användning av par kan den skift-och-stegningsfunktion som kartlägger ( m , n ) till ( n , n + 1) definieras som

Φ: = λ x. PAIR (SECOND x ) (SUCC (SECOND x ))

vilket gör att vi kan ge den kanske mest transparenta versionen av föregångarfunktionen:

PRED: = λ n. FIRST ( n Φ (PAIR 0 0)).

Ytterligare programmeringsteknik

Det finns en stor mängd programmeringsidiom för lambda -kalkyl. Många av dessa utvecklades ursprungligen i samband med att man använde lambda calculus som grund för programmeringsspråksemantik , effektivt använder lambda calculus som ett programmeringsspråk på låg nivå . Eftersom flera programmeringsspråk inkluderar lambda -kalkylen (eller något mycket liknande) som ett fragment, ser dessa tekniker också användning i praktisk programmering, men kan då uppfattas som dunkla eller främmande.

Namngivna konstanter

I lambda-kalkyl skulle ett bibliotek ha formen av en samling av tidigare definierade funktioner, som som lambda-termer bara är särskilda konstanter. Den rena lambda-kalkylen har inte ett koncept med namngivna konstanter eftersom alla atomiska lambda-termer är variabler, men man kan efterlikna att ha namngivna konstanter genom att avsätta en variabel som namnet på konstanten, med hjälp av abstraktion för att binda variabeln i huvudkroppen , och tillämpa denna abstraktion på den avsedda definitionen. Således att använda f för att betyda M (någon uttrycklig lambda-term) i N (en annan lambda-term, "huvudprogrammet"), kan man säga

(λ f . N ) M

Författare introducerar ofta syntaktiskt socker , till exempel låt , för att tillåta att skriva ovan i den mer intuitiva ordningen

låt f = M i N

Genom att kedja sådana definitioner kan man skriva ett lambda-kalkyl "program" som noll eller flera funktionsdefinitioner, följt av en lambda-term som använder de funktioner som utgör programmets huvuddel.

En anmärkningsvärd begränsning av denna låt är att namnet f inte definieras i M , eftersom M ligger utanför omfattningen av abstraktionsbindningen f ; detta betyder att en rekursiv funktionsdefinition inte kan användas som M med låt . Den mer avancerade letrec- syntaktiska sockerkonstruktionen som gör det möjligt att skriva rekursiva funktionsdefinitioner i den naiva stilen i stället använder dessutom fasta punktkombinatorer.

Rekursion och fasta punkter

Rekursion är definitionen av en funktion som använder själva funktionen. Lambda -kalkylen kan inte uttrycka detta så direkt som vissa andra anteckningar: alla funktioner är anonyma i lambda -kalkylen, så vi kan inte hänvisa till ett värde som ännu inte har definierats, inom lambda -termen som definierar samma värde. Emellertid kan rekursion fortfarande uppnås genom att arrangera för en lambda-uttryck för att ta emot sig själv som sitt argument värde, exempelvis i  (λ x . X x ) E .

Betrakta faktoriell funktionen F ( n ) rekursivt definieras av

F ( n ) = 1, om n = 0; annars n × F ( n - 1) .

I lambda -uttrycket som ska representera denna funktion kommer en parameter (vanligtvis den första) att antas ta emot lambda -uttrycket själv som dess värde, så att det att kalla det - tillämpa det på ett argument - kommer att utgöra rekursion. För att uppnå rekursion måste det avsedda-som-själv-refererande argumentet (kallas r här) alltid skickas till sig själv inom funktionskroppen, vid en call point:

G: = λ r . λ n . (1, om n = 0; annars n × ( r r ( n −1)))

med  r r x = F x = G r x  att hålla, så  {{{1}}}  och

F: = GG = (λ x . X x ) G

Självapplikationen uppnår replikering här och skickar funktionens lambda-uttryck vidare till nästa anrop som ett argumentvärde, vilket gör det tillgängligt för att refereras och kallas dit.

Detta löser det men kräver omskrivning av varje rekursivt samtal som självapplikation. Vi skulle vilja ha en generisk lösning utan att behöva skriva om:

G: = λ r . λ n . (1, om n = 0; annars n × ( r ( n −1)))

med  r x = F x = G r x  att hålla, så  r = G r =: FIX G  och

F: = FIX G  där  FIX g  : = ( r där r = g r ) = g (FIX g )

så att  FIX G = G (FIX G) = (λ n . (1, om n = 0; annars n × ((FIX G) ( n −1))))

Med tanke på en lambda-term med första argument som representerar rekursivt samtal (t.ex. G här), kommer fixpunkts- kombinatorn FIX att returnera ett självreplikerande lambda-uttryck som representerar den rekursiva funktionen (här, F ). Funktionen behöver inte uttryckligen vidarebefordras till sig själv, för självreplikationen ordnas i förväg, när den skapas, för att göras varje gång den anropas. Således återskapas det ursprungliga lambdauttrycket (FIX G) inuti sig själv, vid call-point, för att uppnå självreferens .

Faktum är att det finns många möjliga definitioner för denna FIX -operatör, den enklaste av dem är:

Y  : = λ g . (Λ x . G ( x x )) (λ x . G ( x x ))

I lambda-beräkningen är Y g   en fast punkt för g , eftersom den expanderar till:

Y g

(λ h . (λ x . h ( x x )) (λ x . h ( x x ))) g

(λ x . g ( x x )) (λ x . g ( x x ))

g ((λ x . g ( x x )) (λ x . g ( x x )))

g ( Y g )

Nu, för att utföra vårt rekursiva samtal till faktorfunktionen, skulle vi helt enkelt ringa ( Y G) n , där n är det tal som vi beräknar fabriken för. Med tanke på n = 4 ger detta till exempel:

( Y G) 4

G ( Y G) 4

(λ r .λ n . (1, om n = 0; annars n × ( r ( n −1)))) ( Y G) 4

(λ n . (1, om n = 0; annars n × (( Y G) ( n −1)))) 4

1, om 4 = 0; annars 4 × (( Y G) (4−1))

4 × (G ( Y G) (4−1))

4 × ((λ n . (1, om n = 0; annars n × (( Y G) ( n −1)))) (4−1))

4 × (1, om 3 = 0; annars 3 × (( Y G) (3−1)))

4 × (3 × (G ( Y G) (3−1))))

4 × (3 × ((λ n . (1, om n = 0; annars n × (( Y G) ( n −1)))) (3−1)))

4 × (3 × (1, om 2 = 0; annars 2 × (( Y G) (2−1))))

4 × (3 × (2 × (G ( Y G) (2−1))))

4 × (3 × (2 × ((λ n . (1, om n = 0; annars n × (( Y G) ( n −1)))) (2−1)))))

4 × (3 × (2 × (1, om 1 = 0; annars 1 × (( Y G) (1−1)))))

4 × (3 × (2 × (1 × (G ( Y G) (1−1)))))

4 × (3 × (2 × (1 × ((λ n . (1, om n = 0; annars n × (( Y G) ( n −1)))) (1−1))))))

4 × (3 × (2 × (1 × (1, om 0 = 0; annars 0 × (( Y G) (0−1))))))

4 × (3 × (2 × (1 × (1)))))

24

Varje rekursivt definierad funktion kan ses som en fast punkt för någon lämpligt definierad funktion som stänger över det rekursiva samtalet med ett extra argument, och därför kan varje rekursivt definierad funktion uttryckas som ett lambda -uttryck med hjälp av Y. I synnerhet kan vi nu rent definiera subtraktion, multiplikation och jämförelse predikat för naturliga tal rekursivt.

Standardvillkor

Vissa termer har vanligt accepterade namn:

Jag  : = λ x . x

K  : = λ x .λ y . x

S  : = λ x .λ y .λ z . x z ( y z )

B  : = λ x .λ y .λ z . x ( y z )

C  : = λ x .λ y .λ z . x z y

W  : = λ x .λ y . x y y

U  : = λ x . x x

ω  : = λ x . x x

Ω  : = ω ω

Y  : = λ g . (Λ x . G ( x x )) (λ x . G ( x x ))

Flera av dessa har direkta tillämpningar vid eliminering av abstraktion som förvandlar lambda -termer till kombinatorberäkningstermer .

Abstraktionseliminering

Om N är en lambda-term utan abstraktion, men möjligen innehåller namngivna konstanter ( kombinatorer ), finns det en lambda-term T ( x , N ) som motsvarar λ x . N men saknar abstraktion (utom som en del av de namngivna konstanterna, om dessa anses vara icke-atomiska). Detta kan också ses som anonymiserande variabler, eftersom T ( x , N ) tar bort alla förekomster av x från N , samtidigt som argumentvärden kan ersättas med positionerna där N innehåller ett x . Konverteringsfunktionen T kan definieras av:

T ( x , x ): = I

T ( x , N ): = K N om x inte är fri i N .

T ( x , M N ): = S T ( x , M ) T ( x , N )

I båda fallen kan en term av formen T ( x , N ) P reduceras genom att låta den initiala kombinatorn I , K eller S ta tag i argumentet P , precis som β-reduktion av (λ x . N ) P skulle göra. Jag återkommer med det argumentet. K kastar argumentet bort, precis som (λ x . N ) skulle göra om X har någon fri förekomst i N . S vidarebefordrar argumentet till båda delområdena i ansökan och applicerar sedan resultatet av det första på resultatet av det andra.

Kombinatorerna B och C liknar S , men skickar argumentet till endast en delterm för en applikation ( B till deltermen "argument" och C till delterm "funktion"), vilket sparar ett efterföljande K om det inte förekommer något av x i en delterm. I jämförelse med B och C , den S combinator faktiskt sammanflätar två funktionaliteter: ordna om argument, och duplicera ett argument, så att den kan användas på två ställen. Den W combinator gör endast den senare, vilket ger B, C, K, W-system som ett alternativ till SKI combinator tandsten .

Typade lambda -kalkyl

En typad lambda-kalkyl är en maskinskriven formalism som använder lambda-symbolen ( ) för att beteckna anonym funktionsabstraktion. I detta sammanhang är typer vanligtvis objekt av syntaktisk natur som tilldelas lambda -termer; den exakta typen av en typ beror på den beräknade kalkylen (se Typer av typade lambda -beräkningar ). Ur en viss synvinkel kan maskinskrivna lambda -beräkningar ses som förfiningar av den otypade lambda -kalkylen men från en annan synvinkel kan de också betraktas som den mer grundläggande teorin och den otypade lambda -kalkylen som ett specialfall med endast en typ. ${\ displaystyle \ lambda}$

Typade lambda -beräkningar är grundläggande programmeringsspråk och är basen för maskinskrivna funktionella programmeringsspråk som ML och Haskell och, mer indirekt, typade imperativa programmeringsspråk . Typade lambda -beräkningar spelar en viktig roll vid utformningen av typsystem för programmeringsspråk; här fångar typbarhet vanligtvis programmets önskvärda egenskaper, t.ex. kommer programmet inte att orsaka minnesåtkomstöverträdelse.

Typade lambda -beräkningar är nära besläktade med matematisk logik och bevisteori via Curry -Howard -isomorfismen och de kan betraktas som det interna språket i kategorier av kategorier , t.ex. är den enkelt skrivna lambda -kalkylen språket för kartesiska slutna kategorier (CCC).

Reduktionsstrategier

Huruvida en term normaliseras eller inte, och hur mycket arbete som behöver göras för att normalisera den om den är det, beror i stor utsträckning på den reduceringsstrategi som används. Vanliga lambda -kalkylreduceringsstrategier inkluderar:

Normal ordning

Den vänstra, yttersta återlösningen reduceras alltid först. Det vill säga när så är möjligt ersätts argumenten i abstraktionens kropp innan argumenten reduceras.

Tillämplig ordning

Den vänstra, innersta återlösningen reduceras alltid först. Intuitivt betyder det att en funktions argument alltid reduceras före själva funktionen. Tillämplig ordning försöker alltid tillämpa funktioner på normala former, även när detta inte är möjligt.

Full β-reduktion

Varje återlösning kan reduceras när som helst. Detta innebär i huvudsak avsaknaden av någon särskild reduceringsstrategi - när det gäller reducerbarhet är "alla spel avstängda".

Svaga strategier för minskning minskar inte under lambda -abstraktioner:

Ring efter värde

En redex reduceras endast när dess högra sida har reducerats till ett värde (variabel eller abstraktion). Endast de yttersta inlösenerna reduceras.

Ring efter namn

Som normal ordning, men inga reduktioner utförs inuti abstraktioner. Till exempel är λ x . (Λ x . X ) x i normal form enligt denna strategi, även om den innehåller redex (λ x . X ) x .

Strategier med delning minskar beräkningar som är "samma" parallellt:

Optimal minskning

Som normal ordning, men beräkningar som har samma etikett reduceras samtidigt.

Ring efter behov

Som anrop med namn (därav svag), men funktionsapplikationer som skulle duplicera termer istället namnge argumentet, som sedan reduceras bara "när det behövs".

Beräknbarhet

Det finns ingen algoritm som tar in två lambdauttryck och matar in SANT eller FALSK beroende på om det ena uttrycket reduceras till det andra. Närmare bestämt ingen beräkningsbar funktion kan avgöra frågan. Detta var historiskt sett det första problemet för vilket oavgörbarhet kunde bevisas. Som vanligt för ett sådant bevis, beräkningsbara organ beräkningsbar av någon modell av beräkning som Turing komplett . Faktum är att beräkningsbarheten själv kan definieras via lambda -beräkningen: en funktion F : N → N för naturliga tal är en beräkningsbar funktion om och bara om det finns ett lambda -uttryck f så att för varje par x , y i N , F ( x ) = y om och endast om f x  = _β  y , där x och y är kyrkans siffror som motsvarar x respektive y och = _β betyder ekvivalens med β-reduktion. Se Church -Turing -avhandlingen för andra metoder för att definiera beräkningsbarhet och deras likvärdighet.

Kyrkans bevis på datorkompatibilitet minskar först problemet till att avgöra om ett givet lambdauttryck har en normal form . Sedan antar han att detta predikat är beräkningsbart och kan därför uttryckas i lambda -kalkyl. Med utgångspunkt i tidigare verk av Kleene och konstruering av en Gödel -numrering för lambdauttryck konstruerar han ett lambdauttryck e som noggrant följer beviset på Gödels första ofullständighetssats . Om e tillämpas på sitt eget Gödel -nummer, uppstår en motsägelse.

Komplexitet

Begreppet beräkningskomplexitet för lambda-kalkylen är lite knepigt, eftersom kostnaden för en β-reduktion kan variera beroende på hur den implementeras. För att vara exakt måste man på något sätt hitta platsen för alla förekomster av den bundna variabeln V i uttrycket E , vilket innebär en tidskostnad, eller man måste hålla reda på platserna för fria variabler på något sätt, vilket innebär en rymdkostnad. En naiv sökning efter placeringarna av V i E är O ( n ) i längden n av E . Direktörsträngar var ett tidigt tillvägagångssätt som handlade denna tidskostnad för en kvadratisk rymdanvändning. Mer allmänt har detta lett till studier av system som använder uttrycklig substitution .

År 2014 visade det sig att antalet ß-reduktion steg vid normal orderreduktion för att minska en term är en rimlig tidskostnadsmodell, det vill säga att minskningen kan simuleras på en Turing-maskin i tid polynomt proportionellt mot antalet steg . Detta var ett mångårigt öppet problem, på grund av storleksplosion , förekomsten av lambda-termer som växer exponentiellt i storlek för varje β-reduktion. Resultatet kommer runt detta genom att arbeta med en kompakt delad representation. Resultatet klargör att mängden utrymme som behövs för att utvärdera en lambda -term inte är proportionell mot termens storlek under reduktion. Det är för närvarande inte känt vad ett bra mått på rymdkomplexitet skulle vara.

En orimlig modell betyder inte nödvändigtvis ineffektiv. Optimal reduktion minskar alla beräkningar med samma etikett i ett steg, vilket undviker duplicerat arbete, men antalet parallella β-reduktionssteg för att reducera en given term till normal form är ungefär linjär i termens storlek. Detta är alldeles för litet för att vara ett rimligt kostnadsmått, eftersom vilken Turing -maskin som helst kan vara kodad i lambda -beräkningen i storlek linjärt proportionell mot storleken på Turing -maskinen. Den verkliga kostnaden för att reducera lambda-termer beror inte på β-reduktion i sig utan snarare hanteringen av dubblering av redexes under β-reduktion. Det är inte känt om optimala reduktionsimplementeringar är rimliga när de mäts med avseende på en rimlig kostnadsmodell, såsom antalet längst ut yttersta steg till normal form, men det har visats för fragment av lambda-beräkningen att den optimala reduktionsalgoritmen är effektiv och har högst en kvadratisk overhead jämfört med längst ut ytterst. Dessutom genomförde BOHM -prototypimplementeringen av optimal reduktion bättre än både Caml Light och Haskell på rena lambda -villkor.

Lambda -kalkyl och programmeringsspråk

Som påpekats i Peter Landins artikel från 1965 "A Correspondence between ALGOL 60 and Church's Lambda-notation", kan sekventiella procedurprogrammeringsspråk förstås i form av lambda-kalkylen, som tillhandahåller de grundläggande mekanismerna för procedurell abstraktion och procedur (delprogram) Ansökan.

Anonyma funktioner

I Lisp kan till exempel funktionen "kvadrat" uttryckas som ett lambda -uttryck enligt följande:

(lambda (x) (* x x))

Ovanstående exempel är ett uttryck som utvärderas till en förstklassig funktion. Symbolen lambdaskapar en anonym funktion, med tanke på en lista över parameternamn, (x)- bara ett enda argument i det här fallet, och ett uttryck som utvärderas som kroppen av funktionen (* x x). Anonyma funktioner kallas ibland lambdauttryck.

Till exempel har Pascal och många andra tvingande språk länge stött att passera delprogram som argument till andra delprogram genom mekanismen för funktionspekare . Funktionspekare är dock inte en tillräcklig förutsättning för att funktioner ska vara förstklassiga datatyper, eftersom en funktion är en förstklassig datatyp om och bara om nya instanser av funktionen kan skapas vid körning. Och den här funktionen för att skapa funktioner stöds bland annat i Smalltalk , JavaScript och Wolfram Language , och nyligen bland annat i Scala , Eiffel ("agenter"), C# ("delegater") och C ++ 11 .

Parallelism och samtidighet

Den Church-Rosser egenskap hos lambda calculus organen att utvärdering (β-reduktion) kan utföras i vilken ordning som helst , även parallellt. Detta innebär att olika icke -bestämda utvärderingsstrategier är relevanta. Lambda -beräkningen erbjuder emellertid inte några uttryckliga konstruktioner för parallellitet . Man kan lägga till konstruktioner som Futures till lambda -kalkylen. Andra processberäkningar har utvecklats för att beskriva kommunikation och samtidighet.

Semantik

Det faktum att lambda calculus termer fungerar som funktioner på andra lambda calculus termer, och även på sig själva, ledde till frågor om semantiken i lambda calculus. Kan en vettig betydelse tilldelas lambda calculus termer? Den naturliga semantiken var att hitta en uppsättning D isomorf för funktionsutrymmet D → D , av funktioner på sig själv. Emellertid kan inget icke -sådant D existera, av kardinalitetsbegränsningar eftersom uppsättningen av alla funktioner från D till D har större kardinalitet än D , om inte D är en singletonsats .

På 1970 -talet visade Dana Scott att om man bara övervägde kontinuerliga funktioner kunde man hitta en uppsättning eller domän D med den erforderliga egenskapen, vilket gav en modell för lambda -beräkningen.

Detta arbete låg också till grund för programmeringsspråks denotationella semantik .

Varianter och tillägg

Dessa tillägg finns i lambda -kuben :

• Typad lambda -kalkyl - Lambda -kalkyl med maskinskrivna variabler (och funktioner)
• System F- En maskinskriven lambda-kalkyl med typvariabler
• Konstruktionskalkyl- En maskinskriven lambda-kalkyl med typer som förstklassiga värden

Dessa formella system är förlängningar av lambda -kalkyl som inte finns i lambda -kuben:

• Binär lambda -kalkyl - En version av lambda -kalkyl med binär I/O, en binär kodning av termer och en utsedd universell maskin.
• Lambda-mu-kalkyl- En förlängning av lambda-kalkylen för behandling av klassisk logik

Dessa formella system är variationer av lambda -kalkyl:

• Kappa calculus- En första ordningens analog av lambda calculus

Dessa formella system är relaterade till lambda calculus:

• Kombinerande logik - En notation för matematisk logik utan variabler
• SKI -kombinationsberäkning - Ett beräkningssystem baserat på S , K och I -kombinatorerna, motsvarande lambda -kalkyl, men reducerbar utan variabla substitutioner

Se även

Anteckningar

Referenser

Vidare läsning

• Abelson, Harold & Gerald Jay Sussman. Struktur och tolkning av datorprogram . MIT Press . ISBN  0-262-51087-1 .
• Hendrik Pieter Barendregt Introduktion till Lambda Calculus .
• Henk Barendregt , The Impda of the Lambda Calculus in Logic and Computer Science . Bulletin of Symbolic Logic, volym 3, nummer 2, juni 1997.
• Barendregt, Hendrik Pieter , The Type Free Lambda Calculus pp1091–1132 i Handbook of Mathematical Logic , North-Holland (1977) ISBN  0-7204-2285-X
• Cardone och Hindley, 2006. History of Lambda-calculus and Combinatory Logic . In Gabbay and Woods (red.), Handbook of the History of Logic , vol. 5. Elsevier.
• Church, Alonzo, An unsolvable problem of elementary number theory , American Journal of Mathematics , 58 (1936), s. 345–363. Detta dokument innehåller beviset på att ekvivalensen av lambdauttryck i allmänhet inte går att avgöra.
• Alonzo Church, The Calculi of Lambda-Conversion ( ISBN  978-0-691-08394-0 )
• Frink Jr., Orrin, Review: The Calculi of Lambda-Conversion
• Kleene, Stephen, A theory of positive integers in formal logic , American Journal of Mathematics , 57 (1935), s. 153–173 och 219–244. Innehåller lambda calculus definitioner av flera välkända funktioner.
• Landin, Peter , En korrespondens mellan ALGOL 60 och Church's Lambda-Notation , Communications of the ACM , vol. 8, nej. 2 (1965), sidorna 89–101. Tillgänglig från ACM -webbplatsen . Ett klassiskt papper som belyser vikten av lambda -kalkyl som grund för programmeringsspråk.
• Larson, Jim, En introduktion till Lambda Calculus and Scheme . En skonsam introduktion för programmerare.
• Schalk, A. och Simmons, H. (2005) En introduktion till λ-calculi och aritmetik med ett anständigt urval av övningar . Anteckningar för en kurs i matematisk logik MSc vid Manchester University.
• de Queiroz, Ruy JGB (2008). "Om reduktionsregler, betydelse som användning och bevisteoretisk semantik". Studia Logica . 90 (2): 211–247. doi : 10.1007/s11225-008-9150-5 . S2CID  11321602 . Ett papper som ger en formell grund för idén om "mening-är-användning" som, även om den är baserad på bevis, skiljer sig från bevisteoretisk semantik som i Dummett-Prawitz-traditionen eftersom den tar minskning som reglerna som ger mening.
• Hankin, Chris, En introduktion till Lambda Calculi för datavetenskapare, ISBN  0954300653

Monografier/läroböcker för doktorander:

• Morten Heine Sørensen, Paweł Urzyczyn, Lectures on the Curry – Howard isomorphism , Elsevier, 2006, ISBN  0-444-52077-5 är en ny monografi som täcker huvudämnen för lambda calculus från den typfria sorten till de flesta typade lambda calculi , inklusive nyare utveckling som rena typsystem och lambdakuben . Det täcker inte undertypstillägg .
• Pierce, Benjamin (2002), Typer och programmeringsspråk , MIT Press, ISBN 0-262-16209-1täcker lambda calculi ur ett praktiskt systemsystemperspektiv; vissa ämnen som beroende typer nämns bara, men underskrivning är ett viktigt ämne.

Vissa delar av denna artikel är baserade på material från FOLDOC , som används med tillstånd .

externa länkar

• Graham Hutton, Lambda Calculus , en kort (12 minuter) datorfilm om Lambda Calculus
• Helmut Brandl, steg för steg Introduktion till Lambda Calculus
• "Lambda-calculus" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Achim Jung, En kort introduktion till Lambda Calculus -( PDF )
• Dana Scott, A timeline of lambda calculus -( PDF )
• David C. Keenan, To Dissect a Mockingbird: A Graphical Notation for the Lambda Calculus with Animated Reduction
• Raúl Rojas, En självstudie Introduktion till Lambda Calculus -( PDF )
• Peter Selinger, Föreläsningsanteckningar om Lambda Calculus -( PDF )
• L. Allison, Några exekverbara λ-kalkylexempel
• Georg P. Loczewski, Lambda Calculus och A ++
• Bret Victor, Alligator Eggs: A Puzzle Game Baserat på Lambda Calculus
• Lambda Calculus på Safalras webbplats
• LCI Lambda Interpreter en enkel men kraftfull ren kalkyltolk
• Lambda Calculus-länkar på Lambda-the-Ultimate
• Mike Thyer, Lambda Animator , en grafisk Java -applet som visar alternativa reduktionsstrategier.
• Implementera Lambda -kalkylen med hjälp av C ++ - mallar
• Marius Buliga, Grafisk lambda -kalkyl
• Lambda Calculus as a Workflow Model av Peter Kelly, Paul Coddington och Andrew Wendelborn; nämner grafreduktion som ett vanligt sätt att utvärdera lambdauttryck och diskuterar tillämpningen av lambda -beräkning för distribuerad beräkning (på grund avegenskapen Church – Rosser , som möjliggör parallell grafreduktion för lambdauttryck).
• Shane Steinert-Threlkeld, "Lambda Calculi" , Internet Encyclopedia of Philosophy
• Anton Salikhmetov, Makro Lambda Calculus