Dědičnost dnes

[Kiwi]

Další z textů, jejichž autor podlehl dojmu, že OOP stojí a leží na dědění. I s "povinným" prvoplánovým příkladem grafických objektů, na němž je "všechno krásně jasné", aspoň do doby, než by se v tom zvídavý čtenář začal šťourat a začal si klást otázky, jestli je opravdu dobrý nápad odvozovat děděním křivku od úsečky, jestli je to opravdu šikovné doplňovat takto vzniklou hierarchii o vlastnost barvy dalším děděním od již specializovaných tříd a k čemu je to celé dobré, když stejně na vykreslení každého z těch útvarů je objekt plátno, který to všechno umí tak nějak bokem i bez objektů.

Jestli to nebude "krásně jasné", protože to je "správný" příklad. OOP opravdu krásně funguje na diskrétní simulace a grafické objekty (nebo ještě lépe na GUI).

V učebnicích vypadá každý takový příklad správný a jasný. Právě protože je to jen příklad, bez kontextu. V praxi to tak jasné není a má-li někdo potřebu psát další a další učebnice a tutoriály, tak ať si jeden takový "jasný", "správný" příklad vezme a rozebere ho trošku detailněji. Protože když to udělá, tak vyjde najevo, že málokdy existuje jediný, správný, optimální návrh, že obvyklá situace je více možností a v první řadě je třeba mít na mysli, co vlastně chci řešit za problém, k čemu to má sloužit, čeho chci docílit a podle toho zvolit vhodný přístup. Což je přesně to, co v takovýchto učebnicových příkladech naprosto chybí. Dokonce i u takovýchto "jasných" příkladů, jež by neměly představovat problémy. Nemluvě o modelování objektů "reálného", nebo naopak abstraktního světa dekomponovaného IS, s nimiž se vývojář setká zdaleka nejvíce a u nichž to je mnohem zapeklitější. Obvykle se v praxi totiž nebude zabývat navrhováním GUI knihovny nebo grafického editoru po milionté prvé.
Z toho textu jsem se nedozvěděl, proč zvolil autor zrovna tento model, a zajímalo by mne, jak jsi přišel na to, že je "správný". Autor to neudělal, máš příležitost udělat to za něj.

A pokud jde o ten odkazovaný článek, tak je to opravdu tak napůl esoterická záležitost, protože se snaží nás přesvědčit, že chceme-li posuzovat časovou složitost co nejobecněji, tak musíme předpokládat sice konečná, ale libovolně rozsáhlá data, na nichž ukazuje, že je obecně nelze obsloužit v konstantním čase z ryze fyzikálních důvodů (jen jsem čekal, kdy tam začne vytahovat holografický princip z teorie strun).
To je sice roztomilé, ale jen jako taková kratochvilná teoretická onanie. Protože v praxi při porovnávání algoritmů předpokládám nikoliv "sice konečné, avšak libovolně rozsáhlé" paměti, ale jeden a ten samý konkrétní stroj.

Ono se ukazuje, že navrhovat algoritmy, počítat jejich složitost a vzájemně porovnávat jejich efektivitu je paradoxně jednodušší, když předpokládáme sice konečná, ale libovolně velká data. Dělá se to tak desítky let a i když o tom možná nevíte, výsledky takových teoretických úvah denně používáte. A ten odkazovaný článek vlastně není nic překvapivého ani esoterického, je to spíš téměř triviální pozorování.

Autor článku tvrdí, že bychom měli přehodnotit svůj pohled na časovou náročnost přístupu k paměti s nahodilým přístupem a uvědomit si, že v tom nejobecnějším případě není O(1), ale O(√n). Máš příležitost mi tu teď vysvětlit, v čem se mi tak co zjednoduší v praxi.

Takže pokud by mi podobný rozumbrada začal opravovat mé odhady řka, že přístup k paměti má přece složitost O(√n), pousmál bych se, poplácal bych ho po tvářičce a popřáv mu mnoho radosti při onaniích nad řešením otázek, kolik andělů se vejde na povrch horizontu událostí černé díry, bych ho kopnul do...

Hodně vtipné. Zvlášť když si uvědomíte, že při taktovacích frekvencích v řádu GHz a omezení rychlostí světla se omezení rychlosti přístupu k paměti (nebo obecně latence libovolné komunikace) začnou projevovat na vzdálenostech několika centimetrů.

Úžasné. A teď mi na základě toho dej konkrétní příklad, na kterém bude vidět, že O(1) aproximace složitosti přístupu k RAM povede k nesprávným, rozuměj příliš optimistickým výsledkům.

[Reklama]

[gll]

Tak já nevím, já když do Googlu zadám "haskell dijkstra algorithm", tak to mám hned na prvních třech pozicích. Ale možná mám jinej Google.

Implementace, které jsem našel, používají knihovny, které uvnitř nejsou FP.

Já mam vážně asi nějakej jinej Google. U mě je druhý odkaz tohle: https://github.com/ddrake/haskell-dijkstra
Tam jsou nějaké "unitř ne-FP knihovny"?

To není moc dobrý příklad rychlé implementace.

Výběr minima tímto způsobem?

Kód: [Vybrat]

current = head . sortBy (\(_,(d1,_)) (_,(d2,_)) -> compare d1 d2) $ dunchecked

Pro výběr hran vedoucích z vrcholu se prochází všechny vrcholy grafu v každém kroku.

[Mirek Prýmek]

Pro výběr hran vedoucích z vrcholu se prochází všechny vrcholy grafu v každém kroku.

Nezapomněl jsi, že Haskell je lazy?! )

[Mirek Prýmek]

Ale když člověk zrovna čeká na doběhnutí make při ladění obskurní chyby v poměrně low-level kódu v C++, tak je čtení názorů místních odborníků na teorii vyčíslitelnosti, složitosti a programovacích jazyků docela dobrý relax

Jj, taky občas praktikuju

[gll]

Pro výběr hran vedoucích z vrcholu se prochází všechny vrcholy grafu v každém kroku.

Nezapomněl jsi, že Haskell je lazy?! )

V každém volání dijkstra', tedy pro každý vrchol, se volá

Kód: [Vybrat]

edges = edgesFor g c


Kód: [Vybrat]

edgesFor :: Graph -> Node -> [Edge]
edgesFor g n = snd . head . filter (\(nd, _) -> nd == n) $ g

díky tomu, že je to lazy, se procházení zastaví po nalezní vrcholu? To na asymptotické složitosti nic nezmění.

[Reklama]

[Mirek Prýmek]

díky tomu, že je to lazy, se procházení zastaví po nalezní vrcholu? To na asymptotické složitosti nic nezmění.

...a došlo na moje slova

No... neuraž se, ale já bych teda nechtěl vidět, jak bys tu složitost pro konkrétní implementaci počítal

Tak radši dobrou

[gll]

díky tomu, že je to lazy, se procházení zastaví po nalezní vrcholu? To na asymptotické složitosti nic nezmění.

...a došlo na moje slova

No... neuraž se, ale já bych teda nechtěl vidět, jak bys tu složitost pro konkrétní implementaci počítal

Tak radši dobrou

dolní odhad složitosti  O(V^2 log V)

o dost horší než jiné implementace.

[MartinBeran]

V učebnicích vypadá každý takový příklad správný a jasný. Právě protože je to jen příklad, bez kontextu. V praxi to tak jasné není a má-li někdo potřebu psát další a další učebnice a tutoriály, tak ať si jeden takový "jasný", "správný" příklad vezme a rozebere ho trošku detailněji. Protože když to udělá, tak vyjde najevo, že

Bývá celkem dobrým zvykem v úvodních výukových textech používat zjednodušení a nerozebírat detailně všechny související problémy. Jinak by to začátečníci nepochopili.

málokdy existuje jediný, správný, optimální návrh, že obvyklá situace je více možností a v první řadě je třeba mít na mysli, co vlastně chci řešit za problém, k čemu to má sloužit, čeho chci docílit a podle toho zvolit vhodný přístup. Což je přesně to, co v takovýchto učebnicových příkladech naprosto chybí. Dokonce i u takovýchto

Tak snad to je v učebnicových příkladech pro pokročilé...

Z toho textu jsem se nedozvěděl, proč zvolil autor zrovna tento model, a zajímalo by mne, jak jsi přišel na to, že je "správný". Autor to neudělal, máš příležitost udělat to za něj.

Já jsem nereagoval na tento konkrétní článek, ale na obecné tvrzení: "Další z textů, jejichž autor podlehl dojmu, že OOP stojí a leží na dědění." Přiznám se, že jsem tento článek nečetl, úvodem do OOP jsem si prošel už před nějakými 25 lety

Autor článku tvrdí, že bychom měli přehodnotit svůj pohled na časovou náročnost přístupu k paměti s nahodilým přístupem a uvědomit si, že v tom nejobecnějším případě není O(1), ale O(√n). Máš příležitost mi tu teď vysvětlit, v čem se mi tak co zjednoduší v praxi.

Ono praxi spíš komplikuje, ale zato je to bližší realitě. Je to jak s fyzikou - někde stačí Newtonova mechanika, jinde je potřeba obecná teorie relativity. Já ve své každodenní praxi také nepotřebuju počítat s nekonstantní cenou přístupu do paměti, ale to mě ještě neopravňuje k tvrzení, že je to blbost, kterou nepotřebuje nikdo.

Úžasné. A teď mi na základě toho dej konkrétní příklad, na kterém bude vidět, že O(1) aproximace složitosti přístupu k RAM povede k nesprávným, rozuměj příliš optimistickým výsledkům.

Příklad je v tom diskutovaném článku a nějaká měření už tu někdo v tomto vlákně uváděl. Obecně každá paměťová hierarchie s více úrovněmi cache bude dávat při O(1) aproximaci v závislosti na volbě konstanty a analyzovaném algoritmu buď příliš optimistické, nebo pesimistické výsledky.

[gll]

díky tomu, že je to lazy, se procházení zastaví po nalezní vrcholu? To na asymptotické složitosti nic nezmění.

...a došlo na moje slova

No... neuraž se, ale já bych teda nechtěl vidět, jak bys tu složitost pro konkrétní implementaci počítal

Tak radši dobrou

dolní odhad složitosti  O(V^2 log V)

o dost horší než jiné implementace.

možná je to jen O(V^2), pokud sortBy dokáže nalézt minimum v lineárním čase.

[lopata]

Kvituji s velkým vděkem, že jsi pastnul text, který podstatu problému perfektně vystihuje (daleko líp než napůl pochopený Turing, jak je tady zhusta vidět). Jenom škoda, že neuvádíš, odkud ta citace je.

Wikipedia, už jsem to jednou posílal: https://en.wikipedia.org/wiki/Halting_problem

Nicméně pořád se se mnou míjíš, já jsem netvrdil, že to řešitelné je, tvrdil jsem, že uvedená argumentace Turingem je chybná, neplatná. Pokud se na tomhle shodneme všichni, dá se jít dál a Turinga nechat spát

Argumentace Turingem funguje jedním směrem. Pokud by bylo možné na Turingově stroji rozhodnout halting problém, bylo by ho možné rozhodnout i pro jakýkoliv Java program na reálném stroji. Opačně to obecně neplatí.

Co "to"? Pro libovolný javovský program rozhodnout, jestli se na nějakém reálném hw zastaví? To se nejspíš nikomu (obecně) nepovede, protože to (obecně) není zajímavý problém.

Obecně je to velmi zajímavý problém a jeho řešení by rádi viděli všichni, kteří dělají mission critical aplikace (ne teda v Javě ). Kosmonatika, letectví, automotive, lékařství.... Řešení nemají, takže se bezpečnost snaží zaručit jinak, obvykle tak, že si stanoví nějaký subset a pravidla toho, co se smí používat (MISRA), ale 100% záruka to není, tím pouze snižují pravděpodobnost chyby.

[v]

Obecně je to velmi zajímavý problém a jeho řešení by rádi viděli všichni, kteří dělají mission critical aplikace (ne teda v Javě ). Kosmonatika, letectví, automotive, lékařství.... Řešení nemají

co např. spark ada? nebo simulink verification toolkit?

[Mirek Prýmek]

Argumentace Turingem funguje jedním směrem. Pokud by bylo možné na Turingově stroji rozhodnout halting problém, bylo by ho možné rozhodnout i pro jakýkoliv Java program na reálném stroji. Opačně to obecně neplatí.

[Poslední příspěvek k TS, už jsme se tady o tom naplácali dost nedávno]

Pokud by bylo možné vyřešit zastavení neomezeného stroje na neomezeném stroji, tak by to mělo (jakýkoli) praktický důsledek pro omezený stroj? Určitě?

To není "halting problem", to je "TM halting problem".

Vždyť to, co jsi citoval, to popisuje úplně přesně: neomezený stroj může pořád utíkat do nových a nových stavů. Proto ho nejde "vyčíslit" ani neomezeným strojem, protože ten bude taky jenom procházet ty nové a nové stavy (a nikdy neskončí). Pro omezený stroj to nemá důsledek vůbec žádný a problém zastavení neomezeného stroje nás z praktického hlediska tak nějak moc nepálí

Čili pokud se bavíme o problému zastavení omezeného stroje, je to úplně jiný problém a Turing pro něj neplatí ani "jedním směrem".

[JS]

Trosku to mate pomylene a velmi ste si o vzoroch necitali. Vzory nie su od toho, aby suplovali prikazy, alebo napomahali zlym rieseniam. Taketo vase "vzory" s goto by boli ihned zavrhnute.
To ani nie je mozne nazvat vzorom, taku hlupost by ste pomocou pattern language ani neopisali.

Potiz je, ze ty se na to divas optikou dnesnich jazyku. Abys pochopil co rikam, musis se podivat na tu vec v historicke perspektive. Je to jako s evoluci, taky neni intuitivni, kdyz se divas jen na to, co je ted.

Ja obcas (stare) programy v assembleru ctu a pisu. Takze, naprosto dobre vim, ze kdyz s takovym programem pracuji, pouzivam interne v hlave neco jako "GOTO patterns". A pokud ten program je zapsan nejak nestandardne, napr. se tam skace dovnitr smycky, nebo se tam prekryvaji dve smycky, je pro me narocnejsi ten program pochopit, protoze si ho nemuzu vysvetlit ve standardnich konceptech. A naopak, kdyz program pisu, uvazuji v terminech jako smycka a podmineny prikaz. Je to nachlup stejna situace jako u navrhovych vzoru v OOP.

A vidis, co se stalo. Nakonec lide zacali ty koncepty (idiomy) primo zapisovat (pomoci prikazu), misto aby je donekonecna prekladali do kodu rucne. To same se bude muset eventualne stat i s navrhovymi vzory. Ja bych mohl uplne stejne rict, ze Strategy pattern je blbost, protoze v FP proste predavame funkci, hotovo dvacet. (Jak uz jsem ukazal vys.)

(Sranda je, ze v assembleru, co pouzivam, nekteri lide pouzivaji specialni makra pro if, while apod., ale ja se jim vyhybam, protoze mi to prijde mene citelne. Takze svym zpusobem chapu odpor nadsencu pro design patterns vuci jejich konceptualizaci v jazyce.)

Vzory su od toho, aby sa z nich casom stali idiomy avsak opisuju inteligentne riesenia. OOP vzory su v aspektotovo-orientovanom programovani idiomy. AOP sa da realizovat aj miernym pozmenenim funkcionalneho. Jediny problem, ze funkcionalnemu programovaniu aj s AOP podivnost stale zostava aj jeho priaznivci su nadalej nieco ako crossfit-vegani.

Hm, AOP.. je to sice hezke, ale asi to bude slepa evolucni vetev OOP. Taky se mi to jeden cas libilo, ale potiz je, ze to neni moc dobre formalne ukotvene (narozdil od FP, ktere ma pevne formalni zaklady v lambda kalkulu(ech)). To je ostatne i problem s OOP.

[JS]

Makra sa vacsinou pouzivaju na to, aby programatori mohli pouzivat nie zrovna zrejme konstrukcie, ktore sa ani nemusia podobat povodnemu jazyku. Clovek neznaly, ake makra tam niekno naprplal vidi kod a ide si oci vyocit, ze ako to dofrasa moze vobec fungovat . Nebodaj, ked je este v makre chyba...  Zly koncept na urovni copy-paste programovania.

Funkce se vetsinou pouzivaji k tomu, aby programatori mohli pouzivat ne zrovna zrejme operatory, ktere se ani nemusi podobat vestavenym operatorum. Clovek neznaly, jake funkce tam niekno naprplal vidi kod a ide si oci vyocit, ze ako to dofrasa moze vobec fungovat. Nebodaj, kdyz je jeste ve funkci chyba...

Slozitost maker se precenuje. Ve finale to neni zase o tolik horsi nez funkce (lepe receno procedury). Bottom line - musis proste porozumet tomu, co ten zapis dela, jako u funkci. Jinak vetsinou se makra pouzivaji bud tam, kde chceme vygenerovat kod (treba kvuli efektivite, jsou to v podstate hacky do kompilatoru), nebo tam, kde chceme ovlivnit, co se bude vyhodnocovat a kdy a jak. Naopak, vhodne pouziti makra je mnohem lepsi nez copy-paste.

[Mirek Prýmek]

Slozitost maker se precenuje. Ve finale to neni zase o tolik horsi nez funkce

Přesněji je to úplně stejné, protože (dobře udělaná) makra jsou funkce

Jediný rozdíl je v tom, že makra se spouští při překladu a manipulují s kódem, který se dál ještě překládá a spouští. Takže ta horší srozumitelnost je daná tím, že makro mi vygeneruje nějakou funkci, která se pak ještě spustí. Pokud teda chci vědět "co to dělá", musím v hlavě zvážit dva po sobě následující kroky (transformace při překladu, spuštění při běhu), zatímco u normální funkce jenom jeden (spuštění při běhu).