30. 11. 2011 19:22 (aktualizováno)
zboj
Tentokrát něco málo z informatické prehistorie. Prolog zná asi každý programátor, i když většina jen ze školy jako příklad deklarativního logického programování. Svou největší slávu si užil nejspíše v době, kdy japonská vláda uvažovala o počítačích páté generace a Prolog měl být jazykem operačního systému. Z projektu nakonec víceméně sešlo a Prolog se vrátil do akademické sféry.
Na tvorbě Prologu se významně podílel Alain Colmerauer z Québeku a založil jej na svém dřívějším jazyce, Q-systémech. Narozdíl Prologu, který je univerzální, byly Q-systémy navrženy pro zpracování přirozeného jazyka. Jazyk to byl úspěšný, byl v něm implementován první komerčně použitelný (a velmi dlouho používaný) systém strojového překladu. Protože vznikl v Kanadě, překládal mezi kanadskými úředními jazyky, konkrétně z angličtiny do francouzštiny. Po mnoho let byl využíván v systému METEO pro překládání předpovědí počasí a nahradil většinu překladatelů (přes vysokou úspěšnost – kam se hrabe Google Translate – pochopitelně nemohl nahradit lidské překladatele stoprocentně).
Q-systémy byly v principu poměrně jednoduchým přepisovacím systémem operujícím nad stromy. Deklarativní transformační pravidla modifikovala graf s hranami ohodnocenými stromy, dokud šlo nějaké pravidlo nedeterministicky aplikovat. Stromy na hranách v konkrétním systému zachycovaly jazykovou informaci, buď slovo s morfologickou informací nebo syntaktický strom frází či celých vět.
Z teoretického pohledu se jednalo o formalismus na úrovni Turingova stroje (bylo v něm možné implementovat gramaticky typu 0 v Chomského hierarichii). Jednoduchá bezkontextová gramatika v Q-systémech vypadá například takto:
the == /DET.
a == /DET.
dog == /N.
cat == /N.
chases == /V.
/DET + /N == /NP.
/V + /NP == /VP.
/NP + /VP == /S.
Uvedená pravidla přímo odpovídají pravidlům Chomského frázové gramatiky. Malými písmeny jsou zapsány terminální symboly, lomítko uvozuje neterminály. Po nedeterministické aplikaci všech pravidel na větu The dog chases a cat dostaneme podle očekávání jako konečný výsledek neterminál S.
V reálném systému jsou pravidla samozřejmě složitější, protože v syntaktickém stromě je třeba uchovat všechny informace ze zdrojové věty. Princip aplikace pravidel a skládání frází je ovšem stejný. Je evidentní, že gramatiky jsou víceznačné (morfologicky i syntakticky) a výsledků je tak zpravidla víc. Například věta You saw a girl with a binocular může mít více významů (dívka měla dalekohled, byla viděna dalekohledem, ale saw znamená také řezat), z nichž některé mohou být sice sémanticky nesmyslné, ale syntakticky jsou všechny interpretace zcela v pořádku.
Dnes se podobné systémy vyvíjejí přímo v Prologu nebo nějakém jiném modernějším deklarativním jazyce, ale Q-systémy byly prvním průkopníkem.
