Polimorfism (informatica)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 25 martie 2021; verificările necesită 11 modificări .

Polimorfismul în limbaje de programare și teoria tipurilor  este capacitatea unei funcții de a procesa date de diferite tipuri [1] [2] [3] .

Există mai multe tipuri de polimorfism. Două dintre ele fundamental diferite au fost descrise de Christopher Strachey în 1967 : acestea sunt polimorfismul parametric și polimorfismul ad-hoc , alte forme sunt subspeciile sau combinațiile lor. Polimorfismul parametric este adevărat deoarece implică executarea aceluiași cod pentru toate tipurile de argument valide, iar polimorfismul ad-hoc este imaginar, deoarece este de a asigura uniformitatea cosmetică a unui cod executabil potențial diferit pentru fiecare tip particular de argument [1] [4] . În același timp, există situații în care este necesar să se folosească polimorfismul exact ad-hoc, și nu parametric [5] . Teoria tipurilor calificate combină toate tipurile de polimorfism într-un singur model.

Există o definiție larg răspândită a polimorfismului atribuită lui Björn Stroustrup : „ o interfață (ca o listă de declarații) - multe implementări (definiții asociate acestor declarații) ” [6] , dar numai polimorfismul ad-hoc (polimorfismul imaginar) se încadrează în acest sens. definiție.

Informații generale

Posibilitatea fundamentală pentru același cod de a procesa date de diferite tipuri este determinată de proprietățile sistemului de tip al limbajului . Din acest punct de vedere, se distinge [7] tastarea statică nepolimorfă (descendenții lui Algol și BCPL ), tastarea dinamică (descendenții lui Lisp , Smalltalk , APL ) și tastarea polimorfă statică (descendenții lui ML ). Utilizarea polimorfismului ad-hoc este cea mai caracteristică tastării nepolimorfe. Polimorfismul parametric și tiparea dinamică măresc reutilizarea codului mult mai mult decât polimorfismul ad-hoc, deoarece o funcție definită odată implementează comportamentul specificat fără duplicare pentru un număr infinit de tipuri nou definite care îndeplinesc condițiile cerute în funcție. Pe de altă parte, uneori devine necesar să se furnizeze un comportament diferit al funcției în funcție de tipul parametrului și atunci este necesar un polimorfism special.

Polimorfismul parametric este sinonim cu abstractizarea tipului [8] . Este omniprezent în programarea funcțională , unde este de obicei denumit pur și simplu „polimorfism”.

În comunitatea de programare orientată pe obiecte , termenul „polimorfism” înseamnă de obicei moștenire , iar utilizarea polimorfismului parametric se numește programare generică [9] , sau uneori „polimorfism static”.

Clasificare

Pentru prima dată, clasificarea varietăților de polimorfism a fost realizată de Christopher Strachey .

Dacă exact un tip este asociat unui parametru de funcție, atunci o astfel de funcție se numește monomorfă. Multe limbaje de programare oferă un mecanism sintactic pentru atribuirea unui singur nume (identificator) mai multor funcții monomorfe. În acest caz, în codul sursă devine posibilă apelarea unei funcții cu parametri reali de diferite tipuri, dar în codul compilat sunt de fapt apelate diferite funcții (vezi procedura și supraîncărcarea funcției ). Strachey a numit această posibilitate „polimorfism ad-hoc”.

Dacă mai mult de un tip este asociat unui parametru de funcție, atunci o astfel de funcție se numește polimorfă . Desigur, cu fiecare valoare actuală poate fi asociat un singur tip, dar o funcție polimorfă ia în considerare parametrii bazați pe proprietăți externe, nu pe propria organizare și conținut. Strachey a numit această posibilitate „polimorfism parametric”.

Ulterior, clasificarea a fost rafinată de Luca Cardelli [10] , evidențiind patru tipuri de polimorfism:

În unele lucrări, polimorfismul parametric, ad-hoc și subtip se disting ca trei clase independente de polimorfism [11] .

Dualitatea semnificației termenului „ad hoc” (pe de o parte – „spontan, prost conceput, făcut cu ocazie”, pe de altă parte – „special, amenajat special pentru un scop dat sau o ocazie dată”) a fost meritat de mulți ani [5] . Strachey a ales acest termen pe baza primului sens, subliniind că, cu polimorfismul ad-hoc, nu există o modalitate sistematică unică de a deduce tipul rezultatului din tipul argumentelor și, deși este posibil să se construiască un anumit set de reguli pentru restrânge spectrul de căutare, aceste reguli sunt de natură spontană, atât în ​​conținut, cât și în contextul aplicării [1] .

Într-adevăr, polimorfismul ad-hoc nu este un polimorfism adevărat [12] . Supraîncărcarea funcției nu dă „valoare având mai multe tipuri”, ci „caracter având mai multe tipuri ”, dar valorile identificate de acel simbol sunt de tipuri diferite (potențial incompatibile). De asemenea, turnarea nu este un polimorfism adevărat: operatorul pare să accepte valori de mai multe tipuri, dar valorile trebuie convertite într-o anumită reprezentare înainte de a le putea folosi, astfel încât operatorul operează de fapt pe un singur tip (adică, are un singur tip). Mai mult, tipul valorii returnate aici nu depinde de tipul parametrului de intrare , ca în cazul polimorfismului parametric.

Cu toate acestea, definirea implementărilor de funcții specifice pentru diferite tipuri este în unele cazuri o necesitate, nu un accident. Exemple clasice sunt implementarea operațiilor aritmetice (diferite din punct de vedere fizic pentru numere întregi și numere în virgulă mobilă ) și egalitatea de tipuri, care timp de decenii nu a avut o formalizare universală acceptată. Soluția au fost clasele de tip , care sunt un mecanism de enumerare discretă explicită a valorilor permise ale variabilelor de tip pentru dispecerare statică în stratul de tip. Ele reunesc cele două varietăți de polimorfism separate de Strachey, „ făcând polimorfismul ad-hoc mai puțin ad-hoc ” [5] ( jucând pe dualitate). Generalizarea ulterioară a claselor de tip a condus la construirea unei teorii a tipurilor calificate , care formalizează uniform cele mai exotice sisteme de tip, inclusiv notații extensibile și subtipuri.

Spre deosebire de supraîncărcare și turnare de tip , polimorfismul de subtip este polimorfism adevărat: obiectele de subtip pot fi manipulate uniform ca și cum ar aparține supertipurilor lor (dar acest lucru nu este valabil pentru limbajele care implementează „polimorfismul prin moștenire” prin turnare ). supraîncărcarea tipurilor și a funcțiilor , ca în cazul C++ ). Cel mai pur este polimorfismul parametric : același obiect sau funcție poate fi utilizat uniform în diferite contexte de tastare, fără modificări, translații sau orice alte verificări sau conversii în timpul execuției. Totuși, aceasta necesită o reprezentare uniformă a datelor (de exemplu, prin pointeri ) [4] .

Tipuri de bază de polimorfism

Polimorfism ad-hoc

Polimorfismul ad-hoc (tradus cel mai adesea în literatura rusă ca „polimorfism special” sau „polimorfism specializat”, deși ambele opțiuni nu sunt întotdeauna adevărate ) este acceptat în multe limbi prin supraîncărcare de funcții și metode și în scris slab cele  si prin turnare tip .

În exemplul următor ( limbajul Pascal ), funcțiile Addarată ca și cum ar implementa aceeași funcționalitate pe tipuri diferite, dar compilatorul le definește ca două funcții complet diferite.

program Adhoc ; function Add ( x , y : Integer ) : Integer ; începe Adaugă := x + y final ; function Add ( s , t : String ) : String ; begin Adaugă := Concat ( s , t ) end ; începe Writeln ( Adaugă ( 1 , 2 )) ; Writeln ( Adăugați ( „Bună ziua, „ , „Lumea!” )) ; sfârşitul .

În limbile cu tastare dinamică, situația poate fi mai complicată, deoarece alegerea funcției necesare de apelat se poate face doar în timpul execuției.

Supraîncărcarea  este un mecanism sintactic care permite apelarea diferitelor funcții printr-un singur identificator [13] . Castingul de tip  este un mecanism semantic realizat pentru a converti tipul real al unui argument în tipul așteptat al unei funcții, fără de care ar apărea o eroare de tip . Adică, atunci când o funcție este apelată cu un tip cast, se execută cod diferit pentru diferite tipuri (precedând apelul funcției în sine) [13] .

Polimorfism parametric

Polimorfismul parametric permite ca o funcție sau un tip de date să fie definit generic, astfel încât valorile să fie tratate identic, indiferent de tipul lor. O funcție polimorfă parametric folosește mai degrabă argumente bazate pe comportament decât pe cele bazate pe valori, accesând doar proprietățile argumentelor de care are nevoie, făcând-o utilizabilă în orice context în care tipul de obiect satisface cerințele comportamentale date.

Sistemele de tip avansat (cum ar fi sistemul Hindley-Milner ) oferă mecanisme pentru definirea tipurilor polimorfe , făcând utilizarea funcțiilor polimorfe mai convenabilă și oferind siguranță de tip static . Astfel de sisteme sunt sisteme de tip de ordinul doi, adăugând la sistemele de tip de ordinul întâi (utilizate în majoritatea limbajelor procedurale ) parametrizarea tipului (prin intermediul unei variabile de tip ) și abstracția tipului (prin intermediul cuantificării existențiale asupra lor). În sistemele de tip de ordinul doi, nu este nevoie imediată de a accepta tipurile primitive , deoarece acestea pot fi exprimate prin mijloace mai avansate. [paisprezece]

Exemplul clasic de tip polimorf este o listă de elemente de tip arbitrar, pentru care multe limbaje tip Hindley-Milner (cele mai multe limbaje de programare funcționale tipizate static ) oferă zahăr sintactic . Următorul exemplu demonstrează definiția unui nou tip algebric „ listă parametric polimorfă ” și două funcții pe acesta:

date Lista a = Nil | Contra a ( Lista a ) lungime :: Lista a -> lungime intreg Nil = 0 lungime ( Cons x xs ) = 1 + lungime xs harta :: ( a -> b ) -> Lista a -> Lista b harta f Nil = Nil harta f ( Cons x xs ) = Cons ( f x ) ( harta f xs )

Când înlocuiți tipuri de beton într-o variabilă de tip și așa mai departe, se vor construi tipuri de beton, respectiv și așa mai departe. Aceste tipuri particulare pot fi, la rândul lor, substituite în acea variabilă de tip din nou , producând tipuri și așa mai departe. În acest caz, pentru toate obiectele de toate tipurile construite, se va folosi aceeași implementare fizică a funcțiilor și . aIntStringList IntList StringList List StringList (Int, List String)lengthmap

Forme limitate de polimorfism parametric sunt, de asemenea, disponibile în unele limbaje de programare imperative (în special orientate pe obiecte ), unde termenul „ programare generică ” este folosit în mod obișnuit pentru a se referi la acesta. În special, în C, polimorfismul parametric netipizat este oferit în mod tradițional prin utilizarea unui pointer void* netipizat , deși este posibilă și o formă tipizată. Utilizarea șabloanelor C++ este superficial similară cu polimorfismul parametric, dar implementată semantic printr-o combinație de mecanisme ad-hoc; în comunitatea C++ se numește „polimorfism static” (spre deosebire de „polimorfism dinamic” ).

Parametricitate

Formalizarea polimorfismului parametric conduce la conceptul de parametricitate , care constă în capacitatea de a prezice comportamentul programelor privind numai tipurile acestora. De exemplu, dacă o funcție este de tipul " forall a. a -> a", atunci fără niciun mijloc extern care să completeze limbajul , se poate dovedi că poate fi doar identică . Prin urmare, parametricitatea este adesea însoțită de sloganul „teoreme gratis” ( ing.  teoreme gratis ). [15] [16] [17]

O consecință importantă a  acestui lucru este și independența de reprezentare , ceea ce înseamnă că funcțiile peste un tip abstract sunt insensibile la structura acestuia, iar implementările diferite de acest tip se pot înlocui liber între ele (chiar și în cadrul aceluiași program) fără a afecta comportamentul acestor funcții. [18] .

Cele mai avansate sisteme polimorfe parametric (punctul cel mai înalt din cubul lambda ) duc ideea de parametrizare până la punctul de a putea demonstra pe deplin corectitudinea programelor: permit să fie scrise programe care sunt corecte prin proiectare, astfel încât trecerea o verificare a coerenței tipului în sine garantează că comportamentul programului este corect.așteptată [19] .

Polimorfismul de înregistrare și variantă

O problemă separată este extinderea polimorfismului parametric la tipurile agregate: produse discriminate de tipuri (numite în mod tradițional înregistrări ) și sume discriminate de tipuri (cunoscute și ca tipuri de variante ). Diverse „ calcul de înregistrare ” ( în engleză  record calculi ) servesc ca bază formală pentru programarea orientată pe obiecte și modulară [20] .

val r = { a = 1 , b = adevărat , c = "bună ziua" } val { a = n , ... = r1 } = r val r2 = { d = 3,14 , ... = r1 }

O elipsă înseamnă un anumit număr de câmpuri tastate, adică o abstractizare a codului din anumite tipuri de înregistrări care ar putea fi procesate aici (și „lungimea” acestei serii poate varia și ea). Compilarea accesului polimorf la câmpuri care pot fi plasate într-o ordine diferită în diferite înregistrări este o problemă dificilă, atât din punct de vedere al controlului securității operațiunilor la nivel de limbă, cât și din punct de vedere al performanței la codul mașinii. nivel. O soluție naivă ar putea fi să căutați în mod dinamic dicționarul la fiecare apel (și limbajele de scripting îl folosesc), dar acest lucru este evident extrem de ineficient. Această problemă a fost studiată activ de câteva decenii; au fost construite multe modele teoretice și sisteme practice bazate pe acestea, care diferă în puterea expresivă și complexitatea metateoretică. Cele mai importante realizări în acest domeniu sunt polimorfismul în linie propus de Mitchell Wand și calculul de înregistrare polimorfă construit de Atsushi Ohori .  Un model mai comun, dar rămas în urmă în multe caracteristici, este subtiparea înregistrărilor .  

Suportul pentru polimorfismul de înregistrare într-o formă sau alta poate deschide posibilități într-un limbaj polimorf, cum ar fi mesajele de ordin superior (cea mai puternică formă de programare orientată pe obiecte ), încorporarea fără întreruperi a operațiunilor pe elementele bazei de date ( SQL ) în cod de limbaj de uz general și altele, până la programare extensibilă (adică programare liberă de problema expresiei ), garantând absența excepțiilor necontrolate în programe și anumite forme de metaprogramare .

Polimorfismul subtipului

Polimorfismul de includere esteo formalizare generalizată a subtipării și a moștenirii [21] . Aceste concepte nu trebuie confundate: subtipurile definesc relațiile la nivel de interfață, în timp ce moștenirea definește relațiile la nivelul implementării [22] .

Subtiparea ( subtiparea ) , sau polimorfismul subtipului ( polimorfismul subtipului ), înseamnă că comportamentul unei funcții polimorfe parametric este limitat la un set de tipuri mărginite într-o ierarhie supertip-subtip [23] [10] [24] . De exemplu, dacă există tipuri , și , limitate de relații și , atunci o funcție definită pe type , va putea, de asemenea, să accepte argumente de tipuri sau , iar comportamentul său va fi identic. Tipul real al unui obiect poate fi ascuns ca o „cutie neagră” și furnizat numai la cererea de identificare a obiectului. De fapt, dacă un tip este abstract, atunci un obiect concret de acel tip nici măcar nu poate exista (vezi abstract class , dar nu trebuie confundat cu tipul de date abstract ). Această ierarhie a tipurilor este cunoscută (mai ales în contextul limbajului Scheme ) ca turnul de numere , și de obicei conține mai multe tipuri. NumberRationalIntegerNumber :> RationalNumber :> IntegerNumberIntegerRationalNumber

Ideea de subtipare este motivată de creșterea setului de tipuri care pot fi gestionate de funcții deja scrise și, prin urmare, creșterea ratei de reutilizare a codului în cazul tastării puternice (adică, creșterea setului de programe tipizate ). Acest lucru este prevăzut de regula de subsumare : „ dacă o expresie eaparține unui tip t'într-un context de tastare Гși este adevărată t'<:t, atunci eaparține și tipuluit ” [25] [26] .

Relațiile de subtipare sunt posibile o mare varietate de categorii de tip: tipuri primitive ( ca Integer <: Number), tipuri de sumă , tipuri de produse , tipuri funcționale etc. subtipări [27] : el a numit genul tuturor subtipurilor sale drept tipul de putere al tipului [ 28 ] .

Un loc aparte în informatică îl ocupă subtiparea pe înregistrări .

Subscriere pe înregistrări

Subtiparea înregistrărilor , cunoscută și sub denumirea de subsumare (  vezi principiul de substituție al lui Barbara Liskov ) , este cea mai comună justificare teoretică pentru programarea orientată pe obiecte (OOP) [29] [30] [24] [31] (dar nu singura - vezi # polimorfism de înregistrare și variantă ).

Martín Abadi și Luca Cardelli au formalizat subtiparea înregistrărilor prin cuantificare constrânsă peste tipuri polimorfe parametric [29] [30] ; în timp ce parametrul tip este setat implicit [32] .

La subtiparea înregistrărilor se disting două soiuri: în lățime și în adâncime.

Subtiparea lățimii implică adăugarea de noi câmpuri la o înregistrare . De exemplu:

tip Object = { vârstă: Int } tip Vehicul = { vârstă: Int; viteza: int} tip Bicicletă = { vârstă: Int; viteza: Int; angrenaj: Int; } typeMachine = { varsta: Int; combustibil: sfoară

Pe de o parte, se pot scrie relațiile de subtipizare Vehicle <: Object, Bike <: Vehicle(și deoarece subtiparea este tranzitivă , atunci și Bike <: Object) și Machine <: Object. Pe de altă parte , putem spune că types Vehicleși Bikeinclud (moștenesc) toate proprietățile tipului . (Aici, semantica structurală a sistemului de tip este implicată ) Machine Object

Deoarece un tip este adesea văzut intuitiv ca un set de valori, creșterea numărului de câmpuri dintr-un subtip poate fi contra-intuitivă din punctul de vedere al teoriei seturilor . În realitate, tipurile nu sunt seturi [33] , ele sunt menite să verifice comportamentul programelor, iar ideea de subtipări este că un subtip are cel puțin proprietățile supertipului său și, astfel, este capabil să-l emuleze cel puțin unde un obiect este de așteptat supertip [25] . Sau cu alte cuvinte: un supertip definește un set minim de proprietăți pentru un set de obiecte, iar apoi un tip care are aceste proprietăți și, eventual, altele, formează un submult al acestei mulțimi și, prin urmare, este subtipul său [30] .

Relațiile subtipurilor în ceea ce privește mulțimile sunt mai intuitive în cazul tipurilor de variante [34] :

tip Ziua = lun | mar | nunta | joi | vineri | sat | soare tip Workday = lun | mar | nunta | joi | vineri tip WeekEnd = sat | soare

Aici Workday <: Dayși WeekEnd <: Day.

Câmpurile de denumire vă permite să faceți abstracție din ordinea apariției lor în înregistrări (spre deosebire de tupluri ), ceea ce face posibilă construirea de grafice de moștenire aciclică direcționată arbitrar, formalizând moștenirea multiplă [34] :

tip Mașină = { vârstă: Int; viteza: Int; combustibil: sfoară

Acum Car <: Vehicleși în același timp Car <: Machine. De asemenea, este evident că Car <: Object(vezi moștenirea în formă de diamant ).

Subtiparea în profunzime înseamnă că tipurile de câmpuri de înregistrare pot fi înlocuite cu subtipurile lor:

tip Voyage = { veh: Vehicul; data: Ziua tip Sport = { veh: Bicicletă; data: Ziua tip Vacanță = { veh: Mașină; data: sfârșitul săptămânii }

Din definițiile de mai sus, putem deduce că Sports <: Voyageși Vacation <: Voyage.

Metode în subtipurile de înregistrare

Suportul deplin pentru programarea orientată pe obiect presupune includerea în numărul câmpurilor de înregistrare și a funcțiilor care procesează valorile tipurilor de înregistrări cărora le aparțin [29] [35] . Astfel de funcții sunt denumite în mod tradițional „ metode ”. Un model generalizat pentru legarea înregistrărilor la metode este matricea de expediere ; în practică, majoritatea limbilor îl descompun în vectori în rânduri sau coloane — respectiv, implementând fie o organizare bazată pe clasă, fie o organizare bazată pe metodă [36 ] . În același timp, ar trebui să se facă distincția între metodele de suprascriere în subtipuri ( suprascrierea metodei ) și funcțiile de subtipare ( subtiparea funcțională ). Suprascrierea metodelor nu le leagă cu relații de subtipare pe funcții, dar le permite să-și schimbe semnăturile de tip. În acest caz, sunt posibile trei opțiuni: redefinirea invariantă, covariantă și contravariantă , iar ultimele două folosesc subtiparea parametrilor lor [37] (pentru mai multe detalii, vezi covarianță și contravarianță ). Calculul Abadi-Cardelli [29] ia în considerare numai metode invariante , ceea ce este necesar pentru a dovedi securitatea .

Multe limbaje orientate pe obiecte oferă un mecanism încorporat pentru legarea funcțiilor în metode , implementând astfel o organizare a programelor bazată pe clasă. Limbile care tratează funcțiile ca obiecte de primă clasă și le tip (vezi funcții de primă clasă , tip funcțional  - a nu fi confundat cu tipul returnat al unei funcții ) permit organizarea arbitrară bazată pe metode, care permite proiectarea orientată pe obiecte fără sprijin direct din părțile laterale ale limbii [38] . Unele limbi (cum ar fi OCaml ) acceptă ambele.

Limbajele cu sisteme de tipuri bazate pe teoria formală a subtipării ( OCaml , proiectul ML succesor ) tratează sistemele obiect și sistemele de clasă în mod independent [39] [40] . Aceasta înseamnă că tipul de obiect este asociat în primul rând cu un obiect și numai atunci când este specificat în mod explicit tipul de obiect este asociat cu o anumită clasă. În acest caz, dispeceratul dinamic se realizează la nivel de obiect, ceea ce înseamnă că în astfel de limbaje, două obiecte aparținând aceleiași clase, în general, pot avea un set diferit de metode. Împreună cu semantica definită în mod formal a moștenirii multiple , aceasta oferă un suport cuprinzător imediat pentru mixin .

CLOS implementează întreaga matrice de dispecerare prin multimetode , adică metode dispecerate dinamic care sunt polimorfe în mai multe argumente simultan [41] .

Unele limbi folosesc soluții speciale ad-hoc]. De exemplu, sistemul de tip limbaj C++ prevede turnarea automată a tipului (adică este slab ), non-polimorfă , emulează subtiparea moștenirea manifestă cu semnături de metodă invariante și nu acceptă abstracția tipului (a nu se confunda cu ascundere de câmp ). Moștenirea în C++ este implementată printr-un set de mecanisme ad-hoc, cu toate acestea, utilizarea sa este numită „polimorfism” în comunitatea lingvistică (iar ascunderea câmpului este numită „abstracție” [42] ). Este posibil să se controleze graficul de moștenire: moștenirea în formă de romb în C++ se numește „ moștenire virtuală ” și este specificată printr-un atribut explicit ; în mod implicit, câmpurile moștenite sunt duplicate și accesate prin nume calificat. Utilizarea unui astfel de limbaj poate fi nesigură  - nu se poate garanta stabilitatea programelor [43] [37] (un limbaj este numit sigur dacă programele din el, care pot fi acceptate de compilator ca fiind bine formate, nu vor depăși niciodată comportamentul permis în dinamică [44] ). virtual

Subtipări de ordin superior

Sistemul este o extensie a Sistemului F (nereprezentat în cubul lambda ), care formalizează cuantificarea restrânsă peste operatori de tip , extinzând relațiile de subtipizare de la gen la tipuri de gen superior . Există mai multe versiuni ale sistemului , care diferă în puterea expresivă și complexitatea metateoretică, dar majoritatea ideilor principale au fost stabilite de Luca Cardelli [45] . *

O combinație de varietăți de polimorfism

Clasele de tip

O clasă de tip implementează un singur tabel independent de metode virtuale pentru multe tipuri ( cuantificate universal ). În acest fel, clasele de tip diferă de clasele din programarea orientată pe obiecte , unde fiecare obiect de orice tip ( restricted quantified ) este însoțit de un pointer către un tabel de metode virtuale [46] . Clasele de tipuri nu sunt tipuri, ci categorii de tipuri; instanțele lor nu sunt valori, ci tipuri.

De exemplu [46] :

clasa Num a unde ( + ), ( * ) :: a -> a -> a negate :: a -> a

Această declarație se citește astfel: „ Un tip aaparține unei clase Numdacă funcțiile și (+), cu semnăturile date(*)negate sunt definite pe ea ”.

instance Num Int unde ( + ) = addInt ( * ) = mulInt negate = negInt instanță Num Float unde ( + ) = addFloat ( * ) = mulFloat negate = negFloat

Prima declarație spune: „ Există funcții și semnături corespunzătoare (+), care sunt definite peste tipul(*)negateInt ”. A doua afirmație se citește în mod similar.

Acum puteți introduce corect următoarele funcții (și deducerea tipului este decidabilă ):

pătrat :: Num a => a -> a pătrat x = x * x pătrate3 :: Num a , Num b , Num c => ( a , b , c ) -> ( a , b , c ) pătrate3 ( x , y , z ) = ( pătrat x , pătrat y , pătrat z )

Deoarece operația de multiplicare este implementată fizic diferit pentru numerele întregi și cu virgulă mobilă , în absența claselor de tip, aici ar fi deja necesare două funcții supraîncărcatesquare și opt funcții supraîncărcatesquares3 , iar în programele reale cu structuri de date complexe, există mult mai mult cod duplicat. . În programarea orientată pe obiecte, problemele de acest fel sunt rezolvate prin dispecerare dinamică , cu overhead asociat. Clasa de tip trimite static, aducând polimorfisme parametrice și ad-hoc într-un singur model [5] . În ceea ce privește polimorfismul parametric, o clasă de tip are un parametru ( o variabilă de tip ) care acoperă un set de tipuri. Din punctul de vedere al polimorfismului ad-hoc, acest set nu este doar discret, ci și specificat explicit până la nivelul implementării. Mai simplu spus, semnătura înseamnă că funcția este polimorfă parametric , dar gama de tipuri ale parametrului său este limitată doar la acele tipuri care aparțin clasei de tip . Din acest motiv, funcția este tastata într-un mod unic, în ciuda apelului la funcția supraîncărcată din corpul său. square :: Num a => a -> aNum

Suportul nativ pentru clasele de tip a fost implementat pentru prima dată în Haskell , dar ele pot fi, de asemenea, introduse în orice limbaj polimorf din punct de vedere parametric prin preprocesare simplă [5] și, de asemenea, implementate idiomatic (vezi, de exemplu, limbajul modulului ML#Implementarea modelelor alternative ). Cu toate acestea, sprijinul direct poate facilita raționamentul automat despre semnificația programelor.

Tipurile de egalitate în Haskell sunt implementate ca instanțe ale unei clase de tipEq(generalizarea variabilelor de tip egalitate din Standard ML ) :

( == ) :: Eq a => a -> a -> Bool

Pentru a reduce problemele de a codifica unele dintre proprietățile adesea evidente necesare ale tipurilor definite de utilizator, Haskell oferă suplimentar zahăr sintactic  , un construct derivingcare este valabil pentru un set limitat de clase de tipuri standard (cum ar fi Eq). (În comunitatea vorbitoare de limbă rusă, utilizarea sa este adesea confundată cu conceptul de „ moștenire ”, datorită particularităților traducerii cuvântului „ derivare ”.)

Tipuri de date algebrice generice

Politipism

Termenul „politipism” sau „generalizare tip de date” este uneori folosit. În esență, politiparea se referă la suportul încorporat al limbajului pentru polimorfismul constructorului de tipuri , conceput pentru a unifica interfețele de programare și pentru a crește reutilizarea codului . Un exemplu de politipism este algoritmul generalizat de potrivire a modelelor [47] .

Prin definiție, într-o funcție de politip, „ deși poate exista un număr finit de ramuri ad-hoc pentru unele tipuri, nu există un combinator ad-hoc ” [48] .

Politiparea poate fi implementată prin utilizarea unui tip de date generic sau a unui polimorfism de rang superior . Extensia PolyP [49] a lui Haskell este un construct de sintaxă care simplifică definirea funcțiilor politip în Haskell .

O funcție de politipizare este într-un anumit sens mai generală decât o funcție polimorfă, dar, pe de altă parte, o funcție poate fi politipată și nu polimorfă, așa cum se poate vedea din următoarele semnături de tip de funcție :

head :: [ a ] ​​​​-> a ( + ) :: Num a => a -> a -> a length :: Regular d => d a -> Int sum :: Regular d => d Int -> Int

Prima funcție ( head) este polimorfă (parametric polimorfă ), a doua (operatorul infix „ ”) este supraîncărcată (ad-hoc-polimorfă), a treia și a patra sunt politipizate: variabila tip din definiția lor variază în funcție de tip constructori . În același timp, a treia funcție ( ) este politipată și polimorfă (se presupune că calculează „lungimea” pentru un set de tipuri de agregate polimorfe - de exemplu, numărul de elemente din liste și arbori ), iar a patra ( ) este politipat, dar nu polimorf (monomorfe peste tipuri de agregate aparținând clasei de tip , pentru care probabil calculează suma numerelor întregi care formează un obiect de un anumit tip de agregat). + dlengthsum Regular

Diverse

Limbile tipizate dinamic reprezintă în mod uniform varietăți de polimorfism, care formează o ideologie distinctivă în ele și afectează metodologiile aplicate de descompunere a sarcinilor. De exemplu, în Smalltalk , orice clasă este capabilă să primească mesaje de orice tip și fie să le proceseze pe cont propriu (inclusiv prin introspecție ), fie să o transmită către o altă clasă - astfel, orice metodă este polimorfă din punct de vedere parametric, în timp ce structura sa internă se poate ramifica în funcție de condiția tipului de argument dinamic, implementând polimorfism special. În CLOS , multimetodele sunt simultan funcții de primă clasă , ceea ce ne permite să le considerăm atât cuantificate limitat , cât și generalizate ( polimorfe adevărate ).

Limbile tipizate static polimorf , în schimb, pot implementa varietăți de polimorfism ortogonal (independent unul de celălalt), permițându-le să fie construite complex într -un mod sigur de tip . De exemplu, OCaml acceptă clase parametrice (asemănătoare ca capabilități cu șabloanele de clasă C++ , dar verificabile fără a fi nevoie de instanțiere), moștenirea lărgimii și adâncimii lor (inclusiv multiple ), implementarea idiomatică a claselor de tip (prin semnături - vezi un exemplu corespunzător de utilizare a limbajului modulului ML ), polimorfismul inline , polimorfismul parametric al rangurilor de peste 1 (prin intermediul așa-numitelor tipuri abstracte local care implementează tipuri existențiale ) și tipuri de date algebrice generalizate .

Istorie

Termenul „polimorfism” provine din limba greacă. πολύς („mult”) și μορφή („formă, aspect, dispozitiv”).

Termenii „polimorfism specializat” și „polimorfism parametric” sunt menționați pentru prima dată în 1967 în notele de curs ale lui Christopher Strachey intitulate „ Fundamentals of Programming Languages ​​​​[ ” [1] . În 1985, Peter Wegner și Luca Cardelli au formalizat polimorfismul de reținere pentru modelarea subtipurilor și a moștenirii [10] [27] , deși implementările de subtipuri și moștenire au apărut mult mai devreme, în limbajul Simula în 1967 . Polimorfismul de includere se bazează pe cuantificare restricționată .

Notarea polimorfismului parametric ca dezvoltare a calculului λ (numit sistem F ) a fost descrisă formal de către logicianul Jean-Yves Girard [50] [51] ( 1971 ), independent de el un sistem similar a fost descris de informaticianul John S. Reynolds [52 ] ( 1974 ).

Primul limbaj bazat în întregime pe λ-calcul polimorf a fost ML ( 1973 ); independent de el, tipurile parametrice au fost implementate în Clu ( 1974 ) [27] . Multe limbaje moderne ( C++ , Java , C# , D și altele) oferă tipuri parametrice într-o formă mai mult sau mai puțin apropiată de implementarea lor în Clu.

În 1987, Mitchel Wand a formalizat polimorfismul inline și inferența de tip pentru acesta [53] ; această lucrare a avut un impact imens asupra dezvoltării ulterioare a sistemelor de tip . În același an, Philip Wadler și Stephen Blott au propus clase de tip pentru a oficializa polimorfismul ad-hoc . 

Vezi și

Note

  1. ↑ 1 2 3 4 Strachey, 1967 .
  2. ↑ Cardelli, 1991 , p. 3.
  3. ↑ Pierce, 2012 , 22.7. Polimorfismul prin lat, p. 354.
  4. ↑ 1 2 Cardelli, 1985 , p. 6.
  5. ↑ 1 2 3 4 5 Wadler, 1988 , p. 1-2.
  6. ↑ Bjarne Stroustrup . Glosar C++ (19 februarie 2007). Arhivat din original pe 29 iunie 2018.
  7. ↑ Andrew W. Appel. O critică a ML standard . - Universitatea Princeton, 1992.
  8. ↑ Harper, 2012 , 20.1 System F, p. 172.
  9. ↑ Pierce, 2012 , 23.2 Varieties of polymorphism, p. 365.
  10. ↑ 1 2 3 Cardelli, 1985 .
  11. ↑ Mitchell, 2002 , 6.4. Polimorfism și supraîncărcare, p. 145-151.
  12. ↑ Cardelli, 1985 , 1.3. Tipuri de polimorfism, p. 6.
  13. ↑ 1 2 Cardelli, 1985 , p. 5-6.
  14. ↑ Cardelli, 1996 , 5 Sisteme de tip de ordinul al doilea, p. 25.
  15. ↑ Harper, 2012 , 20.3 Privire de ansamblu asupra parametrilor, p. 177.
  16. ↑ Harper, 2012 , 49 Parametricity, p. 495-508.
  17. ↑ Pierce, 2012 , 23.9 Parametricity, p. 384-385.
  18. ↑ Harper, 2012 , 21.4 Representation Independence, p. 188.
  19. ↑ Pierce, 2012 , 30.5 Going Further: Dependent Types, p. 489-493.
  20. ↑ Reynolds, 1998 , 16. Subtipuri și tipuri de intersecție. Note bibliografice, p. 376.
  21. ↑ Cardelli, 1985 .
  22. ↑ Mitchell, 2002 , 10.2.6 Moștenirea nu este subtiparea, p. 287.
  23. ↑ Cardelli, 1991 .
  24. ↑ 1 2 Pierce, 2012 , 15 Subtipuri, p. 193.
  25. ↑ 1 2 Pierce, 2012 , 15. Subtipuri, p. 193.
  26. ↑ Harper, 2012 , 23.1. Subsumarea, p. 208.
  27. ↑ 1 2 3 Pierce, 2012 , 1.4 Scurt istoric, p. 11-13.
  28. ↑ Cardelli, 1991 , 6. Genuri de putere, p. 32.
  29. ↑ 1 2 3 4 Abadi, Cardelli, 1994 .
  30. ↑ 1 2 3 Cardelli, 1985 , 6. Bounded Quantification, p. 28.
  31. ↑ Minsky tradus de DMK, 2014 , Subtyping, p. 259.
  32. ↑ Cardelli, 1985 , p. 9.
  33. ↑ Harper, 2012 , capitolul 16. Tipuri recursive, p. 132.
  34. ↑ 1 2 Cardelli, 1991 , p. 35-37.
  35. ↑ Cardelli, 1985 , 2.3. Tipuri de bază, tipuri structurate și recursivitate, p. 12-14.
  36. ↑ Harper, 2012 , capitolul 25. Dynamic Dispatch, p. 229.
  37. ↑ 1 2 Joyner, 1996 , 3.38 Signature Variance, p. 35.
  38. ↑ Programarea orientată pe obiecte în ML standard . Preluat la 11 martie 2016. Arhivat din original la 14 ianuarie 2016.
  39. ↑ Minsky tradus de DMK, 2014 , Capitolul 11. Obiecte, p. 253.
  40. ↑ Grupul de lucru ML2000. Principii și un proiect preliminar pentru ML2000 . — 1999.
  41. ↑ Castagna, Ghelli, Longo. Un calcul pentru funcții supraîncărcate cu subtipări  // Informații și calcul. - Presa academică, 1995. - T. 117 , nr. 1 . - S. 115-135 . - doi : 10.1006/inco.1995.1033 .
  42. ↑ Joyner, 1996 , 2.8 Encapsulation, p. opt.
  43. ↑ Mitchell, 2002 , 6.2.1 Tip Safety, p. 132-133.
  44. ↑ Harper, 2012 , Capitolul 4. Statica, p. 35.
  45. ↑ Pierce, 2012 , 31. Subtipuri de ordin superior, p. 495.
  46. ↑ 12 Wadler , 1988 , p. 3.
  47. ↑ Johan Jeuring. Potrivirea modelului politipic  // FPCA. - 1995. - doi : 10.1.1.36.5645 .
  48. ↑ Ralf Lammel și Joost Visser, „Typed Combinators for Generic Traversal”, în Practical Aspects of Declarative Languages: 4th International Symposium (2002), p. 153.
  49. ↑ Patrik Jansson, Johan Jeuring. PolyP - O extensie a limbajului de programare politipic . — Sigplan SPPL, 1997.
  50. ↑ Girard - Extensia teoriei tipurilor, 1971 .
  51. ↑ Girard - Calcul de ordin superior, 1972 .
  52. ↑ Reynolds, 1974 .
  53. ↑ Bagheta, 1987 .

Literatură

  • Christopher Strachey. Concepte fundamentale în  limbaje de programare . - 1967. Arhivat la 12 august 2017.
    • Republicat: Christopher Strachey. Concepte fundamentale în limbaje de programare  // Calcul de ordin superior și simbolic  . - 2000. - Vol. 13 . - P. 11-49 . - doi : 10.1023/A:1010000313106 .
  • Jean-Yves Girard. Une Extension de l'Interpretation de Gödel à l'Analyse, et son Application à l'Élimination des Coupures dans l'Analyse et la Théorie des Types  (franceză)  // Proceedings of the Second Scandinavian Logic Symposium. - Amsterdam, 1971. - P. 63-92 . - doi : 10.1016/S0049-237X(08)70843-7 .
  • Jean-Yves Girard. Interprétation fonctionnelle et elimination des coupures de l'arithmétique d'ordre supérieur  (franceză) . - Universitatea Paris 7, 1972.
  • John C. Reynolds. Către o teorie a structurii tipului // Note de curs în informatică . - Paris: Colloque sur la programmation, 1974. - Vol. 19 . - S. 408-425 . - doi : 10.1007/3-540-06859-7_148 .
  • Luca Cardelli , Peter Wegner. Despre înțelegerea tipurilor, abstracției datelor și polimorfismului //ACM Computing Surveys. - New York, SUA:ACM, 1985. -17,nr. 4. -S. 471-523. —ISSN 0360-0300. -doi:10.1145/6041.6042.
  • Robert Harper . Introducere în Standard ML. - Universitatea Carnegie Mellon, 1986. - ISBN PA 15213-3891.
  • Traducere în rusă: Robert Harper . Introducere în Standard ML. - Universitatea Carnegie Mellon, 1986. - 97 p. — ISBN PA 15213-3891.
  • Mitchell Wand . Inferență completă de tip pentru obiecte simple // În Proc. Al 2-lea simpozion IEEE privind logica în informatică. - 1987. -P. 37-44.
  • Philip Wadler, Stephen Blott. Cum să faci polimorfismul ad-hoc mai puțin ad -hoc  . — 1988.
  • Luca Cardelli . Programare tipul // IFIP de ultimă generație. - New York: Springer-Verlag, 1991. -Iss. Descrierea formală a conceptelor de programare. -P. 431-507.
  • Martin Abadi, Luca Cardelli . O semantică a tipurilor de obiecte  . — LICS , 1994.
  • Luca Cardelli . Sisteme de tip (engleză) // Handbook of Computer Science and Engineering. — CRC Press, 1996.
  • Benjamin Pierce. Tipuri și limbaje de programare  . - MIT Press , 2002. - ISBN 0-262-16209-1 .
    • Traducere în rusă: Benjamin Pierce. Tipuri în limbaje de programare . - Dobrosvet , 2012. - 680 p. — ISBN 978-5-7913-0082-9 .
  • John C. Mitchell Concepte în limbaje de programare  . - Cambridge University Press, 2002. - 540 p. - ISBN 978-0-521-78098-8 .
  • Minsky, Madhavapeddy, Hickey. Lumea reală OCaml: Programare funcțională pentru  mase . - O'Reilly Media, 2013. - 510 p. — ISBN 9781449324766 .
    • Traducere în rusă: Minsky, Madhavapeddy, Hickey. Programare în limbajul OCaml . - DMK, 2014. - 536 p. — (Programare funcțională). - ISBN 978-5-97060-102-0 .