Gen (teoria tipurilor)
Genul în teoria tipurilor ( engleză kind [1] ) este tipul unui constructor de tip , sau mai formal, tipul unui operator de tip de ordin superior . Sistemul de gen este reprezentat în mod natural ca un calcul lambda parinte (superior) tip simplu , dotat cu un tip primitiv, notat cu „ *” (citește „ tip ”), formând un fel de tipuri de date monomorfe .
Mai clar, un gen este un tip de tipuri sau un metatip - așa cum un set de valori formează un tip , un set de tipuri formează un gen [2] . În același timp, apariția tipurilor în tipuri mai generale (ca subtipuri) diferă de apartenența tipurilor la un gen - împărțirea diferitelor tipuri în genuri are loc la un nivel mai abstract. De exemplu, tipurile „ natural ”, „ întreg ” și „ real ” sunt subtipuri de tipul mai general „ număr ”; toate cele patru tipuri reprezintă valori imediate și, prin urmare, aparțin genului " *". Alte genuri se formează din diferite operații asupra tipurilor , la fel cum aritmetica distinge între numere și operații pe numere .
Ar fi firesc din punct de vedere sintactic să ne gândim la toate tipurile polimorfe ca la constructori de tip ; și, în consecință, toate cele monomorfe sunt constructori de tip nular . Cu toate acestea, toți constructorii nuli, adică toate tipurile monomorfe, aparțin de fapt aceluiași gen, și anume " *".
Deoarece operatorii de tip de ordin superior sunt neobișnuiți în majoritatea limbajelor de programare , în practica de programare, genurile sunt folosite pentru a distinge tipurile de date de tipurile de constructoare utilizate pentru implementarea polimorfismului parametric . Genurile apar explicit sau implicit în limbile cu sisteme complete de tipare , precum Haskell și Scala [3] .
Exemple
- (a se citi „ tip ” ) este un gen de toate tipurile monomorfe, considerate constructori de tip nular , numite și tipuri proprii . Tipurile de funcții din limbile funcționale aparțin și ele acestui gen .
- este genul tuturor constructorilor de tip unar . De exemplu, constructorul de tip listă este .list
- — un fel de constructori binari de tip curred . De exemplu, un constructor de tip pereche sau un constructor de tip funcțional (a nu se confunda cu rezultatul aplicării acestui constructor, adică cu tipul funcțional în sine, care aparține genului " *").
- - un fel de operatori de tip de ordin superior , adică operatori care primesc constructori de tip unari la intrare și generează ei înșiși tipuri la ieșire [4] .
Inferență generică în Haskell
Haskell furnizează tipuri polimorfe, dar nu permite genurile polimorfe [5] . De exemplu, în această definiție a unui tip algebric polimorf
date Arborele z = Frunza | Furcă ( Arborele z ) ( Arborele z )zpoate fi de orice gen, inclusiv „ ”, „ ”, etc. În mod implicit, Haskell deduce întotdeauna genul „ ”, dacă nu se specifică altfel (vezi mai jos). Prin urmare, verificatorul de consistență de tip va respinge următoarea încercare de a utiliza tipul : Tree
tip FunnyTree = Arborele [] -- eroaredeoarece tipul []este al genului " ", care nu este genul așteptat pentru , care este întotdeauna " ". z
Cu toate acestea, sunt permise operatorii de tip de ordin superior. De exemplu,
date App unt z = Z ( unt z )aparține genului „ ” , adică trebuie să fie un constructor unar , dar aici ia un tip ca argument și returnează un alt tip. unt
Vezi și
- sistem Fω
- Sistem de tip pur
Note
- ↑ Nu există o traducere bine stabilită a termenului „ tip ” în literatura de limbă rusă . Există opțiuni de traducere precum „ fel ”, „ sort ”, „ type ”
- ↑ Pierce, 2012 , Capitolul 29. Tip Operatori și Tipuri.
- ↑ Generic de tip superior . Consultat la 30 septembrie 2017. Arhivat din original la 10 iunie 2012.
- ↑ Pierce, 2012 , Capitolul 32. Exemplu extins: Obiecte pur funcționale.
- ↑ Documentația Haskell folosește aceeași săgeată atât pentru tipurile de funcții, cât și pentru genuri
Literatură
- Luca Cardelli Programare tip( (engleză)) // Rapoarte de ultimă generație IFIP. - New York: Springer-Verlag, 1991. -Vol. Descrierea formală a conceptelor de programare. —S. 431–507.
- Luca Cardelli , Peter Wegner. Despre înțelegerea tipurilor, abstracției datelor și polimorfismului. -ACM Computing Surveys, 1985. -S. 471-523. —ISSN 0360-0300.
- Pierce, Benjamin C. Tipuri și limbaje de programare . - MIT Press , 2002. - ISBN 0-262-16209-1 .
- Traducere în rusă: Pierce B. Tipuri în limbaje de programare. - Dobrosvet , 2012. - 680 p. — ISBN 978-5-7913-0082-9 .
| Tipuri de date | |
|---|---|
| Ininterpretabil | |
| Numeric | |
| Text | |
| Referinţă | |
| Compozit | |
| abstract |
|
| Alte | |
| subiecte asemănătoare | |