Antoni M. Zaj czkowski: Algorytmy i podstawy programowania – abstrakcyjne typy danych
5 kwietnia 2009
1
A
BSTRAKCYJNE TYPY DANYCH
Abstrakcja danych (
data abstraction
) polega na tym, e typ danych jest rozumiany jako
struktura składaj ca si ze zbioru warto ci, do którego nale dane i podstawowych operacji,
które mog by wykonywane na elementach tego zbioru (
Feldman, Koffman, 1996
). Z poda-
nego okre lenia wynika, e wprowadzona wcze niej definicja typu danych jest definicj
abs-
trakcyjnego typu danych (
ADT – abstract data type
).
Najwa niejsz własno ci abstrakcji danych jest udost pnianie operacji na danych, przy
jednoczesnym ukryciu szczegółów ich reprezentacji i szczegółów implementacji operacji
zdefiniowanych dla tych danych.
Program korzystaj cy z abstrakcyjnego typu danych nazywamy
programem klienckim
(
client program
), albo krótko
klientem (
client
). W programie tym mo na deklarowa obiekty
i u ywa operacji zdefiniowanych dla tego typu.
Stosuj c
ukrycie informacji (
information hiding
) osi ga si separacj wykorzystania typu
w programie klienckim od
reprezentacji typu (
type representation
) i
implementacji opera-
cji (
operation implementation
). Dzi ki temu program kliencki mo e by opracowany nieza-
le nie od abstrakcyjnego typu danych.
1. Struktura abstrakcyjnego typu danych
Zazwyczaj
abstrakcyjny typ danych (ATD) jest typem strukturalnym, najcz ciej typem
rekordowym. W ród operacji definiowanych dla ATD wyró nia si cztery wa ne grupy tych
operacji (
Feldman, Koffman, 1996
):
-
Konstruktory (
constructors
), które tworz lub konstruuj obiekty typu abstrakcyj-
nego ł cz c składowe typu w jedn cało ,
-
Selektory (
selectors
), które udost pniaj składowe obiektu typu abstrakcyjnego,
-
Zapytania (
inquiries
), które słu do stwierdzenia, czy obiekt typu abstrakcyjnego
posiada pewn własno ,
-
Operacje wej cia/wyj cia (
input/output operations
) słu ce do wprowadzania i
wyprowadzania warto ci obiektu typu abstrakcyjnego na zewn trz.
W Adzie istnieje kilka mechanizmów i poj pozwalaj cych na implementacj i stosowa-
nie ATD. Wyró niamy tu:
- Podtypy,
- Inicjowanie pól rekordów, czyli nadawanie warto ci pocz tkowych (domy lnych)
składowym rekordu przy deklaracji typu rekordowego,
- Pakiety,
- Typy prywatne,
- Przeci anie operatorów,
- Definiowanie i obsługa wyj tków,
- Atrybuty,
- Definicje ogólne.
Dotychczas poznali my podtypy, typy rekordowe, atrybuty, pakiety i przeci anie
operatorów, a teraz zajmiemy si typami prywatnymi.
2. Typy prywatne
W programie klienckim dane typu abstrakcyjnego powinny by u ywane w odpowiedni
sposób. W Adzie do bezpiecznego udost pnianiu abstrakcyjnego typu danych klientowi
przez pakiet słu
typy prywatne (
private types
). Typy tego rodzaju opisuj stopie widzial-
no ci typu pomi dzy klientem, a pakietem udost pniaj cym typ.
W przypadku typu prywatnego program kliencki dysponuje jedynie zdefiniowan wst p-
nie operacj podstawienia := i zdefiniowan wst pnie relacj równo ci = i jej negacj , czyli
Antoni M. Zaj czkowski: Algorytmy i podstawy programowania – abstrakcyjne typy danych
5 kwietnia 2009
2
relacj nierówno ci /=. Pozostałe operacje wykonywane na danych typu prywatnego musza
by zdefiniowane i udost pnione w cz ci publicznej pakietu definiuj cego typ prywatny.
Przykład.
Pakiet definicyjny Wektory_2D. Program Test_Wektory_2D
.
Na pocz tku tego pakietu mamy deklaracj
type
Wektor_2D
is private
;
która definiuje typ prywatny o nazwie Wektor_2d, przy czym istotne jest to, e deklaracja
ta nie zawiera opisu typu, który znajduje si w cz ci prywatnej pakietu Cz
ta wyst puje
po słowie kluczowym
private
. W ten sposób pakiet podzielony jest na dwie cz ci:
pu-
bliczn – do słowa
private
i
prywatn – od tego słowa do ko cz cego tre pakietu
słowa
end
. Typ Wektor_2D słu y do reprezentacji wektorów znanych w elementarnej
geometrii analitycznej na płaszczy nie, a wi c wektorów o pocz tku w pocz tku kartezja -
skiego układu współrz dnych i o ko cu w punkcie reprezentowanym przez par uporz dko-
wan liczb rzeczywistych. Po deklaracji typu prywatnego mamy deklaracj stałej Zero, re-
prezentuj cej wektor zerowy, przy czym deklaracja ta jest niepełna, bo nie zawiera warto ci
stałej. Uzupełnienie deklaracji stałej znajdujemy w cz ci prywatnej, gdzie po podaniu
wszystkich szczegółów reprezentacji typu prywatnego mo na nada warto stałej, zgodnie z
t reprezentacj . Stał tego rodzaju nazywamy
stał odło on (
deferred constant
).
Warto podkre li , e klient pakietu nie ma udost pnionych szczegółów reprezentacji typu
prywatnego i w zwi zku z tym, w programie klienckim nie mo na deklarowa stałych tak,
jak zrobiono to w cz ci prywatnej pakietu.
Pakiet słu y do implementacji struktury rzeczywistej przestrzeni wektorowej w zbiorze
wektorów dwuelementowych. W tym celu cz
publiczna zawiera nagłówki funkcji + i *,
które realizuj odpowiednio dodawanie wektorów i mno enie wektorów przez skalary z ciała
liczb rzeczywistych. Zwró my uwag na to, e mamy dwie funkcje realizuj ce mno enie
lewo i prawostronne. Kompilator analizuj c wyra enia, w których wywołano te funkcje roz-
pozna jaka jest kolejno argumentów mno enia i zastosuje wła ciwy kod. Dzi ki temu
klient nie musi dba o kolejno argumentów mno enia wektorów przez skalary.
Poza tym, pakiet udost pnia dwie operacje wej cia/wyj cia w postaci procedur Czy-
taj_Wektor_2D
i Wypisz_Wektor_2D. Pierwsza z tych procedur jest jednocze nie
konstruktorem danych typu Wektor_2D, natomiast pakiet nie zawiera zapyta i selektorów.
Zwró my uwag na wa n własno ukrycia szczegółów reprezentacji typu Wektor_2D
przed programem klienckim. W sytuacji, gdy z jakich powodów zostanie zmieniona pełna
deklaracja tego typu oraz wynikaj cy z tego sposób warto ciowania stałej Zero, to program
kliencki nie zmieni si , mimo e importowa b dzie zmodyfikowany pakiet Wektory_2D.
Oczywi cie przy zmianie deklaracji typu Wektor_2D musi zosta odpowiednio zmodyfi-
kowana cz
implementacyjna pakietu.
W programie klienckim pakietu udost pniaj cego typ prywatny mo na deklarowa stałe i
zmienne tego typu w zwykły sposób, przy czym stałym nie mo na nadawa warto ci, a
zmiennym nadawa warto ci pocz tkowych lub zmienia ich warto ci odwołuj c si do
szczegółów reprezentacji typu prywatnego. W zwi zku z tym, otrzymamy bł d kompilacji
pisz c
A : Wektor_2D := (1 => 0.0, 2 => 0.0);
natomiast legalna jest deklaracja
A : Wektor_2D := Zero;
Zadanie.
Napisa funkcje First_Component i Second_Component obliczaj ce
odpowiednio pierwsz i drug składow wektora typu Wektor_2D. Zało y przy tym, e
pełna deklaracja tego typu ma posta
type
Wektor_2D
is record
First : Float;
Second : Float;
Antoni M. Zaj czkowski: Algorytmy i podstawy programowania – abstrakcyjne typy danych
5 kwietnia 2009
3
end record
;
Zadanie.
Przyjmuj c definicj typu Wektor_2D jak w poprzednim zadaniu, napisa
funkcje Constructor_2D, "+", "*", "*" słu ce odpowiednio do: konstrukcji wektora
z jego składowych, obliczania sumy dwóch wektorów i obliczania iloczynu wektora przez
skalar rzeczywisty.
Zadanie.
Przyjmuj c definicj typu Wektor_2D jak w poprzednim zadaniu, napisa
pełne deklaracje stałych Zero, Wersor_1 i Wersor_2, które reprezentuj odpowiednio
wektory:
,
,
.
Obiekty zadeklarowane w cz ci prywatnej pakietu definicyjnego dost pne s w cz ci
implementacyjnej. Dotyczy to na przykład stałej Zero z naszego pakietu Wektory_2D.
W ten sposób doszli my do tego, e pakiet abstrakcji danych mo na ogólnie podzieli na trzy
logiczne cz ci
1
(
Feldman, Koffman, 1996
):
1.
Cz widoczn (
visible part
) dla klienta pakietu okre laj c logiczny interfejs pomi -
dzy pakietem, a klientem,
2.
Cz prywatn (
private part
) okre laj c ten interfejs fizycznie,
3.
Cz implementacyjn (
implementation part
), która zawiera szczegóły implementa-
cyjne.
W cz ci widocznej dla klienta nie mo na deklarowa zmiennych typu prywatnego i
alokowa pami ci dla danych tego typu, ale mo na deklarowa typy, podtypy i nagłówki
podprogramów z parametrami typu prywatnego.
3. Typy prywatne ograniczone
W niektórych zastosowaniach zdefiniowana wst pnie i udost pniana klientowi relacja
równo ci danych typu prywatnego mo e by nieodpowiednia.
We my dla przykładu pod uwag ułamki tworz ce zbiór liczb wymiernych. Je eli
zdefiniujemy typ Ulamek nast puj co:
type
Ulamek
is private
;
private
type
Ulamek
is record
Licznik : Integer;
Mianownik : Integer;
end record
;
i je eli w programie klienckim zadeklarujemy zmienne
A, B : Ulamek;
a nast pnie przy pomocy konstruktora typu Ulamek nadamy im warto ci
i
, to
relacja A = B jest fałszywa (porównaj definicj danych typu rekordowego), natomiast z
matematyki wiadomo (
Birkhoff, Mac Lane, 1960, 45
), e
.
Okazuje si , e w przypadku ułamków lepiej zdefiniowa własn relacj równo ci. Mo-
emy w tym celu wykorzysta twierdzenie mówi ce (
Birkhoff, Mac Lane, 1960, 45
), e dwa
ułamki
i
(
i
) s równe wtedy i tylko wtedy, gdy
.
Zadanie.
Napisa funkcj "=" obliczaj c warto relacji równo ci dla danych typu
Ulamek
zdefiniowanego powy ej.
Zadanie.
Napisa funkcj realizuj c skracanie ułamka przez najwi kszy wspólny dziel-
nik licznika i mianownika. W tym celu napisa osobn funkcj NWD obliczaj c najwi kszy
wspólny dzielnik dwóch liczb całkowitych.
Zadanie.
Napisa konstruktor danych typu Ulamek.
1
S one jednak umieszczone w dwóch plikach - Nazwa.ads, Nazwa.adb
Antoni M. Zaj czkowski: Algorytmy i podstawy programowania – abstrakcyjne typy danych
5 kwietnia 2009
4
Poniewa zdefiniowana wst pnie relacja równo ci nie zawsze jest odpowiednia dla da-
nych typu abstrakcyjnego, mo emy w uzasadnionych przypadkach zadeklarowa typ abs-
trakcyjny jako typ
prywatny ograniczony (
limited private type
). W takim przypadku nie ma
zdefiniowanych wst pnie adnych operacji, a wi c nawet instrukcji podstawienia i wspo-
mnianej ju relacji równo ci. Wszystkie potrzebne operacje na danych typu prywatnego
ograniczonego musz by zdefiniowane jako odpowiednie podprogramy udost pniane
klientowi.
Deklaracja typu prywatnego ograniczonego wygl da nast puj co:
type
Identyfikator_Typu
is limited private
; -- cz
publiczna
private
type
Identyfikator_Typu
is
Opis_Typu; -- cz
prywatna
Przykład.
Pakiet definicyjny Wektory_2_Wymiarowe.
Program Test_Wektory_2_Wymiarowe.
4. Typy pochodne i operacje podstawowe
Czasami chcemy wprowadzi nowy typ podobny do istniej cego, ale ró ny od niego.
Je eli T jest istniej cym typem, to mo emy napisa
type
S
is new
T;
W takim przypadku S nazywamy
typem pochodnym (
derived type
), a typ T nazywamy
typem macierzystym (
parent type
) typu S. Mówimy czasami, e typ pochodny
nale y do
tej samej klasy co typ macierzysty.
Oznacza to mi dzy innymi, e zapis literałów i agregatów jest taki sam, oraz domy lne
wyra enia pocz tkowe typu pochodnego, albo jego składowych s takie same jak w przy-
padku typu macierzystego. W szczególno ci je eli typ macierzysty jest typem rekordowym,
to typ pochodny jest te typem rekordowym, a jego składowe maj te same identyfikatory.
Zbiór warto ci typu pochodnego jest kopi zbioru warto ci typu macierzystego, ale typy te
s ró ne i nie mo na warto ci jednego typu przypisywa obiektom drugiego typu. Konwersja
mi dzy danymi tych ró nych typów jest jednak mo liwa.
Operacjami podstawowymi nazywamy nast puj ce operacje:
- Zdefiniowane wst pnie operacje takie jak podstawienie, relacja równo ci, odpowied-
nie atrybuty,
- W przypadku typu pochodnego, operacje podstawowe odziedziczone po typie
macierzystym, które mog by jednak zast pione przez operacje zdefiniowane na
nowo,
- W przypadku typu zadeklarowanego w pakiecie definicyjnym, podprogramy
zadeklarowane w tym pakiecie, posiadaj ce parametry formalne lub wynik zadeklaro-
wanego typu.
Warto wspomnie , e warto ci typu wyliczeniowego te s zaliczane do operacji
podstawowych, poniewa traktowane s jak funkcje bezparametrowe o warto ciach tego typu
(
Barnes, 1998
).
Przykład.
W przypadku typu Boolean, literały False i True s operacjami podstawo-
wymi, poniewa traktowane s jakby były funkcjami takimi jak
function
True
return
Boolean
is
begin
return
Boolean'Val(1);
end
;
Ogólna idea jest taka, e typ pochodny posiada pewne operacje podstawowe, dziedziczone
po typie macierzystym i mo na do zbioru tych operacji doda nowe operacje podstawowe.
Antoni M. Zaj czkowski: Algorytmy i podstawy programowania – abstrakcyjne typy danych
5 kwietnia 2009
5
Przykład.
Pakiet definicyjny Wektory_Na_Plaszczyznie.
Program Test_Wektory_Na_Plaszczyznie.
Wspomnieli my ju , e operacje dziedziczone mog by zast pione przez nowe operacje.
Rozumiemy przez to zast pienie operacji dziedziczonych przez jawnie zadeklarowane pod-
programy o tych samych identyfikatorach jak podprogramy nale ce do zbioru operacji pod-
stawowych typu macierzystego, przy czym podprogramy zast puj ce musz by zadeklaro-
wane w tym samym obszarze deklaracji, w którym definiowany jest typ pochodny.
Deklaruj c typ pochodny nale y przestrzega dwóch zasad (
Barnes, 1998
):
1. Nie mo na tworzy typu pochodnego z typu prywatnego przed podaniem pełnej
deklaracji tego typu.
2. Je eli tworzymy typ pochodny w tym samym pakiecie definicyjnym, w którym
deklarujemy typ macierzysty, to typ pochodny dziedziczy wszystkie operacje po typie
macierzystym i nie mo na doda nowych operacji do typu macierzystego po deklaracji
typu pochodnego.
Mimo e, ka dy typ pochodny jest ró ny, to dzi ki pokrewie stwu typów pochodnych
wyprowadzonych od wspólnego przodka, warto jednego typu pochodnego mo na łatwo za-
mieni na warto innego typu powstałej klasy.
Przykład
(
Barnes, 1998
). Niech b d dane deklaracje:
type
Light
is new
Colour;
type
Signal
is new
Colour;
type
Flare
is new
Signal;
Typy te tworz pewn hierarchi typów, która zaczyna si od typu Colour. Mo emy
swobodnie dokonywa konwersji warto ci tych typów. Na przykład mo emy pisa :
L : Light;
F : Flare;
...
F := Flare(L);
Ostatnia instrukcja jest legalna i nie musimy pisa :
F := Flare(Signal(Colour(L)));
Wprowadzenie typów pochodnych rozszerza mo liwo ci konwersji typów tablicowych.
Warto typu tablicowego mo e by zamieniona na now warto innego typu tablicowego,
je eli podtypy składowych s statycznie zgodne, a typy indeksów s identyczne, albo mog
by konwertowane jeden na drugi.
Powstaje pytanie o korzy ci płyn ce z wprowadzenia typów pochodnych. Jednym z istot-
nych powodów jest unikanie mieszania obiektów koncepcyjnie nale cych do ró nych ty-
pów.
Przykład
(
Barnes, 1998
). Załó my, e chcemy liczy jabłka i pomara cze. W zwi zku z
tym mo emy napisa
type
Apples
is new
Integer;
type
Oranges
is new
Integer;
...
No_Of_Apples : Apples;
No_Of_Oranges : Oranges;
Obydwa typy s typami pochodnymi typu Integer, a wi c obydwa dziedzicz dwuargu-
mentow operacj dodawania, co pozwala napisa
No_Of_Apples := No_Of_Apples + 1;
No_Of_Oranges := No_Of_Oranges + 1;
Oczywi cie, nie wolno pisa
No_Of_Apples := No_Of_Oranges;
Mo emy jednak dokona konwersji
No_Of_Apples := Apples'(No_Of_Oranges);
Antoni M. Zaj czkowski: Algorytmy i podstawy programowania – abstrakcyjne typy danych
5 kwietnia 2009
6
Przypu my teraz, e mamy dwie procedury obsługuj ce sprzeda obydwu rodzajów owo-
ców.
procedure
Sell (N : Apples);
procedure
Sell (N : Oranges);
Mo emy wywoła jedn z nich
Sell (No_Of_Oranges);
natomiast wywołanie
Sell (5);
jest niejednoznaczne. W celu unikni cia tej niejednoznaczno ci trzeba pisa
Sell (Oranges'(5));
Je eli podprogram jest dziedziczony, to w rzeczywisto ci nie jest tworzony nowy podpro-
gram. Wywołanie odziedziczonego podprogramu jest w rzeczywisto ci wywołaniem podpro-
gramu macierzystego, przy czym parametry rodzajów
in
i
in out
s niejawnie konwerto-
wane na typ macierzysty tu przed wywołaniem, natomiast parametry rodzajów
out
i
in
out
s konwertowane niejawnie zaraz po wywołaniu.
Je eli wi c mamy wyra enie
My_Apples + Your_Apples
to w rzeczywisto ci wykonywana jest instrukcja
Apples(Integer(My_Apples) + Integer(Your_Apples))
Zajmijmy si teraz ograniczeniami. Mo emy tworzy typy pochodne ograniczone. Dla
przykładu deklaracja
type
Probability
is new
Float
range
0.0..1.0;
jest równowa na deklaracjom
type
Anonim
is new
Float;
subtype
Probability
is
Anonim
range
0.0..1.0;
Oznacza to, e podtyp Probability jest podtypem ograniczonym, anonimowego typu po-
chodnego. Zauwa my, e zbiór warto ci typu pochodnego jest kopi zbioru warto ci typu
macierzystego Float. Operacje "+", ">" i inne, działaj w całym nieograniczonym zbio-
rze warto ci.
Przykład
(
Barnes, 1998
). Niech b dzie dana deklaracja
P : Probability;
Mo na legalnie napisa
P > 2.0
mimo, e nie mo na podstawi warto ci 2.0 do zmiennej P. Wyra enie P
2.0
jest zaw-
sze nieprawdziwe, chyba e nie jest zainicjowane odpowiednio i przez przypadek ma zł
warto .
Rozpatrzymy teraz ograniczenia wyst puj ce w przypadku dziedziczonych podprogra-
mów. Podprogram odziedziczony jest podprogramem macierzystym, w którym wszystkie
eg-
zemplarze (
instance
) typu macierzystego s wymienione na typ pochodny. Podtypy s wy-
mienione na równowa ne podtypy z odpowiednimi ograniczeniami, a domy lne wyra enia
inicjuj ce s konwertowane przez dodanie konwersji typów. Dowolny parametr, albo wynik
innego typu pozostaje niezmieniony.
Przykład
(
Barnes, 1998
). Niech
type
T
is
... ;
subtype
S
is
T
range
L .. R;
function
F(X : T; Y : T := E; Z : Q)
return
S;
przy czym E jest wyra eniem typu T, natomiast Q nie nale y do klasy typu T, a wi c jest cał-
kowicie niezale ny.
Je eli napiszemy
type
TT
is new
T;
to z tego wynika, e napisali my te
subtype
SS
is
TT
range
TT(L) .. TT(R);
a nagłówek funkcji dziedziczonej F ma posta
Antoni M. Zaj czkowski: Algorytmy i podstawy programowania – abstrakcyjne typy danych
5 kwietnia 2009
7
function
F(X : TT; Y : TT := TT(E); Z : Q)
return
SS;
W nagłówku typ T został zast piony przez TT, podtyp S przez SS, dokonana została
konwersja wyra enia E na warto typu TT, natomiast typ Q pozostał niezmieniony. Warto
zauwa y , e identyfikatory parametrów formalnych pozostały takie same.
Typy pochodne pod pewnymi wzgl dami s alternatyw do typów prywatnych. Typy po-
chodne maj zalet dziedziczenia literałów, ale cz sto maj wad dziedziczenia zbyt wielu
rzeczy po typie macierzystym.
Przykład
(
Barnes, 1998
). We my pod uwag deklaracje
type
Length
is new
Float;
type
Area
is new
Float;
Wprowadzenie tych typów zabezpiecza przed mieszaniem długo ci z powierzchni , ale
dziedziczona jest mo liwo mno enia dwóch egzemplarzy typu Length, w wyniku czego
dostaniemy warto typu Length. Poza tym dziedziczymy mnóstwo nieistotnych operacji
jak na przykład pot gowanie. Takie niepo dane operacje mo na, je eli trzeba, nadpisa
podprogramami abstrakcyjnymi (
abstract subprograms
), takimi jak
function
"*" (Left, Right : Length)
return
Length
is abstract
;
Podprogram abstrakcyjny nie ma tre ci i nie mo na go wywoła . Ka da taka próba jest
wykrywana podczas kompilacji.
Je eli jest wiele niepo danych operacji dziedziczonych po typie macierzystym, cz sto le-
piej u y typu prywatnego i zdefiniowa te operacje których potrzebujemy.
Zadanie
(
Barnes, 1998, 222
). Zadeklarowa pakiet Metrics zawieraj cy deklaracje
typów pochodnych Length i Area wraz z odpowiednimi nagłówkami ró nych operacji
"*"
, "/", "**".
Zadanie obliczeniowe.
Napisa pakiet implementuj cy ciało liczb wymiernych. Liczby
wymierne maj by reprezentowane jako pary uporz dkowane liczb całkowitych. Pakiet ma
udost pnia funkcje realizuj ce operacje arytmetyczne oraz relacje wykonywane na
ułamkach. Nale y te napisa podprogramy tworz ce i wypisuj ce ułamki. W pakiecie
mo na wykorzysta NWD w celu skracania licznika i mianownika przez ich najwi kszy
wspólny dzielnik. Działanie pakietu zilustrowa przy pomocy programu klienckiego.
L
ITERATURA
Barnes, J. (1998). Programming in Ada 95. Addison Wesley, Reading Massachusetts.
Beidler, J. (1997). Data structures and algorithms. An object-oriented approach using Ada
95. Springer, New York.
Birkhoff, G. i S. Mac Lane. (1960). Przegl d algebry współczesnej. PWN, Warszawa
(tłum. z ang.)
Feldman M. B. i E. B. Koffman, (1996). Ada 95 Problem Solving and Program Design.
Addison-Wesley, Reading Massachusetts.