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, wskaz
niki do
zmiennych, wskaz
niki do funkcji
C++: dodatkowo obiekty
Wartości
Wartości
Wartości
Wartości Wartości
pierwszej klasy drugiej klasy
(first-class values) (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,& }  może być typem
 nie może być typem
{& ,3.14,prawda,Jan,& }
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
Rekursywne
Proste Złożone
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 Rozłączne Typy
Mapowania
kartezjański unie rekursywne
Typy złożone  produkt kartezjański
Typy złożone  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}
(u,a) (u,b) (u,c)
× =
×
×
×
u v a b c
(v,a) (v,b) (v,c)
S T
S×T
#(S×T) = #SÅ"#T
Typy złożone  produkt kartezjański
Typy złożone  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  produkt kartezjański
Typy złożone  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  produkt kartezjański
Typy złożone  produkt kartezjański
Struktury w C++
#include
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<<return 0;
}
Typy złożone  mapowania
Typy złożone  mapowania
W mapowaniach każdej wartości typu S odpowiada wartość
typu T.
m: ST = {m|x"SÒ!m(x)"T}
{ua, va} {ua, vb} {ua, vc}
=



u v a b c
{ub, va} {ub, vb}
{ub, vc}
{uc, vb}
{uc, va} {uc, vc}
S T
S T
#(ST) = (#T)#S
Typy złożone  mapowania
Typy złożone  mapowania
W mapowaniach każdej wartości typu S odpowiada wartość
typu T.
Typowymi przedstawicielami mapowań są: tablice, słowniki i
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  mapowania
Typy złożone  mapowania
Tablice w C++
#include
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<}
return 0;
}
Typy złożone  mapowania
Typy złożone  mapowania
SÅ‚owniki w C#
using System;
using System.Collections.Generic;
namespace slownikTest {
class Program {
static void Main(string[] args) {
Dictionary slownik = new Dictionary();
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  mapowania
Typy złożone  mapowania
Funkcje w C++
#include
bool czyParzysta(int wartosc)
{
return (wartosc % 2 == 0);
return (wartosc % 2 == 0);
}
int main()
{
std::cout<std::cout<return 0;
}
Typy złożone  rozłączne unie
Typy złożone  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}
{lewy u} {lewy v}
=
+
u v a b c
{prawy a} {prawy b}
{prawy c}

S T
S+T
#(S+T) = #S+#T
Typy złożone  rozłączne unie
Typy złożone  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:
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  mapowania
Typy złożone  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  mapowania
Typy złożone  mapowania
Unie w C++
#include
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<}
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" "ListaInt}
*" "int; l"
*" " "
*" " "
" A
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 - statyczne
System typów - 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 - dynamiczne
System typów - 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 a" S)
a"
a"
a"
równoważność
równoważność
typów
wg
strukturalna
nazwy
Równoważność typów  strukturalna
Równoważność typów  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 a" S Ô! T i S sÄ… identyczne
a"
a"
a"
" Typy zÅ‚ożone  iloczyn kartezjaÅ„ski (T = A1×B1 i S = A2×B2)
T a" S Ô! A1 a" A2 i B1 a" B2
a" a" a"
a" a" a"
a" a" a"
" Typy złożone  mapowania (T = A1 B1 i S = A2 B2)
T a" S Ô! A1 a" A2 i B1 a" B2
a" a" a"
a" a" a"
a" a" a"
" Typy złożone  unie (T = A1 + B1 i S = A2 + B2)
T a" S Ô! (A1 a" A2 i B1 a" B2) lub (A1 a" B2 i B1 a" A2)
a" a" a" a" a"
a" a" a" a" a"
a" a" a" a" a"
Równoważność typów  strukturalna
Równoważność typów  strukturalna
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 Punkt {int x,y,z}
struct Data {int dzien, miesiac, rok}
void pokaz(struct Data d);
Równoważność typów  wg nazwy
Równoważność typów  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