Nechť výraz - Let expression

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Nechť výraz"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Březen 2017) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

V počítačové vědě, a „nech“ výraz spolupracovníci a funkce definice s omezením rozsah.

The „nech“ výraz mohou být také definovány v matematice, kde spojuje booleovskou podmínku s omezeným rozsahem.

Výraz „let“ lze považovat za a lambda abstrakce aplikován na hodnotu. V rámci matematiky lze výraz let také považovat za a spojení výrazů v rámci existenční kvantifikátor což omezuje rozsah proměnné.

Výraz let je přítomen v mnoha funkčních jazycích, což umožňuje místní definici výrazu pro použití při definování jiného výrazu. Let-výraz je v některých funkčních jazycích přítomen ve dvou formách; nechat nebo „nechat rec“. Let rec je rozšíření jednoduchého výrazu let, který používá kombinátor pevných bodů provádět rekurze.

Dějiny

Dana Scott je Jazyk LCF^[1] byla etapou ve vývoji lambda kalkulu do moderních funkčních jazyků. Tento jazyk zavedl výraz let, který se od té doby objevil ve většině funkčních jazyků.

Jazyky Systém,^[2] ML a nověji Haskell^[3] zdědili letové výrazy z LCF.

Stavové imperativní jazyky jako ALGOL a Pascal v podstatě implementovat let výraz, implementovat omezený rozsah funkcí v blokových strukturách.^{[Citace je zapotřebí ]}

Úzce související "kde"klauzule, spolu s její rekurzivní variantou"kde rec", se již objevil v Peter Landin je Mechanické vyhodnocení výrazů.^[4]

Popis

Výraz „let“ definuje funkci nebo hodnotu pro použití v jiném výrazu. Kromě konstrukce používané v mnoha funkčních programovacích jazycích se jedná o konstrukci přirozeného jazyka, která se často používá v matematických textech. Jedná se o alternativní syntaktický konstrukt pro klauzuli where.

V obou případech je celý konstrukt výrazem, jehož hodnota je 5. Stejně jako Jestliže pak jinak typ vrácený výrazem nemusí být nutně booleovský.

Letový výraz má 4 hlavní formy,

Ve funkčních jazycích nechat výraz definuje funkce, které lze ve výrazu volat. Rozsah názvu funkce je omezen na strukturu výrazu let.

V matematice výraz let definuje podmínku, která je omezením výrazu. Syntaxe může také podporovat deklaraci existenčně kvantifikovaných proměnných lokálních k výrazu let.

Terminologie, syntaxe a sémantika se liší jazyk od jazyka. v Systém, nechat se používá pro jednoduchou formu a nechť rec pro rekurzivní formu. V ML nechat označí pouze začátek bloku deklarací pomocí zábava označení začátku definice funkce. V Haskellu, nechat může být vzájemně rekurzivní, přičemž kompilátor přijde na to, co je potřeba.

Definice

A lambda abstrakce představuje funkci bez názvu. Tohle je zdroj nekonzistence v definici lambda abstrakce. Lambda abstrakce však mohou být složeny tak, aby představovaly funkci se jménem. V této formě je nekonzistence odstraněna. Termín lambda,

${ displaystyle ( lambda f.z) ( lambda x.y)}$

je ekvivalentní definování funkce ${ displaystyle f}$ podle ${ displaystyle f x = y}$ ve výrazu ${ displaystyle z}$, které lze zapsat jako nechat výraz;

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

Let výraz je pochopitelný jako výraz přirozeného jazyka. Výraz let představuje náhradu proměnné za hodnotu. Pravidlo substituce popisuje důsledky rovnosti jako substituci.

Nechť definice v matematice

v matematika the nechat výraz je popsán jako spojení výrazů. Ve funkčních jazycích se výraz let také používá k omezení rozsahu. V matematice je rozsah popsán kvantifikátory. Let výraz je konjunkce v existenciálním kvantifikátoru.

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

kde E a F jsou typu Boolean.

The nechat výraz umožňuje použít substituci na jiný výraz. Tuto substituci lze použít v omezeném rozsahu na dílčí výraz. Přirozené použití výrazu let je v aplikaci v omezeném rozsahu (tzv lambda klesá ). Tato pravidla definují, jak může být rozsah omezen;

${ displaystyle { begin {cases} x not in operatorname {FV} (E) land x in operatorname {FV} (F) implikuje 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) implikuje 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) implikuje operatorname {let} x: G operatorname {in} E F = E F end {případy}}}$

kde F je není typu Boolean. Z této definice lze odvodit následující standardní definici výrazu let, jak se používá ve funkčním jazyce.

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

Pro jednoduchost značka specifikující existenční proměnnou, ${ displaystyle x:}$, bude z výrazu vynechán, pokud je to zřejmé z kontextu.

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

Derivace

Chcete-li odvodit tento výsledek, nejprve předpokládejte,

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

pak

${ displaystyle { begin {zarovnáno} 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 {zarovnáno}}}$

Pomocí pravidla substituce

${ displaystyle { begin {zarovnáno} & 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] & implikuje L z [x: = y] end {zarovnáno}}}$

tak pro všechny L,

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

Nechat ${ displaystyle L X = (X = K)}$ kde K. je nová proměnná. pak,

${ displaystyle ( operatorname {let} x: x = y operatorname {in} z) = K implikuje z [x: = y] = K}$

Tak,

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

Ale z matematické interpretace redukce beta,

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

Zde, pokud je y funkcí proměnné x, není to stejné x jako v z. Může být použito alfa přejmenování. Takže musíme mít,

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

tak,

${ displaystyle x not in operatorname {FV} (y) implikuje operatorname {let} x: x = y operatorname {in} z = ( lambda x.z) y}$

Tento výsledek je reprezentován ve funkčním jazyce ve zkrácené formě, kde je význam jednoznačný;

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

Zde proměnná X je implicitně uznána jako součást rovnice definující x a proměnná v existenciálním kvantifikátoru.

Žádné zvedání z Boolean

Rozpor nastává, pokud je E definováno ${ displaystyle E = neg}$. V tomto případě,

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

se stává

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

a pomocí,

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

${ displaystyle ( existuje xG země neg F) = neg ( existuje xG země F)}$

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

To je nepravdivé, pokud G je nepravdivé. Aby se zabránilo tomuto rozporu F není povoleno být typu Boolean. Pro booleovské F správné tvrzení pravidla zrušení používá implikaci místo rovnosti,

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

Může se zdát divné, že pro Boolean platí jiné pravidlo než jiné typy. Důvodem je to, že pravidlo,

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

platí pouze tam, kde F je booleovský. Kombinace těchto dvou pravidel vytváří rozpor, takže pokud jedno pravidlo platí, druhé nikoli.

Spojování let výrazů

Nechť výrazy mohou být definovány s více proměnnými,

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

pak to může být odvozeno,

${ Displaystyle x not in FV (E) implikuje ( existuje v cdots existuje w existuje xE land F) iff ( existuje v cdots existuje w (E land existuje xF)) }$

tak,

${ displaystyle x not in FV (E) implikuje ( 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)}$

Zákony týkající se lambda kalkulu a nechat výrazy

The Snížení Eta dává pravidlo pro popis lambda abstrakcí. Toto pravidlo spolu se dvěma výše odvozenými zákony definuje vztah mezi lambda kalkulem a výrazy let.

${ displaystyle { begin {array} {l | l} { textbf {Name}} & { textbf {Law}} hline { text {Eta-redukční ekvivalence}} & f x = y equiv f = lambda xy { text {Let-lambda equivalence}} & f not in FV (E) implies ( operatorname {let} f: f = E operatorname {in} L equiv ( lambda fL) E) { text {(kde}} f { text {je název proměnné.)}} { text {Let combination}} & x not in FV (E) implies ( operatorname {let} v, ..., w, x: E land F operatorname {in} L equiv operatorname {let} v, ..., w: E operatorname {in} operatorname {let} x: F operatorname {in} L) end {array}}}$

Nechť je definice definována z lambda kalkulu

Aby se zabránilo Potenciální problémy spojené s matematická definice, Dana Scott původně definoval nechat výraz z lambda kalkulu. To lze považovat za zdola nahoru nebo za konstruktivní definici nechat výraz, na rozdíl od shora dolů, nebo axiomatická matematická definice.

Jednoduché, nerekurzivní nechat výraz byl definován jako syntaktický cukr pro lambda abstrakci aplikovanou na výraz. V této definici

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

Jednoduché nechat definice výrazu byla poté rozšířena, aby umožnila rekurzi pomocí kombinátor pevných bodů.

Kombinátor s pevným bodem

The kombinátor pevných bodů mohou být reprezentovány výrazem,

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

Toto vyjádření lze převést na lambda výraz. Abstrakce lambda nepodporuje odkaz na název proměnné v použitém výrazu, takže X musí být předáno jako parametr do X.

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

Pomocí pravidla eta redukce

${ displaystyle f x = y equiv f = lambda x.y}$

dává,

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

Let výraz může být vyjádřen jako lambda abstrakce pomocí,

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

dává,

${ Displaystyle lambda f. ( lambda x.x x) ( lambda x.f (x x))}$

Toto je možná nejjednodušší implementace kombinátoru pevných bodů v lambda kalkulu. Jedna redukce beta však dává symetrickější formu Curryho Y kombinátoru.

${ Displaystyle lambda f. ( lambda x.f (x x)) ( lambda x.f (x x))}$

Rekurzivní letový výraz

Rekurzivní nechat výraz s názvem „let rec“ je definován pomocí kombinátoru Y pro rekurzivní výrazy let.

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

Vzájemně rekurzivní letový výraz

Tento přístup je poté zobecněn na podporu vzájemné rekurze. Vzájemně rekurzivní výraz let může být složen přeuspořádáním výrazu, aby se odstranily všechny podmínky. Toho je dosaženo nahrazením více definic funkcí jednou definicí funkce, která nastaví seznam proměnných rovný seznamu výrazů. Verze kombinátoru Y s názvem Y * polyvariadický kombinátor fixních bodů^[5] se pak používá k výpočtu pevného bodu všech funkcí současně. Výsledkem je vzájemně rekurzivní implementace nechat výraz.

Více hodnot

Pro vyjádření hodnoty, která je členem množiny, lze použít výraz let

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

V rámci aplikace funkcí, z jednoho nechat výraz do druhého,

${ displaystyle ( operatorname {let} x v X operatorname {in} x) ( operatorname {let} y v Y operatorname {in} y)}$

${ displaystyle = operatorname {let} x in X land y in Y operatorname {in} x y}$

${ displaystyle = operatorname {let} (x, y) v X krát Y operatorname {v} x y}$

Pro použití výrazu let na sebe ale platí jiné pravidlo.

${ displaystyle ( operatorname {let} x v X operatorname {in} x) ( operatorname {let} x v X operatorname {in} x)}$

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

Zdá se, že neexistuje žádné jednoduché pravidlo pro kombinování hodnot. Vyžaduje se obecná forma vyjádření, která představuje proměnnou, jejíž hodnota je členem sady hodnot. Výraz by měl být založen na proměnné a množině.

Aplikace funkcí použitá v tomto formuláři by měla dát další výraz ve stejné podobě. Tímto způsobem lze s jakýmkoli výrazem na funkcích více hodnot zacházet, jako by měl jednu hodnotu.

Nestačí, aby formulář představoval pouze množinu hodnot. Každá hodnota musí mít podmínku, která určuje, kdy má výraz hodnotu. Výsledný konstrukt je sada dvojic podmínek a hodnot, která se nazývá „sada hodnot“. Vidět zúžení množin algebraických hodnot.

Pravidla pro převod mezi lambda kalkulem a výrazy let

Meta-funkce bude uveden popis konverze mezi lambda a nechat výrazy. Meta-funkce je funkce, která bere program jako parametr. Program je údajem pro metaprogram. Program a meta program jsou na různých metaúrovních.

K rozlišení programu od meta programu se použijí následující konvence,

• Hranaté závorky [] budou použity k reprezentaci aplikace funkcí v meta programu.
• Velká písmena budou použita pro proměnné v meta programu. Malá písmena představují proměnné v programu.
• ${ displaystyle equiv}$ bude použito pro rovné v meta programu.

Pro zjednodušení bude použito první pravidlo, že se shodují. Pravidla také předpokládají, že výrazy lambda byly předem zpracovány, takže každá abstrakce lambda má jedinečný název.

Používá se také operátor substituce. Výraz ${ displaystyle L [G: = S]}$ znamená nahradit každý výskyt G v L podle S a vrátit výraz. Použitá definice je rozšířena o náhradu výrazů z definice uvedené na Lambda kalkul strana. Shoda výrazů by měla porovnávat výrazy pro alfa ekvivalenci (přejmenování proměnných).

Převod z lambda na nechat výrazy

Následující pravidla popisují, jak převést z výrazu lambda na a nechat výraz bez změny struktury.

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 P.E] 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 { v} 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 { let} V, W: E land F operatorname {in} G}$
8. ${ displaystyle operatorname {let-combine} [ operatorname {let} V: E operatorname {in} F] equiv operatorname {let} V: E operatorname {in} F}$

Pravidlo 6 vytváří jedinečnou proměnnou V jako název funkce.

Příklad

Například Y kombinátor,

${ Displaystyle lambda f. ( lambda x.f (x x)) ( lambda x.f (x x))}$

je převeden na,

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

Pravidlo	Lambda výraz
6	${ displaystyle operatorname {de-lambda} [ lambda f. ( lambda x.f (x x)) ( lambda x.f (x x))]}$ ${ displaystyle V not in operatorname {FV} [ lambda F.E] to operatorname {de-lambda} [ lambda F.E]}$ ${ Displaystyle V = p, F = f, E = ( lambda x.f (x x)) ( lambda x.f (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 x.f (x x)) ( lambda x.f (x x))]}$ ${ displaystyle operatorname {de-lambda} [E = F]}$ ${ Displaystyle E = p f, F = ( lambda x.f (x x)) ( lambda x.f (x x))}$ ${ displaystyle operatorname {de-lambda} [E] = operatorname {de-lambda} [F]}$ ${ displaystyle operatorname {de-lambda} [p f] = operatorname {de-lambda} [( lambda x.f (x x)) ( lambda x.f (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 {v} 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 {v} p]}$ ${ displaystyle operatorname {de-lambda} [( lambda x.f (x x)) ( lambda x.f (x x))]}$ ${ displaystyle operatorname {de-lambda} [( lambda F.E) L]}$ ${ displaystyle F = x, E = f (x x), L = ( lambda x.f (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 x.f (x x)]}$ ${ displaystyle operatorname {de-lambda} [F = lambda P.E]}$ ${ 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 {let-combine} [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 {let-combine} [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}$

Převod z let na lambda výrazy

Tato pravidla zvrátí výše popsanou konverzi. Konvertují z a nechat výraz na výraz lambda bez změny struktury. Pomocí těchto pravidel nelze převést všechny letové výrazy. Pravidla předpokládají, že výrazy jsou již uspořádány, jako by byly generovány de-lambda.

1. ${ displaystyle operatorname {get-lambda} [F, G V = E] = operatorname {get-lambda} [F, G = lambda V.E]}$
2. ${ displaystyle operatorname {get-lambda} [F, F = E] = operatorname {de-let} [E]}$
3. ${ displaystyle operatorname {de-let} [ lambda V.E] 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 {in} 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]]}$

V lambda kalkulu neexistuje žádný přesný strukturní ekvivalent nechat výrazy, které mají volné proměnné, které se používají rekurzivně. V tomto případě je nutné přidat nějaké parametry. Pravidla 8 a 10 přidávají tyto parametry.

Pravidla 8 a 10 jsou dostatečná pro dvě vzájemně se rekurzivní rovnice v nechat výraz. Nebudou však fungovat pro tři nebo více vzájemně rekurzivních rovnic. Obecný případ vyžaduje další úroveň opakování, což meta funkci trochu ztěžuje. Následující pravidla nahrazují pravidla 8 a 10 při provádění obecného případu. Pravidla 8 a 10 byla ponechána, aby bylo možné nejprve prostudovat jednodušší případ.

1. lambda forma - Převést výraz na spojení výrazů, každý z formulářů proměnná = výraz.
   1. ${ displaystyle operatorname {lambda-form} [G V = E] = operatorname {lambda-form} [G = lambda V.E]}$
   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}$ ...... kde PROTI je proměnná.
2. lift-vars - Získejte sadu proměnných, které potřebujete X jako parametr, protože výraz má X jako volná proměnná.
   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} [X.F]}$
3. dílčí var - Pro každou proměnnou v sadě ji nahraďte proměnnou aplikovanou na X ve výrazu. To dělá X proměnná předaná jako parametr, místo aby byla volnou proměnnou na pravé straně rovnice.
   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 - Výtah každá podmínka v E aby X není volná proměnná na pravé straně rovnice.
   1. ${ displaystyle L = operatorname {lambda-form} [E] land S = operatorname {lift-vars} [X, L] to operatorname {de-let} [ operatorname {let} V ldots W , X: E land F operatorname {in} G]}$

${ displaystyle 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]]}$

Příklady

Například nechat výraz získaný z Y kombinátor,

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

je převeden na,

${ Displaystyle lambda f. ( lambda x.f (x x)) ( lambda q.f (q q))}$

Pravidlo	Lambda výraz
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 V.E]}$
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 V.E]}$ ${ 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 x.f (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 V.E]}$ ${ displaystyle operatorname {get-lambda} [x, x = lambda q.f (q q)]}$
2	${ displaystyle ( lambda x.f (x x)) operatorname {get-lambda} [x, x = lambda q.f (q q)]}$ ${ displaystyle operatorname {get-lambda} [x, x = lambda q.f (q q)]}$ ${ displaystyle operatorname {get-lambda} [F, F = E]}$ ${ displaystyle F = x, E = lambda q.f (q q)}$ ${ displaystyle operatorname {de-let} [E]}$ ${ displaystyle operatorname {de-let} [ lambda q.f (q q)]}$
3	${ displaystyle ( lambda x.f (x x)) operatorname {de-let} [ lambda q.f (q q)]}$ ${ displaystyle operatorname {de-let} [ lambda q.f (q q)]}$ ${ displaystyle operatorname {de-let} [ lambda V.E]}$ ${ 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 x.f (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 V}$
	${ displaystyle ( lambda x.f (x x)) ( lambda q.f (q q))}$