Polymorfní rekurze - Polymorphic recursion
v počítačová věda, polymorfní rekurze (označovaný také jako Milner – Mycroft typovatelnost nebo Milner – Mycroftův počet) odkazuje na a rekurzivní parametricky polymorfní funkce kde se parametr typu mění s každým provedeným rekurzivním vyvoláním, místo aby zůstal konstantní. Odvození typu pro polymorfní rekurzi je ekvivalentní semi-sjednocení a proto nerozhodnutelný a vyžaduje použití a semi-algoritmus nebo programátor dodán zadejte poznámky.[1]
Příklad
Vnořené datové typy
Zvažte následující vnořený datový typ:
data Vnořené A = A :<: (Vnořené [A]) | Epsiloninfixr 5 :<:vnořené = 1 :<: [2,3,4] :<: [[5,6],[7],[8,9]] :<: Epsilon
Funkce délky definovaná v tomto datovém typu bude polymorfně rekurzivní, protože se změní typ argumentu Vnořené a
na Vnořené [a]
v rekurzivním volání:
délka :: Vnořené A -> Intdélka Epsilon = 0délka (_ :<: xs) = 1 + délka xs
Všimněte si, že Haskell normálně vyvozuje podpis typu pro tak jednoduše vypadající funkci, ale zde ji nelze vynechat bez spuštění chyby typu.
Vyšší typy
![]() | Tato sekce potřebuje expanzi. Můžete pomoci přidávat k tomu. (Květen 2012) |
Aplikace
Analýza programu
v typová analýza programu polymorfní rekurze je často nezbytná pro získání vysoké přesnosti analýzy. Pozoruhodné příklady systémů využívajících polymorfní rekurzi zahrnují Dussart, Henglein a Mossin's analýza času vazby[2] a Tofte – Talpin správa paměti podle regionu Systém.[3] Vzhledem k tomu, že tyto systémy předpokládají, že výrazy již byly zadány v podkladovém systému typů (není nutné použít polymorfní rekurzi), lze odvodit rozhodování znovu.
Datové struktury, detekce chyb, řešení grafů
Funkční programování datových struktur často používá polymorfní rekurzi ke zjednodušení kontroly chyb typu a řešení problémů s ošklivými „středními“ dočasnými řešeními, které pohlcují paměť v tradičnějších datových strukturách, jako jsou stromy. Ve dvou následujících citacích uvádí Okasaki (str. 144–146) příklad CONS v Haskell přičemž systém polymorfního typu automaticky označuje chyby programátoru.[4] Rekurzivní aspekt spočívá v tom, že definice typu zajišťuje, že nejvzdálenější konstruktor má jeden prvek, druhý pár, třetí pár párů atd. Rekurzivně, čímž nastavuje vzor automatického vyhledávání chyb v datovém typu. Roberts (str. 171) uvádí související příklad v Jáva, používat Třída reprezentovat rám zásobníku. Uvedený příklad je řešením Hanojská věž problém, ve kterém zásobník simuluje polymorfní rekurzi s počáteční, dočasnou a koncovou vnořenou strukturou nahrazení zásobníku.[5]
Viz také
Poznámky
- ^ Henglein 1993.
- ^ Dussart, Dirk; Henglein, Fritz; Mossin, Christian. "Polymorfní rekurze a kvalifikace podtypu: Polymorfní analýza času vazby v polynomiálním čase". Sborník z 2. mezinárodního symposia statické analýzy (SAS).
- ^ Tofte, Mads; Talpin, Jean-Pierre (1994). "Implementace zadaného počtu λ podle hodnoty podle hodnoty pomocí zásobníku regionů". POPL '94: Sborník 21. sympozia ACM SIGPLAN-SIGACT o zásadách programovacích jazyků. New York, NY, USA: ACM. 188–201. doi:10.1145/174675.177855. ISBN 0-89791-636-0.
- ^ Chris Okasaki (1999). Čistě funkční datové struktury. New York: Cambridge. str. 144. ISBN 978-0521663502.
- ^ Eric Roberts (2006). Myšlení rekurzivně s Javou. New York: Wiley. str.171. ISBN 978-0471701460.
Další čtení
- Meertens, Lambert (1983). "Přírůstková kontrola polymorfního typu v B" (PDF). ACM Symposium on Principles of Programming Languages (POPL), Austin, Texas.
- Mycroft, Alan (1984). Schémata polymorfního typu a rekurzivní definice. Mezinárodní symposium o programování, Toulouse, Francie. Přednášky z informatiky. 167. 217–228. doi:10.1007/3-540-12925-1_41. ISBN 978-3-540-12925-7.
- Henglein, Fritz (1993). Msgstr "Odvození typu s polymorfní rekurzí". Transakce ACM v programovacích jazycích a systémech. 15 (2): 253–289. CiteSeerX 10.1.1.42.3091. doi:10.1145/169701.169692.
- Kfoury, A. J.; Tiuryn, J .; Urzyczyn, P. (duben 1993). "Rekonstrukce typu za přítomnosti polymorfní rekurze". Transakce ACM v programovacích jazycích a systémech. 15 (2): 290–311. doi:10.1145/169701.169687. ISSN 0164-0925.
- Michael I. Schwartzbach (červen 1995). „Odvoz polymorfního typu“. Technická zpráva BRICS-LS-95-3.
- Emms, Martin; Leiß, Hans (1996). „Rozšíření kontroly typu pro SML o polymorfní rekurzi - důkaz správnosti“. Technická zpráva 96-101.
- Richard Bird a Lambert Meertens (1998). "Vnořené datové typy".
- C. Vasconcellos, L. Figueiredo, C. Camarao (2003). "Praktická odvození typu pro polymorfní rekurzi: implementace v Haskellu". Journal of Universal Computer Science.
- L. Figueiredo, C. Camarao. Msgstr "Odvození typu pro polymorfní rekurzivní definice: specifikace v Haskellu".
- Hallett, J. J; Kfoury, A. J. (červenec 2005). „Příklady programování vyžadující polymorfní rekurzi“. Elektronické poznámky v teoretické informatice. 136: 57–102. doi:10.1016 / j.entcs.2005.06.014. ISSN 1571-0661.
externí odkazy
![]() | Tento programování související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to. |