Antoni M. Zaj czkowski: Algorytmy i podstawy programowania – ogólne jednostki programowe

25 maja 2009

1

O

GÓLNE JEDNOSTKI PROGRAMOWE

Pami tamy, e w Adzie typy parametrów formalnych i aktualnych funkcji i procedur musz

by zgodne. Oznacza to, e podprogram realizuj cy ten sam algorytm dla dwóch ró nych ty-

pów danych musi by napisany dwukrotnie – dla ka dego z typów osobno.

Przykład.

(

Feldman, Koffman, 1996

).

We my pod uwag nast puj c procedur :

procedure

Exchange (Element_1, Element_2 :

in out

Natural)

is

Temp : Natural;

begin

Temp := Element_1;
Element_1 := Element_2;
Element_2 := Temp;

end

Exchange;

Procedura ta wymienia warto ci dwóch zmiennych typu Natural. Je eli chcemy wymieni
wielko ci typu Float, to musimy napisa drug procedur :

procedure

Exchange (Element_1, Element_2 :

in out

Float)

is

Temp : Float;

begin

Temp := Element_1;
Element_1 := Element_2;
Element_2 := Temp;

end

Exchange;

Zauwa my, e procedury te s identyczne z wyj tkiem typów danych na jakich wykonywane

s te same instrukcje. W przypadku, gdy chcemy wymieni warto ci zmiennych innego typu
mo emy napisa kolejn procedur Exchange itd. Wszystkie procedury wymiany mo emy

zamkn w pewnym pakiecie bibliotecznym, ale nie jest to eleganckie i niezawodne rozwi -

zanie. W sytuacji, gdy program kliencki importuje jedn z procedur wymiany z tego pakietu i

oka e si , e procedura ta ma bł d, powinni my sprawdzi czy inne procedury tego pakietu s

poprawne. Lepiej napisa jedn

procedur ogóln (

generic

) wymieniaj c warto ci pewnego

typu Element_Type, który ma tylko nazw i nie ma konkretnej reprezentacji. W tym

rozwi zaniu procedura mo e mie posta :

procedure

Generic_Exchange (Element_1, Element_2 :

in out

Element_Type)

is

Temp : Element_Type;

begin

Temp := Element_1;
Element_1 := Element_2;
Element_2 := Temp;

end

Generic_Exchange;

Oczywi cie, procedura ta mo e nazywa si jak poprzednie procedury, natomiast nazwa u yta
tutaj podkre la fakt, e procedura Generic_Exchange jest przepisem, recept , albo

wzor-

cem (

template

), a nie procedur gotow do wymiany dwóch elementów dowolnego typu.

Klient procedury ogólnej musi j przystosowa , czyli dokona

konkretyzacji (

instantiation

)

do u ywanego przez niego typu danych.
1. Typy jako parametry formalne jednostki ogólnej
Kompilator musi mie informacje, e procedura Generic_Exchange jest wzorcem, który

dopiero po konkretyzacji mo e wymienia warto ci konkretnego typu. W celu powiadomienia

kompilatora o tym, e procedura ta jest procedur ogóln w tre ci programu umieszczamy

sekcj ogóln , w której podajemy nazw typu b d cego typem parametrów tej procedury

oraz podajemy jej nagłówek, a nast pnie cał jej deklaracj . Mo emy wi c napisa

-- Specification of the generic exchange procedure

Antoni M. Zaj czkowski: Algorytmy i podstawy programowania – ogólne jednostki programowe

25 maja 2009

2

generic

type

Element_Type

is private

;

procedure

Generic_Exchange

(Element_1, Element_2 :

in out

Element_Type);

procedure

Generic_Exchange (Element_1, Element_2 :

in out

Element_Type)

is

Temp : Element_Type;

begin

Temp := Element_1;
Element_1 := Element_2;
Element_2 := Temp;

end

Generic_Exchange;

Kompilacja sekcji ogólnej generuje kod gotowy do jej konkretyzacji w programie klienckim,

lub w dalszej cz ci naszego programu, w którym istnieje taka sekcja.
W przypadku typów Natural i Float odpowiednie konkretyzacje mog mie posta

procedure

Exchange_Natural

is new

Generic_Exchange

(Element_Type => Natural);

procedure

Exchange_Float

is new

Generic_Exchange

(Element_Type => Float);

W programie sekcja ogólna i tre procedury ogólnej znajduj si w cz ci deklaracyjnej pro-

gramu przed deklaracjami innych podprogramów.
Drugim, bardziej uniwersalnym rozwi zaniem jest umieszczenie procedury ogólnej w pakie-
cie, którego cz

publiczna zawiera identyfikator typu Element_Type i nagłówek proce-

dury.

Program.

Test_Generic_Exchange_Program.

Pakiety.

Exchange.ads, Exchange.adb.

Program.

Test_Generic_Exchange_Client.

Zadanie.

Czy typ prywatny Element_Type zadeklarowany w sekcji ogólnej jako prywatny

(

private

) mo e by typem prywatnym ograniczonym (

limited private

)? Uzasadnij

odpowied .
Mo emy teraz poda definicj jednostki ogólnej.
D

EFINICJA

. Jednostka ogólna (

generic unit

) jest wzorcem podprogramu, albo pakietu. Jed-

nostka ta deklarowana jest z parametrami formalnymi, którymi mog by typy danych, lub

identyfikatory podprogramów.
2. Podprogramy jako parametry formalne jednostki ogólnej
We my pod uwag funkcj obliczaj c warto wi kszego z dwóch jej argumentów typu
Integer

.

function

Maximum (A, B : Integer)

return

Integer

is

Result : Integer;

begin

if

A > B

then

Result := A;

else

Result := B;

end if

;

end

Maximum;

Chcemy napisa funkcj ogóln obliczaj c warto wi kszego z dwóch jej argumentów, nie-

zale nie od tego jakiego s typu. Mo emy oczywi cie u y ogólnego typu parametrów for-

malnych, aby poinformowa kompilator o tym, e konkretyzacja mo e dotyczy dowolnego

typu. Nie jest to jednak informacja wystarczaj ca, poniewa nie wszystkie typy, które mog
konkretyzowa nasz funkcj Maximum, maj zdefiniowan wst pnie relacj wi kszo ci wy-

Antoni M. Zaj czkowski: Algorytmy i podstawy programowania – ogólne jednostki programowe

25 maja 2009

3

korzystywan w cz ci operacyjnej tej funkcji. Mo emy napisa funkcj implementuj c po-

trzebn relacj w przypadku konkretnego typu, ale kompilator musi mie informacj , e ma t

funkcj zastosowa . W tym celu w sekcji ogólnej umieszcza si informacj , e potrzebna

funkcja istnieje. W zwi zku z tym, piszemy:

generic

type

Element_Type

is private

;

with

function

Greater(L, R : Element_Type)

return

Boolean;

function

Maximum (A, B : Element_Type)

return

Element_Type;

function

Maximum (A, B : Element_Type)

return

Element_Type

is

Result : Element_Type;

begin

if

Greater(A, B)

then

Result := A;

else

Result := B;

end if

;

end

Maximum;

Konkretyzacja tej funkcji w przypadku typu standardowego Float mo e mie posta

function

Maximum_Float

is new

Maximum (Element_Type => Float, Greater => ">");

Program.

Compute_Maximum.

Zajmijmy si teraz nieco trudniejszym zagadnieniem. Chcemy napisa program, który znaj-

duje element ekstremalny w tablicy jednowymiarowej, przy czym indeksy tablicy mog by

dowolnego typu dyskretnego, a elementy s dowolnego typu nieograniczonego (nie s typu

limited private

). W tym celu tworzymy sekcj ogóln

generic

type

Element_Type

is private

;

-- Any unlimited type

type

Index_Type

is

(<>);

-- Any discrete type

type

Array_Type

is array

(Index_Type

range

<>)

of

Element_Type;

with

function

Order_Relation(L, R : Element_Type)

return

Boolean;

Szukanie elementu ekstremalnego wymaga porównywania elementów tablicy i dlatego

musimy powiadomi kompilator o tym, e b dzie stosowana odpowiednia funkcja, która

obliczy relacj dwóch elementów.
Musimy jeszcze poda nagłówek funkcji wyznaczaj cej element ekstremalny. Mo e on mie

nast puj c form :

function

Array_Extremum (List : Array_Type)

return

Element_Type;

Sekcja ogólna zawiera ju wszystko czego potrzeba. Teraz trzeba zadeklarowa funkcj

implementuj c algorytm poszukiwania elementu ekstremalnego.

function

Array_Extremum (List : Array_Type)

return

Element_Type

is

Result : Element_Type := List(List’First);

begin

for

I

in

List’

range

loop

if

Order_Relation(List(I), Result)

then

Result := List(I);

end if

;

end loop

;

retutn

Result;

end

Array_Extremum;

Zadanie.

Dlaczego typ Element_Type nie mo e by typem ograniczonym?

W celu sprawdzenia, czy nasz algorytm poprawnie działa w ró nych sytuacjach deklarujemy

nast puj ce typy:

type

Real_Vector

is array

(Integer

range

<>)

of

Float;

subtype

Large_Letter

is

Character

range

'A'..'Z';

Antoni M. Zaj czkowski: Algorytmy i podstawy programowania – ogólne jednostki programowe

25 maja 2009

4

type

Large_Letter_Vector

is array

(Positive

range

<>)

of

Large_Letter;

Zauwa my, e typy tablicowe okre laj tablice otwarte o konkretnych typach indeksów.

Podobnie, konkretne s typy elementów tablic, które s typami standardowymi dzi ki czemu

nie musimy pisa własnych funkcji do porównywania egzemplarzy tych typów.
Pozostała nam jeszcze konkretyzacja funkcji znajduj cej ekstrema. Mo emy napisa :

function

Array_Extremum_Float

is new

Array_Extremum

(Index_Type => Integer, Element_Type => Float,

Array_Type => Real_Vector, Order_Relation => ">=");

function

Array_Extremum_Large_Letter

is new

Array_Extremum

(Index_Type => Positive, Element_Type => Large_Letter,

Array_Type => Large_Letter_Vector, Order_Relation => "<=");

Program.

Generic_Array_Extremum