Concepte fundamentale ale limbajelor de...

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


pointeri

structuri recursive


Cuprins

Sistemul de tipuri in Ada

tipuri predefinite

tipuri scalare definite de programator


pointeri


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


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



case man:boolean of

true:(weight,height:real);

false:(married:boolean);

end;

var p:person;

Reuniuni variabile fara

camp de selectie

type person=record



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


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;


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


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);


end record;

Articole

type person(man:boolean:=true) is

record

name:string(1..30);


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 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


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


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


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


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)


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


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

Concepte fundamentale ale limbajelor de...

Documents

Transcript of Concepte fundamentale ale limbajelor de...