Podtypování na základě chování - Behavioral subtyping

V objektově orientovaném programování je behaviorální podtypování principem, že podtřídy by měly uspokojit očekávání klientů přistupujících k objektům podtříd prostřednictvím odkazů typu nadtřídy, nejen pokud jde o syntaktickou bezpečnost (například absence chyb „metoda nebyla nalezena“), ale také pokud jde o správnost chování. Konkrétně by vlastnosti, které klienti mohou prokázat pomocí specifikace předpokládaného typu objektu, měli držet, i když je objekt ve skutečnosti členem podtypu tohoto typu.

Zvažte například typ zásobníku a typ fronty, které oba mají metodu put pro přidání prvku a metodu get pro odebrání jednoho. Předpokládejme, že dokumentace spojená s těmito typy určuje, že metody typu Stack se budou chovat podle očekávání pro hromádky (tj. Budou vykazovat chování LIFO ) a že metody typu fronty se budou chovat podle očekávání pro fronty (tj. Budou vykazovat chování FIFO ). Předpokládejme, že tento typ Stack byl deklarován jako podtřída typu Queue. Většina překladačů programovacího jazyka ignoruje dokumentaci a provádí pouze kontroly, které jsou nezbytné k zachování bezpečnosti typu . Protože pro každou metodu typu Queue typ Stack poskytuje metodu se shodným názvem a podpisem, bude tato kontrola úspěšná. Klienti přistupující k objektu Stack prostřednictvím odkazu na typ fronty by však na základě dokumentace fronty očekávali chování FIFO, ale sledovali chování LIFO, zneplatňovali důkazy o správnosti těchto klientů a potenciálně vedly k nesprávnému chování programu jako celku.

Tento příklad porušuje podtyp chování, protože typ Stack není podtypem chování typu Queue: není pravda, že chování popsané v dokumentaci typu Stack (tj. Chování LIFO) odpovídá dokumentaci typu Queue (která vyžaduje chování FIFO) .

Naproti tomu program, kde Stack i Queue jsou podtřídami typu Bag, jehož specifikací pro get je pouze to, že odstraňuje nějaký prvek, uspokojuje podtyp chování a umožňuje klientům bezpečně uvažovat o správnosti na základě předpokládaných typů objektů, které komunikovat s. Ve skutečnosti jakýkoli objekt, který vyhovuje specifikaci Stack nebo Queue, také vyhovuje specifikaci Bag.

Je důležité zdůraznit, že to, zda je typ S podtypem chování typu T, závisí pouze na specifikaci (tj. Dokumentaci ) typu T; provádění typu T, má-li nějaký, je zcela irelevantní na tuto otázku. Ve skutečnosti typ T nemusí mít ani implementaci; může to být čistě abstraktní třída. Jako další případ v bodě zadejte výše Stack je behaviorální podtyp typu Bag, i když implementace typu Bag vykazuje chování FIFO: důležité je, že specifikace typu Bag neurčuje, který prvek je odstraněn metodou get . To také znamená, že behaviorální podtyp lze diskutovat pouze s ohledem na konkrétní (behaviorální) specifikaci pro každý zapojený typ a že pokud zapojené typy nemají žádnou přesně definovanou behaviorální specifikaci, nelze podtypování chování smysluplně diskutovat.

Ověření podtypů chování

Typ S je behaviorální podtyp typu T, pokud každé chování povolené specifikací S je také povoleno specifikací T. To vyžaduje zejména to, že pro každou metodu M z T je specifikace M v S silnější než ten v T.

Specifikace Způsob předpokladu, že a předpokladem P s a s postcondition Q y je větší než jedna, kterou poskytla předpokladem P t a postcondition Q t (formálně: (P s , Q s ) ⇒ (P t , Q t )), pokud P s je slabší než P t (tj. P t znamená P s ) a Q s je silnější než Q t (tj. Q s znamená Q t ). To znamená, že posílení specifikace metody lze provést posílením postcondition a oslabením předběžné podmínky. Specifikace metody je skutečně silnější, pokud ukládá konkrétnější omezení na výstupy pro vstupy, které již byly podporovány, nebo pokud vyžaduje podporu více vstupů.

Zvažte například (velmi slabou) specifikaci pro metodu, která počítá absolutní hodnotu argumentu x , která určuje podmínku 0 ≤ x a podmínku 0 ≤ výsledek. Tato specifikace říká, že metoda nemusí podporovat záporné hodnoty pro x a musí pouze zajistit, aby byl výsledek také nezáporný. Dva možné způsoby, jak tuto specifikaci posílit, jsou posílení postcondice na state result = | x |, tj. Výsledek se rovná absolutní hodnotě x, nebo oslabení předpokladu na „true“, tj. Všechny hodnoty pro x by měly být podporovány . Samozřejmě můžeme také kombinovat obojí do specifikace, která uvádí, že výsledek by se měl rovnat absolutní hodnotě x , pro jakoukoli hodnotu x .

Všimněte si však, že je možné posílit specifikaci ((P s , Q s ) ⇒ (P t , Q t )) bez posílení postcondition (Q s ⇏ Q t ). Zvažte specifikaci metody absolutní hodnoty, která určuje podmínku 0 ≤ x a výsledek postcondition = x. Specifikace, která určuje podmínku „true“ a výsledek postcondition = | x | posiluje tuto specifikaci, i když výsledek postcondition = | x | neposiluje (nebo neoslabuje) výsledek postcondition = x. Nutnou podmínkou pro silnější specifikaci s předpokladem P s a postcondition Q s než s předpokladem P t a postcondition Q t je, že P s je slabší než P t a „Q s nebo ne P s “ je silnější než „ Q t nebo ne P t ". „Result = | x | or false" skutečně posiluje „result = x nebo x <0".

„Substitutability“

V vlivné hlavní řeči o abstrakci dat a hierarchií tříd na konferenci o výzkumu programovacího jazyka OOPSLA 1987 Barbara Liskov řekla toto: „To, co se zde chce, je něco jako následující substituční vlastnost: Pokud pro každý objekt typu S existuje objekt typu T tak, že pro všechny programy P definované v termínech T se chování P nezmění, když je nahrazeno , pak S je podtyp T. " Tato charakterizace byla od té doby obecně známá jako Liskovův substituční princip (LSP) . Bohužel však má několik problémů. Za prvé, ve své původní formulaci je příliš silná: zřídka chceme, aby chování podtřídy bylo stejné jako chování její nadtřídy; nahrazení objektu podtřídy objektem nadtřídy se často provádí s úmyslem změnit chování programu, i když při respektování podtypů chování způsobem, který udržuje požadované vlastnosti programu. Zadruhé nezmiňuje specifikace , proto vyzývá k nesprávnému čtení, kde je implementace typu S srovnávána s implementací typu T. To je problematické z několika důvodů, jedním z nich je, že nepodporuje běžný případ, kdy T je abstraktní a nemá žádnou implementaci. Zatřetí, a nejjemněji, v kontextu objektově orientovaného imperativního programování je obtížné přesně definovat, co to znamená univerzálně nebo existenčně kvantifikovat přes objekty daného typu nebo nahradit jeden objekt jiným. Ve výše uvedeném příkladu nenahrazujeme objekt Stack objektem Bag, jednoduše používáme objekt Stack jako objekt Bag.

V rozhovoru v roce 2016 sama Liskov vysvětluje, že to, co uvedla ve svém hlavním projevu, bylo „neformální pravidlo“, které Jeannette Wing později navrhla, aby se „pokusili přesně zjistit, co to znamená“, což vedlo k jejich společné publikaci o behaviorálním chování podtyp, a skutečně to „technicky se tomu říká podtyp chování“. Během rozhovoru nepoužívá k diskusi o pojmech substituční terminologii.

Poznámky

Reference

  • Parkinson, Matthew J .; Bierman, Gavin M. (leden 2008). "Logika separace, abstrakce a dědičnost". Oznámení ACM SIGPLAN . 43 (1): 75–86. doi : 10.1145 / 1328897.1328451 .