Úvodní stránka | Tato stránka v originále

Combinatory logika

Tento článek je ne o combinatorial logice, téma v elektronice.

Combinatory logika je zjednodušený model počítání, použitý v teorii vypočitatelnosti (studie o čem může být počítána) a teorie důkazu (studie o čem může být matematicky dokázaný.) teorie, přes jeho jednoduchost, zachytí mnoho základních rysů povahy počítání.

Combinatory logika je variace lambda počtu, ve kterých lambda výrazech (použitý počítat s funkční abstrakcí) být nahrazený omezeným souborem primitivních funkcí.

Tabulka s obsahem
1 shrnutí lambda počtu
2 Combinatory calculi
3 Undecidability Combinatorial počtu
4 Combinatory termíny jako grafy
5 aplikací
6 odkazů

Shrnutí lambda počtu

Pro kompletní detaily o lambda počtu, viďte článek pod tou hlavou. My budeme shrnovat tady. Lambda počet je znepokojen objekty nazvaný lambda-požadavky, který jsou řetězy symbolů jednoho z sledování forem:

kde v je jméno proměnné kreslené od predefined nekonečného souboru jmén proměnné, a E1 a E2 je lambda-požadavky. Podmínky formy a lambda; v.E1 být nazýván abstrakcemi. Proměnná v je nazýván formálním parametrem abstrakce, a E1 je tělo abstrakce.

Termín a lambda; v.E1 reprezentuje funkci který, jestliže aplikoval argument, sváže formální parametr v k argumentu a pak počítá výslednou hodnotu E1-- - to je, to vrátí E1, s každým výskytem v nahrazený argumentem.

Podmínky formy (E1 E2) je nazýván aplikacemi. Aplikace modelují zaříkávání funkce nebo provádění: Funkce reprezentovala E1 má být použil, s E2 jako jeho argument a výsledek je počítán. Jestliže E1 (někdy volal applicand) je abstrakce, termín může být redukovaný: E2, argument, smět být substituted do skupiny E1 v místě formálního parametru E1, a výsledek je nový lambda termín, který je ekvivalent k tomu starému. Jestliže lambda termín obsahuje žádné subterms formy (a lambda; v.E1 E2) pak to nemůže být redukováno, a je řekl, aby byl v normální formě.

Výraz E[/v] reprezentuje výsledek brát termín E a nahrazovat všechny volné výskyty v s . Tak my píšeme

       (a lambda; v.E ) = > E[/v]
Konvencí, my bereme (b c d... z) jak krátký pro ' ' (... ((( b) c) d)... z) ' '.

Motivace pro tuto definici redukce je že to zachytí základní chování všech matematických funkcí. Například, zvažujte funkci, která počítá čtverec čísla. My bychom mohli psát

       Čtverec x je x*x
(Používání “*” ukázat násobení.) x tady je formální parametr funkce. Ocenit čtverec pro zvláštní argument, říkat 3, my vložíme to do definice na místě formálního parametru:

       Čtverec 3 je 3 * 3
Ocenit výsledný výraz 3 * 3, my bychom museli uchýlit se k naší znalosti násobení a čísla 3. Od některého výpočet je prostě složení ohodnocení vhodných funkcí na vhodných primitve argumentech, tento jednoduchý substituční princip stačí zachytit základní mechanismus počítání. Navíc, v počtu lambda, pojmy takový jak ' 3 ' a ' * ' moci být reprezentován bez nějaké potřeby externě definovaných primitivních operátorů nebo konstant. To je možné poznat termíny v počtu lambda, který, když vhodně interpretovaný, se chovat jako číslo 3 a jako operátor násobení.

Lambda počet je znán být computationally ekvivalentní v síle k mnoha jiným pravděpodobným modelům pro výpočet (včetně Turing strojů); to je, nějaké calculuation, které mohou jsou provedeny v některém tyto jiné modely mohou být vyjádřeny v počtu lambda a zlozvyk versa. Shodovat se k Kostel-Turing teze, oba modely mohou vyjádřit nějaký možný výpočet.

To možná překvapí to lambda-počet může reprezentovat nějaké představitelné výpočetní používání jen jednoduchá ponětí o abstrakci funkce a aplikaci založené na jednoduché textové náhradě termínů pro proměnné. Ale dokonce významnější je ta abstrakce není dokonce požadovaná. Combinatory logika je model výpočtu ekvivalentního k počtu lambda, ale bez abstrakce.

Combinatory calculi

Protože abstrakce je jediný způsob, jak vyrábět funguje v počtu lambda, něco musí nahradit to v počtu combinatory. Místo toho abstrakce, combinatory počet poskytuje omezený soubor primitivních funkcí ven kterých ostatních funkcí smět být stavěn.

Combinatory požadavky

Combinatory termín má jeden z sledování forem:

       V
       P
       (E1 E2)
kde V je proměnná, P je jeden z primitivních funkcí, nebo E1 a E2 combinatorial požadavky. Primitivní funkce sám jsou combinatorsnebo funkce, které obsahují žádné volné proměnné.

Příklady combinators

Nejjednodušší příklad combinator je Já, combinator identity, definovaný

       (Já x) = x
pro všechny požadavky x. Další jednoduchý combinator je K, který vyrábí funkce konstanty: (K x) je funkce který, pro jakýkoliv argument, návraty x, tak my říkáme

       ((K x) y) = x
pro všechny požadavky x a y. Nebo, dodržovat stejnou zvyklost pro rozmanitou aplikaci jak v lambda-počet,

       (K x y) = x
Třetí combinator je S, který je celková verze aplikace:

       (S x y z) = (x z (y z))
S platí x k y po prvním substituting z do každého je.

Daný S a K, Já sám je zbytečný od té doby, co to může být postavené od jiný dva:

        ((S K K) x) = (S K K x) = (K x (K x)) =  x
pro nějaký termín x. Si všimnout toho ačkoli ((S K K) x) = (Já x) pro některého x, (S K K) sám není se rovnat k Já. My říkáme termíny jsou extensionally se rovnají. Extensional rovnost zachytí matematické ponětí o rovnosti funkcí: že dvě funkce jsou ' se rovnat ' jestliže oni vždy přinesou stejné výsledky pro stejné argumenty. V kontrastu, požadavky sám zachytí ponětí o intensional rovnosti funkcí: že dvě funkce jsou ' se rovnat ' jediný jestliže oni mají totožný implemenations. Tam je mnoho způsobů, jak realizovat funkci identity; (S K K) a Já jsem mezi tyto cesty. (S K S) je ještě jeden. My budeme používat slovo ekvivalent ukázat extensional rovnost, rezervovat se rovnat pro totožné combinatorial požadavky.

Úplnost S-K základ

To je možná úžasná skutečnost, že S a K moci být složen k produkci combinators, které jsou extensionally rovné některému lambda termín, a proto, kostel je teze, k některému vypočitatelná funkce whatsoever. Důkaz má představovat transformaci, T[], který přemění libovolný lambda termín do ekvivalentu combinator.

T[] smět být definován takto:

  1. T[V] = > V
  2. T[(E1 E2)] = > (T[E1] T[E2])
  3. T[a lambda; x.E] = > (K E) (jestliže x je ne volný v E)
  4. T[a lambda; x.x] = > Já
  5. T[a lambda; x.a lambda; y.E] = > T[a lambda; x.T[a lambda; y.E]] (jestliže x je volný v E)
  6. T[a lambda; x. (E1 E2)] = > (S T[a lambda; x.E1] T[a lambda; x.E2])

Přeměna lambda termínu k rovnocennému combinatorial termínu

Například, my přeměníme lambda termín a lambda; x.a lambda; y. (y x)) k combinator:

         T[a lambda; x.a lambda; y. (y x)] = T[a lambda; x.T[a lambda; y. (y x)]] (5) = T[a lambda; x. (S T[a lambda; y.y] T[a lambda; y.x])] (6) = T[a lambda; x. (S Já       T[a lambda; y.x])] (4) = T[a lambda; x. (S Já       (K x))] (3) = (S T[a lambda; x. (S Já)] T[a lambda; x. (K x)]) (6) = (S (K (S Já))   T[a lambda; x. (K x)]) (3) = (S (K (S Já)) (S T[a lambda; x.K] T[a lambda; x.x])) (6) = (S (K (S Já)) (S (K K)   T[a lambda; x.x])) (3) = (S (K (S Já)) (S (K K)   Já)) (4)
Jestliže my aplikujeme tento combinator na nějaké dva termíny x a y, to sníží se takto:

         (S (K (S Já)) (S (K K)   Já) x y) = (K (S Já) x (S (K K)   Já x) y) = (S Já (S (K K)   Já x) y) = (Já y (S (K K)   Já x y )) = (y (S (K K)   Já x y )) = (y (K K x (Já x) y )) = (y (K (Já x) y )) = (y (Já x )) = (y x)
Combinatory reprezentace, (S (K (S Já)) (S (K K) Já)) je hodně delší než reprezentace jako termín lambda, a lambda; x.a lambda; y. (y x). Toto je typické. Obecně, T[] stavba může rozšířit lambda termín délky n k termínu combinatorial délky a théta;(3n).

Vysvětlení T[] transformace

T[] transformace je motivována touhou odklidit abstrakci. Dva zvláštní případy, pravidla 3 a 4, být triviální: a lambda; x.x je jasně rovnocenný k Já, a a lambda; x.E je jasně rovnocenný k (K E) jestliže x nevypadá volný v E.

První dvě pravidla jsou také jednoduchá: Proměnné konvertují k sobě, a aplikace, který být dovolen v combinatory termínech, být přeměněn na combinators jednoduše tím, že změní applicand a argument k combinators.

To má pravidla 5 a 6 to být zájmu. Pravidlo 5 jednoduše říká, že přeměnit abstrakci komplexu k combinator, my musíme nejprve změnit jeho tělo na combinator, a pak odklidit abstrakci. Pravidlo 6 vlastně odklidí abstrakci.

a lambda; x. (E1 E2) je funkce, která vezme argument, říkat , a náhrady to do termínu lambda (E1 E2) na místě x, poddajný (E1 E2) [/x]. Ale substituting do (E1 E2) na místě x je jen stejný jak substituting to do obou E1 a E2, tak

       (E1 E2) [/x] = (E1[/x] E2[/x])
       (a lambda; x. (E1 E2) ) = ((a lambda; x.E1 ) (a lambda; x.E2 )) = (S a lambda; x.E1 a lambda; x.E2 ) = ((S a lambda; x.E1 a lambda; x.E2) )
Extensional rovností,

       a lambda; x. (E1 E2) = (S a lambda; x.E1 a lambda; x.E2)
Proto, najít combinator ekvivalent k a lambda; x. (E1 E2), to je dostatečné najít combinator ekvivalent k (S a lambda; x.E1 a lambda; x.E2), a

       (S T[a lambda; x.E1] T[a lambda; x.E2])
zřetelně sedí účtu. E1 a E2 každý obsahovat přísně méně aplikací než (E1 E2), tak rekurze musí končit lambda termínem se žádnými aplikacemi vůbec -- - jeden proměnná, nebo termín formy a lambda; x.E.

Zjednodušení transformace

a eta; - redukce

Combinators vytvářel T[] transformace může být dělána menší jestliže my vezmeme v úvahu a eta; - redukce pravidlo:

       T[a lambda; x. (E x)] = T[E] (jestliže x je ne volný v E)
a lambda; x. (E x) je funkce, která vezme argument, x, a aplikuje funkci E k tomu; toto je extensionally stejné s funkcí E sám. To je proto dostatečné konvertovat E k formě combinatorial.

Brát toto zjednodušení do účtu, příklad nahoře se stojí:

         T[a lambda; x.a lambda; y. (y x)] =... = (S (K (S Já))   T[a lambda; x. (K x)])                 
       = (\S (K (S Já))   K) (a eta; - redukce)
Tento combinator je ekvivalent k dříve, delší:

         (S (K (S Já))   K x y) = (K (S Já) x (K x) y) = (S Já (K x) y) = (Já y (K x y)) = (y (K x y)) = (y x)
Podobně, původní verze T[] transformace přeměnila funkci identity a lambda; f.a lambda; x. (f x) do (S (S (K S) (S (K

K) Já)) (K Já)). S a eta; - pravidlo redukce, a lambda; f.a lambda; x. (f x) je transformován do Já.

Turnerovy combinators

David Turner našel metodu, která produkuje dokonce i kratší combinatory výrazy. On představí dva nové combinators:

       (B  b c) = ( c b) (C  b c) = ( (b c))
Používání tito combinators, my můžeme poskytnout pravidla pro transformaci takto:

  1. T[V] = > V
  2. T[(E1 E2)] = > (T[E1] T[E2])
  3. T[a lambda; x.E] = > (K E) (jestliže x je ne volný v E)
  4. T[a lambda; x.x] = > Já
  5. T[a lambda; x.a lambda; y.E] = > T[a lambda; x.T[a lambda; y.E]] (jestliže x je volný v E)
  6. T[a lambda; x. (E1 E2)] = > (S T[a lambda; x.E1] T[a lambda; x.E2]) (jestliže x je volný v obou E1 a E2)
  7. T[a lambda; x. (E1 E2)] = > (B T[a lambda; x.E1] E2) (jestliže x je volný v E1 ale ne E2)
  8. T[a lambda; x. (E1 E2)] = > (C E1 T[a lambda; x.E2]) (jestliže x je volný v E2 ale ne E1)

Soustružník používání je B a C combinators, transformace a lambda; x.a lambda; y. (y x) vypadá jako toto:

         T[a lambda; x.a lambda; y. (y x)] = T[a lambda; x.T[a lambda; y. (y x)]] = T[a lambda; x. (B T[a lambda; y.y] x)] (pravidlem 7) = T[a lambda; x. (B Já x)] = (B Já) (a eta; - redukce)
A opravdu, (B Já x y) laně sesadí na (y x):

         (B Já x y) = (Já y x) = (y x)
Motivace tady je to B a C jsou omezené verze S. Zatímco S vezme hodnotu a náhrady to do jak applicand tak jeho argumentu dříve vykonávat aplikaci, B vykonává náhradu jediný v applicand, a C jediný v argumentu.

Konverze zpáteční rychlosti

Konverze L[] od požadavků combinatorial k požadavkům lambda je triviální:

       L[Já] = a lambda; x.x
       L[K] = a lambda; x.a lambda; y.x
       L[B] = a lambda; x.a lambda; y.a lambda; z. (x z y)
       L[C] = a lambda; x.a lambda; y.a lambda; z. (x (y z))
       L[S] = a lambda; x.a lambda; y.a lambda; z. (x z (y z))
       L[(E1 E2)] = (L[E1] L[E2])
Poznámka, nicméně, že tato transformace není inverzní transformace některý verzí T[] že my jsme viděli.

Undecidability Combinatorial počtu

To je undecidable zda obecný combinatory termín má normální tvar; zda dva combinatory termíny jsou rovnocenné, etc. Toto je ekvivalent k undecidability korespondenčních problémů pro lambda požadavky. Nicméně, přímý důkaz je takto:

Nejprve, poznamenat, že termín

       W = (S Já Já (S Já Já))
má žádná normální forma, protože to sesadí na sebe po třech krokách, takto:

         (S Já Já (S Já Já)) = (Já (S Já Já) (Já (S Já Já))) = (S Já Já (Já (S Já Já))) = (S Já Já (S Já Já))
a jasně žádná jiná redukční objednávka může dělat výraz kratší.

Nyní, předpokládat N byl combinator pro odhalovat normální formy, takový to

       (N x) = > T, jestliže x má normální forma
                F, jinak.
(Kde T a F transformace konvenčních lambda-definice počtu pravdivý a nepravdivý, a lambda; x.a lambda; y.x a a lambda; x.a lambda; y.y. Combinatory verze mají T = K a F = (K Já).)

Nyní nechat

       Z = (B (B (C N (S Já Já)) W) Já)
nyní zvažovat termín (S Já Já Z). Dělá (S Já Já Z) mít normální tvar? To dělá jestliže a jediný jestliže pokračování dělat také:

         (S Já Já Z) = (Já Z (Já Z)) = (Z (Já Z)) = (Z Z) = (B (B (C N (S Já Já)) W) Já Z) (definice ) = (B (C N (S Já Já)) W Z Já) = (C N (S Já Já) Z W Já) = (N (S Já Já Z) W Já)
Teď my potřebujeme platit N k (S Já Já Z). Jeden (S Já Já Z) má normální forma, nebo to dělá ne. Jestliže to dělá mít normální tvar, pak předcházející se sníží takto:

         (N (S Já Já Z) W Já) = (K W Já) (definice N) = W
ale W dělá nemít normální tvar, tak my máme rozpor. Ale jestliže (S Já Já Z) dělá ne mít normální tvar, předcházející se sníží takto:

         (N (S Já Já Z) W Já) = (K Já W Já) (definice N) = (Já Já)
         Já
který znamená to normální forma (S Já Já Z) je jednoduše Já, další rozpor. Proto, hypotéza normální-combinator formy N moci ne existovat.

Combinatory termíny jako grafy

(Přidat detaily s ilustracemi; nezapomenou diskutovat o účinku fixovaný-bod combinators.)

Aplikace

Kompilace funkčních jazyků

Funkční programovací jazyky jsou často založené na jednoduché ale univerzální sémantice lambda počtu. (dodají detaily.)

(Diskutovat o přísném vs. lenivé ohodnocení sémantika. Všimněte si důsledků grafové redukční implementace pro lenivé ohodnocení. Poukázat na problém efektivity v lenivé sémantice: Opakoval ohodnocení stejného výrazu, v, např. (čtvercový komplikovaný) = > (* komplikovaný komplikovaný), normálně vyhnul se horlivým ohodnocením a hovor-- hodnota. Diskutovat o výhodě redukce grafu v tomto případě: když (čtvercový komplikovaný) je ohodnocen, reprezentace komplikovaný moci být sdílen oběma odvětvími výsledného grafu pro (* komplikovaný komplikovaný), a ocenil jen jednou.)

Logika

Karí-Howard izomorfismus implikuje vztah mezi logikou a programování: Každý platný důkaz teoréma logiky odpovídá si přímo k redukci lambda termínu a zlozvyk versa. Teorémy sám jsou poznáni s funkčními typovými podpisy.

(Sčítat: Demonstrace to axiómy

       (a -> a)
       (a -> b -> a)
       (a -> b -> c) -> (a -> b) -> (a -> c)
být kompletní pro intuitionistic fragment logiky propositional.)

Viz též:

Odkazy