Tipuri de date

Mihai Budiu

mai 1995

Subiect:
Tipurile de date în în Pascal
Cuvinte cheie:
tip de date, operatori, funcții, puternic tipizat, polimorfism, supraîncărcare
Cunoștințe necesare:
Pascal, teoria elementară a mulțimilor


Contents

Introducere

Avantajele folosirii unui limbaj puternic tipizat sunt apreciate de orice programator experimentat. Printre ele sunt:

Un limbaj se numește ``puternic tipizat'' dacă în faza de execuție a unui program nu pot apărea erori cauzate de tipuri incorecte ale expresiilor. Acest articol își propune să explice într-un cadru cît se poate de riguros o colecție foarte simplă de fapte care descrie semnificația noțiunii de ``tip de date''.

Ce este un tip de date

Există mai multe definiții posibile pentru tipurile de date, din mai multe perspective. O privire globală definește simultan atît tipurile de date cît și operațiile care se pot face cu ele, pentru că acestea sunt de fapt cele două fațete ale unei aceleiași monezi: nu pot exista una fără cealaltă. Noi vom trata cele două subiecte pe rînd și în mod inegal, acordînd o oarecare prioritate tipurilor de date.

Astfel, în cea mai simplă accepțiune posibilă, un tip de date nu este altceva decît o mulțime de valori.

Ce este o valoare? Nu are nici o importanță! Este un nume special dat elementelor care aparțin unui tip. Termenul ``aparțin'' este justificat, pentru că, rețineți, tipul este o mulțime, în cel mai precis sens matematic.

Exemple? în Pascal tipul boolean este o mulțime cu două elemente. Aceste două elemente se notează în Pascal cu false și true. False și true se numesc de aceea valori booleene. Tipul integer este tot o mulțime care include, printre altele, niște elemente (valori) care în Pascal se notează cu -2, -1, 0, 1, 2, 3 etc. Tipul integer este un tip interesant, pentru că își propune să mimeze mulțimea matematica Z a numerelor întregi, dar nu reușește prea bine, pentru că mulțimea integer este finită, iar Z nu! Care sunt limitele mulțimii integer nu se specifică. În dialectul Turbo Pascal (cel mai răspîndit pe PC-uri) integer are 65536 de elemente, de la cel notat -32768 la cel notat 32767. Elementele tipului integer sunt numite valori întregi (sau mai precis integer values).

Dacă ați citit textul de mai sus cu atenție ați observat că ne-am ferit să spunem ca false este un element (valoare) boolean. Am spus false este o notație (o reprezentare) a unui element boolean! De aici încolo nu vom mai fi atît de scrupuloși; dealtfel cele două noțiuni (element și reprezentare) se pot adesea interschimba fără ambiguitate.

Vom zice de aceea:

boolean = { false, true }

unde acoladele sunt notația uzuală pentru mulțime.

Tipuri enumerate

Pascal pune la dispoziție programatorului mai multe mecanisme prin care el să-și construiască noi tipuri. Cel mai simplu dintre acestea este enumerarea. Enumerarea construiește un nou tip cu un număr finit de elemente descriind între paranteze reprezentarea canonică a fiecărui element.

Exemplu (tipic) :

 (rosu, verde, albastru, galben, mov, negru, alb)

este descrierea unui nou tip care are 7 elemente cu reprezentările rosu, verde, etc. Putem da acestui tip un nume folosind directiva type din Pascal.

 type culoare = (rosu, verde, albastru, galben, mov, negru, alb);

Din punct de vedere matematic am putea scrie

culoare = { rosu, verde, albastru, galben, mov, negru, alb }

Tipul boolean din Pascal ar putea fi definit el însuși astfel:

 type boolean = (false, true);

De ce ne este oferit însă de-a gata vom afla din următoarea secțiune și din cele consacrate operatorilor.

Tipuri fundamentale

Limbajul Pascal (standard) conține patru tipuri gata construite. Pe acestea le numim tipuri fundamentale. Ele sunt:

real, integer, char, boolean

Pentru boolean am văzut

boolean = { false, true }

Pentru integer am putea scrie ceva de genul

\begin{displaymath}integer =
\{ n \epsilon {\bf Z} \; \vert \; limita_{jos} \leq n < limita_{sus} \} \end{displaymath}

limitajos și limitasus depind de dialectul de Pascal folosit. Pentru Turbo ele sunt (după cum am zis) -32768, respectiv 32768.

Pentru char lucrurile sunt grele pentru că există unele caractere care nu au o reprezentare evidentă! Tot ce putem spune este că această mulțime include mulțimea

{'a', 'b', ...'A', 'B', ..., '0', ..., '!', ...}

a caracterelor care pot fi tipărite.

Iar pentru real lucrurile sunt și mai încîlcite, pentru că, deși real se dorește o imagine a mulțimii R a numerelor reale, în realitate real este finită și are elementele distribuite într-un mod foarte ciudat pe axa reală (nici măcar două elemente ale ei nu sunt echidistante)! Aceasta mulțime este subiectul analizei numerice, care studiază cum putem face calcule cînd putem manipula numai aproximări ale valorilor.

Derivarea tipurilor

Pascal (și nu numai el) pune la dispoziție niște puternice mecanisme prin care putem construi noi tipuri plecînd de la cele existente. (Prin enumerare putem construi tipuri plecînd de la nimic.) Derivarea dă naștere unei noi mulțimi de elemente combinînd elementele unor tipuri deja existente.

Există o interesantă clasă de tipuri numite tipuri scalare. Tipurile boolean, char, integer și toate tipurile construite prin enumerare sunt scalare. Aceste tipuri au întotdeauna un număr finit de elemente și după cum vom vedea mai tîrziu, există (datorită operatorilor de comparație) o relație de ordine totală pe ele (adică dintre două elemente unul e mai mare și celălalt mai mic)1.

Subdomeniu

Există o operație prin care dintr-un tip scalar putem extrage o submulțime formată din elemente consecutive. Ea devine un nou tip care se va numi un subdomeniu (``subrange'' în engleză) al celui inițial. Pentru că pe tipurile scalare există o ordine, submulțimea se indică prin capetele ei. Exemplu:

 1 .. 100

este un tip subdomeniu al integer, avînd 100 de elemente.

Iată un tip subdomeniu al tipului culoare definit mai sus, căruia îi dăm și un nume:

 type CulPrimara = rosu .. albastru;

Tipul numit CulPrimara are 3 elemente:

CulPrimara = {rosu, verde, albastru }.

Tipurile subdomeniu sunt toate scalare.

Articol (record)

Dacă avem la dispoziție tipurile T1, T2, ... Tn putem forma un nou tip cu construcția:

record 
  c1 : T1;
  c2 : T2;
  ....
  cn : Tn;
end

Ce mulțime reprezintă noul tip? O valoare de tip record subsumează n valori, fiecare din tipul Ti respectiv. Cu alte cuvinte putem asimila un record cu un tuplu (o mulțime ordonată) cu n elemente (v1, v2,... , vn), unde $ v_i \epsilon T_i\,\vert\, i \epsilon
\{1 \ldots n\}.$

Să dăm un nume tipului de mai sus:

type R = record 
   c1 : T1; 
   c2 : T2; 
   ... 
   cn : Tn
end;

atunci

\begin{displaymath}R = \{ (v_1, v_2, \ldots, v_n) \; \vert \; v_i \epsilon T_i, \; i = 1\ldots n \}.\end{displaymath}

sau altfel scris

\begin{displaymath}R = T_1 \times T_2 \times \dots \times T_n = \prod_{i=1}^n T_i \end{displaymath}

unde $ \times $ denotă operația de produs cartezian.

Un tip construit cu record nu este scalar.

Notă: pentru deplina rigoare ar trebui să includem în mulțimea R și numele cîmpurilor c1, c2, ..., cn. O definiție completă ar fi: produsul cartezian al tipurilor componente, avînd fiecare componentă etichetată cu numele corespunzător. Etichetarea se poate defini și ea perfect riguros, dar o lăsăm pe seama cititorului.

Vector (matrice)

Dacă avem un tip oarecare B și un tip scalar S (cu excepția lui integer) putem forma din ele un nou tip cu operația (dînd și nume tipului):

 type A = array [S] of B;

Nu este prea complicat de văzut că asta înseamnă

A = B x B x ... x B = B|S|

unde produsul este luat de cardinal din S (numărul de elemente al lui S) ori. Aceasta pentru că un array[S] of B este o colecție de atîtea valori de tipul B cîte valori conține tipul S.

Un tip construit cu array nu este scalar.

Notă: Ca mai sus, fiecare componentă a unui element din produsul Bn este etichetată cu o valoare corespunzătoare din S.

Mulțime

Dacă avem un tip scalar S putem forma tipul (dacă S nu are prea multe elemente):

set of S

Ce valori are acest nou tip? Un element al tipului set of S este o mulțime formată cu elemente din S. Deci dacă avem declarația:

type R = set of S;

atunci

\begin{displaymath}R = \{ M \; \vert \; M \subset S \} = {\cal P} (S) \end{displaymath}

adică mulțimea părților lui S.

Un tip construit cu set nu este scalar.

Fișier

Fișierul este un tip interesant. Este prima metodă de a construi un tip care -- teoretic vorbind -- este infinit! (Toate tipurile de pînă acum sunt finite pentru că sunt construite prin combinații finite ale unor mulțimi finite). Bine-nțeles că practic și acest tip este finit, dar cu o dimensiune maximă neprecizată.

Fiind dat un tip T (care nu e fișier la rîndul său) ce face operația:

file of T

?

Un fișier este asemănator unui array, dar are o lungime neprecizată. El conține la un moment dat 0 sau 1 sau 2, ... valori de tipul T. Deci dacă F e definit

type F = file of T;

atunci ca mulțime

\begin{displaymath}F = \bigcup_n \{ T^n \; \vert \; n
\epsilon {\bf N} \} = T^* \end{displaymath}

unde N este mulțimea numerelor naturale.

(O astfel de operație aplicată lui T (reuniunea tuturor puterilor) se numește operația lui Kleene, și se notează cu T*).

Record cu case

Ajungem la o operație mai puțin omogenă de combinare a tipurilor. Să considerăm directiva Pascal:

type RC = record
   c1 : T1;
   case c2 : T2 of
     v1 : ( c3 : T3 );
     v2 : ( c4 : T4 );
end

Un model aproximativ este dat de

\begin{displaymath}RC \subset T1 \times T2
\times (T3 \cup T4) \end{displaymath}

pentru că o valoare de tip RC are primele două cîmpuri de tipurile T1, respectiv T2, și un alt cîmp dintr-unul din tipurile T3 sau T4.

In realitate RC nu este atît de vastă, pentru că nu orice combinație din mulțimea indicată este în RC. Cînd cîmpul al doilea are valoarea v1, cîmpul al treilea nu poate fi de tipul T4! Deci corect este:

\begin{displaymath}RC = T1 \times ( \{v1\} \times T3 \cup \{v2\}
\times T4) \end{displaymath}

{v1} este mulțimea formată din elementul v1 aparținînd lui T2.

Un astfel de tip nu este scalar.

Pointer

Ultimul mod de derivare a tipurilor în Pascal este prin luarea referinței la ele. Un tip

type PT = ^T;

are printre valorile sale o valoare specială nil, și apoi valori care arată spre valori din tipul T. Tipul PT este deci izomorf (corespondent unu la unu) cu tipul T la care se adaugă un nou element:

\begin{displaymath}PT = T \cup \{ {\bf nil} \}.\end{displaymath}

Tipul pointer din Pascal este singurul tip care poate să includă în definiția sa pe sine însuși, ca în:

type 
  PA = ^A;
  A = record
    i : I;
    n : PA;
  end;

Asta dă o interesantă ``ecuație'' pentru mulțimea PA:

\begin{displaymath}PA = \{ nil \} \cup A = \{ nil \} \cup ( I \times PA ).\end{displaymath}

Nu este nimic contradictoriu în această formulă! Cele două mulțimi sunt într-adevăr egale, în sensul că fiecare element care se află în PA este fie nil fie se poate scrie sub forma (i, pa) unde $i \epsilon I$ și $pa \epsilon
PA$.

De fapt aceasta este definiția (recursivă) a unei liste (ați recunoscut probabil tipul PA ca fiind tipul celulei de bază care compune o listă simplu înlănțuită):

O listă (de tipul I) este sau

Numele tipurilor

Am folosit adesea în exemplele anterioare nume asociate tipurilor cu ajutorul directivei type. în construcția:

 type 
  t = record
    a : array[1..10] of integer;
    c : char;
  end;

avem două parți:

  1. una care construiește un nou tip

     record
       a: array[1..10] of integer;
       c: char;
     end
    

  2. una care îi dă un nume acestei construcții:

     type t = constructie;
    

Acestea sunt două operații distincte. Mai mult, în Pascal tipurile t și record a:array[1..10] of integer; c:char; end sunt în realitate distincte deși au aceeași structură (sunt formate prin produsele acelorași mulțimi: integer10 x char

Asta putem vedea dacă scriem:

 var x, z: t;
     y: record array[1..10] of integer; c: char; end;

Acum x și y au tipuri diferite. O operație de felul x := y nu este permisă! Putem face însă x := z.

Deci: două tipuri nu sunt compatibile chiar dacă au aceeași structură. Ele trebuie să aibă același nume, și atunci de fapt sunt o aceeași mulțime.

Operatori

În realitate orice definiție a unui tip ca mulțime trebuie să includă și o mulțime de operații pe valorile sale, care iau naștere automat odată cu crearea sa. Ce este o operație? Aparent banală întrebarea nu are un răspuns evident. div este o operație între doi întregi. Ce înseamnă asta? Ea combină cele două valori întregi cărora li se aplică pentru a genera una nouă. Este deci o funcție definită astfel:

\begin{displaymath}div : integer \times integer \rightarrow integer
\end{displaymath}

Ea asociază perechii (a,b) de numere întregi numărul ``cîtul împărțirii lui a la b''.

div este o funcție care nu se poate calcula pentru toate perechile de întregi. Dacă al doilea este 0 atunci operația nu are sens. Deci funcția este parțială, adică nu este definită pentru toate valorile posibile ale argumentelor.

De fapt asta sunt toți operatorii -- funcții din tipuri (sau produse carteziene de tipuri) în tipuri.

De ce sunt tipurile atît de legate de operatori? Pentru că crearea unui nou tip prin oricare din operațiile de mai sus dă naștere în mod automat unor operatori care lucrează cu valori din acel tip. De exemplu definirea unui tip enumerare ca cel culoare de mai sus dă naștere următorilor operatori:

operatori domeniu de definiție domeniu de valori
< > <= >= <> = culoare x culoare boolean
succ pred culoare culoare
ord culoare integer

Iată mai jos pentru fiecare tip ce operatori are (dacă este fundamental) și căror operatori le dă naștere:

boolean

operatori domeniu de definiție domeniu de valori
= <> < > <= >= boolean x boolean boolean
and or boolean x boolean boolean
not boolean boolean
succ pred boolean boolean
ord boolean integer

integer

operatori domeniu de definiție domeniu de valori
= <> < > <= >= integer x integer boolean
succ pred integer integer
ord integer integer
+ - * div mod integer x integer integer
odd integer boolean

char

operatori domeniu de definiție domeniu de valori
= <> < > <= >= char x char boolean
succ pred char char
ord char integer
chr integer char

real

operatori domeniu de definiție domeniu de valori
+ - / * real x real real
= <> < > <= >= real x real boolean

pentru orice tip enumerare T

operatori domeniu de definiție domeniu de valori
pred succ T T
= <> < > <= >= T x T boolean
ord T integer

pentru orice tip subrange T

moștenește toate operațiile tipului din care este derivat

pentru orice tip T = array[S] of B

operatori domeniu de definiție domeniu de valori
[] T x S B

(operația de indexare aplicată astfel t[s] unde $t \in
T$ și $s \in S$).

pentru orice tip mulțime T = set of S

operatori domeniu de definiție domeniu de valori
= <> <= >= T x T boolean
in S x T boolean
+ - * T x T T
[] (discutabil) S T

(ultimul este constructorul de mulțime aplicat astfel: [s, s1, s2..s3] unde $s1, s2, s3, s4 \in S$).

pentru orice tip record R = record e1:T1; ... en:Tn; end

operatori domeniu de definiție domeniu de valori
. R x mulțimea etichetelor $ \bigcup_i T_i $

(ultima este operația de selecție, care se aplică astfel r.e unde $r \in R$ și e este una din etichete.)

pentru orice tip pointer PA = $\uparrow$A

operatori domeniu de definiție domeniu de valori
$\uparrow$ PA A

(Operația de dereferențiere, aplicată astfel: pa $\uparrow$ unde $pa \in PA$.)

pentru tipul fișier F = file of T

operatori domeniu de definiție domeniu de valori
$\uparrow$ F I

(Operația de scriere/citire din buffer aplicată astfel: f$\uparrow$ unde $f \in F$.)

În plus pe lîngă operațiile descrise anterior o valoare din orice tip poate fi atribuită (:=) unei variabile de același tip (cu excepția fișierelor).

Polimorfism și supraîncărcare

După cum vedeți anumiți operatori sunt definiți pentru mai multe tipuri. De exemplu succ merge pe orice tip scalar, dînd un rezultat de același tip. în realitate $
succ : integer \rightarrow integer $ și $ succ : char \rightarrow
char $ sunt doi operatori diferiți dar care au același nume. Un astfel de operator, care funcționează pe mai multe tipuri de date simultan și a cărui comportare depinde de tipul la care se aplică se numește supraîncărcat. Adesea astfel de operatori sunt bineveniți, adesea însă pot să dea naștere la probleme. De exemplu teoretic există patru operatori + astfel:

+ : integer x integer --> integer
+ : real x real --> real
+ : integer x real --> real
+ : real x integer --> real



Toți aceștia sunt supraîncărcări ale lui +. (Ca să nu vorbim de folosirea lui + ca reuniune de mulțimi). Putem să aplicăm unul și să ne gîndim la altul, cum ar fi în următorul exemplu:

 var
  i,j : integer;
  r : real;

  i := j + r;

Ori asta nu se poate, pentru că aici + este presupus a fi

+ : integer x real --> integer

care nu există!

Există un gen special de operatori care seamănă cu cei supraîncărcați dar care nu sunt supraîncărcați ci polimorfici. Distincția între ei nu este cîteodată foarte precisă. În Pascal la acest titlu aspiră de pildă operatorii ``.'' (pentru selecție), ``[]'' (pentru indexare), etc.

De ce? Pentru că operatorul [] este definit pentru orice tipuri R, S, B:

R = array [S] of B 
[] : R x S -> B

și operează la fel independent de natura tipurilor S (scalar) și B, extrăgînd din valoarea de tipul R (un array) pe cea etichetată cu valoarea dată de tipul S. Putem spune că [] este un singur operator, oricare ar fi tipul R format ca mai sus. [] este atunci un operator polimorfic -- pentru că lucrează cu mai multe tipuri dar în exact același mod.

(Să observăm că mai există un operator notat tot cu [] pentru construit mulțimi, care este tot polimorfic! Cei doi operatori sunt distinși după modul în care se scriu în expresie. Acesta este tot o supraîncărcare!)

Glosar cu traduceri în engleză

Tip de date (data type)
o mulțime de valori căreia adesea i se adaugă un set de operatori și un set de reguli de folosire a operatorilor.

Puternic tipizat (strongly typed) (despre un limbaj)
care nu poate genera erori cauzate de tipuri eronate în timpul execuției.

Operator (operator)
o operație între mai multe valori dînd ca rezultat o altă valoare; strict vorbind o funcție (parțială) definită pe un produs cartezian de tipuri cu valori într-un tip.

Polimorfic (polymorphic)
un operator care operează la fel asupra mai multor tipuri de date structurate asemănator.

Supraîncărcat (overloaded)
(despre un operator) în realitate mai mulți operatori cu același nume, dar care sunt distinși după contextul în care se aplică (tipurile argumentelor și al rezultatului).

Tip scalar (scalar type)
un tip cu un număr finit de elemente asupra cărora este fixată o relație de ordine totală (cu ajutorul unor operatori).



Footnotes

... mic)1
Raportul Pascal marchează și tipul real ca fiind scalar, dar din motive de omogenitate noi nu îl vom considera astfel, pentru că el nu se comportă în nici o privința ca un tip scalar