Algebraické efekty

15.6.2015 09:29 | Přečteno: 1639× | Programování |

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.

       

Komentáře

[Goheeca]

Zprvu jsem si myslel, že to není zapracovatelné do Haskellu a teď jsem naopak poznal k čemu jsou indexované monády.

[myself]

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?

[Radek Miček]

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).

[kralyk z abclinuxu]

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...

[Radek Miček]

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?

[kralyk z abclinuxu]

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.

[Radek Miček]

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.

[tacoberu]

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.