abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
dnes 00:22 | Pozvánky

Richard Stallman, zakladatel hnutí svobodného softwaru, projektu GNU a Free Software Foundation, vystoupí 6. června od 17:30 v Brně v kině Scala se svou přednáškou Free Software Movement and GNU/Linux Operating System. Přednášku organizuje Ústav práva a technologií Masarykovy univerzity.

Ladislav Hagara | Komentářů: 21
17.5. 21:11 | IT novinky

Hewlett Packard Enterprise (NYSE:HPE) kupuje společnost Cray Inc. (Nasdaq:CRAY) za přibližně 1,3 miliardy dolarů. Výrobce superpočítačů Cray má v seznamu 500 nejvýkonnějších superpočítačů na světě TOP500 aktuálně 52 superpočítačů. S Intelem staví další superpočítač Aurora. S AMD staví superpočítač za 600 milionů dolarů s názvem Frontier. Ten by měl v roce 2021 převzít vedení v TOP500.

Ladislav Hagara | Komentářů: 0
17.5. 19:44 | Zajímavý projekt

Ondřej Kokešpodcastu Dataři představuje projekt Česká otevřená data. Jedná se o sadu skriptů, které stahují především finanční data poskytovaná státními institucemi. V rozhovoru vysvětluje, že ke správné interpretaci dat jsou potřeba doménové znalosti, a popisuje zkušenosti, jak získat dokumentaci, která u datových sad často chybí.

Fluttershy, yay! | Komentářů: 0
17.5. 10:11 | Zajímavý projekt

Nadace XPRIZE vyhlásila před pěti lety soutěž Global Learning XPRIZE o nejlepší open source výukový program nebo inovativní způsob výuky, který umožní dětem v rozvojových zemích samostatně se naučit číst, psát a počítat. Tento týden byly vyhlášeny výsledky (YouTube). O první místo a 10 milionů dolarů se podělili Kitkit School a onebillion. Pět vítězných výukových programů bylo zveřejněno na GitHubu.

Ladislav Hagara | Komentářů: 19
17.5. 06:00 | Komunita

Dalších šest produktů od společnosti ThinkPenguin získalo certifikaci RYF (Respects Your Freedom, Respektuje vaši svobodu) udělovanou Nadací pro svobodný software (FSF). Certifikaci RYF má nově například také převodník z USB na paralelní port (LPT). Certifikace RYF byla představena v říjnu 2012.

Ladislav Hagara | Komentářů: 9
16.5. 23:11 | Pozvánky

Dnes je Světový den přístupnosti, anglicky Global Accessibility Awareness Day (GAAD, Wikipedie). Světový den přístupnosti vznikl v roce 2012. Jeho smyslem je šířit osvětu v této oblasti mezi širokou veřejností a motivovat ji k diskusím, přemýšlení a chuti dozvědět se o tématice přístupnosti webu, dokumentů, software, mobilních aplikací, asistivních technologiích či potřebách lidí s nejrůznějším postižením něco nového. O víkendu

… více »
Ladislav Hagara | Komentářů: 0
16.5. 19:55 | Pozvánky

Spolek OpenAlt zve příznivce otevřených řešení a přístupu na 164. brněnský sraz, který proběhne v pátek 17. května od 18:00 v restauraci Přístav u Vodů u Brněnské přehrady aneb v hantecu u Prýglu.

Ladislav Hagara | Komentářů: 2
16.5. 07:00 | Nová verze

Byla vydána nová major verze 9.0 svobodného systému pro řízení přístupu k síti (NAC) PacketFence (Wikipedie). Přehled novinek v oznámení o vydání. Pro uživatele předchozích verzí jsou k dispozici poznámky k aktualizaci.

Ladislav Hagara | Komentářů: 2
16.5. 06:00 | Bezpečnostní upozornění

K názvům Microarchitectural Data Sampling (MDS) a ZombieLoad Attack aktuálních bezpečnostních chyb v procesorech Intel přibyly nové názvy RIDL a Fallout. Na stránce RIDL and Fallout: MDS attacks jsou k dispozici další videoukázky, technické informace nebo i nástroj pro otestování, zda je konkrétní systém zranitelný. Ke stránkám ZombieLoad Attack, RIDL a Fallout lze přistupovat ze stránky CPU.fail.

Ladislav Hagara | Komentářů: 17
15.5. 18:22 | Zajímavý článek

V Edici CZ.NIC vyšla kniha Porty, bajty, osmibity od Martina Malého. Koupit ji lze tištěnou nebo zdarma stáhnout ve formátech PDF (3,6 MB), EPUB (10,8 MB ) a MOBI (28,7 MB). Jedná se o volné pokračování knihy Hradla, volty, jednočipy. Další informace ke knihám, odkazy na zdrojové kódy nebo errata na webových stránkách Porty, bajty, osmibity a Hradla, volty, jednočipy.

Ladislav Hagara | Komentářů: 24
GPU kterého výrobce aktuálně preferujete pro provoz Linuxu?
 (48%)
 (25%)
 (25%)
 (1%)
Celkem 292 hlasů
 Komentářů: 25, poslední 17.5. 18:39
Rozcestník

Algebraické efekty

15.6.2015 09:29 | Přečteno: 1203× | Programování | Výběrový blog

Algebraickým efektem (dále už jen efektem) jsou například výjimky, (asynchronní) vstup a výstup, měnitelný stav nebo nedeterminismus. V tomto zápisku si ukážeme, k čemu jsou algebraické efekty dobré, jak oddělit deklarace efektů od jejich implementace, a jak toto oddělení prospívá modularitě programů a usnadňuje jejich testování.

Začneme příkladem v OCamlu (efekty v OCamlu jsou experimentální, používáme kompilátor 4.02.1+multicore z repozitáře OCaml Labs):

type severity = Error | Warning

let log severity msg =
  let time = Unix.time () in
  let severity =
    match severity with
      | Error -> "ERROR"
      | Warning -> "WARN" in
  let str = Printf.sprintf "%s: %f %s" severity time msg in
  print_endline str

Funkce log zaloguje zprávu msg na standardní výstup. Samotná funkce je velmi jednoduchá, ale při pokusu ji otestovat nastanou problémy. Aby test vůbec zjistil, co funkce vypsala, musí číst ze standardního výstupu. Další potíž je v tom, že test neví, co vrátila funkce Unix.time, tudíž nemůže ověřit, že vypsaný čas je správný.

Abychom tyto problémy vyřešili, můžeme funkci log parametrizovat funkcemi time a print. Tato změna nám navíc umožní použít funkci log i v situacích, kdy chceme logovat jinam než na standardní výstup.

Pokud funkci log voláme z funkce f, musí funkce f předat funkci log argumenty pro parametry time a print. Pokud bychom funkci log natvrdo předali Unix.time () a print_endline, bude se pro změnu funkce f těžko testovat. Lepší tedy bude funkci f parametrizovat funkcemi time a print. Pokud takto budeme postupovat i u dalších funkcí, jenž volají log nebo f, budeme mít hodně parametrizovaných funkcí. Používání takových funkcí bude pěkná otrava, pokud budeme muset předávat všechny ty parametry ručně, což ve většině programovacích jazyků budeme muset.

Místo toho, abychom time a print předávali pomocí parametrů, můžeme je uložit do globálních proměnných. Globální proměnné inicializujeme pomocí Unix.time a print_endline. Kdykoliv někdo bude chtít logovat jinam, změní hodnotu globální proměnné print a poté, co skončí, tak obnoví její původní hodnotu. Toto řešení bohužel nefunguje pro vícevláknový kód. .NET Framework to řeší použitím globálních proměnných indexovaných vláknem (thread local). Bohužel, toto řešení nefunguje u výpočtů, které probíhají na různých vláknech, což může být případ asynchronních výpočtů. Pro řešení tohoto problému existuje v .NET Frameworku třída SynchronizationContext, která umožňuje zařídit to, že výpočet probíhá pouze ve správných vláknech. Nicméně použití třídy SynchronizationContext tak, aby byl program výkonný a zároveň i správný a přehledný, není jednoduché.

Všimněme si, že handlery výjimek (např. v C#) nemají problém s tím, když je výpočet přerušen a pak obnoven na jiném vlákně, a přesně toto bychom potřebovali i pro globální proměnné. Handlery výjimek jsou na zásobníku, stačilo by tedy, kdyby i globální proměnné pro time a print byly na zásobníku a putovaly po vláknech společně s výpočtem. Při nastavení globální proměnné by se vytvořil záznam na zásobníku, že proměnná má danou hodnotu, při čtení proměnné by se na zásobníku našel nejbližší záznam pro danou proměnnou a z něj se hodnota přečetla. Tomu se říká dynamic scoping a bohužel to většina mainstreamových jazyků včetně OCamlu nepodporuje.

Efekty

Jak jsme již naznačili, mohli bychom použít něco jako výjimky. Místo volání time resp. print vyhodí log výjimku Time resp. Print. Handler, který je na zásobníku, výjimku chytí, zjistí čas resp. vypíše zprávu, a pak pokračuje ve funkci log v místě, kde byla výjimka vyhozena. Avšak výjimky takto obvykle nefungují – například v Javě není možné z bloku catch skočit zpět za příkaz throw, který výjimku vyhodil, a pokračovat, jakoby se nic nestalo. V OCamlu je toto možné pomocí efektů. Time a Print tedy nebudou výjimky, ale efekty. Začněme jejich deklarací:

effect Time : float
effect Print : string -> unit

Deklarace nám říká, že výstup efektu Time je hodnota typu float. Vykonáme-li tedy efekt Time pomocí perform Time, dostaneme číslo v plovoucí řádové čárce – jinak řečeno výraz perform Time se vyhodnotí na číslo v plovoucí řádové čárce. Vstup efektu Print je řetězec a výstup je hodnota typu unit (typ unit má jedinou hodnotu () – používá se, když nám na hodnotě nezáleží, například tam, kde se v Javě používá void). Přepišme funkci log pomocí efektů:

type severity = Error | Warning

let log severity msg =
  let time = perform Time in
  let severity =
    match severity with
      | Error -> "ERROR"
      | Warning -> "WARN" in
  let str = Printf.sprintf "%s: %f %s" severity time msg in
  perform (Print str)

Když funkci log spustíme, například pomocí

let () = log Error "Invalid configuration"

bude vyhozena výjimka Unhandled. Potíž je v tom, že efektům chybí interpretace – nikde v programu jsme neurčili, co mají efekty dělat. To napravíme snadno, volání log obalíme handlerem efektů:

let () =
  match log Error "Invalid configuration" with
    | () -> ()
    | effect Time k -> continue k (Unix.time ())
    | effect (Print str) k -> print_endline str; continue k ()

Řádek začínající | effect (Print str) k -> říká, co se má udělat, když nastane efekt Print str. V našem případě se vypíše řetězec str a poté se pokračuje ve funkci log v místě, kde byl efekt vyhozen. Jelikož je druhým argumentem funkce continue hodnota (), vrátí volání perform, které efekt vyhodilo, hodnotu (). Pokud bychom chtěli, aby volání perform skončilo výjimkou Exit, použili bychom discontinue k Exit.

Podobně řádek začínající | effect Time k -> říká, že když nastane efekt Time, tak volání perform Time vrátí hodnotu vrácenou funkcí Unix.time ().

Nakonec řádek začínající | () -> říká, co dělat, když volání log Error "Invalid configuration" skončí hodnotou ().

Efekty tedy můžeme chápat jako výjimky, které z handleru dovolují skočit zpět do místa vyhození výjimky a kde navíc funkce nebo konstrukce pro vyhazování výjimek (v OCamlu raise, v C# a Javě throw) vrací hodnotu.

Když funkce log udělá efekt, je přerušena. Volání continue k v resp. discontinue k e pak obnoví její běh. Běh funkce není třeba obnovovat ihned, dokonce ho nemusíme obnovit vůbec. Pokud běh nikdy neobnovíme, bude se efekt chovat jako výjimka. V případě efektů však typová kontrola vždy předpokládá, že běh bude obnoven, volání perform tedy musí vracet hodnotu správného typu. Například následující výraz

1 + perform (Print "Hi")

neprojde typovou kontrolou, neboť perform vrací hodnotu typu unit, ale operátor + vyžaduje dvě hodnoty typu int. S výjimkami takový problém nenastane a výraz

1 + raise Exit

typovou kontrolou projde. k je ve skutečnosti kontinuace vymezená blokem match. V některých jazycích můžeme vymezenou kontinuaci (angl. delimited continuation) použít více než jednou, v OCamlu ji jde použít nejvýše jednou, jinak je vyhozena výjimka. Toto omezení je daň za rychlou a snadnou implementaci (není například třeba kopírovat kus zásobníku). Kvůli tomuto omezení pak není možné některé efekty implementovat, například nedeterminismus. Poznamenejme, že pro OCaml existuje knihovna delimcc implementující vymezené kontinuace, jež lze použít vícekrát (některé knihovny však s takovými kontinuacemi nemusí fungovat korektně).

Další použití efektů

K čemu jsou efekty dobré v praxi? Aplikací efektů je kooperativní multitasking nebo generátory. Některé lispovské jazyky nemají klasické výjimky, ale používají systém podmínek a restartů, jenž můžeme také nasimulovat v OCamlu pomocí efektů a výjimek.

Mnoho jazyků dnes umožňuje psát asynchronní kód. Bohužel, mnoho jazyků však nedovoluje zavolat asynchronní funkci z normální funkce, aniž by došlo k zablokování vlákna. Důsledkem je, duplikace kódu – musíme psát jednu normální funkci a jednu asynchronní funkci (například v C# resp. Javě vrací asynchronní funkce Task resp. Future). Tento problém může nastat i s jinými efekty, pak píšeme jednu funkci bez efektů a jinou funkci s efekty. Například v Haskellu je funkce map dvakrát, jednou se jmenuje map (bez efektů) a podruhé mapM (s efekty). Dalším příkladem je rozhraní IEnumerable v C# (v Javě se podobná věc jmenuje Iterable). Toto rozhraní nepodporuje asynchronní operace, proto se nyní uvažuje o dalším rozhraní, které by je podporovalo.

Efekty v OCamlu umožňují tuto duplikaci odstranit. Například normální funkce může volat asynchronní funkci bez zablokování vlákna. Na druhé straně nemá OCaml efektový systém, tj. typový systém nesleduje, jaké efekty výrazy dělají. Stejně se sice chová Haskell a i další mainstreamové jazyky, jenže tam není paleta efektů tak široká. Například v Haskellu existuje jediný efekt – divergence.

Závěr

Efektový systém s inferencí efektů lze vyzkoušet v jazyce Eff. Bohužel, neznám žádný mainstreamový jazyk, který by měl efektový systém (kontrolované výjimky v Javě jsou určitý náznak). Možná se ho časem dočkáme v OCamlu nebo Scale – o efektovém systému ve Scale se nedávno zmínil Martin Odersky.

       

Hodnocení: 91 %

        špatnédobré        

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

Komentáře

Vložit další komentář

Goheeca avatar 16.6.2015 14:09 Goheeca | skóre: 7
Rozbalit Rozbalit vše Re: Algebraické efekty
Zprvu jsem si myslel, že to není zapracovatelné do Haskellu a teď jsem naopak poznal k čemu jsou indexované monády.
16.6.2015 16:24 myself
Rozbalit Rozbalit vše Re: Algebraické efekty
Mnozi efektove, tisice slonu a kontinuace.

Seriously, s ludmi od funkcionalnych jazykov je nieco spatne. Len co si vymyslia pekne slovo continuation, musia ho nahradit skaredym slovom effect. Alebo som nieco nepobral?
16.6.2015 17:12 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Algebraické efekty
Len co si vymyslia pekne slovo continuation, musia ho nahradit skaredym slovom effect.
Algebraické efekty a kontinuace jsou dvě různé věci. V handleru jsme sice používali vymezené kontinuace, ale obecně lze mít jazyk s efekty bez handlerů (například měnitelný stav v mainstreamových jazycích) nebo mít handlery bez kontinuací (například handlery výjimek v mainstreamových jazycích).
18.6.2015 08:18 oryctolagus | skóre: 29 | blog:
Rozbalit Rozbalit vše Re: Algebraické efekty
Místo toho, abychom time a print předávali pomocí parametrů, můžeme je uložit do globálních proměnných. Globální proměnné inicializujeme pomocí Unix.time a print_endline. Kdykoliv někdo bude chtít logovat jinam, změní hodnotu globální proměnné print a poté, co skončí, tak obnoví její původní hodnotu. Toto řešení bohužel nefunguje pro vícevláknový kód. .NET Framework to řeší použitím globálních proměnných indexovaných vláknem (thread local).
Co takhle mít jednu proměnnou pro všechny vlákna a přístup nějak ochránit proti race condition, třeba mutexem? Logování se typicky nevolá moc často a beztak je to typicky I/O operace, takže overhead zámku mi nepřijde jako problém...
18.6.2015 09:40 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Algebraické efekty
To nepomůže, když dva paralelní výpočty běžící v různých vláknech chtějí používat různé loggery, ne?
18.6.2015 10:11 oryctolagus | skóre: 29 | blog:
Rozbalit Rozbalit vše Re: Algebraické efekty
Aha, to ne, no. V takovým případě bych dal těm výpočtům nějaký kontext (v klasických OOP jazycích by to byla nejspíš nějaká třída), jehož součástí by byly parametry logování.

Ty efekty se mi nelíbí v tom, že znepřehledňují control flow imho... Ale je to zajímavá věc, neznal jsem.
18.6.2015 21:03 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Algebraické efekty
V takovým případě bych dal těm výpočtům nějaký kontext (v klasických OOP jazycích by to byla nejspíš nějaká třída)
Ano, to lze. Nicméně, pak je třeba vyřešit předávání (nebo nastavování) těch kontextů – například, když mám jeden výpočet a z něj zavolám druhý výpočet, tak aby ten druhý výpočet dostal správný kontext.
26.8.2015 00:00 tacoberu | skóre: 5
Rozbalit Rozbalit vše Re: Algebraické efekty
Stejně se sice chová Haskell a i další mainstreamové jazyky, jenže tam není paleta efektů tak široká. Například v Haskellu existuje jediný efekt – divergence.

Mohl by si se rozepsat, jaké další efekty (krom devergence) mohou existovat? Snažím se v tom zorientovat.

Díky za skvělej článek.

Založit nové vláknoNahoru

ISSN 1214-1267   www.czech-server.cz
© 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.