Cirkel-ellipsproblem

Cirkel -ellipsproblemet i mjukvaruutveckling (kallas ibland kvadrat-rektangelproblemet ) illustrerar flera fallgropar som kan uppstå när man använder subtyp polymorfism i objektmodellering . Problemen uppstår oftast när man använder objektorienterad programmering (OOP). Per definition är detta problem ett brott mot Liskov-substitutionsprincipen , en av de SOLID- principerna.

Problemet gäller vilken undertypning eller arvsförhållande som ska finnas mellan klasser som representerar cirklar och ellipser (eller på liknande sätt, kvadrater och rektanglar ). Mer generellt illustrerar problemet de svårigheter som kan uppstå när en basklass innehåller metoder som muterar ett objekt på ett sätt som kan ogiltigförklara en (starkare) invariant som finns i en härledd klass, vilket gör att Liskov-substitutionsprincipen bryts.

Förekomsten av cirkel-ellipsproblemet används ibland för att kritisera objektorienterad programmering. Det kan också antyda att hierarkiska taxonomier är svåra att göra universella, vilket innebär att situationsanpassade klassificeringssystem kan vara mer praktiska.

Beskrivning

Det är en central grundsats för objektorienterad analys och design att subtyp polymorfism , som implementeras i de flesta objektorienterade språk via arv , ska användas för att modellera objekttyper som är undergrupper av varandra; detta kallas vanligen för är-en relation. I föreliggande exempel är uppsättningen cirklar en delmängd av uppsättningen ellipser; cirklar kan definieras som ellipser vars stora och små axlar är lika långa. Således kommer kod skriven i ett objektorienterat språk som modellerar former ofta välja att göra klassen Circle till en underklass av klassen Ellipse , dvs ärver från den.

En underklass måste ge stöd för allt beteende som stöds av superklassen; underklasser måste implementera alla mutatormetoder som definieras i en basklass. I det aktuella fallet ändrar metoden Ellipse.stretchX längden på en av dess axlar på plats. Om Circle ärver från Ellipse måste den också ha en metod stretchX , men resultatet av denna metod skulle vara att ändra en cirkel till något som inte längre är en cirkel. Klassen Circle kan inte samtidigt uppfylla sina egna invarianter och beteendekraven för Ellipse.stretchX -metoden.

Ett relaterat problem med detta arv uppstår när man överväger implementeringen. En ellips kräver att fler tillstånd beskrivs än en cirkel, eftersom den förra behöver attribut för att specificera längden och rotationen av de stora och små axlarna medan en cirkel bara behöver en radie. Det kan vara möjligt att undvika detta om språket (som Eiffel ) gör konstanta värden för en klass, fungerar utan argument och datamedlemmar utbytbara.

Vissa författare har föreslagit att vända på förhållandet mellan cirkel och ellips, med motiveringen att en ellips är en cirkel med fler förmågor. Tyvärr misslyckas ellipser med att tillfredsställa många av cirklarnas invarianter; om Circle har en metodradie måste Ellipse nu också tillhandahålla den.

Möjliga lösningar

Man kan lösa problemet genom att:

byta modell
använda ett annat språk (eller en befintlig eller specialskriven tillägg av något befintligt språk)
använder ett annat paradigm

Exakt vilket alternativ som är lämpligt beror på vem som skrev Circle och vem som skrev Ellipse . Om samma författare designar båda från början, kommer författaren att kunna definiera gränssnittet för att hantera denna situation. Om Ellipse -objektet redan var skrivet och inte kan ändras, är alternativen mer begränsade.

Byt modell

Returnera värde för framgång eller misslyckande

Tillåt objekten att returnera ett "framgångs- eller misslyckande"-värde för varje modifierare eller skapa ett undantag vid misslyckande. Detta görs vanligtvis när det gäller fil-I/O, men kan också vara till hjälp här. Nu Ellipse.stretchX och returnerar "true", medan Circle.stretchX helt enkelt returnerar "false". Detta är i allmänhet god praxis, men kan kräva att den ursprungliga författaren till Ellipse förutsåg ett sådant problem och definierade mutatorerna som att returnera ett värde. Det kräver också att klientkoden testar returvärdet för stöd för stretchfunktionen, vilket i själva verket är som att testa om det refererade objektet antingen är en cirkel eller en ellips. Ett annat sätt att se på detta är att det är som att lägga i kontraktet att kontraktet kan eller inte kan uppfyllas beroende på objektet som implementerar gränssnittet. Så småningom är det bara ett smart sätt att kringgå Liskov-begränsningen genom att på förhand säga att postvillkoret kan vara giltigt eller inte.

Alternativt kan Circle.stretchX skapa ett undantag (men beroende på språket kan detta också kräva att den ursprungliga författaren till Ellipse förklarar att den kan ge ett undantag).

Returnera det nya värdet på X

Detta är en liknande lösning som ovan, men är något mer kraftfull. Ellipse.stretchX returnerar nu det nya värdet för sin X-dimension. Nu Circle.stretchX helt enkelt returnera sin nuvarande radie. Alla ändringar måste göras genom Circle.stretch , som bevarar cirkeln invariant.

Räkna med ett svagare kontrakt på Ellipse

Om gränssnittskontraktet för Ellipse bara anger att "stretchX modifierar X-axeln" och inte säger "och inget annat kommer att förändras", så kan Circle helt enkelt tvinga X- och Y-dimensionerna att vara desamma. Circle.stretchX och Circle.stretchY ändrar båda både X- och Y-storleken.

Circle::stretchX(x) { xSize = ySize = x; } Circle::stretchY(y) { xSize = ySize = y; }

Konvertera cirkeln till en ellips

Om Circle.stretchX anropas, ändrar Circle sig själv till en Ellips . Till exempel i Common Lisp kan detta göras via metoden CHANGE-CLASS . Detta kan dock vara farligt om någon annan funktion förväntar sig att det ska vara en cirkel . Vissa språk utesluter denna typ av förändring, och andra lägger restriktioner på Ellipse -klassen för att vara en acceptabel ersättning för Circle . För språk som tillåter implicit konvertering som C++ kan detta bara vara en dellösning som löser problemet på call-by-copy, men inte på call-by-referens.

Gör alla instanser konstanta

Man kan ändra modellen så att instanser av klasserna representerar konstanta värden (dvs de är oföränderliga ). Detta är implementeringen som används i rent funktionell programmering.

I det här fallet måste metoder som stretchX ändras för att ge en ny instans, snarare än att modifiera instansen de agerar på. Det betyder att det inte längre är ett problem att definiera Circle.stretchX , och arvet speglar det matematiska förhållandet mellan cirklar och ellipser.

En nackdel är att ändring av värdet på en instans då kräver en tilldelning , som är obekväm och utsatt för programmeringsfel, t.ex.

Orbit(planet[i]) := Orbit(planet[i]).stretchX

En andra nackdel är att ett sådant uppdrag konceptuellt innebär ett tillfälligt värde, vilket skulle kunna minska prestandan och vara svår att optimera.

Faktorer ut modifierare

Man kan definiera en ny klass MutableEllipse , och lägga in modifierarna från Ellipse i den. Cirkeln ärver bara frågor från Ellipse .

Detta har en nackdel med att införa en extra klass där allt som önskas är att specificera att Circle inte ärver modifierare från Ellipse .

Ställa förutsättningar för modifierare

Man kan specificera att Ellipse.stretchX endast är tillåtet på instanser som uppfyller Ellipse.stretchable , och annars kommer att skapa ett undantag . Detta kräver att man förutser problemet när Ellipse definieras.

Faktorera ut gemensam funktionalitet till en abstrakt basklass

Skapa en abstrakt basklass som heter EllipseOrCircle och sätt in metoder som fungerar med både Circle s och Ellipse s i den här klassen. Funktioner som kan hantera båda typerna av objekt kommer att förvänta sig en EllipseOrCircle , och funktioner som använder Ellipse- eller Circle -specifika krav kommer att använda de descendant-klasserna. Men Circle är då inte längre en Ellipse- underklass, vilket leder till "en Circle is not a sort of Ellipse "-situation som beskrivs ovan.

Släpp alla arvsförhållanden

Detta löser problemet i ett slag. Alla vanliga operationer som önskas för både en Circle och Ellipse kan abstraheras till ett gemensamt gränssnitt som varje klass implementerar, eller till mixins .

Man kan också tillhandahålla omvandlingsmetoder som Circle.asEllipse , som returnerar ett föränderligt Ellips-objekt initierat med hjälp av cirkelns radie. Från den punkten är det ett separat objekt och kan muteras separat från den ursprungliga cirkeln utan problem. Metoder som konverterar åt andra hållet behöver inte binda sig till en strategi. Till exempel kan det finnas både Ellipse.minimalEnclosingCircle och Ellipse.maximalEnclosedCircle , och vilken annan strategi som helst.

Kombinera klasscirkel till klassellips

Sedan, varhelst en cirkel användes tidigare, använd en ellips.

En cirkel kan redan representeras av en ellips. Det finns ingen anledning att ha klass Circle om den inte behöver några cirkelspecifika metoder som inte kan tillämpas på en ellips, eller om inte programmeraren vill dra nytta av konceptuella och/eller prestandafördelar med cirkelns enklare modell.

Omvänt arv

Majorinc föreslog en modell som delar upp metoder på modifierare, väljare och allmänna metoder. Endast väljare kan ärvas automatiskt från superklass, medan modifierare bör ärvas från underklass till superklass. I allmänhet måste metoderna ärvas uttryckligen. Modellen kan emuleras i språk med flera arv , med hjälp av abstrakta klasser .

Ändra programmeringsspråk

Detta problem har enkla lösningar i ett tillräckligt kraftfullt OO-programmeringssystem. I huvudsak handlar cirkel-ellipsproblemet om att synkronisera två representationer av typ: den de facto typen baserad på objektets egenskaper och den formella typen som är associerad med objektet av objektsystemet. Om dessa två informationsbitar, som i slutändan bara är bitar i maskinen, hålls synkroniserade så att de säger samma sak är allt bra. Det är tydligt att en cirkel inte kan tillfredsställa de invarianter som krävs av den medan dess basellipsmetoder tillåter mutation av parametrar. Möjligheten finns dock att när en cirkel inte kan möta cirkelinvarianterna kan dess typ uppdateras så att den blir en ellips. Om en cirkel som har blivit en de facto ellips inte byter typ, då är dess typ en informationsbit som nu är inaktuell, som återspeglar objektets historia (hur det en gång konstruerades) och inte dess nuvarande verklighet ( vad det sedan har muterats till).

Många objektsystem i populär användning bygger på en design som tar för givet att ett objekt bär samma typ under hela sin livstid, från konstruktion till färdigställande. Detta är inte en begränsning av OOP, utan snarare för särskilda implementeringar.

Följande exempel använder Common Lisp Object System (CLOS) där objekt kan byta klass utan att förlora sin identitet. Alla variabler eller andra lagringsplatser som innehåller en referens till ett objekt fortsätter att hålla en referens till samma objekt efter att det byter klass.

Cirkel- och ellipsmodellerna är medvetet förenklade för att undvika distraherande detaljer som inte är relevanta för cirkel-ellipsproblemet. En ellips har två halvaxlar som kallas h-axel och v-axel i koden. Eftersom en cirkel är en ellips, ärver en cirkel dessa, och har även en radieegenskap , vilket värde är lika med axlarnas (som naturligtvis måste vara lika med varandra).

  



  
    
       
  
    
       

  
        
         

  
        







      
      

       
  
  
  
  
      
           







   
         
      






     
   

   
       
      










    
                                                         
      
       
     
            (  defgeneriska  kontrollbegränsningar  (  form  ))  ;; Tillbehören på formobjekt.  Restriktioner för föremål   ;; måste kontrolleras efter att endera axelvärdet har ställts in.   (  defgenerisk  h-axel  (  form  ))  (  defgenerisk  (  setf  h  -axel  )  (  nyvärdesform  )  (  :metod  :efter  (  nyvärdesform  )  (  check-constraints  form  )))  (  defgenerisk  v-  axel  (  form  ) )  (  defgeneric  (  setf  v-axel  )  (  nyvärdesform  )  (  :  metod  :efter  (  nyvärdesform  )  (  check-constraints  shape  )))  (  defclass  ellips  ()  ((  h-axel  :typ  real  :  accessor  h -axis  :initarg  :h-axis  )  (  v-axel  :typ  real  :accessor  v-axel  :initarg  :v-axel  )))  (  defclass  circle  (  ellips  )  ((  radie  :typ  real  :accessor  radie  :initarg  :radius  ) ))  ;;;  ;;; En cirkel har en radie, men också en h-axel och v-axel som   ;;; det ärver från en ellips.  Dessa måste hållas synkroniserade   ;;; med radien när objektet initieras och   ;;; när dessa värden ändras.   ;;;  (  defmethod  initialize-instance  :after  ((  c  circle  )  &key  radie  )  (  setf  (  radie  c  )  radie  ))  ;; via setf-metoden nedan   (  defmethod  (  setf  radius  )  :after  ((  new-value  real  )  (  c  circle  ))  ;; Vi använder SLOT-VALUE snarare än accessorerna för att undvika att ändra  ;; klass i onödan mellan de två tilldelningarna; som cirkeln  ;; kommer att ha olika h-axel- och v-axelvärden mellan ;;-  tilldelningarna, och sedan samma värden efter tilldelningar.  (  setf  (  lucka-värde  c  ' h-axel  )  new-value  (  lucka-värde  c  'v-axeln  )  nytt-värde  ))  ;;;  ;;; Efter en uppgift görs till cirkelns   ;;; h-axel eller v-axel, byte av typ är nödvändig,   ;;; om inte det nya värdet är samma som radien.   ;;;  (  defmethod  check-constraints  ((  c  circle  ))  (  om inte  (  =  (  radie  c  )  (  h-axel  c  )  (  v-axel  c  ))  (  change-class  c  'ellips  )))  ;;;  ;;; Ellipsen ändras till en cirkel om accessorer   ;;; mutera det så att axlarna är lika,   ;;; eller om ett försök görs att konstruera det på det sättet.   ;;;  (  defmethod  initialize-instance  :after  ((  e  ellips  )  &key  )  (  check-constraints  e  ))  (  defmethod  check-constraints  ((  e  ellips  ))  (  när  (  =  (  h-axel e  )  (  v  -axel  e  ))  (  ändra-klass  e  'cirkel  )))  ;;;  ;;; Metod för att en ellips blir en cirkel.  I denna metamorfos,   ;;; objektet får en radie som måste initieras.   ;;; Det finns en "sanity check" här för att signalera ett fel om ett försök   ;;; är gjord för att omvandla en ellips vars axlar är ojämna   ;;; med ett uttryckligt ändringsklasssamtal.   ;;; Hanteringsstrategin här är att basera radien från   ;;; h-axeln och signalerar ett fel.   ;;; Detta hindrar inte klassbytet;  skadan är redan skedd.   ;;;  (  defmethod  update-instance-for-different-class  :after  ((  old-e  ellips  )  (  new-c  circle  )  &key  )  (  setf  (  radie  new-c  )  (  h-axel  old-e  ))  (  om inte  (  =  (  h-axel  old-e  )  (  v-axel  old-e  ))  (  fel  "ellips ~s kan inte ändras till en cirkel eftersom det inte är en!"  old-e ))  )

Denna kod kan demonstreras med en interaktiv session med hjälp av CLISP-implementeringen av Common Lisp.








































 $  clipp -q -i cirkel-ellips.lisp  [1]> (make-instans 'ellips :v-axel 3 :h-axel 3) #  <  CIRCLE  #x218AB566>  [2]> (make-instans 'ellips :v -axel 3 :h-axel 4)  #  <ELLIPSE  #x218BF56E>  [3]> (defvar obj (gör-instans 'ellips :v-axel 3 :h-axel 4))  OBJ  [4]> (klass-av obj )  #  <STANDARD-CLASS ELLIPSE>  [5]> (radius obj)  *** - NO-APPLICABLE-METHOD: När #<STANDARD-GENERIC-FUNCTION RADIUS> anropas  med argument (#<ELLIPSE #x2188C5F6>), ingen metod är tillämplig.  Följande omstarter är tillgängliga:  FÖRSÖK IGEN :R1 försök anropa RADIUS igen  RETURN :R2 ange returvärden  ABORT :R3 Avbryt huvudslinga  Break 1 [6]> :a  [7]> (setf (v-axel obj) 4)  4  [8 ]> (radius obj)  4  [9]> (klass-av obj)  #  <STANDARD-KLASS CIRKEL>  [10]> (setf (radius obj) 9)  9  [11]> (v-axel obj)  9  [12 ]> (h-axel obj)  9  [13]> (setf (h-axel obj) 8)  8  [14]> (klass-av obj)  #  <STANDARD-KLASS ELLIPS>  [15]> (radius obj)  * ** - NO-APPLICABLE-METHOD: När #<STANDARD-GENERIC-FUNCTION RADIUS> anropas  med argument (#<ELLIPSE #x2188C5F6>), är ingen metod tillämplig.  Följande omstarter är tillgängliga:  FÖRSÖK IGEN :R1 försök anropa RADIUS igen  RETURN :R2 ange returvärden  ABORT :R3 Avbryt huvudslinga  Break 1 [16]> :a  [17]>

Utmana premissen för problemet

Även om det vid första anblicken kan verka uppenbart att en cirkel är en ellips, överväg följande analoga kod.

 

       
       
 klass  Person  {  void  walkNorth  (  int  meter  )  {...}  void  walkEast  (  int  meter  )  {...}  }

Nu är en fånge uppenbarligen en person. Så logiskt sett kan en underklass skapas:

   

       
       
 klass  Fånge  förlänger  Person  {  void  walkNorth  (  int  meter  )  {...}  void  walkEast  (  int  meter  )  {...}  }

Också uppenbarligen leder detta till problem, eftersom en fånge inte är fri att röra sig ett godtyckligt avstånd i någon riktning, men kontraktet för klassen Person säger att en person kan.

Således skulle klassen Person bättre kunna heta FreePerson . Om så vore fallet, då är tanken att klass Fånge förlänger FreePerson helt klart fel.

I analogi är alltså en cirkel inte en ellips, eftersom den saknar samma frihetsgrader som en ellips.

Genom att använda bättre namn kan en cirkel istället få namnet OneDiameterFigure och en ellips kan heta TwoDiameterFigure . Med sådana namn är det nu mer uppenbart att TwoDiameterFigure bör utöka OneDiameterFigure , eftersom det lägger till en annan egenskap till den; medan OneDiameterFigure har en egenskap med en enda diameter, har TwoDiameterFigure två sådana egenskaper (dvs. en huvudaxellängd och en mindre axellängd).

Detta tyder starkt på att arv aldrig bör användas när underklassen begränsar den implicita friheten i basklassen, utan endast bör användas när underklassen lägger till extra detaljer till konceptet som representeras av basklassen som i 'Monkey' är -ett djur'.

Att påstå att en fånge inte kan röra sig ett godtyckligt avstånd i någon riktning och en person kan är en felaktig premiss än en gång. Alla föremål som rör sig i valfri riktning kan stöta på hinder. Rätt sätt att modellera detta problem skulle vara att ha ett WalkAttemptResult walkToDirection(int meter, Direction direction) kontrakt. Nu, när du implementerar walkToDirection för underklassen Prisoner, kan du kontrollera gränserna och returnera korrekta promenadresultat.

Invarians

Man kan begreppsmässigt betrakta en cirkel och en ellips som båda föränderliga behållartyper, alias för MutableContainer<ImmutableCircle> respektive MutableContainer<ImmutableEllipse> . I det här fallet ImmutableCircle anses vara en undertyp av ImmutableEllipse . Typen T i MutableContainer<T> kan både skrivas till och läsas från, vilket antyder att den varken är samvariant eller kontravariant, utan istället invariant. Därför Circle inte en undertyp av Ellipse , inte heller tvärtom.

Robert C. Martin , The Liskov Substitution Principle , C++-rapport, mars 1996.

externa länkar

https://web.archive.org/web/20150409211739/http://www.parashift.com/c++-faq-lite/proper-inheritance.html#faq-21.6 En populär C++ FAQ-sida av Marshall Cline. konstaterar och förklarar problemet.
Constructive Deconstruction of Subtyping av Alistair Cockburn på sin egen webbplats. Teknisk/matematisk diskussion om maskinskrivning och subtypning, med tillämpningar på detta problem.
Henney, Kevlin (2003-04-15). "Från mekanism till metod: total ellips" . Dr Dobbs .
http://orafaq.com/usenet/comp.databases.theory/2001/10/01/0001.htm Början på en lång tråd (följ kanske svar: länkarna) om Oracle FAQ som diskuterar problemet. Hänvisar till skrifter av CJ Date. Viss partiskhet mot Smalltalk .
LiskovSubstitutionPrinciple på WikiWikiWeb
Subtyping, Subclassing och Trouble with OOP , en uppsats som diskuterar ett relaterat problem: ska set ärva från påsar?
Subtyping by Constraints in Object-Oriented Databases , en uppsats som diskuterar en utökad version av cirkel-ellipsproblemet i miljön för objektorienterade databaser.