Indukční rekurze - Induction-recursion

v intuicionistická teorie typů (ITT), disciplína uvnitř matematická logika, indukční rekurze je funkce pro současné deklarování typu a funkce na tomto typu. Umožňuje vytváření větších typů, jako jsou vesmíry, než indukční typy. Vytvořené typy stále zůstávají predikativní uvnitř ITT.

An indukční definice je dána pravidly pro generování prvků typu. Potom lze definovat funkce z tohoto typu indukcí na způsobu generování prvků typu. Indukční rekurze zobecňuje tuto situaci, protože je to možné zároveň definujte typ a funkci, protože pravidla pro generování prvků typu mohou odkazovat na funkci.^[1]

Indukční rekurzi lze použít k definování velkých typů včetně různých konstrukcí vesmíru. Podstatně zvyšuje důkazně-teoretickou sílu teorie typů. Přesto jsou stále zvažovány indukčně-rekurzivní rekurzivní definice predikativní.

Pozadí

Indukční rekurze vyplynula z vyšetřování pravidel Martina-Löfa intuicionistická teorie typů. Teorie typů má pro každý z nich řadu „tvůrců typů“ a čtyři druhy pravidel. Martin-Löf naznačil, že pravidla pro každý typ typu se řídila vzorem, který zachoval vlastnosti teorie typů (např. silná normalizace, predikativita ). Vědci začali hledat nejobecnější popis vzoru, protože to by řeklo, jaké druhy tvarovačů lze přidat (nebo nepřidat!) K rozšíření teorie typů.

Nejzajímavější byl typ „vesmír“, protože když byla pravidla napsána „à la Tarski“, současně definovaly „typ vesmíru“ a funkce, která na něm fungovala. To nakonec vedlo Dybjera k indukční rekurzi.

Dybjerovy původní práce nazvaly Indukční rekurze „schématem“ pravidel. Uvedl, jaké formovače typů lze přidat do teorie typů. Později on a Setzer napsali nový formovač typů s pravidly, která umožňovala vytváření nových definic indukční rekurze uvnitř teorie typů.^[2] Toto bylo přidáno k Half proof asistent (varianta Alf ).

Idea

Před pokrytím indukčně-rekurzivních typů je jednodušší případ induktivní typy. Konstruktory pro indukční typy mohou být samoreferenční, ale omezeným způsobem. Parametry konstruktoru musí být „pozitivní“:

neodkazuje na definovaný typ
být přesně definovaným typem, nebo
být funkce, která vrací definovaný typ.

U indukčních typů může typ parametru záviset na dřívějších parametrech, ale nemohou odkazovat na ty z definovaného typu. Induktivně-rekurzivní typy jdou dále a typy parametrů umět odkazují na dřívější parametry, které používají definovaný typ. Musí to být „napůl pozitivní“:

být funkcí v závislosti na dřívějším parametru -li tento parametr je zabalen do definované funkce.

Takže když ${ displaystyle D}$ je definovaný typ a ${ displaystyle f}$ je definovaná funkce (současně), jsou tyto deklarace parametrů kladné:

${ displaystyle a: A}$
${ displaystyle d: D}$
${ displaystyle g: A to Type}$
${ displaystyle h: A až D}$
${ displaystyle i: A až B až D}$
${ displaystyle j: g a}$ (Závisí na dřívějších parametrech, z nichž žádný není typ.) ${ displaystyle D}$ .)

To je napůl pozitivní:

${ displaystyle k: (f d) do D}$ (Závisí na parametru ${ displaystyle d}$ typu ${ displaystyle D}$ ale pouze prostřednictvím volání na ${ displaystyle f}$ .)

Tyto jsou ne pozitivní ani napůl pozitivní:

${ displaystyle k: D do A}$ ( ${ displaystyle D}$ je parametr funkce.)
${ displaystyle l: (A až D) až A}$ (Parametr přebírá funkci, která se vrací ${ displaystyle D}$ , ale vrátí se ${ displaystyle A}$ sám.)
${ displaystyle m: z d}$ (Záleží na ${ displaystyle d}$ typu ${ displaystyle D}$ , ale ne prostřednictvím funkce ${ displaystyle f}$ .)

Příklad vesmíru

Jednoduchým běžným příkladem je typ typu Universe à la Tarski. Vytvoří typ ${ displaystyle U}$ a funkce ${ displaystyle T}$ . Existuje prvek ${ displaystyle U}$ pro každý typ v teorii typů (kromě ${ displaystyle U}$ sám!). Funkce ${ displaystyle T}$ mapuje prvky ${ displaystyle U}$ na přidružený typ.

Typ ${ displaystyle U}$ má konstruktor (nebo úvodní pravidlo) pro každý typ typu v teorii typů. Ten pro závislé funkce by byl:

${ displaystyle konstruktor _ { Pi} (u: U) (u ': T (u) do U): U}$

To znamená, že to vyžaduje prvek ${ displaystyle u}$ typu ${ displaystyle U}$ který bude mapován na typ parametru a funkci ${ displaystyle u '}$ takové, že pro všechny hodnoty ${ displaystyle x: T (u)}$ , ${ displaystyle u '(x)}$ mapuje na návratový typ funkce (který je závislý na hodnotě parametru, ${ displaystyle x}$ ). (Finále ${ displaystyle: U}$ říká, že výsledkem konstruktoru je prvek typu ${ displaystyle U}$ .)

Říká to redukce (nebo výpočetní pravidlo)

${ displaystyle T (konstruktor _ { Pi} (u, u '))}$ se stává ${ displaystyle prod _ {x: T (u)} T (u '(x))}$ .

Po zmenšení funkce ${ displaystyle T}$ pracuje na menší části vstupu. Pokud to platí kdy ${ displaystyle T}$ se tedy použije na libovolného konstruktora ${ displaystyle T}$ vždy skončí. Aniž bychom zacházeli do podrobností, Induction-Recursion uvádí, jaké druhy definic (nebo pravidel) lze přidat do teorie tak, že volání funkce budou vždy ukončena.

Používání

Indukční rekurze je implementována v Agda a Idrisi.^[3]

Viz také

Indukce-indukce - další práce, která definuje typ a rodinu typů současně

Reference

^ Dybjer, Peter (červen 2000). „Obecná formulace simultánních indukčně-rekurzivních definic v teorii typů“ (PDF). Journal of Symbolic Logic. 65 (2): 525–549. CiteSeerX 10.1.1.6.4575. doi:10.2307/2586554. JSTOR 2586554.
^ Dybjer, Peter (1999). Konečná axiomatizace indukčně-rekurzivních definic. Přednášky z informatiky. 1581. str. 129–146. CiteSeerX 10.1.1.219.2442. doi:10.1007/3-540-48959-2_11. ISBN 978-3-540-65763-7.
^ Bove, Ana; Dybjer, Peter; Norell, Ulf (2009). Berghofer, Stefan; Nipkow, Tobias; Urban, Christian; Wenzel, Makarius (eds.). „Stručný přehled Agda - funkčního jazyka se závislými typy“. Věta prokazující logiku vyšších řádů. Přednášky z informatiky. Berlin, Heidelberg: Springer: 73–78. doi:10.1007/978-3-642-03359-9_6. ISBN 978-3-642-03359-9.

externí odkazy

[Dybjer-1] Dybjer, Peter (červen 2000). „Obecná formulace simultánních indukčně-rekurzivních definic v teorii typů“ (PDF). Journal of Symbolic Logic. 65 (2): 525–549. CiteSeerX 10.1.1.6.4575. doi:10.2307/2586554. JSTOR 2586554.

[DybjerSetzer-2] Dybjer, Peter (1999). Konečná axiomatizace indukčně-rekurzivních definic. Přednášky z informatiky. 1581. str. 129–146. CiteSeerX 10.1.1.219.2442. doi:10.1007/3-540-48959-2_11. ISBN 978-3-540-65763-7.

[3] Bove, Ana; Dybjer, Peter; Norell, Ulf (2009). Berghofer, Stefan; Nipkow, Tobias; Urban, Christian; Wenzel, Makarius (eds.). „Stručný přehled Agda - funkčního jazyka se závislými typy“. Věta prokazující logiku vyšších řádů. Přednášky z informatiky. Berlin, Heidelberg: Springer: 73–78. doi:10.1007/978-3-642-03359-9_6. ISBN 978-3-642-03359-9.

[1]

[2]

[3]