funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
««« »»»

Bez typů se obejdeme, ale...

29. 4. 2015 — k47

Však to znáte, něco tweet­nete a jedna od­po­věď vás donutí napsat celý článek jako vy­svět­lení, co je tím vlastně myš­leno.

Dneska to byla tato perla ne­všední krásy (odsud):

Wi­thout sound­ness, types can merely be used as op­ti­mi­sation hints, but the ge­ne­ra­ted code would still need to be able to back out.

Na první pohled tato věta může vy­pa­dat jen jako další ne­vý­znamný pří­spě­vek do debaty mezi pří­z­nivci sta­ticky a dy­na­micky ty­po­va­ných jazyků (které jsou téměř vý­hradně vedeny di­le­tanty, mě ne­vy­jí­maje). Ve sku­teč­nosti jde o hlu­boký prin­cip. Když má jazyk ne­ko­rektní typový systém, typy před­sta­vují jen nástin toho, co se bude s nej­větší prav­dě­po­dob­ností dít, ale vir­tu­ální stroj musí být při­pra­ven na even­tu­a­litu, že věci ne­pů­jdou podle plánu.

Jako pří­klad uvedu le­gen­dární vadu ty­po­vého sys­tému javy, ve kterém jsou pole ko­va­ri­antní. Ko­va­ri­ance zna­mená, že jestliže B je po­to­mek A, tak B[] je po­to­mek A[].

class Animal {}
class Pony extends Animal {}

Pony[] ponies = { new Pony() };
Animal[] animals = ponies; // kovariance zafunguje zde

animals[0] = new Animal(); // tohle skončí výjimkou ArrayStoreException

O co jde. Na za­čátku jsem vy­tvo­řil pole poníků a pak ho při­řa­dil do pro­měnné typu pole zvířat a ko­va­ri­ance polí to po­vo­lila. Teď, když se do pole, na které uka­zuje pro­měnná typu Animal[], snažím při­řa­dit objekt typu Animal (což je na­prosto ko­rektní ope­race), vy­skočí na mě vý­jimka ArrayStoreException. Za běhu. A kom­pi­lá­tor neřekl ani popel, pro­tože ko­va­ri­ance polí není ko­rektní.

A co je na celé věci nej­horší: Za ta tuhle po­div­nost z dáv­no­věku, kdy java neměla ani ge­ne­rika 1, všichni do dneška pla­tíme. Pro­tože tohle může nastat, vir­tu­ální stroj musí při každém vlo­žení do pole pro­vá­dět ty­pe­check jestli typ ele­mentu je pod­ty­pem pří­pustné třídy. Kdyby typový sytém ne­ob­sa­ho­val tuto úchylku a pole by byla in­va­ri­antní, run­time by měl na­pros­tou jis­totu a ne­mu­sel byl po­každé dělat zby­tečný ty­pe­check3.

Vir­tu­ální stroj může v ně­kte­rých si­tu­a­cích nut­nost této kon­t­roly od­stra­nit. Na­pří­klad pokud jde o pole ob­jektů nějaké fi­nální třídy nebo ob­jektů třídy (nebo in­ter­face), která nemá po­tomky nebo je má, ale zatím nejsou na­ta­žené do JVM, někdy může být ty­pe­check vy­ta­žen před smyčku a tak dále.

Jazyk s ne­ko­rekt­ním ty­po­vým sys­té­mem může běžet rychle, jak je na­pří­klad vidět na všech mo­der­ních im­ple­men­ta­cích Ja­vaScriptu. Toho je však do­sa­ženo di­vo­kými a agre­siv­ními spe­ku­la­cemi, které vir­tu­ální stroj pro­vádí. Sází na to, že všechno poběží jako minule, že se typy sta­bi­li­zují a spe­ci­a­li­zuje kód pro to, co vy­po­zo­ro­val. Ale stále musí po­čí­tat s tím, že jeho před­po­klady byly špatné nebo že se si­tu­ace na­jed­nou změní. Ty­pický guard, který hlídá před­po­klady, je tvořen pár in­struk­cemi – kon­t­rola typu a jeden pod­mí­něný skok na místo, které si s pro­blé­mem poradí, de­op­ti­ma­li­zuje kód, přepne se do in­ter­pre­tru a začne znova.

Jestliže typový systém je ko­rektní dá mi na­pros­tou a ne­vy­vra­ti­tel­nou ga­ranci toho, že určité stavy za žád­ných okol­ností ne­mů­žou nastat a vir­tu­ální stroj a JIT s nimi nemusí vůbec ztrá­cet čas. To může vést k jed­no­duš­šímu VM, rych­lej­šímu kódu nebo rych­lejší kom­pi­laci, která je pro jazyky jako Ja­vaScript velice dů­le­žitá, pro­tože com­pile-time je run-time.

To však ne­zna­mená, že VM nebude spe­ku­lo­vat. Na­pří­klad takové JVM ve fázi pro­fi­lo­vání sle­duje všechny call­site a když zjistí, že se z jed­noho místa volají jen metody jedné třídy, místo zcela va­lid­ního vir­tu­ál­ního volání metody op­ti­mis­ticky in­li­nuje tělo metody (pokud je malá) a před ní vloží guard, který se po­stará o si­tu­aci, kdy se na daný call­site do­stane objekt jiné třídy.


Další věc, která in­ter­ne­tem zní jako ozvěna, je tvr­zení, že typy nejsou po­třeba k rych­lému pro­gramu, že je to jen a pouze do­ku­men­tace pro pro­gra­má­tora. S druhou po­lo­vi­nou sou­hla­sím, typy jsou for­ma­li­zací myš­le­nek a před­po­kladů toho, co kód má dělat a na jakých datech. Ale s první částí tvr­zení na­prosto ne­sou­hla­sím a do­lo­vím si tvrdit, že pravý opak je prav­dou: Typy jsou zcela ne­po­stra­da­telné pro rychlý běh pro­gramu. Háček je jenom v tom jaké typy. Pro­tože, když říkám, že typy jsou nutné, ne­mys­lím tím ty vi­di­telné v kódu, ani ty, které odvodí Hindley–Milner, ale ty se kte­rými bude run­time pra­co­vat.

Co dělá každý Ja­vaScrip­tový vir­tu­ální stroj? Snaží se za běhu ob­je­vit tak­zvané skryté třídy (hidden class), které mají nějaký tvar, počet atri­butů ně­ja­kého druhu – tedy typy. Když jsou tyto typy známé, JIT může ge­ne­ro­vat mnohem rych­lejší kód, pro­tože ne­pra­cuje s horou hash ta­bu­lek, ale s bloky paměti, které mají jasně danou struk­turu2.

Tohle před­po­kládá, že ně­ja­kou struk­turu je možné ob­je­vit. Na­štěstí to vět­ši­nou platí, pro­tože i když kód ne­ob­sa­huje typové ano­tace a kom­pi­lá­tor ne­vy­nu­cuje ko­rekt­nost, pro­gramy mají ur­či­tou im­pli­citní struk­turu – ob­jekty pře­dané jako ar­gu­menty nějaké funkci skoro vždycky vy­pa­dají velice po­dobně atd.

Pro rychlý běh tedy není tolik dů­le­žité jestli je jazyk sta­ticky nebo dy­na­micky ty­po­vaný, ale jestli má sta­tic­kou nebo dy­na­mic­kou struk­turu.


Pozn:

  1. Právě chy­bě­jící ge­ne­rika v prv­ních ver­zích javy mohou za toto kri­mi­nální cho­vání. Stej­nou vadou trpí i C#.
  2. Na­pří­klad: Když první verze vir­tu­ální stroje HHVM, vy­ko­ná­valy kód na­psaný v Hacku, což je ve své pod­statě PHP s ko­rekt­ním(!) ty­po­vým sys­té­mem, tak všechny sta­ticky známé typy za­ho­dily a začaly dy­na­micky typy ob­je­vo­vat a spe­ci­a­li­zo­vat kód.
  3. Další po­ně­kud více eso­te­rický pří­klad: Java kon­t­ro­luje, jestli se index ke kte­rému při­stu­puji, na­chází v poli a když je mimo, vyhodí ArrayIndexOutOfBoundsException. V de­pen­detly typed ja­zy­cích může být délka pole ob­sa­žena v typu pole a v ta­ko­vém pří­padě je možné se zbavit těchto kon­t­rol, pro­tože typový systém ga­ran­tuje, že ne­do­jde ke čtení mimo pole.

Dále k tématu:

@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články