Kowariancja i kontrawariancja (informatyka)

Wiele systemów typu języka programowania obsługuje podtypy . Na przykład, jeśli typ Cat jest podtypem Animal , wówczas wyrażenie typu Cat powinno być zastępowalne wszędzie tam, gdzie jest używane wyrażenie typu Animal .

Wariancja odnosi się do tego, w jaki sposób podtypowanie między bardziej złożonymi typami odnosi się do podtypowania między ich składnikami. Na przykład, w jaki sposób lista kotów ma się odnosić do listy zwierząt ? Lub w jaki sposób funkcja, która zwraca Cat, powinna odnosić się do funkcji, która zwraca Animal ?

W zależności od wariancji konstruktora typu , relacja podtypów typów prostych może być zachowana, odwrócona lub zignorowana dla odpowiednich typów złożonych. Na przykład w OCaml „list of Cat” jest podtypem „list of Animal”, ponieważ konstruktor typu listy jest kowariantny . Oznacza to, że relacja podtypów typów prostych jest zachowana dla typów złożonych.

Z drugiej strony „funkcja od zwierzęcia do łańcucha” jest podtypem „funkcji od kota do łańcucha”, ponieważ konstruktor typu funkcji jest kontrawariantny w typie parametru. Tutaj relacja podtypów typów prostych jest odwrócona dla typów złożonych.

Innymi słowy, kowariancja to cecha bycia innym przez bycie bardziej szczegółowym ( Kot jest kowariantny dla Zwierzęcia ), podczas gdy kontrawariancja jest cechą bycia innym przez bycie bardziej ogólnym ( Zwierzę jest przeciwstawne do Kota ).

Projektant języka programowania weźmie pod uwagę wariancję podczas opracowywania reguł pisania dla funkcji języka, takich jak tablice, dziedziczenie i ogólne typy danych . Dzięki uczynieniu konstruktorów typów kowariantnymi lub kontrawariantnymi zamiast niezmiennymi, więcej programów zostanie zaakceptowanych jako dobrze wpisane. Z drugiej strony programiści często uważają kontrawariancję za nieintuicyjną, a dokładne śledzenie wariancji w celu uniknięcia błędów typu w czasie wykonywania może prowadzić do skomplikowanych reguł pisania.

Aby zachować prostotę systemu typów i umożliwić użyteczne programy, język może traktować konstruktor typu jako niezmienny, nawet jeśli można bezpiecznie uznać go za wariant, lub traktować go jako kowariantny, nawet jeśli mogłoby to naruszyć bezpieczeństwo typów.

Definicja formalna

W systemie typów języka programowania regułą pisania lub konstruktorem typu jest:

• kowariantny, jeśli zachowuje kolejność typów (≤) , która porządkuje typy od bardziej szczegółowych do bardziej ogólnych: Jeśli A ≤ B , to I<A> ≤ I<B> ;
• kontrawariantne, jeśli odwraca to uporządkowanie: Jeśli A ≤ B , to I<B> ≤ I<A> ;
• dwuwariantny , jeśli oba z nich mają zastosowanie (tj. jeśli A ≤ B , to I<A> ≡ I<B> );
• wariant , jeśli jest kowariantny, kontrawariantny lub dwuwariantny;
• niezmienny lub niezmienny , jeśli nie wariant.

W artykule rozważono, jak ma to zastosowanie do niektórych typowych konstruktorów typów.

C# przykłady

Na przykład w C# , jeśli Cat jest podtypem Animal , to:

• IEnumerable < Cat > jest podtypem IEnumerable < Animal > . Podtypy są zachowywane, ponieważ IEnumerable < T > jest kowariantna na T .
• Akcja < Zwierzę > jest podtypem akcji < Kot > . Podtypowanie jest odwrócone, ponieważ Akcja < T > jest kontrawariantna na T .
• Ani IList < Cat > ani IList < Animal > nie jest podtypem drugiego, ponieważ IList < T > jest niezmiennikiem T .

Wariancja ogólnego interfejsu języka C# jest deklarowana przez umieszczenie atrybutu out (kowariancja) lub in (kontrawariantność) na parametrach typu (zero lub więcej). Dla każdego tak oznaczonego parametru typu kompilator ostatecznie weryfikuje, przy czym każde naruszenie jest krytyczne, że takie użycie jest globalnie spójne. Powyższe interfejsy są zadeklarowane jako IEnumerable < out T > , Action < in T > i IList < T > . Typy z więcej niż jednym parametrem typu mogą określać różne wariancje dla każdego parametru typu. Na przykład typ delegata Func < in T , out TResult > reprezentuje funkcję z kontrawariantnym parametrem wejściowym typu T i kowariantną wartością zwracaną typu TResult .

Reguły typowania dla wariancji interfejsów zapewniają bezpieczeństwo typu. Na przykład Action < T > reprezentuje pierwszorzędną funkcję oczekującą argumentu typu T , a zamiast funkcji obsługującej tylko koty zawsze można użyć funkcji obsługującej dowolny typ zwierzęcia.

Tablice

Typy danych tylko do odczytu (źródła) mogą być kowariantne; typy danych tylko do zapisu (ujścia) mogą być kontrawariantne. Zmienne typy danych, które działają zarówno jako źródła, jak i ujścia, powinny być niezmienne. Aby zilustrować to ogólne zjawisko, rozważmy typ tablicy . Dla typu Animal możemy utworzyć typ Animal [] , który jest „tablicą zwierząt”. Na potrzeby tego przykładu ta tablica obsługuje zarówno elementy do odczytu, jak i do zapisu.

Mamy możliwość potraktowania tego jako:

• kowariant: kot [] jest zwierzęciem [] ;
• kontrawariantne: zwierzę [] to kot [] ;
• niezmiennik: zwierzę [] nie jest kotem [] , a kot [] nie jest zwierzęciem [] .

Jeśli chcemy uniknąć błędów typograficznych, to tylko trzeci wybór jest bezpieczny. Oczywiście nie każde Animal [] może być traktowane tak, jakby było Cat [] , ponieważ klient czytający z tablicy będzie oczekiwał Cat , ale Animal [] może zawierać np. Dog . Zatem reguła kontrawariantna nie jest bezpieczna.

I odwrotnie, Kot [] nie może być traktowany jak Zwierzę [] . Zawsze powinno być możliwe umieszczenie psa w zwierzęciu [] . W przypadku tablic kowariantnych nie można zagwarantować, że będzie to bezpieczne, ponieważ magazyn zapasowy może w rzeczywistości być tablicą kotów. Zatem reguła kowariantna również nie jest bezpieczna — konstruktor tablicy powinien być niezmienny . Zauważ, że jest to problem tylko dla zmiennych tablic; reguła kowariantna jest bezpieczna dla tablic niezmiennych (tylko do odczytu). Podobnie reguła kontrawariantna byłaby bezpieczna dla tablic tylko do zapisu.

W C # możesz to obejść, używając dynamicznego słowa kluczowego nad tablicą/kolekcją/rodzajami z kaczym pisaniem , intellisense jest tracone w ten sposób, ale działa.

Tablice kowariantne w Javie i C#

Wczesne wersje Javy i C# nie zawierały typów ogólnych, zwanych także polimorfizmem parametrycznym . W takim ustawieniu uczynienie tablic niezmiennymi wyklucza użyteczne programy polimorficzne.

Rozważmy na przykład napisanie funkcji do przetasowania tablicy lub funkcji, która testuje dwie tablice pod kątem równości przy użyciu metody Object . równa się metoda na elementach. Implementacja nie zależy od dokładnego typu elementu przechowywanego w tablicy, więc powinno być możliwe napisanie jednej funkcji, która działa na wszystkich typach tablic. Łatwo jest zaimplementować funkcje typu:

    
   boolowskie  równe tablice  (  obiekt  []  a1  ,  obiekt  []  a2  );  void  shuffleArray  (  Obiekt  []  a  ); 

Jeśli jednak typy tablicowe byłyby traktowane jako niezmienne, możliwe byłoby wywołanie tych funkcji tylko na tablicy dokładnie typu Object [] . Nie można na przykład przetasować tablicy łańcuchów.

Dlatego zarówno Java, jak i C# traktują typy tablic kowariantnie. Na przykład w Javie String [] jest podtypem Object [] , aw C# string [] jest podtypem object [] .

Jak omówiono powyżej, tablice kowariantne prowadzą do problemów z zapisem do tablicy. Java i C# radzą sobie z tym, oznaczając każdy obiekt tablicy typem podczas jego tworzenia. Za każdym razem, gdy wartość jest zapisywana w tablicy, środowisko wykonawcze sprawdza, czy typ wartości w czasie wykonywania jest równy typowi w czasie wykonywania tablicy. W przypadku niezgodności generowany jest wyjątek ArrayStoreException (Java) lub ArrayTypeMismatchException (C#):

    


   




0   // a jest jednoelementową tablicą typu String  String  []  a  =  new  String  [  1  ]  ;  // b jest tablicą obiektów Obiekt  [  ]  b  =  a  ;  // Przypisz liczbę całkowitą do b. Byłoby to możliwe, gdyby b naprawdę było   // tablicą typu Object, ale ponieważ tak naprawdę jest tablicą typu String,  // otrzymamy wyjątek java.lang.ArrayStoreException.  b  [  ]  =  1  ; 

W powyższym przykładzie można bezpiecznie czytać z tablicy (b). Dopiero próba zapisu do tablicy może prowadzić do kłopotów.

Wadą tego podejścia jest to, że pozostawia możliwość wystąpienia błędu w czasie wykonywania, który system o bardziej rygorystycznych typach mógłby wykryć w czasie kompilacji. Ponadto obniża to wydajność, ponieważ każdy zapis do tablicy wymaga dodatkowej kontroli w czasie wykonywania.

Dzięki dodaniu typów generycznych Java i C# oferują teraz sposoby pisania tego rodzaju funkcji polimorficznych bez polegania na kowariancji. Funkcji porównywania i tasowania tablic można nadać typy sparametryzowane

     
    <  T  >  boolowskie  równe tablice  (  T  []  a1  ,  T  []  a2  );  <  T  >  void  shuffleArray  (  T  []  a  ); 

Alternatywnie, aby wymusić, że metoda C# uzyskuje dostęp do kolekcji w sposób tylko do odczytu, można użyć interfejsu IEnumerable < object > zamiast przekazywania jej obiektu tablicy [] .

Typy funkcji

Języki z funkcjami pierwszej klasy mają typy funkcji, takie jak „funkcja oczekująca kota i zwracająca zwierzę” (napisane Cat -> Animal w składni OCaml lub Func < Cat , Animal > w składni C# ).

Języki te muszą również określać, kiedy jeden typ funkcji jest podtypem innego — to znaczy, kiedy można bezpiecznie używać funkcji jednego typu w kontekście, który oczekuje funkcji innego typu. Bezpieczniej jest zastąpić funkcję g funkcją f , jeśli funkcja f akceptuje bardziej ogólny typ argumentu i zwraca typ bardziej szczegółowy niż g . Na przykład funkcje typu Animal -> Cat , Cat -> Cat i Animal -> Animal mogą być używane wszędzie tam, gdzie oczekiwano Cat -> Animal . (Można to porównać do zasady solidności komunikacji: „bądź liberalny w tym, co akceptujesz, i konserwatywny w tym, co tworzysz”). Ogólna zasada jest następująca:

${\ Displaystyle (P_ {1} \ strzałka w prawo R_ {1}) \ równoważnik (P_ {2} \ strzałka w prawo R_ {2})}$ jeśli ${\ Displaystyle P_ {1} \ geq P_ {2}}$ i ${\ Displaystyle R_ {1} \ równoważnik R_ {2}}$ .

Korzystając z notacji reguł wnioskowania, tę samą regułę można zapisać jako:

${\ Displaystyle {\ Frac {P_ {1} \ geq P_ {2} \ quad R_ {1} \ równoważnik R_{2}}{(P_{1}\strzałka w prawo R_{1})\równoważnik (P_{2}\strzałka w prawo R_{2})}}}$

Innymi słowy, konstruktor typu → jest kontrawariantny w typie parametru (wejściowym) i kowariantny w typie zwracanym (wyjściowym) . Zasada ta została po raz pierwszy formalnie sformułowana przez Johna C. Reynoldsa , a następnie spopularyzowana w artykule Luca Cardelli .

Gdy mamy do czynienia z funkcjami, które przyjmują funkcje jako argumenty , regułę tę można zastosować kilka razy. Na przykład, stosując regułę dwukrotnie, widzimy, że ${\ Displaystyle ((P_ {1} \ do R) \ do R) \ równoważnik ((P_ {2} \ do R) \ do R)}$ jeśli ${\ Displaystyle P_ {1} \ równoważnik P_ {2}}$ . $_$ typ _ _ _ $_$ _ W przypadku skomplikowanych typów myślenie w myślach, dlaczego dana specjalizacja typu jest lub nie jest bezpieczna dla typów, może być mylące, ale łatwo jest obliczyć, które pozycje są ko- i kontrawariantne: pozycja jest kowariantna, jeśli znajduje się po lewej stronie parzysta liczba strzałek odnoszących się do niego.

Dziedziczenie w językach obiektowych

Gdy podklasa nadpisuje metodę w nadklasie, kompilator musi sprawdzić, czy nadrzędna metoda ma odpowiedni typ. Podczas gdy niektóre języki wymagają, aby typ dokładnie pasował do typu w nadklasie (niezmienność), bezpieczne jest również, aby metoda zastępująca miała „lepszy” typ. Zgodnie ze zwykłą regułą podtypów dla typów funkcji oznacza to, że metoda nadrzędna powinna zwrócić bardziej szczegółowy typ (zwracana kowariancja typu) i akceptować bardziej ogólny argument (kontrawariancja typu parametru). W UML możliwości są następujące (gdzie klasa B jest podklasą, która rozszerza klasę A, która jest nadklasą):

• Wariancja i zastępowanie metod: przegląd
• 

  Podtypowanie typu parametru/zwrotu metody.

• 

  niezmienność . Sygnatura nadrzędnej metody pozostaje niezmieniona.

• 

  Kowariantny zwracany typ . Relacja podtypowania jest w tym samym kierunku, co relacja między klasą A i klasą B.

• 

  Kontrawariantny typ parametru . Relacja podtypowania jest w kierunku przeciwnym do relacji między klasą A i klasą B.

• 

  Kowariantny typ parametru . Typ nie jest bezpieczny.

Dla konkretnego przykładu załóżmy, że piszemy klasę, która ma modelować schronisko dla zwierząt . Zakładamy, że Cat jest podklasą Animal i że mamy klasę bazową (przy użyciu składni Java)

  

      
        
    
    
       
        
    
 class  AnimalShelter  {  Animal  getAnimalForAdoption  ()  {  // ...  }  void  putAnimal  (  Animal  animal  )  {  //...  }  } 

Teraz pytanie brzmi: jeśli podklasujemy AnimalShelter , jakie typy możemy nadać getAnimalForAdoption i putAnimal ?

Typ zwracany przez metodę kowariantną

W języku, który dopuszcza kowariantne zwracane typy , klasa pochodna może zastąpić metodę getAnimalForAdoption , aby zwrócić bardziej konkretny typ:

    

      
          
    
 class  CatShelter  extends  AnimalShelter  {  Cat  getAnimalForAdoption  ()  {  return  new  Cat  ();  }  } 

Wśród głównych języków OO Java , C++ i C# (od wersji 9.0 ) obsługują kowariantne typy zwracane. Dodanie kowariantnego typu zwracanego było jedną z pierwszych modyfikacji języka C++, zatwierdzoną przez komitet normalizacyjny w 1998 roku. Scala i D obsługują również kowariantne typy zwracane.

Typ parametru metody kontrawariantnej

Podobnie, bezpieczne jest zezwolenie nadrzędnej metodzie na przyjęcie bardziej ogólnego argumentu niż metoda w klasie bazowej:

    
       
        
    
 class  CatShelter  rozszerza  AnimalShelter  {  void  putAnimal  (  obiekt  zwierzę  )  {  // ...  }  } 

Tylko kilka języków zorientowanych obiektowo na to pozwala (na przykład Python po sprawdzeniu typu za pomocą mypy). C++, Java i większość innych języków obsługujących przeciążanie i/lub przesłanianie zinterpretuje to jako metodę z przeciążoną lub przesłoniętą nazwą.

Jednak Sather poparł zarówno kowariancję, jak i kontrawariancję. Konwencja wywoływania metod przesłoniętych jest kowariantna z out i wartościami zwracanymi oraz kontrawariantna z parametrami normalnymi (z trybem in ).

Typ parametru metody kowariantnej

Kilka głównych języków, Eiffel i Dart , pozwala parametrom nadrzędnej metody mieć bardziej określony typ niż metoda w nadklasie (kowariancja typu parametru). Tak więc następujący kod Darta wpisałby check, z putAnimal nadpisując metodę w klasie bazowej:

    

        
        
    
 class  CatShelter  extends  AnimalShelter  {  void  putAnimal  (  kowariantne  Cat  animal  )  {  // ...  }  } 

To nie jest bezpieczne dla typów. Przerzucając CatShelter na AnimalShelter , można spróbować umieścić psa w schronisku dla kotów. To nie spełnia CatShelter i spowoduje błąd w czasie wykonywania. Brak bezpieczeństwa typu (znany jako „problem wywołania” w społeczności Eiffla, gdzie „kot” lub „KOT” to zmieniona dostępność lub typ) był problemem od dawna. Na przestrzeni lat proponowano różne kombinacje globalnej analizy statycznej, lokalnej analizy statycznej i nowych funkcji językowych, aby temu zaradzić, i zostały one zaimplementowane w niektórych kompilatorach Eiffla.

Pomimo problemu z bezpieczeństwem typu, projektanci Eiffla uważają kowariantne typy parametrów za kluczowe dla modelowania rzeczywistych wymagań. Schronisko dla kotów ilustruje powszechne zjawisko: jest rodzajem schroniska dla zwierząt, ale ma dodatkowe ograniczenia i rozsądne wydaje się modelowanie tego za pomocą dziedziczenia i ograniczonych typów parametrów. Proponując takie wykorzystanie dziedziczenia, projektanci Eiffla odrzucają zasadę substytucji Liskova , zgodnie z którą obiekty podklas powinny być zawsze mniej ograniczone niż obiekty ich nadklas.

Innym przykładem głównego języka dopuszczającego kowariancję parametrów metod jest PHP w odniesieniu do konstruktorów klas. W poniższym przykładzie metoda __construct() jest akceptowana, mimo że parametr metody jest kowariantny z parametrem metody elementu nadrzędnego. Gdyby ta metoda była inna niż __construct(), wystąpiłby błąd:

  


    


    


 

        



   

       
    
        
    
 interfejs  AnimalInterface  {}  interfejs  DogInterface  extends  AnimalInterface  {}  class  Dog  implementuje  DogInterface  {}  class  Pet  {  public  function  __construct  (  AnimalInterface  $animal  )  {}  }  class  PetDog  extends  Pet  {  public  function  __construct  (  DogInterface  $ dog  )  {  rodzic  ::  __construct  (  $ pies  );  }  } 

Innym przykładem, w którym parametry kowariantne wydają się pomocne, są tak zwane metody binarne, tj. metody, w których oczekuje się, że parametr będzie tego samego typu, co obiekt, na którym metoda jest wywoływana. Przykładem jest CompareTo : a . CompareTo ( b ) sprawdza, czy a występuje przed, czy po b w jakiejś kolejności, ale sposób porównania, powiedzmy, dwóch liczb wymiernych będzie inny niż sposób porównywania dwóch ciągów znaków. Inne typowe przykłady metod binarnych obejmują testy równości, operacje arytmetyczne i operacje na zbiorach, takie jak podzbiór i suma.

W starszych wersjach Javy metoda porównania została określona jako interfejs Comparable :

  

      
 interfejs  Comparable  {  int  CompareTo  (  Obiekt  o  );  } 

Wadą tego jest to, że metoda jest określona tak, aby pobierała argument typu Object . Typowa implementacja najpierw odrzuciłaby ten argument (zgłaszając błąd, jeśli nie jest oczekiwanego typu):

    
     
     
    
 
        
           
           
                                 
    
 class  RationalNumber  implementuje  Comparable  {  int  licznik  ;  int  mianownik  ;  // ...  public  int  CompareTo  (  Obiekt  inny  )  {  LiczbaWymierna  innaNum  =  (  LiczbaWymierna  )  inna  ;  zwróć  liczbę całkowitą  .  porównaj  (  licznik  *  innyLiczba  .  mianownik  ,  innaLiczba  .  licznik  *  mianownik  );  }  } 

W języku z kowariantnymi parametrami argument porównaniaTo może otrzymać bezpośrednio żądany typ RationalNumber , ukrywając typowanie. (Oczywiście nadal powodowałoby to błąd w czasie wykonywania, gdyby CompareTo zostało następnie wywołane na np. String .)

Unikanie potrzeby kowariantnych typów parametrów

Inne cechy języka mogą zapewnić widoczne korzyści z parametrów kowariantnych przy jednoczesnym zachowaniu substytucyjności Liskowa.

W języku z generykami (inaczej polimorfizmem parametrycznym ) i ograniczoną kwantyfikacją , poprzednie przykłady można zapisać w sposób bezpieczny dla typów. Zamiast definiować AnimalShelter , definiujemy sparametryzowaną klasę Shelter < T > . (Jedną z wad jest to, że osoba wdrażająca klasę podstawową musi przewidzieć, które typy będą wymagały specjalizacji w podklasach).

    

      
        
    

       
        
    


    
    

      
        
    

       
        
    
 class  Shelter  <  T  extends  Animal  >  {  T  getAnimalForAdoption  ()  {  // ...  }  void  putAnimal  (  T  animal  )  {  // ...  }  }  class  CatShelter  extends  Shelter  <  Cat  >  {  Cat  getAnimalFor Adoption  ()  {  // .. .  }  void  putAnimal  (  zwierzę  kot  )  {  // ...  }  } 

Podobnie w ostatnich wersjach Javy sparametryzowano interfejs Comparable , który pozwala na pominięcie rzutowania w dół w sposób bezpieczny dla typów:

    

     
     
    
         
        
            
                                 
    
 klasa  LiczbaWymierna  implementuje  Porównywalne  <LiczbaWymierna>  {  int  licznik  ;  _  _  int  mianownik  ;  // ...  public  int  CompareTo  (  RationalNumber  otherNum  )  {  return  Integer  .  porównaj  (  licznik  *  innyLiczba  .  mianownik  ,  innaLiczba  .  licznik  *  mianownik  );  }  } 

Inną funkcją języka, która może pomóc, jest wysyłanie wielokrotne . Jednym z powodów, dla których pisanie metod binarnych jest niewygodne, jest to, że w wywołaniu takim jak . CompareTo ( b ) , wybór poprawnej implementacji CompareTo naprawdę zależy od typu środowiska wykonawczego zarówno a , jak i b , ale w konwencjonalnym języku OO uwzględniany jest tylko typ środowiska wykonawczego a . W języku z wielokrotnym wysyłaniem w stylu Common Lisp Object System (CLOS) metodę porównania można zapisać jako funkcję ogólną, w której oba argumenty są używane do wyboru metody.

Giuseppe Castagna zauważył, że w języku pisanym z wieloma wysyłkami funkcja ogólna może mieć pewne parametry, które kontrolują wysyłkę, oraz niektóre „pozostałe” parametry, które tego nie robią. Ponieważ reguła wyboru metody wybiera najbardziej specyficzną odpowiednią metodę, jeśli metoda zastępuje inną metodę, wówczas metoda nadrzędna będzie miała bardziej szczegółowe typy dla parametrów sterujących. Z drugiej strony, aby zapewnić bezpieczeństwo typu, język nadal musi wymagać, aby pozostałe parametry były co najmniej tak samo ogólne. Używając poprzedniej terminologii, typy używane do wyboru metody w czasie wykonywania są kowariantne, podczas gdy typy nieużywane do wyboru metody w czasie wykonywania są kontrawariantne. Konwencjonalne języki pojedynczej wysyłki, takie jak Java, również przestrzegają tej zasady: tylko jeden argument jest używany do wyboru metody (obiekt odbiornika, przekazywany do metody jako ukryty argument this ), a typ this jest bardziej wyspecjalizowany w metodach zastępujących niż w superklasie.

Castagna sugeruje, że przykłady, w których kowariantne typy parametrów są lepsze (szczególnie metody binarne), powinny być obsługiwane przy użyciu wielu wysyłek; co jest naturalnie kowariantne. Jednak większość języków programowania nie obsługuje wielu wysyłek.

Podsumowanie wariancji i dziedziczenia

Poniższa tabela podsumowuje zasady zastępowania metod w językach omówionych powyżej.

	Typ parametru	Typ zwrotu
C++ (od 1998), Java (od J2SE 5.0 ), D	Niezmienny	Kowariantny
C#	Niezmienny	Kowariant (od C# 9 — przed niezmiennym)
Scala , Sather	Kontrawariantne	Kowariantny
Eiffla	Kowariantny	Kowariantny

Typy ogólne

W językach programowania, które obsługują generyczne (inaczej polimorfizm parametryczny ), programista może rozszerzyć system typów o nowe konstruktory. Na przykład interfejs C#, taki jak IList < T > umożliwia konstruowanie nowych typów, takich jak IList < Animal > lub IList < Cat > . Powstaje zatem pytanie, jaka powinna być wariancja tych konstruktorów typów.

Istnieją dwa główne podejścia. W językach z adnotacjami wariancji miejsca deklaracji (np. C# ) programista dodaje adnotację do definicji typu ogólnego z zamierzoną wariancją jego parametrów typu. W przypadku adnotacji wariancji miejsca użytkowania (np. Java ) programista zamiast tego dodaje adnotacje do miejsc, w których tworzony jest typ ogólny.

Adnotacje dotyczące wariancji w miejscu deklaracji

Najpopularniejszymi językami z adnotacjami wariancji strony deklaracji są C# i Kotlin (przy użyciu słów kluczowych out i in ) oraz Scala i OCaml (przy użyciu słów kluczowych + i - ). C# zezwala tylko na adnotacje wariancji dla typów interfejsów, podczas gdy Kotlin, Scala i OCaml zezwalają na nie zarówno dla typów interfejsów, jak i konkretnych typów danych.

Interfejsy

W języku C# każdy parametr typu interfejsu ogólnego można oznaczyć jako kowariantny ( out ), kontrawariantny ( in ) lub niezmienny (bez adnotacji). Na przykład możemy zdefiniować interfejs IEnumerator < T > iteratorów tylko do odczytu i zadeklarować, że jest on kowariantny (out) w parametrze typu.

  

        
     
 interfejs  IEnumerator  <  out  T  >  {  T  Current  {  get  ;  }  bool  PrzenieśNastępny  ();  } 

Przy tej deklaracji IEnumerator będzie traktowany jako kowariantny w swoim parametrze typu, np. IEnumerator < Cat > jest podtypem IEnumerator < Animal > .

Kontroler typów wymusza, aby każda deklaracja metody w interfejsie wymieniała tylko parametry typu w sposób zgodny z adnotacjami wejścia / wyjścia . Oznacza to, że parametr, który został zadeklarowany jako kowariantny, nie może występować w żadnych pozycjach kontrawariantnych (gdzie pozycja jest kontrawariantna, jeśli występuje pod nieparzystą liczbą konstruktorów typu kontrawariantnego). Dokładna zasada jest taka, że ​​zwracane typy wszystkich metod w interfejsie muszą być ważne kowariantnie , a wszystkie typy parametrów metody muszą być ważne kontrawariantnie , gdzie ważne S-ly jest zdefiniowane w następujący sposób:

• Typy nieogólne (klasy, struktury, wyliczenia itp.) są ważne zarówno ko-, jak i kontrawariantnie.
• Parametr typu T jest ważny kowariantnie, jeśli nie został oznaczony w , i ważny kontrawariantnie, jeśli nie został oznaczony .
• Typ tablicy A [] jest poprawny S-ly, jeśli A jest. (Dzieje się tak, ponieważ C# ma tablice kowariantne).
• Typ ogólny G < A1 , A2 , ..., An > jest ważny S-ly, jeśli dla każdego parametru Ai ,
  • Ai jest poprawnym S-ly, a i- ty parametr G jest deklarowany jako kowariantny, lub
  • Ai jest ważne (nie S)-ly, a i- ty parametr G jest deklarowany jako kontrawariantny, lub
  • Ai jest poprawne zarówno kowariantnie, jak i kontrawariantnie, a i- ty parametr G jest deklarowany jako niezmienny.

Jako przykład zastosowania tych reguł rozważmy interfejs IList < T > .

 

        
     
 interfejs  IList  <  T  >  {  void  Wstaw  (  indeks  int  ,  pozycja  T  );  IEnumerator  <  T  >  GetEnumerator  ();  } 

Typ parametru T elementu Insert musi być ważny kontrawariantnie, tj. parametr typu T nie może być oznakowany . Podobnie typ wyniku IEnumerator < T > GetEnumerator musi być poprawny kowariantnie, tj. (ponieważ IEnumerator jest interfejsem kowariantnym) typ T musi być poprawny kowariantnie, tj. parametr typu T nie może być oznaczony w . To pokazuje, że interfejs IList nie może być oznaczony jako ko- lub kontrawariantny.

W powszechnym przypadku ogólnej struktury danych, takiej jak IList , ograniczenia te oznaczają, że parametr out może być używany tylko w przypadku metod pobierających dane ze struktury, a parametr in może być używany tylko w przypadku metod umieszczania danych w strukturze, stąd wybór słów kluczowych.

Dane

C# zezwala na adnotacje wariancji dotyczące parametrów interfejsów, ale nie parametry klas. Ponieważ pola w klasach języka C# są zawsze modyfikowalne, klasy z parametrami wariantowymi w języku C# nie byłyby zbyt przydatne. Ale języki, które kładą nacisk na niezmienne dane, mogą dobrze wykorzystać kowariantne typy danych. Na przykład we wszystkich Scala , Kotlin i OCaml niezmienny typ listy jest kowariantny: List [ Cat ] jest podtypem List [ Animal ] .

Zasady Scali dotyczące sprawdzania adnotacji wariancji są zasadniczo takie same jak w C#. Istnieją jednak idiomy, które odnoszą się w szczególności do niezmiennych struktur danych. Ilustruje je następująca (wyciąg z) definicja List [ A ] .

      
      
      

    
           
          
    
 seal  abstract  class  List  [  +  A  ]  extends  AbstractSeq  [  A  ]  {  def  head  :  A  def  tail  :  List  [  A  ]  /** Dodaje element na początku tej listy. */   def  ::  [  B  >:  A  ]  (  x  :  B  ):  Lista  [  B  ]  =  nowa  skala  .  kolekcja  .  niezmienny  .  ::  (  x  ,  to  )  /** ... */  } 

Po pierwsze, członkowie klasy, którzy mają typ wariantu, muszą być niezmienni. Tutaj head ma typ A , który został zadeklarowany jako kowariantny ( + ), i rzeczywiście head został zadeklarowany jako metoda ( def ). Próba zadeklarowania go jako pola zmiennego ( var ) zostałaby odrzucona jako błąd typu.

Po drugie, nawet jeśli struktura danych jest niezmienna, często będzie miała metody, w których typ parametru występuje kontrawariantnie. Weźmy na przykład metodę :: , która dodaje element na początek listy. (Implementacja działa poprzez utworzenie nowego obiektu o podobnej nazwie class :: , klasy niepustych list.) Najbardziej oczywistym typem, który można by nadać, byłoby

     def  ::  (  x  :  A  ):  Lista  [  A  ] 

Byłby to jednak błąd typu, ponieważ kowariantny parametr A pojawia się w pozycji kontrawariantnej (jako parametr funkcji). Ale jest sztuczka, aby obejść ten problem. Dajemy :: bardziej ogólny typ, który pozwala na dodanie elementu dowolnego typu B , o ile B jest nadtypem A . Zauważ, że polega to na kowariantności List , ponieważ ma ona typ List [ A ] i traktujemy ją jako mającą typ List [ B ] . Na pierwszy rzut oka może nie być oczywiste, że uogólniony typ jest poprawny, ale jeśli programista zacznie od deklaracji typu prostszego, błędy typu wskażą miejsce, które należy uogólnić.

Wnioskowanie wariancji

Możliwe jest zaprojektowanie systemu typów, w którym kompilator automatycznie wnioskuje najlepsze możliwe adnotacje wariancji dla wszystkich parametrów typu danych. Jednak analiza może być złożona z kilku powodów. Po pierwsze, analiza jest nielokalna, ponieważ wariancja interfejsu I zależy od wariancji wszystkich interfejsów, o których wspominam . Po drugie, aby uzyskać unikalne najlepsze rozwiązania, system typów musi dopuszczać biwariantne (które są jednocześnie ko- i kontrawariantne). I wreszcie, wariancja parametrów typu powinna prawdopodobnie być celowym wyborem projektanta interfejsu, a nie czymś, co się po prostu dzieje.

Z tych powodów większość języków wnioskuje o bardzo małej wariancji. C# i Scala w ogóle nie wnioskują o adnotacjach wariancji. OCaml może wywnioskować wariancję sparametryzowanych konkretnych typów danych, ale programista musi jawnie określić wariancję typów abstrakcyjnych (interfejsów).

Weźmy na przykład typ danych OCaml T , który opakowuje funkcję

          wpisz  (  '  a  ,  '  b  )  t  =  T  z  (  '  a  ->  '  b  ) 

Kompilator automatycznie wywnioskuje, że T jest kontrawariantne w pierwszym parametrze i kowariantne w drugim. Programista może również podać wyraźne adnotacje, które kompilator sprawdzi, czy są spełnione. Zatem następująca deklaracja jest równoważna poprzedniej:

          typ  (-  '  a  ,  +  '  b  )  t  =  T  z  (  '  a  ->  '  b  ) 

Jawne adnotacje w OCaml stają się przydatne podczas określania interfejsów. Na przykład standardowy interfejs biblioteki Map . S dla tablic asocjacyjnych zawiera adnotację mówiącą, że konstruktor typu mapy jest kowariantny w typie wyniku.

   
    
         
          
           
               
        
     typ  modułu  S  =  typ  sig  typ  klucza  (+  '  a  )  t  val  pusty  :  '  a  t  val  mem  :  klucz  ->  '  a  t  ->  bool  ...  koniec 

Zapewnia to, że np. cat IntMap . t jest podtypem zwierzęcia IntMap . t .

Adnotacje dotyczące odchyleń w miejscu użytkowania (znaki wieloznaczne)

Wadą podejścia opartego na deklaracjach jest to, że wiele typów interfejsów musi być niezmiennych. Na przykład widzieliśmy powyżej, że IList musi być niezmienna, ponieważ zawiera zarówno Insert , jak i GetEnumerator . Aby ujawnić więcej wariancji, projektant API może zapewnić dodatkowe interfejsy, które udostępniają podzbiory dostępnych metod ( np . Jednak szybko staje się to nieporęczne.

Wariancja miejsca użytkowania oznacza, że ​​pożądana wariancja jest wskazana adnotacją w określonym miejscu w kodzie, w którym typ będzie używany. Daje to użytkownikom klasy więcej możliwości tworzenia podtypów bez wymagania od projektanta klasy definiowania wielu interfejsów o różnej wariancji. Zamiast tego, w momencie tworzenia instancji typu ogólnego do rzeczywistego typu sparametryzowanego, programista może wskazać, że zostanie użyty tylko podzbiór jego metod. W efekcie każda definicja klasy generycznej udostępnia również interfejsy dla kowariantnych i kontrawariantnych części tej klasy.

Java zapewnia adnotacje wariancji miejsca użytkowania za pomocą symboli wieloznacznych , ograniczonej formy ograniczonych typów egzystencjalnych . Sparametryzowany typ można utworzyć za pomocą symbolu wieloznacznego ? wraz z górną lub dolną granicą, np. List <? rozszerza Zwierzę > lub Listę <? super zwierzę > . Nieograniczony symbol wieloznaczny, taki jak List <?>, jest równoważny z List <? rozszerza Obiekt > . Taki typ reprezentuje List < X > dla jakiegoś nieznanego typu X , który spełnia warunek. Na przykład, jeśli l ma typ List <? extends Animal > , wtedy moduł sprawdzania typów zaakceptuje

    Zwierzę  a  =  l  .  dostać  (  3  ); 

ponieważ wiadomo, że typ X jest podtypem Animal , ale

  ja  .  dodaj  (  nowe  Zwierzę  ()); 

zostanie odrzucony jako błąd typu, ponieważ Animal niekoniecznie jest X . Ogólnie rzecz biorąc, biorąc pod uwagę interfejs I < T > , odniesienie do I <? extends T > zabrania używania metod z interfejsu, gdzie T występuje kontrawariantnie w typie metody. I odwrotnie, jeśli l miałby typ List <? super Animal > można nazwać l . dodać , ale nie l . dostać .

Podtypy wieloznaczne w Javie można wizualizować jako kostkę.

Podczas gdy sparametryzowane typy bez symboli wieloznacznych w Javie są niezmienne (np. nie ma relacji podtypów między List < Cat > a List < Animal > ), typy wieloznaczne można uszczegółowić, określając ściślejsze ograniczenie. Na przykład lista <? extends Kot > jest podtypem List <? rozszerza Zwierzę > . To pokazuje, że typy wieloznaczne są kowariantne w swoich górnych granicach (a także kontrawariantne w swoich dolnych granicach ). W sumie, biorąc pod uwagę typ wieloznaczny, taki jak C <? extends T > , istnieją trzy sposoby utworzenia podtypu: specjalizacja klasy C , określenie ściślejszego ograniczenia T lub zastąpienie symbolu wieloznacznego ? z określonym typem (patrz rysunek).

Stosując dwie z trzech powyższych form podtypowania, możliwe staje się na przykład przekazanie argumentu typu List < Cat > do metody oczekującej List <? rozszerza Zwierzę > . Jest to rodzaj ekspresji, który wynika z kowariantnych typów interfejsów. Lista <? extends Animal > typów działa jako typ interfejsu zawierający tylko kowariantne metody List < T > , ale implementator List < T > nie musiał go definiować z wyprzedzeniem.

W powszechnym przypadku ogólnej struktury danych IList parametry kowariantne są używane dla metod pobierających dane ze struktury, a parametry kontrawariantne dla metod umieszczających dane w strukturze. Mnemonik dla Producer Extends, Consumer Super (PECS) z książki Effective Java autorstwa Joshua Blocha daje łatwy sposób na zapamiętanie, kiedy używać kowariancji i kontrawariancji.

Symbole wieloznaczne są elastyczne, ale mają pewną wadę. Chociaż wariancja miejsca użytkowania oznacza, że ​​projektanci interfejsów API nie muszą brać pod uwagę wariancji parametrów typu interfejsów, często muszą zamiast tego używać bardziej skomplikowanych sygnatur metod. Typowym przykładem jest Comparable . Załóżmy, że chcemy napisać funkcję, która znajdzie największy element w kolekcji. Elementy muszą zaimplementować CompareTo , więc pierwsza próba może być

      <  T  extends  Comparable  <  T  >>  T  max  (  Collection  <  T  >  coll  ); 

Jednak ten typ nie jest wystarczająco ogólny — można znaleźć maksimum Collection < Calendar > , ale nie Collection < GregorianCalendar > . Problem polega na tym, że GregorianCalendar nie implementuje Comparable < GregorianCalendar > , ale zamiast tego (lepszy) interfejs Comparable < Calendar > . W Javie, w przeciwieństwie do C#, Comparable < Calendar > nie jest uważany za podtyp Comparable < GregorianCalendar > . Zamiast tego typ max musi zostać zmodyfikowany:

        <  T  rozszerza  Porównywalny  <?  super  T  >>  T  max  (  Kolekcja  <  T  >  kol  ); 

Ograniczona karta wieloznaczna ? super T przekazuje informację, że max wywołuje tylko metody kontrawariantne z interfejsu Comparable . Ten konkretny przykład jest frustrujący, ponieważ wszystkie metody w Comparable są kontrawariantne, więc ten warunek jest trywialnie prawdziwy. System witryny z deklaracjami mógłby obsłużyć ten przykład z mniejszym bałaganem, dodając adnotacje tylko do definicji Comparable .

Porównywanie adnotacji deklaracja-miejsce i miejsce użytkowania

Adnotacje wariancji w miejscu użytkowania zapewniają dodatkową elastyczność, umożliwiając sprawdzanie typów większej liczbie programów. Jednak były krytykowane za złożoność, jaką dodają do języka, prowadząc do skomplikowanych podpisów typów i komunikatów o błędach.

Jednym ze sposobów oceny przydatności dodatkowej elastyczności jest sprawdzenie, czy jest ona wykorzystywana w istniejących programach. Badanie dużego zestawu bibliotek Java wykazało, że 39% adnotacji wieloznacznych można było bezpośrednio zastąpić adnotacjami deklaracji witryn. Tak więc pozostałe 61% to wskazanie miejsc, w których Java korzysta z dostępności systemu miejsca użytkowania.

W języku strony deklaracji biblioteki muszą albo ujawniać mniej wariancji, albo definiować więcej interfejsów. Na przykład biblioteka Scala Collections definiuje trzy oddzielne interfejsy dla klas wykorzystujących kowariancję: kowariantny interfejs bazowy zawierający wspólne metody, niezmienną wersję zmienną, która dodaje metody powodujące skutki uboczne, oraz kowariantną niezmienną wersję, która może specjalizować odziedziczone implementacje w celu wykorzystania strukturalnych dzielenie się. Ten projekt dobrze współpracuje z adnotacjami witryn deklaracji, ale duża liczba interfejsów niesie ze sobą koszty złożoności dla klientów biblioteki. Modyfikowanie interfejsu biblioteki może nie wchodzić w grę — w szczególności jednym z celów dodawania generycznych do Javy było zachowanie binarnej kompatybilności wstecznej.

Z drugiej strony symbole wieloznaczne Java są same w sobie złożone. W prezentacji konferencyjnej Joshua Bloch skrytykował je jako zbyt trudne do zrozumienia i użycia, stwierdzając, że dodając wsparcie dla domknięć „po prostu nie stać nas na kolejne symbole wieloznaczne ”. Wczesne wersje Scali wykorzystywały adnotacje wariancji miejsca użycia, ale programiści uznali je za trudne w użyciu w praktyce, podczas gdy adnotacje miejsca deklaracji okazały się bardzo pomocne przy projektowaniu klas. Późniejsze wersje Scali dodały typy egzystencjalne i symbole wieloznaczne w stylu Javy; jednak według Martina Odersky'ego , gdyby nie było potrzeby współdziałania z Javą, prawdopodobnie nie zostałyby one uwzględnione.

Ross Tate argumentuje, że część złożoności symboli wieloznacznych Java wynika z decyzji o kodowaniu wariancji miejsca użytkowania przy użyciu typów egzystencjalnych. Oryginalne propozycje wykorzystywały składnię specjalnego przeznaczenia do adnotacji wariancji, pisząc List <+ Animal > zamiast bardziej szczegółowego List <? rozszerza Zwierzę > .

Ponieważ symbole wieloznaczne są formą typów egzystencjalnych, można ich używać nie tylko do wariancji. Typ taki jak List <?> („lista nieznanego typu”) umożliwia przekazywanie obiektów do metod lub przechowywanie ich w polach bez dokładnego określania ich parametrów typu. Jest to szczególnie cenne w przypadku klas takich jak Class , gdzie większość metod nie wspomina o parametrze typu.

Jednak wnioskowanie o typach dla typów egzystencjalnych jest trudnym problemem. Dla implementatora kompilatora symbole wieloznaczne Java powodują problemy z zakończeniem sprawdzania typu, wnioskowaniem argumentów typu i niejednoznacznymi programami. Ogólnie rzecz biorąc, nie można rozstrzygnąć , czy program Java korzystający z typów generycznych jest dobrze napisany, czy nie, więc każdy moduł sprawdzania typów będzie musiał wejść w nieskończoną pętlę lub przekroczy limit czasu dla niektórych programów. Dla programisty prowadzi to do skomplikowanych komunikatów o błędach typu. Typ Java sprawdza typy symboli wieloznacznych, zastępując symbole wieloznaczne zmiennymi świeżego typu (tzw. konwersja przechwytywania ). Może to utrudnić odczytanie komunikatów o błędach, ponieważ odnoszą się one do zmiennych typu, których programista nie napisał bezpośrednio. Na przykład próba dodania kota do listy <? extends Animal > zwróci błąd podobny do

metoda List.add (przechwytywanie nr 1) nie ma zastosowania (rzeczywistego argumentu Cat nie można przekonwertować na przechwytywanie nr 1 przez konwersję wywołania metody), gdzie przechwytywanie nr 1 jest nową zmienną typu: przechwytywanie nr 1 rozszerza Zwierzę z przechwytywania ? przedłuża Zwierzę

Ponieważ zarówno adnotacje dotyczące miejsca deklaracji, jak i miejsca użytkowania mogą być przydatne, niektóre systemy typów zapewniają jedno i drugie.

Etymologia

Terminy te wywodzą się z pojęcia funktorów kowariantnych i kontrawariantnych w teorii kategorii . Rozważ kategorię $typy i której morfizmy$ relację podtypów ≤. (To jest przykład tego, jak każdy częściowo uporządkowany zestaw może być traktowany jako kategoria). Na przykład konstruktor typu funkcji bierze dwa typy p i r i tworzy nowy typ p → r ; więc przenosi obiekty w obiektach w do $^ {2}}$$displaystyle$ . Zgodnie z regułą podtypowania dla typów funkcji ta operacja odwraca ≤ dla pierwszego parametru i zachowuje go dla drugiego, więc jest to funktor kontrawariantny w pierwszym parametrze i funktor kowariantny w drugim.

Zobacz też

• Polimorfizm (informatyka)
• Dziedziczenie (informatyka)
• Zasada podstawienia Liskowa

Linki zewnętrzne

• Fabulous Adventures in Coding : Seria artykułów na temat implementacji dotyczy ko/kontrawariancji w języku C#
• Contra Vs Co Variance (zwróć uwagę, że ten artykuł nie jest aktualizowany o C++)
• Zamknięcia dla języka programowania Java 7 (v0.5)
• Teoria kowariancji i kontrawariancji w języku C# 4