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

From Studia Informatyczne

Spis treści

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 \varsigma-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 \varsigma-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ązek 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 \varsigma-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 \varsigma-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 \varsigma(x)b oznacza metodę o ciele b; zmienna x to jaźń obiektu.
  • Obiekt zawierający n metod etykietowanych przez l_1,\ldots , l_n zapisujemy jako [l_1=\varsigma(x_1)b_1,\ldots , l_n=\varsigma(x_n)b_n].
  • Wywołanie metody l z obiektu o to o.l.
  • Nadpisanie metody l z obiektu o metodą \varsigma(x)b zapisujemy jako o.l\Leftarrow \varsigma(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; \varsigma(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 wyniku wykonania.
  • Semantyka nadpisania metody o.l\Leftarrow \varsigma(y)b jest funkcyjna: nadpisanie wytwarza kopię obiektu o, w której metoda l jest zastąpiona metodą \varsigma(y)b .

Przykład

  • Obiekt zawierający jedną metodę, zwracającą obiekt pusty:
     [l=\varsigma(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=\varsigma(x_1)[ ], l_2=\varsigma(x_2)x_2.l_1] 

Dodatkowe konwencje notacyjne

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

Semantyka

Wykonanie termu w \varsigma-rachunku to ciąg redukcji

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

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

  • Wywołanie metody redukuje się wówczas tak:
     o.l_j\rightarrow b_j\{x_j\leftarrow o\}
  • Nadpisanie metody redukuje się następująco:
     o.l_j\Leftarrow \varsigma(y)b  \rightarrow       [l_1=\varsigma(x_1)b_1, \ldots,        l_{j-1}=\varsigma(x_{j-1})b_{j-1}, l_j=\varsigma(y)b,
                     l_{j+1}=\varsigma(x_{j+1})b_{j+1}, \ldots,                        l_n=\varsigma(x_n)b_n]
  • Czyli: Wywołanie metody o.l_j redukuje się do rezultatu podstawienia obiektu-właściciela w miejsce parametru w ciele metody o nazwie l_j.
  • Nadpisanie metody o.l_j\Leftarrow \varsigma(y)b redukuje się do kopii obiektu-właściciela, gdzie naspisywana metoda została zastąpiona nową.

Przykład 1

Niech o_1 będzie obiektem [l=\varsigma(x)[]]. Wówczas:

  • o_1.l \rightarrow []\{x\leftarrow o_1\} = []
  • o_1.l \Leftarrow \varsigma(x)o_1 \rightarrow [l=\varsigma(x)o_1]

Zauważmy, że l jest polem i operacje wywołania i nadpisania dają efekt taki, jakiego spodziewamy się dla pól.

Przykład 2

Niech o_2 będzie obiektem [l=\varsigma(x)x.l]. Wówczas:

  • o_2.l \rightarrow x.l\{x\leftarrow o_2\} = o_2.l \rightarrow \ldots

Tu mamy do czynienia z obliczeniami, które nie kończą się. Widać w nich nieskończoną — choć niezupełnie jawną — rekurencję.

Przykład 3

Niech o_3 będzie obiektem [l=\varsigma(x)x], a o_4 — [l=\varsigma(y)(y.l\Leftarrow \varsigma(x)x)]. Wówczas:

  • o_3.l \rightarrow  x\{x\leftarrow o_3\} = o_3
  • o_4.l \rightarrow  (o_4.l\Leftarrow \varsigma(x)x) \rightarrow o_3

Ten przykład pokazuje, że metoda może zwracać lub modyfikować jaźń obiektu.

Zdefiniowana powyżej relacja redukcji w jednym kroku wymaga rozszerzenia.

  • Po pierwsze, relację uogólniamy na „przepisywanie z kontekstem”.
  • A zatem jeśli a\rightarrow b, to przyjmujemy również że \ldots a\ldots\rightarrow \ldots b\ldots, gdzie \ldots a\ldots oznacza dowolny term \varsigma-rachunku zawierający a.
  • Po drugie, tworzymy zwrotne i przechodnie domknięcie, otrzymując relację redukcji „w dowolnej liczbie kroków”, oznaczaną przez \rightarrow^{*}.
  • Relacja \rightarrow^{*} spełnia własność Churcha-Rossera, czyli jeśli a \rightarrow^{*} b i a \rightarrow^{*} c, to istnieje d takie, że b \rightarrow^{*} d i c\rightarrow^{*}d.

Semantyka operacyjna

Redukcje, które dotychczas określiliśmy, nie narzucają konkretnego porządku obliczeń. Pozostaje więc zdefiniowanie deterministycznego systemu redukcji. Przyjmujemy założenie, że dla obiektu [l_1=\varsigma(x_1)b_1,\ldots, l_n=\varsigma(x_n)b_n] ciało b_i redukujemy dopiero wtedy, gdy metoda l_i zostanie wywołana. Celem systemu redukcji jest doprowadzenie każdego (zamkniętego, tzn. bez zmiennych wolnych) wyrażenia \varsigma-rachunku do postaci wyniku. Wynik definiujemy po prostu jako term postaci [l_1=\varsigma(x_1)b_1,\ldots, l_n=\varsigma(x_n)b_n].

Wprowadzamy zatem następujące reguły operacyjne:

  • Wynik nie podlega dalszej redukcji.
  • Żeby obliczyć wyrażenie a.l, obliczamy najpierw wynik a, a następnie obliczamy jego składowe.
  • Żeby obliczyć wyrażenie a.l\Leftarrow \varsigma(x)b, obliczamy najpierw wynik a, zamieniamy w nim metodę l i zwracamy tak powstały obiekt. Zauważmy, że nie obliczamy niczego wewnątrz wyliczonego obiektu.
  • Za każdym razem w obliczeniach należy sprawdzać, czy redukowany term ma właściwą postać.

Powyższe reguły pozwalają skonstruować deterministyczny algorytm redukcji. Algorytm ten to pętla implementująca reguły operacyjne. Dla dowolnego wyrażenia \varsigma-rachunku, które jest zbieżne do wyniku, algorytm wylicza ów wynik. Dwie inne ewentualności to zgłoszenie błędu w wyrażeniu lub obliczenia nieskończone (jak w podanym już przykładzie — wywołanie o.l z obiektu o = [l=\varsigma (x)x.l]). A zatem możliwe jest stworzenie maszyny wirtualnej dla \varsigma-rachunku.

Interesujące wydaje się pokazanie, że siła wyrazu \varsigma-rachunku jest co najmniej taka, jak \lambda-rachunku. W tym celu można skonstruować metodę translacji termów \lambda-rachunku do obiektów. Metodę taką prezentujemy w jednym z zadań, pozostawiając Czytelnikowi jako ćwiczenie zapoznanie się z nią i sprawdzenie jej działania na kilku przykładach.

Przykłady użycia sigma-rachunku

Pokażemy teraz kilka przykładów \varsigma-rachunku w zastosowaniu do konkretnych obiektów i obliczeń. Ponieważ wiemy, że wyrażenia \lambda-rachunku dają się zapisać w \varsigma-rachunku bez utraty znaczenia, będziemy je stosowali w miarę potrzeby.

Przykład 1 — kopia zapasowa

Zdefiniujemy obiekt, który potrafi przechowywać kopię samego siebie i zwrócić ją na żądanie. Obiekt zawiera dwie metody — kopiuj i przywróć — i ewentualne inne metody.

Wygląda on tak:

     o = [przywroc=\varsigma(x)x, kopiuj=\varsigma(y)y.przywroc \Leftarrow \varsigma(x)y, \ldots]

Początkowo metoda przywróć zdefiniowana jest tak, że zwraca obiekt-właściciela. Wywołanie kopiuj zapisuje bieżącą jaźń obiektu jako nową metodę przywróć. Zatem wywołanie przywróć daje jaźń obiektu z chwili ostatniego wywołania kopiuj...

Wywołania przywróć mogą stanowić kaskadę, która spowoduje przywrócenie obiektu sprzed kilku kopiowań.

Przykład 2 — kodowanie liczb naturalnych

Zdefiniujemy obiekty, które będą posiadały metody czyzero, poprzednik oraz następnik i będą zachowywały się jak liczby naturalne. W istocie musimy określić jedynie obiekt reprezentujący liczbę zero (oznaczany dalej jako zero), gdyż wszystkie inne dają się wygenerować z owego zera za pomocą wielokrotnego wywoływania metody następnik.

Oczekujemy następującego zachowania obiektu zero:

  • Wywołanie czyzero powinno dawać true (nota bene, stałe da się oczywiście reprezentować).
  • Wywołanie poprzednik powinno dawać obiekt zero.
  • Wywołanie następnik powinno dawać inny obiekt, o łatwych do ustalenia własnościach...

Nietrudno sprawdzić, że poniższy obiekt spełnia te postulaty:

     zero = [czyzero=true, poprzednik=\varsigma(x)x, nastepnik=\varsigma(x)(x.czyzero:=false).poprzednik:=x]

Zauważmy, że w tym przykładzie ponownie kluczową rolę odgrywa możliwość operowania jaźnią obiektu.

Przykład 3 — kalkulator

Tym razem korzystamy z możliwości wyrażenia w \varsigma-rachunku operacji arytmetycznych, by skonstruować obiekt oferujący operacje takie, jak (prosty raczej...) kalkulator.

Nieodzowne będzie tutaj nadpisywanie metody. Wywołanie metody dodaj lub odejmij spowoduje zapisanie stosownego kodu w metodzie równasię.

Pola arg i akum używane są do przechowywania operandów.

Metoda wpisz służy do wpisania liczby. Wykorzystuje ona możliwość zapisania \lambda-wyrażeń w \varsigma-rachunku.

Kod obiektu kalkulator przedstawia się następująco:

     kalkulator = [
       arg=0,
       akum=0,
       wpisz=\varsigma(x)\lambda(n)x.arg:=n,
       dodaj=\varsigma(x)(x.akum:=x.rownasie).rownasie\Leftarrow \varsigma(y)y.akum+y.arg,
       odejmij=\varsigma(x)(x.akum:=x.rownasie).rownasie\Leftarrow \varsigma(y)y.akum-y.arg,
       rownasie=\varsigma(x)x.arg
     ]

Czytelnikowi pozostawiamy sprawdzenie, że następujące przykładowe ciągi wywołań dają spodziewany rezultat:

  • kalkulator.wpisz(10).odejmij.wpisz(3).równasię = 7
  • kalkulator.wpisz(3).dodaj.równasię = 6