Západočeská univerzita v Plzni Fakulta aplikovaných věd Katedra informatiky a výpočetní techniky. programu pro výuku programovacího jazyka Prolog

Za´padoˇceska´ univerzita v Plzni Fakulta aplikovanyćh vˇed Katedra informatiky a vy´poˇcetn´ı techniky

Bakal´ aˇ rsk´ a pr´ ace Vytvoˇ ren´ı v´ yukov´ eho programu pro v´ yuku programovac´ıho jazyka Prolog

Plzeˇ n 2014

Tomáˇs Cigler

Prohl´ aˇ sen´ı Prohlaˇsuji, ˇze jsem bakaláˇrskou práci vypracoval samostatnˇe a v´ yhradnˇe s pouˇzit´ım citovan´ ych pramen˚ u. V Plzni dne 27. ˇcervna 2014 Tomáˇs Cigler

Abstract Creation of learning program for Prolog learning This bachelor thesis deals with creation of simple learning program for novice programmers or even advanced ones, who want to explore the world of constraint logic programming. You will find here lots of practical examples, which should guide you to understand different way of programming. After reading this thesis, you should be able to write Prolog programs on your own.

Abstrakt Vytvoˇ ren´ı v´ yukov´ eho programu pro v´ yuku programovac´ıho jazyka Prolog Tato práce je zamˇeˇrena na zaˇc´ınaj´ıc´ı i pokroˇcilé programátory, kteˇr´ı chtˇej´ı z´ıskat povˇedom´ı o logickém pˇr´ıstupu k programován´ı. Najdeme zde spoustu praktick´ ych ukázek, které se jednoduch´ ym zp˚ usobem snaˇz´ı ukázat ˇctenáˇr˚ um moˇznosti pouˇzit´ı tohoto odliˇsného pˇr´ıstupu. Programátor by mˇel b´ yt po pˇreˇcten´ı práce schopen sám vytváˇret programy v jazyce Prolog a samostatnˇe ˇreˇsit obvyklé problémy souvisej´ıc´ı s logick´ ym programován´ım.

Obsah ´ 1 Uvod 2 Sezn´ amen´ı s jazykem Prolog 2.1 Co je Prolog? . . . . . . . . . 2.2 Motivace . . . . . . . . . . . . 2.3 V´ yvojové prostˇred´ı . . . . . . 2.3.1 Pˇrehled interpretátor˚ u 2.3.2 Pˇr´ıprava prostˇred´ı . . .

1

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

3 Zaˇ c´ın´ ame programovat 3.1 Základn´ı syntax a terminologie . . . . . . . 3.2 Vlastn´ı program a ukázkové pˇr´ıklady . . . . 3.2.1 Zápis kódu . . . . . . . . . . . . . . . ˇ y kód . . . . . . . . . . . . . . . 3.2.2 Cist´ 3.2.3 Naˇcten´ı programu a základn´ı dotazy 3.2.4 Promˇenné a pravidla v databázi . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

2 2 2 3 3 5

. . . . . .

6 6 8 8 9 10 11

ˇ 4 Cinnost interpret´ atoru a standardn´ı predik´ aty 4.1 Vyhodnocován´ı c´ıl˚ u. . . . . . . . . . . . . . . . 4.2 Jak funguje backtracking? . . . . . . . . . . . . 4.3 Unifikace . . . . . . . . . . . . . . . . . . . . . . ˇ ızen´ı backtrackingu . . . . . . . . . . . . . . . 4.4 R´ ˇ ızen´ı v pravidlech . . . . . . . . . . . . 4.4.1 R´ 4.5 Návratová hodnota . . . . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

13 13 14 15 16 18 19

5 Standard ISO Prolog 5.1 Operátory . . . . . . . . . . . . . . 5.1.1 Definice vlastn´ıch operátor˚ u 5.2 Problém symetrick´ ych relac´ı . . . . 5.2.1 Podm´ınka . . . . . . . . . . 5.2.2 Abstrakce . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

21 21 22 23 24 25

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

5.3 5.4 5.5 5.6

Vstup od uˇzivatele . . . . . Cyklus . . . . . . . . . . . . Rekurze . . . . . . . . . . . Seznamy . . . . . . . . . . . 5.6.1 Pˇridáván´ı prvk˚ u. . . 5.6.2 Zpracováván´ı prvk˚ u. ˇ ezce . . . . . . . . . . . 5.7 Retˇ 5.8 Práce se soubory . . . . . . ˇ ı. . . . . . . . . 5.8.1 Cten´ 5.8.2 Zápis . . . . . . . . . 5.8.3 Jin´ y zp˚ usob . . . . . 5.9 Moduly . . . . . . . . . . . ´ 5.10 Uprava nahrané databáze .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

26 27 28 29 29 30 31 33 33 36 36 38 39

6 V´ yvojov´ e prostˇ red´ı B-Prolog 6.1 Zmˇeny oproti standardu . . . . . . . . . . . . 6.1.1 Vlastn´ı programy . . . . . . . . . . . . 6.1.2 Komunikace s OS . . . . . . . . . . . . 6.1.3 Volán´ı predikát˚ u . . . . . . . . . . . . 6.1.4 Práce se seznamy . . . . . . . . . . . . 6.1.5 Cyklus, kolekce a formátován´ı v´ ystupu 6.1.6 Mód ladˇen´ı . . . . . . . . . . . . . . . 6.1.7 Globáln´ı promˇenné . . . . . . . . . . . 6.2 Propojen´ı s imperativn´ımi jazyky . . . . . . . 6.3 Propojen´ı s jazykem C . . . . . . . . . . . . . 6.3.1 Volán´ı C z Prologu . . . . . . . . . . . 6.3.2 Volán´ı Prologu z C . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

41 41 41 42 42 43 44 45 46 47 47 47 49

7 Z´ avˇ er

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

50

´ 1 Uvod Práce je c´ılena na skupinu zaˇc´ınaj´ıc´ıch i pokroˇcil´ ych programátor˚ u, kteˇr´ı chtˇej´ı z´ıskat zkuˇsenosti s pˇr´ıstupem k programován´ı logick´ ych u ´loh. Jedná se o základy logického programován´ı v jazyce Prolog, s rozˇs´ıˇren´ım o nadstandardn´ı moˇznosti implementace B-Prolog. Prostudován´ım jednotliv´ ych kapitol a pˇr´ıklad˚ u s nimi u ´zce spjat´ ych se ˇctenáˇr postupnˇe dozv´ı, jak s programován´ım zaˇc´ıt, co k tomu vˇse potˇrebuje a následuje pˇredstaven´ı celého procesu programován´ı. Pˇri ˇcten´ı by ˇctenáˇr nemˇel m´ıt pocit informaˇcn´ıho pˇresycen´ı, pˇresto je zachována informaˇcn´ı hodnota a jej´ı vzr˚ ustaj´ıc´ı trend. Prvn´ı kapitoly jsou urˇceny u ´pln´ ym zaˇcáteˇcn´ık˚ um a informace jsou podány jednoduˇse a pˇrirozenˇe. Metoda v´ yuky umoˇzn ˇuje zvolit si k práci i jin´ y interpretátor, neˇz byl k psan´ı a spouˇstˇen´ı program˚ u v´ yhradnˇe pouˇz´ıván. Velká ˇcást práce je realizována za pomoci standardn´ıch zápis˚ u Prologu s následn´ ym obohacen´ım o dalˇs´ı funkce B-Prologu. Závˇerem se ˇctenáˇr dozv´ı o pozitivech a negativech propojen´ı logického a imperativn´ıho programován´ı v jeden funkˇcn´ı celek a moˇznosti pouˇzit´ı ve velk´ ych projektech. Posledn´ı kapitoly kladou vyˇsˇs´ı nároky na znalosti klasického programován´ı v kombinaci se znalostmi z´ıskan´ ymi v pˇredchoz´ıch kapitolách této práce.

1

2 Seznámen´ı s jazykem Prolog 2.1

Co je Prolog?

Programovac´ı jazyk Prolog vznikl na zaˇcátku 70. let ve Francii. P. Roussel jej zaˇcal vyv´ıjet za u ´ˇcelem umoˇznˇen´ı komunikace ˇclovˇeka s poˇc´ıtaˇcem v pˇrirozeném jazyce. Prolog pracuje na bázi predikátové logiky prvn´ıho ˇrádu. Jednoduˇse ˇreˇceno, je to odvozován´ı poznatk˚ u na základˇe znám´ ych fakt˚ u a pravidel neboli vypl´ yván´ı. Modern´ı vysoko´ urovˇ nové jazyky (napˇr. Java) jsou imperativn´ı. Programy popisuj´ı algoritmus, kter´ ym se ˇreˇs´ı specifick´ y problém, a vyuˇz´ıvá se k tomu vˇetˇsinou proceduráln´ı programován´ı a objekty. Prolog je zkratka anglické vˇety Programming in logic“. Ta znaˇc´ı, ˇze se jedná o logické programován´ı. ” Definujeme pouze co se má vyhodnotit a neˇreˇs´ıme zp˚ usob, ˇc´ımˇz se Prolog ˇrad´ı do deklarativn´ıch programovac´ıch jazyk˚ u. Vnitˇrn´ı algoritmy vyhodnocován´ı dotaz˚ u (c´ıl˚ u) jsou pro nás skryté. T´ım je jazyk pˇr´ıvˇetivˇejˇs´ı i pro laiky, nebot’ nen´ı tˇreba znát architekturu a princip fungován´ı poˇc´ıtaˇce [8]. Pro snadnou orientaci v kódu je d˚ uleˇzité znát základy predikátové logiky. Programátor vytváˇr´ı posloupnost urˇcit´ ych v´ yrok˚ u (predikát˚ u), které dohromady v daném sledu a kontextu vytváˇrej´ı databázi pro reprezentaci znalost´ı. Jazyk je interpretovan´ y, ˇcili nemáme pˇredem urˇcen´ y postup ˇreˇsen´ı, ale zadáváme dotazy, které chceme vyhodnotit. K tomu interpretátor vyuˇz´ıvá rekurzi, unifikaci a backtracking (podrobnˇeji viz kapitola 4).

2.2

Motivace

Uˇz na u ´vod m˚ uˇzeme nam´ıtat, ˇze jazyk Prolog dnes nen´ı ve svˇetˇe rozˇs´ıˇren´ y a bude m´ıt malé vyuˇzit´ı. Rozhodnˇe jej nevyuˇzijeme pro sloˇzité matematické v´ ypoˇcty, vykreslován´ı grafiky a podobné v´ ypoˇcetnˇe nároˇcné akce, kde potˇrebujeme vytváˇret v´ ykonné algoritmy. Prolog má ale vlastnosti, d´ıky kter´ ym se v´ ybornˇe hod´ı na specifické u ´kony. Napˇr´ıklad jiˇz zmiˇ novaná komunikace se strojem v pˇrirozeném jazyce byla vyuˇzita v roce 2005 agenturou NASA ve vesm´ırné stanici. V systémech umˇelé inteligence naˇsel Prolog vyuˇzit´ı v nedávné dobˇe i pˇri programován´ı superpoˇc´ıtaˇce Watson od IBM. Stejnˇe d˚ uleˇzité jsou znalostn´ı báze, chytré“ vyhle” dáván´ı apod. [1] 2

Seznámen´ı s jazykem Prolog

Vývojové prostˇred´ı

Prolog pˇrináˇs´ı jin´ y pohled na programován´ı a pˇrechod z klasického pˇr´ıstupu m˚ uˇze b´ yt pro nˇekteré programátory v´ yzva. V Prologu se daj´ı napsat rychle jednoduché a efektivn´ı aplikace, které jsou kódovˇe transparentn´ı a tedy snadno udrˇzitelné, coˇz je vˇetˇsinou naˇs´ım c´ılem. V kombinaci s imperativn´ım jazykem, jako je Java nebo C, má Prolog jeˇstˇe mnohem vˇetˇs´ı potenciál. Nejprve si ˇrekneme, jak s programován´ım v Prologu vlastnˇe zaˇc´ıt.

2.3

V´ yvojov´ e prostˇ red´ı

U kaˇzdého vysoko´ urovˇ nového programovac´ıho jazyka potˇrebujeme software, kter´ y nám umoˇzn´ı spuˇstˇen´ı programu, aniˇz bychom museli znát niˇzˇs´ı programovac´ı jazyky. U kompilovan´ ych jazyk˚ u p´ıˇseme kód v námi zvoleném textovém editoru a následnˇe pouˇzijeme pˇrekladaˇc, kter´ y pˇreloˇz´ı náˇs program do mezikódu nebo strojového kódu. Jazyk Prolog je ale interpretovan´ y, proto potˇrebujeme vhodn´ y interpretátor. Prvn´ı intepretátor naprogramoval jiˇz zm´ıˇ nˇen´ y P. Roussel spoleˇcnˇe s A. Colmerauerem v roce 1972. Postupnˇe se rozˇsiˇrovaly implementace a kaˇzdá v sobˇe obsahovala trochu jinou sadu zabudovan´ ych predikát˚ u. Kv˚ uli pˇrenositelnosti Prologovsk´ ych program˚ u bylo nutné zavést pevn´ y standard. Návrh standardu sepsal v roce 1984 R. O’Keefe, pˇresto ho málokterá verze Prologu dodrˇzovala. V pr˚ ubˇehu let se standard upˇresˇ noval a v roce 1993 vyˇsla dalˇs´ı neoficiáln´ı sumarizace návrhu. V roce 1995 byl standard oficiálnˇe zaveden, ale aˇz v posledn´ıch nˇekolika letech je implementacemi v´ıce dodrˇzován [6]. Rozhran´ı kaˇzdého interpretátoru je odliˇsné, podporuje jiné zápisy a stejné predikáty mohou v r˚ uzn´ ych verz´ıch fungovat trochu jinak. Nás budou zaj´ımat pouze implementace podporuj´ıc´ı ISO Prolog. Záleˇz´ı také na platformˇe, na které budeme pracovat, tzn. zda bude implementace fungovat na systému Windows, Linux nebo Mac OS. V praxi budeme cht´ıt Prolog vyuˇz´ıt k efektivn´ımu ˇreˇsen´ı komplexnˇejˇs´ıch problém˚ u. R˚ uzné implementace se hod´ı na odliˇsné typy u ´loh.

2.3.1

Pˇ rehled interpret´ ator˚ u

K dispozici je celá ˇrada starˇs´ıch implementac´ı, které se neustále vyv´ıjej´ı. Vˇetˇsina z nich je vytvoˇrena na otevˇren´ ych licenc´ıch. Proto nen´ı nutné sahat pro zpoplatnˇené verze, jako je napˇr. SICStus Prolog, kter´ y je velice drah´ y. Na internetov´ ych diskuz´ıch a v ˇclánc´ıch najdeme uˇzivatelská doporuˇcen´ı a hodnocen´ı r˚ uzn´ ych implementac´ı. Pˇrehledné srovnán´ı sepsal C. Heng na sv´ ych 3



internetov´ ych stránkách [5]. Bohuˇzel pˇrehled jiˇz nen´ı aktuáln´ı, proto se pod´ıváme na kaˇzdou implementaci zvláˇst’. Nejzaj´ımavˇejˇs´ı jsou pro nás interpretátory s moˇznost´ı propojen´ı s jin´ ymi jazyky. To znamená, ˇze interpretátor dokáˇze pˇreloˇzit a provést kódovou sekvenci tˇechto jazyk˚ u. Ekvivalentnˇe m˚ uˇzeme v proceduráln´ım programu spolupracovat s interpretátorem, kter´ y zde m˚ uˇze vyˇreˇsit d´ılˇc´ı problém efektivnˇeji, neˇz p˚ uvodn´ı programovac´ı jazyk. • tuProlog – intepretátor je vytvoˇren pod licenc´ı GNU LGPL. Skládá se z minimalistického jádra, které zvládá základn´ı práci s Prologem a lze dále rozˇs´ıˇrit dalˇs´ımi sadami predikát˚ u. P˚ uvodnˇe byl vytvoˇren pro webové applety. V´ ysledné programy kompiluje do .JAR formátu, takˇze jsou spustitelné napˇr´ıˇc platformami s JVM1 . Dále existuje verze pro Android a .NET. S tˇemito jazyky je potom kompatibiln´ı. • Visual Prolog – podporuje pouze platformu Windows. Kombinuje logické, klasické i objektové programován´ı. Je kompatibiln´ı s jazyky C a C++ a m˚ uˇze pouˇz´ıvat funkce Win32. Prostˇred´ı podporuje i grafické vytváˇren´ı a u ´pravy formuláˇr˚ u a oken. Pro soukromé u ´ˇcely je Visual Prolog zdarma, komerˇcnˇe se m˚ uˇze vyuˇz´ıvat aˇz se zaplacenou licenc´ı. • Ciao Prolog – v základu plnˇe podporuje ISO standard, ale mohou se pˇridat pro kaˇzd´ y projekt rozˇsiˇruj´ıc´ı moduly. Posledn´ı verze je ze srpna roku 2011 a funguje na vˇsech nejpouˇz´ıvanˇejˇs´ıch platformách. Ciao Prolog se m˚ uˇze propojit s jazyky C i Java anebo s relaˇcn´ımi databázemi. Existuj´ı i moduly pro s´ıt’ovou komunikaci a webové aplikace. • C#Prolog – stále aktualizovaná verze pod licenc´ı GNU GPLv2. Podporuje jednoduché propojen´ı s jazykem C# a tedy i databázemi, se kter´ ymi tento jazyk dokáˇze pracovat. Má podporu pro formát XML a stále se rozˇsiˇruj´ıc´ı struktury JSON. Funguje na platformˇe Windows i Linux. • GNU Prolog – kromˇe standardu ISO obsahuje v´ıce neˇz 300 dalˇs´ıch zabudovan´ ych predikát˚ u. Podporuje ladˇen´ı a propojen´ı s jazykem C. Obsahuje optimalizovan´ y a rychl´ y kompilátor, kter´ y vytváˇr´ı jednoduché spouˇstˇec´ı soubory. Pracuje na vˇsech základn´ıch platformách a je vytvoˇren pod licenc´ı GNU LGPL. 1

Java Virtual Machine – virtu´ aln´ı prostˇred´ı, které umoˇzn ˇuje spustit programy kompilované do bin´ arn´ıho mezik´ odu jazyka Java

4



• SWI Prolog – nejvˇetˇs´ı projekt na volné GNU GPL licenci, kter´ y se vyv´ıj´ı jiˇz od roku 1987. Standard ISO Prolog je rozˇs´ıˇren o robustn´ı grafické rozhran´ı s moˇznost´ı ladˇen´ı program˚ u a pˇridán´ı rozˇsiˇruj´ıc´ıch bal´ıˇck˚ u. M˚ uˇzeme jej propojit s jazykem C a C++, databázemi, pˇr´ıpadnˇe nahrát hotovou základn´ı knihovnu pro rozpoznáván´ı pˇrirozeného jazyka apod. Samozˇrejmost´ı je podpora vˇsech nejpouˇz´ıvanˇejˇs´ıch platforem. • B-Prolog – implementace od spol. Afany Software, která také splˇ nuje standard ISO Prolog, dokáˇze obousmˇernˇe spolupracovat s jazyky C, C++ a Java a pro osobn´ı, nekomerˇcn´ı nebo akademické u ´ˇcely je zdarma. Podrobnˇeji si ji pˇredstav´ıme v kapitole 6.

2.3.2

Pˇ r´ıprava prostˇ red´ı

Kdyˇz uˇz máme povˇedom´ı o tom, co to Prolog vlastnˇe je a k ˇcemu jej m˚ uˇzeme vyuˇz´ıt, vybereme si vhodnou implementaci interpretátoru. Pro dalˇs´ı práci a ukázky budu po celou dobu vyuˇz´ıvat právˇe B-Prolog na systému Linux. Instalace interpretátoru je jednoduchá. Staˇc´ı z oficiáln´ıch webov´ ych stránek http://www.probp.com/download.html stáhnout nejnovˇejˇs´ı verzi pro naˇsi platformu, rozbalit do poˇzadovaného um´ıstˇen´ı pomoc´ı archivaˇcn´ıho programu a spustit bp.exe na platformˇe Windows, eventuálnˇe na Linuxu soubor bp v pˇr´ıkazové ˇra´dce. V obou pˇr´ıpadech pˇred sebou vid´ıme konzolovou aplikaci, která vyp´ıˇse na obrazovku (v mém pˇr´ıpadˇe): B-Prolog Version 8.1, All rights reserved, (C) Afany Software 1994-2014. | ?-

Pokud se Vám B-Prolog nezamlouvá, pro základy jazyka nen´ı d˚ uleˇzité, jakou implementaci si vyberete. Následuj´ıc´ı postupy by mˇely ve vˇsech implementac´ıch podporuj´ıc´ıch standard ISO Prolog fungovat totoˇznˇe.

5

3 Zaˇc´ınáme programovat Jelikoˇz B-Prolog plnˇe podporuje ˇceské znaky v sadˇe UTF-8, mohli bychom pouˇz´ıvat ˇceská slova vˇcetnˇe diakritiky. Z d˚ uvodu pˇrenositelnosti by ale bylo nejlepˇs´ı psát kód v angliˇctinˇe. Knihy zab´ yvaj´ıc´ı se v´ yukou jazyka Prolog se vyskytuj´ı pˇreváˇznˇe v anglickém jazyce, proto zde budu pro zmˇenu v ukázkov´ ych pˇr´ıkladech pouˇz´ıvat ˇceˇstinu, ale bez diakritiky. Prostˇred´ı nás nyn´ı vyz´ yvá k zápisu pˇr´ıkaz˚ u (anglicky prompt), je to vlastnˇe interaktivn´ı mód interpretátoru. Vˇetˇsina knih, návod˚ u na internetu i odborn´ ych ˇclánk˚ u t´ ykaj´ıc´ıch se v´ yuky programovac´ıho jazyka zaˇc´ıná stejnˇe – vypsat na standardn´ı v´ ystup (tedy vˇetˇsinou na obrazovku) text Hello world!“ ” neboli v pˇrekladu Ahoj, svˇete!“ Pod´ıváme se, jak se to dˇelá v Prologu: ” | ?- write(’Ahoj, svete!’). Ahoj, svete! yes

ˇ ıkali jsme si, ˇze Prolog vyhodnocuje dotazy v závislosti na predikátech R´ v databázi, kterou jsme ale zat´ım sami nevytvoˇrili. Predikát write je souˇcást´ı standardu ISO Prolog, kter´ y je v interpretátoru zabudován. V´ ypis textu Ahoj, svete!“ na obrazovku je u vyhodnocen´ı tohoto predikátu vlastnˇe ved” lejˇs´ı efekt. Slovo yes na konci znamená, ˇze byl c´ıl vyhodnocen u ´spˇeˇsnˇe. Pokud by se vyhodnocen´ı nepovedlo, interpretátor vyp´ıˇse no. At’ uˇz interpretátor vyhodnot´ı predikát u ´spˇeˇsnˇe ˇci ne´ uspˇeˇsnˇe, následuje opˇet interaktivn´ı mód, takˇze je na obrazovku vypsán prompt a ˇceká se na vstup od uˇzivatele. V´ yjimkou je zabudovan´ y predikát halt, kter´ y ukonˇc´ı práci interpretátoru. O dalˇs´ıch zabudovan´ ych predikátech si pov´ıme v kapitole 5.

3.1

Z´ akladn´ı syntax a terminologie

ˇ adek write(’Ahoj, svete!’). je z logiky term. Kaˇzd´ R´ y term je v Prologu ukonˇcen teˇckou. v tomto pˇr´ıpadˇe zastupuje dotaz (c´ıl), kter´ y chceme vyhodnotit. Termy se v Prologu dˇel´ı na konstanty (ˇc´ısla nebo atomy), promˇenné, struktury a pravidla. Struktura – ˇcást pˇred závorkou write se naz´ yvá hlava, pˇresnˇeji funktor, kter´ y mus´ı b´ yt obecnˇe atom. Uvnitˇr závorek je také atom ’Ahoj, svete!’, ale obecnˇe to m˚ uˇze b´ yt jak´ ykoliv jin´ y term. 6

Zaˇc´ınáme programovat

Základn´ı syntax a terminologie

Term˚ um uvnitˇr závorek se ˇr´ıká argumenty. Aˇz budeme pozdˇeji definovat vlastn´ı fakta, argument˚ u m˚ uˇze b´ yt libovoln´ y poˇcet a jsou oddˇelené ˇcárkou. Kdyˇz nepouˇzijeme ˇzádn´ y argument, vynecháme i závorky. Poˇcet argument˚ u se oznaˇcuje jako arita. Pokud mluv´ıme o konkrétn´ı struktuˇre, popisujeme ji zp˚ usobem – funktor/arita, konkrétnˇe write/1. Jestliˇze maj´ı struktury totoˇzn´ y funktor, ale odliˇsnou aritu, jsou také odliˇsné. Podle arity naz´ yváme struktury nulárn´ı (bez argument˚ u, taktéˇz naz´ yváme objekty), unárn´ı (1 argument), binárn´ı (2 argumenty) apod. Atom je jin´ ymi slovy urˇcit´ y bezkontextov´ y nápis“, neboli objekt. Zapi” sujeme jej tˇremi zp˚ usoby. 1) Mus´ı zaˇc´ınat mal´ ym p´ısmenem a jako dalˇs´ı znaky jsou kromˇe mal´ ych a velk´ ych p´ısmen povoleny pouze ˇc´ıslice a podtrˇz´ıtka. 2) Libovoln´ y ˇretˇezec uzavˇren´ y v jednoduch´ ych uvozovkách, kde m˚ uˇzeme pouˇz´ıvat i speciáln´ı znaky (napˇr. ’Ahoj, svete!’). 3) Jeden (nebo posloupnost) z povolen´ ych speciáln´ıch znak˚ u (+ - * / apod.). Dále si nˇekteré z nich ukáˇzeme. ˇ ıslo m˚ C´ uˇze b´ yt celé (integer) nebo s plovouc´ı desetinnou ˇca´rkou a nen´ı omezené velikost´ı. Integer m˚ uˇzeme zapisovat v des´ıtkové (567), osmiˇckové (0o123), hexadecimáln´ı (0xC2A) i binárn´ı (0b011) soustavˇe. Desetinné ˇc´ıslo zapisujeme pouze v des´ıtkové soustavˇe a pouˇz´ıváme desetinnou teˇcku. Zápisy mohou vypadat následovnˇe: 5.33 -5.33 5.33E2 5.33E-5 kde E je exponent. Zápis 5. nebo .33 nen´ı povolen. Promˇ enn´ a se vˇzdy zapisuje s poˇcáteˇcn´ım velk´ ym p´ısmenem nebo podtrˇz´ıtkem a mohou následovat dalˇs´ı znaky. M˚ uˇzeme pouˇz´ıt i ˇc´ıslice. Pro jednoduché programy pouˇz´ıváme bˇeˇznˇe jednop´ısmenné názvy, u sloˇzitˇejˇs´ıch bychom mˇeli pojmenovávat promˇenné dle kontextu, abychom se v programu vyznali. Pokud je promˇenná zapsána pouze podtrˇz´ıtkem, ˇr´ıkáme, ˇze je anonymn´ı. Interpretátor ji pˇriˇrad´ı hodnotu, ale po vyhodnocen´ı ji nezmiˇ nuje, ani s n´ı nem˚ uˇzeme dále pracovat. Promˇenné se dosazuj´ı do struktur, které chceme urˇcit abstraktnˇe. Pouˇz´ıvaj´ı se m´ısto konkrétn´ıch objekt˚ u. Seznam se chová obdobnˇe jako v jazyce LISP – kaˇzd´ y seznam má hlavu (prvn´ı prvek) a tˇelo (orig. tail“), coˇz je zbytek seznamu. V´ yˇcet prvk˚ u se” znamu se zapisuje do hranat´ ych závorek – [a, b, c]. Hod´ı se pˇreváˇznˇe pro pˇr´ıpady, kdy potˇrebujeme pro nˇejak´ y funktor promˇenliv´ y poˇcet argument˚ u. Nepotˇrebujeme pˇredem vˇedˇet, kolik jich bude a se-

7


Vlastn´ı program a ukázkové pˇr´ıklady

znam se vˇzdy pˇrizp˚ usob´ı. M˚ uˇze obsahovat atomy, struktury nebo dalˇs´ı seznamy. Seznamy se mohou vnoˇrovat neomezenˇe: [prvek1, predikat(1, X), Y, [1,2,3]]

3.2

Vlastn´ı program a uk´ azkov´ e pˇ r´ıklady

Kdyˇz uˇz známe základn´ı syntax a stavebn´ı prvky Prologu, vytvoˇr´ıme si vlastn´ı program, kter´ ym definujeme relaˇcn´ı databázi. K tomu potˇrebujeme libovoln´ y textov´ y editor. Vytvoˇr´ıme si prázdn´ y textov´ y soubor, kter´ y si vhodnˇe pojmenujeme. Jako pˇr´ıpona souboru se dle konvenc´ı pouˇz´ıvá .pl. Ze zkuˇsenost´ı uˇzivatel˚ u interpretátoru SWI Prolog se ale v nˇekter´ ych pˇr´ıpadech m˚ uˇze pˇriˇrazen´ı této koncovky kr´ yt se zdrojov´ ymi soubory program˚ u jazyka Perl. V tˇechto pˇr´ıpadech tv˚ urci SWI Prologu v dokumentaci doporuˇcuj´ı pouˇz´ıvat pˇr´ıponu .pro [10].

3.2.1

Z´ apis k´ odu

Pro ukázku si navrhneme malou databázi domác´ıch mazl´ıˇck˚ u do souboru Mazlicci.pro: % Psi pes(alik). pes(rony). pes(besi). % Kocky kocka(micka). kocka(mnauka). kocka(andy). % Kralici kralik(ferda). kralik(matilda).

Programov´ y segment 3.1: Mazl´ıˇcci Pod´ıvejme se bl´ıˇze na v´ yznam tohoto kódu – definovali jsme si celkem 8 fakt˚ u pomoc´ı tˇrech unárn´ıch predikát˚ u pes, kocka a kralik. Predikáty nám urˇcuj´ı relace mezi termy. Jako je zapsán fakt v Prologu pes(rony), pˇrirozenˇe m˚ uˇzeme ˇr´ıct Rony je pes“. ” U námi vytvoˇren´ ych program˚ u velice záleˇz´ı na poˇrad´ı predikát˚ u. Prolog pˇri vyhodnocován´ı postupuje v databázi shora dol˚ u. V programu 3.1 rozd´ıl nepoznáme, ale kdyˇz zaˇcneme definovat sloˇzitˇejˇs´ı pravidla, na problém s poˇrad´ım zápisu m˚ uˇzeme narazit.

8



Na prvn´ım ˇra´dku znakem % zaˇc´ıná jednoˇrádkov´ y komentáˇr a aˇz do odˇra´dkován´ı m˚ uˇzeme psát jakékoliv znaky, které nebudou interpretátorem zpracovány. Pokud chceme psát komentáˇr na v´ıce ˇrádk˚ u, ohraniˇc´ıme text posloupnost´ı znak˚ u /* na zaˇca´tku komentáˇre a */ na konci. Za kaˇzd´ ym termem mus´ı b´ yt napsána teˇcka. Ta slouˇz´ı k odliˇsen´ı zaˇcátku zápisu dalˇs´ıho termu stejnˇe jako stˇredn´ıky v jazyce Java. Proto m˚ uˇzeme v programech zapsat v´ıce term˚ u na jednu ˇra´dku. Pokud budeme cht´ıt, tak m˚ uˇzeme na jednu ˇra´dku zapsat cel´ y program. U rozsáhl´ ych webov´ ych projekt˚ u se d´ıky této vlastnosti mohou vyuˇz´ıt tzv. minimizéry, které automaticky odstran´ı vˇsechna odˇra´dkován´ı a komentáˇre, takˇze se v´ ysledn´ y soubor o nˇeco zmenˇs´ı a rapidnˇe se zhorˇs´ı ˇcitelnost pro pˇr´ıpadné plagiátory.

3.2.2

ˇ y k´ Cist´ od

Komentáˇre jsou u rozsáhlejˇs´ıch program˚ u nutnost´ı. Nˇekteˇr´ı programátoˇri v praxi nam´ıtaj´ı, ˇze nejlepˇs´ım komentáˇrem má b´ yt kód samotn´ y. Vzhledem k transparentnosti Prologovsk´ ych zápis˚ u bychom se toho mohli drˇzet, ale jestliˇze p´ıˇseme sloˇzitˇejˇs´ı pravidla anebo nejasné ˇci na prvn´ı pohled nelogické zápisy, bylo by dobré komentáˇre pouˇz´ıvat. K pˇrehlednosti patˇr´ı i správné a logické pojmenován´ı predikát˚ u. Programátor si jistˇe m˚ uˇze uˇsetˇrit práci t´ım, ˇze bude definovat predikáty se zkratkovit´ ymi názvy. Komentáˇre také stoj´ı nˇejak´ y ˇcas. Pod´ıvejme se, jak m˚ uˇze vypadat nedbale zapsaná stejná databáze mazl´ıˇck˚ u. Pˇredstav´ıme si náˇs myˇslenkov´ y pochod: p(alik). k(micka). k(mnauka). p(rony). p(besi). k(andy). Takov´ y zápis se m˚ uˇze objevit právˇe v pˇr´ıpadech, kdy chceme Prologovsk´ y kód spojit s jin´ ym jazykem, protoˇze vnitˇrn´ı zápisy jsou pro koncového uˇzivatele neviditelné. Programátor definuje postupnˇe jednotlivá zv´ıˇrata, jak mu pˇrijdou pod ˇ ˇ adná jiná zat´ım neporuku. Reknˇ eme, ˇze p/1 pˇredstavuje psa a k/1 koˇcku. Z´ tˇrebuje a bude s nimi dále pracovat v Javˇe. Následnˇe bude cht´ıt do databáze pˇridávat jeˇstˇe král´ıky. Predikát k/1 ale jiˇz zab´ıraj´ı koˇcky. Pouˇzije kr/1 a pˇridá dalˇs´ı fakta. Takto m˚ uˇze vypadat v´ ysledn´ y kód: p(alik). k(micka). k(mnauka). p(rony). p(besi). k(andy). kr(ferda). kr(matilda).

Porovnejme nyn´ı zápis s programem 3.1. Ve v´ ysledku jistˇe budou oba programy fungovat. Poznáte ale programátor˚ uv zámˇer? Nejsp´ıˇs ano, ale bude to 9



trvat déle neˇz u ˇcistˇe napsaného kódu. Jistˇe si tv˚ urce takového programu uˇsetˇril pár minut ˇcasu, kter´ y by mu zabralo formátován´ı, delˇs´ı názvy nebo komentáˇre, ale sám bude za mˇes´ıc chv´ıli pˇrem´ yˇslet, co vlastnˇe znamená predikát kr/1, jestli to tˇreba nen´ı kˇreˇcek. ˇ adn´ Z´ y ˇcas nedbal´ ym pˇr´ıstupem neuˇsetˇr´ıme. Kdyby mˇeli v budoucnu na naˇsem projektu pracovat i extern´ı programátoˇri, takov´ y kód je nepˇrijateln´ y. V této práci se budu drˇzet obdobného zápisu jako v p˚ uvodn´ı ukázce.

3.2.3

Naˇ cten´ı programu a z´ akladn´ı dotazy

Pod´ıvejme se, jak s naˇs´ım programem m˚ uˇzeme pracovat. Kdyˇz spust´ıme interpretátor klasickou cestou, jeho vnitˇrn´ı databáze obsahuje pouze základn´ı zabudované predikáty. O naˇsem kódu se mus´ı nˇejak´ ym zp˚ usobem dozvˇedˇet“. ” K tomu slouˇz´ı predikát consult/1, jehoˇz argumentem je absolutn´ı ˇci relativn´ı cesta k naˇsemu souboru. Implementace B-Prolog 8.1 na Linuxu hledá soubory relativnˇe od um´ıstˇen´ı, ze kterého byla spuˇstˇena, tedy z aktuáln´ı otevˇrené cesty v Shellu. Soubor Mazlicci.pro je um´ıstˇen ve sloˇzce, ze které interpretátor spouˇst´ıme. Staˇc´ı tedy pouˇz´ıt následuj´ıc´ı zápis: |?- consult(’Mazlicci.pro’). consulting::Mazlicci.pro yes

Interpretátor potvrdil syntaktickou správnost a pˇridán´ı naˇsich term˚ u do databáze. Abychom vidˇeli, co vˇsechno interpretátor dosud nahrál do své vnitˇrn´ı databáze, pouˇzijeme predikát listing/0: | ?- listing. kralik(ferda). kralik(matilda). pes(alik). pes(rony). pes(besi). kocka(micka). kocka(mnauka). kocka(andy). yes

Jak je vidˇet, interpretátor seˇradil fakta tak, aby bylo vyhledáván´ı optimalizované. Pokud jednotlivé termy v souboru Mazlicci.pro zpˇreház´ıme, 10



intepretátor vyp´ıˇse na obrazovku informaci ** Warning: Predicate is not defined contiguously: pes/1 a obdobnˇe i pro ostatn´ı predikáty. Pˇresto jsou ve v´ ysledku vnitˇrnˇe seˇrazeny stejnˇe, jako u pˇredchoz´ıho programu. Pˇrehazuj´ı se mezi sebou ale pouze celé bloky spolu souvisej´ıc´ıch predikát˚ u. Stejná fakta nebo pravidla mezi sebou kv˚ uli závislosti na poˇrad´ı interpretátor prohodit samozˇrejmˇe nesm´ı. Na takové databázi si vyzkouˇs´ıme zadáván´ı c´ıl˚ u: | ?- kralik(ferda). yes | ?- pes(rony). yes | ?- pes(micka). no | ?- krecek(tony). *** Undefined procedure: krecek/1

Jestliˇze se ptáme, zda Ferda je král´ık a Rony je pes, intepretátor odpov´ı kladnˇe, jelikoˇz je to pˇr´ımo jeden ze znám´ ych fakt˚ u. Micka je ale koˇcka, proto odpovˇed’ na dotaz, zda je Micka pes, je negativn´ı. Stejnˇe tak by byla negativn´ı, kdyˇz jako argument jednoho z predikát˚ u pouˇzijeme v dotazu atom, kter´ y nen´ı mezi fakty uveden. Pˇri dotazu na kˇreˇcka interpretátor vyp´ıˇse v´ yjimku, protoˇze jsme v programu predikát krecek/1 nedefinovali.

3.2.4

Promˇ enn´ e a pravidla v datab´ azi

Na posledn´ım pˇr´ıkladu této ˇca´sti si vysvˇetl´ıme zápis promˇenn´ ych a pravidel. Pro tyto u ´ˇcely pouze rozˇs´ıˇr´ıme naˇsi databázi mazl´ıˇck˚ u. Definujeme nov´ y predikát zvire/1. M˚ uˇzeme tvrdit, ˇze vˇsechna jména v naˇs´ı databázi pˇredstavuj´ı jména zv´ıˇrat. Abychom nemuseli definovat pro kaˇzd´ y atom nov´ y fakt (napˇr´ıklad ˇze Al´ık je zv´ıˇre, Micka je zv´ıˇre atp.), pouˇzijeme promˇennou a zap´ıˇseme následuj´ıc´ı pravidlo: zvire(X) :- pes(X); kocka(X); kralik(X). Posloupnost znak˚ u :- má v´ yznam jako slovo kdyˇz“. Stˇredn´ık v tomto ” ˇ ˇ X je pes zápisu znamená disjunkci neboli nebo“. Cteme X je zv´ıˇre, KDYZ ” ” NEBO koˇcka NEBO král´ık“. Kromˇe disjunkce m˚ uˇzeme pouˇz´ıt jeˇstˇe logickou konjunkci a zároveˇ n“. K tomu slouˇz´ı operátor ,/2. Definujeme si pro ukázku ” nˇekolik nov´ ych pravidel. Pˇridáme do databáze jeˇstˇe kˇreˇcka a ˇrekneme, ˇze psi, koˇcky a kˇreˇcci ˇzerou maso a král´ıc´ı i kˇreˇcci ˇzerou b´ yl´ı. T´ım dokáˇzeme odliˇsit skupiny masoˇzravc˚ u, b´ yloˇzravc˚ u a vˇseˇzravc˚ u: 11



% Krecci krecek(tony). % Strava zere_maso(X) :- pes(X); kocka(X); krecek(X). zere_byli(X) :- kralik(X); krecek(X). % Potravinove strategie masozravec(X) :- zere_maso(X), not zere_byli(X). bylozravec(X) :- zere_byli(X), not zere_maso(X). vsezravec(X) :- zere_byli(X), zere_maso(X).

V pravidlech se objevuje nov´ y predikát not/1, kter´ y má v´ yznam negace predikátu. Pokud tedy interpretátor vyhodnot´ı u masoˇzravce predikát y, not vrát´ı opak a t´ım je nepravdivé celé pravidlo. zere byli/1 jako pravdiv´ O vyhodnocován´ı si bl´ıˇze pov´ıme v následuj´ıc´ı kapitole. Znovu naˇcteme zmˇenˇen´ y program a zkus´ıme si nˇekolika dotazy funkˇcnost nového ˇreˇsen´ı: | ?yes | ?no | ?no | ?yes

bylozravec(ferda). bylozravec(tony). masozravec(tony). vsezravec(tony).

Programov´ y segment 3.2: Potravinové strategie Abychom vyuˇzili celého potenciálu jazyka Prolog, je tˇreba pochopit základn´ı principy, jak interpretátor pracuje.

12

ˇ 4 Cinnost interpret´ atoru a standardn´ı predik´ aty Zkusme nyn´ı v aktuálnˇe nahraném programu Mazlicci.pro vyhodnotit c´ıl zvire(tony). Ze zápisu v´ıme, ˇze tony je kˇreˇcek a v reálném svˇetˇe je to jistˇe zv´ıˇre. Prolog nám ale odpov´ı negativnˇe. Prologovská databáze je totiˇz uzavˇren´ y svˇet, kde plat´ı právˇe taková pravidla a fakta, která si my sami definujeme. Proto aby interpretátor vˇedˇel, ˇze je kˇreˇcek zv´ıˇre, mus´ıme upravit zápis predikátu zvire/1 následovnˇe: zvire(X) :- kocka(X); pes(X); kralik(X); krecek(X). Tedy pˇridat kˇreˇcka do v´ yˇctu zv´ıˇrat. Potom je vˇse v poˇrádku. Mus´ıme si ale dávat velk´ y pozor na souvislosti. V u ´vodu jsme si ˇrekli, ˇze Prolog je zaloˇzen na vyhodnocován´ı c´ıl˚ u, rekurzi a backtrackingu (tzv. zpˇetném chodu).

4.1

Vyhodnocov´ an´ı c´ıl˚ u

Vrat’me se k prvn´ımu pˇr´ıkladu této práce. Abychom vypsali na obrazovku text Ahoj, svˇete!“, vyuˇzili jsme k tomu predikát write/1. Ten je navrˇzen ” tak, aby jeho vyhodnocen´ı vˇzdy uspˇelo. Vypsán´ı atomu uvnitˇr predikátu na obrazovku nen´ı pˇri vyhodnocen´ı c´ıle standardn´ı chován´ı, proto m˚ uˇzeme ˇr´ıci, ˇze je to vedlejˇs´ı efekt. Sami m˚ uˇzeme definovat takov´ y predikát, kter´ y pˇri vyhodnocen´ı vyp´ıˇse libovoln´ y text. K tomu vyuˇzijeme právˇe jiˇz existuj´ıc´ı predikát write/1. Vytvoˇr´ıme dva predikáty pozdrav, jeden nulárn´ı a jeden s argumentem, a predikát vypis pozdrav/0: pozdrav(Osloveni) :- write(’Ahoj ’), write(Osloveni). pozdrav :- pozdrav(lidi), nl, write(’(Obecny pozdrav)’). vypis_pozdrav :- write(’Prolog zdravi’), nl, pozdrav.

Interpretátor vyhodnocuje c´ıle vˇzdy zleva doprava a prohledává databázi shora dol˚ u. Proto záleˇz´ı na poˇrad´ı. Nejprve se kontroluje hlava predikátu, následnˇe arita a nakonec tˇelo. Na predikátu pozdrav si vyzkouˇs´ıme, jak funguje pˇretˇeˇzován´ı. Argumentem urˇc´ıme, koho v pozdravu oslov´ıme, pokud argument neuvedeme, osloven´ı bude obecnˇe lidi“: ”

13

ˇ Cinnost interpretátoru a standardn´ı predikáty

Jak funguje backtracking?

| ?- pozdrav(’Pepo’). Ahoj Pepo yes | ?- vypis_pozdrav. Prolog zdravi Ahoj lidi (Obecny pozdrav) yes

Bl´ıˇze se pod´ıváme na vyhodnocen´ı c´ıle vypis pozdrav/0. Interpretátor se ˇ ıkali jsme si, ˇze je to zabupokus´ı vyhodnotit write(’Prvni radka’). R´ dovan´ y predikát a je navrˇzen tak, ˇze jeho vyhodnocen´ı vˇzdy uspˇeje. Dalˇs´ı predikát v ˇrade je nl/0. To je také zabudovan´ y predikát, kter´ y na aktuáln´ı v´ ystup vyp´ıˇse novou ˇra´dku a také se ho vˇzdy podaˇr´ı vyhodnotit. Interpretátor pokraˇcuje volán´ım predikátu pozdrav/0. Ten jsme si sami definovali, takˇze interpretátor vyhodnot´ı jeho tˇelo a zjevnˇe uspˇeje. Vyhodnocován´ı se dokonˇc´ı v´ ypisem textu na novou ˇrádku. C´ıl byl vyhodncen v pˇr´ımém chodu a nebylo tˇreba ˇzádn´ ych dalˇs´ıch mechanism˚ u. Pod´ıvejme se ale, co se stane, kdyˇz uprav´ıme predikát pozdrav/0 takto: pozdrav :- pozdrav(lidi), fail. Vyhodnocen´ı zabudovaného predikátu fail/0 je vˇzdy ne´ uspˇeˇsné, tedy umˇele urˇc´ıme, ˇze predikát pozdrav/0 bude také vˇzdy ne´ uspˇeˇsn´ y. V okamˇzik, kdy nˇekter´ y z posloupnosti predikát˚ u je ne´ uspˇeˇsnˇe vyhodnocen, pˇricház´ı na ˇradu backtracking.

4.2

Jak funguje backtracking?

ˇ y v´ Cesk´ yznam slova backtracking je zpˇetn´ y chod“. Pokud má interpretátor ” na v´ ybˇer v´ıce moˇznost´ı vyhodnocen´ı predikátu, vˇzdy vybere prvn´ı moˇznost. Pokud se nepodaˇr´ı vyhodnotit tuto ˇcást posloupnosti, zkus´ı pouˇz´ıt jiné ˇreˇsen´ı, kdyˇz existuje. Jestliˇze dalˇs´ı ˇreˇsen´ı neexistuje, vrát´ı se od tohoto m´ısta o jeden krok zpˇet a postup opakuje – postupuje zprava doleva. Pˇridáme si jeˇstˇe jeden predikát pro pozdrav pro názornou ukázku backtrackingu. Nyn´ı máme definována tato pravidla:

14


Unifikace

pozdrav(Osloveni) :- write(’Ahoj ’), write(Osloveni). pozdrav :- pozdrav(lidi), nl, write(’(Obecny pozdrav)’), fail. % zachyceni chyby predikatu pozdrav/0 pozdrav :- write(’Pozdrav se nezdaril’). vypis_pozdrav :- write(’Prolog zdravi’), nl, pozdrav.

Pod´ıvejme se na vyhodnocen´ı predikátu vypis pozdrav/0: | ?- vypis_pozdrav. Prolog zdravi Ahoj lidi (Obecny pozdrav) Pozdrav se nezdaril yes

Aˇz do predikátu pozdrav/1 (vˇcetnˇe), kter´ y se volá z pozdrav/0, je vˇse stejné jako pˇri pˇredchoz´ım vyhodnocen´ı. Zmˇena je v následuj´ıc´ım predikátu fail/0, kter´ y neuspˇeje. Interpretátor se vrát´ı zpˇet na predikát write/1, kter´ y se pˇri zpˇetném chodu nikdy nevyhodnot´ı kladnˇe a znovu nic nevyp´ıˇse, stejnˇe jako nl/0. Dále interpretátor pokraˇcuje na pozdrav(lidi) a zkus´ı naj´ıt jinou moˇznost ˇreˇsen´ı nebo jinou definici takového pravidla. ˇ adná jiná moˇznost nen´ı, proto vystoup´ı zpˇet tam, odkud vyhodnocován´ı Z´ zaˇcalo, tedy do tˇela struktury vypis pozdrav/0. Interpretátor zkus´ı vyhledat dalˇs´ı v´ yskyty predikátu pozdrav/0. Ten nalezne a pˇri vyhodnocován´ı uspˇeje s v´ ypisem Pozdrav se nezdaril“ a celé vyhodnocen´ı je u ´spˇeˇsné, proto je ” koneˇcná odpovˇed’ yes. Abychom mohli pokroˇcit dále, vysvˇetl´ıme si nejd˚ uleˇzitˇejˇs´ı funkci interpretátoru – unifikaci.

4.3

Unifikace

Pouˇz´ıvá se pˇri vyhodnocován´ı c´ıle s promˇenn´ ymi. Ukáˇzeme si to konkrétnˇe na programu Mazlicci.pro. Budeme cht´ıt napˇr´ıklad vidˇet jména zv´ıˇrat v databázi. Pouˇzijeme následuj´ıc´ı dotaz: zvire(Zvire). Zvire = micka ?

Programov´ y segment 4.1: Pouˇzit´ı promˇenné

15


ˇ ızen´ı backtrackingu R´

Vˇsimnˇeme si pouˇzit´ı promˇenné Zvire. Ta zastupuje mezi argumenty (nyn´ı je pouze jeden) konkrétn´ı atom. V naˇsem pˇr´ıpadˇe je promˇenná v dotazu nepˇriˇrazená – nemá ˇza´dnou v´ ychoz´ı hodnotu. Zde zafunguje právˇe proces unifikace. Je to jin´ ymi slovy pˇriˇrazen´ı do prázdné promˇenné tak, aby byly dva termy shodné. Slouˇz´ı pˇri vyhledáván´ı predikátu v databázi Prologu [2]. Interpretátor prohledává databázi shora dol˚ u a hledá predikát zvire s aritou 1. Ten máme definovan´ y pouze jednou jako pravidlo, jehoˇz hlava je zvire(X). Aby byly predikáty shodné, pˇriˇrad´ı se promˇenné Zvire prázdná promˇenná X. Následnˇe se vyhodnocuje tˇelo pravidla zleva doprava. Prvn´ı je uveden predikát kocka(X). Promˇenná X stále nemá ˇza´dnou hodnotu a hledá se predikát kocka/1 v databázi shora dol˚ u. Prvn´ı je nalezen fakt kocka(micka) a aby byl shodn´ y s kocka(X), mus´ı platit X = micka. Je to pouze fakt, proto vyhodnocen´ı uspˇeje a kladná odpovˇed’ se vrac´ı zpˇet do tˇela predikátu zvire/1. ˇ adné dalˇs´ı predikáty jiˇz vyhodnocovat nemus´ıme (ty jsou za stˇredn´ıkem, Z´ tedy volitelné), proto i celé pravidlo uspˇeje. ˇ adné dalˇs´ı návaznosti Nyn´ı jiˇz máme pˇriˇrazen´ı Zvire = X = micka. Z´ u c´ıle zvire(Zvire) nebyly, c´ıl je tedy vyhodnocen cel´ y. Pokud jsme s v´ ysledkem spokojeni, potvrd´ıme klávesou enter, interpretátor odpov´ı yes a jsme zpˇet v interaktivn´ım uˇzivatelském reˇzimu. My se ale s takovou odpovˇed´ı nespokoj´ıme a pod´ıváme se na to, jak ˇr´ıdit backtracking.

4.4


Vrat’me se zpˇet k ukázce kódu 4.1. Ze zápisu v´ıme, ˇze predikát zvire/1 jistˇe splˇ nuje v´ıce mazl´ıˇck˚ u v databázi definované programem 3.1. Pro nalezen´ı dalˇs´ı moˇznosti pouˇzijeme stˇredn´ık a potvrd´ıme klávesou enter. Pˇriˇrazen´ı promˇenné se v pr˚ ubˇehu celého procesu zmˇen´ı na mnauka a znovu se vyp´ıˇse. V praxi to vypadá takto: zvire(Zvire). Zvire = micka ?; Zvire = mnauka ?; Zvire = andy ?; Zvire = alik ?

Samozˇrejmˇe se postupnˇe vyp´ıˇsou vˇsechna jména zv´ıˇrat. Vypadá to jednoduˇse, ale v interpretátoru je pod t´ım skryt ponˇekud sloˇzitˇejˇs´ı proces.

16



Stˇredn´ıkem ˇrekneme interpretátoru, ˇze posledn´ı pˇriˇrazen´ı do promˇenné, tedy micka, nen´ı správné a t´ım zaˇr´ıd´ıme, ˇze posledn´ı vyhodnocen´ y predikát v ˇradˇe neuspˇeje. Konkrétnˇe to byl predikát kocka(micka). Proces se vrát´ı opˇet aˇz do tˇela pravidla s hlavou zvire(X) s t´ım, ˇze promˇenná X je nyn´ı opˇet nepˇriˇrazena, a pokouˇs´ı se naj´ıt dalˇs´ı v´ yskyt predikátu kocka/1. Ten nalezne, uspˇeje, pˇriˇrad´ı promˇennou Zvire = X = mnauka a vyp´ıˇse. Po tˇret´ım opakován´ı jiˇz nenalezne ani dalˇs´ı predikát kocka/1, ale stále v tˇele následuje za stˇredn´ıkem volitelná podm´ınka pes(X), kterou se povede vyhodnotit. Takto m˚ uˇzeme proj´ıt vˇsechna zv´ıˇrata a u posledn´ıho v´ yskytu interpretátor automaticky vyhodnocován´ı ukonˇc´ı s kladnou odpovˇed´ı. Promˇennou m˚ uˇzeme pˇred volán´ım jeˇstˇe pˇriˇradit. To b´ yvá nˇekdy zdrojem chyb v programu. Poloˇz´ıme napˇr´ıklad takov´ yto dotaz: | ?- X = tony, zvire(X). X = tony yes

Vyhodnocen´ı je stejné, ale do pravidla jiˇz vstupuje definovaná promˇenná, proto se unifikuje odpov´ıdaj´ıc´ı promˇenná v jeho tˇele. Stejnˇe pro tento pˇr´ıpad funguje i dotaz zvire(tony). Kdyˇz budeme cht´ıt zjistit, která zv´ıˇrata jsou b´ yloˇzravci, pouˇzijeme následuj´ıc´ı dotaz: bylozravec(Zvire). Zvire = ferda ?; Zvire = matilda ?; no

Abychom vidˇeli, jak interpretátor postupuje, potˇrebujeme se pod´ıvat, jak je definován predikát bylozravec/1. Z tˇela se vyhodnocuj´ı jeˇstˇe predikáty zere byli/1 a zere maso/1: bylozravec(X) :- zere_byli(X), not zere_maso(X). zere_maso(X) :- pes(X); kocka(X); krecek(X). zere_byli(X) :- kralik(X); krecek(X).

Vyhodnocován´ı prob´ıhá totoˇznˇe s pˇredchoz´ım pˇr´ıkladem. Jelikoˇz jsou pravidla sloˇzitˇejˇs´ı, interpretátor dopˇredu nev´ı, jestli je matilda posledn´ı moˇznost a jeˇstˇe ˇceká na interakci od uˇzivatele. Chceme-li vyvolat dalˇs´ı backtracking, c´ıl se jiˇz vyhodnotit nepovede a dostaneme negativn´ı odpovˇed’. 17


4.4.1


ˇ ızen´ı v pravidlech R´

Backtracking je pro nás velice uˇziteˇcn´ y, ale nˇekdy nám dokáˇze pˇridˇelat vrásky. Proto potˇrebujeme m´ıt moˇznost jej nˇejak´ ym zp˚ usobem kontrolovat i pˇri deˇ finován´ı pravidel. Reknˇeme, ˇze vˇsechna zv´ıˇrata maj´ı srst, aˇz na Besi, která je naháˇc. Definujeme následuj´ıc´ı pravidla: % Vlastnosti ma_srst(besi) :- fail. ma_srst(X) :- zvire(X).

Kdyˇz naˇcteme program do databáze a zadáme c´ıl ma_srst(besi), dostaneme pˇresto kladnou odpovˇed’. To zapˇr´ıˇcinil proces zpˇetného chodu, kter´ y po ne´ uspˇechu unifikoval c´ıl s následuj´ıc´ım predikátem ma srst/1, jehoˇz tˇelo Besi splˇ nuje. Pro zabránˇen´ı backtrackingu vyuˇzijeme predikát !/0 nazvan´ y cut neboli volnˇe pˇreloˇzeno ˇrez“. S v´ yhodou jej vyuˇzijeme jeˇstˇe v následuj´ıc´ı ˇcásti pro ” ˇ pouˇzijeme definován´ı poˇcetn´ıch funkc´ı, ale i v mnoha dalˇs´ıch pˇr´ıpadech. Rez následovnˇe: ma_srst(besi) :- !, fail. ma_srst(X) :- zvire(X).

Pro konkrétn´ı dotazy nyn´ı interpretátor reaguje správnˇe: | ?- ma_srst(besi). no | ?- ma_srst(micka). yes

Zápisu !, fail se ˇr´ıká cut with failure“. Bohuˇzel ani takové oˇsetˇren´ı ” nefunguje ve vˇsech pˇr´ıpadech správnˇe. Poloˇzme obecn´ y dotaz kdo má srst?“: ” | ?- ma_srst(X). no

Negativn´ı vyhodnocen´ı nastane proto, ˇze interpretátor unifikuje promˇennou X jako prvn´ı s atomem besi, kter´ y skonˇc´ı s chybou a zpˇetn´ y chod jsme ˇrezem zakázali. Lepˇs´ı pˇr´ıstup je takov´ y, jak´ y jsme si jiˇz ukázali u potravinov´ ych strategi´ı. Definujeme si nov´ y predikát nahac/1 a budeme tvrdit, ˇze srst má zv´ıˇre, které nen´ı naháˇc. Takto bude vypadat upravená ˇcást:

18


Návratová hodnota

% Vlastnosti nahac(besi). ma_srst(X) :- zvire(X), \+ nahac(X).

Nyn´ı kdyˇz zkus´ıme vyhodnotit c´ıl ma_srst(X), dostaneme správné v´ ysledky. V kódu vid´ıme nov´ y predikát (operátor) \+/1. Ten má stejnou funkci jako not, kter´ y jsme si jiˇz vysvˇetlovali v pˇr´ıkladu 3.2.

4.5

N´ avratov´ a hodnota

Jako napˇr. v jazyce C máme funkce, které nám vracej´ı po proveden´ı hodnotu daného typu (chybov´ y kód apod.), m˚ uˇzeme podobnˇe z´ıskat návratovou hodnotu z vyhodnocen´ı predikátu. Pˇridáme si dva nové predikáty do programu Mazlicci.pro: dlouhe_usi(X) :- kralik(X). dlouhe_usi(rony). dlouhe_usi(alik). vzhled_zvirete(Zvire, chlupate) :- ma_srst(Zvire). vzhled_zvirete(Zvire, bez_srsti) :- nahac(Zvire). vzhled_zvirete(Zvire, usate) :- dlouhe_usi(Zvire).

Pˇri definován´ı predikátu nem˚ uˇzeme nijak explicitnˇe urˇcit návratovou hodnotu, proto je predikát binárn´ı a návratovou hodnotu pˇredstavuje druh´ y argument. Nyn´ı program opˇet naˇcteme a vyzkouˇs´ıme funkˇcnost. Kdyˇz chceme vˇedˇet, jak vypadá Matilda, poloˇz´ıme dotaz t´ımto zp˚ usobem: | ?- vzhled_zvirete(matilda, X). X = chlupate ?; X = usate ? yes

S takto definovan´ ym predikátem také m˚ uˇzeme zadat poˇzadovanou návratovou hodnotu a ptát se na vyhovuj´ıc´ı zv´ıˇrata. Takové chován´ı nám umoˇzn ˇuje backtracking spoleˇcnˇe s unifikac´ı. Jsou to procesy, které v Prologu funguj´ı automaticky vˇsude a nemus´ıme je popisovat ˇza´dn´ ym algoritmem, jak bychom to museli udˇelat v jazyce Java. Návratové hodnoty vyuˇzijeme hojnˇe napˇr. pˇri definován´ı matematick´ ych operac´ı jako napˇr´ıklad porovnáván´ı dvou hodnot: vetsi_cislo(Vetsi, Mensi, Vetsi) :- Vetsi > Mensi, !. vetsi_cislo(_, Vetsi, Vetsi).

19


Návratová hodnota

Tento pˇr´ıklad bude fungovat správnˇe. Jako tˇret´ı argument zadáme v dotazu nedefinovanou promˇennou, do které je pˇredáno vˇetˇs´ı ˇc´ıslo. Vˇsimnˇeme si pˇri této pˇr´ıleˇzitosti pouˇzit´ı ˇrezu. Kdybychom jej vynechali, m˚ uˇze nastat následuj´ıc´ı problém [2]: | ?- vetsi_cislo(8, 5, X). X = 8 ?; X = 5 yes

V programu se m˚ uˇzeme ptát i na konkrétnˇe definované ˇc´ıslo, které si mysl´ıme, ˇze je vˇetˇs´ı: | ?- vetsi_cislo(8, 5, 8). yes

Takto poloˇzen´ y dotaz bez promˇenn´ ych se u ´spˇeˇsnˇe unifikuje se zadan´ ym pravidlem vetsi_cislo(X, Y, X). V tomto pˇr´ıpadˇe by se ale interpretátor vyhodnotil kladnˇe i dotaz: | ?- vetsi_cislo(8, 5, 5). yes

Proto nebudeme spoléhat na postupné vyhodnocován´ı, protoˇze mohou nastat pˇr´ıpady, kdy se bude chovat program jinak, neˇz si pˇredstavujeme. Radˇeji budeme pˇridávat do pravidel kontroly nav´ıc, abychom zajistili robustnost ˇreˇsen´ı.

20

5 Standard ISO Prolog ˇ ast standardn´ıch zabudovan´ C´ ych predikát˚ u jsme si jiˇz pˇredstavili v pˇredchoz´ıch kapitolách, ale stále existuje hodnˇe zabudovan´ ych predikát˚ u, které by se nám v dalˇs´ı práci mohly hodit. Kompletn´ı seznam najdeme v pˇr´ıloze A knihy Prolog Programming in Depth od M. Covingtona [3]. Ukáˇzeme si zde na pˇr´ıkladech pro nás nejzaj´ımavˇejˇs´ı.

5.1

Oper´ atory

Kromˇe standardn´ıch struktur se v Prologu setkáme i s operátory. Ty se pouˇz´ıvaj´ı nejen pro numerické operace, ale m˚ uˇzeme si definovat i vlastn´ı s poˇzadovanou funkc´ı. Zavedeny jsou proto, abychom napˇr´ıklad operaci sˇc´ıtán´ı nemuseli zapisovat ve funktorové notaci, tedy +(4, 7), ale mohli jsme pouˇz´ıt pˇrirozenˇejˇs´ı zápis 4 + 7. Existuj´ı tˇri druhy operátor˚ u: Prefixov´ e – jejich zástupcem je predikát not/1. P´ıˇse se vˇzdy pˇred term, kter´ y pˇredstavuje jeho argument. Napˇr´ıklad not zere_maso(X). Infixov´ e – jsou vˇsechny binárn´ı operátory. Zapisuj´ı se mezi dva termy, které pˇredstavuj´ı jeho argumenty. Je to napˇr. oprátor disjunkce (,)/2 nebo matematick´ ych operac´ı jako sˇc´ıtán´ı (+)/2 apod. Postfixov´ e – p´ıˇs´ı se za argument, vyskytuj´ı se velice zˇr´ıdka. Zkusme nyn´ı vyhodnotit c´ıl 5+3.: | ?- 5+3. *** Undefined procedure: (+)/2

V´ yjimka nastane proto, ˇze operátor + nen´ı urˇcen pro unifikaci. Aby mohl interpretátor unifikaci pouˇz´ıt, naskytne se nám pouˇzit´ı promˇenné. Zkus´ıme poloˇzit dotaz takto: | ?- X = 5 + 3. X = 5+3 yes

Prolog v tomto pˇr´ıpadˇe zafungoval správnˇe, tedy pˇriˇradil do promˇenné X predikát (+)/2. Je to stené, jako bychom promˇenné pˇriˇradili napˇr. strukturu krecek(tony) nebo atom. Aby se vyhodnotily aritmetické operace, mus´ıme pouˇz´ıt zabudovan´ y infixov´ y operátor is/2, a to následovnˇe: 21

Standard ISO Prolog

Operátory

| ?- X is 5 + 3. X = 8 yes

Za is m˚ uˇzeme psát jakékoliv sloˇzité rovnice, bohuˇzel ale nem˚ uˇzeme pouˇz´ıvat nedefinované promˇenné. Jak aproximovat v´ ysledek sloˇzité rovnice s neznám´ ymi napsal M. Covington ve svém v´ yzkumu [4]. Nám bude prozat´ım staˇcit základn´ı práce s operátory.

5.1.1

Definice vlastn´ıch oper´ ator˚ u

Jak jiˇz bylo ˇreˇceno, je moˇzné definovat si vlastn´ı operátory. Pro ukázku si vytvoˇr´ıme do souboru Osoby.pro jednoduchou databázi osob, které jsou spoleˇcnˇe ve vztahu. V dalˇs´ıch kapitolách program rozˇs´ıˇr´ıme: % Muzi muz(jan). muz(roman). muz(ales). % Zeny zena(stela). zena(ema). zena(lucie). zena(petra). % Vztahy manzele(jan, stela). manzele(ales, petra). miluje(X, Y) :- manzele(X, Y).

V naˇsem jednoduchém svˇetˇe jsou tˇri muˇzi a ˇctyˇri ˇzeny, z toho dva páry jsou v manˇzelském vztahu. Tvrd´ıme, ˇze manˇzelé se navzájem miluj´ı. M˚ uˇzeme poloˇzit nˇekolik dotaz˚ u: | ?- miluje(jan, stela). yes | ?- miluje(X, petra). X = ales yes

Ovˇsem pˇrirozenˇejˇs´ı zápis by byl napˇr. jan miluje stela. To se dá zaˇr´ıdit pomoc´ı zabudovaného predikátu op/3. Ten se zapisuje ve tvaru: :- op(priorita, specifikator, nazev_operatoru) Priorita je celé ˇc´ıslo od nuly v´ yˇse a znamená, v jakém poˇrad´ı se bude opeˇ ım vyˇsˇs´ı ˇc´ıslo, t´ım niˇzˇs´ı priorita, tedy rátor vyhodnocovat pˇred ostatn´ımi. C´ 22

Standard ISO Prolog

Problém symetrických relac´ı

pozdˇejˇs´ı vyhodnocen´ı. Napˇr´ıklad násoben´ı má prioritu 400, sˇc´ıtán´ı a odˇc´ıtán´ı 500 apod. Specifikátor urˇcuje asociativitu a zda bude operátor prefixov´ y, infixov´ y nebo postfixov´ y. Asociativita urˇcuje, z jaké strany se zápisy vyhodnocuj´ı. Specifikátor se skládá z urˇcené posloupnost znak˚ u (atom): Atom fx fy xfx xfy yfx xf yf

Notace prefixová prefixová infixová infixová infixová postfixová postfixová

Asociativita neasociativn´ı asociativn´ı zprava neasociativn´ı asociativn´ı zprava asociativn´ı zleva neasociativn´ı asociativn´ı zleva

Operátor miluje/2 definujeme bez asociativity jako infixovou notaci, protoˇze je to p˚ uvodnˇe binárn´ı predikát. Definovat funktor jako operátor mus´ıme pˇred jeho prvn´ım pouˇzit´ım v programu následovnˇe: ?- op(200, xfx, miluje). I v kódu mus´ı b´ yt na zaˇca´tku ˇra´dky zapsány znaky ?-, jimiˇz zaˇc´ıná v´ yzva v uˇzivatelském reˇzimu, event. znaky :-. Tomuto zápisu se ˇr´ıká direktiva [2]. Predikát miluje/2 m˚ uˇzeme pouˇz´ıvat dále libovolnˇe i ve funktorovém zápisu.

5.2

Probl´ em symetrick´ ych relac´ı

Zkus´ıme zadat dotaz za pomoci operátoru a ukáˇzeme si nedostatek v aktua´ln´ım programu: | ?- ales miluje X. X = petra yes | ?- stela miluje X. no

Odpovˇed’ na druh´ y dotaz je negativn´ı, protoˇze jsme definovali tˇelo pravidla miluje pouze jednostrannˇe. Aby pravidlo platilo symetricky, definujeme nov´ y predikát chot/2 a uprav´ıme pravidlo následuj´ıc´ım zp˚ usobem: 23

Standard ISO Prolog


chot(X, Y) :- manzele(X, Y); manzele(Y, X). miluje(X, Y) :- chot(X, Y).

S touto symetrickou realc´ı bude Prolog vyhodnocovat pˇredchoz´ı dotazy správnˇe. Pokud ale poloˇz´ıme obecn´ y dotaz chot(X, Y)., lidé se pˇri backtrackingu budou opakovat. | ?- chot(X, Y). X = jan Y = stela ?; X = ales Y = petra ?; X = stela Y = jan ?; X = petra Y = ales yes

Tento problém se objevuje u kaˇzdé symetrické relace. Vhodné ˇreˇsen´ı m˚ uˇze b´ yt v r˚ uzn´ ych pˇr´ıpadech individuáln´ı a neexistuje ˇza´dné univerzáln´ı pravidlo. V naˇsem pˇr´ıpadˇe staˇc´ı ˇr´ıci, ˇze symetrické ˇreˇsen´ı chceme hledat pouze tehdy, kdyˇz neexistuje ˇreˇsen´ı p˚ uvodn´ı. K tomu pouˇzijeme nov´ y zápis – podm´ınku.

5.2.1

Podm´ınka

Uprav´ıme predikát chot následuj´ıc´ım zp˚ usobem: chot(X, Y) :- \+ manzele(X, Y) -> manzele(Y, X) ; manzele(X, Y). Zápis predikat1 -> predikat2 ; predikat3 je podm´ınka if“ jak ji ” známe z jin´ ych programovac´ıch jazyk˚ u. Prvn´ı se vyhodnot´ı predikat1, pokud uspˇeje, zavolá se predikat2, v opaˇcném pˇr´ıpadˇe se zavolá predikat3 – ten je ale v zápisu nepovinn´ y. Pokud neuspˇeje predikat2, jako dalˇs´ı se predikat3 vyhodnocovat nebude kv˚ uli závislosti implikace -> [2]. Ani ted’ bohuˇzel nen´ı ˇreˇsen´ı ideáln´ı pro vˇsechny pˇr´ıpady. Pod´ıvejme se na následuj´ıc´ı dotazy: | ?- Y = ales, X miluje Y. Y = ales X = petra yes | ?- X miluje Y, Y = ales. no

24

Standard ISO Prolog


Dalˇs´ı problém je symetriˇcnost u dotazu X miluje Y., jelikoˇz je v´ yˇcet interpretován pouze jednostrannˇe, i kdyˇz chceme, aby v naˇsem programu byl tento vztah symetrick´ y. U deklarativn´ıho programován´ı nˇekdy nelze jednoduˇse pokr´ yt vˇsechny moˇznosti zadan´ ych dotaz˚ u, ale mˇeli bychom se soustˇredit hlavnˇe na poˇzadovanou funkˇcnost.

5.2.2

Abstrakce

Na základˇe jiˇz existuj´ıc´ıch a dobˇre navrˇzen´ ych fakt˚ u a pravidel lze vˇzdy snadno pˇridat dalˇs´ı funkcionalitu. Pˇri psan´ı program˚ u za pomoci klasick´ ych i deklarativn´ıch jazyk˚ u bychom mˇeli udrˇzovat vhodnou m´ıru abstrakce. U Prologu abstrakci vyuˇzijeme pro zjednoduˇsen´ı sloˇzit´ ych pravidel. Kaˇzd´ y velk´ y problém se skládá z ˇcást´ı, ale záleˇz´ı na nás, jak drobné ˇca´sti se budou vyskytovat na jednom m´ıstˇe. Dekompozice by na vysoké u ´rovni nemˇela b´ yt u ´plná, ale mˇela by b´ yt rozvrˇzena do v´ıce ˇca´st´ı. To pˇrispˇeje ˇcitelnosti kódu a pˇr´ıpadnˇe následné pouˇzitelnosti ˇca´st´ı v jin´ ych pravidlech. Budeme se snaˇzit psát kód ˇcistˇe a jednoduˇse. Pro ukázku zadáme nová fakta: % Muzi muz(jan). muz(roman). muz(ales). muz(michal). muz(josef). % Zeny zena(stela). zena(ema). zena(lucie). zena(petra). % Vztahy manzele(jan, stela). manzele(roman, ema). manzele(ales, petra). milenci(roman, petra). milenci(lucie, ales).

25

Standard ISO Prolog

Vstup od uˇzivatele

A definujeme rozˇsiˇruj´ıc´ı pravidla vztah˚ u za pouˇzit´ı doposud z´ıskan´ ych znalost´ı: % Obecna pravidla chot(X, Y) :- \+ manzele(X, Y) -> manzele(Y, X) ; manzele(X, Y). v_mileneckem_vztahu(X, Y) :- \+ milenci(X, Y) -> milenci(Y, X); milenci(X, Y). ?- op(200, xfx, podvadi_s). X podvadi_s Y :- chot(X, Z), v_mileneckem_vztahu(X, Y). podvadejici(X) :- X podvadi_s _. ?- op(200, xfx, podvadi). X podvadi Chot :- chot(X, Chot), podvadejici(X). ?- op(200, xfx, miluje(X, Y) :miluje(X, Y) :miluje(X, Y) :-

miluje). milenci(X, Y) ; milenci(Y, X). manzele(X, Y), \+ podvadejici(X). manzele(Y, X), \+ podvadejici(X).

Pro program takto malého rozsahu je nyn´ı dekompozice dostateˇcná. Vˇsimnˇeme si pouˇzit´ı negac´ı, podm´ınek, anonymn´ı promˇenné, definic operátor˚ u atp. Je dobré pouˇz´ıvat korektnˇejˇs´ı názvy promˇenn´ ych neˇz jen X a Y. U binárn´ıch predikát˚ u to ale vˇetˇsinou nen´ı potˇreba, protoˇze je nám z kontextu zápisu jasné, co promˇenné znamenaj´ı.

5.3

Vstup od uˇ zivatele

Jestliˇze vytváˇr´ıme program, ve kterém chceme nechat uˇzivatele zadat libovoln´ y vstup, aniˇz by pro nˇej byly viditelné vnitˇrn´ı struktury, pouˇzijeme k tomu predikát read/1. Jeho argumentem je promˇenná, ve které bude následnˇe pˇriˇrazen zadan´ y vstup. Predikát si m˚ uˇzeme vyzkouˇset i v interaktivn´ım prostˇred´ı interpretátoru: | ?- read(X), write(’napsal(a) jste ’), write(X), nl. | ahoj. napsal(a) jste ahoj X = ahoj yes

26

Standard ISO Prolog

Cyklus

M˚ uˇzeme napsat pouze term dle konvenc´ı jazyka Prolog (viz 3.1) ukonˇcen´ y teˇckou a nakonec potvrd´ıme klávesou enter. Abychom mohli napsat libovoln´ y ˇretˇezec znak˚ u bez znalosti konvenc´ı, definujeme si v kapitole 5.7 predikát, kter´ y to bude umoˇzn ˇovat.

5.4

Cyklus

Cykly jako while nebo for, jak je známe z klasick´ ych programovac´ıch jazyk˚ u, v Prologu nenajdeme. K vytvoˇren´ı cyklu vyuˇzijeme backtracking a zabudovan´ y predikát repeat/0. Ten pˇri pˇr´ımém vyhodnocen´ı uspˇeje a pˇri zpˇetném chodu také. Pˇred tento predikát se backtrackingem jiˇz nedostaneme a program se chová, jako kdyby naˇsel dalˇs´ı moˇzné ˇreˇsen´ı. Po pouˇzit´ı repeat mus´ı existovat moˇznost, jak c´ıl splnit, nebo se bude cyklus opakovat donekoneˇcna. Vytvoˇr´ıme si pro ukázku jednoduch´ y kv´ız: kviz :- write(’Vitejte v pocetnim kvizu!’), nl, otazka. otazka :- write(’Kolik je 5+3?’), nl, repeat, read(X), odpoved(X). odpoved(8) :- write(’Spravna odpoved, dekuji’). odpoved(X) :- write(’Odpoved ’), write(X), write(’ je chybna. Zkuste to prosim znovu’), nl, fail.

Pro lepˇs´ı pochopen´ı se pod´ıváme rovnou na funkci tohoto programu: | ?- kviz Vitejte v pocetnim kvizu! Kolik je 5+3? | 6. Odpoved 6 je chybna. Zkuste to prosim znovu | 8. Spravna odpoved, dekuji yes

Startovac´ı bod je predikát kviz/0. Vid´ıme v´ ypis uv´ıtán´ı a volán´ı predikátu otazka/0. Ten v tˇele obsahuje samotnou otázku a predikát repeat/0, kter´ y pˇredstavuje cyklus pˇri backtrackingu. Následuje naˇcten´ı ze standardn´ıho vstupu do promˇenné X a kontrola tohoto vstupu. Otázka je jasnˇe poloˇzena a má právˇe jednu moˇznost odpovˇedi. Proto staˇc´ı napevno definovat atom správné odpovˇedi. V pˇr´ıpadˇe, ˇze je odpovˇed’ jiná, vyp´ıˇseme na obrazovku upozornˇen´ı a zajist´ıme nesplnˇen´ı c´ıle predikátem 27

Standard ISO Prolog

Rekurze

fail. T´ım nebude splnˇen ani c´ıl odpoved(X), read pˇri backtrackingu neuspˇeje, ale na predikátu repeat se backtracking zastav´ı a pokraˇcujeme opˇet pˇr´ım´ ym chodem od zadán´ı hodnoty.

5.5

Rekurze

Kv´ız v pˇredchoz´ım pˇr´ıkladu je velice primitivn´ı a zaslouˇz´ı si rozˇs´ıˇren´ı. Obohat´ıme jej o cyklus, kter´ y je ˇreˇsen za pomoci jednoduché rekurze, a pˇridáme dynamiˇcnost: kviz :write(’Vitejte v pocetnim kvizu! Ukoncite jej slovem ’’konec’’’), nl, otazka(1, 1). otazka(C1, C2) :write(’Kolik je ’), write(C1), write(’ + ’), write(C2), write(’?’), nl, repeat, read(X), Vysledek is (C1+C2), odpoved(X, Vysledek). odpoved(konec, _) :- write(’Dekuji za spolupraci, nashledanou.’). odpoved(X, Vysledek) :(X == Vysledek) -> write(’Spravna odpoved, dekuji’), nl, Z is ceiling(X*1.3), otazka(X, Z). odpoved(X, _) :write(’Odpoved ’), write(X), write(’ je chybna. Zkuste to prosim znovu’), nl, fail.

Jak kv´ız funguje si jiˇz urˇcitˇe dokáˇzeme pˇredstavit. Novinka je pˇrepoˇc´ıtáván´ı nov´ ych hodnot k seˇcten´ı. Predikátu odpoved/2 mus´ıme pˇredávat mimo tipovanou hodnotu i hodnotu správného v´ ysledku, jelikoˇz bude v kaˇzdém kole jiná. Nové hodnoty vypoˇcteme aˇz po napsán´ı správného v´ ysledku a voláme rekurzivnˇe predikát otazka/2 s tˇemito hodnotami. Kv´ız bude aktivn´ı aˇz do napsán´ı kl´ıˇcového slova konec“. Pˇri chybné ” odpovˇedi se bude vracet backtrackingem aˇz k predikátu repeat/0, pˇri správné se bude rekurzivnˇe pokládat nová otázka. Zaj´ımavˇejˇs´ım pˇr´ıkladem pro rekurzi je poˇc´ıtán´ı souˇctu vˇsech ˇc´ısel od nuly do daného ˇc´ısla. Rekurze spoˇc´ıvá v tom, ˇze pro poˇzadovanou sumu do ˇc´ısla N mus´ıme spoˇc´ıtat souˇcet do ˇc´ısla N − 1 a k tomu ˇc´ıslo N pˇriˇc´ıst. Pokud je 28

Standard ISO Prolog

Seznamy

ˇc´ıslo N = 1, nic nepˇriˇc´ıtáme: suma_do(1, Vysledek) :- Vysledek is 1. suma_do(X, Vysledek) :C1 is X-1, suma_do(C1, C2), Vysledek is C2 + X, !.

Pokud bychom v druhém pravidle nepouˇzili ˇrez, umoˇznili bychom vyvolat zpˇetn´ y chod a interpretátor by rekurzivnˇe poˇc´ıtal záporná ˇc´ısla do nekoneˇcna.

5.6

Seznamy

Velice uˇziteˇcné jsou v prologu seznamy, neboli listy. V kapitole 3.1 jsme si jiˇz nast´ınili moˇznosti pouˇzit´ı a zápis. Zde se pod´ıváme na problematiku podrobnˇeji vˇcetnˇe ukázkov´ ych pˇr´ıklad˚ u. Zápis v hranat´ ych závorkách [a, b, c] je zjednoduˇsen´ y zápis funktorové notace .(a, .(b, .(c, []))).

5.6.1

Pˇ rid´ av´ an´ı prvk˚ u

Jednou z moˇznost´ı, jak pˇridávat prvky do existuj´ıc´ıho seznamu je zápis [termy | seznam], kde svislá ˇca´ra zastupuje konstruktor seznamu. Nalevo je vypsan´ y libovoln´ y poˇcet term˚ u a napravo je seznam, do kterého se maj´ı termy pˇridat: | ?- List = [5, 10, 25], X is 25 - 3, Y = sqrt(121), List2 = [X, Y | List]. List = [5,10,25] X = 22 Y = sqrt(121) List2 = [22,sqrt(121),5,10,25] yes

Jestliˇze chceme pˇridat prvky na konec seznamu, m˚ uˇzeme pouˇz´ıt zabudovan´ y predikát append/3. Jako argumenty pˇrij´ımá v´ yhradnˇe listy. Mus´ıme si dávat pozor na pˇridán´ı jendoduchého atomu: | ?- X = 10, append([5, 10, 25], X, List). X = 10 List = [5,10,25|10] yes

Zápis [5,10,25|10] je sice dle konvenc´ı správn´ y, ale s takovou strukturou ˇ se dále ˇspatnˇe pracuje. Reˇsen´ım je vytvoˇren´ı jednoprvkového seznamu: 29

Standard ISO Prolog

Seznamy

| ?- X = 10, append([5, 10, 25], [X], List). X = 10 List = [5,10,25,10] yes

Predikát append vyuˇz´ıvá vnitˇrnˇe konstruktor seznamu, proto stejného v´ ysledku dosáhneme i zápisem: X = 10, List = [5, 10, 25|[X]].

5.6.2

Zpracov´ av´ an´ı prvk˚ u

Nejd˚ uleˇzitˇejˇs´ı ˇca´st práce s prvky seznamu je jejich zpracován´ı. Záleˇz´ı, na co seznam vyuˇz´ıváme, ale postup je vˇetˇsinou ekvivalentn´ı. Jak jiˇz bylo ˇreˇceno, m˚ uˇzeme provést dekompozici seznamu na prvn´ı prvek (hlavu) a zbytek seznamu. Vyuˇzijeme unifikaci s pravidlem, které jako argument pˇrij´ımá zápis [Hlava | Telo]. Jako nejjednoduˇsˇs´ı pˇr´ıklad si ukáˇzeme v´ ypis vˇsech prvk˚ u seznamu pod sebe: vypis_prvky_seznamu(S) :- vypis_prvky_ocislovane(S, 1). vypis_prvky_ocislovane([], _). vypis_prvky_ocislovane([H|T], N) :write(N), write(’. prvek = ’), write(H), nl, N1 is N+1, vypis_prvky_ocislovane(T, N1).

Vyzkouˇs´ıme si navrˇzené ˇreˇsen´ı: | ?- vypis_prvky([prvni,[1,2],3]). 1. prvek = prvni 2. prvek = [1,2] 3. prvek = 3 yes

Pokud bychom nedefinovali predikát vypis_prvky_ocislovane([], _), vyhodnocen´ı by se provedlo, ale odpovˇed’ by byla negativn´ı, jelikoˇz prázn´ y seznam by se s ˇza´dn´ ym predikátem jiˇz neunifikoval. Hlava seznamu je vˇzdy prvn´ı term neprázdného seznamu a zbytek neboli tˇelo p˚ uvodn´ıho seznamu je vˇzdy seznam bez prvn´ıho prvku, m˚ uˇze b´ yt tedy i prázdn´ y. Definujeme si s aktuáln´ımi znalostmi jednoduchou operaci sˇc´ıtán´ı ˇc´ıseln´ ych prvk˚ u seznamu. Vytvoˇr´ıme pro to prefixov´ y operátor +/1, kter´ y se nap´ıˇse pˇred seznam, kter´ y chceme seˇc´ıst.

30

ˇ ezce Retˇ

Standard ISO Prolog

V´ ysledek sˇc´ıtán´ı potˇrebujeme pˇredat do promˇenné, tak nám unárn´ı predikát staˇcit nebude. U numerické operace se nám naskytne pouˇzit´ı operátoru is/2, jenˇze ten takov´ y zp˚ usob sˇc´ıtán´ı nepodporuje. Zabudované predikáty nem˚ uˇzeme pˇredefinovat, proto si vytvoˇr´ıme vlastn´ı operátor je/2: ?-op(800, xfx, je). ?-op(200, fx, ’+’). X je +[X] :- !. X je +[H|T] :- Y je +T, X is Y + H.

Opˇet unifikujeme hlavu a tˇelo seznamu do zvláˇstn´ıch promˇenn´ ych. Dokud je v seznamu v´ıce neˇz jeden prvek, pouˇzijeme rekurzi. Posledn´ı prvek pˇriˇrad´ıme do promˇenné a pouˇzijeme ˇrez, protoˇze jiné moˇznosti souˇctu ˇc´ısel neexistuj´ı. V´ ysledky rekurzivn´ıch volán´ı pˇriˇc´ıtáme k souˇcasné hodnotˇe. T´ımto zp˚ usobem se pole seˇcte zprava doleva: | ?- X je +[-6,15+6,3*3,2**4,sqrt(36)]. X = 46.0 yes

Jak je vidˇet, v jednotliv´ ych prvc´ıch pole se mohou nacházet i sloˇzitˇejˇs´ı matematické v´ yrazy, které podporuje operátor is/2. Ekvivalentnˇe m˚ uˇzeme za pomoci nového prdikátu je definovat libovolné operace se seznamy nebo s rozˇs´ıˇrené matematické operace. Dalˇs´ı vyuˇzit´ı má seznam pˇri zápisu ˇretˇezc˚ u.

5.7

ˇ ezce Retˇ

Libovolné textové ˇretˇezce nejsou jenom obyˇcejné atomy, ale je to speciáln´ı posloupnost znak˚ u uvozená dvojit´ ymi uvozovkami. Jako v jazyce C se ˇretˇezec reprezentuje pomoc´ı pole (seznamu) jednotliv´ ych znak˚ u a kaˇzd´ y znak má urˇcen´ y sv˚ uj ˇc´ıseln´ y kód v ASCII tabulce: | ?- X = "Retezec" X = [82,101,116,101,122,101,99] yes

Dalˇs´ı uˇziteˇcen´ y zabudovan´ y predikát je name/2. Ten slouˇz´ı k pˇrevodu atomu na ˇretˇezec reprezentuj´ıc´ı jeho název a naopak. Smˇer pˇrevodu urˇc´ıme t´ım, do kterého z argument˚ u zadáme nepˇriˇrazenou promˇennou. M˚ uˇzeme ˇretˇezce i porovnávat: 31

ˇ ezce Retˇ

Standard ISO Prolog

| ?- name(’Retezec’, X). X = [82,101,116,101,122,101,99] yes | ?- name(X, [82,101,116,101,122,101,99]). X = ’Retezec’ yes | ?- name(’Retezec’, [82,101,116,101,122,101,99]). yes

S jeho pomoc´ı si vyrob´ıme predikát cti radku/1, kter´ y bude ˇc´ıst libovoln´ y text ze vstupu aˇz do odˇra´dkován´ı, bez nutnosti uvozovek nebo ukonˇcen´ı teˇckou. Vytvoˇr´ıme si proto nov´ y soubor Vstup.pro: cti_radku(X) :- cti_znak_rekurzivne([], List), name(X, List), !. cti_znak_rekurzivne(Stary_list, Novy_list) :get0(X), zpracuj_znak(X, Stary_list, Novy_list). % Odchyceni odradkovani v Linuxu zpracuj_znak(10, Stary_list, Stary_list). zpracuj_znak(X, Stary_list, Novy_list) :append(Stary_list, [X], L), cti_znak_rekurzivne(L, Novy_list).

Pro správnou funkci jsme vyuˇzili znalosti rekurze, ˇrezu i práce s listy. Vid´ıme nov´ y zabudovan´ y predikát get0/1, kter´ y ˇcte jeden libovoln´ y znak ze vstupu uˇzivatele. Predikát get/1 funguje velice podobnˇe, ale vyuˇz´ıt bychom jej nemohli, jelikoˇz ignoruje vˇsechny b´ılé znaky“ neboli anglicky whitespace“. ” ” Mezi nˇe se ˇrad´ı merezy, odsazen´ı a hlavnˇe odˇrádkován´ı, které potˇrebujeme odchytávat. Takto náˇs predikát funguje: | ?- cti_radku(X). Muzeme pouzit libovolne znaky jako treba: ’?:_-/\%"’ apod. X = ’Muzeme pouzit libovolne znaky jako treba: \’?:_-/\%"\’ apod.’ yes

Aby se z libovolného ˇretˇezce mohl stát atom, volán´ı name ho vloˇz´ı mezi jednoduché uvozovky. Na vˇsechny v´ yskyty tˇechto uvozovek uvnitˇr ˇretˇezce automaticky pouˇzije tzv. escape sekvenci. To je v tomto pˇr´ıpadˇe proces pˇridán´ı zpˇetného lom´ıtka pˇred kaˇzdou uvozovku.

32

Standard ISO Prolog

5.8

Práce se soubory

Pr´ ace se soubory

V Prologu m˚ uˇzeme m´ısto standardn´ıho vstupu a v´ ystupu definovat jednoduˇse konkrétn´ı soubory. Ty je moˇzné otevˇr´ıt pro ˇcten´ı nebo zápis.

5.8.1

ˇ Cten´ ı

Pro ˇcten´ı ze souboru vyuˇzijeme predikát see/1. T´ım urˇc´ıme, ˇze vˇsechny vstupn´ı operace budou pracovat právˇe s uveden´ ym souborem. Vytvoˇr´ıme zkuˇsebn´ı soubor test s obsahem: Zkusebni soubor se dvema radky

Abychom si vyzkouˇseli ˇcten´ı, pˇresmˇerujeme vstup na tento soubor a predikátem seeing/1 ovˇeˇr´ıme, jestli opravdu ze souboru interpretátor ˇcte [3]: | ?- see(’test’). yes | ?- seeing(’test’). yes

Pro jednoduchou ukázku, se souborem vytvoˇren´ ym v Linuxu, m˚ uˇzeme pouˇz´ıt jiˇz navrˇzen´ y a vyzkouˇsen´ y predikát cti radku/1: | ?- cti_radku(X). X = ’Zkusebni soubor’ yes

ˇ ı vstupu funguje jako fronta. Pˇredstavme si, ˇze máme otevˇren´ Cten´ y pomysln´ y pr˚ uchod“, kter´ ym pˇricházej´ı znaky. Nezáleˇz´ı na tom, jestli pocház´ı ” z klávesnice nebo ze souboru. Predikát get0 postupnˇe odebere prvn´ı v ˇradˇe pokaˇzdé, kdyˇz je zavolán. Jestliˇze je vstup standardn´ı a ˇzádné znaky nejsou ve frontˇe, ˇceká se na vstup z klávesnice ze strany uˇzivatele. Vstup ze souboru je ovˇsem koneˇcn´ y a pˇredem urˇcen´ y, takˇze mus´ıme konec souboru hl´ıdat. Jistˇe v´ıte, ˇze konec ˇra´dky v Unixovém systému je urˇcen´ y netisknuteln´ ym znakem s oznaˇcen´ım LF neboli anglicky Line Feed“. V systému Windows se ” pouˇz´ıvaj´ı dva znaky v poˇrad´ı CR+LF, kde CR znamená v angliˇctinˇe Carriage ” Return“.

33

Standard ISO Prolog

Práce se soubory

Tyto znaky pocház´ı jeˇstˇe z poˇca´tk˚ u komunikace. V tehdejˇs´ıch dobách se vypisovalo mechanicky a znak CR mˇel v´ yznam návratu tiskové hlavy (volnˇe pˇreloˇzeno návrat voz´ıku“) na zaˇca´tek ˇrádky. Znak LF mˇel za následek posun ” pap´ıru o ˇra´dek v´ yˇse. Jednoduˇse tak m˚ uˇzeme pˇridat k p˚ uvodn´ı kontrole konce ˇra´dky v Unixu i kontrolu na konec ˇra´dky v systému Windows. Dalˇs´ı souvisej´ıc´ı kontrola je kontrola na konec souboru. Zde pˇri pokusu o pˇreˇceten´ı dalˇs´ıho znaku dostaneme neexistuj´ıc´ı ASCII kód −1. Takto nyn´ı vypadaj´ı vˇsechny moˇznosti zpracován´ı pˇreˇcteného znaku: % Odchyceni odradkovani ve Windows zpracuj_znak(13, Stary_list, Stary_list) :- get0(_). % Odchyceni odradkovani v Linuxu zpracuj_znak(10, Stary_list, Stary_list). % Konec souboru zpracuj_znak(-1, Stary_list, Stary_list) :- !,fail. zpracuj_znak(X, Stary_list, Novy_list) :append(Stary_list, [X], L), cti_znak_rekurzivne(L, Novy_list).

Pokud bychomo chtˇeli podporovat jeˇstˇe nav´ıc platformu Mac OS, vyuˇz´ıvaj´ıc´ı pro odˇra´dkován´ı pouze CR, jiˇz by byly kontroly sloˇzitˇejˇs´ı. Kdyˇz z kontroln´ıho pravidla pro Windows odstran´ıme tˇelo, tedy pˇreˇcten´ı dalˇs´ıho znaku (u Windows následuje LF), bude program v Mac OS fungovat správnˇe na u ´kor platformy Windows, kde se bude jeˇstˇe vypisovat právˇe znak LF. S takto definovan´ ymi pravidly m˚ uˇzeme zavolat predikát cti_radku(X) opakovanˇe: | ?- cti_radku(X). X = ’Zkusebni soubor’ yes | ?- cti_radku(X). X = ’se dvema radky’ yes | ?- cti_radku(X). no

Je vidˇet, ˇze se volán´ım predikátu cti radku rekurzivnˇe pˇreˇcetly vˇsechny znaky aˇz do prvn´ıho v´ yskytu odˇra´dkován´ı, které jsme do v´ ypisu nezahrnuli. D´ıky dvˇema kontrolám funguje zápis ekvivalentnˇe i se soubory vytvoˇren´ ymi pod systémem Windows. Opakované volán´ı ˇcte dalˇs´ı znaky od posledn´ıho pˇreˇcteného. Na základˇe tˇechto znalost´ı jistˇe zvládneme vytvoˇrit predikát, 34

Standard ISO Prolog

Práce se soubory

kter´ y po ˇra´dc´ıch pˇreˇcte cel´ y soubor. To si ukáˇzeme dále v této kapitole. Kdyˇz nyn´ı pˇrip´ıˇseme do souboru dalˇs´ı ˇrádky a zkus´ıme znovu pˇreˇc´ıst dalˇs´ı ˇra´dku, nic se uˇz nevyp´ıˇse. Je to dáno t´ım, ˇze interpretátor B-Prolog soubor pˇri proveden´ı see naˇcte jednorázovˇe na vstup a s t´ımto vstupem m˚ uˇzeme dále libovolnˇe pracovat. Pokud chceme definovat opˇet standardn´ı vstup, nemus´ıme znát jeho pojmenován´ı, ale m˚ uˇzeme pouˇz´ıt predikát seen/0. | ?- seen. yes | ?- seeing(X). X = user yes

Za pomoci predikátu seeing jsme zjistili, ˇze standardn´ı vstup je pojmenován user. Nyn´ı si vytvoˇr´ıme nov´ y soubor pro program, kter´ y bude definovat jednoduchá pravidla pro práci se soubory. Nazveme si jej Soubory.pro a definujeme si predikát pro ˇcten´ı. Vyuˇzijeme pˇritom kód z programu Vstup.pro. Pˇredpokládejme, ˇze jsou soubory ve stejné sloˇzce, tak abychom ˇca´st nemuseli kop´ırovat, staˇc´ı pouˇz´ıt dobˇre znám´ y predikát consult: ?-consult(’Vstup.pro’). % opakujeme, dokud se dari vypisovat cti_soubor(Soubor) :see(Soubor), repeat, \+ vypis_radku, !, seen. vypis_radku :- cti_radku(X), write(X), nl.

V tˇele predikátu je pouˇzit jednoduch´ y cyklus. Nejprve zvol´ıme vstupn´ı soubor a pouˇzijeme zaráˇzku“ v podobˇe predikátu repeat. Pokaˇzdé, kdy se ” povede vypsat ˇra´dku, zaj´ıst´ıme negac´ı, aby pravidlo neuspˇelo. T´ım se pˇreˇcte dalˇs´ı ˇra´dka. Aˇz kdyˇz nen´ı co dál ˇc´ıst, vyhodnocen´ı je pozitivn´ı a dostaneme se k ˇrezu. Ten zde zajiˇst’uje jednoznaˇcnost v´ ysledku. Následuje pˇrepnut´ı zpˇet na standardn´ı vstup. Zkusme vypsat na obrazovku upraven´ y textov´ y soubor test: | ?- cti_soubor(test). Zkusebni soubor se dvema radky PS: jeste jeden radek. yes

35

Standard ISO Prolog

5.8.2

Práce se soubory

Z´ apis

Pˇri zápisu do souboru postupujeme podobnˇe jako pˇri ˇcten´ı. Také staˇc´ı pouze intepretátoru pˇresmˇerovat standardn´ı v´ ystup na náˇs soubor a m˚ uˇzeme pouˇz´ıvat predikáty jako pˇri klasickém vypisován´ı na obrazovku. Jako u ˇcten´ı jsou pro nás pro zápis d˚ uleˇzité tˇri predikáty tell/1, told/0 a telling/1 [3]. Jako ekvivalent k tell/1 je v nˇekter´ ych verz´ıch prologu predikát append/1, kter´ y umoˇzn´ı zápis na konec zvoleného souboru, zat´ımco tell/1 aktuáln´ı obsah pˇrep´ıˇse, nebo vytvoˇr´ı soubor nov´ y, pokud neexistuje [3]. Ukaˇzme si pouˇzit´ı v pravidlech: zapis_radku_do_souboru(Soubor, X) :tell(Soubor), write(X), nl, told. zapis_vstup_do_souboru(Soubor) :cti_radku(X), zapis_radku_do_souboru(Soubor, X).

Predikát zapis radku do souboru/2 pouze pˇresmˇeruje v´ ystup na poˇzadovan´ y soubor, zap´ıˇse text pˇredan´ y promˇennou X a pˇresmˇeruje zpˇet na standardn´ı v´ ystup. Predikát zapis vstup do souboru/1 rozˇsiˇruje stávaj´ıc´ı o moˇznost zadat text z klávesnice nebo z jiného souboru. Podobn´ ym postupem bychom mohli napˇr. upravit obsah vstupn´ıho souboru a po ˇra´dc´ıch jej opˇet uloˇzit do jiného souboru. B-Prolog bohuˇzel nepodporuje predikát append/1, kter´ y je pro práci se soubory velice uˇziteˇcn´ y. Naˇstˇest´ı mimo v´ yˇse jmenované zp˚ usoby existuje jeˇstˇe pˇr´ıstup, kter´ y ocen´ı sp´ıˇse pokroˇcilejˇs´ı programátoˇri, jelikoˇz je podobn´ y standard˚ um v jin´ ych jazyc´ıch.

5.8.3

Jin´ y zp˚ usob

Pro pokroˇcilejˇs´ı práci s proudem dat smˇeˇruj´ıc´ıch z/do souboru, pouˇzijeme zabudovan´ y predikát open/3 nebo open/4. Zápis vypadá následovnˇe: open(Soubor, Akce, Proud, Moznosti) kde Soubor pˇredstavuje soubor, se kter´ ym chceme pracovat, Akce urˇcuje, co chceme se souborem dˇelat. Máme moˇznosti read = ˇcten´ı, write = zápis nebo append = pˇridán´ı na konec souboru. Proud je v´ ystupn´ı promˇenná pˇredstavuj´ıc´ı pomysln´ y komunikaˇcn´ı kanál“ se souborem. Moznosti je seznam ” doplˇ nuj´ıc´ıch nastaven´ı. Tento argument m˚ uˇzeme vynechat. Mezi nejzaj´ımavˇejˇs´ı moˇznosti nastaven´ı patˇr´ı pˇrepnut´ı typu ˇcten´ı. Primárnˇe se pracuje s obsahem souboru jako s textem a ˇcten´ı ˇci zápis prob´ıhá po 36

Standard ISO Prolog

Práce se soubory

znac´ıch. M˚ uˇzeme pˇrepnout typ na binárn´ı soubor nastaven´ım type(binary) a poté jsou operace bitové. Dalˇs´ı moˇznost´ı je pojmenován´ı proudu (tzv. alias). K tomu pouˇzijeme libovoln´ y atom, pomoc´ı kterého m˚ uˇzeme proud pˇri dalˇs´ı práci identifikovat. Pojmenován´ı se urˇcuje predikátem alias(proud1). Ve standardu jsou definovány jeˇstˇe moˇznosti nastaven´ı chován´ı pˇri dosaˇzen´ı konce souboru pomoc´ı predikátu eof action/1. Nejzaj´ımavˇejˇs´ı nastaven´ı je eof_action(reset), d´ıky kterému se pokus´ı interpretátor po dosaˇzen´ı konce souboru znovu jej prohledat a zkontrolovat, zda je moˇzné ˇc´ıst jeˇstˇe dále, v pˇr´ıpadˇe ˇze by do souboru nˇekdo zapsal. Posledn´ı moˇznost´ı je umoˇznˇen´ı posouván´ı se v souboru dopˇredu nebo dozadu pomoc´ı predikátu reposition(true). Posouván´ı je ve v´ ychoz´ım nastaˇ ıdic´ı predikáty je moˇzné v seznamu zapsat v libovolném ven´ı deaktivováno. R´ poˇrad´ı i poˇctu. Abychom mohli pracovat s novˇe otevˇren´ ym proudem, jsou standardem urˇceny speciáln´ı predikáty: ˇ ı: Cten´ get_char(Proud, Znak) – ˇcten´ı jednoho znaku get_code(Proud, Kod) – ˇcten´ı numerického kódu znaku read_term(Proud, Term, Moznosti) a read(Proud, Term) – ˇcten´ı jednoho termu Zápis: put_char(Proud, Znak) – zápis jednoho znaku put_code(Proud, Kod) – zápis numerického kódu znaku write_term(Proud, Term, Moznosti) a write(Proud, Term) – zápis jednoho termu ym nastaPokud pouˇzijeme predikát set output/1 nebo set input/1, kter´ v´ıme aktuáln´ı proud ˇcten´ı/zápisu na náˇs novˇe otevˇren´ y, m˚ uˇzeme pouˇz´ıvat i predikáty read/1, write/1 a podobné, které nepotˇrebuj´ı jako argument tento proud [3]. Pro ukázku si m˚ uˇzeme zkusit jednoduch´ y zápis na konec naˇseho testovac´ıho souboru: | ?- open(test, append, Proud), set_output(Proud), write(’ahoj’), close(Proud). Proud = (stream)[10002] yes

37

Standard ISO Prolog

Moduly

Mus´ıme si dávat pozor také na d˚ usledné uzav´ırán´ı otevˇren´ ych proud˚ u pomoc´ı predikátu close/1. Pokud uzavˇreme proud, na kter´ y jsme pˇresmˇerovali vstup nebo v´ ystup, zruˇs´ı se i pˇresmˇerován´ı a je pouˇzit standardn´ı proud. Aktuálnˇe nastaven´ y proud zjist´ıme volán´ım predikátu current input/1 nebo current output/1. V´ yˇse zm´ınˇené predikáty tell, see apod. pouˇz´ıvaj´ı vnitˇrnˇe právˇe tyto konstrukce, jen jsou zapouzˇrené do pˇr´ıvˇetivˇejˇs´ı podoby, na u ´kor moˇznosti jejich u ´prav.

5.9

Moduly

Pozornost si zaslouˇz´ı i moduly, pˇrestoˇze interpretátor B-Prolog je v aktuáln´ı verzi nepodporuje. Modul je ekvivalent tˇr´ıdy v jazyce Java. Do modulu m˚ uˇzeme zapouzdˇrit predikáty, které spolu u ´zce souvis´ı a zpˇr´ıstupn´ıme veˇrejnˇe pouze ty, které chceme. Ukaˇzme si definici takového modulu, bohuˇzel bez moˇznosti praktického vyzkouˇsen´ı: ?- module(informace). ?- export([vypis_info/0]). ?- begin_module(informace). vypis_info :- write(’Nasleduji informace: ’), info(X), write(X), !. info(’Verejna informace’). info(’Tajna informace’). ?- end_module.

Pˇri definici záleˇz´ı na poˇrad´ı predikát˚ u. Prvn´ı mus´ıme definovat nov´ y modul direktivou module/1 a následuje seznam veˇrejnˇe pˇr´ıstupn´ ych predikát˚ u, kter´ y pˇredáme jako argument pˇri volán´ı export/1. Mezi direktivami begin module/1 a end module/0 definujeme libovoln´ y program, kde se mus´ı vyskytovat predikáty vypsané v direktivˇe export. Pokud chceme nyn´ı v jiném programu volat predikáty definované v urˇcitém modulu, mus´ı b´ yt modul v interpretátoru naˇcten´ y a v poˇzadovaném programu jej importujeme direktivou import/1. Direktivy jsou vˇzdy platné pouze v rámci jednoho souboru. Kdyˇz budeme cht´ıt zavolat neveˇrejn´ y predikát z nˇejakého modulu, je to také moˇzné za pomoci zápisu nazev_modulu:vnitrni_predikat. Pomoc´ı zápisu predikat @ jiny_modul ˇrekneme interpretátoru, ˇze chceme zavolat 38

´ Uprava nahrané databáze

Standard ISO Prolog

predikát predikat z modulu jiny_modul i v pˇr´ıpadˇe, ˇze bude predikat definován v aktuáln´ım programu [3]. Pˇredpokládejme naˇcten´ı programu, kde je importován modul informace definovan´ y v´ yˇse: | ?- vypis_info. Nasleduji informace: Verejna informace yes | ?- informace:info(X). X = ’Verejna informace’ ?; X = ’Tajna informace’ yes

Pˇri volán´ı predikátu info/1 bez definován´ı modulu by interpretátor skonˇcil s v´ yjimkou.

5.10

´ Uprava nahran´ e datab´ aze

V intepretátoru mˇen´ıme obsah databáze hojnˇe napˇr. v pr˚ ubˇehu testován´ı nového programu za pouˇzit´ı predikátu consult/1 ˇci reconsult/1. Kdyˇz po nˇekolika takto nahran´ ych programech vyp´ıˇseme obsah databáze volán´ım predikátu listing/0, zjist´ıme, ˇze velká spousta nepotˇrebn´ ych predikát˚ u z˚ ustává v databázi. Predikáty i pravidla zde z˚ ustávaj´ı do vypnut´ı interpretátoru. Po spuˇstˇen´ı interpretátoru m˚ uˇzeme do prázdné databáze pˇridat vlastn´ı predikáty za pomoci dobˇre známého volán´ı consult/1. Pokud ale nepˇredpokládáme velk´ y rozsah programu, staˇc´ı pouˇz´ıt jeden z predikát˚ u assert/1, asserta/1 nebo assertz/1. Jejich argumentem je libovoln´ y predikát nebo atom. Takto m˚ uˇzeme pˇridávat predikáty i k jiˇz nahranému programu. Predikáty assert a assertz pˇridávaj´ı fakta na konec, predikát asserta pˇridává na zaˇcátek. Jestliˇze chceme pˇridat v´ıce predikát˚ u najednou nebo zadávat pravidla, pouˇzijeme volán´ı consult(user). To m´ısto ze souboru naˇc´ıtá vstup z klávesnice a m˚ uˇzeme psát stejn´ ym zp˚ usobem, jako zapisujeme do souboru. V B-Prologu ukonˇc´ıme zadáván´ı kombinac´ı kláves ctrl + D. V pˇr´ıpadˇe, ˇze chceme fakta z databáze odstranit, pouˇzijeme predikát retract/1. Jako argument zap´ıˇseme predikát a prvn´ı v databázi, se kter´ ym se tento predikát unifikuje, bude z databáze vymazán. Pro vymazán´ı vˇsech odpov´ıdaj´ıc´ıch pouˇzijeme retractall/1. Pro vymazán´ı vˇsech definic konkrétn´ıho predikátu pouˇzijeme abolish(Funktor/Arita) [11]. Pozor na fakta a pravidla nahraná pomoc´ı predikátu consult. Na jejich 39

´ Uprava nahrané databáze

Standard ISO Prolog

smazán´ı nemáme dostateˇcná oprávnˇen´ı. Vyzkouˇs´ıme si budován´ı databáze v praxi: | ?- assert(pred(a)), assert(pred(b)), assert(pred(c) yes | ?- asserta(pred(d)). yes | ?- assert(pred(1, a)). yes | ?- listing. pred(d). pred(a). pred(b). pred(c). pred(1, a). yes | ?- retract(pred(X)). X = d ?; X = a ? yes | ?- listing. pred(b). pred(c). pred(1, a). yes | ?- abolish(pred/1). yes | ?- listing. pred(1, a). | ?- abolish. yes | ?- listing. yes

Pˇredoposledn´ı volán´ı predikátu abolish/0 maˇze vˇsechny námi definovaná fakta.

40

6 Vývojové prostˇred´ı B-Prolog V závˇeru se pod´ıváme podrobnˇeji na interpretátor B-Prolog. Hlavn´ım c´ılem je ukázat moˇznosti Prologu nejen jako interpretovaného jazyka, ale také jako nástroje pro ˇreˇsen´ı d´ılˇc´ıch problém˚ u ve formˇe samostatného spustitelného programu nebo jako souˇca´st programu napsaného v jiném jazyce. Jak se prostˇred´ı instaluje a spouˇst´ı jsme si jiˇz ˇrekli v kapitole 2.3.2. V´ıme, ˇze interpretátor vol´ı v´ ychoz´ı sloˇzku takovou, ze které byl z pˇr´ıkazové ˇra´dky pˇr´ıkazem spuˇstˇen. Pˇri spuˇstˇen´ı m˚ uˇzeme pouˇz´ıvat parametry. Nejzaj´ımavˇejˇs´ı je parametr -g "prikazy", kter´ y vykoná zadané pˇr´ıkazy (c´ıle) bezprostˇrednˇe po startu interpretátoru. Jestliˇze chceme provést pˇr´ıkaz jeˇstˇe pˇred startem, nap´ıˇseme na konec sledu pˇr´ıkaz˚ u predikát $bp_top_level, kter´ y inicializuje start interpretátoru aˇz po tˇechto u ´konech.

6.1

Zmˇ eny oproti standardu

B-Prolog z velké ˇcásti podporuje standard ISO Prolog. Nˇekdy ale nejsou funkce totoˇzné s navrhovan´ ymi poˇzadavky standardu. Obsahuje také velké mnoˇzstv´ı pˇridan´ ych predikát˚ u. Vˇsechny moˇznosti B-Prologu jsou sepsány v rozsáhlé pˇr´ıruˇcce pˇrikládané vˇzdy k aktuáln´ı verzi interpretátoru [11]. Ukáˇzeme si moˇznosti, které by nám pˇri tvorbˇe pˇredchoz´ıch pˇr´ıklad˚ u usnadnily práci nebo pomohly v jejich rozˇs´ıˇren´ı.

6.1.1

Vlastn´ı programy

Pˇri práci ocen´ıme predikát []/1, kter´ y má stejnou funkci jako jiˇz dobˇre znám´ y predikát consult/1. Cesta k souboru se pouze zap´ıˇse do hranat´ ych závorek stejnˇe jako seznam. M˚ uˇzeme také vypsat najednou v´ıce soubor˚ u, které se maj´ı nahrát. Fakta a pravidla definovaná v tˇechto souborech se nahraj´ı do databáze a vid´ıme je pˇri pouˇzit´ı listing/0. Interpretátor umoˇzn ˇuje kompilaci do bajtkódu podobnˇe jako v jazyce Java. Z naˇsich program˚ u m˚ uˇzeme takto vytvoˇrit samostatnˇe funkˇcn´ı celky. Ke kompilaci slouˇz´ı predikát compile/1, kter´ y jako argument pˇrij´ımá název souboru a na jeho základˇe vytvoˇr´ı binárn´ı soubor se stejn´ ym názvem a pˇr´ıponou .out. 41

Vývojové prostˇred´ı B-Prolog

Zmˇeny oproti standardu

Zkompilovan´ y program naˇcteme bud’ pomoc´ı load/1 nebo zadán´ım názvu jako argumentu pˇri spouˇstˇen´ı interpretátoru. Pro rychlou kompilaci a spuˇstˇen´ı vyuˇzijeme predikát cl/1, kter´ y ale nevytvoˇr´ı binárn´ı soubor. Standardnˇe v samostatn´ ych programech definujeme vstupn´ı predikát main, kter´ y by se mˇel automaticky po naˇcten´ı programu vyhodnotit. Pˇri zadán´ı argumentem se po dokonˇcen´ı bˇehu programu ukonˇc´ı i interpretátor. Za název programu m˚ uˇzeme vypsat libovolné argumenty, které v programu naˇcteme pouˇzit´ım get_main_args(Argumenty) do promˇenné Argumenty jako seznam. Spuˇstˇen´ı funguje ve starˇs´ıch verz´ıch, bohuˇzel v aktuáln´ı verzi 8.1 se main nezavolá, ale pouze se spust´ı interpretátor s nahran´ ym programem.

6.1.2

Komunikace s OS

Interpretátor má v sobˇe nav´ıc predikáty pro komunikaci s operaˇcn´ım systémem. Kromˇe predikátu write, kter´ y umoˇzn ˇuje v´ ypis na obrazovku je zde ˇrada dalˇs´ıch. Libovoln´ y pˇr´ıkaz systému zadáme prostˇrednictv´ım predikátu system(Prikaz, Status), kde Status je volitelná promˇenná, kam se uloˇz´ı návratová hodnota po vyhodnocen´ı pˇr´ıkazu Prikaz. Pro zjiˇstˇen´ı aktuáln´ı cesty, se kterou interpretátor pracuje, pouˇzijeme getcwd(Cesta). Pro zmˇenu cesty spouˇz´ı predikát cd/1, kter´ y jako argument pˇrij´ımá cestu absolutn´ı nebo relativn´ı v naˇsem souborovém systému. Seznam soubor˚ u ve sloˇzce z´ıskáme vyhodnocen´ım directory_files(Slozka, Seznam). Lze také kop´ırovat soubory pomoc´ı copy file/2, pˇr´ıpadnˇe mazat soubory volán´ım delete file/1. Sloˇzky maˇzeme volán´ım delete directory/1 a vytváˇr´ıme pomoc´ı make directory/1. Aktuáln´ı datum vyp´ıˇseme predikátem date/1 a aktuáln´ı systémov´ y ˇcas volán´ım time(Hodiny, Minuty, Sekundy).

6.1.3

Vol´ an´ı predik´ at˚ u

Predikáty voláme ve vˇetˇsinˇe interpretátor˚ u stejn´ ym zp˚ usobem. Pro vyhodnocen´ı c´ıle existuje ve standardu jeˇstˇe predikát call(Cil), kter´ y funguje totoˇznˇe jako klasické zadán´ı c´ıle do interaktivn´ıho rozhran´ı, a dále predikát once(Cil), kter´ y zabraˇ nuje backtrackingu stejnˇe jako volán´ı call(Cil, !). Uˇziteˇcné rozˇs´ıˇren´ı pˇredstavuje predikát time out/3, kter´ y se zapisuje ve tvaru time_out(Cil, Cas, Vysledek). Ten jednoduˇse vyhodnot´ı Cil po42



moc´ı volán´ı once, ale pokud pˇred vyhodnocen´ım uplyne ˇcas nastaven´ y argumentem Cas, volán´ı se ukonˇc´ı a v promˇenné Vysledek je pˇriˇrazen atom time_out. V opaˇcném pˇr´ıpadˇe se Vysledek unifikuje na success. M˚ uˇzeme se setkat s pˇr´ıpadem, kdy potˇrebujeme vyvolat akci aˇz kdyˇz se pˇriˇrad´ı promˇenné hodnota. K tomu vyuˇzijeme predikát freeze/2. Prvn´ı argument je promˇenná a druh´ y je c´ıl, kter´ y se má zavolat. Ten je zavolán pomoc´ı once právˇe tehdy, kdyˇz je promˇenná unifikována s konkrétn´ım termem. Predikát forall(Moznosti, Volani) nalezne postupnˇe vˇsechny moˇznosti vyhodnocen´ı termu Moznosti a pro kaˇzdou z moˇznost´ı vyvolá c´ıl Volani. Jako pˇr´ıklad je v manuálu uvedeno procházen´ı prvk˚ u seznamu. Zaj´ımavé je pro nás i tˇelo definice tohoto predikátu: forall(Moznosti, Volani) :- \+ (call(Moznosti), \+ call(Volani)). | ?- forall(member(X,[a,b,c]),write(X)). abc yes

6.1.4

Pr´ ace se seznamy

B-Prolog definuje mimo jiné i základn´ı operace se seznamy, které se ve standardu nevyskytuj´ı. V posledn´ım pˇr´ıkladu vid´ıme pouˇzit´ı nového predikátu member(X, Seznam), kter´ y kontroluje, zda X je prvkem seznamu Seznam. Pokud promˇennou X nepˇriˇrad´ıme, bude unifikována s prvn´ım prvkem seznamu. Pomoc´ı backtrackingu m˚ uˇzeme postupnˇe prohledat cel´ y seznam od zaˇca´tku do konce. Pouˇz´ıvan´ y je také predikát length/2, kter´ y zjist´ı délku seznamu uvedeného v prvn´ım argumentu a ˇc´ıslo unifikuje s druh´ ym argumentem. Pomoc´ı sort/2 seˇrad´ıme seznam v prvn´ım argumentu vzestupnˇe. U predikátu sort/3 m˚ uˇzeme nav´ıc jako prvn´ı argument definovat ˇrad´ıc´ı operátor <, >, =< nebo >=. Predikát keysort(S1, S2) pracuje se seznamem pár˚ u a jeho v´ ystupem je seznam seˇrazen´ y podle prvn´ıho prvku z páru: | ?- keysort([(3,a), (2,c), (1,b)], Serazene). Serazene = [(1,b),(2,c),(3,a)] Yes

Je to obdoba mapy v jazyce Java, kde prvn´ı prvek páru je kl´ıˇc, druh´ y prvek je hodnota.

43



Ze seznamu m˚ uˇzeme konkrétn´ı prvky u ´plnˇe vymazat, nebo je postupnˇe odeb´ırat následuj´ıc´ım zp˚ usobem: | ?List yes | ?List List List no

delete([a,b,a,b,c,a,g], a, List). = [b,b,c,g] select(a, [a,b,a,b,c,a,g], List). = [b,a,b,c,a,g] ?; = [a,b,b,c,a,g] ?; = [a,b,a,b,c,g] ?;

Prvek ze seznamu na konkrétn´ı pozici vybereme pomoc´ı predikátu nth/2 (prvky ˇc´ıslované od jedniˇcky) nebo nth0/2 (prvky jsou ˇc´ıslované od nuly): | ?- nth(2, [1,2,3], X). X = 2 yes | ?- nth0(2, [1,2,3], X). X = 3 yes

6.1.5

Cyklus, kolekce a form´ atov´ an´ı v´ ystupu

Cykus foreach se zapisuje se ve tvaru: foreach(X1 in K1, ..., Xn in Kn, Lokalni_promenne, Cil) Xi pˇredstavuje promˇennou pˇr´ıpadnˇe term, Ki je kolekce, pˇres kterou se bude iterovat. Iterac´ı m˚ uˇze b´ yt libovolné mnoˇzstv´ı a projdou se vˇsechny moˇznosti stejn´ ym postupem, jak funguje backtracking, tedy zleva doprava a s vyvolanou opakovanou zmˇenou moˇzn´ ych hodnot. Promˇenná Lokalni pˇredstavuje seznam promˇenn´ ych, které jsou doˇcasné pro jednu iteraci a Cil je libovoln´ y c´ıl, kter´ y se bude pˇri kaˇzdé iteraci vyhodnocovat. Abychom proˇsli vˇsechny prvky seznamu, m˚ uˇzeme pouˇz´ıt cyklus foreach následovnˇe: | ?- foreach(N in [1,2,3], (write(’Cislo ’), writeln(N))). Cislo 1 Cislo 2 Cislo 3 yes

44



Pod´ıvejme se na sloˇzitˇejˇs´ı zápis vˇcetnˇe pouˇzit´ı kolekce ˇc´ısel a formátován´ı v´ ystupu: | ?- foreach(I in 1..3,J in 2..-1..1,format("{~d, ~d}.\n",[I,J])). {1, 2}. {1, 1}. {2, 2}. {2, 1}. {3, 2}. {3, 1}. yes

Kolekce ˇc´ısel ve tvaru Od..Do nebo Od..Krok..Do se pouˇz´ıvá pouze v cyklu. Od je poˇca´teˇcn´ı ˇc´ıslo, Do je koneˇcné ˇc´ıslo a Krok se k p˚ uvodn´ımu ˇc´ıslu v kaˇzdé iteraci pˇriˇc´ıtá. V´ ychoz´ı hodnota kroku je 1. Z jazyka C známe funkci printf, které zadáme prvn´ım argumentem ˇretˇezec se speciáln´ımi formátovac´ımi znaˇckami a druh´ y argument je v´ yˇcet prvk˚ u, které se do ˇretˇezce za formátovac´ı znaˇcky dosad´ı. Ekvivalentnˇe funguje predikát format/2. Znaˇcky v ˇretˇezci zaˇc´ınaj´ı znakem ’~’. V naˇsem pˇr´ıkladu ~d znaˇc´ı ˇc´ıslo. M˚ uˇzeme také zapsat ~Nd, kde N je ˇc´ıslo, které urˇcuje, jak velké m´ısto má b´ yt pro ˇc´ıslo vyhrazeno. Pokud se nevyuˇzije celé m´ısto, ˇc´ıslo se dopln´ı zleva mezerami. Dalˇs´ı moˇznost´ı je ~a pro v´ ypis atomu bez uvozovek, ~Nc pro v´ ypis N stejn´ ych znak˚ u (pokud N neuvedeme, vyp´ıˇse se jeden). Pro vypsán´ı znaku ’~’ pouˇzijeme zápis ~~. Druh´ y argument bude obsahovat jeden nebo seznam vˇsech prvk˚ u pouˇzit´ ych ve formátovac´ım ˇretˇezci. Formátovac´ı znaˇcky jsou vypsány v návodu [11] na stranˇe 45.

6.1.6

M´ od ladˇ en´ı

Pˇri tvorbˇe program˚ u vyuˇzijeme mód ladˇen´ı (anglicky debugger), kter´ y nám m˚ uˇze pomoci s odhalen´ım chyb v návrhu pravidel a predikát˚ u. Mód v interpretátoru spust´ıme predikátem trace/0. V tomto módu vid´ıme vyhodnocen´ı jednotliv´ ych c´ıl˚ u od zaˇca´tku do konce, vˇcetnˇe veˇskeré unifikace. Ladic´ı mód opust´ıme volán´ım notrace/0:

45



| ?- trace yes {Trace mode} | ?- write(a). Call: (1) write(a) ? a Exit: (1) write(a) ? yes

Vyhodnocován´ı se hned zastav´ı a pomoc´ı klávesy enter se m˚ uˇzeme posouvat po kroc´ıch, které interpretátor ˇcin´ı. P´ısmeno ’s’ pˇreskakuje aktuálnˇe volan´ y predikát a zastav´ı se aˇz po jeho u ´spˇeˇsném ˇci ne´ uspˇeˇsném vyhodnocen´ı. P´ısmenem ’r’ necháme lad´ıc´ı mód vypsat vˇsechny kroky aˇz do konce vyhodnocen´ı. V zastaveném ladˇen´ı se dá vyvolat nápovˇeda pomoc´ı p´ısmene ’h’ nebo znakem ’?’. V programu m˚ uˇzeme definovat pouze konkrétn´ı body, na kter´ ych se chceme zastavit a prozkoumat je pˇri vyhodnocován´ı. K tomu pouˇzijeme predikát spy(Funktor/Arita). Lad´ıc´ı v´ ypisy jsou poté od volán´ı urˇceného predikátu stejné, jako u trace. Jeden bod zastaven´ı odebereme volán´ım nospy/1 a vˇsechny body volán´ım nospy/0.

6.1.7

Glob´ aln´ı promˇ enn´ e

V programech m˚ uˇzeme definovat promˇenné, které jsou poté pouˇzitelné napˇr´ıˇc cel´ ym bˇehem programu. Globáln´ı promˇennou definujeme predikátem global_set(Nazev, Hodnota). Hodnotu globáln´ı promˇenné z´ıskáme volán´ım global_get(Nazev, Hodnota). Název mus´ı b´ yt atom, hodnota je libovoln´ y term. Zda je zadan´ y atom globáln´ı promˇenná zjist´ıme pomoc´ı is global/1: | ?- global_set(promenna, 3). yes | ?- is_global(promenna). yes | ?- global_get(promenna, Hodnota). Hodnota = 3 yes

46


6.2

Propojen´ı s imperativn´ımi jazyky

Propojen´ı s imperativn´ımi jazyky

Kl´ıˇcovou vlastnost´ı dneˇsn´ıch interpretátor˚ u je moˇznost oboustranné spolupráce Prologovského programu s klasick´ ym pˇr´ıstupem k programován´ı. Nejˇcastˇeji se setkáme s propojen´ım s jazyky Java, C, C++ nebo C#. To se odv´ıj´ı od toho, v jakém jazyce byl interpretátor napsán. Abychom mohli realizovat napˇr. propojen´ı s jazykem C, potˇrebujeme speciáln´ı knihovny nebo zdrojové kódy interpretátoru. V nˇekter´ ych implementac´ıch jsou volnˇe dostupné, ale B-Prolog se bohuˇzel ˇrad´ı mezi ty, které maj´ı tyto funkce draze zaplacené. Pod´ıváme se pouze teoreticky na propojen´ı s jazykem C. Podpora jazyka Java nen´ı v aktuáln´ı verzi interpretátoru pˇr´ıliˇs rozˇs´ıˇrena. V návodu je podrobnˇe popsáno, jak´ ym zp˚ usobem m˚ uˇzeme vyvolávat programové segmenty jazyka C v Prologu a obrácenˇe, vˇcetnˇe praktick´ ych pˇr´ıklad˚ u. Ukáˇzeme si struˇcnˇe, jak s propojen´ım zaˇc´ıt. Nejprve je tˇreba pˇridat do systému konstantu BPDIR, která bude odkazovat na instalaci B-Prologu. Zdrojové kódy bychom mˇeli po zakoupen´ı licence naj´ıt ve sloˇzce Emulator.

6.3 6.3.1

Propojen´ı s jazykem C Vol´ an´ı C z Prologu

Pro vytvoˇren´ı funkc´ı v jazyce C takov´ ych, abychom je mohli volat z interpretátoru jako predikáty, je potˇreba m´ıt k dispozici veˇskeré zdrojové kódy interpretátoru. Vytváˇren´ı takového predikátu prob´ıhá ve tˇrech kroc´ıch: 1) Vytvoˇr´ıme soubor, kam definujeme funkci, která bude provádˇet poˇzadovanou akci. Funkce mus´ı b´ yt bez argument˚ u a mus´ı vracet celoˇc´ıselnou hodnotu. Ke komunikaci s interpretátorem vyuˇz´ıváme sadu pˇredpˇripraven´ ych funkc´ı. Ty jsou deklarované v hlaviˇckovém souboru bprolog.h, kter´ y mus´ıme zahrnout do naˇseho programu pomoc´ı #include "bprolog.h". Pouˇzit´ı tˇechto funkc´ı si pˇribl´ıˇz´ıme dále. 2) Novˇe vytvoˇren´ y soubor s funkc´ı mus´ıme zahrnout do kódu interpretátoru, nejˇcastˇeji pˇr´ımo do cpreds.c, kde jsou definovány zabudované preˇ dikáty zapsané v jazyce C. Reknˇ eme, ˇze naˇse funkce je deklarována jako int moje_funkce() a nov´ y predikát urˇc´ıme jako volaniC/2.

47


Propojen´ı s jazykem C

Do tˇela funkce Cboot() pˇridáme následuj´ıc´ı ˇra´dky: extern int moje_funkce(); insert_cpred("volaniC", 2, moje_funkce);

3) Pˇrekompilujeme cel´ y interpretátor a po spuˇstˇen´ı m˚ uˇzeme volat predikát volaniC/2 stejnˇe, jako ostatn´ı zabudované predikáty. Vrat’me se k vytváˇren´ı samotné funkce. Kaˇzd´ y term je popsán strukturou TERM, se kterou pracuj´ı pˇreddefinované funkce. Strukturu z´ıskáme jako návratovou hodnotu funkce nebo ji pˇredáme argumentem. V aktuáln´ı verzi intepretátoru zaˇc´ınaj´ı názvy vˇsech funkc´ı pˇredponou bp “. ” I pˇresto, ˇze nov´ y predikát bude binárn´ı, funkci deklarujeme bez argument˚ u. Ty následnˇe z´ıskáme volán´ım funkce: TERM bp_get_call_arg(int i, int arita) kde i je i-tý argument (poˇc´ıtáno od 1) a arita je arita predikátu. Existuje sada funkc´ı, které kontroluj´ı typ termu. Návratové hodnoty jsou BP_TRUE pˇri u ´spˇechu nebo BP_FALSE pˇri ne´ uspˇechu. Následuje v´ yˇcet nˇekolika funkc´ı a podm´ınky jejich u ´spˇeˇsného vyhodnocen´ı: int bp_is_integer(TERM t) – t je celé ˇc´ıslo int bp_is_atom(TERM t) – t je atom int bp_is_list(TERM t) – t je seznam a dalˇs´ı. Kontroly potˇrebujeme pro konverzi struktury TERM na datov´ y typ, kter´ y m˚ uˇzeme snadno zpracovat pomoc´ı klasick´ ych postup˚ u v C. Pokud známe typ termu, m˚ uˇzeme pouˇz´ıvat odpov´ıdaj´ıc´ı funkce: int bp_get_integer(TERM t) – vrát´ı celoˇc´ıselnou hodnotu termu t double bp_get_float(TERM t) – vrát´ı reálnou hodnotu termu t (char *) bp_get_name(TERM t) – vrát´ı ukazatel na ˇretˇezec, kter´ y odpov´ıdá názvu atomu nebo struktury t int bp_get_arity(TERM t) – vrát´ı aritu atomu nebo struktury t Pokud se konverze nepovede, jsou vráceny v´ ychoz´ı (nulové) hodnoty a globaln´ı promˇenná exception je nastavena na chybovou hodnotu. Jazyk C nepodporuje vyvoláván´ı a odchytáván´ı v´ yjimek, promˇennou proto mus´ıme kontrolovat sami. Dva termy m˚ uˇzeme mezi sebou unifikovat pomoc´ı funkce: int bp_unify(TERM t1, TERM t2) a jako návratovou hodnotu dostaneme BP_TRUE nebo BP_FALSE. Argument na i-té pozici z´ıskáme volán´ım funkce: 48


Propojen´ı s jazykem C

TERM bp_get_arg(int i, TERM t) jej´ıˇz návratovou hodnotou je term na poˇzadované pozici, pokud existuje. V opaˇcném pˇr´ıpadˇe je oznámena chyba. Práce se seznamy je realizována funkcemi: TERM bp_get_car(TERM t) a TERM bp_get_cdr(TERM t) kde car je prvn´ı prvek seznamu a cdr je zbytek, tedy opˇet seznam. V´ ypis termu zajist´ı funkce void bp_write(TERM t). Posledn´ı moˇznost´ı je vytváˇren´ı vlastn´ıch term˚ u v kódu jazyka C: TERM bp_build_var() – vytvoˇr´ı prázdnou promˇennou TERM bp_build_atom(char *nazev) – vytvoˇr´ı atom TERM bp_build_integer(int cislo) – vytvoˇr´ı celoˇc´ıseln´ y term TERM bp_build_nil() – vytvoˇr´ı prázdn´ y seznam TERM bp_build_list() – vytvoˇr´ı prázdn´ y seznam, kter´ y m˚ uˇzeme libovolnˇe definovat TERM bp_build_structure(char *nazev, int arita) – vytvoˇr´ı strukturu nazev/arita, jej´ıˇz argumenty m˚ uˇzeme libovolnˇe definovat Jednoduch´ y pˇr´ıklad k této problematice nalezneme v manuálu [11] na stranˇe 99.

6.3.2

Vol´ an´ı Prologu z C

Pokud chceme z programu napsaného v jazyce C zavolat sekvenci jazyka Prolog, zmˇen´ıme zdrojov´ y kód spouˇstˇec´ıho souboru main.c za náˇs vlastn´ı. Pred volán´ım predikát˚ u mus´ıme pouˇz´ıt funkci: initialize_bprolog(int argc, char *argv[]) Ta alokuje vˇsechnu potˇrebnou pamˇet’ a nahraje sadu zabudovan´ ych predikát˚ u. Pokud se nepodaˇr´ı interpretátor spustit, funkce vrát´ı hodnotu BP_ERROR. Jednotlivé c´ıle m˚ uˇzeme volat pomoc´ı int bp_call_string(char *cil) zadán´ım termu ve formˇe ˇretˇezce nebo pomoc´ı struktury TERM volán´ım funkce int bp_call_term(TERM cil). Ta nav´ıc podporuje unifikaci promˇenn´ ych. Dalˇs´ı moˇznost´ı je pouˇzit´ı funkce bp mount query string pˇrij´ımaj´ıc´ı ˇretˇezec nebo bp mount query term pˇrij´ımaj´ıc´ı strukturu TERM. Tyto funkce naplánuj´ı“ dalˇs´ı c´ıl k vyhodnocen´ı. Poté m˚ uˇzeme v´ıcekrát za sebou pou” ˇz´ıt funkci int bp_next_solution(), která nalezne dalˇs´ı ˇreˇsen´ı. Pokud nen´ı ˇzádn´ y c´ıl naplánován, jej´ı návratová hodnota bude BP_ERROR, pokud jiˇz dalˇs´ı c´ıl nelze vyhodnotit, vrát´ı BP_FALSE.

49

7 Závˇer Jiˇz od zaˇca´tku práce je brán zˇretel na ˇctenáˇre, kteˇr´ı s Prologem tepreve zaˇc´ınaj´ı. Pˇrestoˇze pracuji v´ yhradnˇe s prostˇred´ım B-Prolog, ˇctenáˇr má ˇsanci nauˇcit se základy jazyka Prolog i za pouˇzit´ı jiného interpretátoru. M˚ uˇze si vybrat na základˇe struˇcného shrnut´ı aktuáln´ıch implementac´ı, pˇr´ıpadnˇe jak´ ykoliv jin´ y interpretátor podporuj´ıc´ı standard ISO Prolog. Záleˇz´ı na individuáln´ıch poˇzadavc´ıch na následné vyuˇzit´ı jazyka. Praktické pˇr´ıklady se prol´ınaj´ı s teori´ı. Samozˇrejmost´ı je pozvolné stupˇ nován´ı nároˇcnosti prezentovan´ ych pˇr´ıklad˚ u. Ty jsou nejdˇr´ıve napsány jednoduch´ ym zp˚ usobem a dále rozˇsiˇrovány. C´ılem je vytváˇret programy dostateˇcnˇe dekomponované s následnou moˇznost´ı snadného rozˇs´ıˇren´ı funkcionality. Na ukázkách poukazuji na zápisy, kter´ ym je dobré se vyvarovat a navrhuji, ˇ aˇr by mˇel b´ jak dále a lépe pˇri tvorbˇe program˚ u postupovat. Cten´ yt následnˇe schopen psát programy ˇcistˇe, a mˇel by m´ıt dostateˇcné znalosti pro samostatné ˇreˇsen´ı problém˚ u spojen´ ych s návrhem sloˇzitˇejˇs´ıch program˚ u v Prologu. Pro u ´ˇcely v´ yuky pˇredmˇetu KIV/UZI byla, na základˇe podklad˚ u od vedouc´ıho práce, vytvoˇrena pˇrehledná prezentace shrnuj´ıc´ı d˚ uleˇzité faktory základn´ı práce s Prologem. Ta bude následnˇe um´ıstˇena na webové stránky pˇredmˇetu spoleˇcnˇe s programy, které jsou k náhledu i v textu práce. Mimo to bude k dispozici i mnoˇzina dalˇs´ıch klasick´ ych Prologovsk´ ych problém˚ u pro prezentaci z´ıskan´ ych znalost´ı a funkˇcnosti interpretátoru samotného. Shodn´ y obsah, vˇcetnˇe návodu k obsluze, bude k nalezen´ı na pˇriloˇzeném CD. B-Prolog sk´ ytá mnohá vylepˇsen´ı oproti standardu. Nejvˇetˇs´ı v´ yhodou je moˇznost propojen´ı s jazykem C. Nev´ yhodou je, ˇze nˇekteré zabudované predikáty nefunguj´ı dle pˇr´ıruˇcky, ale to mohou m´ıt za následek ˇcasté aktualizace interpretátoru, kter´ y se neustále vyv´ıj´ı. Pˇrestoˇze na oficiáln´ıch webov´ ych stránkách projektu a v licenc´ıch je uvedeno, ˇze B-Prolog je pro osobn´ı a akademické u ´ˇcely zdarma, zdrojové kódy potˇrebné k propojen´ı s jazykem C k dispozici ke staˇzen´ı nejsou. Prostˇrednictv´ım elektronické komunikace s p. Zhou mi bylo sdˇeleno, ˇze zdrojové kódy je moˇzné zpˇr´ıstupnit za poplatek $2,980, kter´ y vytvoˇril velkou pˇrekáˇzku pˇri realizaci kombinovan´ ych program˚ u. Proto je tato problematika probrána pouze struˇcnˇe a teoreticky. Spojen´ı s jazykem Java je bohuˇzel v aktuáln´ı verzi podporováno minimálnˇe, a to pouze na platformˇe Windows 32-bit. Rozˇs´ıˇren´ı se u ´dajnˇe plánuje v následuj´ıc´ıch verz´ıch B-Prologu. V´ yrobci se nyn´ı v´ıce soustˇred´ı na nov´ y projekt – Picat, kter´ y je nepˇr´ım´ ym následovn´ıkem B-Prologu.

50

Literatura [1] Blackburn, P.; Bos, J. and Striegnitz, K.: Learn Prolog Now!. Texts in Computing, 2006, vol. 7. ISBN: 1-904987-17-6, s. 6-15. [2] Bramer, M.: Logic Programming with Prolog. University of Portsmouth, UK, 2005. ISBN-10: 1-85233-938-1, 223 s. [3] Covington, M. A.; Nute, D.; Vellino, A.: Prolog Programming in Depth. The University of Georgia, Athens, September 1993. Appendix A – ISO Prolog: A Summary of the Draft Proposed Standard, 1993. ISBN: 0-67318659-8, 27 s. [4] Covington, M. A.: Research Report AI-1989-02. A Numerical Equation Solver in Prolog. The University of Georgia, Athens, March 1989, 14 s. [5] Heng, Ch.: Free Prolog Compilers and Interpreters [online]. Last updated c March 24, 2014 1999-2014 [cit. 26. prosince 2013]. Dostupné z: http://www.thefreecountry.com/compilers/prolog. shtml [6] Kantrowitz. M.: Prolog Resource Guide [online]. Version: 1.36, Last c updated Feb 20, 1997. 1992-1994. [cit. 13. dubna 2014]. Dostupné z: http://www.cs.cmu.edu/afs/cs/project/ ai-repository/ai/html/faqs/lang/prolog/prg/top.html ´ [7] Kryl, R.: Neproceduráln´ı programován´ı: Uvod do programovac´ıho jazyka c PROLOG [online]. Verze 3.03. KSVI MFF UK, Praha. Rudolf Kryl, 2013 [cit. 13. dubna 2014]. Dostupné z: http://ksvi.mff.cuni.cz/∼kryl/prolog.pdf ´ [8] Skoupil, D.: Uvod do paradigmat programován´ı. Katedra matematické informatiky, Univerzita Palackého v Olomouci, 1997, s. 9-23

51

LITERATURA

LITERATURA

[9] Sterling, L.; Shapiro, E.: The Art of Prolog: advanced programming techniques. Massachusetts Institute of Technology, 1994. Appendix A – Operators. ISBN: 0-262-19338-8, s. 479-481 [10] Wielemaker, J. aj.: SWI Prolog Reference Manual. Herstellung und Verlag: Books on Demand GmbH, Norderstedt, 2012. ISBN 978-3-84-8226177, s. 59. c [11] Zhou, Neng-Fa: B-Prolog User’s Manual [online]. Version 7.8. Afany Software, 1994-2012. Last updated Jan 24, 2013 [cit. 26. prosince 2013]. Dostupné z: http://www.probp.com/download/manual.pdf

52

Západočeská univerzita v Plzni Fakulta aplikovaných věd Katedra informatiky a výpočetní techniky. programu pro výuku programovacího jazyka Prolog

Recommend Documents