Låt uttryck - Let expression

Inom datavetenskap associerar ett "låt" -uttryck en funktionsdefinition med ett begränsat omfång .

Den "låt" uttryck kan också definieras i matematik, där den associerar en Boolean tillstånd med en begränsad omfattning.

"Låt" -uttrycket kan betraktas som en lambda -abstraktion applicerad på ett värde. Inom matematik kan ett låtuttryck också betraktas som en sammansättning av uttryck, inom en existentiell kvantifierare som begränsar variabelns omfattning.

Låtuttrycket finns på många funktionella språk för att möjliggöra den lokala definitionen av uttryck, för att definiera ett annat uttryck. Låtuttrycket finns på vissa funktionella språk i två former; låt eller "låt rec". Let rec är en förlängning av det enkla let-uttrycket som använder fixpunkts-kombinatorn för att implementera rekursion .

Historia

Dana Scott 's LCF språket var ett steg i utvecklingen av lambdakalkyl till moderna funktionella språk. Detta språk introducerade let -uttrycket, som har dykt upp på de flesta funktionella språk sedan dess.

Språken Scheme , ML och på senare tid har Haskell ärvt låtuttryck från LCF.

Stateful imperative språk som ALGOL och Pascal implementerar i huvudsak ett let -uttryck, för att implementera begränsat funktionsomfång, i blockstrukturer.

Ett närbesläktat " där " klausul, tillsammans med sin rekursiva variant "där rec ", dök upp redan i Peter Landin 's Den mekaniska utvärderingen av uttryck .

Beskrivning

Ett "låt" -uttryck definierar en funktion eller ett värde för användning i ett annat uttryck. Förutom att den är en konstruktion som används i många funktionella programmeringsspråk, är den en naturlig språkkonstruktion som ofta används i matematiska texter. Det är en alternativ syntaktisk konstruktion för en var -sats.

Låt uttryck	Var klausul
Låta ${\ displaystyle a = 3}$ och ${\ displaystyle b = 4}$ i ${\ displaystyle {\ sqrt {a^{2}+b^{2}}}}$	${\ displaystyle {\ sqrt {a^{2}+b^{2}}}}$ var ${\ displaystyle a = 3}$ och ${\ displaystyle b = 4}$

I båda fallen är hela konstruktionen ett uttryck vars värde är 5. Liksom if-then-else är typen som uttrycket returnerar inte nödvändigtvis booleskt.

Ett låtuttryck finns i 4 huvudformer,

Form	Och	Rekursiv	Definition / begränsning	Beskrivning
Enkel	Nej	Nej	Definition	Enkel icke -rekursiv funktionsdefinition.
Rekursiv	Nej	Ja	Definition	Rekursiv funktionsdefinition (implementerad med Y -kombinatorn ).
Ömsesidig	Ja	Ja	Definition	Ömsesidigt rekursiv funktionsdefinition.
Matematisk	Ja	Ja	Begränsning	Matematisk definition som stöder ett allmänt booleskt uthyrningsvillkor.

I funktionella språk den låt uttryck definierar funktioner som kan kallas i uttrycket. Omfattningen av funktionsnamnet är begränsad till strukturen för låta uttryck.

I matematik definierar låtuttrycket ett villkor, vilket är en begränsning för uttrycket. Syntaxen kan också stödja deklarationen av existentiellt kvantifierade variabler som är lokala för uthyrningsuttrycket.

Terminologin, syntaxen och semantiken varierar från språk till språk. I Scheme används let för den enkla formen och låt rec för den rekursiva formen. I ML låter bara markera starten på ett deklarationsblock med roligt som markerar starten på funktionsdefinitionen. I Haskell kan låt vara ömsesidigt rekursivt, med kompilatorn som räknar ut vad som behövs.

Definition

En lambda -abstraktion representerar en funktion utan namn. Detta är en källa till inkonsekvensen i definitionen av en lambda -abstraktion. Lambda -abstraktioner kan dock komponeras för att representera en funktion med ett namn. I denna form avlägsnas inkonsekvensen. Lambda -termen,

${\ displaystyle (\ lambda fz) \ (\ lambda xy)}$

motsvarar att definiera funktionen med i uttrycket , som kan skrivas som låta uttryck; ${\ displaystyle f}$${\ displaystyle f \ x = y}$${\ displaystyle z}$

${\ displaystyle \ operatorname {let} f \ x = y \ operatorname {in} z}$

Låtuttrycket är förståeligt som ett naturligt språkuttryck. Let -uttrycket representerar substitutionen av en variabel för ett värde. I substitutionsregeln beskrivs konsekvenserna av jämlikhet som substitution.

Låt definitionen i matematik

I matematiken den låt uttryck beskrivs som tillsammans uttryck. I funktionella språk används även uttrycket för att begränsa omfattningen. I matematik beskrivs omfattningen av kvantifierare. Låtuttrycket är en konjunktion inom en existentiell kvantifierare.

${\ displaystyle (\ exist xE \ land F) \ iff \ operatorname {let} x: E \ operatorname {in} F}$

där E och F är av typen booleskt.

Det låter uttrycket tillåter substitution som skall tillämpas på ett annat uttryck. Denna substitution kan tillämpas inom ett begränsat omfång, på ett subuttryck. Den naturliga användningen av let -uttrycket gäller för ett begränsat omfång (kallat lambda -dropping ). Dessa regler definierar hur omfattningen kan begränsas.

${\ displaystyle {\ begin {cases} x \ not \ in \ operatorname {FV} (E) \ land x \ in \ operatorname {FV} (F) \ implis \ operatorname {let} x: G \ operatorname {in} E \ F = E \ (\ operatorname {let} x: G \ operatorname {in} F) \\ x \ in \ operatorname {FV} (E) \ land x \ not \ in \ operatorname {FV} (F) \ implicerar \ operatorname {let} x: G \ operatorname {in} E \ F = (\ operatorname {let} x: G \ operatorname {in} E) \ F \\ x \ not \ in \ operatorname {FV} ( E) \ land x \ not \ in \ operatorname {FV} (F) \ implisates \ operatorname {let} x: G \ operatorname {in} E \ F = E \ F \ end {cases}}}$

där F är inte av typen Boolean . Från denna definition kan följande standarddefinition av ett låtuttryck, som används i ett funktionellt språk, härledas.

${\ displaystyle x \ not \ in \ operatorname {FV} (y) \ implicerar (\ operatorname {let} x: x = y \ operatorname {in} z) = z [x: = y] = (\ lambda xz) \ y}$

För enkelhetens skull kommer markören som specificerar den existentiella variabeln ,, att utelämnas från uttrycket där det framgår av sammanhanget. ${\ displaystyle x:}$

${\ displaystyle x \ not \ in \ operatorname {FV} (y) \ implicerar (\ operatorname {let} x = y \ operatorname {in} z) = z [x: = y] = (\ lambda xz) \ y }$

Härledning

För att härleda detta resultat, anta först,

${\ displaystyle x \ not \ in \ operatorname {FV} (L)}$

sedan

${\ displaystyle {\ begin {align} L \ (\ operatorname {let} x: x = y \ operatorname {in} z) & \ iff (\ operatorname {let} x: x = y \ operatorname {in} L \ z) \\ & \ iff x = y \ land L \ z \ end {align}}}$

Med hjälp av substitutionsregeln,

${\ displaystyle {\ begin {align} & \ iff x = y \ land (L \ z) [x: = y] \\ & \ iff x = y \ land (L [x: = y] \ z [x : = y]) \\ & \ iff x = y \ land L \ z [x: = y] \\ & \ innebär L \ z [x: = y] \ end {align}}}$

så för alla L ,

${\ displaystyle L \ operatorname {let} x: x = y \ operatorname {in} z \ innebär L \ z [x: = y]}$

Låt där K är en ny variabel. sedan, ${\ displaystyle L \ X = (X = K)}$

${\ displaystyle (\ operatorname {let} x: x = y \ operatorname {in} z) = K \ innebär z [x: = y] = K}$

Så,

${\ displaystyle \ operatorname {let} x: x = y \ operatorname {in} z = z [x: = y]}$

Men från den matematiska tolkningen av en betareduktion,

${\ displaystyle (\ lambda xz) \ y = z [x: = y]}$

Här om y är en funktion av en variabel x är det inte samma x som i z. Alpha -namnbyte kan tillämpas. Så vi måste ha,

${\ displaystyle x \ not \ in \ operatorname {FV} (y)}$

så,

${\ displaystyle x \ not \ in \ operatorname {FV} (y) \ implicit \ operatorname {let} x: x = y \ operatorname {in} z = (\ lambda xz) \ y}$

Detta resultat representeras i ett funktionellt språk i en förkortad form, där innebörden är entydig;

${\ displaystyle x \ not \ in \ operatorname {FV} (y) \ implicerar (\ operatorname {let} x = y \ operatorname {in} z) = z [x: = y] = (\ lambda xz) \ y }$

Här erkänns variabeln x implicit som både en del av ekvationen som definierar x, och variabeln i den existentiella kvantifieraren.

Inga lyft från booleskt

En motsättning uppstår om E definieras av . I detta fall, ${\ displaystyle E = \ neg}$

${\ displaystyle x \ not \ in \ operatorname {FV} (E) \ land x \ in \ operatorname {FV} (F) \ impliserer \ operatorname {let} x: G \ operatorname {in} E \ F = E \ (\ operatorname {let} x: G \ operatorname {in} F)}$

blir,

${\ displaystyle \ operatorname {let} x: G \ operatorname {in} \ neg F = \ neg \ (\ operatorname {let} x: G \ operatorname {in} F)}$

och använder,

${\ displaystyle (\ exist xE \ land F) \ iff \ operatorname {let} x: E \ operatorname {in} F}$

${\ displaystyle (\ existerar xG \ land \ neg F) = \ neg \ (\ existerar xG \ land F)}$

${\ displaystyle = (\ existerar x \ neg G \ lor \ neg F)}$

Detta är falskt om G är falskt. För att undvika denna motsägelse får F inte vara av typen booleskt. För booleska F använder det korrekta uttalandet av släppregeln implikation istället för jämlikhet,

${\ displaystyle x \ not \ in \ operatorname {FV} (E) \ land x \ in \ operatorname {FV} (F) \ impliserer (\ operatorname {let} x: G \ operatorname {in} E \ F \ to E \ (\ operatorname {let} x: G \ operatorname {in} F))}$

Det kan verka konstigt att en annan regel gäller för booleska än andra typer. Anledningen till detta är att regeln,

${\ displaystyle (\ exist xE \ land F) \ iff \ operatorname {let} x: E \ operatorname {in} F}$

gäller endast där F är booleskt. Kombinationen av de två reglerna skapar en motsättning, så där en regel håller, gör den andra inte.

Gå med låt uttryck

Låt uttryck definieras med flera variabler,

${\ displaystyle (\ existerar v \ cdots \ existerar w \ existerar xE \ land F) \ iff \ operatorname {let} v, \ ldots, w, x: E \ operatorname {in} F}$

då kan det härledas,

${\ displaystyle x \ not \ i FV (E) \ innebär (\ existerar v \ cdots \ existerar w \ existerar xE \ land F) \ iff (\ existerar v \ cdots \ existerar w (E \ land \ existerar xF)) }$

så,

${\ displaystyle x \ not \ i FV (E) \ innebär (\ operatorname {let} v, \ ldots, w, x: E \ land F \ operatorname {in} L \ equiv \ operatorname {let} v, \ ldots , w: E \ operatorname {in} \ operatorname {let} x: F \ operatorname {in} L)}$

Lagar som rör lambda -beräkning och låt uttryck

Den Eta reduktionen ger en regel för att beskriva lambda abstraktioner. Denna regel tillsammans med de två lagarna som härleds ovan definierar förhållandet mellan lambda calculus och let uttryck.

namn	Lag
Eta-reduktion ekvivalens	${\ displaystyle f \ x = y \ equiv f = \ lambda xy}$
Låt-lambda-ekvivalens	${\ displaystyle f \ notin FV (E) \ implicerar (\ operatorname {let} f: f = E \ operatorname {in} L \ equiv (\ lambda fL) \ E)}$(där är ett variabelnamn.) ${\ displaystyle f}$
Låt kombinationen	${\ displaystyle x \ notin FV (E) \ innebär (\ operatorname {let} v, \ dots, w, x: E \ land F \ operatorname {in} L \ equiv \ operatorname {let} v, \ dots, w : E \ operatorname {in} \ operatorname {let} x: F \ operatorname {in} L)}$

Låt definitionen definieras från lambda calculus

För att undvika eventuella problem i samband med matematiska definition , Dana Scott ursprungligen definierat låt uttryck från lambdakalkyl. Detta kan betraktas som den nedifrån uppåt eller konstruktiva, definitionen av låta uttryck, i motsats till uppifrån och ner, eller axiomatisk matematisk definition.

Det enkla, icke rekursiva låtuttrycket definierades som syntaktiskt socker för lambda -abstraktionen som tillämpas på en term. I den definitionen,

${\ displaystyle (\ operatorname {let} _ {s} x = y \ operatorname {in} z) \ equiv (\ lambda xz) \ y}$

Den enkla låtauttrycksdefinitionen utökades sedan för att möjliggöra rekursion med hjälp av fastpunktskombinatorn .

Fixat-punkts kombinator

Den fast punkt combinator kan representeras av uttrycket,

${\ displaystyle \ lambda f. \ operatorname {let} x = f \ x \ operatorname {in} x}$

Denna representation kan omvandlas till en lambda -term. En lambda -abstraktion stöder inte referens till variabelnamnet i det tillämpade uttrycket, så x måste skickas in som en parameter till x .

${\ displaystyle \ lambda f. \ operatorname {let} x \ x = f \ (x \ x) \ operatorname {in} x \ x}$

Med hjälp av eta -reduceringsregeln,

${\ displaystyle f \ x = y \ equiv f = \ lambda xy}$

ger,

${\ displaystyle \ lambda f. \ operatorname {let} x = \ lambda xf \ (x \ x) \ operatorname {in} x \ x}$

Ett låtuttryck kan uttryckas som en lambda -abstraktion med,

${\ displaystyle n \ not \ in FV (E) \ to (\ operatorname {let} n = E \ operatorname {in} L \ equiv (\ lambda nL) \ E)}$

ger,

${\ displaystyle \ lambda f. (\ lambda xx \ x) \ (\ lambda xf \ (x \ x))}}$

Detta är möjligen den enklaste implementeringen av en fixpunktskombinator i lambda -kalkyl. Men en betareduktion ger den mer symmetriska formen av Currys Y -kombinator.

${\ displaystyle \ lambda f. (\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x))}}$

Rekursivt låtuttryck

Det rekursiva let -uttrycket som kallas "let rec" definieras med hjälp av Y -kombinatorn för rekursiva let -uttryck.

${\ displaystyle (\ operatorname {let \ rec} x = y \ operatorname {in} z) \ equiv (\ lambda xz) \ (Y \ (\ lambda xy))}}$

Ömsesidigt rekursivt låt uttryck

Detta tillvägagångssätt generaliseras sedan för att stödja ömsesidig rekursion. Ett inbördes rekursivt låtuttryck kan komponeras genom att ordna om uttrycket för att ta bort alla villkor. Detta uppnås genom att ersätta flera funktionsdefinitioner med en enda funktionsdefinition, som anger en lista med variabler som är lika med en lista med uttryck. En version av Y-kombinatorn, kallad Y* poly-variadic fix-point-kombinatorn, används sedan för att beräkna fixpunkten för alla funktioner samtidigt. Resultatet är en ömsesidigt rekursiv implementering av låtuttrycket .

Flera värden

Ett låtuttryck kan användas för att representera ett värde som är medlem i en uppsättning,

${\ displaystyle \ operatorname {let} x \ in X \ operatorname {in} x}$

Under funktionsapplikation, av ett låt uttryck till ett annat,

${\ displaystyle {\ begin {align} & (\ operatorname {let} x \ in X \ operatorname {in} x) \ (\ operatorname {let} y \ i Y \ operatorname {in} y) \\ & = \ operatorname {låt} x \ i X \ land y \ i Y \ operatorname {in} x \ y \\ & = \ operatorname {let} (x, y) \ i X \ gånger Y \ operatorname {i} x \ y \ end {align}}}$

Men en annan regel gäller för att tillämpa let -uttrycket på sig själv.

${\ displaystyle {\ begin {align} & (\ operatorname {let} x \ in X \ operatorname {in} x) \ (\ operatorname {let} x \ in X \ operatorname {in} x) \\ & = \ operatorname {låt} x \ i X \ operatorname {i} x \ x \ end {justerat}}}$

Det finns ingen enkel regel för att kombinera värden. Det som krävs är en allmän uttrycksform som representerar en variabel vars värde är medlem i en uppsättning värden. Uttrycket bör baseras på variabeln och uppsättningen.

Funktionsapplikation som tillämpas på det här formuläret bör ge ett annat uttryck i samma form. På detta sätt kan alla uttryck på funktioner med flera värden behandlas som om de hade ett värde.

Det är inte tillräckligt att formuläret endast representerar mängden värden. Varje värde måste ha ett villkor som avgör när uttrycket tar värdet. Den resulterande konstruktionen är en uppsättning par av villkor och värden, kallade en "värdeuppsättning". Se förminskning av algebraiska värdeuppsättningar .

Regler för konvertering mellan lambda -kalkyl och let -uttryck

Meta-funktioner kommer att ges som beskriver konverteringen mellan lambda och låt uttryck. En metafunktion är en funktion som tar ett program som parameter. Programmet är data för metaprogrammet. Programmet och metaprogrammet har olika metanivåer.

Följande konventioner kommer att användas för att skilja program från metaprogrammet,

• Kvadratparenteser [] kommer att användas för att representera funktionsapplikationen i metaprogrammet.
• Versaler kommer att användas för variabler i metaprogrammet. Små bokstäver representerar variabler i programmet.
• ${\ displaystyle \ equiv}$ kommer att användas för lika med metaprogrammet.

För enkelhetens skull den första regeln med tanke på att matchningar kommer att tillämpas. Reglerna förutsätter också att lambdauttrycken har förbehandlats så att varje lambda-abstraktion har ett unikt namn.

Substitutionsoperatören används också. Uttrycket betyder att varje förekomst av G i L ersätts med S och returnerar uttrycket. Definitionen som används utvidgas till att täcka substitution av uttryck, från definitionen på Lambda -kalkylsidan . Matchning av uttryck bör jämföra uttryck för alfaekvivalens (byta namn på variabler). ${\ displaystyle L [G: = S]}$

Konvertering från lambda till let uttryck

Följande regler beskriver hur man konverterar från ett lambda -uttryck till ett let -uttryck utan att ändra strukturen.

1. ${\ displaystyle \ operatorname {de-lambda} [V] \ equiv V}$
2. ${\ displaystyle \ operatorname {de-lambda} [M \ N] \ equiv \ operatorname {de-lambda} [M] \ \ operatorname {de-lambda} [N]}$
3. ${\ displaystyle \ operatorname {de-lambda} [F = \ lambda PE] \ equiv \ operatorname {de-lambda} [F \ P = E]}$
4. ${\ displaystyle \ operatorname {de-lambda} [E = F] \ equiv \ operatorname {de-lambda} [E] = \ operatorname {de-lambda} [F]}$
5. ${\ displaystyle \ operatorname {de-lambda} [(\ lambda FE) L] \ equiv \ operatorname {let-combine} [\ operatorname {let} F: \ operatorname {de-lambda} [F = L] \ operatorname { i} E]}$
6. ${\ displaystyle V \ not \ in \ operatorname {FV} [\ lambda FE] \ to \ operatorname {de-lambda} [\ lambda FE] \ equiv \ operatorname {let-combine} [\ operatorname {let} V: \ operatorname {de-lambda} [V \ F = E] \ operatorname {in} V]}$
7. ${\ displaystyle V \ neq W \ to \ operatorname {let-combine} [\ operatorname {let} V: E \ operatorname {in} \ operatorname {let} W: F \ operatorname {in} G] \ equiv \ operatorname { låt} V, W: E \ land F \ operatorname {i} G}$
8. ${\ displaystyle \ operatorname {let-combine} [\ operatorname {let} V: E \ operatorname {in} F] \ equiv \ operatorname {let} V: E \ operatorname {in} F}$

Regel 6 skapar en unik variabel V, som ett namn för funktionen.

Exempel

Till exempel Y -kombinatorn ,

${\ displaystyle \ lambda f. (\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x))}}$

konverteras till,

${\ displaystyle \ operatorname {let} p: p \ f = \ operatorname {let} x: x \ q = f \ (q \ q) \ operatorname {in} f \ (x \ x) \ operatorname {in} p }$

Regel	Lambda uttryck
6	${\ displaystyle \ operatorname {de-lambda} [\ lambda f. (\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x))]]}$ ${\ displaystyle V \ not \ in \ operatorname {FV} [\ lambda FE] \ to \ operatorname {de-lambda} [\ lambda FE]}$ ${\ displaystyle V = p, F = f, E = (\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x))}}$ ${\ displaystyle \ operatorname {let-combine} [\ operatorname {let} V: \ operatorname {de-lambda} [V \ F = E] \ operatorname {in} V]}$
4	${\ displaystyle \ operatorname {let-combine} [\ operatorname {let} p: \ operatorname {de-lambda} [p \ f = (\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x))] \ operatorname {in} p]}$ ${\ displaystyle \ operatorname {de-lambda} [p \ f = (\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x))]}}$ ${\ displaystyle \ operatorname {de-lambda} [E = F]}$ ${\ displaystyle E = p \ f, F = (\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x))}}$ ${\ displaystyle \ operatorname {de-lambda} [E] = \ operatorname {de-lambda} [F]}$ ${\ displaystyle \ operatorname {de-lambda} [p \ f] = \ operatorname {de-lambda} [(\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x))]]}$ ${\ displaystyle \ operatorname {let-combine} [\ operatorname {let} p: \ operatorname {de-lambda} [p \ f] = \ operatorname {de-lambda} [(\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x))] \ operatorname {in} p]}$
5	${\ displaystyle \ operatorname {let-combine} [\ operatorname {let} p: \ operatorname {de-lambda} [p \ f] = \ operatorname {de-lambda} [(\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x))] \ operatorname {in} p]}$ ${\ displaystyle \ operatorname {de-lambda} [(\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x))]]}$ ${\ displaystyle \ operatorname {de-lambda} [(\ lambda FE) L]}$ ${\ displaystyle F = x, E = f \ (x \ x), L = (\ lambda xf \ (x \ x))}$ ${\ displaystyle \ operatorname {let-combine} [\ operatorname {let} F: \ operatorname {de-lambda} [F = L] \ operatorname {in} E]}$ ${\ displaystyle \ operatorname {let-combine} [\ operatorname {let} x: \ operatorname {de-lambda} [x = \ lambda xf \ (x \ x)] \ operatorname {in} f \ (x \ x) ]}}$
3	${\ displaystyle \ operatorname {let-combine} [\ operatorname {let} p: \ operatorname {de-lambda} [p \ f] = \ operatorname {let-combine} [\ operatorname {let} x: \ operatorname {de -lambda} [x = \ lambda xf \ (x \ x)] \ operatorname {in} f \ (x \ x)] \ operatorname {in} p]}$ ${\ displaystyle \ operatorname {de-lambda} [x = \ lambda xf \ (x \ x)]}$ ${\ displaystyle \ operatorname {de-lambda} [F = \ lambda PE]}$ ${\ displaystyle F = x, P = x, E = f \ (x \ x)}$ ${\ displaystyle \ operatorname {de-lambda} [F \ P = E]}$ ${\ displaystyle \ operatorname {de-lambda} [x \ x = f \ (x \ x)]}$
8	${\ displaystyle \ operatorname {let-combine} [\ operatorname {let} p: \ operatorname {de-lambda} [p \ f] = \ operatorname {let-combine} [\ operatorname {let} x: \ operatorname {de -lambda} [x \ x = f \ (x \ x)] \ operatorname {in} f \ (x \ x)] \ operatorname {in} p]}$ ${\ displaystyle \ operatorname {let-combine} [\ operatorname {let} x: \ operatorname {de-lambda} [x \ x = f \ (x \ x)] \ operatorname {in} f \ (x \ x) ]}}$ ${\ displaystyle \ operatorname {låt-kombinera} [Y]}$ ${\ displaystyle Y = \ operatorname {let} x: \ operatorname {de-lambda} [x \ x = f \ (x \ x)] \ operatorname {in} f \ (x \ x)}$ ${\ displaystyle Y}$ ${\ displaystyle \ operatorname {let} x: \ operatorname {de-lambda} [x \ x = f \ (x \ x)] \ operatorname {in} f \ (x \ x)}$
8	${\ displaystyle \ operatorname {let-combine} [\ operatorname {let} p: \ operatorname {de-lambda} [p \ f] = \ operatorname {let} x: \ operatorname {de-lambda} [x \ x = f \ (x \ x)] \ operatorname {in} f \ (x \ x) \ operatorname {in} p]}$ ${\ displaystyle \ operatorname {låt-kombinera} [Y]}$ ${\ displaystyle Y = \ operatorname {let} p: \ operatorname {de-lambda} [p \ f = \ operatorname {let} x: \ operatorname {de-lambda} [x \ x = f \ (x \ x) ] \ operatorname {in} f \ (x \ x)] \ operatorname {in} p}$ ${\ displaystyle Y}$ ${\ displaystyle \ operatorname {let} p: p \ f = \ operatorname {let} x: \ operatorname {de-lambda} [x \ x = f \ (x \ x)] \ operatorname {in} f \ (x \ x) \ operatorname {in} p}$
4	${\ displaystyle \ operatorname {let} p: \ operatorname {de-lambda} [p \ f] = \ operatorname {let} x: \ operatorname {de-lambda} [x \ x = f \ (x \ x)] \ operatorname {in} f \ (x \ x) \ operatorname {in} p}$ ${\ displaystyle \ operatorname {de-lambda} [x \ x = f \ (x \ x)]}$ ${\ displaystyle \ operatorname {de-lambda} [E = F]}$ ${\ displaystyle E = x \ x, F = f \ (x \ x)}$ ${\ displaystyle \ operatorname {de-lambda} [E] = \ operatorname {de-lambda} [F]}$ ${\ displaystyle \ operatorname {de-lambda} [x \ x] = \ operatorname {de-lambda} [f \ (x \ x)]}$
2	${\ displaystyle \ operatorname {let} p: \ operatorname {de-lambda} [p \ f] = \ operatorname {let} x: \ operatorname {de-lambda} [x \ x] = \ operatorname {de-lambda} [f \ (x \ x)] \ operatorname {in} f \ (x \ x) \ operatorname {in} p}$ ${\ displaystyle \ operatorname {de-lambda} [x \ x], \ operatorname {de-lambda} [f \ (x \ x)]}$ ${\ displaystyle \ operatorname {de-lambda} [p \ f], \ operatorname {de-lambda} [M_ {1} \ N_ {1}], \ operatorname {de-lambda} [M_ {2} \ N_ { 2}],}$ ${\ displaystyle M_ {1} = p, N_ {1} = f, M_ {2} = x, N_ {2} = x, M_ {3} = f, N_ {3} = x \ x}$ ${\ displaystyle \ operatorname {de-lambda} [M_ {1}] \ \ operatorname {de-lambda} [N_ {1}], \ operatorname {de-lambda} [M_ {2}] \ \ operatorname {de- lambda} [N_ {2}], \ operatorname {de-lambda} [M_ {3}] \ \ operatorname {de-lambda} [N_ {3}]}$ ${\ displaystyle \ operatorname {de-lambda} [p] \ \ operatorname {de-lambda} [f], \ operatorname {de-lambda} [x] \ \ operatorname {de-lambda} [x], \ operatorname { de-lambda} [f] \ \ operatorname {de-lambda} [x] \ \ operatorname {de-lambda} [x]}$
1	${\ displaystyle \ operatorname {let} p: \ operatorname {de-lambda} [p] \ \ operatorname {de-lambda} [f] = \ operatorname {let} x: \ operatorname {de-lambda} [x] \ \ operatorname {de-lambda} [x] = \ operatorname {de-lambda} [f] \ (\ operatorname {de-lambda} [x] \ \ operatorname {de-lambda} [x]) \ operatorname {in} f \ (x \ x)] \ operatorname {in} p}$ ${\ displaystyle \ operatorname {de-lambda} [V]}$ ${\ displaystyle V}$
	${\ displaystyle \ operatorname {let} p: p \ f = \ operatorname {let} x: x \ x = f \ (x \ x) \ operatorname {in} f \ (x \ x)] \ operatorname {in} p}$

Konvertering från låt till lambda uttryck

Dessa regler vänder omvandlingen som beskrivs ovan. De konverterar från ett låt -uttryck till ett lambda -uttryck, utan att ändra strukturen. Alla låt -uttryck kan inte konverteras med hjälp av dessa regler. Reglerna förutsätter att uttrycken redan är ordnade som om de hade genererats av de-lambda .

1. ${\ displaystyle \ operatorname {get-lambda} [F, G \ V = E] = \ operatorname {get-lambda} [F, G = \ lambda VE]}$
2. ${\ displaystyle \ operatorname {get-lambda} [F, F = E] = \ operatorname {de-let} [E]}$
3. ${\ displaystyle \ operatorname {de-let} [\ lambda VE] \ equiv \ lambda V. \ operatorname {de-let} [E]}$
4. ${\ displaystyle \ operatorname {de-let} [M \ N] \ equiv \ operatorname {de-let} [M] \ \ operatorname {de-let} [N]}$
5. ${\ displaystyle \ operatorname {de-let} [V] \ equiv V}$
6. ${\ displaystyle V \ not \ in FV [\ operatorname {get-lambda} [V, E]] \ to \ operatorname {de-let} [\ operatorname {let} V: E \ \ operatorname {in} V] \ equiv \ operatorname {get-lambda} [V, E]}$
7. ${\ displaystyle V \ not \ in FV [\ operatorname {get-lambda} [V, E]] \ to \ operatorname {de-let} [\ operatorname {let} V: E \ \ operatorname {in} L] \ equiv (\ lambda V. \ operatorname {de-let} [L]) \ \ operatorname {get-lambda} [V, E]}$
8. ${\ displaystyle W \ not \ in \ operatorname {FV} [\ operatorname {get-lambda} [V, E]] \ to \ operatorname {de-let} [\ operatorname {let} V, W: E \ land F \ \ operatorname {in} G] \ equiv \ operatorname {de-let} [\ operatorname {let} V: E \ \ operatorname {in} \ operatorname {let} W: F \ \ operatorname {in} G]}$
9. ${\ displaystyle V \ in \ operatorname {FV} [\ operatorname {get-lambda} [V, E]] \ to \ operatorname {de-let} [\ operatorname {let} V: E \ \ operatorname {in} L ] \ equiv \ operatorname {de-let} [\ operatorname {let} V: V \ V = \ operatorname {get-lambda} [V, E] [V: = V \ V] \ \ operatorname {i} L [ V: = V \ V]]}$
10. ${\ displaystyle W \ in \ operatorname {FV} [\ operatorname {get-lambda} [V, E]] \ to \ operatorname {de-let} [\ operatorname {let} V, W: E \ land F \ \ operatorname {in} L] \ equiv \ operatorname {de-let} [\ operatorname {let} V: V \ W = \ operatorname {get-lambda} [V, E] [V: = V \ W] \ \ operatorname {in} \ operatorname {let} W: F [V: = V \ W] \ \ operatorname {in} L [V: = V \ W]]}$

Det finns ingen exakt strukturell ekvivalent i lambda -beräkning för uthyrningsuttryck som har fria variabler som används rekursivt. I detta fall krävs vissa tillägg av parametrar. Regel 8 och 10 lägger till dessa parametrar.

Reglerna 8 och 10 är tillräckliga för två inbördes rekursiva ekvationer i let -uttrycket. Men de fungerar inte för tre eller flera ömsesidigt rekursiva ekvationer. Det allmänna fallet kräver en extra looping vilket gör metafunktionen lite svårare. Reglerna som följer ersätter reglerna 8 och 10 vid genomförandet av det allmänna ärendet. Regel 8 och 10 har lämnats så att det enklare fallet kan studeras först.

1. lambda -form - Konvertera uttrycket till en kombination av uttryck, var och en av formvariabeln = uttryck .
   1. ${\ displaystyle \ operatorname {lambda-form} [G \ V = E] = \ operatorname {lambda-form} [G = \ lambda VE]}$
   2. ${\ displaystyle \ operatorname {lambda-form} [E \ land F] = \ operatorname {lambda-form} [E] \ land \ operatorname {lambda-form} [F]}$
   3. ${\ displaystyle \ operatorname {lambda-form} [V = E] = V = E}$...... där V är en variabel.
2. lift -vars - Få uppsättningen variabler som behöver X som parameter, eftersom uttrycket har X som en fri variabel.
   1. ${\ displaystyle X \ in \ operatorname {FV} [E] \ to \ operatorname {lift-vars} [X, V = E] = \ {V \}}$
   2. ${\ displaystyle X \ not \ in \ operatorname {FV} [E] \ to \ operatorname {lift-vars} [X, V = E] = \ {\}}$
   3. ${\ displaystyle \ operatorname {lift-vars} [X, E \ land F] = \ operatorname {lift-vars} [X, E] \ cup \ operatorname {lift-vars} [XF]}$
3. sub -vars - För varje variabel i uppsättningen ersätt den med variabeln som tillämpas på X i uttrycket. Detta gör X till en variabel som skickas in som en parameter, istället för att vara en ledig variabel på ekvationens högra sida.
   1. ${\ displaystyle \ operatorname {sub-vars} [E, \ {V \} \ cup S, X] = \ operatorname {sub-vars} [E [V: = V \ X], S, X]}$
   2. ${\ displaystyle \ operatorname {sub-vars} [E, \ {\}, X] = E}$
4. de -let - Lyft varje villkor i E så att X inte är en ledig variabel till höger om ekvationen.
   1. ${\ displaystyle {\ begin {align} L & = \ operatorname {lambda-form} [E] \ land S = \ operatorname {lift-vars} [X, L] \ to \ operatorname {de-let} [\ operatorname { låt} V \ ldots W, X: E \ land F \ \ operatorname {in} G] \\ & \ equiv \ operatorname {de-let} [\ operatorname {let} V \ ldots W: \ operatorname {sub-vars } [L, S, X] \ \ operatorname {in} \ operatorname {let} \ operatorname {sub-vars} [\ operatorname {lambda-form} [F], S, X] \ \ operatorname {in} \ operatorname {sub-vars} [G, S, X]] \ end {align}}}$

Exempel

Till exempel, låt -uttrycket erhållet från Y -kombinatorn ,

${\ displaystyle \ operatorname {let} p: p \ f = \ operatorname {let} x: x \ q = f \ (q \ q) \ \ operatorname {in} f \ (x \ x) \ \ operatorname {in } s}$

konverteras till,

${\ displaystyle \ lambda f. (\ lambda xf \ (x \ x)) \ (\ lambda qf \ (q \ q))}}$

Regel	Lambda uttryck
6	${\ displaystyle \ operatorname {de-let} [\ operatorname {let} p: p \ f = \ operatorname {let} x: x \ q = f \ (q \ q) \ \ operatorname {in} f \ (x \ x) \ \ operatorname {in} p]}$ ${\ displaystyle \ operatorname {de-let} [\ operatorname {let} V: E \ \ operatorname {in} V]}$ ${\ displaystyle V = p, E = p \ f = \ operatorname {let} x: x \ q = f \ (q \ q) \ \ operatorname {in} f \ (x \ x)}$ ${\ displaystyle \ operatorname {get-lambda} [V, E]}$
1	${\ displaystyle \ operatorname {get-lambda} [p, p \ f = \ operatorname {let} x: x \ q = f \ (q \ q) \ \ operatorname {in} f \ (x \ x)]}$ ${\ displaystyle \ operatorname {get-lambda} [F, G \ V = E]}$ ${\ displaystyle F = p, G = p, V = f, E = \ operatorname {let} x: x \ q = f \ (q \ q) \ \ operatorname {in} f \ (x \ x)}$ ${\ displaystyle \ operatorname {get-lambda} [F, G = \ lambda VE]}$
2	${\ displaystyle \ operatorname {get-lambda} [p, p = \ lambda f. \ operatorname {let} x: x \ q = f \ (q \ q) \ \ operatorname {in} f \ (x \ x) ]}}$ ${\ displaystyle \ operatorname {get-lambda} [F, F = E]}$ ${\ displaystyle F = p, E = \ lambda f. \ operatorname {let} x: x \ q = f \ (q \ q) \ \ operatorname {in} f \ (x \ x)}$ ${\ displaystyle \ operatorname {de-let} [E]}$
3	${\ displaystyle \ operatorname {de-let} [\ lambda f. \ operatorname {let} x: x \ q = f \ (q \ q) \ \ operatorname {in} f \ (x \ x)]}$ ${\ displaystyle \ operatorname {de-let} [\ lambda VE]}$ ${\ displaystyle V = f, E = \ operatorname {let} x: x \ q = f \ (q \ q) \ \ operatorname {in} f \ (x \ x)}$ ${\ displaystyle \ lambda V. \ operatorname {de-let} [E]}$
7	${\ displaystyle \ lambda f. \ operatorname {de-let} [\ operatorname {let} x: x \ q = f \ (q \ q) \ \ operatorname {in} f \ (x \ x)]}$ ${\ displaystyle \ operatorname {de-let} [\ operatorname {let} x: x \ q = f \ (q \ q) \ \ operatorname {in} f \ (x \ x)]}$ ${\ displaystyle V \ not \ in FV [\ operatorname {get-lambda} [V, E]] \ to \ operatorname {de-let} [\ operatorname {let} V: E \ \ operatorname {in} L]}$ ${\ displaystyle V = x, E = x \ q = f \ (q \ q), L = f \ (x \ x)}$ ${\ displaystyle (\ lambda V. \ operatorname {de-let} [L]) \ \ operatorname {get-lambda} [V, E]}$
4	${\ displaystyle (\ lambda x. \ operatorname {de-let} [f \ (x \ x)]) \ \ operatorname {get-lambda} [x, x \ q = f \ (q \ q)]}$ ${\ displaystyle \ operatorname {de-let} [f \ (x \ x)]}$ ${\ displaystyle \ operatorname {de-let} [M \ N]}$ ${\ displaystyle M = f, N = (x \ x)}$ ${\ displaystyle \ operatorname {de-let} [M] \ \ operatorname {de-let} [N]}$ ${\ displaystyle \ operatorname {de-let} [f] \ \ operatorname {de-let} [x \ x]}$
4	${\ displaystyle (\ lambda x. \ operatorname {de-let} [f] \ \ operatorname {de-let} [x \ x]) \ \ operatorname {get-lambda} [x, x \ q = f \ ( q \ q)]}$ ${\ displaystyle \ operatorname {de-let} [x \ x]}$ ${\ displaystyle \ operatorname {de-let} [M \ N]}$ ${\ displaystyle M = x, N = x}$ ${\ displaystyle \ operatorname {de-let} [M] \ \ operatorname {de-let} [N]}$ ${\ displaystyle \ operatorname {de-let} [x] \ \ operatorname {de-let} [x]}$
5	${\ displaystyle (\ lambda x. \ operatorname {de-let} [f] \ (\ operatorname {de-let} [x] \ \ operatorname {de-let} [x])) \ \ operatorname {get-lambda } [x, x \ q = f \ (q \ q)]}$ ${\ displaystyle \ operatorname {de-let} [V]}$ ${\ displaystyle V}$
1	${\ displaystyle (\ lambda xf \ (x \ x)) \ \ operatorname {get-lambda} [x, x \ q = f \ (q \ q)]}$ ${\ displaystyle \ operatorname {get-lambda} [x, x \ q = f \ (q \ q)]}$ ${\ displaystyle \ operatorname {get-lambda} [F, G \ V = E]}$ ${\ displaystyle F = x, G = x, V = q, E = f \ (q \ q)}$ ${\ displaystyle \ operatorname {get-lambda} [F, G = \ lambda VE]}$ ${\ displaystyle \ operatorname {get-lambda} [x, x = \ lambda qf \ (q \ q)]}$
2	${\ displaystyle (\ lambda xf \ (x \ x)) \ \ operatorname {get-lambda} [x, x = \ lambda qf \ (q \ q)]}$ ${\ displaystyle \ operatorname {get-lambda} [x, x = \ lambda qf \ (q \ q)]}$ ${\ displaystyle \ operatorname {get-lambda} [F, F = E]}$ ${\ displaystyle F = x, E = \ lambda qf \ (q \ q)}$ ${\ displaystyle \ operatorname {de-let} [E]}$ ${\ displaystyle \ operatorname {de-let} [\ lambda qf \ (q \ q)]}$
3	${\ displaystyle (\ lambda xf \ (x \ x)) \ \ operatorname {de-let} [\ lambda qf \ (q \ q)]}$ ${\ displaystyle \ operatorname {de-let} [\ lambda qf \ (q \ q)]}$ ${\ displaystyle \ operatorname {de-let} [\ lambda VE]}$ ${\ displaystyle V = q, E = f \ (q \ q)}$ ${\ displaystyle \ lambda V. \ operatorname {de-let} [E]}$ ${\ displaystyle \ lambda q. \ operatorname {de-let} [f \ (q \ q)]}$
4	${\ displaystyle (\ lambda xf \ (x \ x)) \ (\ lambda q. \ operatorname {de-let} [f \ (q \ q)])}}$ ${\ displaystyle \ operatorname {de-let} [f \ (q \ q)]}$ ${\ displaystyle \ operatorname {de-let} [M_ {1} \ N_ {1}]}$ ${\ displaystyle M_ {1} = f, N_ {1} = q \ q}$ ${\ displaystyle \ operatorname {de-let} [M_ {1}] \ \ operatorname {de-let} [N_ {1}]}$ ${\ displaystyle \ operatorname {de-let} [f] \ \ operatorname {de-let} [q \ q]}$ ${\ displaystyle \ operatorname {de-let} [M_ {2} \ N_ {2}]}$ ${\ displaystyle M_ {2} = q, N_ {2} = q}$ ${\ displaystyle \ operatorname {de-let} [q] \ \ operatorname {de-let} [q]}$
5	${\ displaystyle (\ lambda xf \ (x \ x)) \ (\ lambda q. \ operatorname {de-let} [f] \ (\ operatorname {de-let} [q] \ \ operatorname {de-let} [q]))}}$ ${\ displaystyle \ operatorname {de-let} [V]}$ ${\ displaystyle}$ ${\ displaystyle V}$
	${\ displaystyle (\ lambda xf \ (x \ x)) \ (\ lambda qf \ (q \ q))}}$

För ett andra exempel, ta den lyftade versionen av Y -kombinatorn ,

${\ displaystyle \ operatorname {let} p, q: p \ f \ x = f \ (x \ x) \ land q \ p \ f = (p \ f) \ (p \ f) \ \ operatorname {in} q \ p}$

konverteras till,

${\ displaystyle (\ lambda p. (\ lambda qq \ p) \ \ lambda p. \ lambda f. (p \ f) \ (p \ f)) \ \ lambda f. \ lambda xf \ (x \ x) }$

Regel	Lambda uttryck
8	${\ displaystyle \ operatorname {de-let} [\ operatorname {let} p, q: p \ f \ x = f \ (x \ x) \ land q \ p \ f = (p \ f) \ (p \ f) \ \ operatorname {in} q \ p]}$
7	${\ displaystyle \ operatorname {de-let} [\ operatorname {let} p: p \ f \ x = f \ (x \ x) \ \ operatorname {in} \ operatorname {let} q: q \ p \ f = (p \ f) \ (p \ f) \ \ operatorname {in} q \ p]}$
1, 2	${\ displaystyle (\ lambda p. \ operatorname {de-let} [\ operatorname {let} q: q \ p \ f = (p \ f) \ (p \ f) \ \ operatorname {in} q \ p] ) \ \ operatorname {get-lambda} [p, p \ f \ x = f \ (x \ x)]}$
7, 4, 5	${\ displaystyle (\ lambda p. \ operatorname {de-let} [\ operatorname {let} q: q \ p \ f = (p \ f) \ (p \ f) \ \ operatorname {in} q \ p] ) \ \ lambda f. \ lambda xf \ (x \ x)}$
1, 2	${\ displaystyle (\ lambda p. (\ lambda qq \ p) \ \ operatorname {get-lambda} [q, q \ p \ f = (p \ f) \ (p \ f)]) \ \ lambda f. \ lambda xf \ (x \ x)}$
	${\ displaystyle (\ lambda p. (\ lambda qq \ p) \ \ lambda p. \ lambda f. (p \ f) \ (p \ f)) \ \ lambda f. \ lambda xf \ (x \ x) }$

För ett tredje exempel översättningen av,

${\ displaystyle \ operatorname {let} x: x \ f = f \ (x \ f) \ \ operatorname {in} x}$

är,

${\ displaystyle (\ lambda xx \ x) \ (\ lambda x. \ lambda ff \ (x \ x \ f))}$

Regel	Lambda uttryck
9	${\ displaystyle \ operatorname {let} x: x \ f = f \ (x \ f) \ \ operatorname {in} x}$
1	${\ displaystyle \ operatorname {let} x: \ operatorname {get-lambda} [x, x \ f = f \ (x \ f)] [x: = x \ x] \ \ operatorname {in} x [x: = x \ x]}$
2	${\ displaystyle \ operatorname {let} x: \ operatorname {get-lambda} [x, x = \ lambda ff \ (x \ f)] [x: = x \ x] \ \ operatorname {in} x \ x}$
	${\ displaystyle \ operatorname {let} x: (x = \ lambda ff \ (x \ f)) [x: = x \ x] \ \ operatorname {in} x \ x}$
7	${\ displaystyle \ operatorname {let} x: (x \ x = \ lambda ff \ (x \ x \ f)) \ \ operatorname {in} x \ x}$
1	${\ displaystyle (\ lambda xx \ x) \ \ operatorname {get-lambda} [x, x \ x = \ lambda ff \ (x \ x \ f)]}$
2	${\ displaystyle (\ lambda xx \ x) \ \ operatorname {get-lambda} [x, x = \ lambda x. \ lambda ff \ (x \ x \ f)]}$
	${\ displaystyle (\ lambda xx \ x) \ (\ lambda x. \ lambda ff \ (x \ x \ f))}$

Nyckelpersoner

• Dana Scott

Se även

• Omfattning (datavetenskap)
• Lambda lyft
• Fixat-punkts kombinator
• Lambda -kalkyl
• Currys paradox
• Deduktiv lambda -kalkyl
• Begränsning av logisk programmering
• Minskning av algebraiska värdesatser

Referenser