Paradygmaty programowania/Wykład 3: Typy, typy abstrakcyjne

From Studia Informatyczne

Spis treści

Wstęp

W najprostszym ujęciu typ to pewien ustalony zbiór wartości (w domyśle: które mogą być przyjmowane przez zmienne). W praktyce z każdym typem związany jest zbiór operacji, które można wykonywać na wartościach z tego typu. Tak postawiona definicja bliska jest klasycznemu pojęciu zbioru — z konieczności skończonego, gdyż pamięć mamy skończoną... Dozwolone operacje to wszystkie operatory (w szerokim rozumieniu, czyli również podprogramy, podstawienia itp.), których dziedziną jest ów typ lub typ z nim zgodny (tu zgodność można rozumieć jako zawieranie).

Przykładowo, niemal w każdym języku występuje podstawowy typ całkowity (int, integer). Jest to skończony podzbiór zbioru liczb całkowitych, na ogół odpowiadający zakresowi liczb, jakie można przechowywać w jednym słowie danego komputera. Dozwolone operacje to np. dodawanie, odejmowanie, mnożenie, dzielenie.

Mówiąc o dozwolonych operacjach w szerszym ujęciu należałoby też wymienić m.in. podstawienie pod zmienną, przekazanie jako parametr, sprawdzanie równości (czy x = y?), sprawdzanie relacji porządku (czy x < y?), wybór elementu składowego tablicy lub struktury/rekordu. Możliwość podstawienia wartości pod zmienną wcale nie jest oczywista. W niektórych językach nie można np. podstawiać ani porównywać tablic i jedyna dozwolona operacja to wybór elementu. Zauważmy, że składanie istniejących operacji prowadzi do nowych operacji, które także można stosować. Zauważmy również, że podobieństwa operacji bywają niekiedy mylące. Dzielenie liczb całkowitych i dzielenie zmiennopozycyjne to różne operacje, nawet po zawężeniu do wspólnej dziedziny („całkowite 3/2” to 1, zaś „zmiennopozycyjne 3/2” to półtora).

Zanim przejdziemy do problemów implementacyjnych, przedstawimy kilka kwestii dotyczących typów.

Tworzenie nowych typów

  • Typ pierwotny to taki, którego w danym języku nie da się zdefiniować za pomocą innych typów.
  • Większość języków posiada pewien zestaw typów pierwotnych, np. char, int, float.
  • Z typów pierwotnych można tworzyć typy złożone, np. rekordy, tablice.
  • Można tworzyć typy wyliczeniowe, czyli listy stałych. Ich ważną cechą jest to, że definiując typ jednocześnie określamy liniowy porządek na nim.
  • Jest wreszcie mechanizm tworzenia podtypów i typów pochodnych.
  • Powyższe mechanizmy to klasyka języków imperatywnych zapoczątkowana przez Algol.

Przy tworzeniu nowych typów łatwo widać analogie do operacji na zbiorach

  • Rekord to iloczyn kartezjański typów składowych.
  • Tablica to iloczyn kartezjański odpowiedniej liczby egzemplarzy tego samego typu.
  • Typ wyliczeniowy to po prostu zbiór zawierający wskazane elementy (choć w istocie definiujemy coś więcej: porządek).
  • Podtyp jakiegoś typu to jego podzbiór.
  • Typ pochodny to „kopia typu pod inną nazwą”. Tutaj analogia jest niezbyt trafna, gdyż — inaczej niż w teorii mnogości — o tożsamości typu decyduje nie tylko jego „treść”, ale i nazwa.

Po co są typy?

  • Na poziomie maszynowym wszelkie dane zapisane są jako układy bitów, niezależnie od tego, co reprezentują.
  • Typy są sposobem na nadanie znaczenia tym „anonimowym” układom bitów.
  • Dzięki temu zyskujemy możliwość wykrywania wielu powszechnych błędów (przez sprawdzanie zgodności typów).
  • Dodatkową korzyścią może być optymalizacja kodu przez kompilator, który np. zna zakresy liczb i może wybrać bardziej efektywną reprezentację.
  • Typy abstrakcyjne są sposobem na modularyzację programów.

Abstrakcyjne typy danych

  • Typ abstrakcyjny to konstrukcja języka programowania, w której definiujemy typ (w dotychczasowym rozumieniu) oraz operacje na nim w taki sposób, że inne byty w programie nie mogą manipulować danymi inaczej niż za pomocą zdefiniowanych przez nas operacji.
  • Istotą rzeczy jest tu oddzielenie części „prywatnej” typu (czyli szczegółów reprezentacji danych i implementacji poszczególnych operacji) od części „publicznej” (tego, co można wykorzystywać w innych miejscach programu).
  • Ta koncepcja stała się podstawą rozwoju programowania obiektowego: instancje abstrakcyjnych typów danych (czyli konkretne wartości z typów, zwane obiektami) można postrzegać jako samodzielne byty, które współdziałają poprzez wykonywanie udostępnianych sobie operacji.
  • Do szczegółów wrócimy później.

Przykłady

  • Wbudowane w języki programowania typy pierwotne można uznać za abstrakcyjne: nie mamy dostępu do reprezentacji wewnętrznej, więc możemy posługiwać się jedynie tym, co dostarcza język.
  • Zdefiniowany przez programistę w Pascalu typ rekordowy i kilka procedur na nim działających nie stanowi abstrakcyjnego typu danych. Ktokolwiek zadeklaruje rekord tego typu, będzie mógł działać bezpośrednio na tym rekordzie z pominięciem „oficjalnych” procedur.
  • Sztandarowy przykład to klasa np. z Javy lub C++. Dane schowane w części prywatnej klasy nie są dostępne na zewnątrz, stąd nie da się wykonywać żadnych operacji bezpośrednio.

Pierwotne typy danych

  • Są to na ogół typy odzwierciedlające cechy sprzętu.
  • Podstawowy pierwotny typ całkowity (int, integer) odpowiada zazwyczaj takiemu zakresowi liczb, jaki mieści się w jednym słowie maszyny.
  • Podstawowy typ całkowity miewa warianty różniące się rozmiarem (byte, short, long) i dopuszczaniem znaku, tzn. liczb ujemnych (signed/unsigned).
  • Pierwotne typy zmiennopozycyjne (float, double) to obecnie prawie zawsze typy obsługiwane sprzętowo, zgodne ze standardem IEEE 754.
  • Pierwotne typy znakowe (char, character) przez długie lata wykorzystywały kodowanie ASCII; obecnie coraz częściej używany jest Unicode.
  • Pierwotny typ logiczny (boolean) jest kodowany za pomocą pojedynczych bitów (co jest oszczędne pamięciowo, ale wolniejsze w dostępie) lub całych bajtów.
  • Występują również pierwotne typy stałopozycyjne (zwykle zwane decimal), czyli liczby z ustaloną w deklaracji liczbą cyfr i liczbą miejsc po przecinku. Typy takie dobrze nadają się do obliczeń finansowych, pozwalając uniknąć niektórych problemów z zaokrągleniami charakterystycznych dla typów zmiennopozycyjnych. Inne zastosowanie to obliczenia na urządzeniach pozbawionych sprzętowej obsługi liczb zmiennopozycyjnych, np. przenośne urządzenia do gier.

Problemy implementacyjne dla różnych typów

Typy napisowe



Typ napisowy może być typem pierwotnym

  • Tak jest np. w Javie (klasa String).
  • W wielu językach, np. w C, napisy są szczególnym rodzajem tablic (a więc nie są typem pierwotnym).

Są różne możliwości obsługi napisów o zmiennej długości

  • Napisy statyczne, czyli po zadeklarowaniu nie można zmienić długości napisu, np. obiekty z klasy String w Javie.
  • Napisy dynamiczne o długości ograniczonej statycznie. Deklarujemy napis z górnym ograniczeniem na długość, np. tablica znakowa w C.
  • Napisy w pełni dynamiczne, czyli długość może zmieniać się bez ograniczeń, np. w Perlu.
  • Ada pozwala stosować wszystkie trzy rodzaje napisów.

Sposób implementacji napisów dynamicznych istotnie wpływa na ich zachowanie

  • Reprezentacja taka jak w języku C (kolejne znaki zapisane w tablicy, ze znakiem o kodzie zero na końcu) jest prosta, ale ma poważne wady: żeby poznać długość napisu, trzeba przejrzeć go od początku do końca.
  • Inny typowy sposób to pamiętanie osobno bieżącej długości napisu.
  • Napisy w pełni dynamiczne wymagają alokowania pamięci w miarę potrzeb, co jest kosztowne.

Tablice zwykłe

Tablica to zestaw elementów takiego samego typu, gdzie dostęp do poszczególnych elementów jest poprzez indeksowanie. Wymaga to dynamicznego wyliczania adresu elementu (chyba że indeks jest stałą znaną w czasie kompilacji).

Problemy implementacyjne

  • Kiedy i skąd alokowana jest pamięć dla tablicy? Generalnie tak jak dla zwykłych zmiennych, choć języki obiektowe skłaniają się do alokowania tablic dynamicznie, ze sterty (np. Java).
  • Jakiego typu mogą być indeksy? W najpowszechniejszym przypadku są to podtypy typu (zakresu)całkowitego, ale niektóre języki dopuszczają wszelkie typy „porządkowe”, czyli dające się odwzorować na zakres liczb całkowitych: typ znakowy, typ logiczny, typy wyliczeniowe. Osobną sprawą są tablice asocjacyjne.
  • Czy indeksy są sprawdzane w czasie wykonania programu? Ada sprawdza indeksy bardzo pieczołowicie, C — wręcz przeciwnie.
  • Kiedy wiązany jest zakres (typ) indeksów? Jeśli tablica alokowana jest statycznie, to zakres indeksów oczywiście musi też być znany statycznie, np. globalna tablica w C. Niekiedy natomiast zakres indeksów może być wiązany statycznie, mimo że sama tablica jest alokowana dynamicznie, np. w Pascalu. Wreszcie i zakres, i pamięć mogą być wiązane dynamicznie, czyli wymiar tablicy może być zadany za pomocą wyrażenia wyliczanego dopiero w chwili alokacji tablicy. Wciąż jednak mówimy o tablicach, których rozmiar jest ustalony w chwili alokacji. Tablice w pełni dynamiczne — które mogą rosnąć i kurczyć się w okresie swojego życia — są np. w Perlu.
  • Czy i jak można inicjować tablice?
  • Czy dopuszczamy tablice wielowymiarowe?
  • Czy dopuszczamy operowanie na wycinkach tablic? Wycinek oznacza tu spójny fragment o rozmiarze mniejszym niż rozmiar pierwotnej tablicy. Szczególnie interesujące są wycinki tablic wielowymiarowych; można wtedy wycinać np. dwuwymiarowy fragment tablicy trójwymiarowej.
  • Czy dopuszczamy operacje indukowane z operacji na elementach? W pewnych sytuacjach takie operacje byłyby naturalne, np. dodawanie macierzy. Tego typu operacje oferuje Fortran.

Dostęp do elementów tablicy

  • Tłumacząc instrukcje zawierające odwołania do elementów tablicy, kompilator generuje kod wyliczający adres elementów.
  • Dla tablic jednowymiarowych adres elementu T[i] to
     (adres pierwszego elementu) + (i – indeks pierwszego elementu)*(rozmiar elementu).
  • Tablice wielowymiarowe przechowywane są tak, jakby to były tablice tablic jednowymiarowych, w dwóch możliwych wariantach: wierszami lub kolumnami.
  • Przy ułożeniu tablicy dwuwymiarowej wierszami daje to adres elementu T[i, j] równy
     (adres elementu T[0, 0]) + (i*n + j)*(rozmiar elementu),

gdzie n jest liczbą elementów w wierszu.

  • Powyższe jest przy założeniu, że indeksujemy od zera; jeśli jest inaczej, należy odjąć dolne ograniczenia indeksów odpowiednio od i oraz j.
  • Przy ułożeniu kolumnami, indeksy i oraz j zamieniają się rolami.

Tablice asocjacyjne

Tablica asocjacyjna to nieuporządkowany zestaw elementów identyfikowanych za pomocą kluczy. Istotą rzeczy jest to, że klucze mogą pochodzić z obszernego zbioru możliwych wartości (zwykle są to dowolne napisy). Nie ma zatem prostego odwzorowania kluczy na adresy elementów tablicy. Tablice asocjacyjne są użyteczne tam, gdzie potrzebny jest swobodny (nieuporządkowany) dostęp do elementów. Tam, gdzie potrzebujemy pętli przetwarzającej wszystkie elementy po kolei, bardziej efektywna jest zwykła tablica. Typowy przykład tablic asocjacyjnych pojawia się w Perlu, np.

     %wzrost = (”Jacek” => 177, ”Joanna” => 166, ”Jerzy” => 199);
     $wzrost{”Józefina”} = 188;
     delete $wzrost{”Jerzy”};
     %wzrost = ();
     if (exists $wzrost{”Joanna”}) ...

Implementacja tablicy asocjacyjnej musi więc przechowywać nie tylko wartości elementów, ale i klucze. Typowy sposób implementacji to użycie funkcji haszującej do odwzorowania kluczy na adresy. Inny możliwy sposób to binarne drzewo poszukiwań. Tablice asocjacyjne są z natury rzeczy implementowane jako dynamiczne (choć przy stosowaniu funkcji haszujących może to wymagać realokowania pamięci w trakcie życia tablicy).

Rekordy



Rekord to zestaw elementów dowolnych typów. Elementy rekordu zwane są polami. Większość języków stosuje zapis „z kropką” na oznaczenie dostępu do pól rekordu. Rekordy przechowywane są w pamięci w kolejnych komórkach, choć architektura sprzętu może narzucać wymóg umieszczania niektórych pól pod adresami będącymi wielokrotnością np. czterech. To może powodować luki pomiędzy polami.

Kwestie implementacji

  • Położenie pól w obrębie rekordu jest znane w czasie kompilacji, zatem nie jest potrzebne przechowywanie informacji o położeniu pól w trakcie wykonania.
  • Naturalna wydaje się implementacja operatora równości rekordów rozumianej jako koniunkcja równości poszczególnych pól. Zauważmy, że z uwagi na luki między polami nie można tego zrealizować jako porównanie bloków pamięci. Drugi problem to napisy o zmiennej długości; trzeba porównywać jedynie faktycznie wykorzystywaną część napisu. Wreszcie — jak traktować pola będące wskaźnikami; czy aby nie chcielibyśmy, by porównania dotyczyły wskazywanych obiektów, a nie samych wskaźników?
  • Zauważmy, że struktury w C są zwykłymi rekordami, natomiast w C++ i C# są w istocie klasami.

Unie

Unia to zestaw elementów dowolnych typów, z których w dowolnym momencie przechowywany jest tylko jeden. Chodzi oczywiście o oszczędne wykorzystanie pamięci w sytuacji, gdy elementy nigdy nie są potrzebne jednocześnie. W niektórych językach unie są deklarowane jako fragment rekordu (rekord z wariantami). Podstawowe pytanie implementacyjne to czy chcemy mieć dynamiczne sprawdzanie typu. Jeśli nie, to odpowiedzialność za użycie niewłaściwej wartości z unii spada na programistę. Tak jest np. w C i C++. Jeśli jednak typ ma być sprawdzany, to unia musi dodatkowo zawierać znacznik przechowujący informację o typie przechowywanej w danej chwili wartości. Tak jest np. w Adzie i Pascalu.

Unie wydają się na tyle niebezpieczne, że chyba odchodzą powoli w przeszłość; Java i C# nie mają unii. Ada oferuje specjalny rodzaj unii ograniczonych, w których znacznik typu traktowany jest jak nazwana stała. Inny, mniej restrykcyjny rodzaj, pozwala na przypisanie nowej wartości z nowym znacznikiem typu, ale tylko przy przypisaniu całego rekordu (którego unia jest fragmentem). Dzięki temu nigdy nie powstaje rozbieżność między znacznikiem a faktycznym typem wartości w unii.

Typy wskaźnikowe

Typ wskaźnikowy obejmuje wartości, które mogą wskazywać inne wartości w pamięci, oraz dodatkową wartość „pustą”, która jest inna niż jakikolwiek „prawdziwy” wskaźnik. Wartość „pusta” bywa oznaczana jako null lub nil. Z technicznego punktu widzenia wskaźniki są po prostu adresami komórek pamięci. Różnica między wskaźnikiem a adresem to dodatkowa informacja o typie wskazywanych obiektów, którą posiada kompilator (i wykorzystuje do sprawdzania zgodności typu). Motywacją do używania wskaźników jest możliwość dynamicznego zarządzania pamięcią oraz elastyczność, jaką daje adresowanie pośrednie. W szczególności, wskaźniki są jedynym sposobem korzystania ze zmiennych alokowanych dynamicznie na stercie.

Pytania implementacyjne

  • Czy wskaźniki mogą być używane do adresowania pośredniego, czy tylko do zarządzania pamięcią?
  • Jaki jest okres życia zmiennych alokowanych dynamicznie na stercie?
  • Czy język ma oferować ograniczone formy wskaźników (typy referencyjne)?

Operacje na wskaźnikach

  • Na pewno potrzebne jest przypisanie i dereferencja wskaźnika, czyli dostęp do elementu wskazywanego przez wskaźnik.
  • Niektóre języki mają niejawną dereferencję, np. Ada czyni tak w oczywistych przypadkach (odwołania postaci p.x).
  • Do zarządzania pamięcią potrzebny jest mechanizm alokacji, np. new, malloc.
  • Adresowanie pośrednie wymaga posiadania operatora pobrania adresu (wskazania) zmiennej (operator & w języku C).
  • Arytmetyka na wskaźnikach, czyli możliwość swobodnego przesuwania wskaźnika, daje programiście duże możliwości, ale jest niebezpieczna: łatwo sięgnąć do „nieswojej” pamięci (np. w C i C++).
  • Bez możliwości przesuwania wskaźnika mechanizm staje się bezpieczniejszy (Java).

Problemy

  • Wiszący wskaźnik to wskaźnik odnoszący się do zmiennej, która została już zdealokowana.
  • Ten problem znika, gdy w języku nie ma jawnej dealokacji (np. Java).
  • Zgubiona zmienna to zmienna na stercie, do której nie mamy żadnego wskaźnika.

Typy referencyjne

  • Pod tym pojęciem kryją się typy wskaźnikowe o ograniczonych możliwościach.
  • W C++ typ referencyjny obejmuje stałe wskaźniki z niejawną dereferencją, na których nie są dozwolone operacje arytmetyczne.
  • W Javie referencje odnoszą się do obiektów. Można je kopiować przez przypisanie; arytmetyka nie jest dozwolona.

Technikalia

  • Na większości maszyn wskaźniki mają rozmiar jednego słowa.
  • Referencje to oczywiście to samo co wskaźniki.
  • Najskuteczniejszym rozwiązaniem problemu wiszących wskaźników i zgubionych zmiennych jest niejawna dealokacja. Jest to jednak rozwiązanie kosztowne.

Implementacja niejawnej dealokacji

  • Pierwsza metoda — liczniki odwołań. Dla każdego przydzielonego bloku pamięci utrzymujemy licznik odwołań do tego bloku. Licznik aktualizujemy przy kopiowaniu wskaźników, wyjściu wskaźnika poza zakres widoczności itp. Blok, do którego nie ma odwołań, jest dealokowany.
  • Druga metoda — zbieranie śmieci. Gdy brakuje miejsca na stercie, rozpoczyna się zbieranie śmieci. Przeglądamy stertę i wszystkie wskaźniki, zaznaczając te bloki, do których nie ma odwołań. Bloki te są następnie dealokowane.
  • Zauważmy, że dopuszczenie arytmetyki wskaźnikowej uniemożliwia stosowanie powyższych metod, gdyż nie da się wówczas stwierdzić, do których bloków są odwołania (programista może odwoływać się za pomocą przesuniętego wskaźnika).

Abstrakcyjne typy danych

Od czego abstrahujemy?

Abstrakcja to — w naszym rozumieniu — reprezentacja pewnego bytu, w której pominięto nieistotne w danym kontekście szczegóły. Pozwala nam to grupować byty według ich wspólnych cech i — zależnie od potrzeby — albo zajmować się całymi grupami (czyli owymi wspólnymi cechami), albo bytami wewnątrz grupy (czyli szczegółami różniącymi byty w grupie). Chodzi oczywiście o to, by poradzić sobie ze złożonością problemów.

Dwie podstawowe abstrakcje w językach programowania to:

  • Abstrakcja procesu: Abstrakcjami procesów są podprogramy. Pozwalają wskazać (przez ich wywołanie), że pewna czynność ma być wykonana, bez wskazywania jak ma być wykonana. Szczegóły znajdują się w treści podprogramu, której wywołujący nie musi znać.
  • Abstrakcja danych: Zamknięta całość obejmująca reprezentację pewnego typu danych wraz z podprogramami, umożliwiającymi działanie na tych danych.

Co to jest abstrakcyjny typ danych? Jak już wspominaliśmy, jest to konstrukcja języka programowania, w której definiujemy typ (w dotychczasowym rozumieniu) oraz operacje na nim w taki sposób, że inne byty w programie nie mogą manipulować danymi inaczej niż za pomocą zdefiniowanych przez nas operacji. Istotą rzeczy jest tu oddzielenie części „prywatnej” typu (czyli szczegółów reprezentacji danych i implementacji poszczególnych operacji) od części „publicznej” (tego, co można wykorzystywać w innych miejscach programu). Rozdzielenie składników abstrakcyjnego typu danych na część prywatną i publiczną jest możliwe za pomocą zawartych w języku programowania mechanizmów sterowania dostępem. Dane w typie abstrakcyjnym zwane są właściwościami lub danymi składowymi; używa się też określeń pole lub po prostu zmienna... Operacje zwane są metodami lub funkcjami składowymi.

Przywołajmy ponownie przykłady

  • Wbudowane w języki programowania typy pierwotne można uznać za abstrakcyjne: nie mamy dostępu do reprezentacji wewnętrznej, więc możemy posługiwać się jedynie tym, co dostarcza język.
  • Zdefiniowany w Pascalu typ rekordowy i kilka procedur na nim działających nie stanowi abstrakcyjnego typu danych. Ktokolwiek zadeklaruje rekord tego typu, będzie mógł działać bezpośrednio na tym rekordzie z pominięciem „oficjalnych” procedur.
  • Sztandarowy przykład to klasa np. z Javy lub C++. Dane schowane w części prywatnej klasy nie są dostępne na zewnątrz, stąd nie da się wykonywać żadnych operacji bezpośrednio.

Co to jest obiekt? Obiekt to instancja abstrakcyjnego typu danych, czyli pojedynczy „egzemplarz” tego typu zaalokowany na stercie (najczęściej), na stosie lub statycznie (najrzadziej). Sam abstrakcyjny typ danych w większości języków zwany jest klasą.

Jakie warunki powinien spełniać abstrakcyjny typ danych definiowany przez użytkownika? Deklaracja części publicznej (interfejsu), czyli danych i podprogramów przeznaczonych do wykorzystania przez inne byty w programie, powinna mieścić się w jednej jednostce syntaktycznej. Pozostała część, czyli ciała podprogramów publicznych (implementacja) oraz dane i podprogramy przeznaczone do wewnętrznego użytku, może mieścić się w tej samej lub innej jednostce syntaktycznej. Inne byty w programie mogą tworzyć zmienne definiowanego typu abstrakcyjnego. Jedynymi bezpośrednimi operacjami (także w sensie dostępu do zmiennych) na obiektach tego typu są te zawarte w części publicznej.

Czy lepiej mieć interfejs i implementację w jednej jednostce syntaktycznej, czy osobno? Razem — pozwala organizować program w sposób modułowy. Osobno — umożliwia ukrycie (w sensie wizualnym, nie tylko w sensie dostępu) części implementacyjnej przed użytkownikami, co zmniejsza pokusę doraźnego manipulowania implementacją.

Implementacja w różnych językach

Omówimy teraz kwestie implementacyjne w kilku językach programowania. Później zajmiemy się sparametryzowanymi abstrakcyjnymi typami danych i ponownie przykładami w paru językach.

Co powinno być w języku?

  • Jednostka syntaktyczna mieszcząca definicję typu (być może część publiczna osobno).
  • Sposób wyszczególnienia danych i podprogramów publicznych.
  • Kilka podstawowych, wbudowanych operacji na obiektach z typu, np. podstawienie, sprawdzenie równości.
  • Pewne operacje są potrzebne niemal w każdym typie, są jednak zależne od szczegółów tego typu. Muszą zatem być implementowane przez programistę. Są to np. konstruktory, destruktory, iteratory.
  • Język może oferować abstrakcyjne typy danych wprost (C++, C#, Java) lub może mieć bardziej ogólne konstrukcje (np. Ada).
  • Dwa pytania implementacyjne: Czy abstrakcyjne typy danych mogą być parametryzowane? Jak realizowane jest sterowanie dostępem?

Ada

  • Ada zawiera konstrukcje enkapsulacyjne (czyli konstrukcje wiążące mniejsze jednostki w zamkniętą całość) zwane pakietami.
  • Pakiet składa się z dwóch części: specyfikacji i ciała.
  • Programista może udostępnić element pakietu w całości lub tylko w postaci interfejsu (czyli specyfikacji, jak użyć danego elementu).
  • W pierwszym przypadku, element staje się bezpośrednio dostępny za pomocą nazwy. Nie jest wówczas typem abstrakcyjnym.
  • W drugim przypadku, skrócona deklaracja pojawia się w publicznej części specyfikacji, a reprezentacja — w części prywatnej.
  • Przykład specyfikacji pakietu do obsługi stosu:
     package Stos is
       type typ_stosowy is limited private;
       maks_rozmiar: constant := 1000;
       function pusty(st: in typ_stosowy) return Boolean;
       procedure połóż(st: in out typ_stosowy; elem: in Integer);
       procedure zdejmij(st: in out typ_stosowy);
       function szczyt(st: in typ_stosowy) return Integer;
       
       private
       type typ_listowy is array (1..maks_rozmiar) of Integer;
       type typ_stosowy is record
         list: typ_listowy;
         wsk_stosu: Integer range 0..maks_rozmiar := 0;
       end record;
     end Stos;

C++

  • Język oferuje dwie konstrukcje: class i struct, różniące się domyślnymi regułami dostępu.
  • Klasy języka C++ są typami.
  • Jednostka programu, która zadeklarowała instancję klasy (obiekt), ma dostęp do publicznych bytów tej klasy, ale tylko poprzez tę instancję.
  • Każda instancja klasy ma własny zestaw danych, natomiast funkcje (metody) nie są powielane lecz przechowywane wspólnie dla całej klasy.
  • Obiekty mogą być statyczne oraz dynamiczne, alokowane na stosie (dostęp przez „zwykłe” zmienne) lub na stercie (dostęp przez wskaźniki).
  • Obiekty mogą zawierać zmienne dynamiczne alokowane na stercie, czyli poza obiektem.
  • Alokacja i dealokacja na stercie są jawne; służą do tego operacje new i delete.
  • Funkcje z klasy mogą być kompilowane jako inline. Kod funkcji jest wówczas kopiowany do wywołującego, eliminując czasochłonną obsługę wywołania. Mechanizm ten jest przydatny dla funkcji niewielkich objętościowo.
  • Elementy klasy mogą być deklarowane jako prywatne (dostęp tylko wewnątrz obiektu), publiczne (dostęp bez ograniczeń) lub chronione (dostęp dla potomków). Osiąga się to przez umieszczenie deklaracji w częściach, odpowiednio, private, public i protected.
  • Deklaracja friend pozwala dać „obcym” klasom dostęp do elementów prywatnych.
  • Definicja klasy może zawierać konstruktor, który będzie niejawnie wywoływany przy tworzeniu obiektu z klasy. Konstruktor ma taką samą nazwę jak klasa. Konstruktory mogą mieć parametry i mogą być przeciążane.
  • Definicja klasy może też zawierać destruktor, wołany przy dealokacji obiektu. Nazwa destruktora to nazwa klasy poprzedzona tyldą.
  • Przykład klasy do obsługi stosu liczb całkowitych (pominięto szczegóły implementacji metod):
     class stos {
     
     private:
       int *baza, maks_rozmiar, wsk_stosu;
     
     public:
       stos()
         baza = new int [1000];
         maks_rozmiar = 999;
         wsk_stosu = -1;
       };
       ~stos() {delete [] baza;};
       void poloz(int elem) {...};
       void zdejmij() {...};
       int szczyt() {...};
       int pusty() {...};
     }

Java

  • W Javie wszystkie typy zdefiniowane przez użytkownika są klasami.
  • Wszystkie obiekty są alokowane na stercie.
  • Podprogramy (metody) mogą być definiowane tylko w klasach.
  • Klasy są deklarowane i definiowana w jednej jednostce syntaktycznej.
  • Do sterowania dostępem stosuje się oznaczenia public, private i protected przy poszczególnych definicjach.
  • Pakiety pozwalają na modularyzację programów. W obrębie pakietu elementy klasy bez oznaczenia dostępu są widoczne dla innych klas.
  • Nie ma destruktorów, gdyż Java wykonuje niejawne zbieranie śmieci.
  • Przykład klasy do obsługi stosu liczb całkowitych (pominięto szczegóły implementacji metod):
class Stos {
  private int baza[];
  private int maks_rozmiar, wsk_stosu;
  public Stos() { 
    baza = new int [1000];
    maks_rozmiar = 999;
    wsk_stosu = -1;
  };
  public void poloz(int elem) {...};
  public void zdejmij() {...};
  public int szczyt() {...};
  public boolean pusty() {...};
}

C#

  • Do sterowania dostępem oprócz public, private, protected można używać internal i protected internal.
  • Wszystkie obiekty typów zdefiniowanych za pomocą class są alokowane na stercie; na stosie są alokowane obiekty typów zdefiniowanych za pomocą struct.
  • C# wykonuje zbieranie śmieci, więc destruktory nie są konieczne. Mogą być jednak definiowane, jeśli programiście zależy na wykonaniu jakichś czynności przed dealokacją obiektu.
  • W C# istnieje pojęcie akcesorów („pobieraczy” i „ustawiaczy”) pozwalających na ograniczony dostęp do danych prywatnych. Jest to bezpieczniejsze niż dostęp bezpośredni. „Pobieracz” to funkcja, która jest wykonywana przy odczytywaniu prywatnej zmiennej obiektu, którą programista postanowił udostępnić w taki sposób. Podobnie „ustawiacz” jest wywoływany przy próbie podstawienia pod zmienną.
  • Klasy można definiować także za pomocą struct. Są to „lekkie” klasy, których obiekty są alokowane na stosie. Nie pozwalają na dziedziczenie.

Sparametryzowane abstrakcyjne typy danych

  • Chodzi o możliwość tworzenia typów abstrakcyjnych, w których element może mieć różne typy w zależności od parametru.
  • Pozwala to tworzyć kod rodzajowy („uniwersalny”): ten sam kod może działać dla różnych typów danych.
  • C++ umożliwia parametryzowanie definicji typów za pomocą deklaracji template. Można więc pisać rodzajowy kod źródłowy, jednak kompilator C++ tworzy oddzielną wersję kodu wynikowego dla każdego użytego typu — można to nazwać „instancjonowaniem statycznym”.
  • W Javie można definiować typy sparametryzowane używając parametrów w nawiasach kątowych. Inaczej niż w C++, kompilator Javy generuje uniwersalny kod wynikowy. Ceną za to jest mniejsza efektywność kodu.
  • Parametryzacja w C# jest składniowo podobna do Javy. Różnica polega na „instancjonowaniu dynamicznym”: kod dla wersji z różnymi typami jest tworzony dynamicznie z kodu pośredniego dopiero w chwili, gdy jest potrzebny. Dodatkowo, dla typów nie będących obiektami (int, float itp.) tworzony jest inny kod niż dla obiektów, co sprzyja efektywności.
  • Ada pozwala tworzyć pakiety rodzajowe, a przez to — sparametryzowane typy abstrakcyjne. Pakiety rodzajowe w Adzie należy jawnie „instancjonować”, czyli tworzyć z nich pakiety konkretne przez podanie konkretnych typów, jakie mają być wykorzystane w danej wersji pakietu.

Przykład w C++

  • Deklaracja sparametryzowanej klasy pair (wraz z definicją konstruktora):
     template <class T>
     class pair {
         T a, b;
       public:
         pair(T elem1, T elem2)
           {a = elem1; b = elem2;}
         T getmax();
     };
  • Definicja metody getmax:
     template <class T>
     T pair<T>::getmax()
     {
       T retval;
       retval = a>b ? a : b;
       return retval;
     }
  • Przykład użycia:
     int main() {
       pair<int> mypair(2, 7);
       cout << mypair.getmax();
       return 0;
     }

Przykład w Javie

  • Interfejs sparametryzowanego typu List:
     public interface List<E> {
       void add(E x);
       Iterator<E> iterator();
     }
  • Wykorzystanie do stworzenia listy zawierającej liczby całkowite:
     List<Integer> myIntList = new LinkedList<Integer>();
     myIntList.add(new Integer(0));
     Integer x = myIntList.iterator().next();

Przykład w C#

     public class GenericList<T>
     {
       private class Node
       {
         public Node(T t)
         {
           next = null;
           data = t;
         }
         
         private Node next;
         public Node Next
         {
           get { return next; }
           set { next = value; }
         }
         
         private T data;
         public T Data  
         {
           get { return data; }
           set { data = value; }
         }
       }
       
       private Node head;
       
       public GenericList() 
       {
         head = null;
       }
       
       public void AddHead(T t) 
       {
         Node n = new Node(t);
         n.Next = head;
         head = n;
       }
       
       public IEnumerator<T> GetEnumerator()
       {
         Node current = head;
         
         while (current != null)
         {
           yield return current.Data;
           current = current.Next;
         }
       }
     }