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.