Generisk programmering - Generic programming

For ikke at forveksle med genetisk programmering .

Programmeringsparadigmer

Generisk programmering er en stil til computerprogrammering , hvor algoritmer skrives i form af typer, der skal specificeres-senere , der derefter instantieres, når det er nødvendigt for bestemte typer, der leveres som parametre . Denne fremgangsmåde, der blev banebrydende af programmeringssproget ML i 1973, gør det muligt at skrive fælles funktioner eller typer, der kun adskiller sig i de typer, de fungerer på, når de bruges, hvilket reducerer dobbeltarbejde . Sådanne softwareenheder er kendt som generika i Ada , C# , Delphi , Eiffel , F# , Java , Nim , Python , Rust , Swift , TypeScript og Visual Basic .NET . De er kendt som parametrisk polymorfisme i ML , Scala , Julia og Haskell (Haskell -samfundet bruger også udtrykket "generisk" om et beslægtet, men noget anderledes begreb); skabeloner i C ++ og D ; og parameteriserede typer i den indflydelsesrige bog fra 1994 Designmønstre .

Udtrykket "generisk programmering" blev oprindeligt opfundet af David Musser og Alexander Stepanov i en mere specifik forstand end ovenstående for at beskrive et programmeringsparadigme, hvor grundlæggende krav til typer abstraheres fra konkrete eksempler på algoritmer og datastrukturer og formaliseres som begreber , med generiske funktioner implementeret med hensyn til disse begreber, typisk ved hjælp af sproggeneritetsmekanismer som beskrevet ovenfor.

Stepanov – Musser og andre generiske programmeringsparadigmer

Generisk programmering defineres i Musser & Stepanov (1989) som følger,

Generisk programmering centrerer sig om ideen om at abstrahere fra konkrete, effektive algoritmer for at opnå generiske algoritmer, der kan kombineres med forskellige datarepræsentationer for at producere en lang række nyttig software.

-  Musser, David R .; Stepanov, Alexander A., ​​Generisk programmering

Det "generiske programmeringsparadigme" er en tilgang til software -nedbrydning, hvor grundlæggende krav til typer abstraheres fra konkrete eksempler på algoritmer og datastrukturer og formaliseres som begreber , analogt med abstraktion af algebraiske teorier i abstrakt algebra . Tidlige eksempler på denne programmeringsmetode blev implementeret i Scheme og Ada, selvom det mest kendte eksempel er Standard Template Library (STL), der udviklede en teori om iteratorer , der bruges til at afkoble sekvensdatastrukturer og algoritmerne, der fungerer på dem.

For eksempel, givet N -sekvensdatastrukturer, f.eks. Enkeltstående link, vektor osv., Og M -algoritmer til at operere på dem, f.eks find. sortOsv., Ville en direkte tilgang implementere hver algoritme specifikt for hver datastruktur, hvilket giver N × M -kombinationer til gennemføre. I den generiske programmeringsmetode returnerer hver datastruktur imidlertid en model af et iterator -koncept (en simpel værditype, der kan afgøres for at hente den aktuelle værdi eller ændres til at pege på en anden værdi i sekvensen), og hver algoritme skrives i stedet generisk med argumenter fra sådanne iteratorer, f.eks. et par iteratorer, der peger på begyndelsen og slutningen af ​​undersekvensen eller området, der skal behandles. Således behøver kun N + M datastruktur-algoritme-kombinationer at blive implementeret. Flere iteratorkoncepter er specificeret i STL, hver en forfining af mere restriktive begreber, f.eks. Fremadgående iteratorer giver kun bevægelse til den næste værdi i en sekvens (f.eks. Egnet til en enkeltstående link eller en strøm af inputdata), hvorimod en tilfældig adgang iterator giver også direkte konstant-tid adgang til ethvert element i sekvensen (f.eks. egnet til en vektor). Et vigtigt punkt er, at en datastruktur vil returnere en model af det mest generelle koncept, der kan implementeres effektivt - krav til kompleksitetskrav er eksplicit en del af begrebsdefinitionen. Dette begrænser datastrukturer, en given algoritme kan anvendes på, og sådanne kompleksitetskrav er en vigtig faktor for valg af datastruktur. Generisk programmering er tilsvarende blevet anvendt i andre domæner, f.eks. Grafalgoritmer.

Bemærk, at selvom denne fremgangsmåde ofte anvender sprogfunktioner i generelitet/skabeloner til kompileringstid , er den faktisk uafhængig af særlige sprogtekniske detaljer. Generisk programmeringspioner Alexander Stepanov skrev,

Generisk programmering handler om at abstrahere og klassificere algoritmer og datastrukturer. Den henter sin inspiration fra Knuth og ikke fra typeteorien. Dets mål er trinvis konstruktion af systematiske kataloger over nyttige, effektive og abstrakte algoritmer og datastrukturer. Sådan en virksomhed er stadig en drøm.

-  Alexander Stepanov, STL's korte historie

Jeg mener, at iteratorteorier er lige så centrale for datalogi, som teorier om ringe eller banachrum er centrale for matematik.

-  Alexander Stepanov, et interview med A. Stepanov

Bjarne Stroustrup bemærkede,

Efter Stepanov kan vi definere generisk programmering uden at nævne sproglige funktioner: Løft algoritmer og datastrukturer fra konkrete eksempler til deres mest generelle og abstrakte form.

-  Bjarne Stroustrup, Evolving et sprog i og for den virkelige verden: C ++ 1991-2006

Andre programmeringsparadigmer, der er blevet beskrevet som generisk programmering, inkluderer Datatype generisk programmering som beskrevet i "Generisk programmering - en introduktion". Den Skrot din standardtekst tilgang er en letvægts generisk programmeringstilgang til Haskell.

I denne artikel skelner vi på højt niveau programmering paradigmer af generisk programmering , oven, fra de lavere niveau programmeringssprog typeparametrisering mekanismer , der anvendes til at gennemføre dem (se Programmering sprogstøtte til typeparametrisering ). For yderligere diskussion og sammenligning af generiske programmeringsparadigmer, se.

Understøttelse af programmeringssprog for genericitet

Genericitetsfaciliteter har eksisteret på sprog på højt niveau siden mindst 1970'erne på sprog som ML , CLU og Ada , og blev efterfølgende vedtaget af mange objektbaserede og objektorienterede sprog, herunder BETA , C ++ , D , Eiffel , Java , og DEC 's nu nedlagte Trellis-Owl sprog.

Genericitet implementeres og understøttes forskelligt i forskellige programmeringssprog; udtrykket "generisk" er også blevet brugt forskelligt i forskellige programmeringssammenhænge. For eksempel i Forth kan kompilatoren eksekvere kode under kompilering, og man kan oprette nye kompilatorsøgeord og nye implementeringer for disse ord i farten. Det har få ord, der afslører kompilatorens adfærd og derfor naturligvis tilbyder genericitetskapacitet , der dog ikke omtales som sådan i de fleste Forth -tekster. På samme måde tilbyder dynamisk indtastede sprog, især fortolkede, normalt genericitet som standard, da både videregivelse af værdier til funktioner og værditildeling er typeglade, og sådan adfærd ofte bruges til abstraktion eller kodetræthed, men dette betegnes typisk ikke som genericitet, da det er en direkte konsekvens af det dynamiske tastesystem, der bruges af sproget. Udtrykket er blevet brugt i funktionel programmering , specifikt på Haskell-lignende sprog, der bruger et strukturelt typesystem, hvor typer altid er parametriske, og den faktiske kode på disse typer er generisk. Disse anvendelser tjener stadig et lignende formål med kodelagring og gengivelse af en abstraktion.

Arrays og strukturer kan ses som foruddefinerede generiske typer. Hver brug af en matrix eller strukturtype instantiserer en ny betontype eller genbruger en tidligere instantieret type. Arrayelementtyper og structelementtyper er parametriserede typer, der bruges til at instantiere den tilsvarende generiske type. Alt dette er normalt indbygget i kompilatoren, og syntaksen adskiller sig fra andre generiske konstruktioner. Nogle udvidelige programmeringssprog forsøger at forene indbyggede og brugerdefinerede generiske typer.

En bred undersøgelse af genericitetsmekanismer i programmeringssprog følger. For en specifik undersøgelse, der sammenligner egnetheden af ​​mekanismer til generisk programmering, se.

I objektorienterede sprog

Når du opretter containerklasser på statisk typede sprog, er det ubelejligt at skrive specifikke implementeringer for hver indeholdt datatype, især hvis koden for hver datatype er praktisk talt identisk. For eksempel i C ++ kan denne kopiering af kode omgås ved at definere en klasseskabelon: 

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

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

Ovenstående Ter en pladsholder for den type, der er angivet, når listen oprettes. Disse "containere af type-T", der almindeligvis kaldes skabeloner , gør det muligt at genbruge en klasse med forskellige datatyper, så længe visse kontrakter som undertyper og signatur bevares. Denne genericitetsmekanisme bør ikke forveksles med inklusionspolymorfisme , som er den algoritmiske anvendelse af udskiftelige underklasser: for eksempel en liste over objekter af typen, der Moving_Objectindeholder objekter af typen Animalog Car. Skabeloner kan også bruges til typeuafhængige funktioner som i Swapeksemplet herunder: 

// "&" 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!".

Den C ++ templatekonstruktion, der bruges ovenfor, er bredt omtalt som den genericitetskonstruktion, der populariserede begrebet blandt programmører og sprogdesignere og understøtter mange generiske programmeringsformsprog. D-programmeringssproget tilbyder også fuldt ud generiske skabeloner baseret på C ++-præcedensen, men med en forenklet syntaks. Java -programmeringssproget har givet genericitetsfaciliteter syntaktisk baseret på C ++ 's siden introduktionen af J2SE 5.0.

C# 2.0, Oxygene 1.5 (også kendt som Chrome) og Visual Basic .NET 2005 har konstruktioner, der drager fordel af understøttelsen af ​​generika, der findes i Microsoft .NET Framework siden version 2.0.

Generics i Ada

Ada har haft generika siden den blev designet første gang i 1977–1980. Standardbiblioteket bruger generika til at levere mange tjenester. Ada 2005 tilføjer et omfattende generisk containerbibliotek til standardbiblioteket, som var inspireret af C ++ 's standardskabelonbibliotek .

En generisk enhed er en pakke eller et underprogram, der tager en eller flere generiske formelle parametre .

En generisk formel parameter er en værdi, en variabel, en konstant, en type, et underprogram eller endda en forekomst af en anden, udpeget, generisk enhed. For generiske formelle typer skelner syntaksen mellem diskrete, floating-point, fixed-point, access (pointer) typer osv. Nogle formelle parametre kan have standardværdier.

For at instantiere en generisk enhed, sender programmereren faktiske parametre for hver formel. Den generiske forekomst opfører sig derefter ligesom enhver anden enhed. Det er muligt at instantiere generiske enheder i løbetid , f.eks. Inde i en loop.

Eksempel

Specifikationen af ​​en generisk pakke: 

 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;

Instantiering af den generiske pakke: 

 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

Brug af en forekomst af en generisk pakke: 

 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;
Fordele og begrænsninger

Sprogsyntaksen tillader præcis specifikation af begrænsninger på generiske formelle parametre. For eksempel er det muligt at angive, at en generisk formel type kun accepterer en modulær type som den faktiske. Det er også muligt at udtrykke begrænsninger mellem generiske formelle parametre; for eksempel: 

 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;

I dette eksempel er Array_Type begrænset af både Index_Type og Element_Type. Ved installation af enheden skal programmereren passere en faktisk matchtype, der opfylder disse begrænsninger.

Ulempen ved denne finkornede kontrol er en kompliceret syntaks, men fordi alle generiske formelle parametre er fuldstændigt defineret i specifikationen, kan kompilatoren instantiere generika uden at se på generikkens krop.

I modsætning til C ++ tillader Ada ikke specialiserede generiske forekomster og kræver, at alle generika eksplicit instantieres. Disse regler har flere konsekvenser:

  • kompilatoren kan implementere delt generik : objektkoden for en generisk enhed kan deles mellem alle instanser (medmindre programmereren anmoder om inlining af underprogrammer, selvfølgelig). Som yderligere konsekvenser:
    • der er ingen mulighed for kodeopblødning (kodeopblødning er almindelig i C ++ og kræver særlig pleje, som forklaret nedenfor).
    • det er muligt at instantiere generika i løbetid såvel som på kompileringstidspunktet, da der ikke kræves nogen ny objektkode til en ny forekomst.
    • faktiske objekter, der svarer til et generisk formelt objekt, anses altid for at være ikke-statiske inde i det generiske; se Generiske formelle objekter i Wikibook for detaljer og konsekvenser.
  • alle tilfælde af at en generisk er nøjagtig den samme, er det lettere at gennemgå og forstå programmer skrevet af andre; der er ingen "særlige tilfælde" at tage højde for.
  • idet alle instantiationer er eksplicitte, er der ingen skjulte instantiationer, der kan gøre det svært at forstå programmet.
  • Ada tillader ikke "skabelonmetaprogrammering", fordi det ikke tillader specialiseringer.

Skabeloner i C ++

Hovedartikel: Skabelon (C ++)

C ++ bruger skabeloner til at aktivere generiske programmeringsteknikker. C ++ - standardbiblioteket indeholder standardskabelonbiblioteket eller STL, der indeholder en ramme med skabeloner til fælles datastrukturer og algoritmer. Skabeloner i C ++ kan også bruges til skabelonmetaprogrammering , hvilket er en måde at forhåndsevaluere noget af koden på kompileringstid frem for løbetid . Ved hjælp af skabelonspecialisering betragtes C ++ skabeloner som Turing fuldført .

Teknisk oversigt

Der er mange slags skabeloner, den mest almindelige er funktionsskabeloner og klasseskabeloner. En funktionsskabelon er et mønster til oprettelse af almindelige funktioner baseret på de parametreringstyper, der leveres, når de instantieres. For eksempel indeholder C ++ - standardskabelonbiblioteket den funktionsskabelon, max(x, y)der opretter funktioner, der returnerer enten x eller y, alt efter hvad der er størst. max()kan defineres sådan: 

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

Specialiseringer af denne funktionsskabelon, instantiering med bestemte typer, kan kaldes ligesom en almindelig funktion: 

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

Kompilatoren undersøger de argumenter, der bruges til at ringe til, maxog bestemmer, at dette er et opkald til max(int, int). Det instantierer derefter en version af funktionen, hvor parameteriseringstypen Ter int, hvilket svarer til følgende funktion: 

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

Dette virker, uanset om argumenterne xog yer heltal, strenge eller enhver anden type, som udtrykket x < yer fornuftigt eller mere specifikt for enhver type, som operator<er defineret. Fælles arv er ikke nødvendig for de typer typer, der kan bruges, og det ligner meget ænder -typning . Et program, der definerer en brugerdefineret datatype, kan bruge operatøroverbelastning til at definere betydningen af ​​den <pågældende type og dermed tillade dets brug med max()funktionsskabelonen. Selvom dette kan virke som en mindre fordel i dette isolerede eksempel, giver det i forbindelse med et omfattende bibliotek som STL programmereren mulighed for at få omfattende funktionalitet til en ny datatype, blot ved at definere et par operatører til det. Blot at definere <gør det muligt at bruge en type med standarden sort(), stable_sort()og binary_search()algoritmer eller at blive indsat i datastrukturer såsom sets, dynger og associerede arrays .

C ++ skabeloner er helt typesikre på kompileringstidspunktet. Som en demonstration complexdefinerer standardtypen ikke <operatøren, fordi der ikke er en streng rækkefølge på komplekse tal . Derfor max(x, y)vil det mislykkes med en kompileringsfejl, hvis x og y er complexværdier. På samme måde kan andre skabeloner, der er afhængige af, <ikke anvendes på complexdata, medmindre der findes en sammenligning (i form af en funktor eller funktion). F.eks .: A complexkan ikke bruges som nøgle til a, mapmedmindre der gives en sammenligning. Desværre genererer kompilatorer historisk noget esoteriske, lange og ubehjælpelige fejlmeddelelser for denne form for fejl. At sikre, at et bestemt objekt overholder en metodeprotokol, kan afhjælpe dette problem. Sprog, der bruger i comparestedet for, <kan også bruge complexværdier som nøgler.

En anden form for skabelon, en klasseskabelon, udvider det samme koncept til klasser. En klasseskabelons specialisering er en klasse. Klasseskabeloner bruges ofte til at lave generiske containere. STL har f.eks. En container med tilknyttet liste . For at lave en sammenkædet liste med heltal, skriver man list<int>. En liste med strenge er angivet list<string>. A listhar et sæt standardfunktioner forbundet med det, der fungerer for alle kompatible parametreringstyper.

Specialisering af skabeloner

En stærk funktion i C ++ 's skabeloner er skabelonspecialisering . Dette gør det muligt at tilvejebringe alternative implementeringer baseret på visse karakteristika for den parameteriserede type, der instantieres. Skabelonspecialisering har to formål: at tillade visse former for optimering og at reducere kodeopblæsning.

Overvej f.eks. En sort()skabelonfunktion. En af de primære aktiviteter, som en sådan funktion udfører, er at bytte eller udveksle værdierne i to af beholderens positioner. Hvis værdierne er store (hvad angår antallet af bytes, der skal til for at gemme hver af dem), er det ofte hurtigere at først oprette en separat liste over pointer til objekterne, sortere disse pointer og derefter bygge den endelige sorterede sekvens . Hvis værdierne er ganske små, er det dog normalt hurtigst at skifte værdierne på stedet efter behov. Hvis den parameteriserede type derudover allerede er af en visningstype, er det derfor ikke nødvendigt at opbygge et separat markør-array. Skabelonspecialisering gør det muligt for skabelonskaberen at skrive forskellige implementeringer og specificere de karakteristika, som den / de parametrerede type (r) skal have for hver implementering, der skal bruges.

I modsætning til funktionsskabeloner kan klasseskabeloner delvist specialiseres . Det betyder, at en alternativ version af klasseskabelonkoden kan leveres, når nogle af skabelonparametrene kendes, mens andre skabelonparametre efterlades generiske. Dette kan f.eks. Bruges til at oprette en standardimplementering (den primære specialisering ), der forudsætter, at kopiering af en parametreringstype er dyr og derefter opretter delspecialiseringer for typer, der er billige at kopiere, og dermed øger den samlede effektivitet. Kunder i en sådan klasseskabelon bruger bare specialiseringer i den uden at skulle vide, om kompilatoren brugte den primære specialisering eller en del specialisering i hvert enkelt tilfælde. Klasseskabeloner kan også være fuldt specialiserede, hvilket betyder, at der kan leveres en alternativ implementering, når alle parametreringstyperne er kendte.

Fordele og ulemper

Nogle anvendelser af skabeloner, såsom max()funktion, blev tidligere besat af funktion-lignende præprocessordirektiver makroer (en arv af sproget C programmering ). For eksempel er her en mulig implementering af en sådan makro: 

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

Makroer udvides (kopieres) af preprocessoren , før kompilering er korrekt; skabeloner er egentlige reelle funktioner. Makroer udvides altid inline; skabeloner kan også være inline -funktioner, når kompilatoren finder det passende.

Imidlertid betragtes skabeloner generelt som en forbedring i forhold til makroer til disse formål. Skabeloner er typesikre. Skabeloner undgår nogle af de almindelige fejl, der findes i kode, der gør stor brug af funktionslignende makroer, såsom at evaluere parametre med bivirkninger to gange. Måske vigtigst af alt, skabeloner blev designet til at være anvendelige på meget større problemer end makroer.

Der er fire primære ulemper ved anvendelsen af skabeloner: understøttede funktioner, compiler støtte, dårlige fejlmeddelelser (som regel med præ C ++ 20 SFINAE), og kode bloat :

  1. Skabeloner i C ++ mangler mange funktioner, hvilket gør det ofte umuligt at implementere dem og bruge dem på en ligetil måde. I stedet skal programmerere stole på komplicerede tricks, der fører til oppustethed, svært at forstå og svært at vedligeholde kode. Den nuværende udvikling i C ++ - standarderne forværrer dette problem ved at gøre stor brug af disse tricks og bygge en masse nye funktioner til skabeloner på dem eller med dem i tankerne.
  2. Mange kompilatorer havde historisk dårlig støtte til skabeloner, og derfor kunne brugen af ​​skabeloner have gjort koden noget mindre bærbar. Support kan også være dårlig, når en C ++-kompilator bruges med en linker , der ikke er C ++-bevidst, eller når man forsøger at bruge skabeloner på tværs af delte biblioteksgrænser .
  3. Kompilatorer kan producere forvirrende, lange og til tider ubehagelige fejlmeddelelser, når der opdages fejl i kode, der bruger SFINAE. Dette kan gøre skabeloner svære at udvikle med.
  4. Endelig kræver brugen af ​​skabeloner, at kompilatoren genererer en separat forekomst af den skabelonklasse eller funktion for hver permutation af typeparametre, der bruges med den. (Dette er nødvendigt, fordi typer i C ++ ikke alle har samme størrelse, og størrelserne på datafelter er vigtige for, hvordan klasser fungerer.) Så den vilkårlige brug af skabeloner kan føre til kodeopblødning , hvilket resulterer i alt for store eksekverbare filer. Men fornuftig brug af skabelonspecialisering og afledning kan drastisk reducere en sådan oppustethed i nogle tilfælde:

Så kan afledning bruges til at reducere problemet med replikering af kode, fordi der bruges skabeloner? Dette ville indebære at udlede en skabelon fra en almindelig klasse. Denne teknik viste sig at være en succes med at bremse kodeopblødning i reel brug. Folk, der ikke bruger en teknik som denne, har fundet ud af, at replikeret kode kan koste megabyte kodeplads, selv i programmer med moderat størrelse.

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

De ekstra instantiationer, der genereres af skabeloner, kan også få nogle fejlfindere til at have svært ved at arbejde yndefuldt med skabeloner. For eksempel kan indstilling af et debug -breakpoint i en skabelon fra en kildefil enten gå glip af at angive breakpointet i den faktiske ønskede instantiering eller angive et breakpoint på hvert sted, som skabelonen instantieres.

Implementeringskildekoden til skabelonen skal også være fuldstændig tilgængelig (f.eks. Inkluderet i et overskrift) for oversættelsesenheden (kildefil) ved hjælp af den. Skabeloner, herunder meget af standardbiblioteket, kan ikke kompileres, hvis de ikke er inkluderet i overskriftsfiler. (Dette er i modsætning til ikke-skabeloneret kode, som kan kompileres til binær, hvilket kun giver en deklarationsoverskriftsfil for kode, der bruger den.) Dette kan være en ulempe ved at afsløre implementeringskoden, som fjerner nogle abstraktioner og kan begrænse dens brug i projekter med lukket kilde.

Skabeloner i D

De D programmeringssprog understøtter skabeloner baseret på design på C ++. De fleste C ++ skabelonidiomer overføres til D uden ændringer, men D tilføjer yderligere funktionalitet:

  • Skabelonparametre i D er ikke begrænset til bare typer og primitive værdier (som det var i C ++ før C ++ 20), men tillader også vilkårlige kompileringstidsværdier (såsom strenge og strukturlitteraler) og aliasser til vilkårlige identifikatorer, herunder andre skabeloner eller skabeloninstitutioner.
  • Skabelonbegrænsninger og static ifsætningen giver et alternativ til henholdsvis C ++ 's C ++ begreber og if constexpr.
  • Det is(...)udtryk giver spekulative instantiering at verificere et objekts egenskaber påkompileringstidspunktet.
  • Den autosøgeord og typeofudtryk tillade typen inferens til variabel erklæringer og funktion returværdier, hvilket igen giver "Voldemort typer" (typer, der ikke har et globalt navn).

Skabeloner i D bruge en anden syntaks end i C ++: henviser i C ++ skabelonparametre er pakket ind i kantede parenteser ( Template<param1, param2>), D anvender en udråbstegn og parenteser: Template!(param1, param2). Dette undgår C ++ - analyseringsproblemer på grund af tvetydighed med sammenligningsoperatorer. Hvis der kun er en parameter, kan parenteserne udelades.

Traditionelt kombinerer D ovenstående funktioner for at tilvejebringe kompileringstidspolymorfisme ved hjælp af trækbaseret generisk programmering. For eksempel et input rækkevidde er defineret som enhver type, som opfylder de kontroller udført af isInputRange, som er defineret som følger: 

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
    }));
}

En funktion, der kun accepterer inputområder, kan derefter bruge ovenstående skabelon i en skabelonbegrænsning: 

auto fun(Range)(Range range)
    if (isInputRange!Range)
{
    // ...
}
Kodegenerering

Ud over skabelonmetaprogrammering giver D også flere funktioner for at muliggøre generering af kompileringstid:

  • Det importudtryk tillader at læse en fil fra disk og bruge dens indhold som en streng udtryk.
  • Reflektion af kompileringstid tillader optælling og inspektion af erklæringer og deres medlemmer under kompilering.
  • Brugerdefinerede attributter giver brugerne mulighed for at vedhæfte vilkårlige identifikatorer til erklæringer, som derefter kan opregnes ved hjælp af kompileringstid.
  • Compile-Time Function Execution (CTFE) gør det muligt at fortolke et delsæt af D (begrænset til sikre operationer) under kompilering.
  • String mixins gør det muligt at evaluere og kompilere indholdet af et strengudtryk som D -kode, der bliver en del af programmet.

Kombination af ovenstående tillader generering af kode baseret på eksisterende erklæringer. For eksempel kan D -serialiseringsrammer opregne en types medlemmer og generere specialiserede funktioner for hver serialiseret type til at udføre serialisering og deserialisering. Brugerdefinerede attributter kan yderligere angive serialiseringsregler.

Udførelsen af importekspressions- og kompileringstidens funktionsudførelse tillader også effektiv implementering af domænespecifikke sprog . For eksempel, givet en funktion, der tager en streng, der indeholder en HTML -skabelon og returnerer tilsvarende D -kildekode, er det muligt at bruge den på følgende måde: 

// 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);

Genericitet i Eiffel

Generiske klasser har været en del af Eiffel siden den oprindelige metode og sprogdesign. Eiffels grundpublikationer bruger udtrykket genericitet til at beskrive oprettelse og brug af generiske klasser.

Grundlæggende/ubegrænset genericitet

Generiske klasser erklæres med deres klassens navn og en liste over en eller flere formelle generiske parametre . I den følgende kode har klassen LISTen formel generisk parameterG 

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

De formelle generiske parametre er pladsholdere for vilkårlige klassenavne, der vil blive leveret, når der afgives en deklaration af den generiske klasse, som vist i de to generiske afledninger herunder, hvor ACCOUNTog DEPOSITer andre klasse navne. ACCOUNTog DEPOSITbetragtes som faktiske generiske parametre, da de giver rigtige klassenavne til erstatning for Gfaktisk brug. 

    list_of_accounts: LIST [ACCOUNT]
            -- Account list

    list_of_deposits: LIST [DEPOSIT]
            -- Deposit list

Inden for Eiffeltypesystemet, selvom klassen LIST [G]betragtes som en klasse, betragtes den ikke som en type. Imidlertid betragtes en generisk afledning af en LIST [G]sådan som LIST [ACCOUNT]en type.

Begrænset genericitet

For listeklassen vist ovenfor kan en faktisk generisk parameter, der erstatter, Gvære enhver anden tilgængelig klasse. For at begrænse det sæt klasser, hvorfra gyldige faktiske generiske parametre kan vælges, kan der angives en generisk begrænsning . I SORTED_LISTklasseerklæringen foreskriver den generiske begrænsning, at enhver gyldig faktisk generisk parameter vil være en klasse, der arver fra klassen COMPARABLE. Den generiske begrænsning sikrer, at elementer i en SORTED_LISTfaktisk kan sorteres. 

class
    SORTED_LIST [G -> COMPARABLE]

Generikere i Java

Hovedartikel: Generics i Java

Understøttelse af generikken eller "containere af type-T" blev tilføjet til programmeringssproget Java i 2004 som en del af J2SE 5.0. I Java kontrolleres generikerne kun ved kompileringstidspunktet for korrekthed af typen. Den generiske typeinformation fjernes derefter via en proces kaldet typesletning , for at opretholde kompatibilitet med gamle JVM -implementeringer, hvilket gør den utilgængelig under runtime. For eksempel List<String>konverteres a til råtypen List. Kompilatoren indsætter typekast for at konvertere elementerne til Stringtypen, når de hentes fra listen, hvilket reducerer ydeevnen i forhold til andre implementeringer, f.eks. C ++ - skabeloner.

Genericitet i .NET [C#, VB.NET]

Generics blev tilføjet som en del af .NET Framework 2.0 i november 2005, baseret på en forskningsprototype fra Microsoft Research, der startede i 1999. Selvom .NET generics ikke ligner generika i Java, anvender det ikke sletning af typer , men implementerer generics som en førsteklasses mekanisme i løbetiden ved hjælp af reification . Dette designvalg giver yderligere funktionalitet, såsom at tillade refleksion med bevarelse af generiske typer, samt lindre nogle af begrænsningerne ved sletning (såsom at være ude af stand til at oprette generiske arrays). Dette betyder også, at der ikke er noget præstationshit fra runtime casts og normalt dyre boksningskonverteringer . Når primitive og værdityper bruges som generiske argumenter, får de specialiserede implementeringer, der muliggør effektive generiske samlinger og metoder. Som i C ++ og Java er indlejrede generiske typer såsom Dictionary <string, List <int>> gyldige typer, men frarådes dog for medlems signaturer i kodeanalysedesignregler.

.NET tillader seks varianter af generiske typebegrænsninger ved hjælp af wheresøgeordet, herunder begrænsning af generiske typer til at være værdityper, at være klasser, have konstruktører og implementere grænseflader. Nedenfor er et eksempel med en grænsefladebegrænsning: 

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;
    }
}

Den MakeAtLeast()metode tillader drift på arrays, med elementer af generiske type T. Metodens typebegrænsning angiver, at metoden kan anvendes på enhver type, Tder implementerer det generiske IComparable<T>interface. Dette sikrer en kompileringstid fejl, hvis metoden kaldes, hvis typen ikke understøtter sammenligning. Grænsefladen giver den generiske metode CompareTo(T).

Ovenstående metode kan også skrives uden generiske typer, blot ved hjælp af den ikke-generiske Arraytype. Men da arrays er modstridende , ville støbningen ikke være typesikker , og kompilatoren ville ikke være i stand til at finde visse mulige fejl, der ellers ville blive fanget ved brug af generiske typer. Derudover skulle metoden have adgang til matrixelementerne som objects i stedet og ville kræve casting for at sammenligne to elementer. (For værdityper som f.eks. Typer som intdette kræver en boksningskonvertering , selvom dette kan løses ved hjælp af Comparer<T>klassen, som det gøres i standardindsamlingsklasserne.)

En bemærkelsesværdig adfærd for statiske medlemmer i en generisk .NET-klasse er statisk medlemsinstansiering pr. Løbetidstype (se eksempel nedenfor). 

    //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);

Genericitet i Delphi

Delphis Object Pascal -dialekt erhvervede generika i Delphi 2007 -udgivelsen, først med den (nu afbrudte) .NET -kompilator, før den blev tilføjet til den oprindelige kode i Delphi 2009 -udgivelsen. Semantikken og mulighederne i Delphi generics er stort set modelleret efter dem, generiske havde i .NET 2.0, selvom implementeringen nødvendigvis er en ganske anden. Her er en mere eller mindre direkte oversættelse af det første C# -eksempel vist ovenfor: 

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.

Som med C#kan metoder såvel som hele typer have en eller flere typeparametre. I eksemplet er TArray en generisk type (defineret af sproget) og MakeAtLeast en generisk metode. De tilgængelige begrænsninger ligner meget de tilgængelige begrænsninger i C#: enhver værditype, enhver klasse, en bestemt klasse eller grænseflade og en klasse med en parameterløs konstruktør. Flere begrænsninger fungerer som en additiv forening.

Genericitet i Free Pascal

Gratis Pascal implementerede generik før Delphi, og med forskellige syntaxer og semantik. Siden FPC version 2.6.0 er syntaksen i Delphi-stil imidlertid tilgængelig, når du bruger sprogfunktionen {$ mode Delphi}. Således er Free Pascal -programmører i stand til at bruge generika i den stil, de foretrækker.

Eksempel på Delphi og 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.

Funktionelle sprog

Genericitet i Haskell

Den typen klasse mekanisme Haskell understøtter generisk programmering. Seks af de foruddefinerede typeklasser i Haskell (herunder Eqde typer, der kan sammenlignes for lighed, og Showde typer, hvis værdier kan gengives som strenge) har den særlige egenskab at understøtte afledte forekomster. Det betyder, at en programmør, der definerer en ny type, kan oplyse, at denne type skal være en forekomst af en af ​​disse specielle typeklasser uden at tilvejebringe implementeringer af klassemetoderne, som det normalt er nødvendigt, når deklarerer klasseforekomster. Alle de nødvendige metoder vil blive "afledt" - det vil sige konstrueret automatisk - baseret på typens struktur. For eksempel angiver den følgende erklæring af en type binære træer , at den skal være en forekomst af klasserne Eqog Show: 

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

Dette resulterer i, at en ligestillingsfunktion ( ==) og en strengrepræsentationsfunktion ( show) automatisk defineres for enhver form for formular, BinTree Tforudsat at den Tselv understøtter disse operationer.

Støtten til afledte forekomster af Eqog Showgør deres metoder ==og showgeneriske på en kvalitativt anderledes måde end parametrisk polymorfe funktioner: disse "funktioner" (mere præcist, typeindekserede familier af funktioner) kan anvendes på værdier af forskellige typer, og selvom de opfører sig forskelligt for hver argumenttype, lidt arbejde er nødvendigt for at tilføje understøttelse af en ny type. Ralf Hinze (2004) har vist, at en lignende effekt kan opnås for brugerdefinerede typeklasser ved hjælp af visse programmeringsteknikker. Andre forskere har foreslået tilgange til denne og andre former for genericitet i forbindelse med Haskell og udvidelser til Haskell (diskuteret nedenfor).

PolyP

PolyP var den første generiske programmeringssprogsudvidelse til Haskell . I PolyP kaldes generiske funktioner polytypiske . Sproget introducerer en særlig konstruktion, hvor sådanne polytypiske funktioner kan defineres via strukturel induktion over strukturen af ​​mønsterfunktoren i en almindelig datatype. Regelmæssige datatyper i PolyP er en delmængde af Haskell -datatyper. En almindelig datatype t skal være af slagsen * → * , og hvis a er det formelle typeargument i definitionen, skal alle rekursive opkald til t have formen ta . Disse begrænsninger udelukker datatyper af højere art samt indlejrede datatyper, hvor de rekursive opkald har en anden form. Fladfunktionen i PolyP er her givet som et eksempel: 

   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
Generisk Haskell

Generisk Haskell er en anden udvidelse til Haskell , udviklet ved Utrecht University i Holland . De udvidelser, den giver, er:

  • Typeindekserede værdier defineres som en værdi indekseret over de forskellige Haskell-type konstruktører (enhed, primitive typer, summer, produkter og brugerdefinerede type konstruktører). Derudover kan vi også specificere adfærden for en typeindekserede værdier for en bestemt konstruktør ved hjælp af konstruktortilfælde og genbruge en generisk definition i en anden ved hjælp af standardtilfælde .

Den resulterende typeindekserede værdi kan specialiseres til enhver type.

  • Kind-indekserede typer er typer indekseret over slags, defineret ved at angive et tilfælde for både * og k → k ' . Forekomster opnås ved at anvende den slagsindekserede type på en slags.
  • Generiske definitioner kan bruges ved at anvende dem på en type eller slags. Dette kaldes generisk applikation . Resultatet er en type eller værdi, afhængigt af hvilken slags generisk definition der anvendes.
  • Generisk abstraktion gør det muligt at definere generiske definitioner ved at abstrahere en type parameter (af en given art).
  • Typeindekserede typer er typer, der er indekseret over typekonstruktørerne. Disse kan bruges til at give typer til mere involverede generiske værdier. De resulterende typeindekserede typer kan specialiseres til enhver type.

Som et eksempel er ligestillingsfunktionen i 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 |} = (==)

Ren

Clean tilbyder generisk programmeringsbaseret PolyP og den generiske Haskell som understøttet af GHC> = 6.0. Det parametrerer efter slags som dem, men tilbyder overbelastning.

Andre sprog

Sprog i ML -familien understøtter generisk programmering gennem parametrisk polymorfisme og generiske moduler kaldet functors. Både Standard ML og OCaml giver funktioner, der ligner klasseskabeloner og Adas generiske pakker. Scheme syntaktiske abstraktioner har også en forbindelse til typeparametrisering - disse er i virkeligheden en overordnet C ++ templates.

Et Verilog -modul kan have en eller flere parametre, som deres faktiske værdier tildeles ved modulets instantiering. Et eksempel er en generisk registermatrix, hvor matrixbredden er givet via en parameter. Et sådant array, kombineret med en generisk trådvektor, kan lave en generisk buffer eller hukommelsesmodul med en vilkårlig bitbredde ud af en enkelt modulimplementering.

VHDL , der stammer fra Ada, har også generiske muligheder.

C understøtter "typegeneriske udtryk" ved hjælp af søgeordet: _Generic

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

Se også

Referencer

Kilder

Yderligere læsning

eksterne links

C ++/D
C#/. NET
Delphi/Object Pascal
Eiffel
Haskell
Java