29. května 2017

Covariance & Contravariance

Myslím, že je dost pravděpodobné, že na univerzitě jste měli nějaký ten semestr statistiky (já jsem měl 4 😱 ) a tak by vám měl být aspoň lehce povědomý termín kovariance, který je vyjádřený vztahem:
cov(X, Y) = E[(X - E[X])(Y - E[Y])]
Tak o tom si dnes povídat nebudeme.

Místo toho bych si chtěl rozebrat téma, které jsem dostal jako otázku na nedávném pohovoru. (Jo, to byl ten pohovor, kvůli kterému jsem napsal článek CAP Theorem, takže to už je druhý zářez na pažbě.)

Když jsem tedy dostal otázku, jestli vím, co je kovariance a kontravariance, tak u prvního termínu mi zablikala kontrolka "mlhavé vzpomínky" (léta nepoužívaná statistika se projeví "určitým povědomím neurčitosti") a pak jsem na férovku přiznal, že termín kontravariance jsem nikdy neslyšel a nevím, co to je.

Poslední varování! Pokud vás neodradila rovnice v úvodu ani vás neodežene tento odstavec, vězte, že se dozvíte o temném zákoutí computer science, které vám asi bude prakticky k ničemu - já jsem tuto "záležitost" za 12 let v Javě nepoužil ani jednou. Na druhou stranu, je to aspekt, který je ve vašem jazyce trvale přítomen a dost možná jsou vám jeho praktické konsekvence známé.

Podivný případ s Array

Než se do toho pořádně pustíme, zkuste se podívat na následující kód v Javě, který se bez problémů zkompiluje. Co je na tom špatně a co se stane, když ho spustíme?


Asi jste správně odhalili, že na 9. řádku micháme jablka s hruškama. Ehm, tedy Jedie se Sithama. Možná už ale nevíte, že zmíněný řádek vyhodí runtime výjimku ArrayStoreException.

Pokud bychom se podívali na ekvivalentní příklad ve Scale, tak se nám následující kód ani nezkompiluje, protože vyhodí kompilační chybu už na řádku 8.


To jsou věci! Vítejte ve světě variance.

3 sestry: Kovariance, Kontravariance a Invariance

Výše uvedené příklady demonstrují, že pole jsou v Javě kovariantní a ve Scale invariantní. Pojďme si na to posvítit. Všechno se to motá kolem pojmů subtyping (pozor, neplést s dědičností) a variance. Takže.

Variance je obecný pojem, který říká, jakým způsobem funguje subtyping u komplexních typů. Komplexním type je třeba generická kolekce, nebo funkce. Variance může být trojího druhu:
  • Invariance říká, že mezi komplexními typy není žádný vztah.
  • Kovariance umožňuje nahradit komplexní typ jeho podtypem.
  • Kontravariance umožňuje nahradit komplexní typ jeho nadtypem.

Pro úplnost je potřeba říct, že je tady ještě čtvrtá sestra: bivariance. Ale protože ji macecha ráda neměla, tak se s ní nebudeme zabývat.

Variance v kolekci

Pokud se vrátím k výše uvedenému příkladu v Javě - proč je pole kovariantní, když to pak působí problémy? Důvod je historický. Pole byla jedna z prvních kolekcí, které Java měla a jak ti starší z nás zažili, až do verze 5, neměla Java generika. (Mimochodem, jeden z lidí, kteří generiky do Javy přidávali, byl Martin Odersky, autor Scaly.)

Pole v Javě byly navrženy, aby podporovaly pole objektů a protože každá třída automaticky dědí z Object, tak jsou pole kovariantní. S příchodem generik to už nedává smysl a tak máme v Javě takovou dichotomii - pole jsou kovariantní (viz příklad nahoře), kdežto generické kolekce jsou invariantní.

Jak taková invariance v kolekci vypadá? Podívejme se na následující příklad seznamu v Javě:


Teď už by mělo být zřejmé, že ačkoliv typy v kolekci podporují subtyping (např. Jedi -> Powerful), tak kolekce samotné jsou invariantní: seznam List<Jedi> není podtypem List<Powerful>.

Immutable kolekce

Jak zrhuba říká Martin Odersky (tady hodně zjednodušuji), mutable kolekce by měly být invariantní, zatímco immutable kolekce můžou být kovariantní.

Kovariantní seznam si můžeme hezky ukázat ve Scale. Jelikož List je ve Scale immutable (ve skutečnosti je to klasická funkcionální struktura cons buněk). Právě immutabilita nám zajistí, že nás nepotká podobné runtime překvapení, jako u Java polí.


Tam, kde se nám Scala u polí bouřila (řádek 8), tak u seznamu ani necekne. Prostě kovariantní pohodička.

Jakou varianci má immutable Java?

Když se člověk dívá, jakou pěknou implementaci immutable kolekcí má Scala, tak ho napadne, jestli jsou také kovariantní immutable kolekce v Javě. Zklamu vás... nejsou.

V první řadě, immutable kolekce v Javě vůbec nejsou. To nejbližší, co se dá v Java kolekcích najít je Collections.unmodifiableList (ev. Map, Set, Collection atd.), což je ale jenom read-only pohled na interní, mutable list. Který je invariantní.

Pokud se podíváme na externí frameworky, immutable kolekce nabízí Google Guava. Když se na ně ale zaměříme z hlediska variance, tak jsou opět invariantní. Navíc, ošklivost builderu pro přidání elementu do kolekce se s funkcionální krásou cons nedá srovnávat:


To je všechno? Co funkce?

Povídání o varianci v kolekcích se nám trochu protáhlo, takže se nedostalo na to nejzajímavější - variance ve funkcích. Jako opravdu ve funkcích - Java se nám vrabčími krůčky přibližuje funkcionálnímu programování, takže bychom toto téma neměli minout.

Související články

  • Covariance & Contravariance II: Funkce (TBD)

6 komentářů:

  1. Další zajímavé téma. Je pravda, že variance a kontravariance jde v praxi ve většině případů použít jen k vysvětlení, proč něco nejde a nepůjde. To není mezi kolegy moc populární:-). Když už to někde použiju pozitivně, aby mi to něco pomohlo vymyslet, pak je to hlavně skrze banální mnemotechnickou pomůcku PECS (producer extends, consumer super). Tu si, na rozdíl od toho teoretického ptydepe, dokážu nějak představit.
    A ještě drobnost na okraj. Aby to nebylo málo zamotané termín "invariant" se vyskytuje v computer science ještě v jednom, zcela nesouvisejícím významu - invarianta algoritmu. Pravidelně tak jednou za rok si to musím osvěžit na wikipedii, abych nebyl za analfabeta v diskuzích, ale zvlášť v Javě to moc velký smysl nemá.

    ‎Prostě poměr praktické použitelnosti a teoretické složitosti z toho dělá ideální pohovorovou nebo státnicovou otázku :-). Zajímavější je to s inferencí, kde se z toho stane ukázkový SAT problém (a to i v Javě, jednou jsem na to sám dojel), ‎ale v praxi to místo řešení NP úplnosti v kompilátoru vyřešíš tak, že budeš prostě psát typy natvrdo.

    Mimochodem už trochu chápeš mé zoufalství z pohovorů?

    OdpovědětVymazat
    Odpovědi
    1. Tvé zoufalství zcela chápu :-) taky o tom chci časem něco napsat. Zatím nevím, jestli se to bude jmenovat Smutná zpráva o IT trhu, nebo jenom Rozpačitá zpráva...

      Jo, o tom PECS a Joshuovi Blochovi jsem taky přemýšlel, že bych to tam zakomponoval, ale člověk musí ořezávat, aby to mělo rozumnou délku a formu.

      Vymazat
  2. Možná to bude znít jako hnidopišství, ale kolekce v Javě nejsou invariantní. Ani nijak jinak variantní. Parametrizovaný typ v Javě totiž nemůže definovat "svou" varianci -- ta se definuje až v místě použití. (Anglické termity jsou declaration-site variance a use-site variance.)

    Takže deklarace rozhraní List, nějaké to List<T>, neříká o varianci zhola nic. Teprve když deklaruju proměnnou, tak volím její varianci: List<Jedi> je vskutku invariantní, ale můžu deklarovat i List<? extends Jedi>, který je kovariantní, nebo List<? super Jedi>, který je kontravariantní.

    Samozřejmě souhlasím s názorem, že to je úplně špatně, ale málo platné, tak už to v Javě je :-)

    OdpovědětVymazat
    Odpovědi
    1. Díky za upřesnění. Určitě to není hnidopišství - píšu i proto, abych dostal zpětnou korekci u věcí, kterým úplně nerozumím.

      Vymazat