concepte fundamentale ale limbajelor de...
TRANSCRIPT
Concepte
fundamentale ale
limbajelor de
programareSisteme de tipuri in limbaje de programare
Curs 08
conf. dr. ing. Ciprian-Bogdan Chirila
Cuprins
Sistemul de tipuri in Pascal
tipuri predefinite
tipuri scalare predefinite de programator
tipuri de date structurate
pointeri
echivalenta de tipuri
Cuprins
Sistemul de tipuri in C
tipuri predefinite
tipul enumerare de constante
tipuri de date structurate
pointeri
structuri recursive
echivalenta de tipuri
Cuprins
Sistemul de tipuri in Ada
tipuri predefinite
tipuri scalare definite de programator
tipuri de date structurate
pointeri
echivalenta de tipuri
subtipuri si tipuri derivate
Cuprins
Sistemul de tipuri in Lisp
tipuri predefinite simple
liste
vectori si matrici
vectori si matrici de biti
siruri de caractere
echivalenta de tipuri
subtipuri
Comparatii
Limbaje de programare puternic tipizate
Sistemul de tipuri in Pascal
tipuri predefinite
numerice: integer, real
ne-numerice: boolean, char
tipuri scalare definite de programator
tipul enumerare
type section=(automation, computer, electronic, electrotechnical, energetic)
subdomenii
type weak_currents=automation..computer;
digits=’0’..’9’;
month=1..12;
Tipuri scalare definite de
programator
un subdomeniu este compatibil cu tipul sau de baza
atribuirile dintre weak_currents si sections sunt permise
domeniul variabilei trebuie verificat
verificarea poate fi realizata doar la executie
Tipuri structurate. Tablouri
tablourile implementeaza in Pascal proiectiile finite
type t:=array[TI] of TE;
TI – tip index;
trebuie sa fie specificat la momentul definirii inainte de
compilare
TE- tip element;
tipul indexului inclusiv dimensiunea acestuia face parte din
tablou
Tablouri
type
t=array[1..10] of integer;
t1=array[1..20] of integer;
sunt diferite, sunt tipuri incompatibile
proceduri generale ce accepta tablouri ca parametri nu pot fi create
o solutie este sa se declare parametri formali la lungimeamaxima
lungimea efectiva <= lungimea maxima
solutia este una rigida si ne-economica
Arrays
solutia in standardul ISO Pascal
tablouri conforme
un parametru formal fara limita de indexare
va fi conform cu unul actual prin
acelasi numar de dimensiuni
acelasi tip de element
procedure p(var a:array[j..s:integer] of real);
var i:integer;
begin
for i:=j to s do
a[i]:=…
end
Inregistrarile
implementeaza in Pascal produsul cartezian si reuniunile
variabile
implica specificarea pentru fiecare camp numele si tipul
type person=record
name:array[1..30] of char;
day,month,year:integer;
end;
Accesul prin mecanismul de
selectie
var author:person;
author.name:=”peter”;
author.day:=5;
author.month:=4;
author.year:=1970;
Accesul prin mecanismul
with
with author do
begin
name:=”peter”;
day:=5;
month:=4;
year:=1970;
end
Reuniuni variabile
type person=record
name:array[1..30] of char;
day,month,year:integer;
case man:boolean of
true:(weight,height:real);
false:(married:boolean);
end;
var p:person;
Reuniuni variabile fara
camp de selectie
type person=record
name:array[1..30] of char;
day,month,year:integer;
case boolean of
true:(weight,height:real);
false:(married:boolean);
end;
Reuniuni variabile
p.name:=”Paul”;
p.day:=30; p.month:=10; p.year:=1980;
p.man:=true;
p.weight:=81;
p.man:=false;
if p.married then …
sunt mai putin sigure in limbajul Pascal
Multimi
tipul multime
permite descrierea de multimi
reuniune, intersectie, diferenta
teste de incluziune, teste de apartenenta
tipul de baza trebuie sa fie scalar si nu real
cardinalitate limitata
type t=set of integer; /* este gresit */
type t=set of 0..255; /* este corect */
Fisiere
secventa de elemente de acelasi tip
type ftype = file of t;
tipul de baza poate fi orice tip
Pointeri
in declararea unui pointer trebuie declarat tipul de
referinta
asigura compatibilitatea de tip in operatiile legate de
pointeri
pointerul nul este marcat / notat cu cuvantul cheie “nil”
obiecte anonime referite de pointeri sunt create cu
operatorul “new”
var p:^t;
new(p);
Pointeri
eliberarea zonelor de memorie se face cu
dispose(p);
nu pot referi variabile ca in limbajul C
pot referi doar obiecte anonime alocate dinamic
Echivalenta de tipuri
semantica limbajului nu specifica cand doua tipuri sunt
echivalente
diferite implementari de limbaj au diferite echivalente de
tip
in standardul Pascal ISO s-a adoptat o definitie care
este aproape de echivalenta de nume
se cheama echivalenta de declaratie
Echivalenta de tipuri
type
t=record
n:array[1..30] of char;
i:integer;
end;
tx=record
n:array[1..30] of char;
i:integer;
end;
t1=t;
var x:t; y:tx; z:t1;
Echivalenta de tipuri
x si z sunt compatibile
tipul lor este descris de aceeasi inregistrare
nu este cazul pentru compatibilitatea de nume
y nu este compatibil cu x sau cu z
asa cum ar fi in cazul echivalentei structurale
tipurile de subdomenii sunt compatibile cu tipurile lor de
baza
aceasta regula este impotriva echivalentei de nume
Sistemul de tipuri al
limbajului C
tipuri predefinite
contante enumerate
tipuri de date structurate
tablouri
structuri
uniuni
pointeri
structuri recursive
echivalente de tipuri
Tipuri predefinite
char – un octet pentru setul de caractere locale
int – multimea intregilor pe masina gazda
short int de regula pe 16 biti
long int pe cel putin 32 de biti
lungime(short) 16 bits
lungime(short)<= lungime(int)<=lungime(long)
modificatorii signed si unsigned pot fi aplicati la tipul char si
int
unsigned char 0..255
signed char -128..+127
float, double
<limits.h> <float.h>
Constante enumerate
enum boolean {NO,YES};
enum days {MO=1,TU,WE,THU,FRI,SAT,SUN};
Tablouri
forma generala
tip_element nume_tablou[expresie_constanta]
dimensiune tablou >0
exemplu
v[10] – tablou de 10 intregi
indicii incep de la zero
primul element v[0]
ultimul element v[9]
initializarea
int x[]={1,2,3};
dimensiunea tabloului trebuie sa fie cunoscuta la compilare
tablourile in C sunt tablouri statice
Tablouri multidimensionale
este un tablou de tablouri
int mat[10][10]
matrice cu 10 linii si 10 coloane
elementul de la pozitia (i,j) poate fi accesat prin mat[i][i] si nu
prin mat[i,j] ca in alte limbaje de programare
array formal parameters can be declared incompletely
without specifying the first dimension
parametri formali de tip tablou pot fi declarati incomplet
far a specifica prima sa dimensiune
int f(char l[],int m[][10]);
Tablouri multidimensionale
dimensiunile efective ale tablourilor poate fi specificata la
apelul functiilor
functiile pot avea un grad mai mare de generalitate ca
cele din Pascal unde
dimensiunea parametrului formal si a celui actual trebuie sa fie
egale
Structuri
implementeaza in C produsele Cartesiene
struct point
{
int x;
int y;
};
poate fi copiat prin atribuire
struct point origin={0,0};
Structuri
accesul la campuri
struct point p;
p.x or p.y
pot fi returnate de functii
struct point f(int x, int y) { }
pot fi incuibate
struct rectangle
{
struct point p1;
struct point p2;
};
accesul poate fi incuibat
struct rectangle r;
r.p1.x
Uniuni
implementeaza reuniuni variabile
union
{
int i;
float f;
char c;
} u;
u poate fi un intreg sau un float sau un char
Uniuni
selectia
u.i, u.f, u.c
pot fi incuibate cu ale uniuni, structuri sau tablouri
reprezentari in memorie
toate au un offset de memorie zero fata de adresa de start
la un moment dat doar o reprezentare este disponibila
nu se face verificare de tip
toata responsabilitatea este lasata pe umerii programatorului
selectarea unei variante rele poate cauza erori de programare grave
operatiile permise sunt cele de la multimi
pot fi initializate cu o valoare corespunzatoare primei variantede tip (intreg pentru u)
Pointeri
o declaratie de pointer trebuie sa utilizeze un tip referit
int x=1, y;
int *p; /* p este un pointer la intreg */
void *p1; /* poate stoca orice tip de pointer */
pot stoca adrese ale obiectelor
p=&x;
pentru a accesa obiectul referit de pointer
este numita dereferentiere
y=*p; /* y gets value 1*/
*p=0; /* x gets value 0 */
pot fi create sinonime cu consecintele cunoscute
Pointeri
permite accesul direct la locatia de memorie a unui
argument
void exchange1(int x, int y) /* gresit */
{
int aux;
aux=x; x=y; y=aux;
}
exchange1(a,b);
/* interschimba doar copii a lui a si b */
Pointeri
void exchange2(int *x, int *y)
{
int aux;
aux=*x; *x=*y; *y=aux;
}
exchange2(&a,&b); /* apel correct */
/* interschimba valorile lui a si b */
Pointeri
pot fi folositi impreuna cu tablourile
int a[10];
int *pa;
pa=&a[0]; /*pa will hold the address of a[0]*/
valoarea unui tablou este de asemenea valoarea primului
element din tablou
a si pa au aceeasi valoare
Pointeri
*(pa+i) este continutul lui a[i]
*(pa+i) este echivalent cu a[i]
(pa+i) este echivalent cu &a[i]
cand un tablou este transmis la o functie
doar adresa primului element este transmisa
parametrul formal este de fapt pointer
se comporta ca o variabila ce contine o adresa
int f(char s[]) { … }
int f(char *s) { … }
cele doua forma sunt echivalente
Aritmetica pointerilor
operatii permise
atribuirea de pointeri de acelasi tip
adunarea sau scaderea a unui pointer cu un intreg
scaderea sau compararea a doi pointeri referind elemente
din acelasi tablou
atribuirea sau compararea cu NULL (0)
Aritmetica pointerilor
operatii ilegale
adunarea a doi pointeri
inmultirea sau impartirea pointerilor
deplasarea pe biti sau aplicarea de masti
adunarea pointerilor cu valori reale
Pointeri la functii
permisi in C
pot fi atribuiti
pot fi atribuiti in tablouri
pot fi trimisi ca parametri functiilor
pot fi returnati ca valori de functii
Alocarea dinamica a
memoriei si realocarea
alocarea dinamica a obiectelor anonima de dimensiune
specificata
malloc(…)
calloc(…)
eliberarea memoriei alocate
free()
eliberarile de memorie pot crea referinte false
Structuri recursive
bazate pe pointeri
permit descrierea de liste sau arbori
struct node
{
type info;
struct node *left;
struct node *right;
};
structurile recursive trebuie sa utilizeze pointeri
un tip nu poate contine o instantiere a sa
Echivalenta de tip
bazata pe echivalenta structurala
exceptii
struct
union
sunt tipuri diferite chiar daca au aceeasi structura
sunt permise conversii de tip prin casting
(type) expression
Sistemul de tipuri in Ada
tipuri predefinite
numerice
intregi
short_integer, long_integer
in virgule flotanta
short_float, long_float
ne-numerice
character
boolean
Tipuri scalare definite de
programator
numerice
type under_hundred is range 0..99
type real is digits 7;
type small_real is digits 7 range 0.0..100.0;
Type centimes is delta 0.01 range 0.0..1.0;
0, 0.01, 0.02, 0.03, 0.04, …, 1
tipuri enumerare
type sections is (automation, computer, electronics,
electrotechnical, energetics)
Tipuri de date structurate.
Tablouri
pot fi declarate static
type student_no is array[sections] of integer;
type tab is array(1..10) of integer;
nu trebuie specificate limite de index
doat tipul de baza este obligatoriu
nu sunt restrictii la tipul tabloului
type st_no is array(sections range<>) of integer;
type matrix is array(integer range<>, integer range<>) of real;
type bits is array(integer range<>) of boolean;
Tablouri
weak_currents_stud_no:st_no(automation..electronics)
tab:matrix(1..5,1..5);
restrictiile pentru indecsi nu trebuiesc specificate static
se pot utiliza expresii ce se pot calcula la compilare
tabele dinamice cu
dimensiune nespecificata la rulare
dimensiune specificata la executie
Tablouri
mask : bits(1..n);
mat : matrix(1..n,1..m);
tip tablou
tip element
numarul de dimensiuni
tip de baza index pentru fiecare dimensiune
Tablouri
type vect is array(integer range<>) of real;
procedure p(a:in out vect) is
temp:vect(a’first..a’last)
i:integer;
begin
for i in a’first..a’last loop
temp(i):=a(i);
end loop;
end p;
Tablouri
procedura p poate fi apelata cu un parametru actual de
dimensiune aleatoare
first, last
atribute ce returneaza limita inferioara si superioara a tabloului
Articole
implementeaza
produsele Carteziene
reuniunile variabile
type person is
record
name:string(1..30);
day,month,year:integer;
end record;
Articole
type person(man:boolean:=true) is
record
name:string(1..30);
day,month,year:integer;
case man is
when true=>weight,height:float;
when false=>married:boolean;
end case;
end record;
Articole
campul de selectie este obligatoriu
in timpul executiei este verificata validitatea campului
referentiat pe baza valorii selectorului
orice obiect de tip “person” va avea campul “man” pus
pe valoarea “true”
astfel campurile “weight” si “height” vor fi accesibile
pm:person
pf:person(false);
Articole
instructiuni ilegale
pm.man:=false;
pf.man:=true;
este posibil sa se procedeze asa
pm:=(false,”john”,25,05,1958,true);
pm:=pf;
Pointeri
type ref is access t;
reference : ref;
--------------------------
reference:=new t;
valoarea null este prezenta
Pointeri
pentru a evita referintele fictive
dealocarea memoriei pentru obiectele dinamice se face
automat
doar cand nu este un pointer care sa il refere
unchecked_deallocation
realizata manual de programator
similara cu instructiunea “dispose” din Pascal
Echivalenta de tipuri
echivalenta de nume
facilitatea de subtipizare
evita un system de tipuri rigid
orice declarative de tip creaza un tip nou
x si y sunt incompatibile
type price is range 0..integer’last;
type under_hundred is range 0..99;
x:price;
t:under_hundred;
------------------------
y:=x; --it is ilegal
Subtipizarea
subtype under_hundred is price range 0..99;
t:under_hundred;
------------------------
y:=x; -- este illegal, dar 0<=y<=99
Subtipizarea
subtype no_of_students is new price;
a:price;
b:no_of_students;
a:=b; -- este ilegal
Sistemul de tipuri in Lisp
include tipuri de date
nu exista variabile in sensul classic
variabilele sunt inlocuite cu atomi simbolici sau simboluri
simbolurile au nume care este un sir de caractere si nu
reprezinta numere
Lisp este proiectat pentru calcul simbolic
Sistemul de tipuri in Lisp
in limbajele imperative
la o variabila atribuim o valoare de un anumit tip
referinta la valoare se face prin numele variabilei
in Lisp
un nume de simbol este atasat la o entitate pentru un timp
tipul de data nu se refera la simboluri ci la valori legate
un simbol poate reprezenta la momente diferite valori diferite
de tipuri diferite
Sistemul de tipuri in Lisp
din punct de vedere al implementarii
legarea dinamica a diferitelor tipuri este posibila
deoarece variabilele Lisp sunt referinte (pointeri) la entitati ce
pot fi de diverse tipuri
in limbajele imperative
variabila este un nume dat unei locatii de memorie
de dimensiune fixa
egal cu tipul variabilei
Legarea unei valori la un
atom
inlocuieste operatia de atribuire
este implementata prin formele functionale setq si setf
setq = set quoted
setf = set field
> (setq x 10)
10
> (setq x ‘Lisp)
LISP
> (setq x ‘(a b c))
(A B C)
Sistemul de tipuri in Lisp
tipul este specific obiectului reprezentat de simbol
dar nu de simbolul insusi
este cazul limbajelor de programare slab tipizate
la compilare este imposibil de stiut care este tipul unei
variabile
facilitatile de procesare dinamica sunt favorizate in
schimbul verificarilor corespondentei de tipuri in timpul
compilarii
Tipuri predefinite simple
numerice
intregi
Fixnum
Bignum
rapoarte
10/3
10/2
10/4
(* 5/2 5/3)
25/6
Tipuri predefinite simple
Numerice (continuare)
float
short-float
single-float
double-float
long-float
complex
a+bi -> #c(a b)
> (sqrt -1)
#c(0 1)
> (* #c(01) #c(0 2))
-2
nenumerice
character
Liste
listele sunt expresii compuse si non-atomice
(red yellow blue)
(1 2 -4 1.5)
((red yellow blue) (1 2 -4 1.5))
organizarea este linara, secventiala
sunt implementate ca si structuri de date dinamice
in limbajele imperative
alocarea si dezalocarea dinamica a elementelor din liste
se face manual de catre programator
in Lisp alocarea si dezalocarea este realizata in mod
automat
Liste
Adding an element into a list using cons
adaugarea unui element intr-o lista folosind primitiva cons
(construct)
(cons ‘d ‘(a b c))
(d a b c)
alocarea dinamica pentru d
legarea lui d la lista
sunt invizibile pentru programator
doua campuri
car – pointer spre primul element al listei
cdr – pointer spre restul de elemente al listei
Vectori si matrici
> (setq mat (make-array ‘(2 3 2):initial-contents
‘(((1 2)(3 4)(5 6)) ((7 8)(9 10)(11 12))))
#3A(((1 2)(3 4)(5 6)((7 8)(9 10)(11 12)))
Vectori si matrici
> (setq vect (vector 0 1 2 3 4 5 6 7 8 9))
#(0 1 2 3 4 5 6 7 8)
> (aref mat 0 0 0)
1
> (aref mat 1 2 0)
11
Vectori de biti si matrici de
biti
> (setq matbits (make-array ‘(2 3 2)
:initial-element 0:element-type ‘bit))
#3A ((#*00 #*00 #*00) (#*00 #*00 #*00))
> (setq (aref matbiti 1 2 0) 1))
1
Vectori de biti si matrici de
biti
> (setq vbiti #*01010101)
#* 01010101
> (bit-not vbiti)
#* 10101010
bit-not
bit-and
bit-ior, bit-xor
bit-eqv - equivalence
bit-orcl - implication
Siruri de caractere
subtip al vectorilor
>(length “abcd”)
4
>(aref “abcd” 2)
#\c
comparatii de siruri de caractere
> (string = “abcd” “abcd”)
T
> (string < “abcd” “abdd”)
2
Siruri de caractere
transformarea unui atom in sir de caractere
> (string ‘abcd)
“ABCD”
cautarea unui subsir intr-un sir
> (search “cd” “abcd”)
2
Echivalente de tip. Subtipuri
programatorul nu trebuie sa fie atent la tipurile de date in
Lisp
in versiunile vechi tipurile nici nu existau
legarea dinamica a tipurilor evita verificarea statica
singura verificare este facuta atunci cand un operator isi
executa operanzii
>(+ 1 “5”)
Subtipuri
tipuri numerice
numere
rationale
integer
fixnum
bignum
ratio
float
short-float
single-float
double-float
long-float
complexe
Subtipuri
tipuri vector
vector
string
bit-vector
operatori
type-of 1 arg
type-p() 2 args
subtype-p() 2 args
Exemple de tipuri
> (type-of 1)
FIXNUM
> (type-of #*01000111)
(SIMPLE-BIT-VECTOR 8)
> (type-of #\a)
CHARACTER
> (type-of ”abcd”)
SIMPLE-STRING
Exemple de subtipuri
> (typep 1 ‘number)
T
> (typep 1 ‘integer)
T
> (typep 1 ‘fixnum)
T
> (typep 1 ‘bignum)
NIL
Exemple de subtipuri
> (typep (a b c) ‘sequence)
T
> (typep (a b c) ‘list)
T
> (subtypep ‘integer ‘number)
T
> (subtypep ‘array ‘sequence)
NIL