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ž je definovaný typ a je definovaná funkce (současně), jsou tyto deklarace parametrů kladné:

  • (Závisí na dřívějších parametrech, z nichž žádný není typ.) .)

To je napůl pozitivní:

  • (Závisí na parametru typu ale pouze prostřednictvím volání na .)

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

  • ( je parametr funkce.)
  • (Parametr přebírá funkci, která se vrací , ale vrátí se sám.)
  • (Záleží na typu , ale ne prostřednictvím funkce .)

Příklad vesmíru

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

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

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

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

se stává .

Po zmenšení funkce pracuje na menší části vstupu. Pokud to platí kdy se tedy použije na libovolného konstruktora 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

  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.
  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.

externí odkazy