Antoni M. Zajączkowski: Algorytmy i podstawy programowania ogólne jednostki programowe 25 maja 2009 OGÓ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). Wezmy 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 1 Antoni M. Zajączkowski: Algorytmy i podstawy programowania ogólne jednostki programowe 25 maja 2009 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 odpowiedz. Możemy teraz podać definicję jednostki ogólnej. DEFINICJA. 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 Wezmy 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- 2 Antoni M. Zajączkowski: Algorytmy i podstawy programowania ogólne jednostki programowe 25 maja 2009 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'; 3 Antoni M. Zajączkowski: Algorytmy i podstawy programowania ogólne jednostki programowe 25 maja 2009 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 4