Lambda kalkul - Lambda calculus

Lambda kalkul (také psáno jako λ-kalkul) je formální systém v matematická logika za vyjádření výpočet na základě funkce abstrakce a aplikace pomocí proměnné vazba a substituce. Je to univerzální model výpočtu které lze použít k simulaci libovolného Turingův stroj. Byl zaveden matematikem Alonzo Church ve třicátých letech minulého století jako součást svého výzkumu základy matematiky.

Lambda kalkul se skládá z konstrukce lambda výrazů a provedení redukčních operací na nich. V nejjednodušší formě lambda kalkulu jsou termíny vytvářeny pouze pomocí následujících pravidel:

produkující výrazy jako: (λX.λy. (λz. (λX.z x) (λy.z y)) (x y)). Závorky lze zrušit, pokud je výraz jednoznačný. U některých aplikací mohou být zahrnuty výrazy pro logické a matematické konstanty a operace.

Mezi operace redukce patří:

Li De Bruijn indexování se použije, pak již není nutná α-konverze, protože nedojde ke kolizím jmen. Li opakovaná aplikace kroků redukce nakonec skončí, poté Církev – Rosserova věta bude produkovat a β-normální forma.

Názvy proměnných nejsou nutné, pokud používáte univerzální funkci lambda, například Iota a Jot, který může vytvořit jakékoli chování funkce voláním na sebe v různých kombinacích.

Vysvětlení a aplikace

Lambda kalkul je Turing dokončen, to znamená, že je univerzální model výpočtu které lze použít k simulaci libovolného Turingův stroj.^[1] Jeho jmenovec, řecké písmeno lambda (λ), se používá v výrazy lambda a lambda podmínky naznačit vazba proměnná v a funkce.

Lambda kalkul může být bez typu nebo napsaný. V zadaném lambda kalkulu lze funkce použít, pouze pokud jsou schopné přijímat „typ“ dat daného vstupu. Zadané lambda kameny jsou slabší než netypický lambda kalkul, který je primárním předmětem tohoto článku, v tom smyslu zadaný lambda kalkul může vyjádřit méně než může netypovaný počet, ale na druhou stranu zadané lambda kalkly umožňují dokázat více věcí; v jednoduše zadaný lambda kalkul je to například věta, že každá strategie hodnocení končí pro každý jednoduše zadaný termín lambda, zatímco hodnocení netypovaných termínů lambda nemusí být ukončeno. Jedním z důvodů, proč existuje mnoho různých zadaných lambda kalkulů, byla touha dělat více (toho, co dokáže netypovaný počet), aniž by se vzdal možnosti dokázat silné věty o kalkulu.

Lambda kalkul má aplikace v mnoha různých oblastech v matematika, filozofie,^[2] lingvistika,^[3][4] a počítačová věda.^[5] Lambda kalkul hraje důležitou roli ve vývoji teorie programovacích jazyků. Funkční programovací jazyky implementovat lambda kalkul. Lambda kalkul je také aktuálním výzkumným tématem v Teorie kategorií.^[6]

Dějiny

Lambda kalkul zavedl matematik Alonzo Church ve třicátých letech v rámci vyšetřování základy matematiky.^[7][A] Ukázalo se, že původní systém byl logicky nekonzistentní v roce 1935, kdy Stephen Kleene a J. B. Rosser vyvinul Paradox Kleene – Rosser.^[8][9]

Následně v roce 1936 Church izoloval a publikoval jen část relevantní pro výpočet, čemu se nyní říká netypický lambda kalkul.^[10] V roce 1940 také představil výpočetně slabší, ale logicky konzistentní systém, známý jako jednoduše zadaný lambda kalkul.^[11]

Až do šedesátých let, kdy byl vyjasněn jeho vztah k programovacím jazykům, byl lambda kalkul pouze formalismem. Díky Richard Montague a další aplikace lingvistů v sémantice přirozeného jazyka si lambda kalkul začal vážit úctyhodného místa v obou lingvistice^[12] a počítačové vědy.^[13]

Původ symbolu lambda

O důvodech, proč církev použila řecký dopis, se vede trochu polemiky lambda (λ) jako označení pro abstrakci funkce v lambda kalkulu, možná částečně kvůli protichůdným vysvětlením samotného církve. Podle Cardone a Hindley (2006):

Mimochodem, proč církev zvolila notaci „λ“? V [nepublikovaném dopise Haraldovi Dicksonovi z roku 1964] jasně uvedl, že to pochází ze zápisu „${displaystyle {hat {x}}}$”Používá se pro abstrakci třídy uživatelem Whitehead a Russell tím, že nejprve upravíte „${displaystyle {hat {x}}}$“Až„ ∧${displaystyle x}$”, Aby se odlišila abstrakce funkce od abstrakce třídy, a poté se pro snadný tisk změní„ ∧ “na„ λ “.

Tento původ byl také popsán v [Rosser, 1984, str. 338]. Na druhou stranu, v pozdějších letech církev řekla dvěma tazatelům, že volba byla náhodnější: byl potřeba symbol a náhodně byl vybrán λ.

Dana Scott se této kontroverzi rovněž věnoval na různých veřejných přednáškách.^[14]Scott líčí, že kdysi položil otázku ohledně původu symbolu lambda církevnímu zeťovi Johnovi Addisonovi, který svému tchánovi napsal pohlednici:

Vážený pane profesore,

Russell měl operátor iota, Hilbert měl operátor epsilon. Proč jste si vybrali operátora lambda?

Podle Scotta celá Churchova odpověď spočívala v vrácení pohlednice s následující anotací: “eeny, meeny, miny, moe ".

Neformální popis

Tato část obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale jeho zdroje zůstávají nejasné, protože mu chybí vložené citace. Prosím pomozte zlepšit tuto část představuji přesnější citace. (září 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Motivace

Vypočitatelné funkce jsou základním pojmem v informatice a matematice. Lambda kalkul poskytuje jednoduchý sémantika pro výpočet, což umožňuje formální studium vlastností výpočtu. Lambda kalkul obsahuje dvě zjednodušení, která tuto sémantiku zjednodušují. Prvním zjednodušením je, že lambda kalkul zachází s funkcemi „anonymně“, aniž by jim dával explicitní názvy. Například funkce

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

lze přepsat dovnitř anonymní forma tak jako

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

(číst jako "n-tice X a y je zmapováno na ${extstyle x ^ {2} + y ^ {2}}$"). Podobně,

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

lze přepsat v anonymní formě jako

${displaystyle xmapsto x}$

kde je vstup jednoduše namapován na sebe.

Druhým zjednodušením je, že lambda kalkul používá pouze funkce jediného vstupu. Běžná funkce, která vyžaduje dva vstupy, například ${extstyle operatorname {square _sum}}$ Funkce může být přepracována do ekvivalentní funkce, která přijímá jeden vstup a jako výstup se vrací další funkce, která zase přijímá jeden vstup. Například,

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

lze přepracovat

${displaystyle xmapsto (ymapsto x ^ {2} + y ^ {2})}$

Tato metoda, známá jako kari, transformuje funkci, která přebírá více argumentů do řetězce funkcí, každý s jediným argumentem.

Aplikace funkcí z ${extstyle operatorname {square _sum}}$ funkce na argumenty (5, 2), výnosy najednou

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

${extstyle = 5 ^ {2} + 2 ^ {2}}$

${extstyle = 29}$,

vzhledem k tomu, že hodnocení kari verze vyžaduje ještě jeden krok

${extstyle {Bigl (} {igl (} xmapsto (ymapsto x ^ {2} + y ^ {2}) {igr)} (5) {Bigr)} (2)}$

${extstyle = (ymapsto 5 ^ {2} + y ^ {2}) (2)}$ // definice ${displaystyle x}$ byl použit s ${displaystyle 5}$ ve vnitřním výrazu. Je to jako β-redukce.

${extstyle = 5 ^ {2} + 2 ^ {2}}$ // definice ${displaystyle y}$ byl použit s ${displaystyle 2}$. Podobně jako u β-redukce.

${extstyle = 29}$

dosáhnout stejného výsledku.

Lambda kalkul

Lambda kalkul se skládá z jazyka lambda podmínky, který je definován určitou formální syntaxí a sadou pravidel transformace, která umožňují manipulaci s lambda výrazy. Na tato pravidla transformace lze pohlížet jako na teorie rovnic nebo jako operační definice.

Jak je popsáno výše, všechny funkce v lambda kalkulu jsou anonymní funkce bez jmen. Přijímají pouze jednu vstupní proměnnou s kari slouží k implementaci funkcí s několika proměnnými.

Lambda podmínky

Syntaxe lambda kalkulu definuje některé výrazy jako platné výrazy lambda kalkulu a některé jako neplatné, stejně jako některé řetězce znaků jsou platné C programy a některé nejsou. Platný výraz lambda kalkulu se nazývá „výraz lambda“.

Následující tři pravidla dávají indukční definice které lze použít k vytvoření všech syntakticky platných výrazů lambda:

• proměnná, ${displaystyle x}$, je sám o sobě platným lambda výrazem
• -li ${displaystyle t}$ je termín lambda a ${displaystyle x}$ je tedy proměnná ${displaystyle (lambda x.t)}$ je lambda výraz (nazývaný abstrakce);
• -li ${displaystyle t}$ a ${displaystyle s}$ jsou tedy výrazy lambda ${displaystyle (ts)}$ je lambda výraz (nazývaný aplikace).

Nic jiného není lambda. Termín lambda je tedy platný právě tehdy, pokud jej lze získat opakovanou aplikací těchto tří pravidel. Některé závorky však lze podle určitých pravidel vynechat. Například nejvzdálenější závorky obvykle nejsou psány. Vidět Zápis níže.

An abstrakce ${displaystyle lambda x.t}$ je definice anonymní funkce, která je schopna přijmout jediný vstup ${displaystyle x}$ a dosadit to do výrazu ${displaystyle t}$Definuje tak anonymní funkci, která trvá ${displaystyle x}$ a vrátí se ${displaystyle t}$. Například, ${displaystyle lambda x.x ^ {2} +2}$ je abstrakce pro funkci ${displaystyle f (x) = x ^ {2} +2}$ pomocí termínu ${displaystyle x ^ {2} +2}$ pro ${displaystyle t}$. Definice funkce s abstrakcí pouze „nastaví“ funkci, ale nevyvolá ji. Abstrakce váže proměnná ${displaystyle x}$ v termínu ${displaystyle t}$.

An aplikace ${displaystyle ts}$ představuje aplikaci funkce ${displaystyle t}$ na vstup ${displaystyle s}$, to znamená, že představuje akt funkce volání ${displaystyle t}$ na vstupu ${displaystyle s}$ k výrobě ${displaystyle t (s)}$.

V lambda kalkulu deklarace proměnné neexistuje žádný koncept. V definici, jako je ${displaystyle lambda x.x + y}$ (tj. ${displaystyle f (x) = x + y}$), lambda kalkul zachází ${displaystyle y}$ jako proměnná, která ještě není definována. Abstrakce ${displaystyle lambda x.x + y}$ je syntakticky platný a představuje funkci, která přidá svůj vstup do dosud neznámého ${displaystyle y}$.

Může být použit bracketing a může být potřebný k vyjasnění pojmů. Například, ${displaystyle lambda x. ((lambda x.x) x)}$ a ${displaystyle (lambda x. (lambda x.x)) x}$ označují různé výrazy (i když se shodou okolností snižují na stejnou hodnotu). Zde první příklad definuje funkci, jejíž výraz lambda je výsledkem použití x na podřízenou funkci, zatímco druhým příkladem je použití nejvzdálenější funkce na vstup x, který vrací podřízenou funkci. Proto oba příklady hodnotí funkce identity ${displaystyle lambda x.x}$.

Funkce, které fungují na funkcích

V lambda kalkulu jsou funkce považovány zahodnoty první třídy ', takže funkce mohou být použity jako vstupy nebo mohou být vráceny jako výstupy z jiných funkcí.

Například, ${displaystyle lambda x.x}$ představuje funkce identity, ${displaystyle xmapsto x}$, a ${displaystyle (lambda x.x) y}$ představuje použitou funkci identity ${displaystyle y}$. Dále, ${displaystyle (lambda x.y)}$ představuje konstantní funkce ${displaystyle xmapsto y}$, funkce, která se vždy vrátí ${displaystyle y}$, bez ohledu na vstup. V lambda kalkulu je aplikace funkcí považována za levo-asociativní, aby ${displaystyle stx}$ prostředek ${displaystyle (st) x}$.

Existuje několik pojmů „ekvivalence“ a „redukce“, které umožňují výrazy „lambda“ „omezit“ na „ekvivalentní“ výrazy lambda.

Alfa ekvivalence

Základní formou ekvivalence, definovatelnou lambda, je alfa ekvivalence. Zachytává intuici, že na konkrétní volbě vázané proměnné v abstrakci (obvykle) nezáleží. ${displaystyle lambda x.x}$ a ${displaystyle lambda y.y}$ jsou alfa-ekvivalentní lambda termíny a oba představují stejnou funkci (funkci identity) ${displaystyle x}$ a ${displaystyle y}$ nejsou alfa-ekvivalent, protože nejsou vázány v abstrakci. V mnoha prezentacích je obvyklé identifikovat alfa-ekvivalentní lambda termíny.

Následující definice jsou nezbytné, aby bylo možné definovat β-redukci:

Volné proměnné

The volné proměnné výrazu jsou ty proměnné, které nejsou vázány abstrakcí. Sada volných proměnných výrazu je definována indukčně:

• Volné proměnné ${displaystyle x}$ jsou jen ${displaystyle x}$
• Sada volných proměnných ${displaystyle lambda x.t}$ je sada volných proměnných ${displaystyle t}$, ale s ${displaystyle x}$ odstraněn
• Sada volných proměnných ${displaystyle ts}$ je spojení sady volných proměnných z ${displaystyle t}$ a soubor volných proměnných ${displaystyle s}$.

Například výraz lambda představující identitu ${displaystyle lambda x.x}$ nemá žádné volné proměnné, ale funkci ${displaystyle lambda x.yx}$ má jednu volnou proměnnou, ${displaystyle y}$.

Náhrady zabraňující zachycení

Předpokládat ${displaystyle t}$, ${displaystyle s}$ a ${displaystyle r}$ jsou lambda výrazy a ${displaystyle x}$ a ${displaystyle y}$ jsou proměnné ${displaystyle t [x: = r]}$ označuje nahrazení ${displaystyle r}$ pro ${displaystyle x}$ v ${displaystyle t}$ v vyhnout se zachycení způsob. To je definováno tak, že:

• ${displaystyle x [x: = r] = r}$;
• ${displaystyle y [x: = r] = y}$ -li ${displaystyle xeq y}$;
• ${displaystyle (ts) [x: = r] = (t [x: = r]) (s [x: = r])}$;
• ${displaystyle (lambda x.t) [x: = r] = lambda x.t}$;
• ${displaystyle (lambda y.t) [x: = r] = lambda y. (t [x: = r])}$ -li ${displaystyle xeq y}$ a ${displaystyle y}$ není ve volných proměnných ${displaystyle r}$. Proměnná ${displaystyle y}$ se říká, že je „čerstvý“ pro ${displaystyle r}$.

Například, ${displaystyle (lambda x.x) [y: = y] = lambda x. (x [y: = y]) = lambda x.x}$, a ${displaystyle ((lambda x.y) x) [x: = y] = ((lambda x.y) [x: = y]) (x [x: = y]) = (lambda x.y) y}$.

Podmínka čerstvosti (vyžaduje to ${displaystyle y}$ není ve volných proměnných ${displaystyle r}$) je zásadní, aby se zajistilo, že substituce nezmění význam funkcí. Například se provede substituce, která ignoruje podmínku čerstvosti: ${displaystyle (lambda x.y) [y: = x] = lambda x. (y [y: = x]) = lambda x.x}$. Tato substituce změní konstantní funkci ${displaystyle lambda x.y}$ do identity ${displaystyle lambda x.x}$ substitucí.

Obecně lze nesplnění podmínky čerstvosti napravit alfa přejmenováním pomocí vhodné čerstvé proměnné. Například přepnutím zpět na náš správný pojem substituce v ${displaystyle (lambda x.y) [y: = x]}$ abstrakci lze přejmenovat pomocí nové proměnné ${displaystyle z}$, získat ${displaystyle (lambda z.y) [y: = x] = lambda z. (y [y: = x]) = lambda z.x}$a význam funkce je zachován substitucí.

β-redukce

Pravidlo β-redukce uvádí, že aplikace formuláře ${displaystyle (lambda x.t) s}$ redukuje na termín ${displaystyle t [x: = s]}$. Zápis ${displaystyle (lambda x.t) s o t [x: = s]}$ se používá k označení toho ${displaystyle (lambda x.t) s}$ β-redukuje na ${displaystyle t [x: = s]}$Například pro každého ${displaystyle s}$, ${displaystyle (lambda x.x) s o x [x: = s] = s}$. To ukazuje ${displaystyle lambda x.x}$ ve skutečnosti je to identita. ${displaystyle (lambda x.y) s o y [x: = s] = y}$, což to dokazuje ${displaystyle lambda x.y}$ je konstantní funkce.

Lambda kalkul lze považovat za idealizovanou verzi funkčního programovacího jazyka Haskell nebo Standardní ML V tomto pohledu odpovídá β-redukce výpočetnímu kroku. Tento krok lze opakovat dalšími β-redukcemi, dokud nezůstanou žádné další aplikace ke snížení. U netypovaného lambda kalkulu, jak je zde uvedeno, nemusí být tento redukční proces ukončen. Zvažte například termín ${displaystyle Omega = (lambda x.xx) (lambda x.xx)}$.Tady ${displaystyle (lambda x.xx) (lambda x.xx) o (xx) [x: = lambda x.xx] = (x [x: = lambda x.xx]) (x [x: = lambda x.xx ]) = (lambda x.xx) (lambda x.xx)}$To znamená, že se termín redukuje sám na sebe v jedné β-redukci, a proto redukční proces nikdy neskončí.

Dalším aspektem netypového počtu lambda je, že nerozlišuje mezi různými druhy dat. Může být například žádoucí napsat funkci, která funguje pouze na číslech. V netypovém lambda kalkulu však neexistuje způsob, jak zabránit použití funkce pravdivostní hodnoty, řetězce nebo jiné objekty bez čísla.

Formální definice

Definice

Lambda výrazy se skládají z:

• proměnné proti₁, proti₂, ...;
• symboly abstrakce λ (lambda) a. (tečka);
• závorky ().

Sada výrazů lambda, Λ, může být definováno indukčně:

1. Li X je tedy proměnná X ∈ Λ.
2. Li X je proměnná a M ∈ Λ, pak (λX.M) ∈ Λ.
3. Li M, N ∈ Λ, pak (M N) ∈ Λ.

Instance pravidla 2 jsou známé jako abstrakce a instance pravidla 3 jsou známé jako aplikace.^[15][16]

Zápis

Aby notace výrazů lambda zůstala přehledná, obvykle se používají následující konvence:

• Vnější závorky jsou vynechány: M N místo (M N).
• Předpokládá se, že aplikace zůstanou asociativní: místo ((M N) P) lze psát M N P.^[17]
• Tělo abstrakce se rozšiřuje co nejvíce vpravo: λX.M N znamená λX.(M N) a ne (λX.M) N.
• Posloupnost abstrakcí je zkrácena: λX.λy.λz.N je zkrácen jako λxyz.N.^[18][17]

Volné a vázané proměnné

O operátoru abstrakce λ se říká, že váže svou proměnnou všude, kde se vyskytuje v těle abstrakce. Proměnné, které spadají do rozsahu abstrakce, jsou považovány za vázaný. Ve výrazu λX.Mčást λX se často nazývá pořadač, jako náznak, že proměnná X je vázán připojením λX na M. Všechny ostatní proměnné se nazývají volný, uvolnit. Například ve výrazu λy.x x y, y je vázaná proměnná a X je volná proměnná. Proměnná je také vázána svou nejbližší abstrakcí. V následujícím příkladu je jediný výskyt X ve výrazu je vázán druhou lambdou: λX.y (λX.z x).

Sada volné proměnné lambda výrazu, M, se označuje jako FV (M) a je definován rekurzí ve struktuře termínů, a to následovně:

1. F V(X) = {X}, kde X je proměnná.
2. FV (λX.M) = FV (M) {X}.
3. F V(M N) = FV (M) ∪ FV (N).^[19]

Říká se, že výraz, který neobsahuje žádné volné proměnné Zavřeno. Uzavřené výrazy lambda jsou také známé jako kombinátory a jsou ekvivalentní výrazům v kombinační logika.

Snížení

Význam výrazů lambda je definován tím, jak lze výrazy omezit.^[20]

Existují tři druhy redukce:

• α-konverze: změna vázaných proměnných;
• β-redukce: použití funkcí na jejich argumenty;
• η-redukce: který zachycuje pojem extenzionality.

Mluvíme také o výsledných ekvivalencích: dva výrazy jsou α-ekvivalent, pokud je lze převést na stejný výraz. Podobně jsou definovány β-ekvivalence a η-ekvivalence.

Termín redex, zkratka pro redukovatelný výraz, odkazuje na dílčí termíny, které lze snížit jedním z pravidel redukce. Například (λX.M) N je β-redex ve vyjádření substituce N pro X v M. Výraz, na který se redex redukuje, se nazývá jeho redukovat; redukce (λX.M) N je M[X := N].

Li X není zdarma v M, λX.M x je také η-redex s redukcí o M.

α-konverze

α-konverze, někdy známá jako α-přejmenování,^[21] umožňuje změnu vázaných názvů proměnných. Například α-konverze λX.X může poskytnout λy.y. Termíny, které se liší pouze α-konverzí, se nazývají α-ekvivalent. Často se při použití lambda kalkulu považují termíny ekvivalentní α za ekvivalentní.

Přesná pravidla pro α-konverzi nejsou zcela triviální. Nejprve při α-převodu abstrakce jsou přejmenovány pouze výskyty proměnných, které jsou vázány na stejnou abstrakci. Například α-konverze λX.λX.X může mít za následek λy.λX.X, ale mohlo ne mít za následek λy.λX.y. Ten druhý má jiný význam než originál. To je analogické s programovací představou variabilní stínování.

Za druhé, α-převod není možný, pokud by vedl k zachycení proměnné jinou abstrakcí. Například pokud nahradíme X s y v λX.λy.X, dostaneme λy.λy.y, což není vůbec stejné.

V programovacích jazycích se statickým rozsahem lze použít α-převod rozlišení jmen jednodušší tím, že zajistí, že žádný název proměnné masky jméno v obsahujícím rozsah (vidět α-přejmenování, aby rozlišení názvu bylo triviální ).

V De Bruijnův index notace, jakékoli dva α-ekvivalentní výrazy jsou syntakticky identické.

Střídání

Střídání, písemné M[PROTI := N], je proces nahrazení všech volný, uvolnit výskyty proměnné PROTI ve výrazu M s výrazem N. Substituce za podmínky lambda kalkulu je definována rekurzí ve struktuře termínů následovně (poznámka: xay jsou pouze proměnné, zatímco M a N jsou libovolné lambda výrazy):

X[X := N] = N

y[X := N] = y, pokud 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]), pokud X ≠ y a y ∉ FV (N)

Chcete-li dosadit do abstrakce, je někdy nutné α-převést výraz. Například není správné pro (λX.y)[y := X] za následek λX.X, protože substituovaný X měl být volný, ale nakonec byl spoután. Správná substituce je v tomto případě λz.X, až do α-ekvivalence. Substituce je definována jednoznačně až do α-ekvivalence.

β-redukce

β-redukce vystihuje myšlenku aplikace funkcí. β-redukce je definována z hlediska substituce: β-redukce (λPROTI.M) N je M[PROTI := N].

Například za předpokladu nějakého kódování 2, 7, × máme následující β-redukci: (λn.n × 2) 7 → 7 × 2.

β-redukce může být považována za stejnou jako koncept lokální redukovatelnost v přirozený odpočet prostřednictvím Curry – Howardův izomorfismus.

η-redukce

η-redukce vyjadřuje myšlenku extenzionalita, což v této souvislosti znamená, že dvě funkce jsou stejné kdyby a jen kdyby dávají stejný výsledek pro všechny argumenty. η-redukce převádí mezi λX.F X a F kdykoli X se nezobrazí zdarma v F.

η-redukce může být považována za stejnou jako koncept místní úplnost v přirozený odpočet prostřednictvím Curry – Howardův izomorfismus.

Normální formy a soutok

Pro netypový počet lambda, β-redukce jako a přepisovací pravidlo není ani jedno silně normalizující ani slabě normalizující.

Lze však ukázat, že β-redukce je soutok při práci na α-konverzi (tj. považujeme dvě normální formy za rovnocenné, pokud je možné α-přeměnit jednu na druhou).

Proto mají silně normalizující termíny i slabě normalizující termíny jedinečnou normální formu. U silně normalizujících podmínek je zaručeno, že jakákoli redukční strategie poskytne normální formu, zatímco u slabě normalizujících podmínek ji některé redukční strategie nemusí najít.

Kódování datových typů

Základní lambda kalkul lze použít k modelování booleov, aritmetický, datové struktury a rekurze, jak je znázorněno v následujících podkapitolách.

Aritmetika v lambda kalkulu

Existuje několik možných způsobů, jak definovat přirozená čísla v lambda kalkulu, ale zdaleka nejběžnější jsou Církevní číslice, které lze definovat takto:

0: = λF.λX.X

1: = λF.λX.F X

2: = λF.λX.F (F X)

3: = λF.λX.F (F (F X))

a tak dále. Nebo pomocí alternativní syntaxe uvedené výše v Zápis:

0: = λfx.X

1: = λfx.F X

2: = λfx.F (F X)

3: = λfx.F (F (F X))

Církevní číslo je a funkce vyššího řádu —Bere funkci s jedním argumentem F, a vrátí další funkci s jedním argumentem. Církevní číslo n je funkce, která přebírá funkci F jako argument a vrátí n-té složení F, tj. funkce F složený sám se sebou n krát. Toto je označeno F⁽ⁿ⁾ a ve skutečnosti je n-tá síla F (považováno za provozovatele); F⁽⁰⁾ je definována jako funkce identity. Takové opakované skladby (jediné funkce F) poslouchejte zákony exponentů, což je důvod, proč lze tyto číslice použít pro aritmetiku. (V původním církevním lambda kalkulu bylo nutné, aby se formální parametr výrazu lambda vyskytl alespoň jednou ve funkčním těle, což způsobilo výše uvedenou definici 0 nemožné.)

Jeden způsob uvažování o církevní číslici n, což je často užitečné při analýze programů, je jako opakování instrukce n krát '. Například pomocí PÁR a NULA níže definované funkce lze definovat funkci, která vytvoří (propojený) seznam n všechny prvky stejné X opakováním 'předložit další X živel' n krát, počínaje prázdným seznamem. Termín lambda je

λn.λX.n (PÁR X) NIL

Změnou toho, co se opakuje, a změnou toho, na jaký argument se tato opakovaná funkce použije, lze dosáhnout mnoha různých účinků.

Můžeme definovat nástupnickou funkci, která převezme církevní číslici n a vrátí se n + 1 přidáním další aplikace F, kde „(mf) x“ znamená, že funkce „f“ je použita „m“ krát na „x“:

SUCC: = λn.λF.λX.F (n F X)

Protože m-té složení F složený s n-té složení F dává m+n-té složení F, přidání lze definovat takto:

PLUS: = λm.λn.λF.λX.m F (n F X)

PLUS lze jej považovat za funkci, která vezme dvě přirozená čísla jako argumenty a vrátí přirozené číslo; lze to ověřit

PLUS 2 3

a

5

jsou β-ekvivalentní lambda výrazy. Od přidání m na číslo n lze dosáhnout přidáním 1 m alternativní definice:

PLUS: = λm.λn.m SUCC n^[22]

Podobně lze násobení definovat jako

MULT: = λm.λn.λF.m (n F)^[18]

Alternativně

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

od násobení m a n je stejné jako opakování přidání n funkce m krát a poté ji aplikovat na nulu. Exponentiace má poměrně jednoduché vykreslení v církevních číslech, jmenovitě

POW: = λb.λE.E b^[19]

Funkce předchůdce definovaná PRED n = n − 1 pro kladné celé číslo n a PRED 0 = 0 je podstatně obtížnější. Vzorec

PRED: = λn.λF.λX.n (λG.λh.h (G F)) (λu.X) (λu.u)

lze ověřit indukčním zobrazením, že pokud T označuje (λG.λh.h (G F)), pak T⁽ⁿ⁾(λu.X) = (λh.h(F⁽ⁿ⁻¹⁾(X))) pro n > 0. Dvě další definice PRED jsou uvedeny níže, jeden používá podmíněné a druhý pomocí páry. S funkcí předchůdce je odečítání jednoduché. Definování

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

SUB m n výnosy m − n když m > n a 0 v opačném případě.

Logika a predikáty

Podle konvence se pro booleovské hodnoty používají následující dvě definice (známé jako booleovské církve) SKUTEČNÝ a NEPRAVDIVÉ:

PRAVDA: = λX.λy.X

FALSE: = λX.λy.y

(Všimněte si, že NEPRAVDIVÉ odpovídá ekvivalentu církevní číslice nula definované výše)

Potom s těmito dvěma lambda výrazy můžeme definovat některé logické operátory (jedná se pouze o možné formulace; další výrazy jsou stejně správné):

AND: = λp.λq.p q p

NEBO: = λp.λq.p p q

NE: = λp.p FALSE TRUE

IFTHENELSE: = λp.λA.λb.p A b

Nyní jsme schopni vypočítat některé logické funkce, například:

A SKUTEČNÁ NEPRAVDA

≡ (λp.λq.p q p) SKUTEČNÁ NEPRAVDA →_β TRUE FALSE TRUE

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

a my to vidíme A SKUTEČNÁ NEPRAVDA je ekvivalentní k NEPRAVDIVÉ.

A predikát je funkce, která vrací logickou hodnotu. Nejzákladnějším predikátem je ISZERO, který se vrací SKUTEČNÝ pokud je jeho argumentem církevní číslice 0, a NEPRAVDIVÉ pokud je jeho argumentem jakákoli jiná církevní číslice:

ISZERO: = λn.n (λX.FALSE) PRAVDA

Následující predikát testuje, zda je první argument menší než nebo stejný jako druhý:

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

a od té doby m = n, pokud LEQ m n a LEQ n m, je jednoduché vytvořit predikát pro číselnou rovnost.

Dostupnost predikátů a výše uvedená definice SKUTEČNÝ a NEPRAVDIVÉ je vhodné psát výrazy „pokud-pak-jiné“ do lambda kalkulu. Například funkci předchůdce lze definovat jako:

PRED: = λn.n (λG.λk.ISZERO (G 1) k (PLUS (G k) 1)) (λproti.0) 0

což lze ověřit tím, že to indukčně ukážeme n (λG.λk.ISZERO (G 1) k (PLUS (G k) 1)) (λproti.0) je doplněk n - 1 funkce pro n > 0.

Páry

Pár (2-n-tice) lze definovat z hlediska SKUTEČNÝ a NEPRAVDIVÉpomocí Církevní kódování pro páry. Například, PÁR zapouzdřuje pár (X,y), ZA PRVÉ vrací první prvek dvojice a DRUHÝ vrací druhý.

PAIR: = λX.λy.λF.F X y

PRVNÍ: = λp.p SKUTEČNÝ

DRUHÉ: = λp.p NEPRAVDIVÉ

NIL: = λX.SKUTEČNÝ

NULL: = λp.p (λX.λy.NEPRAVDIVÉ)

Propojený seznam lze definovat buď jako NIL pro prázdný seznam, nebo jako PÁR prvku a menšího seznamu. Predikát NULA testy hodnoty NULA. (Alternativně s NIL: = FALSE, konstrukt l (λh.λt.λz.deal_with_head_h_and_tail_t) (deal_with_nil) odstraňuje potřebu explicitního testu NULL).

Jako příklad použití párů je funkce posunu a přírůstku, která mapuje (m, n) na (n, n + 1) lze definovat jako

Φ: = λX.PAIR (DRUHÝ X) (SUCC (DRUHÉ X))

což nám umožňuje dát možná nejtransparentnější verzi funkce předchůdce:

PRED: = λn.ZA PRVÉ (n Φ (PAIR 0 0)).

Další techniky programování

Existuje značná skupina programovací idiomy pro lambda kalkul. Mnoho z nich bylo původně vyvinuto v souvislosti s použitím lambda kalkulu jako základu pro sémantiku programovacího jazyka, efektivně využívající lambda kalkul jako nízkoúrovňový programovací jazyk. Protože několik programovacích jazyků zahrnuje lambda kalkul (nebo něco velmi podobného) jako fragment, tyto techniky také vidí použití v praktickém programování, ale mohou být poté vnímány jako nejasné nebo cizí.

Pojmenované konstanty

V lambda kalkulu, a knihovna by mělo podobu kolekce dříve definovaných funkcí, které jako lambda-termíny jsou pouze konkrétní konstanty. Čistý lambda kalkul nemá koncept pojmenovaných konstant, protože všechny atomové lambda termíny jsou proměnné, ale lze napodobit pojmenované konstanty tak, že jako název konstanty vyčleníme proměnnou, která pomocí abstrakce tuto proměnnou v hlavní části vytvoří , a použít tuto abstrakci na zamýšlenou definici. Tak použít F znamenat M (nějaký výslovný termín lambda) v N (další termín lambda, „hlavní program“), dá se říci

(λF.N) M

Autoři často uvádějí syntaktický cukr, jako nechat, umožnit psaní výše uvedeného v intuitivnějším pořadí

nechat F =M v N

Zřetězením těchto definic lze napsat „program“ lambda kalkulu jako nulu nebo více definic funkcí, za kterým následuje jeden lambda termín využívající ty funkce, které tvoří hlavní část programu.

Toto je pozoruhodné omezení nechat je to jméno F není definováno v M, od té doby M je mimo rozsah abstrakční vazby F; to znamená, že definici rekurzivní funkce nelze použít jako M s nechat. Čím pokročilejší letrec syntaktická konstrukce cukru, která umožňuje psaní definic rekurzivních funkcí v tomto naivním stylu, místo toho navíc používá kombinátory pevných bodů.

Rekurze a pevné body

Rekurze je definice funkce pomocí samotné funkce. Lambda kalkul to nemůže vyjádřit tak přímo jako některé jiné notace: všechny funkce jsou v lambda kalkulu anonymní, takže nemůžeme odkazovat na hodnotu, kterou je třeba ještě definovat, uvnitř termínu lambda definujícího stejnou hodnotu. Rekurze však stále lze dosáhnout uspořádáním výrazu lambda, aby se přijímal jako hodnota argumentu, například v (λX.X X) E.

Zvažte faktoriál funkce F(n) rekurzivně definované

F(n) = 1, pokud n = 0; jiný n × F (n − 1).

Ve výrazu lambda, který má představovat tuto funkci, a parametr (obvykle první) se předpokládá, že bude přijímat samotný výraz lambda jako jeho hodnotu, takže jeho volání - jeho použití na argument - bude činit rekurzi. Tedy k dosažení rekurze je argument zamýšleného automatického odkazu (tzv r zde) musí být vždy předán sám sobě v těle funkce na tlačítkovém hlásiči:

G: = λr. λn. (1, pokud n = 0; jiný n × (r r (n−1)))

s r r X = F X = G r X držet, tak {{{1}}} a

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

Samoaplikace zde dosahuje replikace a předává výraz lambda funkce na další vyvolání jako hodnotu argumentu, čímž je zpřístupněna pro odkazování a volání tam.

To to vyřeší, ale vyžaduje přepsání každého rekurzivního volání jako vlastní aplikace. Chtěli bychom mít obecné řešení bez nutnosti jakýchkoli přepisů:

G: = λr. λn. (1, pokud n = 0; jiný n × (r (n−1)))

s r X = F X = G r X držet, tak r = G r =: OPRAVIT G a

F: = FIX G kde OPRAVIT G := (r kde r = G r) = G (OPRAVIT G)

aby FIX G = G (FIX G) = (λn. (1, pokud n = 0; jiný n × ((FIX G) (n−1))))

Vzhledem k termínu lambda s prvním argumentem představujícím rekurzivní volání (např. G zde), pevný bod kombinátor OPRAVIT vrátí samoreplikující se výraz lambda představující rekurzivní funkci (zde F). Funkce nemusí být v žádném okamžiku explicitně předána sama sobě, protože autoreplikace je předem uspořádána, když je vytvořena, je třeba ji provést pokaždé, když je volána. Tedy původní výraz lambda (OPRAVA G) je znovu vytvořen v sobě, na call-point, dosažení vlastní reference.

Ve skutečnosti pro to existuje mnoho možných definic OPRAVIT operátor, nejjednodušší z nich je:

Y : = λG. (λX.G (X X)) (λX.G (X X))

V lambda kalkulu Y G je pevný bod G, protože se rozšiřuje na:

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)

Nyní, abychom provedli naše rekurzivní volání faktoriální funkce, jednoduše zavoláme (Y G) n, kde n je číslo, ze kterého počítáme faktoriál. Dáno n = 4, například, toto dává:

(Y G) 4

G (Y G) 4

(λr.λn. (1, pokud n = 0; jiný n × (r (n−1)))) (Y G) 4

(λn. (1, pokud n = 0; jiný n × ((Y G) (n−1)))) 4

1, pokud 4 = 0; jinak 4 × ((Y G) (4-1))

4 × (G (Y G) (4-1))

4 × ((λn. (1, pokud n = 0; jiný n × ((Y G) (n−1)))) (4−1))

4 × (1, pokud 3 = 0; jinak 3 × ((Y G) (3-1)))

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

4 × (3 × ((λn. (1, pokud n = 0; jiný n × ((Y G) (n−1)))) (3−1)))

4 × (3 × (1, pokud 2 = 0; jinak 2 × ((Y G) (2-1))))

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

4 × (3 × (2 × ((λn. (1, pokud n = 0; jiný n × ((Y G) (n−1)))) (2−1))))

4 × (3 × (2 × (1, pokud 1 = 0; jinak 1 × ((Y G) (1-1)))))

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

4 × (3 × (2 × (1 × ((λn. (1, pokud n = 0; jiný n × ((Y G) (n−1)))) (1−1)))))

4 × (3 × (2 × (1 × (1, pokud 0 = 0; jinak 0 × ((Y G) (0-1))))))

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

24

Každá rekurzivně definovaná funkce může být považována za pevný bod nějaké vhodně definované funkce zavírající se nad rekurzivním voláním s argumentem navíc, a proto pomocí Y, každou rekurzivně definovanou funkci lze vyjádřit jako výraz lambda. Zejména nyní můžeme čistě rekurzivně definovat predikát odčítání, násobení a porovnání přirozených čísel.

Standardní podmínky

Některé výrazy mají běžně přijímané názvy:^{[Citace je zapotřebí ]}

Já : = λ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

Ž : = λX.λy.X y y

U : = λX.X X

ω : = λX.X X

Ω := ω ω

Y : = λG. (λX.G (X X)) (λX.G (X X))

Některé z nich mají přímé použití v EU eliminace abstrakce který promění lambda výrazy na kombinační počet podmínky.

Odstranění abstrakce

Li N je lambda-termín bez abstrakce, ale pravděpodobně obsahující pojmenované konstanty (kombinátory ), pak existuje lambda-termín T(X,N) což odpovídá λX.N ale postrádá abstrakci (s výjimkou části pojmenovaných konstant, pokud jsou považovány za jiné než atomové). To lze také zobrazit jako anonymizující proměnné, jako T(X,N) odstraní všechny výskyty X z N, zatímco stále umožňuje substituci hodnot argumentů do pozic kde N obsahuje X. Funkce převodu T lze definovat:

T(X, X) := Já

T(X, N) := K. N -li X není zdarma v N.

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

In either case, a term of the form T(X,N) P can reduce by having the initial combinator Já, K.nebo S grab the argument P, just like β-reduction of (λX.N) P by udělal. Já returns that argument. K. throws the argument away, just like (λX.N) would do if X has no free occurrence in N. S passes the argument on to both subterms of the application, and then applies the result of the first to the result of the second.

The combinators B a C jsou podobné S, but pass the argument on to only one subterm of an application (B to the "argument" subterm and C to the "function" subterm), thus saving a subsequent K. if there is no occurrence of X in one subterm. In comparison to B a C, S combinator actually conflates two functionalities: rearranging arguments, and duplicating an argument so that it may be used in two places. The Ž combinator does only the latter, yielding the B, C, K, W system as an alternative to SKI combinator calculus.

Typed lambda calculus

A zadaný lambda kalkul is a typed formalismus that uses the lambda-symbol (${displaystyle lambda}$) to denote anonymous function abstraction. In this context, types are usually objects of a syntactic nature that are assigned to lambda terms; the exact nature of a type depends on the calculus considered (see Kinds of typed lambda calculi ). From a certain point of view, typed lambda calculi can be seen as refinements of the netypový lambda kalkul but from another point of view, they can also be considered the more fundamental theory and netypový lambda kalkul a special case with only one type.^[23]

Typed lambda calculi are foundational programovací jazyky and are the base of typed funkční programovací jazyky jako ML a Haskell and, more indirectly, typed imperativní programování jazyky. Typed lambda calculi play an important role in the design of systémy typu for programming languages; here typability usually captures desirable properties of the program, e.g. the program will not cause a memory access violation.

Typed lambda calculi are closely related to matematická logika a teorie důkazů přes Curry – Howardův izomorfismus and they can be considered as the internal language tříd Kategorie, např. the simply typed lambda calculus is the language of Cartesian closed categories (CCCs).

Computable functions and lambda calculus

Funkce F: N → N of natural numbers is a computable function if and only if there exists a lambda expression F such that for every pair of X, y v N, F(X)=y kdyby a jen kdyby F X =_β y, kde X a y are the Church numerals corresponding to X a y, respectively and =_β meaning equivalence with β-reduction. This is one of the many ways to define computability; viz Církev – Turingova teze for a discussion of other approaches and their equivalence.

Undecidability of equivalence

There is no algorithm that takes as input any two lambda expressions and outputs SKUTEČNÝ nebo NEPRAVDIVÉ depending on whether or not the two expressions are equivalent.^[10] More precisely, no vypočítatelná funkce umět rozhodni se the equivalence. This was historically the first problem for which undecidability could be proven. As usual for such a proof, vypočitatelný means computable by any model výpočtu to je Turing dokončen.

Church's proof first reduces the problem to determining whether a given lambda expression has a normální forma. A normal form is an equivalent expression that cannot be reduced any further under the rules imposed by the form. Then he assumes that this predicate is computable, and can hence be expressed in lambda calculus. Building on earlier work by Kleene and constructing a Gödelovo číslování for lambda expressions, he constructs a lambda expression E that closely follows the proof of Gödelova první věta o neúplnosti. Li E is applied to its own Gödel number, a contradiction results.

Lambda calculus and programming languages

As pointed out by Peter Landin 's 1965 paper "A Correspondence between ALGOL 60 and Church's Lambda-notation",^[24] sekvenční procedurální programování languages can be understood in terms of the lambda calculus, which provides the basic mechanisms for procedural abstraction and procedure (subprogram) application.

Anonymní funkce

Například v Lisp the "square" function can be expressed as a lambda expression as follows:

(lambda (X) (* X X))

The above example is an expression that evaluates to a first-class function. The symbol lambda creates an anonymous function, given a list of parameter names, (X) – just a single argument in this case, and an expression that is evaluated as the body of the function, (* x x). Anonymous functions are sometimes called lambda expressions.

Například, Pascal and many other imperative languages have long supported passing subprograms tak jako argumenty to other subprograms through the mechanism of ukazatele funkcí. However, function pointers are not a sufficient condition for functions to be první třída datatypes, because a function is a first class datatype if and only if new instances of the function can be created at run-time. And this run-time creation of functions is supported in Pokec, JavaScript, and more recently in Scala, Eiffelova ("agents"), C# ("delegates") and C ++ 11, mezi ostatními.

Reduction strategies

Whether a term is normalising or not, and how much work needs to be done in normalising it if it is, depends to a large extent on the reduction strategy used. The distinction between reduction strategies relates to the distinction in functional programming languages between nedočkavé hodnocení a líné hodnocení.

Full β-reductions

Any redex can be reduced at any time. This means essentially the lack of any particular reduction strategy—with regard to reducibility, "all bets are off".

Applicative order

The leftmost, innermost redex is always reduced first. Intuitively this means a function's arguments are always reduced before the function itself. Applicative order always attempts to apply functions to normal forms, even when this is not possible.

Most programming languages (including Lisp, ML and imperative languages like C and Jáva ) are described as "strict", meaning that functions applied to non-normalising arguments are non-normalising. This is done essentially using applicative order, call by value reduction (viz. níže ), but usually called "eager evaluation".

Normal order

The leftmost, outermost redex is always reduced first. That is, whenever possible the arguments are substituted into the body of an abstraction before the arguments are reduced.

Volání podle hodnoty

Only the outermost redexes are reduced: a redex is reduced only when its right hand side has reduced to a value (variable or abstraction).

Volejte podle jména

As normal order, but no reductions are performed inside abstractions. Například, λX.(λX.X)X is in normal form according to this strategy, although it contains the redex (λX.X)X.

Call by need

As normal order, but function applications that would duplicate terms instead name the argument, which is then reduced only "when it is needed". Called in practical contexts "lazy evaluation". In implementations this "name" takes the form of a pointer, with the redex represented by a thunk.

Applicative order is not a normalising strategy. The usual counterexample is as follows: define Ω = ωω kde ω = λX.xx. This entire expression contains only one redex, namely the whole expression; its reduct is again Ω. Since this is the only available reduction, Ω has no normal form (under any evaluation strategy). Using applicative order, the expression KIΩ = (λX.λy.X) (λX.X)Ω is reduced by first reducing Ω to normal form (since it is the rightmost redex), but since Ω has no normal form, applicative order fails to find a normal form for KIΩ.

In contrast, normal order is so called because it always finds a normalizing reduction, if one exists. Ve výše uvedeném příkladu KIΩ reduces under normal order to Já, a normal form. A drawback is that redexes in the arguments may be copied, resulting in duplicated computation (for example, (λX.xx) ((λX.X)y) snižuje na ((λX.X)y) ((λX.X)y) using this strategy; now there are two redexes, so full evaluation needs two more steps, but if the argument had been reduced first, there would now be none).

The positive tradeoff of using applicative order is that it does not cause unnecessary computation, if all arguments are used, because it never substitutes arguments containing redexes and hence never needs to copy them (which would duplicate work). In the above example, in applicative order (λX.xx) ((λX.X)y) reduces first to (λX.xx)y and then to the normal order yy, taking two steps instead of three.

Většina čistě functional programming languages (notably Mirando and its descendants, including Haskell), and the proof languages of theorem provers, použijte líné hodnocení, which is essentially the same as call by need. This is like normal order reduction, but call by need manages to avoid the duplication of work inherent in normal order reduction using sdílení. In the example given above, (λX.xx) ((λX.X)y) snižuje na ((λX.X)y) ((λX.X)y), which has two redexes, but in call by need they are represented using the same object rather than copied, so when one is reduced the other is too.

A note about complexity

While the idea of β-reduction seems simple enough, it is not an atomic step, in that it must have a non-trivial cost when estimating výpočetní složitost.^[25] To be precise, one must somehow find the location of all of the occurrences of the bound variable PROTI ve výrazu E, implying a time cost, or one must keep track of these locations in some way, implying a space cost. A naïve search for the locations of PROTI v E je Ó(n) in the length n z E. This has led to the study of systems that use explicit substitution. Sinot's director strings^[26] offer a way of tracking the locations of free variables in expressions.

Parallelism and concurrency

The Church–Rosser property of the lambda calculus means that evaluation (β-reduction) can be carried out in any order, even in parallel. This means that various nondeterministic evaluation strategies are relevant. However, the lambda calculus does not offer any explicit constructs for rovnoběžnost. One can add constructs such as Futures to the lambda calculus. jiný process calculi have been developed for describing communication and concurrency.

Optimal reduction

In Lévy's 1988 paper "Sharing in the Evaluation of lambda Expressions ", he defines a notion of optimal sharing, such that no work is duplicated. For example, performing a β-reduction in normal order on (λX.xx) (II) reduces it to II (II). The argument II is duplicated by the application to the first lambda term. If the reduction was done in an applicative order first, we save work because work is not duplicated: (λX.xx) (II) snižuje na (λX.xx) I. On the other hand, using applicative order can result in redundant reductions or even possibly never reduce to normal form. For example, performing a β-reduction in normal order on (λF.f I) (λy.(λX.xx) (y I)) výnosy (λy.(λX.xx) (y I)) I, (λX.xx) (II) which we know we can do without duplicating work. Doing the same but in applicative order yields (λF.f I) (λy.y I (y I)), (λy.y I (y I)) I, I I (I I), and now work is duplicated.

Lévy shows the existence of lambda terms where there neexistuje a sequence of reductions which reduces them without duplicating work. The below lambda term is such an example.

((λg.(g(g(λx.x))))(λh.((λf.(f(f(λz.z))))(λw.(h(w(λy.y)))))))

It is composed of three similar terms, x=((λg. ... ) (λh.y)) a y=((λf. ...) (λw.z) ), a nakonec z=λw.(h(w(λy.y))). There are only two possible β-reductions to be done here, on x and on y. Reducing the outer x term first results in the inner y term being duplicated, and each copy will have to be reduced, but reducing the inner y term first will duplicate its argument z, which will cause work to be duplicated when the values of h and w are made known. Incidentally, the above term reduces to the identity function (λy.y), and is constructed by making wrappers which make the identity function available to the binders g=λh..., f=λw..., h=λx.x (at first), and w=λz.z (at first), all of which are applied to the innermost term λy.y.

The precise notion of duplicated work relies on noticing that after the first reduction of I I is done, the value of the other I I can be determined, because they have the same structure (and in fact they have exactly the same values), and result from a common ancestor. Such similar structures can each be assigned a label that can be tracked across reductions. If a name is assigned to the redex that produces all the resulting II terms, and then all duplicated occurrences of II can be tracked and reduced in one go. However, it is not obvious that a redex will produce the II období. Identifying the structures that are similar in different parts of a lambda term can involve a complex algorithm and can possibly have a complexity equal to the history of the reduction itself.

While Lévy defines the notion of optimal sharing, he does not provide an algorithm to do it. In Vincent van Oostrom, Kees-Jan van de Looij, and Marijn Zwitserlood's paper Lambdascope: Another optimal implementation of the lambda-calculus, they provide such an algorithm by transforming lambda terms into interaction nets, which are then reduced. Roughly speaking, the resulting reduction is optimal because every term that would have the same labels as per Lévy's paper would also be the same graph in the interaction net. In the paper, they mention that their prototype implementation of Lambdascope performs as well as the optimised version of the reference optimal higher order machine BOHM.^[b]

Sémantika

The fact that lambda calculus terms act as functions on other lambda calculus terms, and even on themselves, led to questions about the semantics of the lambda calculus. Could a sensible meaning be assigned to lambda calculus terms? The natural semantics was to find a set D isomorphic to the function space D → D, of functions on itself. However, no nontrivial such D can exist, by mohutnost constraints because the set of all functions from D na D has greater cardinality than D, unless D je singletonová sada.

V 70. letech Dana Scott showed that, if only spojité funkce were considered, a set or doména D with the required property could be found, thus providing a Modelka for the lambda calculus.

This work also formed the basis for the denotační sémantika programovacích jazyků.

Variations and extensions

These extensions are in the lambda cube:

• Typed lambda calculus – Lambda calculus with typed variables (and functions)
• Systém F – A typed lambda calculus with type-variables
• Calculus of constructions – A typed lambda calculus with typy as first-class values

Tyto formální systémy are extensions of lambda calculus that are not in the lambda cube:

• Binary lambda calculus – A version of lambda calculus with binary I/O, a binary encoding of terms, and a designated universal machine.
• Lambda-mu calculus – An extension of the lambda calculus for treating klasická logika

These formal systems are variations of lambda calculus:

• Kappa calculus – A first-order analogue of lambda calculus

These formal systems are related to lambda calculus:

• Kombinovaná logika – A notation for mathematical logic without variables
• SKI combinator calculus – A computational system based on the S, K. a Já combinators, equivalent to lambda calculus, but reducible without variable substitutions

Viz také

Poznámky

Reference

Další čtení

• Abelson, Harold a Gerald Jay Sussman. Struktura a interpretace počítačových programů. MIT Press. ISBN  0-262-51087-1.
• Hendrik Pieter Barendregt Úvod do lambda kalkulu.
• Henk Barendregt, Dopad lambda kalkulu v logice a informatice. Bulletin of Symbolic Logic, svazek 3, číslo 2, červen 1997.
• Barendregt, Hendrik Pieter, Typ zdarma lambda kalkul pp1091–1132 ze dne Příručka matematické logiky, Severní Holandsko (1977) ISBN  0-7204-2285-X
• Cardone a Hindley, 2006. Historie lambda-kalkulu a kombinatorické logiky. V Gabbay a Woods (eds.), Příručka dějin logiky, sv. 5. Elsevier.
• Kostel, Alonzo, Neřešitelný problém elementární teorie čísel, American Journal of Mathematics, 58 (1936), str. 345–363. Tento příspěvek obsahuje důkaz, že ekvivalence výrazů lambda není obecně rozhodnutelná.
• Alonzo Church, Kalkul lambda-konverze (ISBN  978-0-691-08394-0) ^[1]
• Frink Jr., Orrin, Recenze: The Calculi of Lambda-Conversion ^[2]
• Kleene, Stephen, Teorie kladných celých čísel ve formální logice, American Journal of Mathematics, 57 (1935), str. 153–173 a 219–244. Obsahuje definice lambda počtu několika známých funkcí.
• Landin, Peter, Korespondence mezi ALGOL 60 a církevní lambda notací, Komunikace ACM, sv. 8, č. 2 (1965), strany 89–101. Dostupné z Stránka ACM. Klasický článek zdůrazňující důležitost lambda kalkulu jako základu pro programovací jazyky.
• Larson, Jim, Úvod do lambda kalkulu a schématu. Jemný úvod pro programátory.
• Schalk, A. a Simmons, H. (2005) Úvod do λ-kalkulů a aritmetiky se slušným výběrem cvičení. Poznámky k kurzu matematické logiky na univerzitě v Manchesteru.
• de Queiroz, Ruy J.G.B. (2008). „O pravidlech redukce, významu jako použití a teoreticko-teoretické sémantice“. Studia Logica. 90 (2): 211–247. doi:10.1007 / s11225-008-9150-5. S2CID  11321602. Příspěvek formálně podporující myšlenku „smysl-je-použití“, která se, i když je založena na důkazech, liší od sémantiky důkazu jako v tradici Dummett-Prawitz, protože jako pravidla dává smysl redukci.
• Hankin, Chris, Úvod do lambda kalkulů pro počítačové vědce, ISBN  0954300653

Monografie / učebnice pro postgraduální studenty:

• Morten Heine Sørensen, Paweł Urzyczyn, Přednášky o izomorfismu Curryho – Howarda, Elsevier, 2006, ISBN  0-444-52077-5 je nedávná monografie, která se zabývá hlavními tématy lambda kalkulu od beztypové odrůdy po většinu zadaný lambda kalkul, včetně novějšího vývoje jako systémy čistého typu a lambda kostka. Nezahrnuje to podtypování rozšíření.
• Pierce, Benjamin (2002), Typy a programovací jazyky, MIT Press, ISBN  0-262-16209-1 pokrývá lambda kameny z pohledu systému praktického typu; některá témata, jako závislé typy, jsou pouze uvedena, ale podtypování je důležité téma.

Některé části tohoto článku jsou založeny na materiálu z FOLDOC, použitý s povolení.

externí odkazy

• Graham Hutton, Lambda kalkul, krátké (12 minut) videofilmové video z lambda kalkulu
• Helmut Brandl, Krok za krokem Úvod do lambda kalkulu
• „Lambda-kalkul“, Encyclopedia of Mathematics, Stiskněte EMS, 2001 [1994]
• Achim Jung, Krátký úvod do lambda kalkulu -(PDF )
• Dana Scott, Časová osa lambda kalkulu -(PDF )
• David C. Keenan, Disekovat ptáčka: Grafická notace pro lambda kalkul se animovanou redukcí
• Raúl Rojas, Výukový úvod do lambda kalkulu -(PDF )
• Peter Selinger, Poznámky k přednášce o lambda kalkulu -(PDF )
• L. Allison, Některé spustitelné příklady λ-kalkulu
• Georg P. Loczewski, Lambda kalkul a A ++
• Bret Victor, Alligator Eggs: Logická hra založená na lambda kalkulu
• Lambda kalkul na Web společnosti Safalra
• „Lambda kalkul“. PlanetMath.
• LCI Lambda Tlumočník jednoduchý, ale výkonný tlumočník čistého počtu
• Lambda Calculus odkazy na Lambda-the-Ultimate
• Mike Thyer, Lambda Animator, grafický applet Java demonstrující alternativní redukční strategie.
• Implementace lambda kalkulu použitím C ++ šablony
• Marius Buliga, Grafický lambda kalkul
• Lambda kalkul jako model pracovního toku Peter Kelly, Paul Coddington a Andrew Wendelborn; zmiňuje redukce grafu jako běžný prostředek pro hodnocení výrazů lambda a pojednává o použitelnosti lambda kalkulu pro distribuované výpočty (v důsledku Kostel - Rosser vlastnost, která umožňuje paralelní redukce grafu pro výrazy lambda).
• Shane Steinert-Threlkeld, „Lambda Calculi“, Internetová encyklopedie filozofie
• Anton Salikhmetov, Makro lambda kalkul