Koprogram

Koprogramy (anglicky coroutine) jsou v informatice programové komponenty, které umožňují na rozdíl od podprogramů (procedur, funkcí, metod) více vstupních bodů, pozastavení a obnovení výpočtu v jejich různých místech. Koprogramy jsou vhodné pro implementaci kooperativního multitaskingu, iterátorů, proudů (stream) a trubek (pipe).

Termín koprogram poprvé použil Melvin Conway ve své seminární práci v roce 1963.

Srovnání s podprogramy

Koprogramy jsou obecnější, než podprogramy. Životní cyklus podprogramů je řízen zásobníkem (LIFO) (tj. poslední volaný podprogram provede návrat jako první). Naproti tomu životní cyklus koprogramů závisí výhradně na jejich použití a aktuální potřebě.

Podprogram má pouze jeden vstupní bod (svůj začátek) a můžeme se z něj vrátit jen jednou. Naproti tomu koprogramy se mohou vracet několikrát (příkazem yield). Začátek koprogramu je první vstupní bod a následující vstupní body označuje příkaz yield. V praxi příkaz yield vrací výsledek a předává řízení do volajícího koprogramu podobně, jako u klasických podprogramů. Avšak při dalším volání koprogramu nezačne provádění na jeho začátku, ale následujícím příkazem za posledním provedeným příkazem yield.

V následujícím příkladu si ukážeme, jak mohou být koprogramy užitečné. Předpokládejme, že máme vazbu producent-konzument, kde jedna rutina vytváří položky a přidává je do fronty a druhá odebírá položky z fronty a zpracovává je. Z úsporných důvodů chceme přidávat a odebírat několik položek najednou. Zápis programu by mohl vypadat takto:

var q := new queue

coroutine produce
loop
while q is not full
create some new items
add the items to q
yield to consume

coroutine consume
loop
while q is not empty
remove some items from q
use the items
yield to produce

Fronta je zde kompletně naplněna nebo vyprázdněna před voláním příkazu yield a předáním řízení druhému koprogramu. Vnitřní koprogramové smyčka zajišťuje další volání koprogramů přímo za příkazem yield.

Přestože je tento příklad obvykle uváděn jako úvod do multithreadingu, není nutné, abychom kvůli tomu vytvářeli dva thready. Příkaz yield může být implementován jako přímý odskok z jedné rutiny do druhé.

Srovnání s generátory

Generátory jsou také zobecněním podprogramů, ale jsou více limitovány než koprogramy. Obě umožňují více návratů, což zastaví jejich vykonávání s tím, že je možné pokračovat z více vstupních bodů. Liší se v tom, že korutiny mohou kontrolovat místo, ve kterém bude vykonávání programu pokračovat po zavolání yield. Toto generátory nemohou ovlivnit, pouze vrací kontrolu zpět na místo kde byly zavolány.

Nicméně je stále možné implementovat koprogramy za pomocí více generátorů s vrchní rozhodující funkcí, která předává kontrolu explicitně svým generátorům identifikovatelným pomocí tokenů, které jsou z nich předány zpět:

var q := new queue

generator produce
    loop
        while q is not full
            create some new items
            add the items to q
        yield consume

generator consume
    loop
        while q is not empty
            remove some items from q
            use the items
        yield produce

subroutine dispatcher
    var d := new dictionary(generator → iterator)
    d[produce] := start produce
    d[consume] := start consume
    var current := produce
    loop
        current := next d[current]

Mnoho implementací koprogramů pro jazyky s podporou generátorů, avšak bez nativních koprogramů (e.g. Python před 2.5), využívá tento přístup.

Častá použití

Koprogramy jsou užitečné při implementaci:

• Stavových automatů v jediném podprogramu, kde stav je určen aktuálním vstupním/výstupním bodem procedury;takto může vzniknout více čitelný kód v porovnání s použitím goto a m;6e být také implementován pomocí vzájemné rekurze s koncovým voláním.
• Aktorový model souběhu, například v počítačových hrách. Každý aktor má své vlastní procedury (logicky odděluje kód), ale dobrovolně předává kontrolu hlavnímu plánovači, který je vykonává sekvenčně (určitá forma kooperativního multitaskingu).
• Generátory jsou užitečné pro proudy – zejména vstupní/výstupní – a pro obecné procházení datových struktur.
• Komunikace mezi sekvenčními procesy, kde každý podproces je koprogram. Vstupně-výstupní kanály a blokující operace volají yield v koprogramu a plánovač je následně odblokuje při dokončení.

Reference

V tomto článku byl použit překlad textu z článku Coroutine na anglické Wikipedii.