Zobecněný algebraický datový typ - Generalized algebraic data type

v Funkcionální programování, a zobecněný algebraický datový typ (GADT, taky prvotřídní fantomový typ,[1] hlídaný rekurzivní datový typ,[2] nebo rovnoprávný typ[3]) je zobecněním parametrické algebraické datové typy.

Přehled

V GADT konstruktéři produktu (tzv datové konstruktory v Haskell ) může poskytnout explicitní instanci ADT jako instanci typu jejich návratové hodnoty. To umožňuje definovat funkce s pokročilejším chováním typu. U datového konstruktoru Haskell 2010 má návratová hodnota instanci typu implikovanou instancí parametrů ADT v aplikaci konstruktoru.

- Parametrický ADT, který není GADTdata Seznam A = Nula | Nevýhody A (Seznam A)celá čísla = Nevýhody 12 (Nevýhody 107 Nula)       - typ celých čísel je List Intstruny = Nevýhody "loď" (Nevýhody "dok" Nula) - typ řetězců je List String- GADTdata Expr A kde    EBool  :: Boole     -> Expr Boole    EInt   :: Int      -> Expr Int    Rovnocenné :: Expr Int -> Expr Int  -> Expr Booleeval :: Expr A -> Aeval E = případ E z    EBool A    -> A    EInt A     -> A    Rovnocenné A b -> (eval A) == (eval b)expr1 = Rovnocenné (EInt 2) (EInt 3)        - typ expr1 je Expr Boolret = eval expr1                        - ret je False

V současné době jsou implementovány v EU GHC překladač jako nestandardní rozšíření, používaný mimo jiné Mopslíci a Darcs. OCaml nativně podporuje GADT od verze 4.00.[4]

Implementace GHC poskytuje podporu pro existenciálně kvantifikované parametry typu a pro místní omezení.

Dějiny

Časnou verzi zobecněných algebraických datových typů popsal Augustsson & Petersson (1994) a na základě porovnávání vzorů v ALF.

Zobecněné algebraické datové typy byly zavedeny nezávisle na sobě Cheney & Hinze (2003) a před Xi, Chen & Chen (2003) jako rozšíření do ML a Haskell je algebraické datové typy.[5] Oba jsou v zásadě rovnocenné. Jsou podobné jako induktivní rodiny datových typů (nebo induktivní datové typy) nalezen v Coq je Počet indukčních konstrukcí a další závislé typy jazyků, modulovat závislé typy a kromě toho, že tyto mají další omezení pozitivity který není v GADT vynucován.[6]

Sulzmann, Wazny & Stuckey (2006) představen rozšířené algebraické datové typy které kombinují GADT s existenční datové typy a typová třída omezení zavedená Perry (1991), Läufer & Odersky (1994) a Läufer (1996).

Odvození typu v nepřítomnosti dodaného programátoru zadejte poznámky je nerozhodnutelný[7] a funkce definované přes GADT nepřipouštějí hlavní typy obecně.[8] Typ rekonstrukce vyžaduje několik kompromisů designu a je oblastí aktivního výzkumu (Peyton Jones, Washburn & Weirich 2004; Peyton Jones a kol. 2006; Pottier & Régis-Gianas 2006; Sulzmann, Schrijvers & Stuckey 2006; Simonet & Pottier 2007; Schrijvers a kol. 2009; Lin & Sheard 2010a; Lin & Sheard 2010b; Vytiniotis, Peyton Jones & Schrijvers 2010; Vytiniotis a kol. 2011).

Aplikace

Mezi aplikace GADT patří generické programování, modelování programovacích jazyků (vyšší syntaxe abstraktního řádu ), udržování invarianty v datové struktury, vyjadřující omezení v vestavěné jazyky specifické pro doménu a modelování objektů.[9]

Abstraktní syntaxe vyššího řádu

Další informace: Abstraktní syntaxe vyššího řádu

Důležitou aplikací GADT je ​​vložení vyšší syntaxe abstraktního řádu v typ bezpečný móda. Zde je vložení souboru jednoduše zadaný lambda kalkul s libovolnou sbírkou základní typy, n-tice a a kombinátor pevných bodů:

data Lam :: * -> * kde  Výtah :: A                     -> Lam A        - ^ zvednutá hodnota  Pár :: Lam A -> Lam b        -> Lam (A, b)   - ^ produkt  Lam  :: (Lam A -> Lam b)      -> Lam (A -> b) - ^ lambda abstrakce  Aplikace  :: Lam (A -> b) -> Lam A -> Lam b        - ^ funkce aplikace  Opravit  :: Lam (A -> A)          -> Lam A        - ^ pevný bod

A funkce bezpečného vyhodnocení typu:

eval :: Lam t -> teval (Výtah proti)   = protieval (Pár l r) = (eval l, eval r)eval (Lam F)    = X -> eval (F (Výtah X))eval (Aplikace F X)  = (eval F) (eval X)eval (Opravit F)    = (eval F) (eval (Opravit F))

Faktoriální funkci lze nyní zapsat jako:

skutečnost = Opravit (Lam (F -> Lam (y -> Výtah (-li eval y == 0 pak 1 jiný eval y * (eval F) (eval y - 1)))))eval(skutečnost)(10)

Při použití běžných algebraických datových typů bychom narazili na problémy. Zrušení parametru typu by způsobilo, že zvednuté základní typy existenciálně kvantifikovaly, což znemožňuje zápis hodnotitele. S parametrem typu bychom byli stále omezeni na jeden základní typ. Navíc špatně tvarované výrazy jako např App (Lam (x -> Lam (y -> App x y))) (Lift True) by bylo možné postavit, zatímco jsou typově nesprávné pomocí GADT. Dobře vytvořený analog je App (Lam (x -> Lam (y -> App x y))) (Lift (z -> True)). Je to proto, že typ X je Lam (a -> b), odvozený z typu Lam datový konstruktor.

Viz také

Poznámky

  1. ^ Cheney & Hinze 2003.
  2. ^ Xi, Chen & Chen 2003.
  3. ^ Sheard & Pasalic 2004.
  4. ^ „OCaml 4.00.1“. ocaml.org.
  5. ^ Cheney & Hinze 2003, str. 25.
  6. ^ Cheney & Hinze 2003, s. 25–26.
  7. ^ Peyton Jones, Washburn & Weirich 2004, str. 7.
  8. ^ Schrijvers a kol. 2009, str. 1.
  9. ^ Peyton Jones, Washburn & Weirich 2004, str. 3.

Další čtení

Aplikace
Sémantika
  • Patricia Johann a Neil Ghani (2008). "Základy strukturovaného programování s GADT".
  • Arie Middelkoop, Atze Dijkstra a S. Doaitse Swierstra (2011). "Štíhlá specifikace pro GADT: systém F s prvotřídními důkazy o rovnosti". Vyšší řád a symbolický výpočet.
Typ rekonstrukce
jiný
  • Andrew Kennedy a Claudio V. Russo. "Zobecněné algebraické datové typy a objektově orientované programování". Ve sborníku z 20. ročníku konference ACM SIGPLAN o objektově orientovaném programování, systémech, jazycích a aplikacích. ACM Press, 2005.

externí odkazy