Lambda kalkul: opis vety, vlastnosti, príklady

Lambda kalkul je formálny systém v matematickej logike na vyjadrenie výpočtov založených na abstrakcii a aplikácii funkcií pomocou väzby a substitúcie premenných. Jedná sa o univerzálny model, ktorý možno použiť na návrh akéhokoľvek Turingovho stroja. Lambda kalkul bol prvýkrát predstavený Church, slávny matematik, v roku 1930.

Systém pozostáva z konštrukcie členov lambda a vykonávania redukčných operácií na nich.

Vysvetlenia a žiadosti

Grécke písmeno lambda (λ) sa používa vo výrazoch lambda a výrazoch lambda na označenie väzby premennej vo funkcii.

Počet Lambda môže byť netypovaný alebo napísaný. V prvom variante môžu byť funkcie použité iba vtedy, ak sú schopné prijímať údaje tohto typu. Zadané Lambda kalkuly sú slabšie, môžu vyjadrovať menšiu hodnotu. Ale na druhej strane vám umožňujú dokázať viac vecí.

Jedným z dôvodov, prečo existuje veľa rôznych typov, je túžba vedcov urobiť viac bez toho, aby sa vzdali príležitosti dokázať silné vety o Lambda kalkule.

Systém nachádza uplatnenie v mnohých rôznych oblastiach matematiky, filozofie, lingvistiky a informatiky. Po prvé, Lambda kalkul je výpočet, ktorý zohral dôležitú úlohu pri vývoji teórie programovacích jazykov. Sú to štýly funkčnej tvorby, ktoré implementujú systémy. Sú tiež aktuálnou témou výskumu v teórii týchto kategórií.

Pre figuríny

Lambda kalkul bol predstavený matematik Alonzo Church v roku 1930 ako súčasť štúdie základov vedy. Pôvodný systém sa ukázal ako logicky nekompatibilný v roku 1935, keď Stephen Kline a J. B. Rosser vyvinul klini-Rosserov paradox.

Neskôr, v roku 1936, Church vybral a publikoval iba časť, ktorá je relevantná pre výpočty, čo sa dnes nazýva netypovaný Lambda kalkul. V roku 1940 predstavil aj slabšiu, ale logicky konzistentnú teóriu známu ako systém jednoduchého typu. Vo svojej práci vysvetľuje celú teóriu jednoduchým jazykom, takže môžeme povedať, že Church publikoval Lambda calculus for dummies.

Až do roku 1960, keď sa jeho postoj k programovacím jazykom stal jasným, λ sa stal len formalizmom. Vďaka aplikáciám Richarda Montagueho a ďalších lingvistov v sémantike prirodzeného jazyka začal kalkul zaujímať čestné miesto v lingvistike aj informatike.

Pôvod symbolu

Lambda neoznačuje slovo ani skratku, vznikla vďaka odkazu v Russellovej "základnej matematike", po ktorom nasledovali dve typografické zmeny. Príklad zápisu: pre funkciu f S f (y) = 2y + 1 sa rovná 2ŷ + 1. A tu sa nad y používa symbol vozíka ("klobúk") na označenie vstupnej premennej.

Kostol pôvodne zamýšľal používať podobné symboly, ale sadzači nedokázali umiestniť symbol "klobúka" nad písmená. Takže namiesto toho to pôvodne vytlačili ako " /y.2y + 1". V ďalšej epizóde úprav sadzače nahradili "/" vizuálne podobným znakom.

Úvod do Lambda kalkulu

Systém pozostáva z jazyka výrazov, ktoré sú vybrané určitou formálnou syntaxou, a súboru transformačných pravidiel, ktoré vám umožňujú manipulovať s nimi. Posledný bod možno považovať za teóriu rovníc alebo za operačnú definíciu.

Všetky funkcie v Lambda kalkulu sú anonymné, to znamená, že nemajú mená. Prijímajú iba jednu vstupnú premennú, zatiaľ čo Kari sa používa na implementáciu grafov s viacerými nekonštantnými premennými.

Obchodné podmienky

Syntax počtu definuje niektoré výrazy ako platné a iné ako neplatné. Rovnako ako rôzne reťazce znakov sú platné programy C a niektoré nie. Platný výraz počtu lambda sa nazýva "termín lambda".

Nasledujúce tri pravidlá poskytujú induktívnu definíciu, ktorú je možné použiť na zostavenie všetkých syntakticky platných konceptov:

Samotná premenná x je platný termín lambda:

• ak T je LT a x je nekonštantný, potom (lambda xt) sa nazýva abstrakcia.
• ak T a tiež s sú koncepty, potom (TS) sa nazýva aplikácia.

Nič iné nie je lambda termín. Koncept je teda platný vtedy a len vtedy, ak ho možno získať opakovaným uplatňovaním týchto troch pravidiel. Niektoré zátvorky však možno vynechať podľa iných kritérií.

Definícia

Lambda výrazy pozostávajú z:

• premenné v 1, v 2,..., v n,...
• abstrakčné symboly ` λ ` a bodky `.`
• držiak ().

Množinu Λ je možné definovať indukčne:

• Ak x je premenná, potom x Λ Λ;
• x je nekonštantný a M Λ Λpotom (λx.M ) Λ Λ;
• M , N Λ Λ, potom ( MN) Λ Λ.

Označenie

Aby bola notácia výrazov lambda prehľadná, zvyčajne sa používajú tieto konvencie:

• Vonkajšie zátvorky sú vynechané: MN namiesto (MN).
• Predpokladá sa, že aplikácie zostávajú asociatívne: namiesto ((MN) P) môžete písať MNP.
• Abstrakčné telo sa rozširuje ďalej doprava: λx.MN znamená λx. (MN), nie (λx.M) N.
• Postupnosť abstrakcií je znížená: λx.λy.λz.N môže byť λxyz.N.

Voľné a viazané premenné

Operátor λ sa pripojí k svojmu nekonštantnému, kdekoľvek sa nachádza v abstrakčnom tele. Premenné, ktoré spadajú do rozsahu, sa nazývajú viazané. Vo výraze λ x. M, časť λ x sa často nazýva spojivo. Akoby naznačoval, že premenné sa stanú skupinou s pridaním X X do M. Všetky ostatné nestabilné sa nazývajú zadarmo.

Napríklad vo výraze λ y. x x y, y je viazaný nekonštantný a x je voľný. A tiež stojí za to Poznámka, že premenná je zoskupená podľa jej "najbližšej" abstrakcie. V nasledujúcom príklade je riešenie Lambda počtu reprezentované jediným výskytom x, ktorý je spojený druhou zložkou:

λ x. y (λ X. z x)

Súbor voľných premenných M je označený ako FV (M) A je definovaný rekurziou podľa štruktúry pojmov nasledovne:

• FV (x) = {x}, kde x je premenná.
• FV (λx.M) = FV (M){x}.
• FV (MN) = FV (M) ∪ FV (N).

Vzorec, ktorý neobsahuje voľné premenné, sa nazýva uzavretý. Uzavreté Lambda výrazy sú tiež známe ako kombinátory a sú ekvivalentné výrazom v kombinatorickej logike.

Zníženie

Význam výrazov lambda je určený tým, ako ich možno skrátiť.

Existujú tri typy rezov:

• α-transformácia: zmena súvisiacich premenných (alfa).
• β-redukcia: použitie funkcií na ich argumenty (beta).
• n-transformácia: pokrýva koncept extenzionality.

Tu hovoríme aj o získaných ekvivalenciách: dva výrazy sú β-ekvivalentné, ak sa dajú β-transformovať na rovnakú zložku, a α / n-ekvivalencia je definovaná podobne.

Termín redex, skratka citovaného obratu, sa vzťahuje na podtémy, ktoré je možné skrátiť jedným z pravidiel. Lambda kalkul pre figuríny, príklady:

(λ X.M) N je beta redex vo vyjadrení nahradenia N X v M. Komponent, na ktorý je redex redukovaný, sa nazýva jeho redukcia. Redukcia (λ x.M) N je M [x: = N].

Ak x nie je zadarmo V M, λ x. M x tiež et-REDEX s regulátorom M.

α-transformácia

Alfa premenovanie vám umožňuje zmeniť názvy súvisiacich premenných. Napríklad λ x. x môže dať λ y. y. Pojmy, ktoré sa líšia iba alfa transformáciou, sa nazývajú α-ekvivalent. Pri použití Lambda počtu sa α-ekvivalencie často považujú za recipročné.

Presný pravidlá pre alfa transformácie nie sú úplne triviálne. Po prvé, s touto abstrakciou sa premenujú iba tie premenné, ktoré sú spojené s rovnakým systémom. Napríklad alfa transformácia λ x.λ x. x môže viesť k λ y.λ x. x, ale nemusí sa ponoriť do λy.λx.y ten druhý má iný význam ako originál. Je to analogické s konceptom programovania premenlivého tieňovania.

Po druhé, alfa transformácia nie je možná, ak vedie k zachyteniu nestálou inou abstrakciou. Napríklad, ak nahradíte x S y v λ x.λ y. x, potom môžete získať λ y.λ y. y, čo vôbec nie je to isté.

V programovacích jazykoch so statickým rozsahom možno na zjednodušenie rozlíšenia názvu použiť alfa transformáciu. Zároveň sa uistite, že koncept premennej nezakrýva označenie v obsahujúcej oblasti.

V De Bruyne index notácia, akékoľvek dva výrazy ekvivalentné alfa sú syntakticky identické.

Výmena

Zmeny napísané E [V: = R], predstavujú proces nahradenia všetkých voľných výskytov premennej v vo výraze E obratom R. Substitúcia z hľadiska λ je definovaná lambda rekurzívneho počtu podľa štruktúry pojmov nasledovne (Poznámka: x a y sú iba premenné A M A N sú akékoľvek λ výraz).

x [x:= N] ≡ N

y [x: = N] ≡ y Ak 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]), Ak x ≠ y, za predpokladu, že y ∉ FV (N).

Pre substitúciu do Lambda abstrakcie je niekedy potrebné α-transformovať výraz. Napríklad nie je pravda, že (λ X. Y) [y: = x] viedol k (λ X. X), pretože substituované x malo byť voľné, ale nakoniec bolo viazané. Správna výmena v tomto prípade je (λ z. X) do α-ekvivalencie. Stojí za zmienku, že substitúcia je jednoznačne určená s vernosťou až po lambda.

β-redukcia

Beta redukcia odráža myšlienku aplikácie funkcie. Beta-redukčný je definovaný z hľadiska substitúcie: ((X V. E) E`) je E [V: = E`].

Napríklad za predpokladu určitého kódovania 2, 7, × existuje nasledujúca β-redukcia: ((λ n. N × 2) 7) → 7 × 2.

Redukciu Beta možno považovať za rovnakú ako koncept lokálnej redukovateľnosti pri prirodzenej dedukcii prostredníctvom Curry-Howardovho izomorfizmu.

n-

Konverzia Eta vyjadruje myšlienku extenzionality, ktorá v tejto súvislosti spočíva v tom, že dve funkcie sú rovnaké, keď poskytujú rovnaký výsledok pre všetky argumenty. Táto konverzia sa vymieňa medzi λ x. (F x) A f vždy, keď sa x nezdá byť voľné V f.

Túto akciu možno považovať za rovnakú ako koncepciu miestnej úplnosti v prirodzenej dedukcii prostredníctvom Curry-Howardovho izomorfizmu.

Normálne formy a zlúčenie

Pre netypovaný počet lambda, β-redukcia ako pravidlo prepisovania nie je ani silne normalizujúca, ani slabo.

Napriek tomu je možné preukázať, že β-redukcia sa spája pri práci až po α-transformáciu (t. j. . dve normálne formy možno považovať za rovnaké, ak je možné transformovať jednu na druhú).

Preto majú silne normalizačné pojmy aj slabo upravujúce koncepty jednu normálnu formu. Pri prvých termínoch je zaručené, že každá stratégia znižovania bude mať za následok typickú konfiguráciu. Zatiaľ čo pre slabo normalizujúce podmienky to niektoré redukčné stratégie nemusia nájsť.

Ďalšie metódy programovania

Existuje veľké množstvo idiómov tvorby pre Lambda kalkul. Mnohé z nich boli pôvodne vyvinuté v kontexte používania systémov ako základy pre sémantika programovací jazyk, efektívne ich aplikovať ako tvorbu na nízkej úrovni. Pretože niektoré štýly zahŕňajú Lambda kalkul (alebo niečo veľmi podobné) ako fragment, tieto metódy nachádzajú uplatnenie aj v praktickej tvorbe, ale potom ich možno vnímať ako nejasné alebo cudzie.

Pomenované konštanty

V Lambda kalkul, knižnica má formu množiny predtým definovaných funkcií, v ktorých sú výrazy iba konkrétnymi konštantami. Čistý počet nemá koncepciu pomenovaných nemenných, pretože všetky atómové výrazy lambda sú premenné. Môžu sa však napodobniť aj zvýraznením nekonštantného názvu ako konštantného názvu pomocou abstrakcie lambda na viazanie tejto premennej v hlavnej časti a použitie tejto abstrakcie na zamýšľanú definíciu. Ak teda použijeme f na označenie M V N, môžeme povedať,

(λ f. H) M.

Autori často zavádzajú syntaktický koncept, ako napríklad let, aby umožnili písať všetko v intuitívnejšom poradí.

f = M v N

Kombináciou takýchto definícií do reťazca je možné napísať "program" počtu lambda ako nulovú alebo viac definícií funkcií, za ktorými nasleduje jeden výraz lambda, s použitím definícií, ktoré tvoria hlavnú časť programu.

Pozoruhodným obmedzením tohto let je, že názov f nie je definovaný v M, pretože M je mimo záväzného rozsahu Lambda abstrakcie f. To znamená, že atribút rekurzívnej funkcie nemožno použiť ako M S let. Pokročilejšia syntaktická konštrukcia letrec, ktorá vám umožňuje písať definície rekurzívnych funkcií v tomto štýle, namiesto toho navyše používa kombinátory s pevným bodom.

Tlačené analógy

Tento typ je typizovaný formalizmus, ktorý používa symbol na označenie abstrakcie anonymnej funkcie. V tejto súvislosti sú typy zvyčajne objekty syntaktickej povahy, ktoré sú priradené výrazom lambda. Presná povaha závisí od príslušného počtu. Z určitého hľadiska možno písaný LI považovať za vylepšenie netypovaného LI. Ale na druhej strane ich možno považovať aj za zásadnejšiu teóriu a netypický Lambda kalkul je špeciálny prípad iba s jedným typom.

Typované LI sú základné programovacie jazyky a základ funkčných jazykov, ako sú ML a Haskell. A nepriamo imperatívne štýly tvorby. Zadané Lambda kalkuly hrajú dôležitú úlohu pri vývoji typových systémov pre programovacie jazyky. Tu typovateľnosť zvyčajne zachytáva požadované vlastnosti programu, napríklad nespôsobí porušenie prístupu do pamäte.

Písané Lambda kalkuly úzko súvisia s matematickou logikou a teóriou dôkazov prostredníctvom Curry-Howardovho izomorfizmu a možno ich považovať napríklad za interný jazyk tried kategórií, čo je jednoducho Karteziánsky uzavretý štýl.