Podtyp behawioralny - Behavioral subtyping

W programowaniu obiektowym , podtypów behawioralna jest zasada, że podklasy powinno spełniać oczekiwania klientów uzyskujących dostęp podklasa obiektów poprzez referencje typu nadklasy, nie tylko jeśli chodzi składniowej bezpieczeństwa (takich jak brak „-not-found metoda” błędy), ale również w zakresie poprawności zachowania. W szczególności właściwości, które klienci mogą udowodnić przy użyciu specyfikacji domniemanego typu obiektu, powinny być zachowane, nawet jeśli obiekt jest w rzeczywistości elementem członkowskim podtypu tego typu.

Na przykład rozważmy typ Stack i Type Queue, które mają metodę put do dodania elementu i metodę get do usunięcia jednego. Załóżmy, że dokumentacja związana z tymi typami określa, że ​​metody stosu typu powinny zachowywać się zgodnie z oczekiwaniami dla stosów (tj. Powinny wykazywać zachowanie LIFO ), a metody kolejki tego typu powinny zachowywać się zgodnie z oczekiwaniami dla kolejek (tj. Powinny wykazywać zachowanie FIFO ). Załóżmy teraz, że ten typ Stack został zadeklarowany jako podklasa typu Queue. Większość kompilatorów języków programowania ignoruje dokumentację i przeprowadza tylko testy niezbędne do zachowania bezpieczeństwa typów . Ponieważ dla każdej metody typu Queue typ Stack udostępnia metodę o pasującej nazwie i podpisie, to sprawdzenie zakończy się powodzeniem. Jednak klienci uzyskujący dostęp do obiektu Stack poprzez odniesienie typu Queue, na podstawie dokumentacji Queue, oczekiwaliby zachowania FIFO, ale obserwowaliby zachowanie LIFO, unieważniając dowody poprawności tych klientów i potencjalnie prowadząc do nieprawidłowego zachowania programu jako całości.

Ten przykład narusza podtyp behawioralny, ponieważ typ Stack nie jest behawioralnym podtypem typu Queue: nie jest tak, że zachowanie opisane w dokumentacji typu Stack (tj. Zachowanie LIFO) jest zgodne z dokumentacją typu Queue (co wymaga zachowania FIFO) .

W przeciwieństwie do tego program, w którym zarówno Stack, jak i Queue są podklasami typu Bag, którego specyfikacja dla get polega jedynie na tym, że usuwa jakiś element, spełnia podtypy behawioralne i pozwala klientom bezpiecznie wnioskować o poprawności na podstawie przypuszczalnych typów obiektów, które współdziałać z. Rzeczywiście, każdy obiekt, który spełnia wymagania specyfikacji stosu lub kolejki, spełnia również specyfikację torby.

Należy podkreślić, że to, czy typ S jest behawioralnym podtypem typu T, zależy tylko od specyfikacji (tj. Dokumentacji ) typu T; realizacja typu T, jeśli ma w ogóle, jest zupełnie bez znaczenia na to pytanie. Rzeczywiście, typ T nie musi nawet mieć implementacji; może to być klasa czysto abstrakcyjna. Jako inny przykład, powyższy typ Stack jest behawioralnym podtypem typu Bag, nawet jeśli implementacja typu Bag wykazuje zachowanie FIFO: liczy się to, że specyfikacja typu Bag nie określa, który element jest usuwany metodą get . Oznacza to również, że podtyp behawioralny można omawiać tylko w odniesieniu do określonej specyfikacji (behawioralnej) dla każdego zaangażowanego typu, a jeśli typy te nie mają dobrze zdefiniowanej specyfikacji behawioralnej, podtyp behawioralny nie może być w znaczący sposób omówiony.

Weryfikacja podtypów behawioralnych

Typ S jest behawioralnym podtypem typu T, jeśli każde zachowanie dozwolone przez specyfikację S jest również dozwolone przez specyfikację T. Wymaga to w szczególności, że dla każdej metody M z T specyfikacja M w S jest silniejszy niż ten w T.

Specyfikacja metody określona przez warunek wstępny P s i warunek końcowy Q s jest silniejsza niż specyfikacja określona przez warunek wstępny P t i warunek końcowy Q t (formalnie: (P s , Q s ) ⇒ (P t , Q t )) jeżeli P s jest słabsze niż P t (tj. P t implikuje P s ), a Q s jest silniejsze niż Q t (tj. Q s implikuje Q t ). Oznacza to, że wzmocnienie specyfikacji metody można osiągnąć poprzez wzmocnienie warunku końcowego i osłabienie warunku wstępnego. Rzeczywiście, specyfikacja metody jest silniejsza, jeśli nakłada bardziej szczegółowe ograniczenia na dane wyjściowe dla danych wejściowych, które były już obsługiwane, lub jeśli wymaga obsługi większej liczby danych wejściowych.

Na przykład rozważmy (bardzo słabą) specyfikację metody, która oblicza wartość bezwzględną argumentu x , który określa warunek wstępny 0 ≤ x i warunek końcowy 0 ≤ wynik. Ta specyfikacja mówi, że metoda nie musi obsługiwać ujemnych wartości dla x i musi tylko zapewnić, że wynik również nie będzie ujemny . Dwa możliwe sposoby wzmocnienia tej specyfikacji to wzmocnienie warunku końcowego do stwierdzenia wyniku = | x |, tj. Wynik jest równy wartości bezwzględnej x lub osłabienie warunku wstępnego do „prawda”, tj. Wszystkie wartości dla x powinny być obsługiwane . Oczywiście możemy również połączyć oba, w specyfikację, która stwierdza, że ​​wynik powinien być równy wartości bezwzględnej x dla dowolnej wartości x .

Należy jednak zauważyć, że możliwe jest wzmocnienie specyfikacji ((P s , Q s ) ⇒ (P t , Q t )) bez wzmacniania warunku końcowego (Q s ⇏ Q t ). Rozważ specyfikację metody wartości bezwzględnej, która określa warunek wstępny 0 ≤ x i wynik warunku końcowego = x. Specyfikacja określająca warunek wstępny „prawda” i wynik warunku końcowego = | x | wzmacnia tę specyfikację, mimo że wynik warunku końcowego = | x | nie wzmacnia (ani nie osłabia) wyniku warunku końcowego = x. Warunkiem koniecznym, aby specyfikacja z warunkiem wstępnym P s i warunkiem końcowym Q s była silniejsza niż specyfikacja z warunkiem wstępnym P t i warunkiem końcowym Q t, jest to, że P s jest słabsze niż P t, a „Q s lub nie P s ” jest silniejsze niż " Q t czy nie P t ". Rzeczywiście, „wynik = | x | lub fałsz” wzmacnia ”wynik = x lub x <0”.

„Zastępowalność”

W wpływowym przemówieniu na temat abstrakcji danych i hierarchii klas na konferencji badań nad językiem programowania OOPSLA 1987 Barbara Liskov powiedziała, co następuje: „Chodzi o coś podobnego do następującej właściwości zastępowania: Jeśli dla każdego obiektu typu S istnieje obiekt typu T taki, że dla wszystkich programów P zdefiniowanych w kategoriach T zachowanie P pozostaje niezmienione, gdy jest podstawiane , to S jest podtypem T. " Ta charakterystyka jest od tego czasu szeroko znana jako zasada substytucji Liskova (LSP) . Niestety ma kilka problemów. Po pierwsze, w swoim pierwotnym sformułowaniu jest zbyt silny: rzadko chcemy, aby zachowanie podklasy było identyczne z zachowaniem jej nadklasy; podstawianie obiektu podklasy za obiekt nadklasy jest często wykonywane z zamiarem zmiany zachowania programu, aczkolwiek, jeśli przestrzegane jest podtyp behawioralny, w sposób, który zachowuje pożądane właściwości programu. Po drugie, nie wspomina o specyfikacjach , więc zachęca do błędnego czytania, w którym implementacja typu S jest porównywana z implementacją typu T. Jest to problematyczne z kilku powodów, z których jednym jest to, że nie obsługuje typowego przypadku, w którym T jest streszczenie i nie ma implementacji. Po trzecie, i najdelikatniej, w kontekście zorientowanego obiektowo programowania imperatywnego trudno jest precyzyjnie zdefiniować, co oznacza uniwersalne lub egzystencjalne kwantyfikowanie obiektów danego typu lub podstawianie jednego obiektu innym. W powyższym przykładzie nie zastępujemy obiektu Stack obiektem Bag, po prostu używamy obiektu Stack jako obiektu Bag.

W wywiadzie z 2016 roku sama Liskov wyjaśnia, że ​​to, co przedstawiła w swoim przemówieniu programowym, było „nieformalną zasadą”, którą Jeannette Wing później zaproponowała, aby „próbowali dokładnie zrozumieć, co to oznacza”, co doprowadziło do ich wspólnej publikacji na temat behawioralnych podtyp i rzeczywiście to „technicznie nazywa się podtypem behawioralnym”. Podczas rozmowy nie używa terminologii dotyczącej substytucji do omawiania pojęć.

Uwagi

Bibliografia

  • Parkinson, Matthew J .; Bierman, Gavin M. (styczeń 2008). „Logika separacji, abstrakcja i dziedziczenie”. Uwagi ACM SIGPLAN . 43 (1): 75–86. doi : 10.1145 / 1328897.1328451 .