Lambda Počet

2023 Autor: Noah Black | [email protected]. Naposledy změněno: 2023-11-26 16:06

Vstupní navigace

• Obsah příspěvku
• Bibliografie
• Akademické nástroje
• Náhled PDF přátel
• Informace o autorovi a citaci
• Zpět na začátek

Lambda počet

První publikováno 12. prosince 2012; zásadní revize 8. února 2013

Λ-počet je v podstatě jednoduchým zápisem funkcí a aplikací. Hlavními myšlenkami jsou aplikace funkce na argument a formování funkcí pomocí abstrakce. Syntaxe základního počtu λ-kalkulu je poměrně řídká, což z něj činí elegantní, soustředěný zápis reprezentující funkce. Funkce a argumenty jsou na stejné úrovni. Výsledkem je intenzivní teorie funkcí jako pravidel výpočtu, která kontrastuje s extenzivní teorií funkcí jako množiny uspořádaných párů. Přes jeho řídkou syntaxi, expresivita a flexibilita λ-kalkulu z ní činí hojnost logiky a matematiky. Tento příspěvek rozvíjí některé hlavní body oboru a připravuje čtenáře na další studium předmětu a jeho aplikací ve filozofii, lingvistice, informatice a logice.

• 1. Úvod

  • 1.1 Operace s více argumenty
  • 1.2 Intenzita

• 2. Syntaxe

  • 2.1 Proměnné, vázané a volné
  • 2.2 Kombinátory
• 3. Stručná historie λ-počtu

• 4. Redukce

  • 4.1 Další pojmy redukce
  • 4.2 Strategie snižování

• 5. λ-teorie

  • 5.1 Základní teorie λ
  • 5.2 Rozšíření základní teorie λ
• 6. Konzistence počtu λ
• 7. Sémantika λ-počtu

• 8. Rozšíření a variace

  • 8.1 Kombinovaná logika
  • 8.2 Přidávání typů

• 9. Aplikace

  • 9.1 Logika à la λ
  • 9.2 Výpočet
  • 9.3 Vztahy
• Bibliografie
• Akademické nástroje
• Další internetové zdroje
• Související záznamy

1. Úvod

Λ-kalkul je elegantní zápis pro práci s aplikacemi funkcí na argumenty. Abychom si vzali matematický příklad, předpokládejme, že dostáváme jednoduchý polynom, například x ²  - 2 · x + 5. Jaká je hodnota tohoto výrazu, když x = 2? Vypočítáme to 'připojením' 2 pro x ve výrazu: dostaneme 2 ²  - 2 · 2 + 5, které můžeme dále redukovat, abychom dostali odpověď 5. Abychom použili λ-kalkul k reprezentaci situace, začneme s termínem λ

A x [x ²  - 2 · x + 5].

Operátory λ nám umožňují abstraktovat přes x. Jeden může intuitivně číst 'λ x [x ²  - 2 · x + 5]' jako výraz, který čeká na hodnotu a pro proměnnou x. Když je dána taková hodnota a (jako je číslo 2), hodnota výrazu je ²  - 2 · a + 5. 'λ' samo o sobě nemá význam; pouze váže proměnnou x a chrání ji před vnějšími vlivy. Terminologie v λ-kalkulu je taková, že chceme tento výraz použít na argument a získat hodnotu. Píšeme „M a“, abychom označili aplikaci funkce M na argument a. Pokračováním příkladu získáme:

	(A x [x 2  - 2 · x + 5]) 2
⊳	⟨Náhrada 2 za x⟩
	2 2  - 2 · 2 + 5
=	⟨Aritmetika⟩
	4 - 4 + 5
=	⟨Aritmetika⟩
	5

Prvním krokem tohoto výpočtu, připojením '2' pro výskyt x ve výrazu 'x ² - 2 · x + 5', je přechod od abstrakčního členu k jinému členu operací substituce. Zbývající rovnosti jsou odůvodněny výpočtem s přirozenými čísly.

Tento příklad navrhuje ústřední princip λ-kalkulu, který se nazývá β-redukce:

(β) (λ x [M]) N ⊳ M [x: = N]

Rozumí se, že můžeme omezit nebo zkrátit (⊳) aplikaci (λ x M) N abstrakčního termínu (levá strana, λ x M) na něco (pravá strana, N) pouhým připojením N pro výskyt x uvnitř M (to je to, co vyjadřuje zápis 'M [x: = N]'). Toto je princip β-redukce; je to srdce λ-kalkulu.

1.1 Operace s více argumenty

A co funkce více argumentů? Může λ-kalkul představovat operace, jako je výpočet délky převisu pravého trojúhelníku:

Hypotenuse pravého trojúhelníku s nohami o délce x a y and √ (x ² + y ²),

Operace délka hypotéky mapuje dvě kladná reálná čísla xay a na další kladná reálná čísla. Jeden může představovat takové operace s více arity pomocí aparátu A-počtu tím, že sleduje operaci jako přijímání jednoho vstupu najednou. Operaci lze tedy chápat jako přijímání jednoho vstupu, x, kladného reálného čísla, a produkující jako svou hodnotu ne číslo, ale operaci: jmenovitě operaci, která bere kladné reálné číslo y jako vstup a produkuje jako výstup kladné reálné číslo √ (x ² + y ²). Dalo by se shrnout diskusi tím, že operace, délka tykve, která spočítá délku tykve pravého trojúhelníku vzhledem k délkám a a b jeho nohou, je:

délka hypotéky: = λ a [λ b [√ (a ² + b ²)]

Zásadou β-redukce máme například to, že délka hypotéky 3, aplikace délky hypotéky na 3, je λ b [√ (3² + b ²)], což je její funkce čeká na další argument. Λ-termín hypotéka délka 3 lze považovat za funkci, která spočítá délku hypotenze pravého trojúhelníku o délce jednoho z jeho nohou 3. Nakonec zjistíme, že (délka hypotenze 3) aplikace délky hypotéky na 3 a poté na 4 je 5, jak se očekávalo.

Dalším způsobem, jak porozumět redukci mnoha funkcí na jedno místo, je představit si stroj M, který zpočátku začíná načtením prvního a více argumentů a, b, … do paměti. Jestliže jeden pak pozastaví stroj po načtení první argument do paměti, lze zobrazit výsledek jako další stroj M _A, který je čeká jeden méně vstup; první argument je nyní opraven.

1.2 Intenzita

Představa funkce nebo operace při práci v λ-kalkulu je náročná. Můžeme zobrazit λ x [M] jako popis operace, která při dané x produkuje M; tělo M abstrakčního členu je samo popis toho, co dělat s x. Intuitivně, vzhledem k popisům M a N, se obecně nemůžeme rozhodnout, zda λ x [M] se rovná λ x [N]. Tyto dva výrazy by se mohly „chovat“stejně (mít stejnou hodnotu vzhledem ke stejným argumentům), ale nemusí být jasné, jaké zdroje jsou potřebné k prokázání rovnosti termínů.

Naproti tomu definice funkce v teorii množin jako množina f uspořádaných párů splňující vlastnost, kterou (x, y) ∈ f a (x, z) ∈ f implikují y = z. Pojem rovnost funkcí je rovnost funkcí qua množin, která podle standardního principu rozšiřitelnosti množin znamená, že dvě funkce jsou si rovny, pokud obsahují stejné uspořádané páry.

K λ-kalkulu lze přidat jakýsi princip rozšiřitelnosti; viz oddíl 5.2.

2. Syntaxe

Oficiální syntaxe λ-počtu je poměrně jednoduchá; to je obsaženo v další definici.

Definice Pro abecedu jazyka λ-kalkulu bereme levou a pravou závorku, levou a pravou hranatou závorku, symbol 'λ' a nekonečnou množinu proměnných. Třída λ-termínů je definována induktivně následovně:

1. Každá proměnná je λ-term.
2. Pokud M a N jsou λ-termy, pak je to také (MN).
3. Pokud M je λ-term a x je proměnná, pak (λ x [M]) je λ-term.

Termínem „termín“vždy myslíme termín „λ-termín“. Pojmy vytvořené podle pravidla (2) se nazývají aplikační podmínky. Pojmy vytvořené podle pravidla (3) se nazývají abstrakční termíny.

Jak je běžné při jednání s formálními jazyky, které mají seskupovací symboly (v našem případě levá a pravá závorka), některé závorky budou vynechány, pokud je to bezpečné (tj. Když je lze znovu zavést pouze jedním rozumným způsobem)). Spojení více než dvou termínů λ je přísně vzato nezákonné. Abychom se vyhnuli tediu vždy psaní všech potřebných závorek, přijímáme následující konvenci:

Konvence (přiřazení zleva): Pokud jsou vedle sebe více než dva termíny M ₁ M ₂ M ₃ … M _n, můžeme obnovit chybějící závorky přidružením doleva: čtení zleva doprava, skupiny M ₁ a M ₂ dohromady, výtěžek (M ₁ M ₂) M ₃ … M _n; pak seskupte (M ₁ M ₂) s M ₃: ((M ₁ M ₂) M ₃)… M _n, atd.

Konvence tak dává jedinečné čtení jakékoli sekvenci X-termínů, jejichž délka je větší než 2.

2.1 Proměnné, vázané a volné

Funkce λ v abstrakčním členu (λ x [M]) je taková, že váže proměnnou, která se objevuje bezprostředně za ní v termínu M. A je tedy analogické univerzálním a existenciálním kvantifikátorům ∀ a ∃ logiky prvního řádu. Analogicky lze definovat pojmy volné a vázané proměnné očekávaným způsobem následujícím způsobem.

Definice Syntaktické funkce FV a BV (pro „volnou proměnnou“a „vázanou proměnnou“) jsou definovány na množině λ-termínů strukturální indukcí, takže:

Volný, uvolnit	Vázaný
Pro každou proměnnou x, FV (x) = {x}. Pro každý termín M a každý termín N, FV (MN) = FV (M) ∪ FV (N). Pro každou proměnnou x a každý termín M, FV (λ x [M]) = FV (M) - {x}.	Pro každou proměnnou x, BV (x) = ∅. Pro každý termín M a každý termín N, BV (MN) = BV (M) ∪ BV (N). Pro každou proměnnou x a každý termín M, BV (λ x [M]) = BV (M) ∪ {x}.

Pokud FV (M) = ∅, pak se M nazývá kombinator.

Klauzule (3) ve dvou definicích podporuje záměr, že λ váže proměnné (zajišťuje, že nejsou volné). Všimněte si rozdílu mezi BV a FV u proměnných.

Jak je typické v jiných předmětech, kde se objevují koncepty, jako je logika prvního řádu, je třeba o této záležitosti dávat pozor; příležitostný přístup k substituci může vést k syntaktickým obtížím. ^[1] Můžeme bránit příležitostný přístup přijetím úmluvy, že nás nezajímá samy o sobě, ale určité třídy ekvivalence. Nyní definujeme substituci a poté stanovíme konvenci, která nám umožní vyhnout se takovým obtížím.

Definice (substituce) Píšeme 'M [x: = N]', abychom označili substituci N za volné výskyty x v M. Přesná definice ^[2] rekurzí na množině λ-podmínek je následující: pro všechny pojmy A, B a M a pro všechny proměnné x a y definujeme

1. x [x: = M] ≡ M
2. y [x: = M] ≡ y (y odlišné od x)
3. (AB) [x: = M] ≡ A [x: = M] B [x: = M]
4. (λ x [A]) [x: = M] ≡ λ x [A]
5. (λ y [A]) [x: = M] ≡ λ y [A [x: = M] (y odlišné od x)

Klauzule (1) definice jednoduše říká, že pokud máme nahradit M za x a jednáme jednoduše s x, pak je výsledkem pouze M. Ustanovení (2) říká, že se nic neděje, když jednáme (pouze) s proměnnou odlišnou od x, ale musíme něco nahradit x. Ustanovení (3) nám říká, že substituce se bezpodmínečně distribuuje v aplikacích. Ustanovení (4) a (5) se týkají abstrakčních termínů a paralelních ustanovení (1) a (2) (nebo spíše ustanovení (2) a (1) v opačném pořadí): Pokud je vázaná proměnná z abstrakčního termínu λ z [A] je identická s proměnnou x, pro kterou máme provést substituci, pak neprovádíme žádnou substituci (tj. Substituce „zastaví“). To je v souladu s úmyslem, že M [x: = N] má označovat substituci N za výskyty volných x v M. Je-li M abstrakční člen λ x [A], jehož vázaná proměnná je x, pak se x v M nevyskytuje volně, takže není co dělat. To vysvětluje ustanovení 4. Klauzule (5), konečně, říká, že pokud se vázaná proměnná abstrakčního členu liší od x, pak alespoň x má „šanci“, že se v abstrakčním termínu vyskytne volně, a substituce pokračuje do těla termín abstrakce.

Definice (změna vázaných proměnných, α-konvertibilita, konvence bez záchytu o β-konverzi) Termín N je získán z termínu M změnou vázaných proměnných, pokud zhruba jakýkoli abstrakční člen λ x [A] uvnitř M má byl nahrazen λ y [A [x: = y].

Řekněme, že termíny M a N jsou a-konvertibilní, pokud existuje sekvence změn vázaných proměnných počínaje M a končící N.

Nakonec souhlasíme, že když píšeme

'(λ x [M]) N se redukuje na M [x: = N]',

požadujeme, aby se žádná proměnná vyskytující se volně v N po vazbě na M nevázala.

Zhruba musíme dodržovat zásadu, že volné proměnné by měly zůstat volné; pokud hrozí, že výskyt proměnné bude vázán substitucí, jednoduše proveďte dostatečné a-převody, abyste se vyhnuli problému. Pokud to budeme mít na paměti, můžeme pracovat s λ-kalkulem, aniž bychom se museli obávat syntaktických obtíží.

Syntaxe λ-počtu je poměrně flexibilní. Jeden může tvořit nejrůznější termíny, dokonce i self-aplikace takový jako xx. Takové výrazy se na první pohled zdají podezřelé; jeden by mohl mít podezření, že použití takových termínů by mohlo vést k nekonzistentnosti, a v každém případě by se člověk mohl dostat za nástroj, kterým by takové termíny zakázal. Pokud bychom měli prohlížet funkce a sady uspořádaných párů určitého druhu, pak by x v xx byla funkce (sada uspořádaných párů), která obsahuje jako prvek pár (x, y), jehož první prvek by byl x sám. Žádný soubor se však nemůže takto izolovat, aby nedošlo k porušení axiomu nadace (nebo pravidelnosti). Z teoretického hlediska jsou tedy tyto pojmy jasně pochybné. Níže je uveden krátký náčrt jednoho takového nástroje, teorie typů. Ve skutečnosti však takové termíny nevedou k nekonzistentnosti a slouží užitečnému účelu v kontextu počtu λ. Navíc zakazování takových termínů, jako je tomu v teorii typů, nepřichází zdarma (např. Část expresivity netypovaného λ-kalkulu je ztracena).

2.2 Kombinátory

Jak bylo definováno dříve, kombinátor je λ-termín bez volných proměnných. Kombinátory lze intuitivně chápat jako „zcela specifikované“operace, protože nemají žádné volné proměnné. Existuje několik kombinátorů, které se osvědčily v historii λ-kalkulu; následující tabulka vyzdvihuje některé z těchto speciálních kombinátorů. Mohlo by být dáno mnohem více (a samozřejmě existuje nekonečně mnoho kombinátorů), ale následující mají stručné definice a prokázaly svou užitečnost.

Některé standardní λ-termíny a kombinátory

název	Definice a komentáře
S	λ x [λ y [λ z [xz (yz)] Mějte na paměti, že „xz (yz)“je třeba chápat jako aplikaci (xz) (yz) z xz na yz. S lze tedy chápat jako operátor nahrazení a použití: z 'zasahuje' mezi xay: místo použití x na y použijeme xz na yz.
K	λ x [λ y [x] Hodnota K M je konstantní funkce, jejíž hodnota pro jakýkoli argument je jednoduše M.
Já	λ x [x] Funkce identity.
B	λ x [λ y [λ z [x (yz)] Připomeňme, že „xyz“je třeba chápat jako (xy) z, takže tento kombinátor není triviální funkcí identity.
C	λ x [λ y [λ z [xzy] Zaměňuje argument.
T	λ x [λ y [x] Pravda je pravdivá. Shodné s K. Později uvidíme, jak tyto reprezentace hodnot pravdy hrají roli v prolnutí logiky a λ-kalkulu.
F	λ x [λ y [y] Pravdivá hodnota nepravdivá.
ω	λ x [xx] Samoobslužný kombinátor
Ω	ωω Samo-aplikace kombinátoru samo-aplikace. Snižuje se na sebe.
Y	λ f [(λ x [f (xx)]) (λ x [f (xx)])] Curryho paradoxní kombinátor. Pro každý λ-termín X máme: Y X ⊳ (λ x [X (xx)]) (λ x [X (xx)]) ⊳ X ((A x [X (xx)]) (A x [X (xx)])) První krok redukce ukazuje, že Y X se redukuje na aplikační období (Xx [X (xx)]) (Xx [X (xx)]), které se ve třetím kroku opakuje. Tak, Y má kuriózní vlastnost, že Y X a X (Y X) převést na společného termínu.
Θ	(λ x [λ f [f (xxf)]) (λ x [λ f [f (xxf)]) Turingův kombinátor s pevným bodem. Pro každý λ-termín X se Θ X sníží na X (Θ X), což lze potvrdit ručně. (Curryho paradoxní kombinátor Y tuto vlastnost nemá.)

V této položce jsou používány notační konvence

Zápis	Čtení a komentáře
MN	Použití funkce M na argument N. Obvykle se závorky používají k oddělení funkce od argumentu, například: 'M (N)'. Avšak u λ-počtu a příbuzných předmětů jsou závorky použity jako seskupovací symboly. Je tedy bezpečné napsat funkci a argument sousedící s ostatními.
PQR	Aplikace funkce PQ - která je sama o sobě aplikací funkce P na argument Q-to R. Pokud nepoužíváme závorky k oddělení funkcí a argumentů, jak můžeme disambiguovat výrazy, které zahrnují tři nebo více výrazů, například „PQR“? Připomeňme naši konvenci, že máme pochopit takové oficiálně nezákonné výrazy tím, že pracujeme zleva doprava a vždy uvádějte závorky kolem sousedních výrazů. „PQR“je tedy třeba chápat jako (PQ) R. 'PQRS' je ((PQ) R) S. Výraz '(PQ) R' je nezpochybněný; podle naší úmluvy je totožné s PQR. Výraz „P (QR)“je také výslovně nesrozuměn; je odlišný od PQR, protože se jedná o aplikaci P na argument QR (což je samo o sobě použití funkce Q na argument R).
(λ x [M])	Termín λ, který váže proměnnou x v těle termín M. Úřední slovník λ-kalkulu se skládá ze závorek se symbolem „λ“, levého “(„ a pravého “) a ze souboru proměnných (předpokládá se, že se liší od tří symbolů„ λ “,„ (“a ')' Abychom neměli syntaktický chaos). Alternativní zápis. Není nutné zahrnout do syntaxe dva druhy skupinových symbolů (závorky a hranaté závorky). Samotné závorky nebo hranaté závorky by zřejmě stačily. V této položce jsou použity dva druhy závorek kvůli čitelnosti. Vzhledem k těmto dvěma druhům seskupovacích symbolů bychom mohli dále šetřit a vynechat závorky z abstrakčních termínů, takže „(λ x [M])“bude zapsáno jako „λ x [M]“. Někteří autoři píší 'λ x. M 'nebo' λ x · M 's tečkou nebo středovou tečkou oddělující vázanou proměnnou od těla abstrakčního členu. Stejně jako u hranatých závorek jsou tato zařízení určena ke čtení podmínek λ; obvykle nejsou součástí oficiální syntaxe. (Jeden vidí toto zařízení používané v dřívějších logických pracích, jako je Principia Mathematica, kde funkce symbolu. Ve výrazech, jako je '∀ x. Is', má přimět nás, abychom si přečetli celý vzorec φ jako v rámci rozsahu ∀ x.) Někteří autoři píšou abstrakční termíny bez jakéhokoli zařízení oddělujícího vázanou proměnnou od těla: takové termíny jsou ostře psány jako např. „Λ xx“, „λ yx“. Cvičení není bez jeho zásluh: je to tak stručné, jak si člověk může vyžádat, a umožňuje ještě jednodušší oficiální syntaxi λ-kalkulu. Tato praxe však není bezchybná. V 'λ xyz', je vázaná proměnná x, nebo je to xy? Jména proměnných jsou obvykle jednoduchá písmena a teoreticky je to dostačující. Zdá se však nepřiměřeně restriktivní zakazovat postup přidělování proměnných dlouhým jménům; skutečně takové konstrukce vznikají přirozeně v počítačových programovacích jazycích. V zájmu jednotnosti použijeme v této položce zápis s hranatými závorkami. (Mimochodem, tento zápis se používá v (Turing, 1937).)
M [x: = A]	Λ-termín, který je získán nahrazením λ-term A za všechny výskyty volných x uvnitř M. V literatuře o λ-kalkulu a spřízněných předmětech najdete ohromující řadu zápisů reprezentujících substituci: M [x / A], M [A / x], M x A, M A x, [x / A] M,… Který zápis, který se má použít jako náhrada, se jeví jako osobní záležitost. V této položce používáme lineární notaci, vyhýbání horních a dolních indexů. Praxe reprezentace substituce ': =' pochází z informatiky, kde ': =' se v některých programovacích jazycích čte jako přiřazení hodnoty proměnné. Stejně jako u hranatých závorek používaných pro psaní abstrakčních termínů, hranaté závorky používané pro zápis substitucí nejsou oficiálně součástí syntaxe λ-kalkulu. M a A jsou termíny, x je proměnná; M [x: = A] je další termín.
M ≡ N	A-termíny M a N jsou identické: chápané jako sekvence symbolů, M a N mají stejnou délku a odpovídající symboly sekvencí jsou identické. Syntaktický vztah identity ≡ není součástí oficiální syntaxe λ-počtu; tento vztah mezi λ-termy patří do metatheory λ-počtu. Je to zjevně poněkud přísná představa rovnosti mezi podmínkami λ. Není tedy případ (pokud x a y jsou odlišné proměnné), že λ x [x] ≡ λ y [y], i když se tyto dva termíny zjevně „chovají“stejným způsobem ve smyslu, že oba jsou výrazy operace identifikace x ⇒ x. Později vytvoříme formální teorie rovnosti λ-termů s cílem zachytit tuto intuitivní rovnost λ x [x] a λ y [y].

3. Stručná historie λ-počtu

λ-počet vznikl ze studia funkcí jako pravidel. Již základní složky tohoto předmětu lze nalézt ve Fregeově průkopnickém díle (Frege, 1893). Frege, jak jsme to řekli výše, Frege poznamenal, že při studiu funkcí stačí soustředit se na unární funkce (tj. Funkce, které berou přesně jeden argument). (Postup prohlížení operace s více arity jako sledu abstrakcí, které dávají ekvivalentní unární operaci, se nazývá currying operace. Možná by bylo historicky přesnější nazvat operaci fregeing, ale v označení matematických myšlenek často dochází k justičním omylům.) Ve dvacátých letech minulého století matematik Moses Schönfinkel tento předmět dále studoval pomocí tzv. kombinátorů. Jak bylo běžné v prvních dnech předmětu, Schönfinkel se zajímal o druhy transformací, které člověk vidí ve formální logice, a jeho kombinátory byly zamýšleny jako příspěvek k základům formální logiky. Analogicky s redukcí, kterou člověk vidí v klasické výrokové logice pomocí Shefferovy mrtvice, Schöfinkel zjistil úžasný výsledek, že všechny funkce (ve smyslu všech transformací) by mohly být dány jako kombinátory K a S; Později uvidíme definici těchto kombinátorů.

Věta Pro každý termín M složený z K a S a proměnné x existuje pojem F (vytvořený pouze z K a S), takže můžeme odvodit F x = M.

(Důkaz, že tyto dvě stačit k reprezentaci všech funkcí, je nad rámec tohoto záznamu. Pro další diskusi viz záznam o kombinatorické logice.) Jeden může dokázat teorém konstruktivně: existuje algoritmus, který vzhledem k M, produkuje požadované F. Kostel nazýval tento F 'λ x [M]' (Church, 1932). ^[3] Z tohoto hlediska lze β-pravidlo ospravedlnit: pokud „λ x [M]“má být funkcí F splňující F x = M, pak λ x [M] x by se mělo transformovat na M. Toto je jen zvláštní případ obecnější zásady, že pro všechny N, (λ x [M]) N by se měla transformovat na M [x: = N].

Ačkoli dnes máme jasněji ohraničené systémy abstrakce a přepisování, v počátcích byly λ-počet a kombinovaná logika (à la Schönfinkel) spojeny s vyšetřováním základů matematiky. V rukou Curryho, Církve, Kleene a Rossera (někteří průkopníci v tomto předmětu) se pozornost soustředila na definování matematických objektů a provádění logického uvažování uvnitř těchto nových systémů. Ukázalo se, že tyto rané pokusy o tzv. Illativní λ-kalkul a kombinatorickou logiku byly nekonzistentní. Curry izoloval a vyleštil nesrovnalost; výsledek je nyní známý jako Curryho paradox. Viz položka o Curryho paradoxu a dodatek B (Barendregt, 1985).

Λ-kalkul získává zvláštní místo v historii logiky, protože to byl zdroj prvního nerozhodnutelného problému. Problém je: za podmínek λ a M a N určete, zda M = N. (Teorie rovnice uvažování o λ-termíny ještě nebyla definována; definice přijde později.) Tento problém se ukázal jako nerozhodnutelný.

Dalším časným problémem v počtu A bylo to, zda je vůbec konzistentní. V této souvislosti nekonzistence znamená, že všechny termíny jsou si rovny: jeden může redukovat jakýkoli λ-termín M na jakýkoli λ-termín N. To, že tomu tak není, je časným výsledkem λ-počtu. Zpočátku jeden měl výsledky ukazovat, že jisté termíny nebyly vzájemně zaměnitelné (např. K a S); později, mnohem silnější výsledek, takzvaná Church-Rosserova věta, pomohl vrhnout více světla na β-konverzi a mohl být použit k poskytnutí rychlých důkazů o nepřevoditelnosti celých tříd λ-termínů. Viz níže pro podrobnější diskusi o konzistenci.

A-počet byl poněkud nejasný formalismus až do šedesátých let, kdy byla nakonec nalezena „matematická“sémantika. Rovněž byl objasněn její vztah k programovacím jazykům. Do té doby byly jedinými modely λ-kalkulu „syntaktické“, to znamená, že byly vytvořeny ve stylu Henkina a sestávaly z tříd ekvivalence λ-výrazů (pro vhodné pojmy ekvivalence). Aplikace v sémantice přirozeného jazyka, díky vývoji Montague a dalších lingvistů, pomohly „šířit slovo“o předmětu. Od té doby má λ-kalkul významné místo v matematické logice, informatice, lingvistice (viz např. Heim a Kratzer 1998) a příbuzných oborech.

4. Redukce

K dispozici jsou různé pojmy redukce pro λ-termy, ale hlavní je redukce β-redukce, kterou jsme již viděli dříve. Dříve jsme použili notaci '⊳' můžeme být přesnější. V této části diskutujeme β-redukci a některá rozšíření.

Definice (jednostupňová β-redukce ⊳ _{β, 1}) Pro λ-termíny A a B říkáme, že Ap β-redukuje v jednom kroku na B, psané A ⊳ _{β, 1} B, jen v případě, že existuje (výskyt) a) dílčí část C A, proměnná x a λ-termíny M a N tak, že C ≡ (λ x [M]) N a B je A kromě toho, že výskyt C v A je nahrazen M [x: = N].

Zde je několik příkladů β-redukce:

1. Proměnná x se neredukuje na nic. (Nemá správný tvar: je to jednoduše proměnná, nikoli aplikační termín, jehož levá strana je abstrakční termín.)
2. (λ x [x]) a ⊳ _{β, 1a}.
3. Jestliže x a y jsou odlišné proměnné, pak (λ x [y]) a ⊳ _{β, 1} y.

4. Λ-termín (λ x [(λ y [xy]) a]) b β-redukuje v jednom kroku na dva různé λ-termy:

   (λ x [(λ y [xy]) a]) b ⊳ _{β, 1} (λ y [by]) a

   a

   (λ x [(λ y [xy]) a]) b ⊳ _{β, 1} (λ x [xa]) b

   Kromě toho lze zkontrolovat, zda se tyto dva termíny β-redukují v jednom kroku na běžný termín: ba. Máme tedy:

   		(λ y [by]) a
   	↗		↘
   (λ x [(λ y [xy]) a]) b				ba
   	↘		↗
   		(A x x [xa]) b

Jako u každého binárního vztahu lze položit mnoho otázek o vztahu ⊳ _{β, 1, který} drží mezi λ-termy, a lze definovat různé odvozené pojmy jako ⊳ _{β, 1}.

Definice A - redukční sekvence od A-A do A-B je konečná posloupnost s ₁,… _sn z X-termínů začínajících A, končících B a jejichž sousední členy (s _k, s _{k +1}) uspokojí vlastnost, která s _k ⊳ _{β, 1} s _{k +1}.

Obecněji řečeno, jakákoli sekvence s -finit nebo nekonečná začínající A-termínem A je označována jako p-redukční sekvence začínající na A za předpokladu, že sousední členy (s _k, s _{k +1}) z splňují vlastnost, která s _k ⊳ _{β, 1} s _{k +1}.

1. Pokračování s p-redukcí z příkladu 1 neexistují vůbec žádné p-redukční sekvence začínající proměnnou x.

2. Pokračování s p-redukcí příkladu 2, dvoudobé sekvence

   (λ x [x]) a, a

   je p-redukční sekvence od (A x [x]) a do a. Je-li a proměnná, pak nemůže být tato β-redukční sekvence prodloužena a neexistují žádné jiné β-redukční sekvence začínající (A x [x]) a; sada β-redukčních sekvencí počínaje (Xx [x]) a je tedy konečná a neobsahuje žádné nekonečné sekvence.

3. Kombinátor Ω má zvláštní vlastnost, že Ω ⊳ _{β, 1} Ω. Každý termín každé β-redukční sekvence začínající na Ω (konečný nebo nekonečný) je roven Ω.

4. Uvažujme termín K a Ω. S tímto termínem začíná nekonečně mnoho redukčních sekvencí:

   • K W ⊳ _{beta, 1}
   • K W ⊳ _{beta, 1} K W ⊳ _{beta, 1}
   • K a Ω ⊳ _{β, 1} Ka a Ω ⊳ _{β, 1} Ka a Ω ⊳ _{β, 1} a
   • K a Ω ⊳ _{β, 1} Ka a Ω ⊳ _{β, 1} Ka a Ω …

   Jestliže a je proměnná, můžeme vidět, že všechny konečné redukční sekvence začínající K a Ω koncem v a, a existuje přesně jedna nekonečná redukční sekvence.

Definice P-redex A -termínu M je (výskyt) subtermem M tvaru (A x [P]) Q. ('redex' pochází z 'redukovatelné exprese.) β-redex je jednoduše kandidátem pro aplikaci β-redukce. Když tak učiníte, uzavírá se β-redex. Termín je řekl, aby byl v B-normální formě, pokud nemá žádné p-redexy.

(Může mít výraz více β-normálních forem? Odpověď je doslovně „ano“, ale v podstatě je odpověď „ne“: Pokud jsou M a M 'β-normální formy nějakého termínu, pak M je α-konvertibilní na M 'Tedy, p-normální formy jsou jedinečné až do změn vázaných proměnných.)

Doposud jsme se zaměřili pouze na jeden krok β-redukce. Jeden může kombinovat více kroků redukce p do jednoho tím, že vezme tranzitivní uzavření vztahu ⊳ _{β, 1}.

Definice Pro λ-termíny A a B, jeden říká, že Ap - redukuje na B, psaný A ⊳ _β B, pokud buď A ≡ B, nebo existuje konečná β-redukční sekvence od A do B.

Definice Termín M má p-normální formy, pokud existuje termín N tak, že N je v beta-normální zaznamenání M ⊳ _beta N.

Redukovatelnost, jak je definována, je jednosměrný vztah: obecně není pravda, že pokud A ⊳ _β B, pak B ⊳ _β A. V závislosti na svých cílech však lze chtít zacházet s A a B jako s rovnocennými, pokud se A buď redukuje na B, nebo B redukuje na A. V opačném případě činí s ohledem na reflexivní, symetrická a tranzitivní uzávěr vztahu ⊳ _{p, 1,}.

Definice Pro λ-termíny A a B, říkáme, že A = _β B, pokud buď A ≡ B, nebo pokud existuje sekvence s ₁,… s _n začínající A, končící B, a jejíž sousední termíny (s _k, s _{k +1}) jsou takové, že buď s _k ⊳ _{β, 1} s _{k +1} nebo s _{k +1} ⊳ _{β, 1} s _k.

4.1 Další pojmy redukce

Dosud jsme vyvinuli teorii β-redukce. Toto není v žádném případě jediný pojem redukce, který je k dispozici v λ-kalkulu. Kromě β-redukce je standardní vztah mezi λ-termíny také η-redukce:

Definice (jednostupňová η-redukce) Pro λ-termíny A a B říkáme, že βη-se v jednom kroku redukuje na B, napsané A ⊳ _{βη, 1} B, jen v případě, že existuje (výskyt a) subterm C z A, proměnná x a λ-termíny M a N tak, že buď

C ≡ (λ x [M]) N a B je A s tím rozdílem, že výskyt C v A je nahrazen M [x: = N]

nebo

C ≡ (λ x [M x]) a B je A s tou výjimkou, že výskyt C v A je nahrazen M.

První věta v definici ⊳ _{βη, 1} zajišťuje, že vztah rozšiřuje vztah jednostupňové β-redukce. Stejně jako jsme to udělali pro vztah jednostupňové β-redukce, můžeme přehrát vývoj pro η-redukci. Tak, jeden má představu η-redex, a od ⊳ _{η, 1} jeden může definovat vztah ⊳ _η mezi λ-termíny jako symetrický a tranzitivní uzavření ⊳ _{η, 1}, který zachytí nula nebo více kroků η-redukce. Pak jeden definuje = _η jako symetrické a přechodné uzavření ⊳ _η.

Jestliže A ⊳ _{η, 1} B, pak délka B je přísně menší než délka A. Nemůže tedy dojít k nekonečným η-redukcím. Toto není případ p-redukce, jak jsme viděli výše v příkladech 3 a 4 p-redukční sekvence.

Lze kombinovat pojmy redukce. Jednou užitečnou kombinací je smísení redukce p a η.

Definice (jednostupňová redukce βη) λ x [M x] ⊳ _{βη, 1} M a (A x [M]) N ⊳ _{βη, 1} M [x: = N]. A-termín Apη-redukuje v jednom kroku na X-termín B právě v případě, že buď A p-redukuje na B v jednom kroku, nebo A n-redukuje na B v jednom kroku.

Opět lze přehrát základní pojmy redukce, jako jsme to udělali pro β-redukci, pro tento nový pojem redukce βη.

4.2 Strategie snižování

Připomeňme si, že se říká, že je v β-normální formě, pokud nemá β-redexy, tj. Subtermy tvaru (A x [M]) N. Termín má β-normální formu, pokud jej lze redukovat na termín v β-normální formě. Mělo by být intuitivně jasné, že pokud má výraz β-normální formu, můžeme ji najít tak, že se vyčerpávajícím způsobem uzavře všechny všechny β-redexy termínu, potom se vyčerpávajícím způsobem zkrátí všechny β-redexy všech výsledných termínů atd. Řeknout, že termín má β-normální formu, znamená, že toto slepé hledání jednoho nakonec skončí.

Slepé hledání β-normálních forem není uspokojivé. Kromě toho, že je esteticky nepříjemný, může být docela neefektivní: nemusí být nutné vyčerpávajícím způsobem stahovat všechny p-redexy. Hledá se strategie - nejlépe srovnatelná - pro nalezení β-normální formy. Problémem je efektivně rozhodnout, zda existuje více β-redexů termínu, který by měl být snížen.

Definice strategie β-redukce je funkce jehož doména je množina všech lambda-podmínek a jehož hodnota na období M není v beta-normální formy je REDEX subterm M, a jehož hodnota na všech podmínek M v p-normální forma je jednoduše M.

Jinými slovy, strategie redukce β vybere, kdykoli má výraz více β-redexů, který z nich by měl být uzavřen. (Pokud je termín v β-normální formě, pak se nic nedělá, proto v definici β-redukční strategie požadujeme, aby nezměnil žádný termín v β-normální formě.) Jeden může představovat strategii s jako vztah ⊳ _s na lambda-podmínek, s tím, že M ⊳ _s N za předpokladu, že M je získán z M v jednom kroku drží strategie S. Při pohledu jako vztahy, strategie představují subrelation z ⊳ _{beta, 1}.

Strategie β-redukce může nebo nemusí mít vlastnost, která dodržuje strategii, zajistí, že my (případně) dosáhneme β-normální formy, pokud existuje.

Definice A-redukční strategie S je normalizována, pokud pro všechny λ-termíny M, pokud M má β-normální formu N, pak sekvence M, S (M), S (S (M)), … končí na N.

Některé strategie redukce β se normalizují, jiné nikoli.

• Strategie zcela vpravo, kdy se vždy rozhodneme redukovat pravý β-redex (pokud existují β-redexy), není normalizována. Uvažujme například termín KIω. Tento termín má dva p-redexy: sám a ω (což, vzpomínáme, je termín (λx [xx]) (xx [xx])). Práce s levými β-redexy umožňuje β-redukci KIω na I ve dvou krocích. Pokud budeme trvat na práci s nejpravější beta-REDEX ω snížíme KIω se KI (ωω), a pak KI (ωωω), ….
• Strategie zcela vlevo, kdy se vždy rozhodneme snížit nejvíce vlevo β-redex (pokud existují β-redexy), je normalizována. Důkaz této skutečnosti je nad rámec tohoto záznamu; viz (Barendregt, 1985, oddíl 13.2) pro podrobnosti.

Jakmile jsme definovali strategii snižování, je přirozené se ptát, zda ji lze vylepšit. Pokud má výraz β-normální formu, pak strategie zjistí normální formu; ale mohla by existovat kratší β-redukční sekvence, která dosáhne stejné normální formy (nebo termínu, který je a-konvertibilní na tuto normální formu)? To je otázka optimality. Definování optimálních strategií a ukázání, že jsou optimální, je obecně mnohem obtížnější než prosté vymezení strategie. Další diskuse viz (Barendregt, 1984, kapitola 10).

V zájmu konkrétnosti jsme diskutovali pouze o β-redukčních strategiích. Ve výše uvedených definicích je však pojem redukce β jedinou možností. Pro jakoukoli představu o redukci máme přidruženou teorii strategií redukce R a pro R můžeme přehrát problémy normalizace, optimality atd..

5. λ-teorie

Dříve jsme diskutovali o tom, jak je λ-počet inherentní teorií funkcí. Pokud v intenzivním duchu chápeme λ-termíny jako popisy, jak bychom měli zacházet s rovností λ-termů? K dispozici jsou různé přístupy. V této části pojďme pojmout vztah rovnosti = jako primitivní, nedefinovaný vztah, který drží dva termíny λ, a pokusme se axiomatizovat vlastnosti, které by rovnost měla mít. Úkolem je identifikovat axiomy identity a formulovat vhodná pravidla odvozování týkající se rovnosti λ-podmínek.

Některé zjevné vlastnosti rovnosti, které nemají nic společného s λ-kalkulem, jsou následující:

Reflexivita, symetrie a transitivita rovnosti λ-termů jako pravidel inference

Reflexivita		Symetrie		Transitivita
		X = Y		X = YY = Z
X = X		Y = X		X = Z

Jak je standardem v teorii důkazů, způsob, jak číst tato pravidla odvozování, je, že nad horizontálním pravidlem - jsou prostorem pravidla (což jsou rovnice) a rovnice pod horizontálním pravidlem je závěr pravidla odvozování. V případě pravidla reflexivity se nad horizontální pravidlo nic nepíše. Takový případ chápeme tak, že říkáme, že pro všechny podmínky X můžeme odvodit rovnici X = X z žádných prostor.

5.1 Základní teorie λ

Tři pravidla odvozování uvedená v předchozí části upravující rovnost nemají nic společného s λ-kalkulem. Následující seznam uvádí pravidla odvození, která se týkají nedefinovaného pojmu rovnosti a dvou operací budování termínů λ-kalkulu, aplikace a abstrakce.

Pravidla usuzování týkající se rovnosti při používání a abstrakce

M = N		M = N		M = N
AM = AN		MA = NA		λ x [M] = λ x [N]

Tato pravidla odvozování říkají, že = je kongruenční vztah k množině λ-termů: „zachovává“jak operace vytváření, tak abstrakce termínů

Poslední pravidlo inference, β-konverze, je nejdůležitější:

p
	(λ x [M]) A = M [x: = A]

Stejně jako dříve u pravidla reflexivity nemá pravidlo β žádné předpoklady: pro libovolnou proměnnou x a jakékoli výrazy M a A lze odvodit rovnici (λ x [M]) A = M [x: = A] v kterémkoli bodě formální derivace v teorii λ.

5.2 Rozšíření základní teorie λ

K dispozici je řada rozšíření λ. Uvažujme například pravidlo (η), které vyjadřuje princip η-redukce jako pravidla odvozování:

(η)
	X x [M x] = M

Pravidlo η nám říká, že určitý druh abstrakce je otioza: je bezpečné identifikovat M pomocí funkce, která při argumentu x použije M na x. Prostřednictvím tohoto pravidla můžeme také vidět, že všechny pojmy jsou účinně funkční. Člověk může intuitivně zdůvodnit toto pravidlo pomocí principu β-redukce.

(Ext)	M x = N x	za předpokladu, x ∉ FV (M) ∪ FV (N)
	M = N

Jeden může vidět pravidlo Ext jako jakýsi druh zobecňovacího principu. Pokud jsme odvodili, že M x = N x, ale x čísla v M ani N, pak jsme efektivně ukázali, že M a N jsou stejné. Porovnejte tento princip s principem univerzální zobecnění v logice prvního řádu: pokud jsme odvodili φ (x) z množiny Γ hypotéz, ve kterých x není volný, pak můžeme dojít k závěru, že Γ odvozuje ∀ x φ.

Další produktivní princip v λ-kalkulu nám umožňuje identifikovat pojmy, které „jednají“stejně:

(ω)	Pro všechny pojmy x, M x = N x
	M = N

Pravidlo ω má nekonečně mnoho hypotéz: za předpokladu, že M x = N x, bez ohledu na to, co x může být, můžeme usoudit, že M = N. Ω pravidlo je analogem v lambda-kalkulu právního závěru pod stejným názvem ve formální teorie čísel, podle které lze uzavřít, univerzální vzorec ∀ x φ za předpokladu, jeden má důkazy pro cp (x: = 0), φ (x: = 1),…. Všimněte si, že na rozdíl od pravidla Ext nenastane podmínka, že x se nevyskytuje volně v M nebo N.

6. Konzistence počtu λ

Je λ-počet konzistentní? Otázka možná nebude dobře položená. A-počet není logikou pro uvažování o propozicích; neexistuje zjevná představa o rozporu (⊥) ani o metodě vytváření absurdních tvrzení (např. p ∧ ¬ p). Tudíž „nekonzistence“λ-kalkulu nemůže znamenat, že ⊥, nebo nějaký vzorec rovný ⊥, lze odvodit. K dispozici je však vhodný pojem „konzistentní“. Intuitivně je logika nekonzistentní, pokud nám to umožňuje odvodit příliš mnoho. Teorie λ je teorie rovnic. Můžeme tedy vzít v úvahu nekonzistenci λ, což znamená: všechny rovnice jsou odvozitelné. Taková vlastnost, pokud by platila pro λ, by jasně ukázala, že λ je málo užitečná jako formální teorie.

Rané formulace myšlenky A-počtu od A. Church byly skutečně nekonzistentní; viz (Barendregt, 1985, dodatek 2) nebo (Rosser, 1985) pro diskusi. Abychom si vzali konkrétní problém: jak víme, že rovnice K = I není věta o λ ? Oba výrazy jsou zjevně intuitivně odlišné. K je funkcí dvou argumentů, zatímco já je funkcí jednoho argumentu. Pokud bychom dokázali, že K = I, pak bychom mohli ukázat, že KK = IK, odkud je KK = K věta o λ, spolu s mnoha dalšími rovnicemi, které nás považují za intuitivně nepřijatelné. Když však zkoumáme formální teorii, jako je λ, intuitivní nepřijatelnost v žádném případě neznamená nedotknutelnost. Chybí hlubší pochopení β-redukce.

První výsledek, který dal takové porozumění, se nazývá Church-Rosserova věta:

Věta (Church-Rosser) Pokud P _{β β} Q a P ⊳ _β R, pak existuje pojem S tak, že jak Q ⊳ _β S, tak R ⊳ _β S.

(Důkaz této věty je docela netriviální a je mimo rozsah tohoto záznamu.) Výsledkem je hluboký fakt o β-redukci. Říká se, že bez ohledu na to, jak se odchylujeme od P pomocí β-redukcí, můžeme se vždy znovu sblížit na běžný termín.

Církev-Rosserova věta nám mimo jiné dává, že obyčejný λ-počet - tj. Teorie λ rovnic mezi λ-termy - je konzistentní v tom smyslu, že ne všechny rovnice lze odvodit.

Pro ilustraci můžeme použít Church-Rosserovu větu k vyřešení dřívějšího problému, který ukazuje, že dva pojmy K a I nejsou identifikovány λ. Oba termíny jsou v B-normální formě, takže z nich neexistují žádné p-redukční sekvence. Jestliže K = I byly teorém Á, pak by termín M, ze které je β-redukce cesta jak I a K. Církev-Rosserova věta pak naznačuje, že obě cesty odlišné od M mohou být sloučeny. To je však nemožné, protože K a I jsou odlišné β-normální formy.

Církev-Rosserova věta znamená existenci β-redukčních sekvencí začínajících od K a od I, které končí běžným termínem. Ale nejsou tam žádné sekvence β-redukční vůbec, které začíná od I, protože je v beta-normální formě, a podobně pro K.

Věta λ je konzistentní v tom smyslu, že ne každá rovnice je věta.

K prokázání věty stačí vytvořit jednu nedocházející rovnici. Už jsme prošli příkladem: použili jsme Church-Rosserovu větu, abychom ukázali, že rovnice K = I není věta o λ. O těchto dvou termínech samozřejmě není nic zvláštního. K dispozici je významná zobecnění tohoto výsledku: pokud jsou M a N v p-normální formě, ale M je odlišné od N, potom rovnice M = N není věta o λ. (Tato jednoduchá podmínka nedotknutelnosti obecně neplatí, pokud k λ přidáme další odvozovací pravidla.)

Teorie λη a λω jsou rovněž konzistentní. Jeden může dokázat tyto výsledky konzistence v souladu s důkazem konzistence pro λ rozšířením Church-Rosserovy věty na širší smysly odvozitelnosti těchto teorií.

7. Sémantika λ-počtu

Přestože je λ-kalkul „o“výpočtu s funkcemi nahrazováním hodnot argumenty, tento jednoduchý úhel pohledu nemůže podporovat sémantiku (nespecifikovaného) λ-kalkulu, pokud „funkcí“rozumíme, jak je standardem v teorii množin, vztah R takový, že pro každý pár (x, y) a (x, z) v R se stejnou první složkou x máme y = z. Pro množiny X a Y nechť X ^Y označuje množinu funkcí, jejichž doménou je Y, as hodnotami v X. Intuitivně, pokud X je doménou interpretace λ-kalkulu, pak by X mělo být v jistém smyslu izomorfní k X ^Xprotože doména by měla být uzavřena pod abstrakcí (stejně jako aplikace). Brát doslovně, i když to izomorfismus je nemožné, protože mohutnost X je vždy striktně menší než mohutnost X ^X.

Pokud se člověk zajímá pouze o existenci nějakého modelu λ-kalkulu, jehož doména nemusí nutně sestávat z funkcí, lze je najít pomocí různých známých „syntaktických“konstrukcí zahrnujících teorii λ, na rozdíl od dobře - známé konstrukce Henkin. Tyto tzv. Termínové modely jsou však neuspokojivým řešením otázky, zda existují „matematické“modely λ-kalkulu.

Argument kardinality ukazuje, že máme-li mít sémantiku pro λ-počet, interpretace λ-termínů nemůže být jednoduše funkcemi v set-teoretickém smyslu tohoto termínu. Existují však interpretace λ-kalkulu. První model, D _∞, byl nalezen D. Scottem; jiné modely byly nalezeny později. Tyto modely vyřešit problém mohutnost omezením domény X výkladu, tak, že v nich, X je ve vhodném smyslu izomorfní k ‚prostoru funkcí‘ X ^X.

Jednou z výhod různých interpretací je to, že vidíme různé aspekty rovnosti: každý z těchto modelů má odlišný pohled na to, co se identifikují λ-termíny. Definice D _∞ a jiné interpretace, ověření, že jsou skutečně modely λ-kalkulu, a charakterizace λ-teorií těchto modelů jsou mimo rozsah této položky; viz (Barendregt, 1985, kapitola 18) pro podrobnosti.

8. Rozšíření a variace

8.1 Kombinovaná logika

Sesterský formalismus A-počtu, vyvinutý o něco dříve, se zabývá kombinací bez proměnných. Kombinovaná logika je ve skutečnosti ještě jednodušší než počet A, protože postrádá představu variabilní vazby.

Jazyk kombinační logiky je vytvořen z kombinátorů a proměnných. Existuje určitá flexibilita ve které přesně kombinátory jsou vybrány jako základní, ale některé z nich jsou standardní I, K, S, B a C. (Jména nejsou libovolná.)

Stejně jako u počtu A, iu kombinované logiky se zajímá o redukovatelnost a prokazatelnost. Hlavní redukční vztahy jsou:

Kombinátor	Redukční axiom
Já	I x = x
K	K xy = x
S	S xyz = xz (yz)
B	B xyz = x (yz)
C	C xyz = xzy

Existuje pasáž z λ-počtu do kombinatorické logiky prostřednictvím překladu. Ukazuje se, že ačkoli kombinační logika postrádá představu abstrakce, lze takový pojem definovat a simulovat tak počet A v kombinatorické logice. Zde je jeden překlad; je definován rekurzivně.

Pravidlo	Výraz	Překlad	Stav
1	X	X	(bezpodmínečně)
2	MN	M * N *	(bezpodmínečně)
3	λ x [M]	K M	x se nevyskytuje volně v M
4	λ x [x]	Já	(bezpodmínečně)
5	λ x [M x]	M	x se nevyskytuje volně v M
6	λ x [MN]	B M (λ x [N)] *	x se nevyskytuje volně v M
7	λ x [MN]	C (X x [M]) * N	x nenastává volně v N
8	λ x [MN]	S M * N *	x se vyskytuje volně v M i N

Tento překlad funguje naruby, nikoli zvenčí. Pro ilustraci:

1. Překlad termínu AY [y], zástupce funkce identity, je mapován tímto překladem do kombinátoru I identity (kvůli pravidlu 4), jak se očekávalo.

2. Λ-termín λ x [λ y [x], který jsme nazvali ' K ', je mapován tímto překladem na:

   	λ x [λ y [x]
   ≡	⟨Pravidlo 1⟩
   	λ x [ K x]
   ≡	⟨Pravidlo 3⟩
   	K

3. Λ-termín λ x [λ y [yx], který přepíná své dva argumenty, je tímto překladem mapován na:

   	λ x [λ y [yx]
   ≡	⟨Pravidlo 8⟩
   	λ x [ C (λ y [y]) * x]
   ≡	⟨Λ y [y] ≡ já, podle pravidla 4⟩
   	λ x [ CI x]
   ≡	⟨Pravidlo 7⟩
   	B (CI) (λ x [x]) *
   ≡	⟨(Λ x [x]) * ≡ I, podle pravidla 4⟩
   	B (CI) I

   Můžeme potvrdit, že λ-termín λ x [λ y [yx] a přeložený kombinativní logický výraz B (CI) I mají analogické aplikační chování: pro všechny λ-termy P a Q máme

   (Xx [Xy [yx]) PQ XY [y P]) QP;

   podobně pro všechny kombinatorické logické termíny P a Q máme

   B (CI) I PQ ⊳ (CI) (I P) Q ⊳ I Q (I P) ⊳ Q (I P) ⊳ QP

Můžeme dát jen krátký pohled na kombinativní logiku; více o tomto tématu najdete v poznámce o kombinované logice. Mnoho z otázek diskutovaných zde pro λ-počet má analogie v kombinatorické logice a naopak.

8.2 Přidávání typů

V mnoha kontextech uvažování a výpočtů je přirozené rozlišovat mezi různými druhy objektů. Způsob, jakým se toto rozlišení zavádí, je vyžadováním toho, aby určité vzorce, funkce nebo vztahy akceptovaly argumenty nebo umožňovaly nahrazení pouze některých druhů objektů, nikoli jiných. Můžeme například požadovat, aby sčítání + čísla jako argumenty. Účinkem tohoto omezení je zakázat, řekněme, přidání 5 a identifikační funkci X x. x. (4). Regulace objektů do typů je také myšlenkou přechodu od (netříděné nebo jednořádkové) logiky prvního řádu k mnoha seřazené logice prvního řádu. (Viz (Enderton, 2001) a (Manzano, 2005), kde je více o mnohočetné logice prvního řádu.) Jak je uvedeno, počet A nepodporuje tento druh diskriminace; jakýkoli výraz lze použít na jakýkoli jiný termín.

Je snadné rozšířit nerozptýlený λ-kalkul tak, aby rozlišoval mezi různými druhy objektů. Tato položka se omezuje na λ-počet bez typu. Podrobné informace o rozšíření počtu λ-kalkulů, které získáme při přidávání typů, najdete v položkách teorie typů a církevní teorie typů.

9. Aplikace

9.1 Logika à la λ

Zde jsou dva smysly, ve kterých je λ-počet spojen s logikou.

9.1.1 Pojmy jako logické konstanty

V tabulce kombinátorů výše jsme definovali kombinátory T a F a uvedli, že slouží jako reprezentace v λ-kalkulu pravdivých hodnot pravdivých a nepravdivých. Jak tyto pojmy fungují jako hodnoty pravdy?

Ukazuje se, že když člověk zachází s λ-kalkulem jako s určitým druhem programovacího jazyka, je možné psát podmíněné příkazy „Pokud P pak A jinde B“jednoduše jako PAB, kde samozřejmě P, A a B jsou chápány jako λ-termy. Pokud P ⊳ T, to znamená, že P je „pravda“, pak ano

if- P-Then- A -else- B: = PAB ⊳ T AB ⊳ A,

(vzpomeňte, že podle definice, T ≡ K) a pokud P ⊳ F, to znamená, že P je „nepravdivé“, pak

if- P-Then- A -else- B: = PAB ⊳ F AB ⊳ B,

(vzpomeňme na to, z definice, F ≡ KI), což je přesně to, co očekáváme od pojmu if-then-else. Pokud se P nezmenšuje ani na T ani F, potom obecně nemůžeme říci, co-li-P-potom-A -else-B.

Kódování, které jsme právě načrtli o některých známých hodnotách pravdy a logických spojivech klasické logiky pravdivých tabulek, neprokazuje, že λ-počet a klasická logika spolu úzce souvisejí. Kódování ukazuje o něco více než vložitelnost pravidel výpočtu klasické logiky pravdivých tabulek v λ-kalkulu. Logika jiná než klasická logika pravdivých tabulek může být rovněž reprezentována v λ-kalkulu, má-li člověk dostatečné kompatibilní ingredience pro danou logiku (např. Pokud je vztah logických důsledků kompatibilní, nebo pokud je možné odvodit vztah, atd.)). Další informace o práci s výpočtem λ-kalkulu naleznete v části 9.2 níže. Vnitřní vztah mezi logikou a λ-kalkulem je diskutován v následující části.

9.1.2 Typizovaný λ-počet a Curry-Howard-de Bruijn korespondence

Korelace, která má být zde popsána mezi logikou a λ-kalkulem, je vidět pomocí přístroje známého jako typy. Tato část nastiňuje začátky vývoje předmětu známého jako teorie typů. Zajímáme se o vývoj teorií typů pouze do té míry, aby zviditelnili takzvanou Curry-Howard-de Bruijnovu korespondenci. Podrobnější zpracování lze nalézt v položce teorie typů; viz také (Hindley 1997).

Teorie typů obohacuje untyped λ-počet tím, že vyžaduje, aby byly dané typy dány typům. V untyped λ-počtu je aplikace MN právním termínem bez ohledu na to, co M a N jsou. Taková svoboda dovoluje tvořit takové termíny jako podezřelé xx a odtud termíny jako paradoxní Combinator Y. Jeden by mohl chtít vyloučit pojmy jako xx z toho důvodu, že x slouží jak jako funkce (na levé straně aplikace), tak jako argument (na pravé straně aplikace). Teorie typů nám poskytuje zdroje pro zpřesnění tohoto intuitivního argumentu.

Přiřazení typů k pojmům Teorie jazyka typu začíná (nekonečnou) množinou typových proměnných (která je považována za disjunktní od množiny proměnných λ-počtu a od samotného symbolu 'λ'). Sada typů se skládá z proměnných typu a operace σ → τ. Proměnné v teorii typů nyní přicházejí s anotací typu (na rozdíl od neoznačených termínových proměnných untyped λ-počtu). Zadané proměnné jsou vykresleny 'x: σ' intuitivní čtení je 'proměnná x má typ σ'. Intuitivní čtení rozsudku 't: σ → τ' je, že termín t je funkce, která transformuje argumenty typu σ do argumentů typu τ. Přiřazení typů k termínovým proměnným má člověk pravidla psaní:

(M: σ → τ) (N: σ): τ

a

(λ x: σ [M: τ]): σ → τ

Výše uvedená dvě pravidla definují přiřazení typů aplikacím a abstrakčním podmínkám. Sada pojmů teorie typů je množina pojmů vytvořených podle těchto pravidel formace.

Výše uvedená definice množiny pojmů teorie typů je dostatečná k vyloučení pojmů jako xx. 'Xx' samozřejmě není typizovaný termín z jednoduchého důvodu, že k němu nebyly přiřazeny žádné typy. To znamená, že neexistuje žádný typ σ, který by mohl být přiřazen k x tak, že by „xx“mohlo být legálně anotováno, aby se vytvořil typovaný výraz. Nemůžeme přiřadit proměnné typu xa, protože pak by typ levé strany x nebyl funkční typ (tj. Typ tvaru 'σ → τ'). Navíc nemůžeme přiřadit xa typu funkce σ → τ, protože pak σ by se rovnalo σ → τ, což je nemožné.

Jako hlavní příklad zvažte typy přiřazené kombinátorům I, K a S:

Kombinátor	Typ [5]
Já	a → a
K	a → (b → a)
S	a → (b → c) → ((a → b) → (a → c))

(Viz Hindley (1997) Tabulka hlavních typů pro podrobnější seznam.) Pokud čteme '→' jako implikační a typové proměnné jako výrokové proměnné, pak v pravém sloupci tabulky rozpoznáme tři známé tautologie. Použitý jazyk je chudý: existují pouze výrokové proměnné a implikace; neexistují žádné další spojky.

Tabulka navrhuje zajímavou korespondenci mezi λ-kalkulem. Je možné, že typy přiřazené vzorcům, pokud jsou chápány jako logické vzorce, jsou platné? Ano, ačkoli „platnost“je třeba chápat jako klasickou platnost:

Věta Pokud je τ typ nějakého λ-termu, pak τ je intuitionisticky platný.

Obrácení této věty platí také:

Věta Pokud je φ intuicionálně platný logický vzorec, jehož jedinou konektivitou je implikace (→), pak φ je typ nějakého λ-termínu.

Korešponenci lze vidět, když člověk identifikuje intuicionální platnost s derivovatelností v určitém přirozeném dedukčním formalismu. Důkaz těchto dvou vět je uveden (Hindley, 1997, kapitola 6).

Korespondence vyjádřená předchozími dvěma větami mezi intuicionální platností a typizovatelností je známá jako Curry-Howard-de Bruijn korespondence, po třech logikech, kteří si ji všimli samostatně. Jak je uvedeno, korespondence je pouze mezi výrokovou intuicionistickou logikou a je omezena na fragment obsahující pouze implikační spojovací →. Lze korespondenci rozšířit i na další spojovací členy a také na kvantifikátory, ale nejostřejší korespondence je na úrovni fragmentu, který je pouze implikační. Podrobnosti viz (Howard, 1980).

9.2 Výpočet

Jeden může reprezentovat přirozená čísla jednoduchým způsobem takto:

Definice (uspořádaná n-tice, přirozená čísla) Uspořádaná n-tice ⟨a ₀, i … _n ⟩ z lambda-požadavků je definován jako λ x [x a ₀ i … _n]. Jeden pak definuje lambda-term ⌜ n ⌝ odpovídající přirozené číslo n, jako jsou: ⌜0⌝ = I, a pro každé k, k + ⌜ 1⌝ = ⟨ F, ⌜ k ⌝⟩.

1. Λ-termín odpovídající číslu 1 v této reprezentaci je:

   	⌜1⌝
   ≡
   	⟨ F, ⌜0⌝⟩
   ≡
   	⟨ F, I ⟩
   ≡
   	λ x [x FI]

2. Λ-termín odpovídající číslu 2 v této reprezentaci je:

   	⌜2⌝
   ≡
   	⟨ F, ⌜1⌝⟩
   ≡
   	λ x [x F λ x [x FI]

3. Podobně ⌜3⌝ je λ x [x F λ x [x F λ x [x FI].

K dispozici jsou různé reprezentace přirozených čísel; tato reprezentace je pouze jedna. ^[6]

Pomocí přísad poskytnutých λ-kalkulu lze reprezentovat všechny rekurzivní funkce. To ukazuje, že model je přesně tak výrazný jako jiné modely výpočetní techniky, jako jsou Turingovy stroje a registrační stroje. Přednost jde o Turingovu definici jeho stroje, ale církevní návrh počtu λ-kalkulů byl vyvinut téměř přesně ve stejnou dobu.

Věta Pro každou rekurzivní funkci f arity n existuje λ-termín f ^* takový, že

ve všech přirozených čísel a ₁, i … _n: f (a ₁, i … _n) = y právě tehdy, když lambda ⊢ f ^* ⟨a ₁, i … _n ⟩ = y

Důkaz viz příloha.

Protože třída rekurzivních funkcí je adekvátní reprezentací třídy všech vypočítatelných (číselně teoretických) funkcí, díky výše uvedené práci zjistíme, že všechny vypočítatelné (číselně teoretické) funkce lze věrně reprezentovat v λ-kalkulu.

9.3 Vztahy

Motivace λ-kalkulu daná na začátku záznamu byla založena na čtení λ-výrazů jako popisu funkcí. Rozuměli jsme tedy, že 'λ x [M]' je (nebo) funkce, která vzhledem k x dává M (což obecně, i když ne nutně, zahrnuje x). Není však nutné číst λ-termíny jako funkce. Jeden by mohl chápat λ-termíny jako označující vztahy, a číst abstrakční termín 'λ x [M]' jako unární vztah R, který drží argument x jen v případě M. Při relačním čtení můžeme termín aplikace MN chápat jako formu predikace. Dá se tyto pojmy pochopit pomocí principu β-konverze:

(λ x [M]) a = M [x: = A],

který říká, že abstrakční vztah λ x [M], predikovaný na A, je vztah získaný zapojením A pro všechny volné výskyty x uvnitř M.

Jako konkrétní příklad tohoto druhu přístupu k λ-kalkulu zvažte rozšíření logiky prvního řádu, kde je možné pomocí nových λ-výrazů vytvořit nové atomové vzorce následujícím způsobem:

Syntaxe: Pro jakýkoli vzorec φ a jakoukoli konečnou posloupnost x ₁,…, x _n proměnných je výraz „λ x ₁ … x _n [φ]“predikátním symbolem arity n. Rozšířit pojem volné a vázané proměnné (pomocí funkcí FV a BV) tak, aby

FV (λ x ₁ … x _n [φ]) = FV (φ) - {x ₁, … x _n }

a

BV (λ x ₁ … x _n [φ]) = BV (φ) ∪ {x ₁,… x _n }

Odpočet Předpokládejme jako axiomy univerzální uzavření všech ekvivalencí

λ x ₁ … x _n [φ] (t ₁,… t _n) ↔ φ [x ₁,… x _n: = t ₁,… t _n]

kde φ [x ₁,… x _n: = t ₁,… t _n] označuje současné nahrazení výrazů t _k proměnnými x _k (1 ≤ k ≤ n).

Sémantika Pro strukturu A prvního řádu a přiřazení prvků A proměnným definujte

A ⊨ λ x ₁ … x _n [φ] (t ₁,… t _n) [s] iff A ⊨ φ [x ₁,… x _n: = t ₁,… t _n] [s]

Podle tohoto přístupu lze použít λ k léčbě v podstatě jakéhokoli vzorce, dokonce i složitého, jako by byly atomové. V deduktivní a sémantické části vidíme princip β-redukce. To, že tento přístup dodržuje relační čtení výrazů λ, lze jasně vidět v sémantice: podle standardní sémantiky Tarskiho stylu pro logiku prvního řádu znamená interpretace vzorce (možná s volnými proměnnými) množinu n-tic prvky struktury, protože proměníme přiřazení proměnných, které proměnným přiřazuje prvky struktury.

Tento funkční přístup lze „internalizovat“. Toto je děláno v případě různých majetkových teorií, formálních teorií pro uvažování o vlastnostech jako metafyzických objektů (Bealer 1982, Zalta 1983, Menzel 1986 a Turner 1987). Tento druh teorie se používá v určitých metafyzických výzkumech, kde vlastnosti jsou metafyzické entity, které mají být zkoumány. V těchto teoriích jsou metafyzické vztahy předmětem zájmu; stejně jako přidáváme symboly pro budování čísel + a × do formálních teorií aritmetiky pro vytváření čísel, λ se v teorii vlastností používá k budování vztahů. Tento přístup je v rozporu s výše uvedeným přístupem. Tam, λ byl přidán do gramatiky logiky prvního řádu tím, že se stal receptem na vytváření atomových vzorců; byl to nový operátor pro vytváření receptur, jako je ∨ nebo → nebo jiná spojovací zařízení. V případě teorií vlastností hraje λ roli spíše jako + a × ve formálních teoriích aritmetiky: používá se ke konstrukci vztahů (které se v tomto nastavení mají chápat jako druh metafyzického objektu). Na rozdíl od + a × však λ váže proměnné.

Pro ilustraci toho, jak se v tomto nastavení používá λ, se podívejme na gramatiku typické aplikace (McMichael a Zalta, 1980). Jeden má obvykle predikčního operátora (nebo přesněji skupinu predikčních operátorů) p _k (k ≥ 0). V jazyce, ve kterém máme pojmy mary a john a binární vztah miluje, můžeme formálně vyjádřit:

• John miluje Mary: miluje (john, mary)
• Vlastnost, kterou John miluje Mary: λ [miluje (john, mary)] (všimněte si, že λ neváže žádné proměnné; můžeme to nazvat „vakuózní vazbou“. Takové vlastnosti lze chápat jako výroky.)
• Vlastnost objektu x, který ji John miluje: λ x [miluje (john, x)].
• Vlastnost, kterou Mary miluje něco: λ [∃ x (miluje (x, mary))] (další příklad vakuové vazby, viz., Výrok)
• Predikce vlastnosti x, kterou John miluje x vůči Mary: p ₁ (λ x [miluje (john, x)], mary).
• (0-ary) predikce vlastnosti, kterou John miluje Mary: p ₀ (λ x [miluje (john, mary)])).
• Vlastnost objektů x a y, které x miluje y: λ xy [miluje (x, y)].
• Vlastnost objektů x, které x miluje sama sebe: λ x [miluje (x, x)].
• Predikce vlastnosti objektů x a y, které x miluje y, s Johnem a Mary (v tomto pořadí): p ₂ (λ xy [miluje (x, y)], john, mary).

S těmito λ-termíny uvažujeme pomocí principu β-konverze, jako například:

p _n (λ x ₁, … X _n [A], t ₁, …, t _n) ↔ A [x ₁, … x _n: = t ₁, … t _n]

Formálně je operátor predikce p _k (k +1) -ary predikátový symbol. První argument je zamýšlen jako argument λ-term k a zbytek argumentů je zamýšlen jako argument argumentu λ-term. Princip β výše říká, že predikace n -arych λ-termů L na n platí přesně tehdy, když tělo L drží tyto termíny.

Ukazuje se, že v těchto teoriích můžeme nebo nemusíme být schopni plně se zavázat k principu β-konverze. Opravdu, v některých teoriích vlastnictví, plný princip β-konverze vede k paradoxu, protože když je zaveden plný princip β-konverze, lze přehrát argument Russellova stylu. V takovém nastavení je omezeno vytváření λ-vzorců tím, že se požaduje, aby tělo λ-termínu neobsahovalo další λ-termy nebo kvantifikátory. Pro další diskusi viz (Orilia, 2000).

Bibliografie

• Baader, Franz a Tobias Nipkow, 1999, Term Rewriting and All That, Cambridge: Cambridge University Press.
• Barendregt, HP, 1985, The Lambda Calculus: jeho syntax a sémantika (Studie v logice a základy matematiky 103), 2. vydání, Amsterdam: Severní Holandsko.
• Barendregt, HP, 1993, „Lambda kalkulu s typy“, v S. Abramsky, D. Gabbay, T. Maibaum a H. Barendregt (eds.), Handbook of Logic in Computer Science, Svazek 2, New York: Oxford University Stiskněte na str. 117–309.
• Bealer, G., 1982, Quality and Concept, Oxford: Clarendon Press.
• van Benthem, Johan, 1998, Manuál intenzivní logiky, Stanford: CSLI Publications.
• Church, A., 1932, „Soubor postulátů pro založení logiky“, Annals of Mathematics (2. řada), 33 (2): 346–366.
• Cutland, NJ, 1980, Computability, Cambridge: Cambridge University Press.
• Doets, Kees a Jan van Eijk, 2004, Haskellova cesta k logice, matematice a programování, Londýn: College Publications.
• Enderton, Herbert B., 2001, Matematický úvod do logiky, 2. vydání, San Diego: Harcourt / Academic Press.
• Frege, Gottlob, 1893, Grundgesetze der Arithmetik, Jena: Verlag Hermann Pohle, Band I. Částečný překlad jako základní aritmetické zákony, M. Furth (trans.), Berkeley: University of California Press, 1964.
• Kleene, Stephen C., 1981, „Počátky teorie rekurzivních funkcí“, Annals of the History of Computing, 3 (1): 52–67.
• Heim, Irene a Angelika Kratzer, 1998, sémantika v generativní gramatice, Malden, MA: Blackwell.
• Hindley, J. Roger, 1997, Základní teorie jednoduchých typů (Cambridge Tracts v teoretické informatice 42), New York: Cambridge University Press.
• Hindley, J. Roger a Jonathan P. Seldin, 2008, Lambda-Calculus and Combinators: Úvod, 2. vydání, Cambridge: Cambridge University Press.
• Howard, W., 1980, „Pojem konstrukce podle typu“, J. Hindley a J. Seldin (eds.), K HB Curry: Eseje o kombinované logice, Lambda-Calculus a formalismus, Londýn: Academic Press, str. 479–490.
• Manzano, Maria, 2005, Rozšíření logiky prvního řádu (Cambridge Tracts v teoretické informatice 19), Cambridge: Cambridge University Press.
• McCarthy, John, 1960, „Rekurzivní funkce symbolických výrazů a jejich výpočet pomocí počítače (část I)“, Komunikace ACM, 3 (4): 184–195.
• McMichael, Alan a Edward N. Zalta, 1980, „Alternativní teorie neexistujících objektů“, Journal of Philosophical Logic, 9: 297–313.
• Menzel, Christopher, 1986, „Kompletní logika vlastností, vztahů a propozic druhého řádu bez typu“, technická zpráva č. CSLI-86-40, Stanford: CSLI Publications.
• Nederpelt, R., s H. Geuvers a R. de Vriejer (eds.), 1994, Selected Papers on Automath (Study in Logic and Foundations of Mathematics 133), Amsterdam: North-Holland.
• Orilia, Francesco, 2000, 'Teorie vlastností a revize teorie definic', Journal of Symbolic Logic, 65 (1): 212–246.
• Partee, Barbara H., s Alice ter Meulen a Robert E. Wall, 1990, Matematical Methods in Linguistics, Berlin: Springer.
• Revesz, GE, 1988, Lambda-Calculus, kombinátory a funkční programování, Cambridge: Cambridge University Press; dotisk 2008.
• Rosser, J. Barkley, 1984, „Highlights of the History of the Lambda-Calculus“, Annals of the History of Computing, 6 (4): 337–349.
• Schönfinkel, M., 1924. „O stavebních blocích matematické logiky“, v J. van Heijenoort (ed.), Od Frege k Gödel: Zdrojová kniha v matematické logice, Cambridge, MA: Harvard University Press, 1967, pp 355–366.
• Troelstra, AS a H. Schwichtenberg, 2000, Základní teorie důkazů (Cambridge Tracts v teoretické informatice 43), 2. vydání, Cambridge: Cambridge University Press.
• Turing, AM, 1937, „Vyčíslitelnost a λ-definovatelnost“, Journal of Symbolic Logic, 2 (4): 153–163.
• Turner, R., 1987, „Teorie vlastností“, Journal of Symbolic Logic, 52 (2): 455–472.
• Zalta, E., 1983, Abstraktní objekty: Úvod do axiomatické metafyziky, Dordrecht: D. Reidel.

Akademické nástroje

	Jak citovat tento záznam.
	Náhled na PDF verzi tohoto příspěvku v Friends of the SEP Society.
	Vyhledejte toto vstupní téma v projektu Indiana Philosophy Ontology Project (InPhO).
	Vylepšená bibliografie tohoto záznamu ve PhilPapers s odkazy na jeho databázi.

Další internetové zdroje

• Lambda kalkulačka, nástroj pro práci s λ-termy s pohledem na jejich použití ve formální sémantice přirozeného jazyka.
• Lambda Evaluator, pro vizualizaci redukcí. Standardní kombinátory a církevní číslice jsou předdefinovány.
• Pracovní stůl pro redukci počtu Lambda pro vizualizaci redukčních strategií
• λ-Calculus: Then and Now, užitečný leták o milnících, přispěvatelích a bibliografii λ-počtu, prezentovaných na několika konferencích Turing Centennial.