Paradygmaty

Paradygmaty

programowania

programowania

Wykład 2 – Wartości i typy danych

Wartości

Wartości

Wartością jest dowolny obiekt, który może być modyfikowany

przez program

• Wartości mogą być obliczane, przechowywane, przekazywane do

• Wartości mogą być obliczane, przechowywane, przekazywane do

funkcji, zwracane z funkcji jako wynik.

• Wyróżniamy dwa rodzaje wartości:

proste i złożone

.

• Różne języki programowania wspierają różne typy wartości np.

C : całkowite, rzeczywiste, struktury, tablice, unie, wskaźniki do

zmiennych, wskaźniki do funkcji

C++: dodatkowo obiekty

Wartości

Wartości

Wartości

Wartości

pierwszej klasy

(first-class values)

Wartości

drugiej klasy

(second-class values)

Typy

Typy

Typ jest zbiorem wartości połączonym z co najmniej jedną

operacją, którą można zastosować do wszystkich wartości typu

{…,-3,-2,-1,0,1,2,3,…}

{…,3.14,prawda,Jan,…}

– może być typem

– nie może być typem

Typy

Typy

Typ jest zbiorem wartości połączonym z co najmniej jedną

operacją, którą można zastosować do wszystkich wartości typu

Typy

Typy

Proste

Złożone

Rekursywne

Typy proste

Typy proste

Wartością prostą nazywamy wartość, która nie może być

rozłożona na prostsze wartości.

Typ prosty jest to typ, który przyjmuje wartości proste

Logiczne (boolean) =

{prawda, fałsz}

Znakowe (char) =

{…, ’a’,…,’z’,…,’0’,…,’9’,…,’@’,…}

Całkowite (integer) =

{…,-2,-1,0,1,2,…}

Rzeczywiste (float) =

{…,-2.0,…,-1.0,…,0.0,…,1.0,…,2.0,…}

Typy proste

Typy proste

Wartością prostą nazywamy wartość, która nie może być

rozłożona na prostsze wartości.

Typ prosty jest to typ, który przyjmuje wartości proste

C

C++

Java

bool

boolean

int

int

int

long

long

long

float

float

float

double

double

double

char

char

char

Typy proste

Typy proste

Wartością prostą nazywamy wartość, która nie może być

rozłożona na prostsze wartości.

Typ prosty jest to typ, który przyjmuje wartości proste

Liczebność typu T (#T)

– określa liczbę różnych wartości

przyjmowanych przez typ T

#Boolean = 2

#char = 256 (ISO LATIN)
#char = 65536 (UNICODE)

#int = 4294967296 (Java)
#int = 131070 (C)

Typy złożone

Typy złożone

Wartością złożoną nazywamy wartość, która może być

rozłożona na prostsze wartości.

Typ złożony jest to typ, który przyjmuje wartości złożone.

Typy złożone

Produkt

kartezjański

Mapowania

Rozłączne

unie

Typy

rekursywne

Typy złożone

Typy złożone –

– produkt kartezjański

produkt kartezjański

W typach będących produktem kartezjańskim wartości kilku

(być może różnych) typów są grupowane w n-tki.

S×T

= {(x,y) | x∈S; y∈T}

S×T

= {(x,y) | x∈S; y∈T}

#(S×T) = #S⋅#T

u

v

(u,a)

(u,b)

(u,c)

(v,a)

(v,b)

(v,c)

a

b

c

×

×

×

×

=

S

T

S×T

Typy złożone

Typy złożone –

– produkt kartezjański

produkt kartezjański

W typach będących produktem kartezjańskim, wartości kilku

(być może różnych) typów są grupowane w n-tki.

Podstawowe operacje jakie można wykonywać na

Podstawowe operacje jakie można wykonywać na
n-tkach to:

•

stworzenie

n-tki z n elementów

•

wybranie

jednego z elementów n-tki

Typy złożone

Typy złożone –

– produkt kartezjański

produkt kartezjański

Rekody w Pascalu

program Rekordy;
type

Data = record

rok : integer;
miesiace : 1..12;
dzien : 1..31;

end;

var

dataUrodzenia : Data;

begin

dataUrodzenia.dzien := 12;
dataUrodzenia.miesiac := 7;
dataUrodzenia.rok := 1997;
write(”Data urodzenia: ”, dataUrodzenia.dzien,

dataUrodzenia.miesiac, dataUrodzenia.rok);

end;

Typy złożone

Typy złożone –

– produkt kartezjański

produkt kartezjański

Struktury w C++

#include<iostream>

enum Miesiac {sty, lut, mar, kwi, maj, cze, lip, sie,

wrz, paz, lis, gru};

struct Data {

Miesiac miesiac;
byte dzien;

};

int main()
{

struct Data wyklad = {lut, 21};
std::cout<<wyklad.miesiac<<” ”<<wyklad.Dzien

<<std::endl;

return 0;

}

Typy złożone

Typy złożone –

– mapowania

mapowania

W mapowaniach każdej wartości typu S odpowiada wartość

typu T.

m

: S→T = {m|x∈S⇒m(x)∈T}

#(S→T) = (#T)

#S

u

v

a

b

c

→

→

→

→

=

{u→a, v→a} {u→a, v→b} {u→a, v→c}

{u→b, v→a}

{u→c, v→a}

{u→b, v→b} {u→b, v→c}

{u→c, v→b} {u→c, v→c}

S

T

S → T

Typy złożone

Typy złożone –

– mapowania

mapowania

Typowymi przedstawicielami mapowań są:

tablice, słowniki i

W mapowaniach każdej wartości typu S odpowiada wartość

typu T.

Typowymi przedstawicielami mapowań są:

tablice, słowniki i

funkcje mapujące (funkcje)

.

Podstawowe operacje jakie można wykonywać na
mapowaniu to:

•

stworzenie

mapowania z n elementów

•

indeksacja

wybranie jednego elementu mapowania na

podstawie jego indeksu

Typy złożone

Typy złożone –

– mapowania

mapowania

Tablice w C++

#include<iostream>

int main()
{

bool tab1[3];

bool tab1[3];
int tab2[] = {0,23,53};

tab1[0] = 4;
for(int i=0; i<3; i++)
{

std::cout<<tab2[i]<<std::endl;

}
return 0;

}

Typy złożone

Typy złożone –

– mapowania

mapowania

Słowniki w C#

using System;
using System.Collections.Generic;

namespace slownikTest {

class Program {

static void Main(string[] args) {

Dictionary<string, int> slownik = new Dictionary<string,int>();

slownik.Add("ala", 1);
slownik.Add("ma", 1);
slownik.Add("kota", 1);

Console.WriteLine( slownik["ala"] );
Console.WriteLine( slownik["ma"] );
Console.WriteLine( slownik["kota"] );

}

}

}

Typy złożone

Typy złożone –

– mapowania

mapowania

Funkcje w C++

#include<iostream>

bool czyParzysta(int wartosc)
{

return (wartosc % 2 == 0);

return (wartosc % 2 == 0);

}

int main()
{

std::cout<<czyParzysta(4)<<std::endl;
std::cout<<czyParzysta(7)<<std::endl;
return 0;

}

Typy złożone

Typy złożone –

– rozłączne unie

rozłączne unie

W uniach wartość jest wybierana dla jednego z wielu

(zazwyczaj różnych) zbiorów

S

+T={lewy x | x∈S} ∪ {prawy y|y∈T}

→

#(S+T) = #S+#T

u

v

a

b

c

{lewy u}

{lewy v}

{prawy a}

{prawy b}

{prawy c}

+

=

S

T

S

+T

Podstawowe operacje jakie można wykonywać na uniach to:

Typy złożone

Typy złożone –

– rozłączne unie

rozłączne unie

W uniach wartość jest wybierana dla jednego z wielu

(zazwyczaj różnych) zbiorów

Podstawowe operacje jakie można wykonywać na uniach to:

•

stworzenie

unii poprzez ustawienie wartości

z T lub z S i odpowiednie jej oznaczenie

•

sprawdzenie etykiety

- określenie czy wartość

pochodzi ze zbioru S czy z T

•

projekcja

odzyskanie wartości zbioru S lub zbioru T

Typy złożone

Typy złożone –

– mapowania

mapowania

Rekord z wariantami (discriminant record) w Ada

type Dokladnosc is (dokladna, niedokladna);
Type Liczba (dok:Dokladnosc := dokladna) is

record

case dok of

when dokladna => calk: Integer;
when niedokladna => rzecz: Float;

when niedokladna => rzecz: Float;

end case;

end record;

pi: constant Liczba := (dok=> niedokladna, rval=> 3.14);

function zaokr(licz: Liczba) return Float is

case licz.acc is

when dokladna => return licz.calk;
when niedokladna => return licz.rzecz;

end case;

end;

Typy złożone

Typy złożone –

– mapowania

mapowania

Unie w C++

#include<iostream>

int main()
{

union Przyklad

{

char znaki[4];

char znaki[4];
int calkowita;

};

Przyklad p;
p.znaki[0] = ’A’;
p.znaki[1] = ’B’;
p.znaki[2] = ’C’;
p.znaki[3] = ’\n’;

std::cout<<p.znaki<<” ”<<p.calkowita<<std::endl;

}

Typy rekursywne

Typy rekursywne

Typ rekursywny to taki, który zawiera sam siebie.

Przykładowe typy rekursywne:

Przykładowe typy rekursywne:

• Listy:

ListaInt = {pusta_lista} ∪

∪

∪

∪

{Elem(i, l) | i∈

∈

∈

∈

int; l∈

∈

∈

∈

ListaInt}

• Łańcuchy znaków (string) (Haskell, Prolog)
• Drzewa

System typów

System typów

System typów grupuje wartości w typy

systemy

typów

statyczne

dynamiczne

System typów

System typów -- statyczne

statyczne

W statycznych systemach typów każda zmienna i wyrażenie

posiada ustalony typ (ustawiony przez programistę lub

wywnioskowany przez kompilator)

Właściwości statycznych systemów typów:

Właściwości statycznych systemów typów:

• są bardzie efektywne niż systemy dynamiczne
• wymagają sprawdzenia już na etapie kompilacji programu
• wymagają mniej pamięci
• są bardziej bezpieczne

Przykłady języków o statycznych systemach typów:
Ada, C, C++, C#, Java, Pascal, Visual Basic

System typów

System typów -- dynamiczne

dynamiczne

W dynamicznych systemach typów wartości posiadają

ustalony typ, ale zmienne i wyrażenia już nie

Właściwości dynamicznych systemów typów:

Właściwości dynamicznych systemów typów:

• są mniej efektywne niż systemy statyczne
• wymagają sprawdzenia podczas wykonywania programu
• wymagają więcej pamięci
• są mniej bezpieczne

Przykłady języków o statycznych systemach typów:
Lisp, JavaScript, Perl, PHP, Prolog, Python, Smalltalk

Równoważność typów

Równoważność typów

Pozwala na sprawdzenie czy dwa typy danych są sobie

równoważne (T ≡

≡

≡

≡

S)

równoważność

równoważność

typów

strukturalna

wg

nazwy

Równoważność typów

Równoważność typów –

– strukturalna

strukturalna

Dwa typy T i S są równoważne wtedy i tylko wtedy gdy

mają te same zbiory wartości

• Typy proste

• Typy proste

T ≡

≡

≡

≡

S ⇔ T i S są identyczne

• Typy złożone – iloczyn kartezjański (T = A

1

×

B

1

i S = A

2

×

B

2

)

T ≡

≡

≡

≡

S ⇔ A

1

≡

≡

≡

≡

A

2

i B

1

≡

≡

≡

≡

B

2

• Typy złożone – mapowania (T = A

1

→

B

1

i S = A

2

→

B

2

)

T ≡

≡

≡

≡

S ⇔ A

1

≡

≡

≡

≡

A

2

i B

1

≡

≡

≡

≡

B

2

• Typy złożone – unie (T = A

1

+ B

1

i S = A

2

+ B

2

)

T ≡

≡

≡

≡

S ⇔ (A

1

≡

≡

≡

≡

A

2

i B

1

≡

≡

≡

≡

B

2

) lub (A

1

≡

≡

≡

≡

B

2

i B

1

≡

≡

≡

≡

A

2

)

Równoważność typów

Równoważność typów –

– strukturalna

strukturalna

struct Punkt {int x,y,z}

Dwa typy T i S są równoważne wtedy i tylko wtedy gdy

mają te same zbiory wartości

struct Punkt {int x,y,z}

struct Data {int dzien, miesiac, rok}

void pokaz(struct Data d);

Równoważność typów

Równoważność typów –

– wg nazwy

wg nazwy

Dwa typy T i S są równoważne wtedy i tylko wtedy gdy

są zdefiniowane w tym samym miejscu

Równoważność wg nazwy wymaga aby każdy typ był zdefiniowany
w jednym i tylko jednym miejscu w programie