Nová kniha: Regulated Grammars and Automata

Před cca dvěma týdny, konkrétně 17. března 2014, nám s prof. Medunou vyšla již druhá kniha z oblasti teorie formálních jazyků. Jedná se o téměř 700 stran rozsáhlou monografii zabývající se řízenými formálními modely. Kniha byla vydána mezinárodním nakladatelstvím Springer v New Yorku. V příspěvku bych vás chtěl s knihou seznámit a popsat své osobní zkušenosti s její tvorbou.

Suché údaje na úvod

• Autoři: Alexander Meduna, Petr Zemek
• Název: Regulated Grammars and Automata
• Počet stran: 694
• Vydavatel: Springer, New York, US
• ISBN: 978-1-4939-0368-9
• Odkazy: stránka vydavatele | amazon.com | wiki prof. Meduny | prezentace knihy

O čem kniha je?

Stejně jako první kniha, i tato se zabývá tzv. řízenými formálními modely. Jedná se o klasické modely doplněné dodatečným matematickým formalismem, pomocí kterého lze předepsat řízení v těchto modelech. Tím lze dosáhnout mnoha nových a žádaných vlastností, jako je například zvýšení generativní síly. Mezi tyto modely patří např. řízené gramatiky, což jsou ve své podstatě bezkontextové gramatiky doplněné o řídicí mechanismy. Mezi další pak patří řízené automaty a řízené gramatické systémy. Toto téma spadá do oblasti teoretické informatiky, teorie formálních jazyků a diskrétní matematiky.

Kniha se skládá z 9 částí a 22 kapitol a sumarizuje poznatky o řízených gramatikách a automatech. V kapitole 1 je dán úvod do studovaného tématu a umístění do vědeckého kontextu. Aby byla kniha soběstačná, tak kapitoly 2 a 3 obsahují souhrn a definice všech použitých matematických pojmů, notace a základů teorie formálních jazyků. Kapitola 4 definuje gramatiky řízené na základě kontextu a studuje jejich vlastnosti. Následující kapitola 5 se pak zabývá gramatikami řízenými pravidly.

V kapitole 6 jsou zavedeny a studovány tzv. jednostranné gramatiky s nahodilým kontextem, což je téma mé disertační práce. Kapitola 7 řeší eliminaci tzv. vymazávajících pravidel z bezkontextových gramatik a řízených gramatik. V kapitole 8 jsou studovány gramatiky, které generují jazyky rozšířené o doplňující informace, jako např. sekvence pravidel, které byly použity při generování řetězců. Kapitola 9 zavádí bezkontextové gramatiky nad slovními monoidy a studuje jejich generativní sílu.

Kapitoly 10 až 12 se zaměřují na řízené gramatiky pracující paralelně. Konkrétně kapitola 10 definuje a studuje L systémy řízené kontextem, kapitola 11 zavádí uniformní přepisování u paralelních gramatik, a kapitola 12 studuje paralelní gramatiky definované nad slovními monoidy.

Další část knihy se zabývá řízenými gramatickými systémy. Přesněji, kapitola 13 zavádí a studuje multigenerativní gramatické systémy. Kapitola 14 pak řeší tzv. čisté verze řízených gramatických systémů, které mají pouze terminální symboly.

Tématem následující části jsou řízené automaty. Kapitola 15 studuje samořídící automaty a kapitola 16 se zaměřuje na konečné a zásobníkové automaty řízené pomocí jazyků. Kapitoly 17 a 18 pak definují a studují skákající konečné automaty a hluboké zásobníkové automaty, které mají vazby na řízené automaty.

I přesto, že celkově je kniha primárně orientována teoreticky, tak jedna část v knize je věnována praxi. Konkrétně v kapitole 19 jsou uvedeny praktické perspektivy aplikací řízených modelů. V kapitole 20 jsou pak prezentovány velmi specifické případy užití těchto gramatik v praxi, konkrétně v biologii, lingvistice a syntaktické analýze.

V závěru knihy jsou v kapitole 21 naznačeny budoucí trendy, shrnuty otevřené problémy a sepsány bibliografické a historické poznámky. Kapitola 22, které knihu uzavírá, obsahuje souhrn všeho, co se v knize řešilo.

Kde si ji mohu koupit či zhlédnout?

Knihu si lze koupit např. na stránce vydavatele či na amazonu. Musím vás ale předem varovat, že jelikož je kniha úzce zaměřená především na vědce a Ph.D. studenty, tak i cena tomu odpovídá. Konkrétně vydavatel ji nabízí za 118 eur (3 200,- Kč).

Lepší bude se na knihu mrknout v knihovně. Např. v knihovně na FITu je kniha k dispozici (celkem je tam sedm výtisků, ale část jich je již zapůjčena).

Jak dlouho jste na knize pracovali?

Na knize jako takové jsme začali pracovat v květnu 2011, kdy došlo k podepsání smlouvy mezi vydavatelem (Springer) a námi. Deadline jsme měli říjen 2013. Na knize jsme tedy intenzivně pracovali cca dva a půl roku. Koncem roku 2013 šla kniha do produkce. Začátkem roku 2014 jsme obdrželi verzi knihy k poslední kontrole. Kniha vyšla 17. března 2014.

Jaké jsou tvé zkušenosti s tvorbou tak rozsáhlé knihy?

Asi to nikoho nepřekvapí, ale kniha o 700 stranách, psaná dva a půl roku, se píše úplně jinak, než bakalářské/diplomové/disertační práce, které mají rozsah cca 40 - 120 stran a jsou napsané v řádu měsíců. Níže jsem sepsal několik postřehů.

• Koncept a struktura knihy. Kniha musí mít souvislou a jednotnou stavbu a jednotlivé části na sebe musí navazovat. Názvy kapitol a sekcí jsou podstatně abstraktnější, než je tomu u kratších dokumentů. Taktéž je třeba promyslet, kam umístit definice a výsledky, protože jsou potřeba na různých místech v knize. Nejhorší jsou pak cyklické závislosti. V neposlední řadě je třeba řešit další věci, které se u jiných publikací neřeší, jako je rejstřík, seznam použitých symbolů apod.
• LaTeX. Pro sazbu knihy jsme použili LaTeX, za což jsme nesmírně vděčný, protože psát knihu o takovém rozsahu a navíc matematicky orientovanou v čemkoliv jiném by byla sebetrýzeň. Vysázení knihy jsme měl kompletně na starosti já, takže jsem si s LaTeXem užil času až až :).
• Strukturování zdrojových kódů. Je potřeba vhodně rozdělit a strukturovat zdrojové kódy. Přece jen, mít přes 30 000 řádků v jednom zdrojáku je značně nepohodlné. Dalším důvodem je doba vysázení knihy do PDF. Překlad celé knihy trvá cca 15 sekund. I když je 15 sekund na 700 stránek moc pěkné číslo, tak pokud pracujete na jedné kapitole a při každém překladu byste měli čekat 15 sekund, než uvidíte výsledek, tak by vás to zbytečně zdržovalo. Vhodnější je tedy překládat jen to, co v danou chvíli potřebujete, k čemuž vám vhodné rozdělení zdrojáků napomůže.
• Sjednocení vyjadřování. To, co napíšete při zahájení práce na knize, musí být konzistentní s tím, co napíšete o rok později. Mnohdy se nám stávalo, že jsme po určité době po sobě jisté části přepisovali, protože se za tu dobu mírně změnil náš styl vyjadřování apod. Nebo jsme zjistili, že jisté konstrukce jsou gramaticky špatně, a bylo třeba je opravit na všech místech. Jsou to sice drobnosti, ale v tom moři textu jsou znatelně cítit. Samozřejmě lze namítat, že tyto problémy je třeba řešit i u bakalářky/diplomky, ale zde nabývají jiného rozměru.
• Sjednocení formátování. Část vám sice předepíše šablona, ale mnoho věci si musíte vyřešit sami. Např. číslování (1), (a), (I), 1., a., I. apod., což by mělo být konzistentní v celé knize. Je dobré si v LaTeXu udělat vlastní zkratky (\newcommand{}), abyste při změně formátování nemuseli měnit všechny výskyty dané konstrukce, ale změnili je pouze na jedno místě. Celkem jsem použil přes 500 zkratek.
• Sjednocení značení a terminologie. Z hlediska času a námahy definitivně nejnáročnější část. V celé knize byste měli používat konzistentní značení a terminologii. Problém je, že v literatuře se různé věci nazývají jinak a v každém článku si autoři zvolí vlastní způsob značení. V knize je však potřeba toto všechno sjednotit. Někde je např. formalismus definován jako pětice, jinde jako šestice, jinde se zase liší význam komponent onoho modelu apod. Dále, někde se např. používá termín "propagating", jinde "non-erasing" a ještě jinde "epsilon-free". Nejhorší je dělat změny v důkazech, kdy máte důkaz postavený na jistém značení a máte jej předělat do jiného značení. Jelikož jsou matematické důkazy precizní záležitost, je potřeba si dát pozor na to, abyste někde neudělali chybu.
• Kontroly. Jen samotná kontrola všech 700 stránek zabrala každému z nás cca měsíc práce. Nalezené nesrovnalosti pak bylo potřeba opravit, což byla další práce. Při přijetí tiskové verze od vydavatele bylo navíc potřeba provést další kontroly, protože jejich sazeči v textu provedli různé změny, které se mohly zdát i nepatrné, ale v matematickém textu může být každá změna k horšímu. Celkem jsme v tiskové verzi ještě odhalili a reportovali cca 120 chyb.

Jaká byla spolupráce s vydavatelem?

Na začátku jsme dostali pokyny a LaTeX šablonu, ve které jsme knihu vypracovali. Většinu času jsme pracovali samostatně s tím, že vydavatel se průběžně dotazoval na stav knihy. Kdykoliv jsme něco potřebovali vědět, tak jsme dostali promptní reakci. Vše bylo transparentní a o všem jsme byli informováni.

Co říci na závěr?

Na knihu jsem velmi pyšný a jsem rád, že jsme ji dali dohromady. Bylo s tím opravdu hodně práce, ale výsledek stojí za to. I když, to je na čtenářích, aby to posoudili.