Siri, potřebuju se zbavit těla

Umělou inteligencí je lidstvo fascinováno odnepaměti, už ve starém Egyptě či antickém Řecku se filozofové zabývali stroji myslícími jako člověk. Teprve počítače učinily tuto myšlenku realizovatelnou a zdá se, že právě letos se objevila první komerční aplikace umělé inteligence, která je použitelná: automatický asistent Siri v iPhonu 4S.

Vše je seznam

Ve třicátých letech došlo k rozvoji formální logiky, algoritmizace a vůbec všeho, co dnes známe jako teorie vyčíslitelnosti. Zpětně se ukazuje, že velkým pokrokem byl lambda kalkul, jejž vynalezl Alonzo Church. Na ten navázal po válce John McCarthy, když se snažil vymyslet způsob zápisu libovolného algoritmu, který by byl jednodušší než Turingův stroj. Výsledkem jeho čistě teoretické práce byla první verze Lispu. McCarthy byl nemálo překvapen, když jeden z jeho studentů, Steve Russell, napsal program schopný lispovské výrazy vyhodnocovat na počítači. Zrodil se tak jeden z vůbec prvních jazyků vyšší úrovně.

Lisp se stal populárním zejména na poli umělé inteligence, a to díky své jednoduché syntaxi založené na symbolických výrazech (jedinou datovou strukturou je seznam), formální síle a v neposlední řadě absenci alternativy. Protože tehdejší počítače výkonem zrovna neoplývaly, vznikal pro systémy psané v Lispu speciální hardware. Než se ale stihl prosadit, výkon běžných počítačů se zvýšil natolik, že pro Lisp postačoval.

I když dnes je Lisp jazykem spíše okrajovým, přímo či nepřímo ovlivnil většinu dnešních programovacích jazyků. Jako první používal automatickou správu paměti, inkrementální kompilaci, virtuální stroj atd. A veleužitečné lambda výrazy se dostaly do C++ až letos s novým standardem jazyka (C++11).

Vynález gramatiky

Přestože Noam Chomsky není a nikdy nebyl informatikem, zcela změnil kromě formální jazykovědy právě informatiku, konkrétně tvorbu překladačů a interpretů. Chomského fascinovalo, že malé děti jsou schopny naučit se perfektně jazyk, přestože v prvních letech života přijdou do styku jen s velice omezenou množinou vět. Jeho vysvětlení, mimochodem dodnes kontroverzní, předpokládá v lidském mozku existenci mechanismu, ve kterém je struktura jazyka zakódována, a parametrů, které každé dítě získá v prvních letech života z okolí. Chomsky šel ještě dál a tento domnělý mechanismus popsal. Jako Američanovi mu byl bližší lingvistický deskriptivismus spíše než evropská funkcionální jazykověda, inspiroval se proto bezprostředními složkami Leonarda Bloomfielda a vytvořil systém formálních přepisovacích pravidel. Zrodila se tak formální gramatika.

Přestože v jazykovědě má Chomského teorie dodnes odpůrce, v informatice způsobila doslova revoluci. Jak se totiž záhy ukázalo, nejobecnější typ Chomského formální gramatiky je ekvivalentní Turingovu stroji, takovou gramatikou lze tedy vyjádřit libovolný algoritmus. Omezenější typ gramatik je zase ekvivalentní regulárním výrazům. A hlavně, bezkontextové gramatiky jsou základem většiny dnešních programovacích jazyků, protože pro ně existují efektivní algoritmy pro analýzu (parsing).

Chomského zásluhou je oddělení syntaktické struktury od sémantiky. Jeho slavná věta Colorless green ideas sleep furiously je v angličtině naprosto v pořádku, i když postráda význam. Přeházíme-li slova (např. takto: Furiously sleep ideas green colorless), dostaneme nesmysl. Rozdíl mezi těmito větami je ten, že první z nich je, vyjádřeno Chomského terminologií, generována formální gramatikou anglického jazyka. Podobně v programovacím jazyce můžeme napsat x / 0, což je syntakticky naprosto korektní výraz (je-li x číselná proměnná), ale sémanticky je to nesmysl, protože nulou se dělit nedá.

Confusio linguarum

S Chomským vliv jazykovědy na informatiku nekončí. Kromě projektů zabývajících se umělou inteligencí vznikaly po válce také projekty mající za cíl strojový překlad. Ve Spojených státech byla většina financována z vojenského rozpočtu, protože v době studené války mělo ministerstvo obrany eminentní zájem na automatické analýze textů v ruštině.

Pro implementaci zpracování přirozeného jazyka chyběl vhodný formalismus. Jedním z prvních byly Q-systémy vytvořené Francouzem Alainem Colmerauerem v Kanadě. Jeho projekt byl orientován prakticky a výsledkem práce jeho týmu byl vůbec první úspěšně nasazený systém strojového překladu. Nazýval se METEO a překládal z angličtiny do francouzštiny předpovědi počasí.

I když byly Q-systémy ekvivalentní Turingovu stroji (bylo v nich možné implementovat Chomského gramatiky typu 0, tedy ty nejobecnější), jednalo se spíše o doménově specifický jazyk, který se pro něco jiného než zpracování přirozených jazyků příliš nehodil. Přímo ale ovlivnily pozdější jazyky pro logické programování, které převzaly koncepty jako deklarativní zápis pravidel, unifikaci či nedeterministické vyhodnocování výrazů.

Programujme logicky

Když se Alain Colmerauer vrátil do Francie, vytvořil tým na univerzitě v Marseille pod jeho vedením Prolog. Tento jazyk vyšel z Q-systémů, byl ale univerzálně použitelný. Podobně jako jsou podstatou Lispu lambda výrazy, Prolog je založen na Hornových klauzulích. První interpret napsal jmenovec prvního implementátora Lispu Steva Russella, Philippe Roussel. Programy v Prologu byly zpočátku interpretovány, teprve na začátku 80. let vymyslel David Warren bajtkód a k němu virtuální stroj (tzv. WAM – Warren's abstract machine) a pro Prolog začaly vznikat překladače.

Většina programátorů jistě zná Prolog ze studií, nemá tedy smysl se tu o něm rozepisovat. Připomeňme, že narozdíl od imperativních jazyků (kam spadají i objektově orientované jazyky) v Prologu program nepopisuje, jak problém řešit, ale co se má řešit. To se ovšem snáze řekne, než udělá, proto byl Prolog postupně rozšířen o některé koncepty z imperativních jazyků. Výpočet například není striktně nedeterministický (jako u Q-systémů), byla přidána negace, řez apod. Zastánci čistě logického programování to sice považují za zcestné, ale z praktického hlediska to umožňuje psát v Prologu efektivnější programy.

Pátá generace počítačů

V 80. letech Prolog zpopularizoval projekt japonského Ministerstva mezinárodní obchodu a průmyslu, jehož cílem bylo vyvinout počítač páté generace. V předchozích desetiletích Japonci ovládli americký trh se spotřební elektronikou a automobily a nyní si vytyčili cíl dobýt trh s počítači. Zmíněné ministerstvo si totiž nechalo vypracovat nákladnou studii, ze které vyplynulo, že odvětvím budoucnosti je informatika. Byl vytvořen Institute for New Generation Computer Technology a konsorcium největších japonských společností se pustilo do výzkumu a vývoje.

Cílem Japonců bylo vyvinout zcela nový hardware, odklánějící se od von Neumannovy architektury, a k němu operační systém umožňující komunikaci v přirozeném jazyce. V roce 1985 byl do provozu uveden první takový počítač, Personal sequential inference machine. Operační systém byl napsán v KL0, což je zkratka z Kernel language. KL0 nebylo nic jiného než Prolog upravený pro paralelní výpočty.

Rozhodnutí vyvinout zcela nový počítač bylo dáno slabým výkonem tehdejšího hardwaru. A protože výsledkem nemělo být nic menšího než funkční umělá inteligence, rozhodli se vědci ve fázi plánování vyvinout nový operační systém v Prologu. Vyvinuté počítače měly stovky procesorů a veškeré aplikace využívaly služeb jádra napsaného v KL0 (a později v ještě paralelizovějším Prologu KL1).

Projekt bohužel nakonec skončil neúspěchem, respektive předběhl svoji dobu. Dal ovšem akademické obci mnoho výsledků ohledně reprezentace znalostí apod.

Armáda spásou

Jak známo, do vědy jsou politici ochotni investovat velké peníze v zájmu obrany, což je důvod, proč pod americkým ministerstvem obrany existuje agentura Defense Advanced Research Projects Agency (DARPA). Jedním z projektů této agentury byl vývoj malého zařízení spojujícího rozpoznávání a generování řeči a automatického překladu. Výsledkem projektu byla krabička, se kterou běhali američtí vojáci po iráckém bojišti a mohli se díky ní domluvit s civilním obyvatelstvem. Prostě řekli něco anglicky a ze sluchátek zaznělo to samé v irácké arabštině (starší verze jen vypisovala překlad na obrazovku, než generálové do vlasti poslali hlášení, že velká část obyvatel neumí číst). V současnosti pracuje DARPA na podobném projektu, jen jde o překlad mezi angličtinou a perštinou. Asi čekají válku s Íránem.

Projekt CALO patřil v DARPĚ k těm větším, pracovaly na něm stovky vědců. Cílem bylo vyvinout automatického asistenta, kterému můžete položit otázku a on na základě databáze znalostí odpoví. Později byl tento projekt vyčleněn do samostatné firmy, která vyvinula aplikaci Siri pro iPhone a nakonec byla koupena Applem.

Celý tento dlouhý vývoj od Turingova stroje přes lambda výrazy, Lisp, Chomského fascinaci fungováním dětského mozku, Q-systémy a japonskou ambicióznost až po snahu (nejen) amerického ministerstva obrany mít na bojišti i v zázemí lepší technologii než nepřítel vedl k tomu, že když iPhonu dnes řeknete větu z nadpisu tohoto článku, příjemný ženský hlas vám ve zlomku vteřiny odpoví: „Přejete si seznam přehrad, dolů, skládek, nebo močálů?“