Cvičení 1

Kurs: Paradigmata programování IV
Přednášející: Vilém Vychodil
Cvičící: Vilém Vychodil
Téma cvičení: Seznámení se s jazykem PROLOG. Databázový model PROLOGu.

Úvod do logického programování. Základy práce s interpretem PROLOGu. Logický program. Fakta, pravidla a dotazy. Syntaxe výrazů jazyka PROLOG. Vytváření databáze faktů, vytváření pravidel a cílů. Práce s malými a velkými databázemi faktů. Vytváření databází faktů podle slovního popisu. Nalezení nejměnšího herbrandovského modelu.


1.  Jak pracovat s interpretem PROLOGu

Na přednášce byly prezentovány základní myšlenky a motivace logického programování. Logické programy lze obecně chápat jako definice faktů a pravidel, kterými lze z těchto faktů odvozovat další závěry. Samotný výpočet je vlastně dedukcí z předložených faktů s využitím pravidel. Typickým rysem logického programování je jeho deklarativní charakter, programátor v drtivé většině případů specifikuje „co“ (se má počítat), nikoliv „jak“ (se má počítat). Pro úspěšné zvládnutí tohoto cvičení není nutné znát inferenční mechanismus PROLOGu, to jest mechanismus, kterým PROLOG dokáže nalézt odpovědi k daným cílům. Na inferenční mechanismus PROLOGu se zatím můžeme dívat jako na „černou skříňku“. K úspěšnému zvládnutí cvičení plně postačuje znalost deklarativní sémantiky programu a pojmu korektní odpověď.

Programy v jazyku PROLOG se skládají z výrazů, které tvoří faktapravidla. Zvláštní výrazy, které nejsou přímou součástí programů, jsou cíle, někdy nazývané dotazy. Programy v PROLOGu slouží k vyjádření (popisu) naší znalostní báze (to jest programy píšeme v roli „programátorů“), pomocí cílů aktivujeme výpočet (cíle zadáváme v roli „uživatelů“ vytvořeného programu).

Nejjednoduššími výrazy programu v jazyku PROLOG jsou fakta. Fakta vyjadřují relaci mezi objekty (elementy, individui), přitom objekty jsou označovány pomocí termů. Relace může být n-ární. Unární relaci se obvykle říká vlastnost, binární relaci lze interpretovat jako vztah dvou objektů, ternární relaci jako vztah tří objektů a tak dále. Fakta jsou zapisována ve tvaru

relační_symbol(term_1, term_2, ..., term_n).

POZOR! Mezi relačním symbolem (někdy též zvaným predikát) a levou závorkou „(“ nesmí být mezera ani znak nový řádek. Na ostatních místech jsou mezery povoleny. Termy se v PROLOGu skládají z proměnných, konstant (atomů, objektů) a funkčních symbolů (někdy též funktorů) a jsou zapisovány standardním způsobem. PROLOG rozlišuje proměnné od symbolů pomocí velkých písmen -- proměnné musejí začínat velkým písmenem. Slovo, které začíná malým písmenem je buďto funkční symbol, relační symbol nebo konstanta (atom). Například X, Zvire či BLAH jsou proměnné, kdežto x, zvireblah nikoliv. V tomto cvičení si vystačíme pouze s jednoduchými termy -- buďto pouze proměnnými nebo konstantami (atomy).

Pro ukázku si uveďme jednoduchou databázi faktů.

 %% unarni predikat ,,byti savcem''
 savec(kocka).
 savec(pes).
 savec(mys).
 
 %% binarni predikat ,,X lovi Y''
 lovi(kocka,ptak).
 lovi(pes,mys).
 lovi(kocka,mys).
 lovi(kocka,ryba).
 lovi(ptak,mys).

Fakta sama o sobě již tvoří jednoduchý logický program. Předchozí fakta (řádky začínající znakem „%“ jsou komentáře) lze interpretovat například tak, že „kočka, pes a myš jsou savci“, „kočka loví ptáky“, „pes loví myši“ a tak dále. Toto je ale pouze jedna z mnoha interpretací předchozího programu. Pro nás je ale zajímavá z toho pohledu, že je to naše „zamýšlená interpretace“.

Dalším typem výrazu v PROLOGu je dotaz, neboli cíl. Dotaz má tvar

?- formule_1, formule_2, ..., formule_k.

Dotaz lze chápat jako konjunkci jednotlivých (atomických) formulí. Po vložení dotazu PROLOG spustí inferenční mechanismus a snaží se najít odpověď na dotaz. Odpověď je buďto nalezena nebo nikoliv, interpret se rovněž může dostat do nekonečného cyklu. V dalším si zatím vystačíme se zjednodušující představou, že PROLOG nám na zadaný dotaz odpoví vždy všemi korektními odpověďmi (to obecně neplatí, jak uvidíme na dalších přednáškách a cvičeních).

Interpret PROLOGu je možné spustit několikerým způsobem. Nejjednodušší, ale nejméně pohodlné, je spustit program swipl, poté do něj načíst program v PROLOGu a zadat konkrétní dotaz. Druhou možností je použít textový editor GNU Emacs, v jednom bufferu editovat zdrojový soubor a v druhém bufferu pružně zadávat dotazy. Pro uživatele GNU Emacsu přikládám konfigurační soubor, který umožňuje jednoduše pracovat s interpretem SWI-Prolog přímo v editoru, viz ukázku. Obsah přiloženého souboru stačí vložit do uživatelského konfiguračního souboru editoru Emacs (soubor se jménem .emacs a nachází ve vašem domovském adresáři -- pokud tento soubor nemáte doposud vytvořen, můžete jej vytvořit prostým zkopírováním přiloženého konfiguračního souboru). K opětovnému načtení programu do interpretu lze použít klávesu F8. Pokud používáte interpret bez editoru GNU Emacs, zdrojový kód programu do něj načtete pomocí zabudovaného predikátu consult/1. Viz ukázku.

 $ swipl
 Welcome to SWI-Prolog (Version 3.3.0)
 For help, use ?- help(Topic). or ?- apropos(Word).
 ?- consult('soubor.prolog').
 % soubor.prolog compiled 0.00 sec, 7,116 bytes
 Yes
 ?- 

Programy v jazyku PROLOG mívají obvykle příponu „.pl“, jelikož je však přípona „.pl“ používána převážně pro programy v jazyku PERL, budeme používat alternativní příponu „.prolog“. Předchozí databázi faktů naleznete v souboru sample.prolog. Spusťte interpret PROLOGu a načtěte do něj tento program.

Nyní můžete zkusit zadat následující cíl.

 ?- lovi(Zvire,mys), savec(Zvire).

Výše uvedený cíl lze vzhladem k našemu zamýšlenénu významu programu interpretovat jako dotaz: „Který savec loví myši?“ PROLOG má několik možností jako na tento dotaz odpovědět, z databáze faktů vyplývá, že tuto podmínku splňuje Zvire=kocka a také Zvire=pes. Pokud má PROLOG víc možností jak odpovědět, nabídne uživateli postupně všechny odpovědi. Pokud je uživatel s odpovědí spokojen, může stiskem Enter inferenční mechanismus přerušit, pokud chce zobrazit další odpověď, může stisknout klávesu „;“. Viz ukázku odpovědi na dotaz.

 ?- lovi(Zvire,mys), savec(Zvire).
 Zvire = pes ;
 Zvire = kocka ;
 No
 ?-

Odpověď „No“ znamená, že na daný dotaz neexistuje žádná další odpověď.

Posledním typem výrazů v PROLOGu jsou pravidla. Každé pravidlo se skládá z hlavytěla oddělených dvojicí znaků „:-“. Hlavu tvoří jedna (atomická) formule, tělo je tvořeno konjunkcí (atomických) formulí. Viz příklady pravidel.

 lovi_mysi(Lovec) :- lovi(Lovec,mys).
 savec_loveny_kockou(X) :- lovi(kocka,X), savec(X).
 lovi_a_je_loven(X) :- lovi(X,_), lovi(_,X).
 lovi_sam_sebe(X) :- lovi(X,X).

V předchozích pravidlech byla využita speciální anonymní proměnná „_“. Interprety PROLOGu zacházejí s anonymní proměnnou speciálním způsobem: anonymní proměnná není nikdy vázána na žádnou hodnotu. Neformálně řečeno, na obsahu (vazbě) anonymní proměnné „nezáleží“. Každý výskyt anonymní proměnné v pravidle (nebo v cíli) si lze představit jako výskyt nové proměnné, která se v daném pravidle (cíli) nikde jinde nevyskytuje. V důsledku se tedy nelze nijak odkazovat na hodnotu navázanou na tuto proměnnou -- na vazbě proměnné skutečně nezáleží. Účel anonymní proměnné (to jest označení „libovolné hodnoty“) si nejlépe uvědomíme, pokud nahradíme předchozí definici pravidla lovi_a_je_loven(X) následovně:

 lovi_a_je_loven(X) :- lovi(X,Y), lovi(Z,X).

Pokud nyní načteme kód do interpretu PROLOGu, získáme hlášení

 $ swipl
 Welcome to SWI-Prolog (Version 3.3.0)
 For help, use ?- help(Topic). or ?- apropos(Word).
 ?- consult('soubor.prolog').
 Warning: (soubor.prolog:1):
         Singleton variables: [Y, Z]
 % soubor.prolog compiled 0.00 sec, 724 bytes
 Yes
 ?- 

To jest interpret nás varoval, že proměnné YZ se v klasuli vyskytují pouze jednou (tzv. singleton variable). Většina implementací PROLOGu v takovém případě vypisuje varovná hlášení, aby programátora upozornila na potenciální chyby způsobené „překlepy“. V podobných případech je vhodné používat anonymní proměnnou.

Úkol 1. Předchozí pravidla přidejte k databázi faktů a vyzkoušejte si jednoduché dotazy obsahující nově definované predikáty. Pokud jste se dostatečně seznámili s ovládáním interpretu PROLOGu, umíte formulovat cíle, zapisovat fakta a pravidla, můžete začít řešit následující úkoly.

2.  Databáze příbuzenských vztahů

V následujících úkolech budeme uvažovat jednoduchou databázi faktů zachycující hierarchii příbuzenských vztahů. Databázi lze najít v souboru genealogy.prolog. Tato databáze obsahuje fakta zapsaná pomocí binárních predikátů manzel/2, matka/2 a otec/2 definujících vztahy člověk X je manželem/otcem/matkou člověka Y. V databázi jsou dále použity dva unární predikáty muz/1 a zena/1 definující pohlaví dané osoby. Například tedy z části databáze

 manzel(jan,petra).
 matka(petra,dorotka).
 matka(petra,vojtech).
 otec(jan,vojtech).
 muz(vojtech).
 zena(petra).

lze vyčíst, že jan je manželem atomu petra. Dále, že petra je matkou atomů dorotkavojtech a tak dále. Uvědomte si prosím, že předchozí výřez z databáze nedefinuje, je-li například jan otcem atomu dorotka. Ačkoliv bychom to mohli intuitivně předpokládat, v této části databáze není tento fakt uveden.

V dalších příkladech budeme vytvářet různá pravidla pro klasifikaci příbuzenských vztahů. Abychom nemíchali originální databázi faktů s našimi výtvory, na začátku práce si otevřete nový soubor a napište do něj následující řádky.

 %% nacti databazi lidi
 :- consult('genealogy.prolog').
 
 %% X je rodic Y -- ukazka definice novych pravidel
 rodic(X,Y) :- otec(X,Y).
 rodic(X,Y) :- matka(X,Y).

Na druhém řádku je uveden dotaz, ve kterém jsou pomocí mimologického predikátu consult/1 načtena fakta ze souboru genealogy.prolog. Na dalších řádcích je pomocí dvou pravidel definován binární predikát „X je rodičem Y“. Vyzkoušejte si funkčnost předchozí definice uvedením cíle ?- rodic(X,Y). Další vytvořená pravidla můžete připisovat do tohoto souboru.

Úkol 2. Nejprve vyzkoušejte formulovat dotaz, kterým zjistíte, zda-li se v databázi vyskytuje osoba, která má definována obě dvě pohlaví. Dále vytvořte pravidla definující unární predikát provdana(X) a binární predikát partner(X,Y) určující, zda-li je daná žena provdaná a zda-li jsou dvě osoby partnery.

Úkol 3. Napište pravidla pro ternární predikát syn(X,Y,Z) zachycující, zda-li je „X synem matky Y a otce Z“. Analogicky definujte ternární predikáty dcera/3 a dite/3. Dále vyřešte tyto problémy.

Úkol 4. Podobně jako v předchozích příkladech vytvořte pravidla definující binární predikáty dedecek/2, babicka/2, vnuk/2, vnucka/2, teta/2 a stryc/2. Predikáty otestujte.

Úkol 5. Vytvořte pravidla pro další binární predikáty: tchan/2, tchyne/2, snacha/2, zet/2, svagr/2 a svagrova/2.

3.  Databáze koček

PROLOG a jeho inferenční mechanismus lze využít jako jednoduchý dotazovací jazyk. Definice faktů můžeme chápat podobně, jako jsou v relačních databázích chápány tabulky, dotazy nad daty uloženými v tabulkách jsou v PROLOGu reprezentovány vytvářením vhodných cílů, případně dalších pravidel.

Nyní budeme uvažovat databázi informací o vybraných kočičích plemenech, viz soubor cats.prolog. Základní informace o kočkách jsou reprezentovány jako fakta pomocí tří základních predikátů,

kocka(Jmeno,Velikost,Povaha,Hlucnost,Srst)
barvy(Jmeno,Barva)
barvy_oci(Jmeno,Barva)

Jméno kočky lze chápat v databázové terminologii jako primární klíč, to jest jednoznačný identifikátor každého plemene kočky. Vytvářením nových odvozovacích pravidel a vhodnými dotazy můžeme získávat informace z této databáze. Například pokud nadefinujeme predikát klidna/2 následovně

 klidna(X,Y) :- kocka(X,_,klidna,_,_), barvy_oci(X,Y).

a definujeme cíl

 ?- klidna(X,svetle_zelena).

získáme tím odpověď na dotaz: „Které klidné kočky mají světle zelené oči?“. V definici pravidla si všimněte použití anonymní proměnné „_“ (informace o hodnotách velikosti, hlučnosti, nebo barvě srsti v tomto případě nehrají roli). Následující příklady jsou zaměřeny na vytváření podobných dotazů.

Úkol 6. Z databáze zjistěte následující informace. Pomozte si vytvořením dodatečných pravidel. Jména koček, názvy vlastností, barev, etc., jsou v databázi bez diakritiky.

  1. Které kočky mají aktivní povahu?
  2. Jakou barvu srsti a očí může mít tonkinská kočka?
  3. Které dlouhosrsté kočky jsou malé?
  4. Které kočky jsou velké a tiché?
  5. V jakých barvách se vyskytují polodlouhosrsté kočky?
  6. Jak se jmenují polodlouhosrsté kočky?
  7. Které kočky mohou být bílé?

4.  Vytváření databáze faktů ze slovního popisu

Doposud jsme pracovali s již vytvořenými databázemi faktů. Nalezení samotné databáze faktů není věcí logického programování, ale spadá do jednotlivých problémových domén. Na druhou stranu, součástí každého logického programu je databáze faktů a odvozovací pravidla, které je potřeba umět vytvořit například na základě slovního popisu nějakého problému.

Při formalizaci faktů lze využít jednoduchého větného rozboru. V první fázi je dobré v popisu najít objekty -- atomy (obvykle podstatná jména) a jejich jejich závislosti. Dalším krokem je formulace vlastností atomů a jejich vzájemných vztahů (přídavná jména, slovesa).

Úkol 7. Přečtěte si následující ukázkový text. Podle textu vytvořte vhodnou databázi faktů, tak, aby bylo v databázi uloženo co možná nejvíce informací z tohoto textu. Pokud nebudou fakta vhodně formalizována, v dalším příkladu bude obtížné sestavovat některé dotazy.

Auta jsou dvoustopá vozidla, která jezdí buďto na benzin, na naftu nebo na plyn. Auta se řídí volantem. Motorky jsou jednostopá vozidla a jezdí na benzin. Motorky mají řídítka. Kola nemají motor, jsou jednostopá a mají řídítka. Pavel má kolo i auto. Mirek má motorku a auto. Petr má kolo. Vilém nemá žádný dopravní prostředek.

Úkol 8. Vyzkoušejte vytvořit následující dotazy.

  1. Která vozidla jezdí na benzin?
  2. Kteří lidé vlastní jednostopé dopravní prostředky?
  3. Kdo řídí svůj dopravní prostředek volantem?
  4. Existují některé jednostopé dopravní prostředky, které se řídí volantem?
  5. Které dopravní prostředky mají řídítka?

5.  Práce s velkými databázemi faktů

Všechny předchozí databáze faktů byly malé. Jejich velikost byla natolik přijatelná, že fakta v databázi byla svým rozsahem „mentálně uchopitelná“. Při řešení reálných problémů se však lze setkat s databázemi, které mají tisíce faktů (běžně i řádově více). Takto velké databáze si již nelze zapamatovat a snadno z nich nelze „zpaměti“ vyvozovat nějaké závěry. V těchto případech může pomoci nasazení logických programovacích jazyků. Formulací vhodných dotazů můžeme snadno a rychle najít požadované odpovědi, které bychom jinak hledali jen velmi těžce a zdlouhavě. Obecnost logických programů je navíc méně limitující než například relační databáze. Na druhou stranu, relační databáze mají daleko efektivněji implementován mechanismus hledání odpovědí na dotazy (samotné dotazy jsou však výrazně jednodušší než obecné PROLOGovské cíle).

V poslední části cvičení budeme pracovat s velkou databází faktů, která obsahuje přes čtyři tisíce záznamů. Jedná se o databázi nainstalovaných softwarových balíků obsahující informace o vzájemných vztazích balíků. Některé balíky například mohou být závislé na jiných nebo mohou být naopak s jinými balíky v konfliktu. Všechna tato fakta jsou zaznamenána v přiloženém souboru packages.prolog (141 kB). Struktura faktů v databázi je jednoduchá a zahrnuje jednak informace o balíku a jednak o jeho vztahu k ostatním balíkům, viz následující ukázku.

 package(gv,optional,text).
 depends(gv,gs).
 depends(gv,libc6).
 recommends(lyx,gv).

Ternární predikát package(X,Y,Z) slouží k definici faktu, že balík X má důležitost Y a je v sekci Z. V předchozí ukázce je definován fakt, že balík jménem gv má důležitost optional a nachází se v sekci text. Další predikáty jsou binární a mají jména conflicts/2, depends/2, provides/2, recommends/2 a replaces/2. Pomocí těchto predikátů jsou definovány vztahy mezi dvěma balíky. V předchozí ukázce je například balík gv závislý na balících gslibc6. Na druhou stranu balík lyx doporučuje nainstalovat balík gv.

Úkol 9. Vyzkoušejte si jednoduché dotazy nad databází balíků. Zjistěte, na kterých balících a z jakých sekcí je závislý balík jménem icewm. Naopak, zjistěte, které balíky jsou závislé na icewm. Zjistěte, které balíky zajišťují editor, použijte predikát provides/2. Poté, co si vyzkoušíte jednoduché dotazy, můžete přikročit k řešení dalších příkladů.

Úkol 10. Zjistěte, které balíky s důležitostí optional závisí na balíku jménem base_passwd. Dále zjistěte, které textové editory zajišťují rovněž www_browser. Zjistěte, které balíky jsou v konfliktu s balíky s důležitostí optional závisejícími na balíku perl.

Úkol 11. Vytvořte následující nová pravidla.

  1. Vytvořte pravidlo definující unární predikát webtool/1, který bude vyjadřovat, které balíky patří mezi webové nástroje (balíky jsou v sekci web). Vyzkoušejte nové pravidlo a zjistěte, které balíky do této sekce patří.
  2. Vytvořte pravidlo definující binární predikát neslucitelne/2. Predikát vyjadřuje, které balíky jsou vzájemně neslučitelné (to jest vzájemně se vylučují). Zjistěte které dvojice balíků mají tuto vlastnosti.
  3. Vytvořte pravidla definující unární predikát nutne/1. Predikát by měl vyjadřovat, které balíky jsou v systému nutné. Za nutné považujeme balíky s důležitostí requiredimportant.

6.  Nejmenší herbrandovský model

Na přednášce byla prezentována deklarativní sémantika logických programů jejímiž ústředními pojmy jsou herbrandovská struktura, herbrandovský model, nejmenší herbrandovský modelkorektní odpověď. Nalezení korektní odpovědi k zadanému dotazu je úzce spjato s nejmenším herbrandovským modelem.

Úkol 12. Pro následující program se pokuste najít minimální herbrandovský model. Využijte postupu uvedeného na přednášce.

 savec(kocka). savec(pes). savec(mys).
 lovi(kocka,ptak). lovi(pes,mys). lovi(kocka,mys).
 lovi(kocka,ryba). lovi(ptak,mys).
 lovi_mysi(Lovec) :- lovi(Lovec,mys).
 savec_loveny_kockou(X) :- lovi(kocka,X), savec(X).
 lovi_a_je_loven(X) :- lovi(X,Y), lovi(Y,X).
 lovi_sam_sebe(X) :- lovi(X,X).