Lambda kalkul: popis věty, funkce, příklady

Lambda kalkul je formální systém v matematické logice pro vyjádření počtu na základě abstrakce a použití funkcí pomocí vazby a substituce proměnných. Jedná se o univerzální model, který lze použít k návrhu jakéhokoli Turingova stroje. Poprvé představen lambda kalkulu Church, známý matematik, ve třicátých letech.

Systém se skládá z budování členů lambda a provádění redukčních operací na nich.

Vysvětlení a aplikace

Řecké písmeno lambda (λ) se používá v Lambda výrazech a lambda termínech k označení vazby proměnné ve funkci.

Lambda kalkul může být atypován nebo zadán. V první variantě lze funkce použít, pouze pokud jsou schopny přijímat data tohoto typu. Zadané Lambda kalkuly jsou slabší, mohou vyjádřit menší hodnotu. Ale na druhé straně umožňují dokázat více věcí.

Jedním z důvodů, proč existuje mnoho různých typů, je touha vědců udělat více, aniž by se vzdali možnosti prokázat silné věty lambda kalkulu.

Systém najde uplatnění v mnoha různých oblastech matematiky, filozofie, lingvistiky, a informatiky. Lambda kalkul je především výpočet, který pomohl při vývoji teorie programovacích jazyků. Systémy implementují styly funkčního vytváření. Jsou také aktuálním tématem výzkumu v teorii těchto kategorií.

Pro figuríny

Lambda kalkul představil matematik Alonzo Church ve třicátých letech jako součást výzkumu základů vědy. Původní systém byl zobrazen jako logicky nekompatibilní v roce 1935, kdy Stephen Wedge a J. B. Rosser vyvinul paradox Klini-Rosser.

V následku, v roce 1936, Church vybral a publikoval pouze část relevantní pro výpočty, to, co se nyní nazývá netypizovaný lambda kalkul. V roce 1940 také představil slabší, ale logicky konzistentní teorii známou jako systém jednoduchého typu. Ve své práci vysvětluje celou teorii jednoduchým jazykem, takže můžeme říci, že Church publikoval lambda kalkul pro figuríny.

Až do šedesátých let, kdy se objevil jeho vztah k programovacím jazykům, se λ stalo pouze formalismem. Díky použití Richarda Montagu a dalších lingvistů v sémantice přirozeného jazyka se počet stal čestným místem jak v lingvistice, tak v informatice.

Původ symbolu

Lambda neoznačuje slovo ani zkratku, vznikla díky odkazu v Russellově" základní matematice", následované dvěma typografickými změnami. Příklad notace: pro funkci f s f (y) = 2y + 1 se rovná 2ŷ + 1. A zde se používá symbol vozíku ("klobouk") nad y k označení vstupní proměnné.

Církev původně zamýšlela používat podobné symboly, ale sazeči nebyli schopni umístit symbol "klobouk" nad písmena. Místo toho to původně vytiskli jako " /y.2y+1». V další epizodě úprav nahradili sazeči "/" vizuálně podobným znakem.

Úvod do lambda kalkulu

Systém se skládá z jazyka termínů, které jsou vybírány konkrétní formální syntaxí, a sady pravidel transformace, která jim umožňují manipulovat. Poslední bod lze považovat za Rovníkovou teorii nebo za provozní definici.

Všechny funkce v Lambda kalkulu jsou anonymní, tj. Berou pouze jednu vstupní proměnnou, přičemž currenting se používá k implementaci grafů s více nekonzistentními.

Lambda-termíny

Syntaxe počtu definuje některé výrazy jako platné a jiné jako neplatné. Také, jak různé řetězce znaků jsou platné programy na C, ale některé nejsou. Skutečný výraz lambda kalkulu se nazývá "Lambda termín".

Následující tři pravidla poskytují induktivní definici, kterou lze použít k vytvoření všech syntakticky platných pojmů:

Proměnná X je sama o sobě platným termínem Lambda:

• pokud T je lt A x je nekonzistentní ,pak (lambda xt) se nazývá abstrakce.
• pokud T, a s pojmy, pak (TS) se nazývá aplikace.

Nic jiného není termín Lambda. Koncept je tedy platný pouze tehdy, když jej lze získat opětovným použitím těchto tří pravidel. Některé závorky však mohou být vynechány podle jiných kritérií.

Definice

Lambda výrazy se skládají z:

• proměnné v 1, v 2,..., v n,...
• znaky abstrakce `λ `a body`.`
• závorka ().

Množina Λ, může být definována indukčně:

• Pokud X je proměnná, pak x Λ Λ;
• x je nekonzistentní a m Λ Λ, pak (λx.M) ∈ Λ;
• M, n Λ Λ, pak (MN) Λ Λ.

Označení

Chcete-li zachovat notaci Lambda výrazů přehledně, obvykle platí následující konvence:

• Vnější závorky jsou vynechány: MN místo (MN).
• Předpokládá se, že aplikace zůstávají asociativní: na oplátku ((MN) P) lze napsat MNP.
• Tělo abstrakce sahá dále doprava: λx.Mn znamená λx. (MN), ne (λx.M) N.
• Posloupnost abstrakcí je zkrácena: λx.λy.λz.N může λxyz.N.

Volné a související proměnné

Operátor λ spojuje svůj nestálý, ať je kdekoli v abstrakčním těle. Proměnné spadající do oblasti se nazývají související. Ve výrazu λ x. M, část λ X se často nazývá pojivo. Jako by naznačoval, že proměnné se stávají skupinou s přidáním X X do M. Všechny ostatní nestabilní se nazývají volné.

Například ve výrazu λ Y. X X Y, Y-vázaný nestálý a X-Volný. A také stojí za to všimnout si, že proměnná je seskupena svou" nejbližší " abstrakcí. V následujícím příkladu je řešení lambda kalkulu reprezentováno jediným výskytem x, který je spojen druhou složkou:

λ x. y (λ x. z x)

Sada volných proměnných M je označena jako FV (M) a je definována rekurzí ve struktuře termínů následujícím způsobem:

• FV (x) = {x}, kde X je proměnná.
• FV (λx.M) = FV (M){x}.
• FV (MN) = FV (M) ∪ FV (N).

Vzorec, který neobsahuje volné proměnné, se nazývá uzavřený. Uzavřené lambda výrazy jsou také známé jako kombinátory a jsou ekvivalentní termínům v kombinatorické logice.

Snížení

Hodnota Lambda výrazů je dána tím, jak mohou být zkráceny.

Existují tři typy řezání:

• α-transformace: změna souvisejících proměnných (alfa).
• β-redukce: aplikace funkcí na vaše argumenty (beta).
• η-transformace: zahrnuje pojem extenzionality.

Zde mluvíme také o odvozených ekvivalencích: dva výrazy jsou β-ekvivalentní, pokud mohou být β-převedeny na stejnou složku a α / η-ekvivalence je definována podobně.

Termín redex, zkratka pro citovaný obrat, odkazuje na podtémata, která mohou být zkrácena jedním z pravidel. Lambda kalkul pro figuríny, příklady:

(λ x.M) n je beta-Redex ve výrazu substituce N x V M. Složka, na kterou se redukuje Redex, se nazývá jeho redukce. Redukce (λ x.M) n Je M [x: = N].

Pokud x není volné v M, λ X. M x také et-REDEX s regulátorem m.

α-transformace

Alfa přejmenování vám umožní změnit názvy souvisejících proměnných. Například λ X. X může dát λ Y. u. Termíny, které se liší pouze alfa transformací, se nazývají α-ekvivalentní. Při použití lambda kalkulu jsou často α-ekvivalentní považovány za vzájemné.

Přesný pravidla pro alfa transformace nejsou zcela triviální. Za prvé, při dané abstrakci jsou přejmenovány pouze proměnné, které jsou spojeny se stejným systémem. Například alfa transformace λ x.λ x. x může vést k λ Y.λ x. X, ale to nemusí vrhnout do λy.λx.y ten má jiný význam než originál. To je podobné konceptu programování stínování proměnných.

Za druhé, alfa transformace není možná, pokud povede k zachycení nekonzistentní jinou abstrakcí. Například pokud nahradíte x y v λ x.λ y. x, pak můžete získat λ Y.λ y. y, což není úplně stejné.

V programovacích jazycích se statickým rozsahem lze alfa transformaci použít ke zjednodušení rozlišení názvů. Současně se ujistěte, že pojem proměnné nezakrývá notaci v oblasti obsahující.

V notaci de Bruyneova indexu jsou jakékoli dva termíny ekvivalentní alfa syntakticky identické.

Výměna

Změny napsané E [V: = R] jsou procesem substituce všech volných výskytů proměnné V ve výrazu e s obratem R. Substituce z hlediska λ je definována lambdou rekurzního počtu strukturou pojmů následujícím způsobem (POZNÁMKA: x a y jsou pouze proměnné A M A N jsou jakýkoli λ výraz).

x [x: = N] ≡ N

y [x: = N] ≡ y, pokud x ≠ y

(M 1 M 2) [x: = N] ≡ (M 1 [x: = N]) (M 2 [x: = N])

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

(λ y.M) [x: = N] y λ y. (M [x: = N]), pokud x ≠ y, za předpokladu, že y ∉ FV (N).

Pro substituci do abstrakce lambda je někdy nutné převést výraz α. Například je nesprávné, aby (λ X. Y) [y: = x] vedlo k (λ x. X), protože substituovaný x měl být volný, ale nakonec byl vázán. Správná náhrada v tomto případě (λ z. X) s přesností na α-ekvivalenci. Je třeba věnovat pozornost, že substituce je jednoznačně určena věrností lambdě.

β-redukce

Beta redukce odráží myšlenku aplikace funkce. Beta-redukční je definován z hlediska substituce: ((X V. E) E`) je E [V: = e`].

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

Beta redukci lze považovat za stejnou jako koncept lokální redukovatelnosti při přirozené dedukci prostřednictvím Curry – Howardova izomorfismu.

η-transformace

Tato konverze vyjadřuje myšlenku extenzionality, která v této souvislosti je, že obě funkce jsou stejné, když dávají stejný výsledek pro všechny argumenty. Tato konverze vyměňuje mezi λ x. (F x) a f, kdykoli se X nezdá být volný ve f.

Danou akci lze považovat za stejnou jako koncept místní úplnosti v přirozené dedukci prostřednictvím izomorfismu Curry-Howard.

Normální formy a fúze

U atypizovaného lambda kalkulu není β-redukce obvykle přepisování ani silně normalizující, ani slabě.

Lze však ukázat, že β-redukce se spojuje při práci před převodem α (t. e. lze považovat dvě normální formy za rovné, pokud je to možné α-transformace jedné na druhou).

Proto mají vysoce normalizační členové i volně se rozvíjející pojmy jedinou normální formu. U prvních termínů je zaručeno, že jakákoli strategie redukce povede k typické konfiguraci. Zatímco pro slabě normalizační podmínky nemusí některé strategie snižování najít.

Další programovací metody

Existuje velké množství idiomů stvoření pro lambda kalkul. Mnoho z nich bylo původně vyvinuto v kontextu používání systémů jako základy pro sémantika programovací jazyk, efektivní jejich použití jako vytvoření nízké úrovně. Protože některé styly zahrnují lambda kalkul (nebo něco velmi podobného) jako fragment, tyto metody také nacházejí uplatnění v praktickém vytváření, ale pak mohou být vnímány jako nejasné nebo cizí.

Pojmenované konstanty

V Lambda kalkulu má knihovna podobu sady dříve definovaných funkcí, ve kterých jsou termíny pouze konkrétní konstanty. Čistý počet nemá žádnou představu o pojmenovaných neměnných, protože všechny atomové Lambda termíny jsou proměnné. Lze je však také napodobit zvýrazněním nestálého jako názvu konstanty pomocí abstrakce Lambda k propojení této proměnlivé v hlavní části a použít tuto abstrakci na zamýšlenou definici. Pokud tedy použijete f k označení M V N, lze říci,

(λ f. N) M.

Autoři často zavádějí syntaktický koncept, jako je let, aby umožnili psát vše intuitivnějším způsobem.

f = M V N

Zřetězením takových definic je možné napsat "program" lambda kalkulu jako nulu nebo více definic funkcí následovaných jedním Lambda termínem pomocí definic, které tvoří hlavní část programu.

Pozoruhodným omezením tohoto let je, že název f není definován v M, protože M je mimo vazebnou oblast Lambda abstrakce f. To znamená, že atribut rekurzivní funkce nelze použít jako M S let. Pokročilejší syntaktická konstrukce letrec, která umožňuje psát rekurzivní definice funkcí v tomto stylu, místo toho dále používá kombinátory s pevným bodem.

Tištěné analogy

Tento typ je typizovaný formalismus, který používá symbol k označení anonymní funkce abstrakce. V této souvislosti jsou typy obvykle objekty syntaktické povahy, které jsou přiřazeny termínům Lambda. Přesná povaha závisí na uvažovaném počtu. Z určitého hlediska lze typizované li považovat za objasnění netypického li. Na druhé straně je však lze také považovat za zásadnější teorii a atypizovaný lambda kalkul za zvláštní případ pouze s jedním typem.

Typizované li jsou základními programovacími jazyky a základem funkčních jazyků, jako jsou ML a Haskell. A více nepřímo, imperativní styly tvorby. Zadané Lambda kalkuly hrají důležitou roli ve vývoji typových systémů pro programovací jazyky. Zde typovatelnost obvykle zachycuje požadované vlastnosti programu, například nezpůsobí narušení přístupu do paměti.

Zadané Lambda kalkuly úzce souvisejí s matematickou logikou a teorií důkazů prostřednictvím Curry – Howardova izomorfismu a lze je považovat za vnitřní jazyk tříd kategorií, například, což je jednoduše kartézský uzavřený styl.