Variabilă de tip

O variabilă de tip ( variabilă de tip ) în limbaje de programare și teoria tipurilor  este o variabilă care poate lua o valoare dintr-un set de tipuri de date .

O variabilă de tip este utilizată într-o definiție de tip de date algebrică în același mod în care este utilizat un parametru într-o definiție de funcție , dar este folosită pentru a transmite un tip de date fără a transmite datele în sine. Caracterele grecești sunt folosite în mod tradițional ca identificatori pentru variabilele de tip în teoria tipurilor (deși multe limbaje de programare folosesc alfabetul latin și permit nume mai lungi).

Exemplu

În următoarea definiție a tipului polimorf „ listă ” din Standard ML , identificatorul 'a(pronunțat „alfa”) este o variabilă de tip [2] :

tipul de date 'a list = nil | :: of 'a * 'o list

Când se folosește acest tip polimorf , un tip specific este înlocuit în variabila tip, astfel încât în ​​program se pot forma multe tipuri monomorfe: string list, int list, int list listși așa mai departe. Cu această înlocuire, fiecare referință la o variabilă de tip este înlocuită cu același tip. Informațiile de tip rezultat sunt folosite pentru a verifica și optimiza programul, după care acesta este de obicei șters, astfel încât același cod țintă procesează obiecte de tipuri inițial diferite (dar există excepții de la această regulă, în special, în MLton ).

Dacă un tip polimorf este parametrizat de mai multe variabile de tip, atunci tipurile substituite în ele pot fi fie diferite, fie identice, dar se respectă regula de substituție. De exemplu, dacă acest tip este:

tipul de date ( 'a , 'b ) t = Single of 'a | Dublu de 'a * 'a | Perechea de 'a * 'b

instanțiază astfel:

tastați t_ir = ( int , real ) t

apoi Single(4), Double(4,5)și Pair(4,5.0)vor fi valori valide de tip t_ir, iar încercarea de a construi o valoare Single(5.0)va avea ca rezultat o eroare de tastare deoarece parametrul 'aare valoarea „ int”.

Legături și cuantificare

Sfera oricărei variabile de tip este legată de un context specific [3] [4] . În exemplul următor, identificatorul 'aeste utilizat independent în două semnături, ceea ce înseamnă că nu necesită egalitatea tipurilor efectiv inline între definiții:

val foo : 'a -> 'a val bar : 'a -> 'a

Acest lucru devine clar atunci când utilizați variabile de tip de legare explicită (limitare explicită sau limitare explicită ):

val foo : [ 'a ] 'a -> 'a val bar : [ 'a ] 'a -> 'a

O legare limitează sfera unei variabile de tip dat.

În dialectele clasice ale ML, legarea explicită a variabilelor de tip este o caracteristică opțională și majoritatea implementărilor nu sunt acceptate ca fiind inutile - legarea lor este implicită în deducția tipului , care devine posibilă datorită limitărilor versiunilor timpurii ale sistemului Hindley-Milner . În sistemul complet F , această declarație este scrisă ca . O astfel de notație se numește forma normală prenex . Litera mare din această intrare înseamnă funcția stratului de tip ( funcție la nivel de tip ), al cărui parametru este variabila de tip. După înlocuirea unui anumit tip în această variabilă, această funcție returnează o funcție monomorfă la nivel de valoare (funcție la nivel de valoare ). Un preex este o legare explicită a unei variabile de tip prefixate unei semnături de tip. Versiunile timpurii ale sistemului Hindley-Milner permiteau doar forma preex, adică necesitau ca o variabilă de tip să fie instanțiată cu o anumită valoare înainte de a fi necesar un apel de funcție. Această restricție se numește polimorfism preex  - nu numai că simplifică foarte mult mecanismul de potrivire a tipurilor , dar face și posibilă deducerea tuturor sau aproape a tuturor (în funcție de dialect) tipurile din program.

Cea mai simplă legare a variabilelor de tip se numește cuantificarea lor . Două cazuri ies în evidență:

  • acțiunea unei variabile de tip se extinde la întreaga definiție a tipului: ['a, 'b] 'a -> 'b -> 'a, matematic, un astfel de tip se scrie prin cuantificatorul universal - - de aceea o astfel de variabilă de tip se numește „cuantificată universal”, iar întregul tip se numește „polimorfă universală”;
  • efectul unei variabile de tip se extinde doar la o parte din definiția tipului: ['a] 'a -> (['b] 'b -> 'a), matematic, un astfel de tip se scrie prin cuantificatorul existențial - - de aceea o astfel de variabilă se numește „cuantificată existențial”, iar întregul tip se numește „existențial”.

Nu în toate cazurile, „transformarea” unui tip universal polimorf într-un tip existențial dă un tip practic sau diferențe notabile față de polimorfismul universal, dar în anumite cazuri, utilizarea tipurilor existențiale ridică polimorfismul parametric la un nivel de primă clasă , adică. permite ca funcțiile polimorfe să fie transmise fără legarea ca parametri la alte funcții (vezi polimorfismul de primă clasă ). Un exemplu clasic este implementarea listei eterogene (vezi wikibook). Adnotarea explicită a tipurilor în acest caz devine obligatorie, deoarece Inferența de tip pentru polimorfismul de deasupra rangului 2 este indecidabilă din punct de vedere algoritmic [5] .

În practică, tipurile universal polimorfe dau o generalizare a tipului de date , iar tipurile existențiale - abstracția tipului de date [6] .

Haskell distinge mai multe moduri (disponibile ca extensii de limbaj): modul Rank2Types permite doar unele forme de tipuri existențiale care deschid polimorfismul nu mai mare de rangul 2, pentru care inferența de tip este încă decidabilă; modul RankNTypes permite mutarea cuantificatorului universal ( forall a) în interiorul unor tipuri funcționale care fac parte din semnături mai complexe [7] , modul ImpredicativeTypes permite tipuri existențiale arbitrare [8] .

OCaml implementează suport pentru cuantificarea existențială printr-o soluție numită „tipuri abstracte local” [ 9 ] .

Specificația ML standard definește o cuantificare specială pentru unele operațiuni încorporate. Sintaxa sa nu este reglementată și diferă în implementările limbajului (cel mai adesea este pur și simplu ascunsă). De exemplu, semnătura operației de adăugare încorporată poate fi simplificată după cum urmează:

val + : [ int , cuvânt , real ] 'a * 'a -> 'a

Această semantică implementează o formă primitivă de polimorfism ad-hoc  - combinând mai multe operații de adunare fizic diferite sub un singur identificator " +". Dezvoltatorii OCaml au abandonat această soluție prin eliminarea completă a polimorfismului ad-hoc din limbaj ( tipurile de date algebrice generalizate au apărut în versiunile ulterioare ).

La sfârșitul anilor 1980, a apărut extensia Hindley-Milner , oferind capacitatea de a limita, dacă este necesar, intervalul de valori pentru orice variabilă de tip în tipuri nou definite - clase de tip . O clasă de tip restricționează mai strict contextele de tastare permise , permițând ca o variabilă de tip să fie instanțiată numai de tipuri care aparțin unei clase specificate în mod explicit.

Această extensie a fost implementată pentru prima dată la baza limbajului Haskell , de exemplu, operatorul de comparare a egalității are următoarea semnătură în el :

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

Proiectul limbajului de generație următoare - succesorul ML [1]  - refuză nevoia de inferență de tip , bazându-se pe adnotare de tip explicit (manifest) (inclusiv legarea explicită a variabilelor de tip), care oferă suport direct pentru sistemul complet F cu primul- polimorfismul de clasă și o serie de extensii, inclusiv ierarhii de subtipuri și tipuri existențiale [1] .

Variabile de tip special

Clasa principală de variabile de tip utilizate în toate limbile din familia ML sunt variabile de tip aplicativ care pot lua valori din setul de toate tipurile permise într-o anumită limbă. În dialectele clasice, ele sunt desemnate sintactic ca " 'a" (un identificator alfanumeric, începând întotdeauna cu un singur apostrof ); în Haskell ca „ a” (un identificator alfanumeric, începând întotdeauna cu o literă mică).

În plus, de-a lungul istoriei ML , au fost distinse subclase speciale de variabile de tip.

Variabile de tip care pot fi verificate pentru egalitate (sau variabile de tip comparabil, variabile de tip egalitate ) - pot lua valori din setul de toate tipurile care pot fi verificate pentru egalitate ( tipuri de egalitate în engleză  ). Utilizarea lor permite ca operația de comparare a egalității să fie aplicată la obiecte de tipuri polimorfe. Ele sunt notate ca " " (identificator alfanumeric, începând întotdeauna cu două apostrofe ). Interesant, unul dintre scopurile originale pentru care au fost dezvoltate clase de tip a fost tocmai generalizarea unor astfel de variabile de tip din Standard ML [10] . Ele au fost criticate în mod repetat din cauza complicației semnificative (și probabil justificate) a definiției limbajului și a implementării compilatorilor (jumătate de pagini ale Definiției conțin una sau alta modificare a acestora) [11] . În principiu, nu este recomandabil să verificați tipurile de date abstracte complexe pentru egalitate, deoarece astfel de verificări pot necesita o perioadă semnificativă de timp. Prin urmare, din limbile ulterioare ale familiei ML , suportul pentru variabile de tip care permite testarea egalității a fost eliminat. Haskell folosește în schimb clasa de tip . ''a Eq a

Variabilele de tip imperativ au oferit o soluție ad-hoc la problema de siguranță a tipului asociată cu efecte secundare într-un limbaj cu polimorfism parametric . Această problemă nu apare în limbile pure ( Haskell , Clean ), dar pentru limbajele impure ( Standard ML , OCaml ) polimorfismul de referință reprezintă o amenințare a erorilor de tastare [3] [4] . Variabilele de tip imperativ au făcut parte din Definiția SML'90, dar au încetat să aibă propriul lor sens după ce a fost inventată „ restricția de valoare ” , care a devenit parte a definiției revizuite SML'97. Suportul sintactic pentru variabilele de tip imperativ în SML'97 a fost păstrat pentru compatibilitatea cu codul scris anterior, dar implementările moderne le tratează identic cu cele aplicative. Notat cu „ '_a” (un identificator alfanumeric, care începe întotdeauna cu un apostrof și o liniuță de subliniere) [3] .

Variabilele de tip slab au fost utilizate în compilatorul SML/NJ ca alternativă la variabilele de tip imperativ, oferind mult mai multă putere (mai precis, mai puține restricții). Notat cu " '1a", " '2a" și așa mai departe (un identificator alfanumeric, care începe întotdeauna cu un apostrof și un număr). Numărul imediat după apostrof a indicat gradația „slăbiciunii” a variabilei de tip. La fel ca variabilele de tip imperativ, ele sunt acum tratate identic cu cele aplicative. [3]

Note

  1. ↑ 1 2 3 ML2000, 1999 .
  2. ↑ Aici, pentru legarea explicită ( explicit binding ) o variabilă de tip, se utilizează sintaxa curentă adoptată în proiectul ML succesor [1] : ['a]. Deoarece Haskell a desemnat această sintaxă ca un sugar sintactic peste tip , cuvântul cheieList a fost introdus pentru a declara variabilele de tip . forall
  3. ↑ 1 2 3 4 MacQueen - TypeChecking .
  4. ↑ 12 MLton - Scoping .
  5. ↑ haskell_existentials .
  6. ↑ Cardelli, Wegner, 1985 .
  7. ↑ haskell_rankNtypes .
  8. ↑ haskell_impredicative_types .
  9. ↑ Extensii OCaml. 7.13 Tipuri abstracte local
  10. ↑ Philip Wadler, Stephen Blott. Cum să faci polimorfismul ad-hoc mai puțin ad-hoc . — 1988.
  11. ↑ Andrew W. Appel. O critică a ML standard . — Universitatea Princeton, versiunea revizuită a CS-TR-364-92, 1992.

Literatură

Link -uri

 Tipuri de date
Ininterpretabil
Numeric
Text
Referinţă
Compozit
abstract
Alte
subiecte asemănătoare