Paradygmaty programowania/Wykład 9: U podstaw programowania obiektowego — rachunek sigma

Wprowadzenie

Mówimy o rachunku sigma — formalizmie, który ma za zadanie dać nam wgląd w fundamentalne cechy programowania obiektowego podobnie jak rachunek lambda w przypadku programowania funkcyjnego i imperatywnego. Omawiamy zatem podstawy rachunku sigma, by Czytelnik mógł sam się przekonać, na ile ścisłe, formalne zdefiniowanie problemu może pomóc w jego głębszym rozumieniu.

Wstęp

Klasyczne programowanie imperatywne rozwinęło i rozpowszechniło się wcześniej niż pojawiła się teoria opisująca i tłumacząca w sposób wyczerpujący jego — subtelne przecież nieraz — właściwości. Podobnie jest z programowaniem obiektowym: najpierw pojawił się pomysł, języki programowania i doraźne zaledwie opisy formalne. Dopiero z upływem lat, gdy programowanie obiektowe zdążyło już okrzepnąć (także w sensie komercyjnym), pojawiają się formalne teorie opisujące je ściślej niż tworzone ad hoc modele. Takim formalizmem, stworzonym w latach 90-tych XX wieku, jest rachunek sigma. Tak jak rachunek lambda wniósł ważny wkład w rozumienie języków funkcyjnych i imperatywnych, tak rachunek sigma ma ambicje spełniać podobną rolę wobec programowania obiektowego.

Rachnek sigma (zwany dalej $\sigma$-rachunkiem) to prosty model matematyczny na tym samym poziomie abstrakcji co $\lambda$-rachunek. Jest wystarczająco elastyczny, by wyrazić w nim złożone pojęcia programowania obiektowego (choć bezpośrednio nie reprezentuje żadnego z nich). Pierwotnymi bytami są w nim obiekty (a nie funkcje jak w $\lambda$-rachunku). Konstrukcja $\sigma$-rachunku zaczyna się od bardzo prostego „jądra”; następnie rachunek wzbogaca się o konstrukcje, które można wywieść z tych prostych, i o system typów. W efekcie otrzymujemy narzędzie mogące modelować istotne cechy „prawdziwych” języków.

Rachunek sigma można też postrzegać jako rezultat redukcji języków obiektowych do podstawowych mechanizmów. Typowe języki obiektowe skupiają się wokół pojęcia klasy. Niektóre języki obiektowe „pozaklasowe” oferują mechanizmy obiektowe nie korzystając z pojęcia klasy, lecz poprzez prostsze operacje (np. tworzenie obiektów w JavaScripcie). Taki rozkład na elementarne składniki pozwala często na dostrzeżenie nowych możliwości... Złożone mechanizmy można z powrotem zsyntezować z owych składników elementarnych. Rachunek sigma idzie jeszcze dalej w wyodrębnianiu elementarnych części. Siła wyrazu pozostaje bez zmian, a uzyskujemy prostszy opis semantyki.

Przykład [Dlaczego zbytnia złożoność pojęć może nas ograniczać?]

• Przyjrzyjmy się pojęciu klasy w języku C++.
• Mamy tu ścisły związek pomiędzy relacjami dziedziczenia, podklasy i podtypu.
• Przypomnijmy, co oznaczają te pojęcia...
• Relacja dziedziczenia polega na przejęciu kodu z wcześniej zdefiniowanej klasy.
• Relacja podklasy to częściowy porządek klas, indukowany przez definicje klas. Mamy tu na myśli zwrotne i przechodnie domknięcie relacji bezpośredniej podklasy, czyli relacji ustanowionej przez deklaracje w rodzaju class A : B {...}.
• Relacja podtypu to w istocie możliwość użycia obiektu z podtypu wszędzie tam, gdzie można użyć obiektu z typu bazowego.
• Z drugiej strony, podklasa pewnej klasy może być od niej tak odległa, że nie dziedziczy żadnego kodu...
• O problemie „Czy podklasy są podtypami?” już mówiliśmy...
• Wydaje się, że nowsze języki starają się osłabić związem między relacją podklasy a relacją podtypu (np. poprzez pojęcie interfejsu, które pozwala stworzyć typ bez tworzenia klasy).

Wstępne założenia

Zajmujemy się obiektami „samoistnymi”, w oderwaniu od klas. To niewątpliwie upraszcza rozważania. Pojęcie klasy traktujemy jako wtórne wobec pojęcia obiektu; można je zdefiniować za pomocą manipulacji na obiektach.

Obiekty są zbiorami metod

• Każda metoda otrzymuje parametr „jaźń”, oznaczający obiekt, przez który metoda została wywołana. Podobny twór w popularnych językach programowania oznaczany jest przez this lub self.
• Pola obiektu traktujemy jako szczególny przypadek metod — takich, które nie wykorzystują owego parametru (czyli nie wywołują innych metod).
• To podejście upraszcza formalizm, ale ma też kontrowersyjne skutki: naturalna operacja zapisywania wartości do pola staje się teraz operacją nadpisania metody.
• Jest to rzadkość w językach programowania — możemy zamienić metodę w obiekcie na inną... W ten sposób obiekt może dynamicznie zmieniać swoje zachowanie.
• Konsekwentnie traktując pola jako szczególny przypadek metod, odczyt pola traktujemy jak wywołanie metody.
• Podsumujmy: obiekt to zbiór metod, dla których mamy dwie operacje — wywołanie i nadpisanie.

Skupiamy się na rachunku w wersji raczej „funkcyjnej” niż „imperatywnej”

• Chodzi o to, że wykonanie programu rozumiemy jako ciąg operacji (redukcji) na obiektach, gdzie każda następna operacja korzysta z rezultatu poprzedniej.
• To wcale nie oznacza, że nie zajmujemy się stanem obiektów (czyli wartością ich pól).

Przedstawiamy $\sigma$-rachunek w najprostszym, nietypowanym wariancie

• To — rzecz jasna — dopiero początek.
• Pozwala on jednak zorientować się w istocie zjawiska...
• Zainteresowanych odsyłamy do literatury, np. do książki Abadiego i Cardellego „A Theory of Objects”, na której fragmentach oparty jest w dużej mierze niniejszy wykład.

Nietypowany $\sigma$-rachunek

Definicje

Obiekty są jedynymi strukturami pierwotnymi $\sigma$-rachunku

• Obiekt to zbiór metod.
• Każda metoda posiada zmienną związaną reprezentującą jaźń obiektu oraz ciało, które wytwarza wynik.
• Jedyne operacje na obiekcie to wywołania metod i nadpisywania metod.
• Rachunek wykorzystuje jeszcze zmienne i nic ponadto.

Czy można skonstruować inny rachunek obiektów?

• Oczywiście tak.
• W szczególności można rozważać niemal taki sam rachunek z operacjami dodawania i usuwania metod z obiektów. Wówczas nadpisywanie metody można by zdefiniować za ich pomocą.
• Nie rozważamy tu w ogóle obiektów o zmiennej liczbie składników.
• Podobnie nie zajmujemy się np. operacją ekstrahowania metody z obiektu jako funkcji.
• Są to wszystko wybory służące uproszczeniu rachunku lub zachowaniu jego obiektowej natury (ekstrakcja metody kłóciłaby się z fundamentalnym założeniem, że metoda jest nierozerwalnie związana z obiektem).

Notacja

• Zapis $\sigma (x)b$ oznacza metodę o ciele $b$; zmienna x to jaźń obiektu.
• Obiekt zawierający $n$ metod etykietowanych przez $l_1,\dots ,l_n$ zapisujemy jako [$l_1=\sigma (x_1)b_1,\dots ,l_n=\sigma (x_n)b_n$].
• Wywołanie metody l z obiektu o to o.l.
• Nadpisanie metody l z obiektu o metodą $\sigma (x)b$ zapisujemy jako o.l ς(x)b.

Uwagi

• Porządek metod w obiekcie nie jest istotny.
• Obiekt zawierający daną metodę zwany jest jej właścicielem.
• Litera sigma używana jest jako symbol wiążący; $\sigma (x)b$ oznacza metodę, w której zmienna $x$ jest związana z obiektem-właścicielem.
• Sens wywołania o.l to wykonanie metody l z obiektu o, z parametrem związanym z obiektem o, i zwrócenie wyniki wykonania.
• Semantyka nadpisania metody o.l $\sigma (y)b$ jest funkcyjna: nadpisanie wytwarza kopię obiektu o, w której metoda l jest zastąpiona metodą $\sigma (y)b$ .

Przyklad

• Obiekt zawierający jedną metodę, zwracającą obiekt pusty:

     [$l=\sigma (x)[]$ ]

• Obiekt z dwiema metodami; pierwsza jak powyżej, druga wywołuje pierwszą (wykorzystując jaźń obiektu, z którą związany jest parametr $x_2$):

     [$l_1=\sigma (x_1)[],l_2=\sigma (x_2)x_2.l_1$] 

Dodatkowe konwencje notacyjne

• Jeśli metoda nie wykorzystuje parametru x (czyli jest polem), to zamiast [$\dots ,l=\sigma (x)b,\dots$] piszemy [$\dots ,l=b,\dots$].
• Analogicznie, przy nadpisaniu pola zamiast o.l $\sigma (y)b$ piszemy o.l:=b.

Semantyka

Wykonanie termu w $\sigma$-rachunku to ciąg redukcji

• Zapis $a\to b$ oznacza, że $a$ redukuje się do $b$ w jednym kroku.
• Podstawienie termu $a$ za wszystkie wolne wystąpienia $x$ w $b$ zapisujemy jako $bx\leftarrow a$.

Załóżmy, że $o$ jest obiektem $[l_1=\sigma (x_1)b_1,\dots ,l_n=\sigma (x_n)b_n]$, gdzie etykiety $l_i$ są parami różne.

• Wywołanie metody redukuje się wówczas tak:

     $o.l_j\to b_j\{x_j\leftarrow o\}$