Lambda-mu kalkul - Lambda-mu calculus
v matematická logika a počítačová věda, lambda-mu kalkul je rozšířením lambda kalkul představil M. Parigot.[1] Představuje dva nové operátory: operátor μ (který je zcela odlišný od μ operátor nalezen v teorie vypočítatelnosti a od operátora μ z modální μ-kalkul ) a operátor závorky. Důkaz teoreticky, poskytuje dobře vychovanou formulaci klasický přírodní dedukce.
Jedním z hlavních cílů tohoto rozšířeného počtu je umět popsat výrazy odpovídající větám v klasická logika. Podle Curry – Howardův izomorfismus, lambda kalkul sám o sobě může vyjádřit věty v intuicionistická logika a několik klasických logických vět nelze vůbec napsat. S těmito novými operátory je však možné psát výrazy, které mají typ, například Peirceův zákon.
Sémanticky těmto operátorům odpovídá pokračování, nalezený v některých funkční programovací jazyky.
Formální definice
Můžeme rozšířit definici výrazu lambda, abychom získali jeden v kontextu lambda-mu kalkulu. Tři hlavní výrazy nalezené v lambda kalkulu jsou následující:
- PROTI, a proměnná, kde PROTI je jakýkoli identifikátor.
- λV.E, an abstrakce, kde PROTI je jakýkoli identifikátor a E je jakýkoli výraz lambda.
- (E E '), an aplikace, kde E a E'; jsou jakékoli lambda výrazy.
Podrobnosti viz odpovídající článek.
Kromě tradičních proměnných λ obsahuje počet lambda-mu početnou sadu proměnných μ. Tyto μ-proměnné lze použít k název nebo zmrazit libovolné dílčí termíny, což nám umožňuje později abstrahovat od těchto jmen. Sada termínů obsahuje bezejmený (všechny tradiční výrazy lambda jsou tohoto druhu) a pojmenovaný podmínky. Výrazy, které jsou přidány lambda-mu kalkulem, mají tvar:
- [α] t je pojmenovaný termín, kde α je μ-proměnná a t je nejmenovaný termín.
- (μ α. E) je nejmenovaný termín, kde α je μ-proměnná a E je pojmenovaný termín.
Snížení
Základní pravidla redukce použitá v kalkulu lambda-mu jsou následující:
- logická redukce
- strukturální redukce
- přejmenování
- ekvivalent η-redukce
- , protože α se volně nevyskytuje v u
Tato pravidla způsobí, že počet bude soutok. Mohla by být přidána další pravidla snižování, která nám poskytnou silnější představu o normální formě, i když by to bylo na úkor soutoku.
Viz také
- Klasický systémy čistého typu pro typizované zobecnění lambda kalkulů s kontrolou
Reference
- ^ Michel Parigot (1992). „Λμ-Calculus: Algoritmická interpretace klasické přirozené dedukce“. λμ-Calculus: Algoritmická interpretace klasické přirozené dedukce. Přednášky z informatiky. 624. 190–201. doi:10.1007 / BFb0013061. ISBN 3-540-55727-X.
externí odkazy
- Lambda-mu relevantní diskuse o Lambda the Ultimate.