Obecné programování - Generic programming

Generické programování je styl počítačového programování, ve kterém jsou algoritmy zapsány z hlediska typů, které mají být později specifikovány, a které jsou pak v případě potřeby vytvořeny pro konkrétní typy poskytnuté jako parametry . Tento přístup, propagovaný programovacím jazykem ML v roce 1973, umožňuje psaní běžných funkcí nebo typů, které se liší pouze v sadě typů, na kterých při použití fungují, čímž se snižuje duplikace . Takové softwarové entity jsou známé jako generika v Ada , C# , Delphi , Eiffel , F# , Java , Nim , Python , Rust , Swift , TypeScript a Visual Basic .NET . Jsou známé jako parametrický polymorfismus v ML , Scala , Julia a Haskell (komunita Haskell také používá termín „generický“ pro související, ale poněkud odlišný koncept); šablony v C ++ a D ; a parametrizované typy ve vlivné knize Design Patterns z roku 1994 .

Termín „generické programování“ původně vytvořili David Musser a Alexander Stepanov ve specifičtějším smyslu než výše, aby popsal paradigma programování, přičemž základní požadavky na typy jsou abstrahovány z konkrétních příkladů algoritmů a datových struktur a formalizovány jako koncepty , s generickými funkcemi implementovanými ve smyslu těchto konceptů, obvykle využívajících mechanismy obecnosti jazyka, jak je popsáno výše.

Stepanov – Musser a další obecná programovací paradigmata

Obecné programování je definováno v Musser & Stepanov (1989) následovně,

Generické programování se soustředí na myšlenku abstrakce od konkrétních, efektivních algoritmů k získání generických algoritmů, které lze kombinovat s různými datovými reprezentacemi za účelem vytvoření široké škály užitečného softwaru.

-  Musser, David R .; Stepanov, Alexander A., ​​Obecné programování

Paradigma „generického programování“ je přístup k rozkladu softwaru, přičemž základní požadavky na typy jsou abstrahovány z konkrétních příkladů algoritmů a datových struktur a formalizovány jako koncepty , analogicky k abstrakci algebraických teorií v abstraktní algebře . Rané příklady tohoto programovacího přístupu byly implementovány ve Scheme a Ada, ačkoli nejznámějším příkladem je Standard Template Library (STL), která vyvinula teorii iterátorů, která se používá k oddělení sekvenčních datových struktur a algoritmů, které na nich působí.

Například s ohledem na datové struktury sekvence N , např. Jednotlivě propojený seznam, vektor atd., A M algoritmy pro jejich provoz, např find. sortAtd., By přímý přístup implementoval každý algoritmus specificky pro každou datovou strukturu, což by dávalo kombinace N × M nářadí. V obecném programovacím přístupu však každá datová struktura vrací model konceptu iterátoru (jednoduchý hodnotový typ, který lze zrušit pro získání aktuální hodnoty nebo jej změnit tak, aby ukazoval na jinou hodnotu v pořadí) a každý algoritmus je místo toho zapsán obecně s argumenty takových iterátorů, např. dvojice iterátorů směřujících na začátek a konec dílčí posloupnosti nebo rozsahu zpracování. Je tedy nutné implementovat pouze kombinace datové struktury a algoritmu N + M. V STL je specifikováno několik konceptů iterátoru, z nichž každý je upřesněním restriktivnějších konceptů, např. Dopředné iterátory poskytují pouze přesun na další hodnotu v pořadí (např. Vhodné pro jednotlivě propojený seznam nebo proud vstupních dat), zatímco náhodný přístup iterátor také poskytuje přímý přístup v konstantním čase k jakémukoli prvku sekvence (např. vhodný pro vektor). Důležitým bodem je, že datová struktura vrátí model nejobecnějšího konceptu, který lze efektivně implementovat - požadavky na výpočetní složitost jsou výslovně součástí definice konceptu. To omezuje datové struktury, na které lze daný algoritmus aplikovat, a takové požadavky na složitost jsou hlavním determinantem výběru datové struktury. Generické programování bylo obdobně aplikováno v jiných doménách, např. Grafových algoritmech.

Všimněte si toho, že ačkoli tento přístup často využívá jazykové funkce generičnosti/šablon při kompilaci , je ve skutečnosti nezávislý na konkrétních jazykově technických podrobnostech. Průkopník generického programování Alexander Stepanov napsal:

Obecné programování je o abstrakci a klasifikaci algoritmů a datových struktur. Inspiraci získává z Knutha, a ne z teorie typů. Jejím cílem je inkrementální konstrukce systematických katalogů užitečných, efektivních a abstraktních algoritmů a datových struktur. Takový závazek je stále snem.

-  Alexander Stepanov, Krátká historie STL

Domnívám se, že teorie iterátorů jsou pro informatiku stejně důležité jako teorie prstenů nebo Banachových prostorů pro matematiku.

-  Alexander Stepanov, Rozhovor s A. Stepanovem

Bjarne Stroustrup poznamenal,

Po Stepanově můžeme definovat generické programování, aniž bychom zmínili jazykové funkce: Zvedněte algoritmy a datové struktury z konkrétních příkladů do jejich nejobecnější a nejabstraktnější podoby.

-  Bjarne Stroustrup, Vyvíjející se jazyk, a to na reálném světě: C ++ 1991-2006

Mezi další programovací paradigmata, která byla popsána jako generické programování, patří generické programování datového typu, jak je popsáno v části „Generické programování - úvod“. Přístup Zrušte svůj standard je lehký generický programovací přístup pro Haskell.

V tomto článku rozlišujeme výše uvedená paradigmata generického programování na vysoké úrovni od obecných mechanismů obecnosti programovacích jazyků nižších úrovní používaných k jejich implementaci (viz obecnost podpory programovacího jazyka ). Další diskuse a srovnání obecných paradigmat programování viz.

Obecná podpora programovacího jazyka

Obecné prostředky existují v jazycích na vysoké úrovni nejméně od 70. let minulého století v jazycích, jako je ML , CLU a Ada , a následně byly přijaty mnoha objektově a objektově orientovanými jazyky, včetně BETA , C ++ , D , Eiffel , Java , a DEC je nyní zaniklý jazyk Trellis-Owl .

Obecnost je implementována a podporována odlišně v různých programovacích jazycích; termín „generický“ byl také používán různě v různých kontextech programování. Například ve Forthu může kompilátor při kompilaci spouštět kód a lze za běhu vytvářet nová klíčová slova kompilátoru a nové implementace pro tato slova. Má několik slov, která odhalují chování kompilátoru, a proto přirozeně nabízí kapacity obecnosti, které však ve většině textů Forth nejsou označovány jako takové. Podobně dynamicky typované jazyky, zvláště interpretované, obvykle ve výchozím nastavení nabízejí obecnost, protože předávání hodnot funkcím a přiřazování hodnot je indiferentní a takové chování se často používá pro abstrakci nebo kódovou terseness, nicméně toto není obvykle označováno jako genericita, protože přímý důsledek systému dynamického psaní používaného jazykem. Termín byl použit ve funkčním programování , konkrétně v jazycích podobných Haskellu , které používají systém strukturálních typů, kde jsou typy vždy parametrické a skutečný kód těchto typů je obecný. Tato použití stále slouží k podobnému účelu ukládání kódu a vykreslování abstrakce.

Pole a struktury lze považovat za předdefinované obecné typy. Každé použití typu pole nebo struktury vytvoří instanci nového konkrétního typu nebo znovu použije předchozí typ instance. Array element types and struct element types are parameterized types, which are used to instantiate the corresponding generic type. To vše je obvykle integrováno v kompilátoru a syntaxe se liší od ostatních generických konstrukcí. Některé rozšiřitelné programovací jazyky se snaží sjednotit integrované a uživatelsky definované obecné typy.

Následuje široký přehled mechanismů genericity v programovacích jazycích. Konkrétní průzkum porovnávající vhodnost mechanismů pro generické programování viz.

V objektově orientovaných jazycích

Při vytváření tříd kontejnerů ve staticky napsaných jazycích je nepohodlné psát konkrétní implementace pro každý obsažený datový typ, zvláště pokud je kód pro každý datový typ prakticky identický. Například v C ++ lze tuto duplikaci kódu obejít definováním šablony třídy:

template<typename T>
class List {
  // Class contents.
};

List<Animal> list_of_animals;
List<Car> list_of_cars;

Nahoře Tje zástupný symbol pro jakýkoli typ zadaný při vytváření seznamu. Tyto „kontejnery typu T“, běžně nazývané šablony , umožňují opětovné použití třídy s různými datovými typy, pokud jsou zachovány určité smlouvy, jako jsou podtypy a podpis . Tento mechanismus genericity by neměl být zaměňován s polymorfismem inkluze , což je algoritmické využití vyměnitelných podtříd: například seznam objektů typu Moving_Objectobsahující objekty typu Animala Car. Šablony lze také použít pro funkce nezávislé na typu, jako v následujícím Swappříkladu:

// "&" denotes a reference
template<typename T>
void Swap(T& a, T& b) { // A similar, but safer and potentially faster function 
                        // is defined in the standard library header <utility>
  T temp = b;
  b = a;
  a = temp;
}

std::string world = "World!";
std::string hello = "Hello, ";
Swap(world, hello);
std::cout << world << hello << ‘\n;  // Output is "Hello, World!".

Výše templatepoužitý konstrukt C ++ je široce citován jako generický konstrukt, který popularizoval pojem mezi programátory a jazykovými designéry a podporuje mnoho generických programovacích idiomů. Programovací jazyk D také nabízí plně generické šablony založené na precedentu C ++, ale se zjednodušenou syntaxí. Programovací jazyk Java poskytuje zařízení genericity syntakticky založené na C ++ od zavedení J2SE 5.0.

C# 2.0, Oxygene 1.5 (také známý jako Chrome) a Visual Basic .NET 2005 mají konstrukce, které využívají podporu generik přítomných v Microsoft .NET Framework od verze 2.0.

Generika v Ada

Ada má generika od svého prvního návrhu v letech 1977–1980. Standardní knihovna používá k poskytování mnoha služeb generika. Ada 2005 přidává do standardní knihovny komplexní generickou kontejnerovou knihovnu, která byla inspirována standardní knihovnou šablon C ++ .

Generická jednotka je balíček nebo podprogram, který má jeden nebo více generických formální parametry .

Obecný formální parametr je hodnota, proměnná, konstanta, typ, podprogram, nebo dokonce instancí další, označený, generické jednotka. U generických formálních typů syntaxe rozlišuje mezi typy diskrétní, s plovoucí desetinnou čárkou, s pevnou řádovou čárkou, přístupové (pointerové) atd. Některé formální parametry mohou mít výchozí hodnoty.

Chcete -li vytvořit instanci obecné jednotky, programátor předá skutečné parametry pro každou formální. Obecná instance se pak chová stejně jako každá jiná jednotka. Je možné generovat generické jednotky za běhu , například uvnitř smyčky.

Příklad

Specifikace generického balíčku:

 generic
    Max_Size : Natural; -- a generic formal value
    type Element_Type is private; -- a generic formal type; accepts any nonlimited type
 package Stacks is
    type Size_Type is range 0 .. Max_Size;
    type Stack is limited private;
    procedure Create (S : out Stack;
                      Initial_Size : in Size_Type := Max_Size);
    procedure Push (Into : in out Stack; Element : in Element_Type);
    procedure Pop (From : in out Stack; Element : out Element_Type);
    Overflow : exception;
    Underflow : exception;
 private
    subtype Index_Type is Size_Type range 1 .. Max_Size;
    type Vector is array (Index_Type range <>) of Element_Type;
    type Stack (Allocated_Size : Size_Type := 0) is record
       Top : Index_Type;
       Storage : Vector (1 .. Allocated_Size);
    end record;
 end Stacks;

Vytvoření instance generického balíčku:

 type Bookmark_Type is new Natural;
 -- records a location in the text document we are editing

 package Bookmark_Stacks is new Stacks (Max_Size => 20,
                                        Element_Type => Bookmark_Type);
 -- Allows the user to jump between recorded locations in a document

Použití instance generického balíčku:

 type Document_Type is record
    Contents : Ada.Strings.Unbounded.Unbounded_String;
    Bookmarks : Bookmark_Stacks.Stack;
 end record;

 procedure Edit (Document_Name : in String) is
   Document : Document_Type;
 begin
   -- Initialise the stack of bookmarks:
   Bookmark_Stacks.Create (S => Document.Bookmarks, Initial_Size => 10);
   -- Now, open the file Document_Name and read it in...
 end Edit;
Výhody a omezení

Syntaxe jazyka umožňuje přesnou specifikaci omezení obecných formálních parametrů. Je například možné určit, že obecný formální typ bude akceptovat pouze modulární typ jako skutečný. Je také možné vyjádřit omezení mezi generickými formálními parametry; například:

 generic
    type Index_Type is (<>); -- must be a discrete type
    type Element_Type is private; -- can be any nonlimited type
    type Array_Type is array (Index_Type range <>) of Element_Type;

V tomto příkladu je Array_Type omezeno Index_Type i Element_Type. Při vytváření instance jednotky musí programátor předat skutečný typ pole, který splňuje tato omezení.

Nevýhodou tohoto jemnozrnného ovládacího prvku je komplikovaná syntaxe, ale protože všechny obecné formální parametry jsou ve specifikaci zcela definovány, kompilátor může generovat generika, aniž by hleděl na tělo generika.

Na rozdíl od C ++ Ada nepovoluje specializované generické instance a vyžaduje, aby byla všechna generika explicitně vytvořena. Tato pravidla mají několik důsledků:

  • kompilátor může implementovat sdílená generika : objektový kód pro generickou jednotku lze sdílet mezi všechny instance (pokud programátor samozřejmě nepožaduje vložení podprogramů). Jako další důsledky:
    • neexistuje možnost bloatování kódu (bloat kódu je v C ++ běžný a vyžaduje zvláštní péči, jak je vysvětleno níže).
    • je možné generovat generika za běhu, stejně jako v době kompilace, protože pro novou instanci není vyžadován žádný nový objektový kód.
    • skutečné objekty odpovídající obecnému formálnímu objektu jsou uvnitř generika vždy považovány za nestatické; podrobnosti a důsledky viz Obecné formální objekty ve Wikibooku.
  • všechny případy generické bytosti jsou naprosto stejné, je snazší revidovat a porozumět programům napsaným ostatními; není třeba brát v úvahu žádné „zvláštní případy“.
  • všechny instance jsou explicitní, neexistují žádné skryté instance, které by mohly ztěžovat porozumění programu.
  • Ada nepovoluje „šablony metaprogramování“, protože nepovoluje specializace.

Šablony v C ++

C ++ používá šablony k povolení obecných technik programování. Standardní knihovna C ++ obsahuje knihovnu standardních šablon nebo STL, která poskytuje rámec šablon pro běžné datové struktury a algoritmy. Šablony v C ++ lze také použít pro metaprogramování šablon , což je způsob, jak předem vyhodnotit část kódu v době kompilace, nikoli za běhu . Pomocí specializace šablon jsou šablony C ++ považovány za úplné Turing .

Technický přehled

Existuje mnoho druhů šablon, nejběžnější jsou šablony funkcí a šablony tříd. Funkce šablona je vzor pro vytvoření běžné funkce založené na typech parametrizaci dodané při instance. Například knihovna C ++ Standard Template Library obsahuje šablonu funkcí, max(x, y)která vytváří funkce, které vracejí buď x nebo y, podle toho , co je větší. max()lze definovat takto:

template<typename T>
T max(T x, T y) {
  return x < y ? y : x;
}

Specializace této šablony funkce, instance s konkrétními typy, lze volat stejně jako běžnou funkci:

std::cout << max(3, 7);  // Outputs 7.

Kompilátor zkoumá argumenty používané k volání maxa určuje, že se jedná o volání max(int, int). Potom instanci verzi funkce, kde typ parametrování Tje int, aby ekvivalent následující funkce:

int max(int x, int y) {
  return x < y ? y : x;
}

To funguje bez ohledu na to, zda argumenty xa yjsou celá čísla, řetězce nebo jakýkoli jiný typ, pro který je výraz x < yrozumný, nebo konkrétněji pro jakýkoli typ, pro který operator<je definován. Společná dědičnost není pro sadu typů, které lze použít, nutná, a je tedy velmi podobná psaní kachen . Program definující vlastní datový typ může použít přetížení operátora k definování významu <pro tento typ, což umožňuje jeho použití se max()šablonou funkce. I když se to v tomto izolovaném příkladu může zdát jako menší výhoda, v kontextu komplexní knihovny, jako je STL, umožňuje programátorovi získat rozsáhlé funkce pro nový datový typ, a to pouhým definováním několika operátorů. Pouhé definování <umožňuje typu pro použití se standardem sort(), stable_sort()a binary_search()algoritmy nebo být zavřel datových struktur, jako jsou sets, hromad a asociativní pole .

Šablony C ++ jsou v době kompilace zcela bezpečné pro typ . Jako ukázka standardní typ complexnedefinuje <operátor, protože na složitá čísla neexistuje přísné pořadí . Pokud tedy x a y jsou hodnoty , max(x, y)selže s chybou kompilace . Stejně tak další šablony, na které se spoléhají, nelze použít na data, pokud není poskytnuto srovnání (ve formě funktoru nebo funkce). Např .: A nelze použít jako klíč pro a, pokud není poskytnuto srovnání. Kompilátory bohužel pro tento druh chyb generují historicky poněkud esoterické, dlouhé a neužitečné chybové zprávy. Zajištění toho, že určitý objekt dodržuje protokol metody, může tento problém zmírnit. Jazyky, které používají místo, mohou také používat hodnoty jako klíče. complex<complexcomplexmapcompare<complex

Jiný druh šablony, šablona třídy, rozšiřuje stejný koncept na třídy. Specializace šablony třídy je třída. Šablony tříd se často používají k vytváření generických kontejnerů. Například STL má kontejner propojeného seznamu . Aby se vytvořil propojený seznam celých čísel, píše se list<int>. Označí se seznam řetězců list<string>. A listmá k sobě přidruženou sadu standardních funkcí, které fungují pro všechny kompatibilní typy parametrizací.

Specializace šablony

Výkonnou funkcí šablon C ++ je specializace šablon . To umožňuje poskytnout alternativní implementace na základě určitých charakteristik parametrizovaného typu, který je instancován. Specializace šablon má dva účely: umožnit určité formy optimalizace a omezit nadýmání kódu.

Zvažte například sort()funkci šablony. Jednou z hlavních činností, které taková funkce dělá, je výměna nebo výměna hodnot ve dvou pozicích kontejneru. Pokud jsou hodnoty velké (pokud jde o počet bajtů potřebných k uložení každého z nich), pak je často rychlejší nejprve vytvořit samostatný seznam ukazatelů na objekty, seřadit tyto ukazatele a poté sestavit konečnou seřazenou sekvenci . Pokud jsou hodnoty poměrně malé, je obvykle nejrychlejší jednoduše vyměnit hodnoty na místě podle potřeby. Kromě toho, pokud je parametrizovaný typ již určitého typu ukazatele, není třeba vytvářet samostatné pole ukazatelů. Specializace šablon umožňuje tvůrci šablon psát různé implementace a specifikovat vlastnosti, které musí mít parametrizované typy pro každou implementaci, která má být použita.

Na rozdíl od šablon funkcí mohou být šablony tříd částečně specializované . To znamená, že pokud jsou známy některé parametry šablony, může být poskytnuta alternativní verze kódu šablony třídy, zatímco ostatní parametry šablony zůstanou obecné. To lze použít například k vytvoření výchozí implementace ( primární specializace ), která předpokládá, že kopírování parametrizačního typu je nákladné, a poté vytvořit dílčí specializace pro typy, které lze levně kopírovat, čímž se zvýší celková efektivita. Klienti takové šablony třídy pouze používají její specializace, aniž by museli vědět, zda kompilátor v každém případě použil primární specializaci nebo nějakou částečnou specializaci. Šablony tříd mohou být také plně specializované, což znamená, že je možné poskytnout alternativní implementaci, pokud jsou známy všechny typy parametrizace.

Výhody a nevýhody

Některá použití šablon, jako například max()funkce, byla dříve vyplněna funkčně podobnými makry preprocesoru (dědictví programovacího jazyka C ). Zde je například možná implementace takového makra:

#define max(a,b) ((a) < (b) ? (b) : (a))

Makra jsou rozbalena (kopie vložena) preprocesorem před vlastní kompilací; šablony jsou skutečné skutečné funkce. Makra se vždy rozšiřují přímo; šablony mohou být také vloženými funkcemi, pokud to kompilátor uzná za vhodné.

Šablony jsou však pro tyto účely obecně považovány za vylepšení oproti makrům. Šablony jsou typově bezpečné. Šablony se vyhýbají některým běžným chybám nalezeným v kódu, který hojně využívá makra podobná funkcím, jako je vyhodnocování parametrů s vedlejšími efekty dvakrát. A co je nejdůležitější, šablony byly navrženy tak, aby byly použitelné pro mnohem větší problémy než makra.

Používání šablon má čtyři hlavní nevýhody: podporované funkce, podpora kompilátoru, špatné chybové zprávy (obvykle s pre C ++ 20 SFINAE) a bloat kódu :

  1. Šablonám v C ++ chybí mnoho funkcí, což často znemožňuje jejich implementaci a přímé použití. Místo toho se programátoři musí spoléhat na komplikované triky, které vedou k nafouklému, těžko pochopitelnému a těžko udržovatelnému kódu. Současný vývoj standardů C ++ tento problém ještě zhoršuje tím, že tyto triky hojně využíváme a vytváříme na nich nebo s ohledem na ně spoustu nových funkcí pro šablony.
  2. Mnoho kompilátorů mělo v minulosti špatnou podporu pro šablony, takže použití šablon mohlo způsobit, že kód bude poněkud méně přenosný. Podpora může být také špatná, pokud je kompilátor C ++ používán s linkerem, který neumí C ++, nebo když se pokoušíte použít šablony přes hranice sdílené knihovny .
  3. Když jsou v kódu používajícím SFINAE detekovány chyby, kompilátory mohou vytvářet matoucí, dlouhé a někdy i neužitečné chybové zprávy. To může ztěžovat vývoj šablon.
  4. Nakonec použití šablon vyžaduje, aby kompilátor generoval samostatnou instanci šablony nebo funkce šablony pro každou permutaci parametrů typu, které jsou s ní použity. (Je to nutné, protože typy v C ++ nemají všechny stejnou velikost a velikosti datových polí jsou důležité pro to, jak třídy fungují.) Nerozlišené používání šablon tedy může vést k nadýmání kódu , což má za následek nadměrně velké spustitelné soubory. Rozumné používání specializace a odvozování šablon však může v některých případech dramaticky omezit nadýmání kódu:

Lze tedy derivaci použít ke snížení problému s replikací kódu, protože se používají šablony? To by zahrnovalo odvození šablony z běžné třídy. Tato technika se osvědčila při omezování nadýmání kódu v reálném použití. Lidé, kteří nepoužívají tuto techniku, zjistili, že replikovaný kód může stát megabajty místa v kódu i v programech střední velikosti.

-  Bjarne Stroustrup , The Design and Evolution of C ++, 1994

Extra instance vytvořené šablonami mohou také způsobit, že některé ladicí programy budou mít potíže s ladnou prací se šablonami. Například nastavení zarážky ladění v rámci šablony ze zdrojového souboru může buď zmeškat nastavení zarážky ve skutečné požadované instanci, nebo může nastavit zarážku na každém místě, kde je instance instance šablony.

Také zdrojový kód implementace šablony musí být zcela dostupný (např. Zahrnut v záhlaví) překladatelské jednotce (zdrojový soubor), která jej používá. Šablony, včetně velké části standardní knihovny, pokud nejsou zahrnuty v hlavičkových souborech, nelze kompilovat. (To je na rozdíl od netemplovaného kódu, který může být kompilován do binárního souboru, který poskytuje pouze hlavičkový soubor deklarací pro kód, který jej používá.) To může být nevýhodou odhalením implementačního kódu, který odstraní některé abstrakce a může omezit jeho použití v projektech uzavřeného zdroje.

Šablony v D

K D programovací jazyk stojany šablony založené na designu na C ++. Většina idiomů šablony C ++ se přenese do D beze změny, ale D přidává některé další funkce:

  • Parametry šablony v D nejsou omezeny pouze na typy a primitivní hodnoty (jako tomu bylo v C ++ před C ++ 20), ale také umožňují libovolné hodnoty v době kompilace (například řetězce a strukturální literály) a aliasy na libovolné identifikátory, včetně jiné šablony nebo instance šablon.
  • Omezení šablony a static ifprohlášení poskytují alternativu k C ++ konceptům C ++ a if constexpr.
  • is(...)Výraz umožňuje spekulativní instance ověřit vlastnosti objektových v době kompilace.
  • autoKlíčové slovo a typeofvýraz povolit typ závěr pro deklarace proměnných a návratové hodnoty funkcí, což umožňuje „typy Voldemort“ (druhy, které nemají globální název).

Šablony v D použít jinou syntaxi než v C ++: vzhledem k tomu, C ++ parametrů šablony jsou zabaleny v úhlových závorkách ( Template<param1, param2>), D používá vykřičníkem a závorky: Template!(param1, param2). Tím se vyhnete problémům s analýzou C ++ kvůli nejednoznačnosti s porovnávacími operátory. Pokud existuje pouze jeden parametr, lze závorky vynechat.

Obvykle D kombinuje výše uvedené funkce a poskytuje polymorfismus v době kompilace pomocí generického programování založeného na vlastnostech. Například vstupní rozsah je definován jako jakýkoli typ, který splňuje kontroly prováděné isInputRange, který je definován následovně:

template isInputRange(R)
{
    enum bool isInputRange = is(typeof(
    (inout int = 0)
    {
        R r = R.init;     // can define a range object
        if (r.empty) {}   // can test for empty
        r.popFront();     // can invoke popFront()
        auto h = r.front; // can get the front of the range
    }));
}

Funkce, která přijímá pouze vstupní rozsahy, pak může použít výše uvedenou šablonu v omezení šablony:

auto fun(Range)(Range range)
    if (isInputRange!Range)
{
    // ...
}
Generování kódu

Kromě metaprogramování šablon poskytuje D také několik funkcí, které umožňují generování kódu v době kompilace:

  • importVýraz umožňuje čtení souborů z disku a používání jeho obsah jako výraz řetězec.
  • Reflexe v době kompilace umožňuje výčet a kontrolu deklarací a jejich členů během kompilace.
  • Uživatelem definované atributy umožňují uživatelům připojit libovolné identifikátory k deklaracím, které lze poté vyčíslit pomocí reflexe při kompilaci.
  • Provádění funkcí kompilace (CTFE) umožňuje při kompilaci interpretovat podmnožinu D (omezenou na bezpečné operace).
  • Řetězcové mixiny umožňují vyhodnocení a kompilaci obsahu řetězcového výrazu jako D kód, který se stane součástí programu.

Kombinace výše uvedeného umožňuje generování kódu na základě existujících deklarací. Například rámce serializace D mohou vytvořit výčet členů typu a generovat specializované funkce pro každý serializovaný typ k provádění serializace a deserializace. Uživatelem definované atributy mohou dále indikovat pravidla serializace.

importExprese a kompilaci čas spuštění funkce také umožňují efektivní provádění domény specifické jazyky . Například vzhledem k funkci, která přebírá řetězec obsahující šablonu HTML a vrací ekvivalentní zdrojový kód D, je možné jej použít následujícím způsobem:

// Import the contents of example.htt as a string manifest constant.
enum htmlTemplate = import("example.htt");

// Transpile the HTML template to D code.
enum htmlDCode = htmlTemplateToD(htmlTemplate);

// Paste the contents of htmlDCode as D code.
mixin(htmlDCode);

Obecnost v Eiffelově

Generické třídy jsou součástí Eiffelu od původní metody a jazykového designu. Nadační publikace Eiffela používají termín genericita k popisu vytváření a používání generických tříd.

Základní/neomezená obecnost

Obecné třídy jsou deklarovány názvem třídy a seznamem jednoho nebo více formálních obecných parametrů . V následujícím kódu LISTmá třída jeden formální obecný parametrG

class
    LIST [G]
            ...
feature   -- Access
    item: G
            -- The item currently pointed to by cursor
            ...
feature   -- Element change
    put (new_item: G)
            -- Add `new_item' at the end of the list
            ...

Formální obecné parametry jsou zástupné symboly pro názvy libovolných tříd, které budou dodány při deklaraci generické třídy, jak je ukázáno ve dvou generických derivacích níže, kde ACCOUNTa DEPOSITjsou názvy jiných tříd. ACCOUNTa DEPOSITjsou považovány za skutečné obecné parametry , protože poskytují skutečné názvy tříd, které lze nahradit Gpři skutečném použití.

    list_of_accounts: LIST [ACCOUNT]
            -- Account list

    list_of_deposits: LIST [DEPOSIT]
            -- Deposit list

V systému typu Eiffel, ačkoli třída LIST [G]je považována za třídu, není považována za typ. Za typ je však považováno generické odvození LIST [G]takového typu, jako LIST [ACCOUNT]je.

Omezená genericita

Pro výše uvedenou třídu seznamu Gmůže být skutečným obecným parametrem, který nahrazuje, jakákoli jiná dostupná třída. Chcete -li omezit sadu tříd, ze kterých lze vybrat platné skutečné obecné parametry, lze určit obecné omezení . V SORTED_LISTníže uvedené deklaraci třídy generické omezení určuje, že jakýkoli platný skutečný obecný parametr bude třída, která dědí ze třídy COMPARABLE. Obecné omezení zajišťuje, že prvky a SORTED_LISTlze ve skutečnosti třídit.

class
    SORTED_LIST [G -> COMPARABLE]

Generika v Javě

V roce 2004 byla do programovacího jazyka Java v rámci J2SE 5.0 přidána podpora pro generika neboli „kontejnery typu T“ . V Javě se generika kontroluje pouze v době kompilace na správnost typu. Informace o obecném typu jsou poté odebrány procesem nazývaným mazání typů , aby byla zachována kompatibilita se starými implementacemi JVM, a tím byla za běhu nedostupná. Například a je převedeno na nezpracovaný typ . Kompilátor vloží přetypování typů pro převod prvků na typ, když jsou načteny ze seznamu, což snižuje výkon ve srovnání s jinými implementacemi, jako jsou šablony C ++. List<String>ListString

Obecnost v .NET [C#, VB.NET]

Generika byla přidána jako součást rozhraní .NET Framework 2.0 v listopadu 2005 na základě výzkumného prototypu od společnosti Microsoft Research zahájeného v roce 1999. Ačkoli generika .NET podobná generikám v Javě nepoužívají mazání typů , ale implementují generika jako mechanismus první třídy za běhu pomocí reifikace . Tato volba návrhu poskytuje další funkce, například umožňuje reflexi se zachováním obecných typů a také zmírňuje některá omezení mazání (například neschopnost vytvářet obecná pole). To také znamená, že neexistuje žádný výkon hit z runtime odlitků a obvykle drahé boxerské konverzí . Když jsou jako obecné argumenty použity primitivní a hodnotové typy, získají specializované implementace, což umožňuje efektivní generické kolekce a metody. Stejně jako v C ++ a Javě jsou vnořené generické typy, jako například Dictionary <string, List <int>>, platnými typy, ale nedoporučuje se pro podpisy členů v pravidlech návrhu analýzy kódu.

.NET umožňuje šest variant omezení obecného typu pomocí whereklíčového slova včetně omezení generických typů na typy hodnot, na třídy, na konstruktory a na implementaci rozhraní. Níže je uveden příklad s omezením rozhraní:

using System;

class Sample
{
    static void Main()
    {
        int[] array = { 0, 1, 2, 3 };
        MakeAtLeast<int>(array, 2); // Change array to { 2, 2, 2, 3 }
        foreach (int i in array)
            Console.WriteLine(i); // Print results.
        Console.ReadKey(true);
    }

    static void MakeAtLeast<T>(T[] list, T lowest) where T : IComparable<T>
    {
        for (int i = 0; i < list.Length; i++)
            if (list[i].CompareTo(lowest) < 0)
                list[i] = lowest;
    }
}

MakeAtLeast()Způsob umožňuje provoz na pole, s prvky uvedeného druhu T. Omezení typu metody naznačuje, že je metoda použitelná pro jakýkoli typ, Tkterý implementuje obecné IComparable<T>rozhraní. Tím je zajištěna chyba kompilace , pokud je metoda volána, pokud typ nepodporuje srovnání. Rozhraní poskytuje obecnou metodu CompareTo(T).

Výše uvedenou metodu lze také zapsat bez generických typů, jednoduše pomocí negenerického Arraytypu. Protože jsou však pole protikladná , přetypování by nebylo bezpečné pro typ a kompilátor by nemohl najít určité možné chyby, které by se jinak zachytily při použití generických typů. Kromě toho by metoda musela objectmísto toho přistupovat k položkám pole jako s a vyžadovala by casting pro porovnání dvou prvků. (U hodnotových typů, jako jsou tyto, jako je inttento, vyžaduje převod boxu , i když to lze obejít pomocí Comparer<T>třídy, jak se to dělá ve standardních třídách kolekce.)

Pozoruhodné chování statických členů ve generické třídě .NET je vytváření instancí statických členů podle typu za běhu (viz příklad níže).

    //A generic class
    public class GenTest<T>
    {
        //A static variable - will be created for each type on reflection
        static CountedInstances OnePerType = new CountedInstances();

        //a data member
        private T mT;

        //simple constructor
        public GenTest(T pT)
        {
            mT = pT;
        }
    }

    //a class
    public class CountedInstances
    {
        //Static variable - this will be incremented once per instance
        public static int Counter;

        //simple constructor
        public CountedInstances()
        {
            //increase counter by one during object instantiation
            CountedInstances.Counter++;
        }
    }

  //main code entry point
  //at the end of execution, CountedInstances.Counter = 2
  GenTest<int> g1 = new GenTest<int>(1);
  GenTest<int> g11 = new GenTest<int>(11);
  GenTest<int> g111 = new GenTest<int>(111);
  GenTest<double> g2 = new GenTest<double>(1.0);

Obecnost v Delphi

Dialekt Delphi Object Pascal získal generika ve verzi Delphi 2007, zpočátku pouze s (nyní ukončeným) kompilátorem .NET, než byl přidán do nativního kódu ve verzi Delphi 2009. Sémantika a možnosti generik Delphi jsou z velké části modelovány na základě generik v .NET 2.0, i když implementace je podle potřeby zcela odlišná. Zde je víceméně přímý překlad prvního příkladu C# uvedeného výše:

program Sample;

{$APPTYPE CONSOLE}

uses
  Generics.Defaults; //for IComparer<>

type
  TUtils = class
    class procedure MakeAtLeast<T>(Arr: TArray<T>; const Lowest: T;
      Comparer: IComparer<T>); overload;
    class procedure MakeAtLeast<T>(Arr: TArray<T>; const Lowest: T); overload;
  end;

class procedure TUtils.MakeAtLeast<T>(Arr: TArray<T>; const Lowest: T;
  Comparer: IComparer<T>);
var
  I: Integer;
begin
  if Comparer = nil then Comparer := TComparer<T>.Default;
  for I := Low(Arr) to High(Arr) do
    if Comparer.Compare(Arr[I], Lowest) < 0 then
      Arr[I] := Lowest;
end;

class procedure TUtils.MakeAtLeast<T>(Arr: TArray<T>; const Lowest: T);
begin
  MakeAtLeast<T>(Arr, Lowest, nil);
end;

var
  Ints: TArray<Integer>;
  Value: Integer;
begin
  Ints := TArray<Integer>.Create(0, 1, 2, 3);
  TUtils.MakeAtLeast<Integer>(Ints, 2);
  for Value in Ints do
    WriteLn(Value);
  ReadLn;
end.

Stejně jako u C#mohou mít metody i celé typy jeden nebo více parametrů typu. V tomto příkladu je TArray obecným typem (definovaným jazykem) a MakeAtLeast obecnou metodou. Dostupná omezení jsou velmi podobná dostupným omezením v C#: jakýkoli typ hodnoty, jakákoli třída, konkrétní třída nebo rozhraní a třída s konstruktorem bez parametrů. Vícenásobná omezení fungují jako aditivní unie.

Obecnost ve Free Pascalu

Free Pascal implementoval generika před Delphi as různou syntaxí a sémantikou. Od verze FPC 2.6.0 je však při použití jazykového režimu {$ mode Delphi} k dispozici syntaxe ve stylu Delphi. Programátoři Free Pascal jsou tedy schopni používat generika v jakémkoli stylu, kterému dávají přednost.

Příklad Delphi a Free Pascal:

// Delphi style
unit A;

{$ifdef fpc}
  {$mode delphi}
{$endif}

interface

type
  TGenericClass<T> = class
    function Foo(const AValue: T): T;
  end;

implementation

function TGenericClass<T>.Foo(const AValue: T): T;
begin
  Result := AValue + AValue;
end;

end.

// Free Pascal's ObjFPC style
unit B;

{$ifdef fpc}
  {$mode objfpc}
{$endif}

interface

type
  generic TGenericClass<T> = class
    function Foo(const AValue: T): T;
  end;

implementation

function TGenericClass.Foo(const AValue: T): T;
begin
  Result := AValue + AValue;
end;

end.

// example usage, Delphi style
program TestGenDelphi;

{$ifdef fpc}
  {$mode delphi}
{$endif}

uses
  A,B;

var
  GC1: A.TGenericClass<Integer>;
  GC2: B.TGenericClass<String>;
begin
  GC1 := A.TGenericClass<Integer>.Create;
  GC2 := B.TGenericClass<String>.Create;
  WriteLn(GC1.Foo(100)); // 200
  WriteLn(GC2.Foo('hello')); // hellohello
  GC1.Free;
  GC2.Free;
end.

// example usage, ObjFPC style
program TestGenDelphi;

{$ifdef fpc}
  {$mode objfpc}
{$endif}

uses
  A,B;

// required in ObjFPC
type
  TAGenericClassInt = specialize A.TGenericClass<Integer>;
  TBGenericClassString = specialize B.TGenericClass<String>;
var
  GC1: TAGenericClassInt;
  GC2: TBGenericClassString;
begin
  GC1 := TAGenericClassInt.Create;
  GC2 := TBGenericClassString.Create;
  WriteLn(GC1.Foo(100)); // 200
  WriteLn(GC2.Foo('hello')); // hellohello
  GC1.Free;
  GC2.Free;
end.

Funkční jazyky

Obecnost v Haskellu

Mechanismus třídy třídy Haskell podporuje generické programování. Šest předdefinovaných tříd typů v Haskellu (včetně Eqtypů, které lze porovnávat pro rovnost, a Showtypů, jejichž hodnoty lze vykreslit jako řetězce) mají speciální vlastnost podpory odvozených instancí. To znamená, že programátor definující nový typ může uvést, že tento typ má být instancí jedné z těchto tříd speciálních typů, aniž by poskytoval implementace metod třídy, jak je obvykle nutné při deklaraci instancí tříd. Všechny potřebné metody budou „odvozeny“ - tj. Vytvořeny automaticky - na základě struktury typu. Například následující deklarace typu binárních stromů uvádí, že se má jednat o instanci tříd Eqa Show:

data BinTree a = Leaf a | Node (BinTree a) a (BinTree a)
      deriving (Eq, Show)

Výsledkem je, že funkce rovnosti ( ==) a funkce řetězcové reprezentace ( show) jsou automaticky definovány pro jakýkoli typ formuláře BinTree Tza předpokladu, že Tsám podporuje tyto operace.

Podpora odvozených instancí Eqa Showjejich metody ==a showgeneriky je kvalitativně odlišná od para-metricky polymorfních funkcí: tyto „funkce“ (přesněji typově indexované rodiny funkcí) lze aplikovat na hodnoty různých typů, a přestože pro každý typ argumentu se chovají odlišně, s přidáním podpory pro nový typ je potřeba jen málo práce. Ralf Hinze (2004) ukázal, že podobných efektů lze dosáhnout u uživatelem definovaných tříd typů určitými programovacími technikami. Jiní výzkumníci navrhli přístupy k tomuto a dalším druhům obecnosti v kontextu Haskell a rozšíření Haskell (diskutováno níže).

Polyp

PolyP bylo první generické rozšíření programovacího jazyka pro Haskell . V PolyP se obecné funkce nazývají polytypické . Jazyk zavádí speciální konstrukci, ve které lze takové polytypové funkce definovat strukturální indukcí přes strukturu funktoru vzoru pravidelného datového typu. Pravidelné datové typy v PolyP jsou podmnožinou datových typů Haskell. Pravidelný datový typ t musí být typu * → * , a pokud a je v definici formální argument typu, pak všechna rekurzivní volání t musí mít tvar ta . Tato omezení vylučují datové typy vyššího druhu i vnořené datové typy, kde rekurzivní volání mají jinou formu. Funkce sloučení v PolyP je zde uvedena jako příklad:

   flatten :: Regular d => d a -> [a]
   flatten = cata fl

   polytypic fl :: f a [a] -> [a]
     case f of
       g+h -> either fl fl
       g*h -> \(x,y) -> fl x ++ fl y
       () -> \x -> []
       Par -> \x -> [x]
       Rec -> \x -> x
       d@g -> concat . flatten . pmap fl
       Con t -> \x -> []

   cata :: Regular d => (FunctorOf d a b -> b) -> d a -> b
Obecný Haskell

Generic Haskell je dalším rozšířením Haskell , vyvinutým na univerzitě v Utrechtu v Nizozemsku . Rozšíření, která poskytuje, jsou:

  • Hodnoty indexované podle typu jsou definovány jako hodnoty indexované přes různé konstruktory typu Haskell (jednotky, primitivní typy, součty, produkty a konstruktory typu definované uživatelem). Kromě toho můžeme také specifikovat chování hodnot indexovaných pro konkrétní konstruktor pomocí případů konstruktoru a znovu použít jednu obecnou definici v jiné pomocí výchozích případů .

Výslednou typově indexovanou hodnotu lze specializovat na jakýkoli typ.

  • Druhy indexované podle druhu jsou typy indexované nad druhy, definované zadáním případu pro * i k → k ' . Instance jsou získány použitím druhu indexovaného na druh.
  • Obecné definice lze použít tak, že je použijete na typ nebo druh. Tomu se říká obecná aplikace . Výsledkem je typ nebo hodnota v závislosti na tom, jaký druh obecné definice se použije.
  • Obecná abstrakce umožňuje definovat obecné definice abstrakcí parametru typu (daného druhu).
  • Typově indexované typy jsou typy, které jsou indexovány přes konstruktory typů. Ty lze použít k poskytnutí typů více zapojeným obecným hodnotám. Výsledné typy s indexovaným typem lze specializovat na jakýkoli typ.

Jako příklad funkce rovnosti v Generic Haskell:

   type Eq {[ * ]} t1 t2 = t1 -> t2 -> Bool
   type Eq {[ k -> l ]} t1 t2 = forall u1 u2. Eq {[ k ]} u1 u2 -> Eq {[ l ]} (t1 u1) (t2 u2)

   eq {| t :: k |} :: Eq {[ k ]} t t
   eq {| Unit |} _ _ = True
   eq {| :+: |} eqA eqB (Inl a1) (Inl a2) = eqA a1 a2
   eq {| :+: |} eqA eqB (Inr b1) (Inr b2) = eqB b1 b2
   eq {| :+: |} eqA eqB _ _ = False
   eq {| :*: |} eqA eqB (a1 :*: b1) (a2 :*: b2) = eqA a1 a2 && eqB b1 b2
   eq {| Int |} = (==)
   eq {| Char |} = (==)
   eq {| Bool |} = (==)

Čistý

Clean nabízí generické programování založené na PolyP a generickém Haskellu podporovaném GHC> = 6.0. Parametrizuje se podle druhu, ale nabízí přetížení.

Jiné jazyky

Jazyky v rodině ML podporují generické programování prostřednictvím parametrického polymorfismu a generických modulů nazývaných funktory. Oba standard ML a OCaml poskytovat funktory, které jsou podobné šablony třídy a generických balíčků Adina. Syntaktické abstrakce schématu mají také souvislost s obecností - ve skutečnosti jde o nadmnožinu šablon C ++.

Modul Verilog může mít jeden nebo více parametrů, kterým jsou přiřazeny jejich skutečné hodnoty při vytváření instance modulu. Jedním příkladem je generické registrové pole, kde je šířka pole udávána prostřednictvím parametru. Takové pole v kombinaci s obecným drátovým vektorem může vytvořit generickou vyrovnávací paměť nebo paměťový modul s libovolnou šířkou bitů z implementace jednoho modulu.

VHDL , odvozený od Ada, má také obecné funkce.

C podporuje "typové obecné výrazy" pomocí klíčového slova: _Generic

#define cbrt(x) _Generic((x), long double: cbrtl, \
                              default: cbrt, \
                              float: cbrtf)(x)

Viz také

Reference

Prameny

Další čtení

externí odkazy

C ++/D
C#/. SÍŤ
Delphi/Object Pascal
Eiffelova
Haskell
Jáva