Jazyky pro umělou inteligenci

VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ FAKULTA STROJNÍHO INŽENÝRSTVÍ Ústav automatizace a informatiky

Jazyky pro umělou inteligenci

Jiří Dvořák

2005

Jiří Dvořák


Obsah 1. Úvod............................................................…..........……………….………..

4

1.1 Funkcionální programování ........................................................…...…….

4

1.2 Logické programování ................................................................…....……

7

2. Jazyk Lisp ........................................................................………….……….

9

2.1 Typy dat …………………………………………………………………..

9

2.2 Struktura programu ………………………………………………………. 12 2.3 Základní funkce .......................................………………………...……… 12 2.4 Aritmetické a relační operace ..........................................................……... 16 2.5 Definice funkcí ...........................................................……………….....… 16 2.6 Funkce pro pracování seznamů …………………………………………… 19 2.7 Predikátové funkce ……………………………………………………….. 20 2.8 Vyhodnocovací funkce ................................................................................ 23 2.9 Řídicí programové struktury ........................................................................ 24 2.10 Mapovací funkcionály .......................................………….......................... 28 2.11 Definice a vyhodnocení maker .........……………..................................…. 29 2.12 Modifikace struktur ………………………………………………………. 31 2.13 Reprezentace atomů …………………………………………..………….. 33 2.14 Vstup a výstup ……………………………………………………………. 35

3. Využití jazyka Lisp pro řešení úloh umělé inteligence …..………………. 37 3.1 Přehled aplikací………………………………………………...……….… 37 3.2 Příklad využití Lispu pro tvorbu expertního systému ………….…….…… 38

4. Jazyk Prolog ………………………………….………………..…………… 42 4.1 Charakteristika a příklad programu …………………………….………… 42 4.2 Typy a syntaxe dat …………………………………………………….….. 48 4.3 Syntaxe programu ………………………………………………………… 49 4.4 Unifikace …………………..……………………………………………… 50 4.5 Deklarativní a procedurální sémantika ………………………………….... 51 4.6 Blokový model vyhodnocování …………………………………………... 54 4.7 Zpracování čísel .……………………………...…………………………... 56 -2-

Jiří Dvořák


4.8 Zpracování seznamů ………………………………………….………..…. 58 4.9 Operátorová notace …………………………….…………………………. 61 4.10 Typové predikáty …………………………………………………………. 63 4.11 Rozklad a vytváření termů ……………………………………………….. 64 4.12 Meta-logické predikáty ……………………………….…………………... 65 4.13 Řez ………………………………………………………………………... 67 4.14 Negace ……………………………………………………………………. 68 4.15 Práce s databází …………………………………………………………... 68 4.16 Vstup a výstup ……………………………………………………………. 70 4.17 Cykly ……………………………………………………..………………. 71

5. Využití jazyka Prolog pro řešení úloh umělé inteligence ………….…….. 73 5.1 Přehled aplikací …………………………………………………………... 73 5.2 Příklad využití Prologu pro tvorbu expertního systému ………….………. 73

Literatura ………………………………………………………………………. 78 Seznam internetových adres …………………………………………………... 79 Přílohy Příloha A: Přehled definovaných jmen Lispu ……………………………….…. 80 Příloha B: Přehled definovaných jmen a operátorů Prologu …………………… 81 Příloha C: Výsledky úloh na procvičení ……………………………………….. 82

-3-

Jiří Dvořák


1. Úvod Řešení problémů umělé inteligence (UI) lze naprogramovat i v běžných programovacích jazycích, jako je Pascal nebo C. Vzhledem k charakteru problémů UI jsou pro tento účel často používány speciální programovací jazyky, jako např. Lisp (používaný zejména v USA) a Prolog (populární zejména v Evropě). Speciální programovací jazyky pro UI jsou obvykle založeny na jiných paradigmatech programování (programovacích stylech) než klasické programovací jazyky. Programovací styly Niklaus Wirth (autor jazyka Pascal) zformuloval známou rovnici Program = algoritmus + datové struktury Robert Kowalski (jeden za zakladatelů logického programování) tuto rovnici doplnil takto: Algoritmus = funkce (logika) + řízení Podle toho, na kterou složku algoritmu je kladen větší důraz, můžeme rozlišit dva hlavní programovací styly: •

Imperativní programovací styl: Je kladen důraz na řídicí složku, tj. JAK se má výpočet provést. Program je tvořen posloupností příkazů.

•

Neimperativní (deklarativní) programovací styly: Řídicí složka je potlačena a důraz je kladen na to CO má být vypočteno. Program je např. tvořen souborem definic funkcí a jejich aplikací ve formě výrazů (funkcionální programování) nebo souborem logických formulí (logické programování), které specifikují řešený problém.

Významným rysem deklarativních jazyků (v jejich čisté podobě) je absence přiřazovacího příkazu. Bez tohoto příkazu mohou programátoři pouze deklarovat, jaké účinky by měly vést k jakým výsledkům. Deklarativní jazyky můžeme charakterizovat jako jazyky s referenční transparentností. Referenční transparentnost znamená omezení rozsahu, ve kterém mohou programátoři měnit hodnoty proměnných. V rámci neimperativních programovacích stylů hrají důležitou roli tyto dva styly: •

Funkcionální styl: základní komponentou programu je funkce.

•

Logický styl: základní komponentou programu je relace.

Použití neimperativních jazyků: •

Řešení speciálních problémů (např. problémů umělé inteligence)

•

Vytvoření prototypu programu, po jehož ověření se může pokračovat imperativním způsobem

1.1 Funkcionální programování Funkcionální program se vytváří jako souhrn definic funkcí a jejich aplikací ve formě výrazů. Jedná se o to, jak vyjádřit daný algoritmus pomocí vzájemně provázaných (zpravidla rekurzivních) funkcí. Výpočet podle takového programu lze chápat jako provedení aplikace nějaké funkce na určitou sadu hodnot jejích argumentů s cílem získat výslednou hodnotu. Počítač

-4-

Jiří Dvořák


má ve funkcionálním programování roli vyhodnocovače výrazů přičemž základním krokem vyhodnocení je zjednodušení (redukce) výrazu. Výsledek výpočtu do značné míry nezávisí na pořadí, v němž se redukují jednotlivé dílčí výrazy. To vede ke snížení rizika možných chyb programování a umožňuje paralelní provádění redukčních transformací na víceprocesorových počítačích. Principy funkcionálního programování mohou také vést k navrhování počítačů, jejichž technická realizace už nemusí vycházet z von Neumannova modelu. Definice

Výrazy

Vyhodnocení

Prostředí

Výsledky Obr. 1.1. Počítač jako vyhodnocovač výrazů

Výhody funkcionálních programovacích jazyků lze shrnout do těchto bodů: •

dovolují psát kratší a elegantnější programy než v konvenčních jazycích;

•

dovolují psát programy, které vypadají jako specifikace; automatické transformační systémy je pak mohou konvertovat do účinně fungujících programů;

•

funkcionální programy mohou snadno využít paralelismu multiprocesorových systémů.

Funkcionální jazyky nahrazují statické datové struktury dynamickými datovými strukturami, kde paměť pro nějakou položku je (automaticky) alokována teprve v okamžiku, kdy položka začíná existovat. Příklady funkcionálních programovacích jazyků: •

Lisp -5-

Jiří Dvořák •

FP

•

Hope

•

Miranda [21]

•

Haskell


Při striktním pohledu není možno jazyk Lisp považovat za čistě funkcionální jazyk, protože do různých verzí Lispu byly přidány početné imperativní rysy. Problematikou funkcionálního programování se zabývá např. kniha [7]. Rekurze V neimperativním programovacím stylu je rekurze důležitým nástrojem pro řešení složitých problémů. Taxonomie rekurzivních definic: •

Vnořená rekurze: rekurzivní volání funkce obsahuje v argumentech volání téže funkce. Příklad: Ackermannova funkce ( x = 0) y +1  ack ( x, y ) = ack ( x − 1, 1) ( y = 0) ack ( x − 1, ack ( x, y − 1)) ( jinak ) 

•

Kaskádní (stromová) rekurze: ve stejném výrazu se objevuje několik rekurzivních volání, ale bez vzájemného vnoření. Příklad: Funkce pro určení n-tého prvku Fibonacciho posloupnosti ( n ≤ 1) n fib( n ) =   fib( n − 2) + fib( n − 1) ( jinak )

•

Lineární rekurze: v každé z alternativ v definici funkce se vyskytuje nejvýše jedno její rekurzivní volání. Příklad: Funkce pro výpočet faktoriálu přirozeného čísla n ( n = 0) 1 fakt ( n ) =  n * fakt ( n − 1) ( jinak )

•

Koncová rekurze: speciální případ lineární rekurze, kdy rekurzivní volání je poslední operací příslušné alternativy definice. Příklad: funkce pro výpočet největšího společného dělitele dvou celých kladných čísel ( x = y) x  nsd ( x, y ) = nsd ( x − y, y ) ( x > y ) nsd ( x, y − x) ( jinak ) 

Příklady převodu definice faktoriálu na koncovou rekurzi: -6-

Jiří Dvořák a)

Jazyky pro umělou inteligenci fakt ( n ) = fakt1(1, n ) (i = 0) m fakt1( m, i ) =   fakt1( m * i, i − 1) (i > 0)

b)

fakt ( n ) = fakt 2(1, n, 1) (i > n) m fakt 2(m, n, i ) =   fakt 2(m * i, n, i + 1) (i ≤ n)

1.2 Logické programování Při logickém programování těžiště práce tvůrce programu spočívá v nalezení vhodného popisu řešené úlohy a vztahů v ní. Typickým reprezentantem jazyků pro logické programování je jazyk Prolog. Tento jazyk vychází z toho, že pokud máme k dispozici co nejpřesnější popis všech důležitých vlastností světa úlohy, pak je možné využít metod automatického dokazování vět pro nalezení posloupnosti akcí, které povedou k řešení úlohy. Systém automatického dokazování vět tak přebírá roli překladače logického programu a jeho úkolem je navrhnout vhodné zřetězení základních operací počítače pro vyřešení zadané úlohy. Výchozím vyjadřovacím jazykem logického programování je jazyk logiky prvního řádu. Objekty světa jsou v tomto jazyce popisovány pomocí termů, které reprezentují konstanty, proměnné a případně i složené termy vzniklé aplikací funkcí na termy jednodušší. Proměnná je jméno, které zastupuje neznámý objekt splňující formuli, v níž se vyskytuje. Tento objekt může být postupně upřesňován pomocí substituce v průběhu výpočtu. Často se zkoumá, zda dva výrazy logického jazyka lze ztotožnit tím, že se provede vhodná substituce za proměnné v obou výrazech (říkáme, že se hledá unifikující substituce resp. unifikace). Vztahy mezi objekty popisují predikáty, které odpovídají relacím. Prolog je postaven na lineární strategii rezoluce, která se stala jeho hlavním odvozovacím prostředkem. Tato strategie je však úplná jen pro jistou třídu klauzulí, označovanou jako Hornovy klauzule. Klauzule je libovolná konečná disjunkce literálů (atomů) a v Hornově klauzuli se nesmí objevit více než jeden pozitivní atom. Tím jsou poněkud zúženy vyjadřovací možnostmi jazyka Prolog ve srovnání s jazykem predikátové logiky 1. řádu v plné obecnosti. Je-li toto omezení plně respektováno, říkáme, že jde o čistý Prolog. Pro praktické účely se zavádějí různá vhodná mimologická rozšíření. Při přechodu od malých prototypů k rozsáhlým uživatelsky orientovaným systémům naráží použití standardního Prologu na bariéry, způsobené nadměrnými časovými a paměťovými nároky. Tyto problémy sice zčásti řeší kompilační verze překladačů Prologu, ale přesto je programátor často nucen se odchylovat od čistě deklarativního přístupu. Jiným problémem standardního Prologu je unifikace, která dovoluje srovnávat pouze syntakticky příbuzné objekty. Při řešení praktických úloh by však často bylo výhodná možnost srovnávat i objekty sémanticky ekvivalentní. Řešení výše uvedených problémů nabízí nová programovací metoda – logické programování s omezujícími podmínkami (Constraint Logic Programming – CLP). V CLP je unifikace nahrazena rozhodovací procedurou, která umožňuje využívat jak syntaxi, tak i sémantiku -7-

Jiří Dvořák


zpracovávaných objektů. Základem této procedury je řešení omezujících podmínek (constraint satisfaction). CLP není pouhým rozšířením standardního Prologu, ale jeho zobecněním. Výhody logického programování lze shrnout takto: •

Logické programování je deklarativní, neboť výsledná posloupnost elementárních akcí vedoucích k cíli je odvozena automaticky bez zásahu programátora. Vzhledem k této vlastnosti je snadné rozšířit logický program o nové informace, datové struktury a pravidla, jak s nimi zacházet.

•

Při použití logických programovacích jazyků je výsledný programový kód krátký a přehledný, což usnadňuje jeho ladění a udržování.

•

Jazyky logického programování mají bohaté prostředky pro konstrukci a definici různých datových struktur. Uživatel má bezprostřední přístup k prvkům složitých struktur bez nutnosti používat ukazatel (pointer). Navíc operace unifikace a zpětného chodu (backtracking) usnadňují srovnávání vzorů a prohledávání prostoru možností. Uvedené vlastnosti podporují metaprogramování, kdy se s programy zachází jako s daty.

Příklady jazyků pro logické programování: •

Prolog

•

ECLiPSe

•

Gödel

•

Mercury

-8-

Jiří Dvořák


2. Jazyk Lisp Jazyk Lisp je jedním z nejstarších dosud používaných programovacích jazyků. Původně vznikl koncem 50. let (Mc Carthy, 1960) jako určitá notace pro zápis algoritmů pracujících se seznamy (LISP = LISt Processing). Verze jazyka Lisp: •

Lisp 1.5 (Mc Carthy, 1962)

•

MacLisp [24]

•

InterLisp

•

Franz Lisp [22]

•

Zeta Lisp

•

Scheme [8]

•

Common Lisp [12]

•

Xlisp

V této kapitole jsou popsány pouze základy jazyka Lisp, přičemž se orientujeme zejména na Common Lisp. Podrobněji se s jazykem Lisp můžete seznámit v knihách [10], [12], [18], [22], [24].

2.1 Typy dat Souhrnně se data v Lispu nazývají S-výrazy (symbolické výrazy). Dělíme je na jednoduché a strukturované. Další dělení ukazuje obr. 2.1.

S-výrazy

jednoduché (atomy)

čísla

celá

reálná

symboly

strukturované

tečka-dvojice

speciální znaky identifikátory Obr. 2.1. Typy dat v Lispu -9-

seznamy

Jiří Dvořák


Atomy

Atomy jsou základní syntaktickou jednotkou jazyka a zahrnují jednak čísla (celá nebo reálná), jednak symboly (speciální znaky a identifikátory). Příklady atomů: •

čísla:

•

speciální znaky: + - * < > =

•

identifikátory.

123 -5.46 alfa

Beta1

pocet_atomu

ponekud-delsi-atom

Identifikátory mohou obsahovat písmena, číslice, pomlčku a podtržítko. Obvykle se nerozlišují velká a malá písmena. Tečka-dvojice (S-výraz1.S-výraz2)

Tečka-dvojice představuje binární strom, kde S-výraz1 odpovídá levému podstromu a S-výraz2 pravému podstromu. Tečka-dvojice je fyzicky reprezentována základní lispovskou buňkou (tzv. cons-buňkou), dělenou na 2 části, které obsahují ukazatele na příslušné podvýrazy (viz obr. 2.2). Názvy těchto částí jsou dány historicky (označují části strojového slova na počítači IBM 1040, kde byl Lisp poprvé implementován). address part

decrement part

S-výraz1

S-výraz2

Obr. 2.2. Fyzická reprezentace tečka-dvojice Příklady tečka-dvojic:

(A.B)

A

((A.B).C)

B

C

A

B

Obr. 2.3. Příklady reprezentace tečka-dvojic

- 10 -

Jiří Dvořák


Seznam (S-výraz1 S-výraz2 … S-výrazN)

Seznam je tvořen posloupností S-výrazů oddělených mezerami a uzavřených do kulatých závorek. Seznam je vlastně speciální případ tečky-dvojice zapsané ve zkrácené notaci.

Zápis seznamu v podobě tečky-dvojice: (S-výraz1.(S-výraz2.( … .(S-výrazN.nil)… )))

Atom nil je speciální atom, který reprezentuje konec seznamu. Fyzickou implementaci seznamu ukazuje obr. 2.4.

… S-výraz1

S-výraz2

S-výrazN

Obr. 2.4. Fyzická reprezentace seznamu Příklady: seznamová notace

tečka notace

(A)

(A.nil)

(A B C)

(A.(B.(C.nil)))

(A (B C) D)

(A.((B.(C.nil)).(D.nil)))

Prázdný seznam ( ) je ekvivalentní atomu nil.

A

B

C

A

D

B

Obr. 2.5. Příklady reprezentace seznamů

- 11 -

C

Jiří Dvořák


2.2 Struktura programu Program v Lispu se skládá z tzv. forem. Forma (E-výraz) je S-výraz, který lze vyhodnotit lispovským interpretem. Program je tedy posloupností vyhodnotitelných S-výrazů, což znamená, že program má stejný charakter jako jím zpracovávaná data. Typy forem: •

Číselný atom – vyhodnocením se získá číslo vyjádřené zápisem atomu.

•

Symbolický atom (identifikátor)

•

Zápis funkce

Symbolický atom (identifikátor) v pozici formy

Jestliže se symbolický atom nachází v pozici formy, je považován za proměnnou a jeho vyhodnocením se získá hodnota, která je v daném okamžiku vázána na daný atom. Pokud v okamžiku vyhodnocení není na daný atom žádná hodnota navázána, je signalizována chyba. Proměnné se standardně přiřazenou hodnotou: T

… hodnota je T (true)

NIL … hodnota je NIL F

… hodnota je NIL

Pozn.: platí konvence, že jakákoli hodnota různá od NIL vyjadřuje pravdivostní hodnotu true. Zápis funkce

Zápis funkce (přesněji zápis aplikace funkce) má tvar seznamu (f a1 a2 … aN)

kde f je jméno (symbolický atom) vyjadřující funkci a a1, a2, … , aN jsou formy vyjadřující argumenty, na něž se má funkce f aplikovat. Pro zápis funkce se v Lispu používá důsledně prefixová notace, přičemž se celý zápis uzavírá vždy do závorek. Tento požadavek se týká i zápisu aritmetických a relačních výrazů. Při vyhodnocení zápisu funkce Lisp nejprve vyhodnotí všechny argumenty a teprve na získané hodnoty aplikuje funkci f. Pořadí vyhodnocování argumentů není v Lispu přesně specifikováno. Výjimkou z tohoto pravidla jsou speciální funkce, z nichž každá má specifická pravidla pro vyhodnocení (resp. nevyhodnocení) argumentů. Zápisy těchto funkcí se nazývají speciální formy.

2.3 Základní funkce Speciální funkce quote (quote S-výraz)

Funkce quote představuje speciální identitu: jejím argumentem může být libovolný S-výraz, který se nevyhodnocuje a funkce jej vrátí jako svůj výsledek.

- 12 -

Jiří Dvořák


Příklad (za šipkou je uvedena výsledná hodnota): (quote (a b)) ⇒ (a b)

Tato identita se může zkráceně zapsat pomocí apostrofu podle následujícího vztahu 'S-výraz ≡ (quote S-výraz)

Tedy místo (quote (a b)) můžeme napsat '(a b). Použití apostrofu před číselným argumentem je ovšem zbytečné. Speciální funkce setq (setq proměnná forma)

Funkce setq je analogií příkazu přiřazení z imperativních jazyků. Prvý argument funkce setq je proměnná, která se nevyhodnocuje. Druhý argument je forma, která se vyhodnotí a její hodnota se naváže na uvedenou proměnnou. Tato hodnota je také výsledkem aplikace funkce setq. Příklady: (setq X 0) ⇒ 0

⇒ 0

X

(setq Y '(a b c)) ⇒ (a b c)

⇒ (a b c)

Y

Pokud bychom opomenuli apostrof před seznamem (a b c), systém by se jej pokusil vyhodnotit jako aplikaci funkce a, přičemž b a c by chápal jako proměnné. Pomocí setq je možné zajistit vazbu více proměnných. Vyhodnocování a navazování se v tomto případě provádí postupně. Výslednou hodnotou je hodnota poslední formy. (setq prom1 forma1 ... promN formaN)

Příklad: (setq A 'B B 'C) ⇒ C A

⇒ B

B

⇒ C

Funkce car a cdr (car forma)

Hodnotou argumentu musí být tečka-dvojice a hodnotou funkce car je pak první prvek této dvojice. Při aplikaci na neprázdný seznam dostaneme první prvek seznamu. CAR znamená Contents of Address Register.

- 13 -

Jiří Dvořák


(cdr forma)

Hodnotou argumentu musí být tečka-dvojice a hodnotou funkce cdr je pak druhý prvek této dvojice. Při aplikaci na neprázdný seznam dostaneme zbytek seznamu. CDR znamená Contents of Decrement Register. Pozn.: Tyto funkce nemají destruktivní charakter – původní S-výraz zůstává zachován. Příklady: (car '(A))

⇒ A

(cdr '(A))

⇒ nil

(car '(A.B))

⇒ A

(cdr '(A.B))

⇒ B

(car '(A B))

⇒ A

(cdr '(A B))

⇒ (B)

(car '(A B C)) ⇒ A (cdr '(A B C)) ⇒ (B C)

Existují také složené funkce tvaru cxx…xr, kde místo x může být a (zastupuje car) nebo d (zastupuje cdr). Příslušné funkce se aplikují zprava doleva. Platí např. následující identity: (caar X) ≡ (car (car X)) (cadr X) ≡ (car (cdr X)) Funkce cons (cons forma1 forma2)

Hodnotami argumentů mohou být libovolné S-výrazy. Hodnotou funkce cons je tečka-dvojice vytvořená z prvého a druhého S-výrazu. Provedení funkce cons znamená vytvoření nové consbuňky, obsahující ukazatele na buňky reprezentující uvedené S-výrazy. Příklady: (cons 'A 'B) ⇒ (A.B) (cons 'A '(B)) ⇒ (A B) (cons '(A B) '(C D)) ⇒ ((A B) C D) (car (cons 'A '(B C))) ⇒ A (cdr (cons 'A '(B C))) ⇒ (B C) (setq L '(A B)) ⇒ (A B) (cons (car L) (cdr L)) ⇒ (A B)

- 14 -

Jiří Dvořák


Funkce atom a eq (atom forma)

Hodnotou argumentu může být libovolný S-výraz. Funkce atom testuje, zda tato hodnota je atom, tj. číslo nebo symbol, a v tom případě má hodnotu T. V opačném případě má tato funkce hodnotu nil. (eq forma1 forma2)

Hodnotami argumentů musejí být atomy. Funkce eq testuje, zda tyto hodnoty jsou shodné atomy a v tom případě nabývá hodnotu T. Pokud hodnotami argumentů jsou různé atomy, je výsledkem nil. Příklady: (setq L '(A B)) ⇒ (A B) (atom L) ⇒ nil (atom (car L)) ⇒ T (atom (cdr L)) ⇒ nil (eq 'A (car L)) ⇒ T (eq 'A 'B) ⇒ nil Speciální funkce cond (cond (test1 ... výsledek1) (test2 ... výsledek2) ... (testN ... výsledekN))

Tato funkce zajišťuje větvení výpočtu, tedy výběr z několika alternativ v závislosti na splnění zadaných podmínek. Každá alternativa je vyjádřena seznamem forem, kterému říkáme klauzule. Speciální forma cond se vyhodnocuje tak, že se postupně vyhodnocují formy test na začátku klauzulí, až se nalezne první s hodnotou testu různou od nil. Pro tuto klauzuli se vyhodnotí i ostatní výrazy v ní obsažené a hodnota posledního z nich je výsledkem celé formy cond. Pokud se při vyhodnocení nenalezla žádná úspěšná klauzule, je výsledná hodnota nil. Speciálním případem klauzule je seznam obsahující pouze jediný výraz, který pak slouží současně jako podmínka i jako výsledek. Příklad: forma pro získání absolutní hodnoty proměnné X: (cond ((< X 0) (- 0 X)) (T X))

- 15 -

Jiří Dvořák


2.4 Aritmetické a relační operace Aritmetické operace: +,–,*,/ Relační operace: = , < , > , <= , >= , /= (nerovno) Výrazy s těmito operacemi je třeba zapisovat v prefixovém tvaru. Příklady: infixová notace

Lisp

a+b+c

(+ a b c)

a*b−c

(- (* a b) c)

a + 2 / (3 – b)

(+ a (/ 2 (- 3 b)))

(a + 2) / (3 – b)

(/ (+ a 2) (- 3 b))

a
(< a (- b c))

x=0

(= 0 x)

x>0

(> x 0)

K porovnání s nulou je možno použít predikáty zerop, plusp a minusp (viz str. 22)

2.5 Definice funkcí Speciální funkce defun (defun jméno-funkce (par1 par2 ... parN) výraz1 výraz2 ... výrazM )

Speciální funkce defun zajišťuje definování nových funkcí. Její hodnotou je jméno definované funkce. Při aplikaci takto definované funkce se nejprve vyhodnotí argumenty a jejich hodnoty se navážou na proměnné par1, par2, ... , parN. Potom se postupně vyhodnocují výrazy uvedené v těle funkce a hodnota posledního z nich je výsledkem aplikace. Po skončení aktivace funkce se zruší lokálně platné vazby argumentů a obnoví se platnost vazeb z nadřazeného prostředí. Příklad: Definice funkce pro test, zda zadaný seznam je prázdný (defun Prazdny (S) (cond ((atom S) (eq S nil)) (T nil)))

- 16 -

Jiří Dvořák


Volné a vázané proměnné

Výrazy v těle definované funkce nemusejí obsahovat jen proměnné reprezentující argumenty funkce, tj. vázané proměnné (tyto proměnné odpovídají v terminologii imperativního programování formálním parametrům funkce). Kromě vázaných proměnných se v těle funkce mohou vyskytovat i tzv. volné proměnné, které jsou vedle argumentů dalším nástrojem komunikace funkce s jejím okolím (tyto proměnné představují v terminologii imperativního programování nelokální proměnné). Rozlišení proměnných na volné a vázané se v Lispu netýká jen definice funkcí pomocí defun, ale také všech dalších lispovských konstrukcí, které zavádějí proměnné s lokálně vymezeným rozsahem platnosti (např. speciální funkce let – viz s. 27). Existují dva způsoby určení vazby volné proměnné: •

Statické určení: Funkce si při své aktivaci přináší vazbu volné proměnné z globálního prostředí.

•

Dynamické určení: Vazba volné proměnné se zjišťuje až v místě volání podle nejblíže nadřazeného prostředí, které tuto volnou proměnnou váže.

Pro Lisp je typické dynamické určení rozsahu, avšak některé varianty Lispu používají statické určení rozsahu, neboť to umožňuje efektivnější kompilaci funkcí. Je třeba poznamenat, že používání volných proměnných je v rozporu se snahami o srozumitelnou a modulární strukturu programů. Příklad: Program pro testování typu vazby volné proměnné: (setq S '(STATICKA)) (defun Pripoj (X) (cons X S))

; S je volna

promenna

(defun Test (S Y) (pripoj Y))

Zkoušku provedeme aplikací funkce Test: (Test 'DYNAMICKA 'VAZBA)

Jiná podoba tohoto programu využívající funkci let je uvedena na str. 27. Programování rekurzivních funkcí

Typické možnosti pro testování triviálních alternativ v definici funkce a pro redukci argumentu v rekurzivním volání: •

Pro číselný argument testujeme rovnost nule nebo jedné, případně i zápornou hodnotu argumentu; do rekurzivní větve dáváme zmenšenou hodnotu argumentu (typicky o hodnotu jedna), obecně hodnotu bližší triviální alternativě.

•

Pro seznam zpracovávaný jen v nejvyšší úrovni testujeme, zda seznam je prázdný a argument redukujeme pomocí cdr. - 17 -

Jiří Dvořák •


Pro obecně strukturovaný S-výraz testujeme většinou jako zvláštní případy prázdný seznam a atom (v tomto pořadí) a argument redukujeme pomocí car i cdr.

Příklady: •

Definice funkce pro výpočet faktoriálu (defun Faktorial (N) (cond ((= N 0) 1) (T (* N (Faktorial (- N 1)))) ))

•

Definice funkce pro spojení dvou seznamů (defun Spoj (X Y) (cond ((Prazdny X) Y) (T (cons (car X) (spoj (cdr X) Y))) ))

•

Definice funkce pro testování shodnosti S-výrazů (defun Stejne (X Y) (cond ((atom X) (cond ((atom Y) (eq X Y)) (T nil))) ((atom Y) nil) ((stejne (car X) (car Y)) (stejne (cdr X) (cdr Y))) (T nil)))

Úlohy na procvičení

a) Definujte funkci pro výpočet absolutní hodnoty zadané proměnné (viz s. 82). b) Definujte funkci pro určení maxima ze dvou čísel (viz s. 82). c) S využitím funkce prázdný definujte funkci pro výpočet délky seznamu, tj. počtu prvků na nejvyšší úrovni (viz s. 82). d) S využitím funkce prázdný definujte funkci pro získání posledního prvku na nejvyšší úrovni seznamu (viz s. 82). e) S využitím funkce prázdný definujte funkci pro odstranění posledního prvku na nejvyšší úrovni seznamu (viz s. 82).

- 18 -

Jiří Dvořák


2.6 Funkce pro zpracování seznamů Funkce append (append seznam-forma1 ... seznam-formaN)

Funkce append může mít proměnný počet argumentů. Hodnotami argumentů musejí být seznamy a výsledkem je seznam vzniklý spojením těchto seznamů. Při provedení funkce append se tolikrát provede primitivní konstruktor cons, kolik činí součet délek seznamů ve všech argumentech kromě posledního. (append '(A B) '(C D)) ⇒ (A B C D) Funkce list (list forma1 ... formaN)

Funkce list může mít rovněž proměnný počet argumentů, ale jejich hodnotami mohou být libovolné S-výrazy. Výsledkem je seznam těchto S-výrazů. Jedno provedení funkce list má za následek tolik aplikací primitivního konstruktoru cons, kolik má list argumentů. (list '(A B) '(C D)) ⇒ ((A B) (C D))

Příklad: Aplikace funkcí append a list pro obrácení pořadí prvků seznamu na nejvyšší úrovni (funkce prazdny byla definována na str. 16). (defun obraceni (x) (cond ((prazdny x) nil) (t (append (obraceni (cdr x)) (list (car x)) )))) Funkce last (last seznam-forma)

Funkce last má jeden argument, jehož hodnotou musí být seznam. Výsledkem je seznam obsahující pouze poslední prvek seznamu v argumentu. (last '(A B C))

⇒ (C)

(last '((A B) (C D))) ⇒ ((C D)) Funkce length (length seznam-forma)

Funkce length má jeden argument, jehož hodnotou musí být seznam. Výsledkem je počet prvků na nejvyšší úrovni seznamu v argumentu. (length '(A B C))

⇒ 3

(length '((A B) (C D))) ⇒ 2

- 19 -

Jiří Dvořák


Funkce reverse (reverse seznam-forma)

Funkce reverse má jeden argument, jehož hodnotou musí být seznam. Výsledkem je obrácený seznam, přičemž obracení se týká pouze nejvyšší úrovně seznamu a nižší vrstvy zůstávají nedotčeny. ⇒ (C B A)

(reverse '(A B C))

(reverse '((A B) (C D))) ⇒ ((C D) (A B))

2.7 Predikátové funkce Funkce equal (equal forma1 forma2)

Funkce equal má dva argumenty, jejichž hodnotami mohou být libovolné S-výrazy. Pokud jsou shodné, výsledkem je T, v opačném případě je výsledkem nil. (setq X '(A B C))

⇒ (A B C)

(equal X X))

⇒ T

(equal X '(A B C))) ⇒ T (equal X 'X))

⇒ nil

(equal 'X 'X))

⇒ T

Funkce null (null seznam-forma)

Funkce null má jeden argument, jehož hodnotou by měl být seznam. Pokud je tento seznam prázdný, výsledkem je T, v opačném případě je výsledkem nil. (setq X '(A))

⇒ (A)

(null X)

⇒ nil

(null '())

⇒ T

(null (car X)) ⇒ nil (null (cdr X)) ⇒ T Funkce member (member forma seznam-forma)

Funkce member má dva argumenty. Hodnotou prvého je libovolný S- výraz a hodnotou druhého musí být seznam. Funkce testuje existenci S-výrazu na nejvyšší úrovni seznamu. V případě úspěchu vrací nikoli hodnotu T, ale část seznamu začínající tímto S-výrazem. Při neúspěchu vrací samozřejmě nil.

- 20 -

Jiří Dvořák


(setq X '(C A D (B D) A)) ⇒ (C A D (B D) A) (member 'A X))

⇒ (A D (B D) A)

(member 'B X))

⇒ nil

(member '(B D) X))

⇒ ((B D) A)

Funkce listp (listp forma)

Funkce listp má jeden argument. Tato funkce testuje, zda hodnotou argumentu je seznam. (setq X '(A B C))

⇒ (A B C)

(listp X)

⇒ T

(listp (car X))

⇒ nil

(listp (cdr X))

⇒ T

Funkce numberp (numberp forma)

Funkce numberp má jeden argument a testuje, zda hodnotou tohoto argumentu je číslo. (setq X '(A 1 2))

⇒ (A 1 2)

(numberp (car X))

⇒ nil

(numberp (car (cdr X))) ⇒ T Funkce symbolp (symbolp forma)

Funkce symbolp má jeden argument a testuje, zda jeho hodnotou je symbol. (setq X '(A 1 2))

⇒ (A 1 2)

(symbolp (car X))

⇒ T

(symbolp (car (cdr X))) ⇒ nil Funkce boundp (boundp forma)

Funkce boundp má jeden argument, jehož hodnotou by měl být symbolický atom. Pokud je na tento atom navázána hodnota, funkce vrací T, jinak vrací nil. (setq X '(A B C))

⇒ (A B C)

(boundp X)

⇒ T

(boundp (car X))

⇒ nil - 21 -

Jiří Dvořák


Funkce pro porovnávání s nulou (zerop forma)

Funkce zerop má jeden argument, jehož hodnotou by mělo být číslo. Tato funkce testuje, zda hodnota argumentu je rovna nule. (plusp forma)

Funkce plusp má jeden argument, jehož hodnotou by mělo být číslo. Tato funkce testuje, zda hodnota argumentu je kladná. (minusp forma)

Funkce minusp má jeden argument, jehož hodnotou by mělo být číslo. Tato funkce testuje, zda hodnota argumentu je záporná. Příklady: (setq X -5 Y 7)

⇒ 7 ⇒ nil

(zerop X)

(zerop (+ X 5)) ⇒ T

⇒ nil

(plusp X)

(plusp (+ X Y)) ⇒ T (minusp X)

⇒ T

(minusp (+ X Y)) ⇒ nil Funkce not (not forma)

Tato funkce je v podstatě synonymem pro predikát null. Je však doporučeno ji používat jako zdůraznění, že se nejedná o testování konce seznamu, ale o logickou negaci (v lispovském pojetí). Platí: (not nil) => T (not x)

=> nil pro x ≠ nil

Příklady: (setq X '(A B C))

⇒ (A B C)

(not (member 'B X)) ⇒ nil (not (member 'D X)) ⇒ T Funkce and a or

Predikáty and a or jsou speciální funkce zajišťující výpočet logického součinu a logického součtu svých argumentů v lispovské interpretaci. - 22 -

Jiří Dvořák


(and forma1 … formaN)

Funkce and vyhodnocuje své argumenty tak dlouho, až narazí na prvý s hodnotou ni1 a pak vrátí nil. Jinak vyhodnotí všechny argumenty a vrací hodnotu posledního. (or forma1 … formaN)

Funkce or vyhodnocuje své argumenty tak dlouho, až narazí na prvý s hodnotou různou od ni1 a jeho hodnotu pak vrátí jako výsledek. Jinak vyhodnotí všechny argumenty a vrátí nil. Z uvedeného popisu vyplývá, že tyto speciální funkce vyhodnotí vždy jen tolik argumentů, kolik je zapotřebí k určení výsledku. Příklady: (setq X '(A B C D))

⇒ (A B C D)

(and (member 'B X) (member 'C X)) ⇒ (C D) (and (member 'A X) (member 'F X)) ⇒ nil (or (member 'B X) (member 'C X)) ⇒ (B C D) (or (member 'E X) (member 'F X)) ⇒ nil Úlohy na procvičení

a) Pomocí základních funkcí a funkcí null a equal definujte funkci pro test, zda S-výraz X je prvkem seznamu S na nejvyšší úrovni (viz s. 82).

2.8 Vyhodnocovací funkce Funkce eval (eval forma)

Funkce eval je základem vyhodnocovacího systému Lispu. Tato funkce má jediný argument a pokud je použita v explicitním volání, dojde ke dvojímu vyhodnocení tohoto argumentu: poprvé se vyhodnotí jako argument kterékoliv jiné funkce, získaná hodnota se pak předá funkci eval a ta ji pak vyhodnotí znovu. Hodnota argumentu funkce eval musí mít jeden z těchto tvarů: •

číselný atom – eval vrátí totéž číslo

•

symbolický atom – eval vrátí hodnotu vázanou na toto jméno

•

seznam tvaru (f al a2 ... an), kde f je jméno funkce a každé aj lze opět vyhodnotit

Prostřednictvím funkce eval dostává programátor velmi mocný nástroj: může totiž dynamicky vytvořit určitou část programu a takto vytvořenou část bezprostředně jako program vyhodnotit. Příklad: (setq A 'B B 'C) ⇒ C

- 23 -

Jiří Dvořák


(eval 'A)

⇒ B

(eval A)

⇒ C

(setq X '(A B) Y '(1 2 3) Z '(X Y)) ⇒ (X Y) (eval (cons 'append Z))

⇒ (A B 1 2 3)

Funkce apply

Při vyhodnocení zápisu funkce v Lispu se vyhodnotí její argumenty, z jejich hodnot se udělá seznam a ten se předá k aplikaci. Ta část vyhodnocovacího systému, která aplikaci funkce provádí, je v Lispu k dispozici prostřednictvím funkce apply. (apply funkce-forma seznam-forma)

Funkce apply má dva argumenty. Hodnotou prvého argumentu musí být jméno funkce a hodnotou druhého musí být seznam hodnot jejích argumentů. Platí vztah (apply 'fce '(val1 val2 … valn)) = (fce arg1 arg2 … argn)

kde vali je hodnota argumentu argi. (apply 'cons '(A (B C))) ⇒ (A B C) Funkce funcall (funcall funkce-forma forma1 … formaN)

Tímto zápisem se zajistí aplikace funkce, která je hodnotou výrazu funkce-forma, na argumenty vypočtené jako hodnoty výrazů forma1, … , formaN. (funcall 'cons 'A '(B C)) ⇒ (A B C)

2.9 Řídicí programové struktury Spolu s funkcí cond je v Lispu základním nástrojem pro řízení výpočtu rekurze (viz str. 17). Použití rekurze má ovšem jisté nevýhody. Při rekurzivním volání funkcí dochází ke větší spotřebě strojového času, než kolik by potřeboval odpovídající iterační algoritmus. Dále jsme v tomto případě při výpočtu i té nejjednodušší rekurzivně definované funkce omezeni maximální kapacitou zásobníku, pomocí něhož systém provádí rekurzivní volání. Iterativní verze mají při výpočtu konstantní paměťové nároky a podobné nebezpečí u nich tedy nehrozí. Pokud je to možné, je vhodné používat koncovou rekurzi (viz str. 6), protože řada překladačů Lispu dovede automaticky převést koncovou rekurzi na iteraci. Příklady použití koncové rekurze: •

Obrácení pořadí prvků seznamu (defun obraceni_kr (x) (obrat x nil))

- 24 -

Jiří Dvořák


(defun obrat (sez revs) (cond ((null sez) revs) (t (obrat (cdr sez) (cons (car sez) revs))) ))

•

Délka seznamu (defun delka_kr (x) (delkr x 0)) (defun delkr (x pocet) (cond ((null x) pocet) (t (delkr (cdr x) (+ 1 pocet))) ))

Z důvodů možných problémů s použitím rekurze je i jazyk Lisp vybaven prostředky dovolujícími explicitní používání iteračních konstrukcí, přestože neodpovídají klasickému funkcionálnímu stylu. Speciální funkce do (do

((var1 ini-forma1 opak-forma1)

; předpisy pro práci

(var2 ini-forma2 opak-forma2)

; s proměnnými cyklu

... (varN ini-formaN opak-formaN)) (test výraz1 výraz2 ... výrazK)

; testovací klauzule

forma1

; tělo cyklu

forma2 ... formaM )

Výrazy opak-forma mohou být vynechány, výrazy ini-forma mohou být vynechány pouze současně s odpovídajícími výrazy opak-forma. Vynechány mohou být také výrazy test a současně výraz1 až výrazK v testovací klauzuli nebo výrazy forma1 až formaM v těle cyklu do. Vyhodnocení formy do: 1. Vyhodnotí se všechny výrazy ini-forma určující počáteční hodnoty proměnných cyklu. 2. Výsledné hodnoty se navážou na proměnné; kde hodnota nebyla uvedena, dosadí se nil. 3. Je-li testovací klauzule neprázdná, vyhodnotí se test; a) je-li úspěšný, vyhodnotí se postupně všechny výrazy v klauzuli, cyklus se ukončí a výsledkem je hodnota posledního výrazu, b) je-li neúspěšný, pokračuje se krokem 5. 4. Je-li testovací klauzule prázdná, cyklus končí s hodnotou nil. 5. Vyhodnotí se postupně všechnu formy těla cyklu. 6. Vyhodnotí se všechny části opak-forma. - 25 -

Jiří Dvořák


7. Hodnoty získané v kroku 6 se navážou na příslušné proměnné. 8. Pokračuje se krokem 3. Je důležité si uvědomit, že vyhodnocení výrazů předepisujících počáteční nebo změnové hodnoty proměnných cyklu se provádí dříve, než se jakákoliv z těchto hodnot naváže na příslušnou proměnnou, tedy vlastně jakoby paralelně. Chování cyklu tudíž vůbec nezávisí na pořadí, v jakém na začátku cyklu uvedeme jednotlivé proměnné. Příklad: Obrácení pořadí prvků seznamu pomocí iterace (defun obraceni_i (x) (do ((sez x (cdr sez)) (revs nil (cons (car sez) revs))) ((null sez) revs) )) Speciální funkce dolist a dotimes (dolist (var list-forma result-forma) forma1 ... formaN)

Při vyhodnocování se na proměnnou var postupně navazují jednotlivé prvky seznamu, který se dostane vyhodnocení výrazu list-forma, přičemž pro každou hodnotu se provede vyhodnocení všech forem těla cyklu. Výsledná hodnota je pak určena hodnotou formy result-forma. (dotimes (var pocet-forma result-forma) forma1 ... formaN)

Při vyhodnocování se proměnné var postupně přiřazují hodnoty od 0 do hodnoty počet-forma – 1, přičemž pro každou hodnotu se provede vyhodnocení všech forem těla cyklu. Výsledná hodnota je pak určena hodnotou formy result-forma. Příklady: •

Sečtení prvků číselného seznamu pomocí dolist (defun sum-list (num-list) (setq s 0) (dolist (p num-list s) (setq s (+ s p))))

•

Výpočet faktoriálu pomocí dotimes (defun fakt (n) (setq m 1) (dotimes (i n m) (setq i (+ i 1)) (setq m (* m i))))

- 26 -

Jiří Dvořák


Speciální funkce typu prog (prog1 výraz1 výraz2 ... výrazN) (prog2 výraz1 výraz2 ... výrazN) (progn výraz1 výraz2 ... výrazN) (progv (var1 var2 ... varN) (exp1 exp2 ... expN) forma1 forma2 ... formaM)

Funkce prog1, prog2 a progn vyhodnotí postupně své argumenty; prog1 vrací hodnotu prvního výrazu, prog2 vrací hodnotu druhého a progn vrací hodnotu posledního. Všechny tyto funkce tedy vytvářejí obdobu složeného příkazu jazyka Pascal. Funkce progv nejprve vyhodnotí všechny výrazy exp1 až expN, pak naváže jejich hodnoty na odpovídající proměnné, a potom postupně vyhodnocuje výrazy forma1 až formaM. Výsledkem je hodnota poslední formy. Kromě uvedených funkcí existuje také speciální funkce prog, jejíž tělo je obdobou imperativního programu. V těle této funkce se dokonce může objevit funkce go, umožňující nepodmíněný skok. Speciální funkce let (let ((var1 ini-forma1) (var2 ini-forma2) ... (varN ini-formaN)) forma1 forma2 ... formaM)

Var je symbolický atom označující zaváděnou lokální proměnnou a ini-forma je (počáteční) hodnota této proměnné. Je také možné inicializační výraz vůbec neuvést a příslušná proměnná má pak počáteční hodnotu nil. Nejprve se vyhodnotí všechny výrazy ini-forma a teprve pak se provede jejich přiřazení proměnným (na pořadí proměnných tedy nezáleží). Potom se postupně vyhodnotí forma1 až formaM, přičemž výsledkem je hodnota poslední formy. Příklad: Program pro test typu vazby volné proměnné (viz str. 17) s použitím funkce let: (setq S '(STATICKA)) (defun Pripoj (X) (cons X S))

; S je volna

(defun Test (Y) (pripoj Y)) (let ((S 'DYNAMICKA)) (Test 'VAZBA))

- 27 -

promenna

Jiří Dvořák



a) Definujte funkci pro výpočet faktoriálu pomocí koncové rekurze (viz s. 83). b) Definujte funkci pro výpočet faktoriálu pomocí iterace (viz s. 83). c) Definujte funkci pro sečtení prvků číselného seznamu pomocí iterace (viz s. 83).

2.10 Mapovací funkcionály Často je zapotřebí aplikovat nějakou funkci na všechny prvky seznamu. Pro takovéto účely je výhodné používat mapovací funkcionály. Funkcionál mapcar (mapcar funkce-forma seznam-forma1 ... seznam-formaN)

Funkcionál mapcar aplikuje funkci, která je hodnotou výrazu funkce-forma na jednotlivé (stejnolehlé) prvky seznamů (tyto seznamy jsou hodnotami forem seznam-forma) a vrací seznam výsledků. (mapcar '+ '(1 2 3) '(3 2 1)) ⇒ (4 4 4) (mapcar (car '(cons list)) '(A B C) '(D E F))

⇒ ((A.D) (B.E) (C.F)) (mapcar (cadr '(cons list)) '(A B C) '(D E F))

⇒ ((A D) (B E) (C F)) Pozn.: (cadr x) ≡ (car (cdr x)) Příklad: Určení počtu atomů na všech úrovních seznamu pomocí apply a mapcar. (defun PocetAtomu (S) (cond ((null S) 0) ((atom S) 1) (T (apply '+ (mapcar 'PocetAtomu S))) )) Funkcionál mapc (mapc funkce-forma seznam-forma1 ... seznam-formaN)

Funkcionál mapc aplikuje funkci na jednotlivé (stejnolehlé) prvky seznamů a vrací triviální hodnotu (zpravidla nil nebo první seznam). Funkcionál maplist (maplist funkce-forma seznam-forma1 ... seznam-formaN)

Funkcionál maplist aplikuje funkci na celé seznamy, pak na jejich zbytky atd., a vrací seznam výsledků.

- 28 -

Jiří Dvořák


(maplist 'cons '(A B C) '(D E F))

⇒ (((A B C).(D E F)) ((B C).(E F)) (C.F)) (maplist 'append '(A B C) '(D E F))

⇒ ((A B C D E F) (B C E F) (C F)) Funkcionál mapl (mapl funkce-forma seznam-forma1 ... seznam-formaN)

Funkcionál mapl aplikuje funkci na celé seznamy, pak na jejich zbytky atd., a vrací triviální hodnotu (zpravidla nil nebo první seznam). Lambda výraz

Ve spojení s mapovacími funkcionály se často používají anonymní funkce zavedené pomocí lambda výrazů. (lambda (par1 par2 ... parN) výraz1 výraz2 ... výrazM)

Lambda-výraz představuje nepojmenovanou funkci. Seznam parametrů (lambda-seznam) určuje, jaké jsou vázané proměnné této funkce. Na ně se při aplikaci navážou hodnoty argumentů a pak se postupně vyhodnotí výrazy výraz1, výraz2, ... , výrazM. Výsledná hodnota je určena hodnotou posledního výrazu. Lambda-výraz využíváme buď pro zavedení anonymní funkce v místě jejího použití nebo jako prostředek lokálního přizpůsobení počtu argumentů nějaké funkce (a fixaci zbývajících). Příklad: Přičtení skaláru ke každému prvku vektoru pomocí lambda a mapcar. (defun PrictiSkalar (Skalar Vektor) (mapcar '(lambda (X) (+ Skalar X)) Vektor))

Poznamenejme, že v některých implementacích Lispu je nutno před lambda výraz psát místo apostrofu dvojici znaků #'. (mapcar #'(lambda (X) (+ Skalar X)) Vektor))

Tato dvojice znaků má stejný účel jako samotný apostrof, tj. zabraňuje vyhodnocení následujícího S-výrazu, a používá se tehdy, jestliže následující S-výraz představuje funkci.

2.11 Definice a vyhodnocení maker Předpokládejme, že často potřebujeme navázat na nějakou proměnnou hodnotu nil a tudíž pro tento účel definujeme funkci: (defun Niluj (Arg) (setq Arg nil))

- 29 -

Jiří Dvořák


Pokusme se nyní tuto funkci aplikovat: (Niluj X) ⇒ Chyba, nenavazana promenna

Při aplikaci funkce Niluj se nejprve totiž vyhodnotí její argument. Protože na X dosud nebyla navázána žádná hodnota, je signalizována chyba. Zkusme nyní ověřit, co by se dělo, kdyby na X nějaká hodnota už navázána byla: (setq X 99) ⇒ 99

⇒ nil

(Niluj X)

⇒ 99

X

Vidíme, že ani teď to nefunguje. Hodnota nil se totiž v rámci funkce Niluj naváže na lokální proměnnou Arg, kdežto proměnná X zůstane beze změny. Pro řešení takovýchto situací v Lispu existují makra, která na rozdíl od funkcí poskytují jiný mechanismus vyhodnocení své aplikace. Speciální funkce defmacro (defmacro jméno-makra (par1 par2 ... parN) výraz1 výraz2 ... výrazM)

Při vyhodnocení aplikace makra se na parametry makra navážou nevyhodnocené argumenty a pro ně se provede vyhodnocení jednotlivých výrazů v rámci prostředí, v němž se nachází definice makra. Tato první etapa vyhodnocení se nazývá expanze makra a jejím výsledkem je hodnota posledního výrazu z těla definice makra. Výsledek expanze se pak opět považuje za E-výraz a ten se ve druhé etapě znovu vyhodnotí, tentokrát ale v prostředí místa aplikace makra. Definice a použití operace Niluj jako makra vypadá následovně: (defmacro Niluj (Arg) (list 'setq Arg nil)) ⇒ Niluj (Niluj X)

⇒

(setq X nil) ⇒ nil

expanze

X ⇒ nil

Jiným příkladem aplikace makra jsou aplikace zásobníkových operací. Předpokládejme, že zásobník je implementován jako seznam, přičemž začátek seznamu představuje vrchol zásobníku. V následujícím příkladě je definována operace vložení prvku na vrchol zásobníku. Příklad: (defmacro Push (Element Stack) (list 'setq Stack (list 'cons Element Stack)))

- 30 -

Jiří Dvořák


(Push X Z)

⇒

(setq Z (cons X Z))

expanze

Aby se zkrátila a zjednodušila definice makra, byl zaveden mechanismus obráceného apostrofu, který nahrazuje použití funkce list. Obrácený apostrof funguje jako normální apostrof (tj. zabraňuje vyhodnocování) s tím, jakákoli čárka, která se vyskytne uvnitř jeho rozsahu, zruší jeho účinek (tj. povolí vyhodnocení) pro následující S-výraz. Výše definovaná makra můžeme pomocí této notace zapsat takto: (defmacro Niluj (Arg) ‘(setq ,Arg nil)) (defmacro Push (Element Stack) ‘(setq ,Stack (cons ,Element ,Stack)))

2.12 Modifikace struktur Ve striktně chápaném funkcionálním programování se datové struktury pouze vytvářejí a jako celek pak mohou být zařazovány do vyšších struktur nebo být zrušeny, nelze je však měnit. Každá modifikace struktury znamená v takovém případě její kompletní rekonstrukci (tj. nové vytvoření), i když se bude lišit např. jen v záměně jednoho atomu za jiný. Tento přístup by v praktických aplikacích mohl vést k neúnosným časovým nárokům nebo ke zbytečnému čerpání buněk volné paměti (což se v konečném efektu projeví mimo jiné opět zpomalením výpočtu). Jazyk Lisp proto dává uživateli možnost modifikovat existující datové struktury. Funkce rplaca a rplacd

Názvy těchto pseudofunkcí jsou odvozeny z anglických výrazů „replace car“ a „replace cdr“, které vyjadřují jejich sémantiku. (rplaca forma-tečka-dvojice forma-nový-car)

Tato funkce modifikuje 1. část tečky-dvojice, která je hodnotou prvého argumentu tak, že do ní uloží odkaz na hodnotu druhého argumentu. Dojde tedy k náhradě prvního prvku tečky-dvojice za jiný, ale nestane se tak vytvořením nové tečky-dvojice, nýbrž modifikací původní struktury. (rplacd forma-tečka-dvojice forma-nový-cdr)

Tato funkce modifikuje 2. část tečky-dvojice, která je hodnotou prvého argumentu tak, že do ní uloží odkaz na hodnotu druhého argumentu. Příklady: (setq X '(A B C))

⇒ (A B C)

(setq Y '(1))

⇒ (1)

(rplaca X Y)

⇒ ((1) B C)

X

⇒ ((1) B C)

(rplacd Y (cdr X)) ⇒ (1 B C)

- 31 -

Jiří Dvořák


Y

⇒ (1 B C)

X

⇒ ((1 B C) B C)

Funkce nconc (nconc seznam-forma1 … seznam-formaN)

Funkce nconc může mít proměnný počet argumentů. Hodnotami argumentů musejí být seznamy a výsledkem je seznam vzniklý jejich spojením. Přitom se změní struktura všech těchto seznamů kromě posledního, což se projeví také ve všech strukturách, do nichž byly příslušné seznamy dříve začleněny. Příklady: (setq X '(A B))

⇒ (A B)

(setq Y '(C D))

⇒ (C D)

(setq Z '(E F))

⇒ (E F)

(setq P (cons X Y)) ⇒ ((A B) C D) (nconc X Y Z)

⇒ (A B C D E F)

X

⇒ (A B C D E F)

Y

⇒ (C D E F)

Z

⇒ (E F)

P

⇒ ((A B C D E F) C D E F)

Funkce setf (setf forma1 forma2)

Funkce setf má dva argumenty. První musí určovat nějaké „místo“ a druhý určuje hodnotu, která se na toto „místo“ dosadí. Následující zápisy jsou tedy sémanticky ekvivalentní: (rplaca X Y) ≡ (setf (car X) Y) (rplacd X Y) ≡ (setf (cdr X) Y)

Příklady: (setq X cons 'A 'B)) ⇒ (A.B) X (setf (car X) 'C)) X (setf (cdr X) 'D)) X

⇒ (A.B) ⇒ C ⇒ (C.B) ⇒ D ⇒ (C.D)

- 32 -

Jiří Dvořák


Funkcionály mapcan a mapcon (mapcan funkce-forma seznam-forma1 … seznam-formaN)

Funguje jako funkcionál mapcar, ale vrací seznam vzniklý spojením dílčích výsledků pomocí funkce nconc. (mapcon funkce-forma seznam-forma1 … seznam-formaN)

Funguje jako maplist, ale vrací seznam vzniklý spojením dílčích výsledků pomocí funkce nconc.

2.13 Reprezentace atomů Při grafickém znázornění paměťové reprezentace symbolických výrazů Lispu je odkaz na atom vyjadřován šipkou směřující ke jménu daného atomu. Zdálo by se, že k paměťové reprezentaci symbolického atomu bude stačit uložení příslušné posloupnosti znaků. Jméno je však pouze jednou z tzv. vlastností atomu a každý symbolický atom může mít teoreticky libovolný počet vlastností. Některé z vlastností atomu vyhodnocovací systém Lispu vytváří a využívá automaticky při zpracování programu a takové vlastnosti označujeme jako standardní. Vedle standardních vlastností může uživatel přiřadit atomu libovolné další vlastnosti a využívat je podle vlastní úvahy. To spolu s jednoznačnou reprezentací symbolických atomů v Lispu poskytuje zcela nové programovací možnosti, které tvoří základ pro daty řízené programování a objektově orientované programování. Seznam vlastností atomu

K reprezentaci symbolického atomu slouží seznam vlastností atomu (property-list, zkráceně Pseznam), který má následující strukturu: (ind1 hodn1 ind2 hodn2 … indN hodnN)

kde ind označuje indikátor vlastnosti a hodn její hodnotu. Reprezentace atomu v paměti je tedy obdobná jako reprezentace neatomických S-výrazů a je založena na využití cons-buněk. Pseznam nelze ovšem chápat jako obyčejný seznam, neboť je to vnitřní reprezentace atomu, a pro práci s ním je tedy nutno používat speciální funkce. Struktura reprezentující symbolický atom se vytvoří při prvním výskytu daného atomu v programu nebo v datech, a od té chvíle se každý další výskyt vyjádří odkazem na tuto jedinou reprezentaci. Přestože všechny výskyty daného atomu reprezentuje jediná paměťová struktura, neznamená to, že tato struktura zůstává během výpočtu neměnná. Pro číselné atomy jedinečnost reprezentace neplatí. Protože číselný atom představuje pouze příslušnou číselnou hodnotu, týká se možnost existence různých vlastností pouze symbolických atomů. Příklady standardních vlastností atomů: •

PNAME – hodnotou je řetězec znaků tvořící jméno atomu (print-name).

•

APVAL – slouží pro uložení hodnoty navázané na proměnnou

- 33 -

Jiří Dvořák


•

EXPR

– slouží k uložení uživatelské definice funkce; její hodnotou je příslušný lambdavýraz.

•

SUBR

– slouží k uložení odkazu na funkci ve strojovém kódu.

•

FEXPR – charakterizuje atom jako speciální funkci a za hodnotu má příslušnou lambdadefinici.

•

FSUBR – charakterizuje atom jako standardní speciální funkci a za hodnotu má odkaz na její realizaci ve strojovém kódu.

Tentýž atom může být vázanou proměnnou i jménem funkce a kontext jeho použití rozhoduje, kterou interpretaci systém Lisp zvolí. Vlastnosti EXPR a FEXPR (a ovšem též SUBR a FSUBR) se u jednoho atomu nemohou vyskytovat současně. Funkce pro práci se seznamy vlastností (get atom-forma indikátor-forma)

Funkce get má dva argumenty. Hodnotou prvého by měl být atom a hodnotou druhého indikátor vlastnosti (také atom). Tato funkce se používá pro zjištění existence a hodnoty vlastnosti s určeným indikátorem v P-seznamu daného atomu. Pokud tento atom požadovanou vlastnost nemá, je výsledkem nil. (putprop atom-forma hodnota-forma indikátor-forma)

Funkce putprop zajistí uložení hodnoty vlastnosti určené indikátorem vlastnosti do P-seznamu daného atomu. Tato funkce vrací ukládanou hodnotu. (remprop atom-forma indikátor-forma)

Funkce remprop zajistí vypuštění vlastnosti určené indikátorem (včetně její hodnoty) z Pseznamu daného atomu. Tato funkce vrací nil. Příklady: (putprop 'A '(B C) 'SOUSEDE) ⇒ (B C) (get 'A 'SOUSEDE)

⇒ (B C)

V jazyku Common Lisp funkce putprop chybí. Vložení hodnoty do seznamu vlastností se zajišťuje pomocí kombinace funkcí setf a get: (setf (get atom-forma indikátor-forma) hodnota-forma)Hodnotu vlastnosti můžeme do P-seznamu vložit také pomocí kombinace funkcí setf a get: (setf (get 'B 'SOUSEDE) '(A C D)) ⇒ (A C D) (get 'B 'SOUSEDE)

⇒ (A C D)

Pomocí seznamů vlastností můžeme implementovat např. grafovou strukturu. Vrcholy (uzly) grafu mohou být reprezentovány atomy a hrany vlastnostmi sousedé (v případě neorientovaných hran) nebo následníci (v případě orientovaných hran). Jiným příkladem použití seznamů vlastností je implementace rámců (frames), které jsou jedním z prostředků reprezentace znalostí v expertních systémech.

- 34 -

Jiří Dvořák


Funkce gensym (gensym)

Hodnotou aplikace funkce gensym bez argumentů je vygenerovaný atom. Jeho jméno je tvořeno aktuálně platným prefixem (implicitně G) za nímž následuje aktuální pořadové číslo (na počátku obvykle 0). Po každém volání funkce gensym se pořadové číslo zvětšuje, takže je zaručena různost generovaných atomů. (gensym výraz)

Hodnota argumentu určuje jméno generovaného atomu takto: •

je-li hodnotou symbolický atom (v Common Lispu to musí být řetězec), použije se jako prefix generovaného atomu,

•

je-li hodnotou nezáporné celé číslo, použije se jako pořadové číslo generovaného atomu.

2.14 Vstup a výstup Vstup/výstup z/do standardních zařízení (read)

Funkce read přečte ucelený S-výraz a ten vrátí jako výslednou hodnotu. (print výraz) (princ výraz)

Tyto funkce zajistí vypsání hodnotu argumentu (zobrazený S-výraz je současně výslednou hodnotou těchto funkcí). Funkce print pak přejde na nový řádek. Funkce print zobrazí hodnotu argumentu ve tvaru, který je zpětně čitelný pomocí funkce read, kdežto funkce princ potlačuje některé speciální znaky. (terpri)

Funkce terpri ukončí aktuální řádek a vrátí nil. Příklad: (setq x (read)) (print x) Vstup/výstup z/do souboru (open jméno-souboru)

Funkce open zajistí otevření souboru. Jméno souboru je řetězec. Funkce vrací ukazatel na soubor. (close ukazatel-na-soubor)

Funkce close zajistí uzavření souboru. Příklad: (setq f (open "C:/adresar/data.txt")) (close f)

- 35 -

Jiří Dvořák


Výše uvedené funkce read, print, princ, terpri mohou být používány i pro soubory: (read ukazatel-na-soubor) (print výraz ukazatel-na-soubor) (princ výraz ukazatel-na-soubor) (terpri soubor)

Aplikace funkce read může mít i takovouto podobu: (read ukazatel-na-soubor eof-error eof-value)

Je-li argument eof-error různý od nil, je při dosažení konce souboru (eof) signalizována chyba. Má-li tento argument hodnotu nil, pak je při dosažení konce souboru vrácena hodnota určená argumentem eof-value. Příklad: Výpočet součtu čísel ze zadaného souboru. ; Konec souboru je signalizovan symbolem f (defun secti1 (f) (setq s 0) (do ((x (read f nil f) (read f nil f))) ((eq x f) s) (setq s (+ s x)))) ; Konec souboru je signalizovan symbolem nil (defun secti2 (f) (setq s 0) (do ((x (read f nil nil) (read f nil nil))) ((null x) s) (setq s (+ s x)))) Vstup/výstup znaků (read-char) (read-char ukazatel-na-soubor) (read-char ukazatel-na-soubor eof-error eof-value)

Funkce read-char přečte jeden znak a jako výslednou hodnotu vrátí #\znak. (write-char výraz) (write-char výraz ukazatel-na-soubor)

Hodnotou výrazu by měl být znak reprezentovaný trojicí #\znak. Funkce write-char zajistí vypsání tohoto znaku (trojice #\znak je současně výslednou hodnotou této funkce).

- 36 -

Jiří Dvořák


3. Využití jazyka Lisp pro řešení úloh umělé inteligence 3.1 Přehled aplikací Kniha [4] je věnována programování v Lispu a jeho použití pro problémy umělé inteligence. Jsou zde popsány následující programovací techniky UI: •

diskriminační sítě

•

řídicí struktury agendy

•

deduktivní vyhledávání informací

•

produkční systémy

•

backtracking

V knize [13] je ukázáno použití Lispu pro řešení následujících: •

strategie prohledávání

•

porovnávání se vzorem (pattern matching)

•

expertní systémy

•

sémantické sítě

•

strojové učení

Kniha [8] je věnována jazyku Scheme, který je jedním z dialektů Lispu. V kapitole věnované umělé inteligenci jsou popsány tyto problémy: •

prohledávání

•

plánování

•

expertní systémy

•

zpracování přirozeného jazyka

•

robotika

•

rozpoznávání objektů

V knize [2] je ukázáno použití Lispu pro řešení následujících úloh: •

reprezentace znalostí

•

prohledávání

•

mechanismy inference

•

porovnávání se vzorem

•


V knize [24] jsou analyzovány následující problémy. •


- 37 -

Jiří Dvořák


•


•

pravidlové expertní systémy

•

implementace rámců

Kniha [22] uvádí jako příklady aplikací Lispu tyto úlohy: •


•

implementace asociativních databází

Významnou aplikací Lispu je tvorba expertních (znalostních) systémů. Touto problematikou se zabývá např. kniha [23]. V jazyku Common Lisp byl vytvořen např. systém GBB (Generic Blackboard Builder), což je objektově orientované programové prostředí pro vývoj systémů typu tabule. Na Lispu je založený také prázdný expertní systém ART. Další příklady aplikace Lispu je možno nalézt na stránkách následujících firem: •

Franz Inc. Tato firma nabízí Allegro CL, což je dynamické objektově orientované vývojové prostředí pro Common Lisp, a jeho aplikace.

•

Xanalys LispWorks Firma se zabývá vývojem softwaru založeného na jazyce Common Lisp.

3.2 Příklad využití Lispu pro tvorbu expertního systému Následující příklad obsahuje jednoduchý inferenční mechanismus pro případ, že bázi znalostí tvoří seznam pravidel tvaru (rule identifikator (if

podminka1 … podminkaN)

(then zaver1 … zaverM))

Podmínky i závěry mohou být atomy nebo seznamy. Například (rule R1 (if zivocich_ma_peri) (then zivocich_je_ptak))

nebo (rule R1 (if (zivocich ma peri)) (then (zivocich je ptak)))

Závěry pravidel mohou vystupovat jako podmínky v jiných pravidlech. Například (rule R2 (if (zivocich je ptak) (zivocich neleta) (zivocich plave) (zivocich je cerny a bily)) (then (zivocich je tucnak)))

Báze faktů je tvořena seznamem faktů, které mohou mít tyto tvary: (ano podminka) (ne podminka) (ano zaver)

- 38 -

Jiří Dvořák


Fakta mohou být na počátku vložena do seznamu faktů, nebo mohou být v případě potřeby zjišťována dotazem na uživatele. Lze se ovšem ptát pouze na takové věci, které nejsou odvoditelné z jiných pravidel (tj., které se nevyskytují v závěrech jiných pravidel. Příklad inferenčního mechanismu

Uvedený inferenční mechanismus vychází z programu, který je součástí souboru příkladů příslušných k systému Xlisp a je rozšířen o možnost komunikace s uživatelem. ; Funkce testuje, zda se odpoved na danou podmínku nachazi ; v seznamu faktu (defun memb (item list) (cond((null list) nil) ((equal item (car (cdr (car list)))) list) (t (memb item (cdr list))))) ; Funkce pridava zaver do seznamu zaveru, jestlize tam jeste neni (defun remember (newconc) (cond((member newconc conclusions) nil) (t (setq conclusions (cons newconc conclusions))))) ; Funkce pridava fakt do seznamu faktu, jestlize tam jeste neni (defun rememb (newfact) (cond((memb (car (cdr newfact)) facts) nil) (t ( setq facts (cons newfact facts)) newfact))) ; ; ; ; ;

Funkce zjistuje, zda se hodnota podminky (ano/ne) nachazi v bazi faktu. Jestlize se tam nenachazi a nejedna se o zaver jineho pravidla, zjistuje hodnotu dotazem na uzivatele. Funkce vraci hodnotu T (hodnota ano) nebo nil (hodnota ne, nebo se jedna o zaver jineho pravidla a hodnota neni znama).

(defun recall (afact) (setq pom (memb afact facts)) (cond (pom (eq 'ano (car (car pom)))) ((member afact conclusions) nil) (t (terpri) (print (list "Plati " afact "? (ano/ne)")) (cond ((eq (read) 'ano) (rememb (list 'ano afact)) t) (t (rememb (list 'ne afact)) nil))))) ; Funkce testuje, zda jsou splneny vsechny podminky zadane ; v podminkove casti nejakeho pravidla

- 39 -

Jiří Dvořák


(defun testif (iflist) (cond((null iflist) t) ((recall (car iflist)) (testif (cdr iflist))) (t nil))) ; Funkce pridava zavery nejakeho pravidla do seznamu zaveru (defun usethen (thenlist) (cond ((null thenlist) nil) (t (remember (car thenlist)) (usethen (cdr thenlist))))) ; Funkce prochazi seznam pravidel a pridava jejich zavery do ; seznamu zaveru (defun searchrules (listrules) (cond ((null listrules) nil) (t (usethen (cdr(car(cdr(cdr(cdr (car listrules))))))) (searchrules (cdr listrules))))) ; Funkce pridava zavery nejakeho pravidla do seznamu faktu ve ; tvaru (ano zaver) a vraci seznam pridanych zaveru (defun useth (thenlist addlist) (cond ((null thenlist) addlist) ((rememb (list 'ano (car thenlist))) (useth (cdr thenlist) (cons (car thenlist) addlist))) (t (useth (cdr thenlist) addlist)))) ; ; ; ;

Funkce zpracovava dane pravidlo. Pokud jsou splneny vsechny podminky, pridava zavery do seznamu faktu (pokud tam jeste nejsou). Skutecne pridane zavery jsou pak vypisovany na obrazovku.

(defun tryrule (rule) (setq ifrules (cdr(car(cdr(cdr rule))))) (setq thenlist (cdr(car(cdr(cdr(cdr rule)))))) (setq addlist nil) (cond (( testif ifrules) (cond ((setq addlist (useth thenlist addlist)) (terpri) (print (list "Rule " (car(cdr rule)) "Deduced " addlist)) t) (t nil))) (t nil)))

- 40 -

Jiří Dvořák


; Funkce postupne zpracovava jednotliva pravidla dokud neodvodi ; nejake nove zavery (pak vraci hodnotu T) nebo dokud nevycerpa ; seznam pravidel (pak vraci nil). (defun stepforward (rulelist) (cond((null rulelist) nil) ; all done ((tryrule (car rulelist)) t) (t (stepforward(cdr rulelist))))) ; ; ; ;

Funkce prochazi seznam pravidel a zpracovava jednotliva pravidla. Jestlize byly odvozeny nejake nove zavery, pokracuje v prochazeni znovu od zacatku. Jestlize pri poslednim pruchodu zadne nove zavery odvozeny nebyly, vraci hodnotu T.

(defun deduce () (cond((stepforward rules) (deduce)) (t t))) ; Funkce vytvori seznam zaveru pravidel a zahajuje proces reseni (defun start () (searchrules rules) (deduce)) ; Inicializace (setq conclusions nil) (setq facts nil) ; zde je mozno vlozit seznam vychozich faktu do promenne facts ; (setq facts '(fact1 fact2 ... )) ; Zde je nutno vlozit seznam pravidel do promenne rules ; (setq rules '(rule1 rule2 ... ))

- 41 -

Jiří Dvořák


4. Prolog Prolog znamená programování v logice a je vyústěním snahy o použití logiky jako programovacího jazyka. Ve srovnání s ostatními programovacími jazyky přinesl Prolog tuto změnu programovacího stylu: namísto otázky, JAK se má získat výsledek, se uživatel zajímá o to, CO platí mezi objekty, s nimiž jeho program pracuje (tím se Prolog podobá specifikačním jazykům). Prolog je tedy vhodným prostředkem pro řešení takových úloh, ve kterých zkoumáme vztahy mezi objekty. Podobně jako v Lispu můžeme za základ systému Prolog považovat jakýsi univerzální vyhodnocovací systém (interpret). Namísto definic funkcí dostává tento systém definice relací (vztahů), kterými dotváří své pracovní prostředí. Toto prostředí spolu se standardním odvozovacím mechanismem pak systém používá při zodpovídání dotazů uživatele na platnost nebo neplatnost konkrétních případů vztahů mezi objekty. Historie jazyka Prolog: •

A. Colmerauer a P. Roussel (Universita v Marseille, 1972): Prvá verze Prologu jako prostředek pro efektivní odvozování důsledků z určité třídy formulí predikátové logiky.

•

R. Kowalski (1974): Teoretický model Prologu na základě procedurální implementace Hornových klauzulí.

•

D. Warren (Edinburgh, 1974): Efektivní implementace na počítači DEC-10; zahájení éry překladačů Prologu.

•

Japonský projekt počítačů 5.generace (1981): Prolog zvolen jako základní jazyk logického procesoru centrální jednotky počítače; vyvolání vlny zájmu o Prolog a metody logického programování.

Implementace jazyka Prolog: •

Amzi! Logic Explorer

•

LPA Prolog

•

Quintus Prolog

•

SICStus Prolog 3

•

Strawberry Prolog

•

SWI-Prolog

•

Visual Prolog

V této kapitole jsou podány pouze základy jazyka Prolog. Podrobněji je možné se s tímto jazykem seznámit v knihách [1], [3], [5], [6], [9], [17], [19], [20].

4.1 Charakteristika a příklad programu Program v Prologu sestává z klauzulí. Existují tři typy klauzulí: fakta, pravidla a dotazy. Klauzule definující stejnou relaci vytvářejí tzv. proceduru. Definice vztahů vyjádřené fakty a pravidly se po zadání stávají součástí pracovního prostředí Prologu nazývaného databáze.

- 42 -

Jiří Dvořák


Pravidla vyjadřují tvrzení závislá na splnění nějakých podmínek. Každé pravidlo má hlavu a (neprázdné) tělo, které je konjunkcí cílů. Fakta se používají k vyjádření bezpodmínečně pravdivých tvrzení. Fakta jsou klauzule s hlavou, ale s prázdným tělem. Dotazy vyvolávají výpočet programu; jeho smyslem je zjistit, zda nějaké tvrzení platí či nikoliv. Každý dotaz je klauzule bez hlavy.

Zodpovězení dotazu probíhá postupným ověřováním splnitelnosti jednotlivých cílů. Je-li výsledek vyhodnocení cíle kladný, říkáme, že cíl byl úspěšný (uspěl) a že je splnitelný. V případě záporného výsledku říkáme, že cíl byl neúspěšný (neuspěl, selhal) a že je nesplnitelný. Během procesu vyhodnocení cíle (dotazu) dochází v případě úspěchu k nastavení proměnných na takové hodnoty, které umožní jeho splnitelnost. Je-li více možností, jak dosáhnout splnění cíle, Prolog je schopen je všechny zjistit pomocí postupu nazývaného zpětné prohledávání (backtracking). Neúspěch při vyhodnocení cíle neznamená, že Prolog dokázal jeho neplatnost, ale pouze to, že nebyl schopen ze své databáze dokázat jeho platnost. Často se pro úvod do Prologu požívá příklad rodinných vztahů. Uvažujme část rodokmenu nějaké rodiny, uvedenou na obr. 4.1.

Vladislav

Ludvík

Johana

Anna

Ferdinand

Karel

Maxmilián

Marie

Rudolf

Matyáš

Obr. 4.1. Příklad rodinných vztahů V Prologu můžeme tyto rodinné vztahy zapsat takto: rodic(vladislav,ludvik). rodic(vladislav,anna).

- 43 -

Jiří Dvořák


rodic(johana,ferdinand). rodic(johana,karel). rodic(anna,maxmilian). rodic(ferdinand,maxmilian). rodic(karel,marie). rodic(maxmilian,rudolf). rodic(maxmilian,matyas). rodic(marie,rudolf). rodic(marie,matyas).

Z hlediska syntaxe Prologu se jedná o fakta. Souhrn těchto faktů definuje vztah rodic. Zápis rodic(x, y) zde interpretujeme tak, že x je rodičem y. Všechna jména píšeme s malým počátečním písmenem, protože identifikátory, které začínají velkým písmenem, se v Prologu chápou jako proměnné. Uvedená fakta můžeme doplnit údaji o pohlaví: muz(vladislav). muz(ludvik). muz(ferdinand). muz(karel). muz(maxmilian). muz(rudolf). muz(matyas). zena(johana). zena(anna). zena(marie).

Nyní uveďme příklady dotazů, které můžeme našemu prologovskému programu klást (dotazy začínají otazníkem, řádky bez otazníku představují odpovědi systému). Začněme jednoduchými dotazy, které neobsahují proměnné: ?- rodic(vladislav,ludvik). yes ?- rodic(karel,rudolf). no

Zajímavější je, když se v dotazu vyskytují proměnné. Systém však v případě úspěšného vyhodnocení dotazu (splnění cíle) neodpoví pouze yes, ale vypíše hodnoty proměnných, pro něž je daný cíl splněn. Pokud stiskneme klávesu středník, systém se pokusí o další vyhodnocení. Je-li další vyhodnocení neúspěšné, napíše no. ?- rodic(X,maxmilian). X = anna; X = ferdinand; no

Je možné zadat dotaz, který obsahuje pouze proměnné: ?- rodic(X,Y).

- 44 -

Jiří Dvořák


X = vladislav, Y = ludvik; X = vladislav, Y = anna; X = johana, Y = ferdinand; X = johana, Y = karel; ...

Po požadavku o opakované vyhodnocení se postupně vypisují hodnoty proměnných, pro které je cíl splněn. Můžeme pokládat i složené dotazy, představující konjunkci cílů (cíle v dotazu se oddělují čárkami). Dotaz „Je Marie vnučkou Johany? “ se může zadat takto: ?- rodic(johana,X),rodic(X,marie). X = karel; no

Systém postupuje tak, že nejprve se na proměnnou X naváže hodnota ferdinand, neboť první fakt, s nímž se může prvý cíl ztotožnit, je fakt rodic(johana, ferdinand). Systém se pak pokouší v databázi najít fakt rodic(ferdinand, marie). Takový tam není, takže tento pokus skončí neúspěchem. Další možnou substitucí je X = karel, po níž vyhodnocení dopadne úspěšně. Při požadavku o další vyhodnocení zadaném středníkem systém už odpovídá no. Odpověď systému na zadaný dotaz je tedy kladná s tím, že Marie je vnučkou Johany přes svého otce Karla. Co se stane, když změníme pořadí cílů v dotazu? ?- rodic(X,marie),rodic(johana,X).

Vyhodnocení je pak efektivnější, protože odpadne pokus s navázáním hodnoty ferdinand na proměnnou X. Dotaz „Kdo jsou praprarodiče Rudolfa?“ je nejvýhodnější zadat takto: ?- rodic(X,rudolf),rodic(Y,X),rodic(Z,Y). X = maxmilian, Y = anna, Z = vladislav; X = maxmilian, Y = ferdinand, Z = johana; X = marie, Y = karel, Z = johana; no

Odpověď na danou otázku dává proměnná Z. Dotaz „Kdo je sestrou Ludvíka?“ může vypadat následovně: ?- rodic(X,ludvik),rodic(X,Y),zena(Y). X = vladislav, Y = anna; no

Odpověď na danou otázku dává proměnná Y. Používání složených dotazů je nevýhodné. Vhodnější je pro podobné účely zavést pravidla.

- 45 -

Jiří Dvořák


Příklady pravidel (texty počínající znakem % do konce řádku představují poznámky): % X je prarodicem Y prarodic(X,Y):- rodic(X,Z),rodic(Z,Y). % X je sestrou Y sestra(X,Y):- rodic(Z,Y),rodic(Z,X),zena(X).

Můžeme pak pokládat takovéto dotazy: % Kdo je prarodicem Marie? ?- prarodic(X,marie). % Kdo je vnukem nebo vnuckou johany? ?- prarodic(johana,X). % Kdo je sestrou ludvika? ?- sestra(X,ludvik). % Ci sestrou je anna? ?- sestra(anna,X).

Uvedené příklady dokumentují skutečnost, že se často můžeme ptát na kteroukoli proměnnou, která vstupuje do vztahu definovaného pravidlem. Definujme nyní vztah bratr a ověřme, jak funguje. % X je bratrem Y bratr(X,Y):- rodic(Z,Y),rodic(Z,X),muz(X). % Kdo je bratrem Rudolfa ?- bratr(X,rudolf). X = rudolf; X = matyas; X = rudolf; X = matyas; no

Dostali jsme nesmyslnou odpověď, že bratrem Rudolfa je Rudolf. Definice vztahu bratr je tedy nedokonalá a musí být doplněna o podmínku, že X je různé od Y. K tomu můžeme použít buď operátor \= (viz str. 51) nebo operátor \== (viz str. 66). Dalším nedostatkem je skutečnost, že odpovědi jsou zdvojené v důsledku toho, že cíl je splněn jednou přes otce a jednou přes matku. Pokud chceme obdržet všechny možné odpovědi bez opakování, můžeme to udělat dvěma způsoby. Do databáze zaznamenáváme nově získaná řešení pomocí predikátu asserta (viz str. 68) a testujeme jejich přítomnost. Jednodušší možností je použít predikát setof (viz str. 69). Pravidla podobná výše uvedeným příkladům neumožňují realizovat složitější výpočty. Tuto možnost však poskytují rekurzivní pravidla. Příkladem může být procedura, definující vztah předek: - 46 -

Jiří Dvořák


% X je predkem Y predek(X,Y):- rodic(X,Y).

% Trivialni pripad

predek(X,Y):- rodic(X,Z),predek(Z,Y).

% Rekurze

Rekurzívní proceduru musíme definovat tak, aby alespoň jedno pravidlo neobsahovalo rekurzi. Zkusme nyní položit dotaz ?- predek(X,rudolf). X = maxmilian ; X = marie ; X = vladislav ; X = johana ; X = johana ; X = anna ; X = ferdinand ; X = karel ; no

Připadá-li zkoumaná rodinka nějak podivná či něco připomínající, nechť nahlédne do následující tabulky. Zjistí, že se jedná o průnik rodokmenů jagellonské, habsburské a kastilsko-aragonské dynastie. Skutečnost, že Rudolf II. byl dvojnásobným potomkem Johany Šílené, může vysvětlit některé rysy jeho osobnosti. Osoba

rok narození

rok úmrtí

Vladislav Jagellonský

1456

1516

český a uherský král

Johana Šílená

1479

1555

dcera Isabely Kastilské a Ferdinanda Aragonského; manželka Filipa Habsburského (zemřel r. 1500)

Ludvík Jagellonský

1506

1526

český a uherský král; padl v bitvě u Moháče

Anna Jagellonská

1503

1547

česká a uherská královna; je po ní pojmenován letohrádek na Pražském hradě

Ferdinand I.

1503

1564

český a uherský král a římský císař

Karel V.

1500

1558

španělský král a římský císař

Maxmilián II.

1527

1576


Marie

1528

1603

Rudolf II.

1552

1612


Matyáš

1557

1619


- 47 -

poznámka

Jiří Dvořák



a) Definujte vztahy strýc, teta, dědeček, babička. b) Navrhněte vlastní databázi rodinných vztahů a vyzkoušejte definované predikáty.

4.2 Typy a syntaxe dat Přehled a členění datových objektů Prologu ukazuje obr. 4.2. datové objekty (termy)

jednoduché objekty

konstanty

atomy

struktury (složené termy)

proměnné

čísla Obr. 4.2. Datové objekty v Prologu

Atomy

•

identifikátory začínající malým písmenem; součástí jména atomu může být i znak _ (podtržení), který se syntakticky zařazuje do stejné skupiny znaků jako velká písmena, takže jím jméno atomu nesmí začínat

•

posloupnosti speciálních znaků

•

řetězce znaků uzavřené mezi apostrofy; v takovém případě může jméno atomu obsahovat libovolné znaky a může i začínat velkým písmenem

Čísla

Používá se notace běžná v tradičních programovacích jazycích. Všechny implementace Prologu dovolují používat celých čísel, jen některé mají zavedeny rovněž operace s čísly necelými zobrazenými v pohyblivé řádové čárce. Proměnné

Na rozdíl od Lispu, kde proměnnou můžeme vyjádřit libovolným symbolickým atomem, Prolog syntakticky rozlišuje atomy a proměnné. Proměnné v Prologu jsou reprezentovány identifikátory, které začínají velkým písmenem nebo znakem _ (podtržení). Zvláštní význam má tzv. anonymní proměnná vyjádřená pouze znakem _ . Touto proměnnou označujeme takový argument relace, - 48 -

Jiří Dvořák


jehož hodnota nás nezajímá. Každý výskyt znaku _ představuje novou anonymní proměnnou, takže hodnoty na příslušných místech se nemusejí shodovat. Každá proměnná má svůj rozsah platnosti lexikálně omezen klauzulí, v níž je použita. V jistém smyslu lze roli proměnných v pravidlech chápat jako obdobu formálních parametrů v procedurách; přitom způsob volání těchto „parametrů“ je specificky prologovská varianta volání jménem. Každá proměnná se může nacházet v jednom z následujících dvou stavů: •

nenastavená (neinstanciovaná) proměnná není vázána na žádnou konstantu nebo strukturu jako na svoji hodnotu

•

nastavená (instanciovaná) proměnná má již přiřazenu konkrétní hodnotu

K nastavení proměnných dochází především při výběru pravidla nebo faktu z databáze, podle něhož se bude Prolog řídit při vyhodnocení určitého cíle. Jednou definovanou hodnotu proměnné nelze v rozsahu její platnosti měnit. Ke zrušení nastavení dochází jednak při úspěšném nebo neúspěšném výstupu z lexikálního rozsahu platnosti dané proměnné, ale také při zpětném návratu a požadavku na nové splnění cíle, v němž došlo k předchozímu nastavení proměnné. Struktury

Strukturované objekty neboli struktury jsou vytvořené z dílčích komponent (složek) jejich spojením do zápisu, který má syntaktickou podobu tzv. složeného termu f(t1, t2, … , tn)

kde f je atom (identifikátor) vyjadřující funktor struktury a t1, t2, … , tn jsou libovolné datové objekty vyjadřující argumenty. Strukturu lze chápat jako linearizovaný zápis obecného stromu. Diskutabilní vlastností Prologu je možnost používat v termech stejné jméno funktoru s rozdílným počtem argumentů. Z tohoto důvodu se každý funktor vedle svého jména charakterizuje ještě svojí četností neboli aritou. Syntaxe Prologu dovoluje vžité binární operátory (např. aritmetické a relační operátory) používat také v infixovém zápisu. Příklady struktur: bod(1,1) bod(X,Y) trojuhelnik(bod(1,1),bod(3,1),bod(2,3))

4.3 Syntaxe programu Program je posloupnost klauzulí (případně doplněná komentáři): klauzule1 klauzule2 ...

- 49 -

Jiří Dvořák


klauzuleN

Každá klauzule má jeden z těchto tvarů: term0 :- terml,term2, … ,termM.

(pravidlo)

term.

(fakt)

?- terml,term2, … ,termK.

(dotaz)

Za komentář se v Prologu považuje text začínající znakem % (procento) až do konce řádku. Každý term použitý v klauzuli má nejčastěji tvar struktury, může to však být také atom. Symboly používané pro zápis klauzulí je třeba považovat za infixové popř. prefixové operátory, takže i klauzule jsou syntakticky vzato termy (např. hlavním funktorem pravidla je operátor :-). Význam symbolů v pravidle: symbol :- znamená implikaci ⇐ a čárka znamená konjunkci (je také možno použít středník ve významu disjunkce). Termy uvedené v klauzulích se při výpočtu interpretují jako cíle. Termy lze vytvářet dynamicky i během výpočtu programu a existuje i způsob, jak takto vytvořené termy interpretovat jako cíle. Lze tedy konstatovat, že podobně jako v Lispu, také v Prologu nelze syntakticky rozlišit program od dat a záleží na kontextu použití, zda se určitý term chápe pouze jako datový objekt nebo jako cíl.

4.4 Unifikace Vyhodnocovací systém musí určovat, zda určité pravidlo nebo fakt jsou použitelné při vyhodnocení zadaného cíle. To znamená, že tedy musí být schopen důkladného srovnání hlavy klauzule a cíle. Operace srovnání (matching) je jedním ze základních pilířů systému Prolog. Je to aktivní mechanismus, jehož výsledkem není jen odpověď ano/ne. Během procesu srovnání se totiž případně musí hledat vhodná substituce za proměnné, pomocí níž se podaří termy "zestejnit". Dva termy se srovnají když jsou identické, nebo když proměnné vyskytující se v těchto termech lze nastavit na takové hodnoty, že se získají identické termy . Protože český termín srovnání má obecnější význam, používá se často místo něj termín unifikace. Výsledkem unifikace je vždy buď neúspěch, nebo substituce, s jejíž pomocí se termy unifikují, tj. stanou se identickými. Tato substituce může ovšem být i prázdná, pokud jsou unifikované termy identické. Zásady pro unifikaci

Nechť S a T jsou termy: 1. Jsou-li S a T konstanty, pak se unifikují právě tehdy, když se jedná o stejné objekty. 2. Je-li S nenastavená proměnná a T jakýkoliv term, pak se unifikují a současně se S nastaví na hodnotu T. Podobně, je-li T nenastavená proměnná, pak se nastaví na hodnotu S. Je-li S nebo T nastavená proměnná, pak se k unifikaci použije její hodnota. 3. Jsou-li S a T struktury, pak se unifikují právě tehdy, když (a) S i T mají stejný hlavní funktor, - 50 -

Jiří Dvořák


(b) odpovídající si složky termů S a T se unifikují. Výsledkem úspěšné unifikace je vždy tzv. nejobecnější unifikátor, což je substituce, která váže hodnoty proměnných tím nejméně omezujícím způsobem, a tak jim dává větší volnost pro případné následující unifikace. Operátory = a \=

Pomocí operátoru = můžeme explicitně požádat o unifikaci termů. Tento operátor uspěje, pokud jsou oba termy unifikovatelné. Naopak operátor \= uspěje, když zadané termy nejsou unifikovatelné. Vztah bratr (viz str. 46) můžeme nyní pomocí operátoru \= předefinovat takto: % X je bratrem Y bratr(X,Y):- rodic(Z,Y),rodic(Z,X),muz(X),X\=Y.

Příklad unifikace: ?- trojuhelnik(bod(1,1),A,bod(2,3))= trojuhelnik(X,bod(4,5),bod(2,Y)). A = bod(4,5), X = bod(1,1), Y = 3

4.5 Deklarativní a procedurální sémantika Deklarativní sémantika programu popisuje vztahy mezi objekty (tzn. CO platí). Procedurální sémantiku programu určuje způsob, JAK Prolog využívá svoji databázi při zodpovídání dotazů, jaká je posloupnost dílčích kroků při této činnosti. Například mějme klauzuli tvaru P :– Q, R. Při deklarativním pohledu můžeme tuto klauzuli číst takto: •

P je pravdivé, jestliže Q i R jsou pravdivé,

•

z platnosti Q a R plyne P, apod.

Při procedurálním pohledu chápeme tuto klauzuli takto: •

aby se vyřešil problém P, je třeba nejprve vyřešit Q a pak vyřešit R,

•

aby se splnil cíl P, je třeba nejprve splnit cíl Q a potom splnit cíl R.

Procedurální sémantika určuje, že cíle jsou vyhodnocovány v tom pořadí, v jakém jsou zapsány v dotazu nebo v pravidle, a dále že při vyhodnocování cílů systém prochází klauzule v databázi v tom pořadí, v jakém jsou zde uloženy. Vztah bratr můžeme definovat dvěma způsoby: % X je bratrem Y bratr1(X,Y):- rodic(Z,Y),rodic(Z,X),muz(X),X\=Y. bratr2(X,Y):- muz(X),rodic(Z,X),rodic(Z,Y),X\=Y.

- 51 -

Jiří Dvořák


Z hlediska deklarativní sémantiky jsou oba vztahy rovnocenné, avšak z hlediska procedurální sémantiky tomu tak není. Záleží totiž na tom, na co se ptáme. Je-li zadáno Y a X je proměnná, pak je výhodnější prvá varianta, kdežto ve druhém případě je tomu naopak. Sloučit obě varianty do jedné a ponechat rozhodnutí o tom, co je výhodnější, na systému umožňuje predikát nonvar (viz str. 65). Podobně vztah předek (viz str. 47) můžeme definovat dokonce čtyřmi způsoby, které jsou z hlediska deklarativní sémantiky rovnocenné: % Varianta 1 predek1(X,Y):- rodic(X,Y). predek1(X,Y):- rodic(X,Z),predek1(Z,Y). % Varianta 2 predek2(X,Y):- rodic(X,Y). predek2(X,Y):- predek2(Z,Y),rodic(X,Z). % Varianta 3 predek3(X,Y):- rodic(X,Z),predek3(Z,Y). predek3(X,Y):- rodic(X,Y). % Varianta 4 predek4(X,Y):- predek4(Z,Y),rodic(X,Z). predek4(X,Y):- rodic(X,Y).

V důsledku procedurální sémantiky je nejvýhodnější prvá varianta, méně efektivní je druhá varianta, ještě hůře ja na tom třetí varianta a nejhorší je čtvrtá varianta, která skončí chybovým hlášením (tato varianta totiž definuje potenciálně nekonečnou rekurzi). Substituce

Substituci je možno definovat jako konečnou množinu dvojic

σ = {X1 = t1, X2 = t2, … , Xn = tn} kde Xi jsou proměnné a ti jsou termy, přičemž Xi ≠ Xj a žádný z termů ti neobsahuje proměnné Xj pro všechna j. Výsledek substituce σ na term A je term, který se získá dosazením termu ti za každý výskyt proměnné Xi v termu A. Tento term označme jako Aσ . Term (klauzule) B je instancí termu (klauzule) A, pokud existuje taková substituce σ , pro kterou platí B = Aσ . Variantou termu (klauzule) nazýváme takovou jeho instanci, v níž se každá proměnná nahradila jinou proměnnou. Deklarativní sémantika

Deklarativní sémantika programu v Prologu má základ ve vztahu Prologu a predikátové logiky. Místo pojmu formule se používá pojem cíl. - 52 -

Jiří Dvořák


Pro daný program a cíl G stanoví deklarativní sémantika, že cíl G je pravdivý právě tehdy, když v programu existuje klauzule C taková, že existuje její instance I taková, že (a) hlava klauzule I je identická s cílem G a současně (b) všechny cíle z těla klauzule I jsou pravdivé. Deklarativní sémantika dotazu majícího tvar posloupnosti cílů G1, G2, ..., Gn se definuje v Prologu tak, že všechny cíle této posloupnosti musejí být pravdivé pro stejnou substituci proměnných. Substituce získaná jako výsledek zpracování dotazu je nejobecnější takovou substitucí. Procedurální sémantika

Procedurální sémantika vyjadřuje, jak Prolog zodpovídá dotazy. Zodpovědět dotaz znamená pokusit se splnit cíle, které jsou v něm uvedeny, neboli nalézt takovou substituci proměnných uvedených v těchto cílech, že cíle logicky vyplývají z programu. Procedurální sémantiku Prologu tedy můžeme vyjádřit procedurou, kterou se vyhodnocuje posloupnost cílů s ohledem na zadaný program. Vyhodnocovací proceduru nazvěme Evaluate. Při vyhodnocení posloupnosti cílů postupuje procedura Evaluate takto: •

Je-li posloupnost cílů prázdná, vyhodnocení končí úspěchem.

•

Pro neprázdnou posloupnost cílů G1, G2, … , Gm se provádí operace označená jako prohlížení. Prohlíží se klauzule programu shora dolů až do nalezení první klauzule C takové, že její hlava se úspěšně unifikuje s cílem G1. Pokud se taková klauzule nenalezne, končí vyhodnocení neúspěšně.

Operace prohlížení pracuje následovně: 1. Mějme klauzuli C tvaru A :– B1 , B2 , … , Bn . Přejmenují se všechny její proměnné tak, aby se dostala varianta C' klauzule C, která nemá žádné společné proměnné s cíli G1, G2, … , Gm . 2. Nechť má C' tvar A' :– B1', B2', … , Bn' . Unifikují se G1 a A'. Je-li unifikace úspěšná, získá se substituce σ. V posloupnosti cílů se cíl G1 nahradí tělem klauzule C', takže se získá nová posloupnost cílů ve tvaru B1', B2', … , Bn', G2 , … , Gm . Je-li klauzule C faktem, pak je n = 0 a posloupnost cílů se tak fakticky zkrátí o jeden cíl, což může posléze vést k jejímu vyprázdnění a úspěšnému ukončení vyhodnocení. 3. Provede se substituce σ do nového seznamu cílů, takže se získá další tvar B1'σ, B2'σ, … , Bn'σ, G2σ , … , Gmσ. Rekurzivním voláním procedury Evaluate se vyhodnotí tato posloupnost cílů a přitom se průběžně doplňuje vytvářená substituce. Skončí-li toto vyhodnocení úspěšně, také původní vyhodnocení se považuje za úspěšné. Není-li toto vyhodnocení úspěšné, provede se návrat k předchozí posloupnosti cílů, přičemž se odstraní ty části substituce, které byly doplněny při zpracování klauzule C. Dále se pokračuje v prohlížení bezprostředně za klauzulí C ve snaze nalézt další použitelnou klauzuli.

- 53 -

Jiří Dvořák


4.6 Blokový model vyhodnocování Každý cíl, který má být splněn, si můžeme představit jako schránku či blok (box) se čtyřmi branami (porty), které mají názvy CALL, EXIT, FAIL, REDO. Brány CALL a REDO jsou vstupní, brány EXIT a FAIL výstupní. Při volání cíle se vstoupí branou CALL. Je-li cíl splněn, vystoupí se z boxu branou EXIT. Není-li cíl splněn, vystoupí se branou FAIL. Když dojde k návratu, tj. při požadavku nalézt alternativní řešení, vstoupí se opět do schránky, ale branou REDO. Je-li cíl splněn, vystoupí se branou EXIT a není-li splněn, vystoupí se branou FAIL.

EXIT

CALL Cíl

REDO

FAIL

Obr. 4.3. Blokový model vyhodnocování Názvy těchto bran se objevují ve výpisu při ladění programu. Uvažujme tuto definici vztahu bratr: % X je bratrem Y bratr(X,Y):- rodic(Z,Y),rodic(Z,X),muz(X),X\=Y.

Po položení dotazu „Kdo je bratrem Rudolfa?“ ?- bratr(X,rudolf).

získáme následující výpis (byl použit systém Amzi!Prolog): CALL: user:bratr(H13, rudolf) trying:(1) user:bratr(H13, rudolf) CALL: user:rodic(H87, rudolf) trying:(8) user:rodic(maxmilian, rudolf) EXIT:(8) user:rodic(maxmilian, rudolf) CALL: user:rodic(maxmilian, H13) trying:(8) user:rodic(maxmilian, rudolf) EXIT:(8) user:rodic(maxmilian, rudolf) CALL: user:muz(rudolf) trying:(6) user:muz(rudolf) EXIT:(6) user:muz(rudolf) CALL: user:(rudolf \= rudolf) FAIL: user:(rudolf \= rudolf) REDO: user:muz(rudolf)

- 54 -

Jiří Dvořák


FAIL: user:muz(rudolf) REDO: user:rodic(maxmilian, rudolf) trying:(9) user:rodic(maxmilian, matyas) EXIT:(9) user:rodic(maxmilian, matyas) CALL: user:muz(matyas) trying:(7) user:muz(matyas) EXIT:(7) user:muz(matyas) CALL: user:(matyas \= rudolf) EXIT: user:(matyas \= rudolf) EXIT:(1) user:bratr(matyas, rudolf)

Čísla v kulatých závorkách jsou pořadová čísla použitých klauzulí v rámci procedur bratr, rodic (viz str. 43) a muz (viz str. 44). Jestliže však položíme dotaz „Čí bratr je Rudolf?“ ?- bratr(rudolf,X).

dostaneme výpis dokumentující, že použití uvedeného pravidla pro tento typ dotazu je méně výhodné. CALL: user:bratr(rudolf, H26) trying:(1) user:bratr(rudolf, H26) CALL: user:rodic(H99, H26) trying:(1) user:rodic(vladislav, ludvik) EXIT:(1) user:rodic(vladislav, ludvik) CALL: user:rodic(vladislav, rudolf) FAIL: user:rodic(vladislav, rudolf) REDO: user:rodic(vladislav, ludvik) trying:(2) user:rodic(vladislav, anna) EXIT:(2) user:rodic(vladislav, anna) CALL: user:rodic(vladislav, rudolf) FAIL: user:rodic(vladislav, rudolf) REDO: user:rodic(vladislav, anna) trying:(3) user:rodic(johana, ferdinand) EXIT:(3) user:rodic(johana, ferdinand) CALL: user:rodic(johana, rudolf) FAIL: user:rodic(johana, rudolf) REDO: user:rodic(johana, ferdinand) trying:(4) user:rodic(johana, karel) EXIT:(4) user:rodic(johana, karel) CALL: user:rodic(johana, rudolf) FAIL: user:rodic(johana, rudolf) REDO: user:rodic(johana, karel) trying:(5) user:rodic(anna, maxmilian) EXIT:(5) user:rodic(anna, maxmilian) CALL: user:rodic(anna, rudolf) FAIL: user:rodic(anna, rudolf) REDO: user:rodic(anna, maxmilian) trying:(6) user:rodic(ferdinand, maxmilian) EXIT:(6) user:rodic(ferdinand, maxmilian) CALL: user:rodic(ferdinand, rudolf)

- 55 -

Jiří Dvořák


FAIL: user:rodic(ferdinand, rudolf) REDO: user:rodic(ferdinand, maxmilian) trying:(7) user:rodic(karel, marie) EXIT:(7) user:rodic(karel, marie) CALL: user:rodic(karel, rudolf) FAIL: user:rodic(karel, rudolf) REDO: user:rodic(karel, marie) trying:(8) user:rodic(maxmilian, rudolf) EXIT:(8) user:rodic(maxmilian, rudolf) CALL: user:rodic(maxmilian, rudolf) trying:(8) user:rodic(maxmilian, rudolf) EXIT:(8) user:rodic(maxmilian, rudolf) CALL: user:muz(rudolf) trying:(6) user:muz(rudolf) EXIT:(6) user:muz(rudolf) CALL: user:(rudolf \= rudolf) FAIL: user:(rudolf \= rudolf) REDO: user:muz(rudolf) FAIL: user:muz(rudolf) REDO: user:rodic(maxmilian, rudolf) FAIL: user:rodic(maxmilian, rudolf) REDO: user:rodic(maxmilian, rudolf) trying:(9) user:rodic(maxmilian, matyas) EXIT:(9) user:rodic(maxmilian, matyas) CALL: user:rodic(maxmilian, rudolf) trying:(8) user:rodic(maxmilian, rudolf) EXIT:(8) user:rodic(maxmilian, rudolf) CALL: user:muz(rudolf) trying:(6) user:muz(rudolf) EXIT:(6) user:muz(rudolf) CALL: user:(rudolf \= matyas) EXIT: user:(rudolf \= matyas) EXIT:(1) user:bratr(rudolf, matyas)

4.7 Zpracování čísel Prolog byl koncipován jako jazyk vhodný pro symbolické výpočty a programování číselných operací má v něm ještě menší podporu než např. v Lispu. Bez počítání s čísly se však neobejdeme ani v logickém programování, a tak je celočíselná aritmetika součástí každé implementace Prologu. Operátory, které implementace Prologu dovolují používat při zápisu aritmetických výrazů, zpravidla vyjadřují všechny čtyři základní aritmetické operace (t.j. +, –, *, /), k dispozici mohou být i operátor celočíselného dělení a zbytku (div a mod). Operátor / pak v takovém případě vyjadřuje dělení s výsledkem typu real. Možnost zapisovat v Prologu aritmetické výrazy v infixové notaci ještě neznamená, že aritmetický výraz se vždy vyhodnocuje. Pro vyhodnocení aritmetických výrazů slouží operátor is, který patří mezi tzv. standardní neboli zabudované predikáty Prologu. - 56 -

Jiří Dvořák


Operátor is

Predikát is funguje do určité míry podobně jako operátor přiřazení v imperativních programovacích jazycích. Nejprve se vyhodnotí aritmetický výraz na pravé straně. Pak se ale neprovede běžné přiřazení vzniklé hodnoty, nýbrž její unifikace s proměnnou na straně levé. Pokud tato proměnná zatím není nastavena na konkrétní datovou hodnotu, získá hodnotu výrazu a is skončí úspěšně. Pokud již proměnná hodnotu má, pak se musí rovnat spočtené hodnotě výrazu, jinak is skončí neúspěchem. Samozřejmým předpokladem úspěšného vyhodnocení výrazu na pravé straně je to, aby všechny proměnné obsažené v tomto výrazu měly v době vyhodnocení definovanou číselnou hodnotu. Pokud tato podmínka není splněna, vyhodnocení skončí chybovým hlášením (nikoliv tedy mechanismem neúspěchu). Relační operátory

Vedle aritmetických operátorů jsou v Prologu k dispozici také následující infixové binární operátory umožňující srovnání číselných hodnot vyjádřených aritmetickými výrazy: <

menší než

=<

menší nebo rovno

=:=

rovno

>

větší než

>=

větší nebo rovno

=\=

různé

Tyto operátory slouží v Prologu výhradně ke srovnání číselných hodnot a způsobí automatické vyhodnocení svých operandů na obou stranách. Následující příklad ukazuje rozdíl mezi operátorem =:= a operátorem = , který slouží ke srovnání (unifikaci) termů. ?-3*4=:=4+8. yes ?-3*4=4+8. no ?-3*X=Y*6. X=6, Y=3

Příklad: Predikát pro výpočet faktoriálu % Vztah faktorial(N,F) znamena, ze faktorialem N je F faktorial(0,1). faktorial(N,F):- N>0, N1 is N-1,

- 57 -

Jiří Dvořák

Jazyky pro umělou inteligenci faktorial(N1,F1), F is N*F1.

Vraťme se nyní k programu z podkap. 4.1 (viz str. 43) a zaveďme do něj údaje o narození a úmrtí: narozeni(vladislav, 1456). narozeni(johana, 1479). narozeni(ludvik, 1506). narozeni(anna, 1503). narozeni(ferdinand, 1503). narozeni(karel, 1500). narozeni(maxmilian, 1527). narozeni(marie, 1528). narozeni(rudolf, 1552). narozeni(matyas, 1557). umrti(vladislav, 1516). umrti(johana, 1555). umrti(ludvik, 1526). umrti(anna, 1547). umrti(ferdinand, 1564). umrti(karel, 1558). umrti(maxmilian, 1576). umrti(marie, 1603). umrti(rudolf, 1612). umrti(matyas, 1619).

Nyní můžeme např. definovat vztah mladší % X je mladsi nez Y mladsi(X,Y):-narozeni(X,Rx),narozeni(Y,Ry),Rx>Ry.

a položit dotaz, zda měl Rudolf mladšího bratra: ?-bratr(X,rudolf),mladsi(X,rudolf). X=matyas Úlohy na procvičení

a) Definujte predikát pro určení maxima ze dvou čísel (viz s. 83). b) Definujte predikát pro výpočet největšího společného dělitele (viz s. 83).

4.8 Zpracování seznamů Seznam v Prologu má tvar [t1, t2, … , tn]

kde ti jsou termy. Příklady seznamů: - 58 -

Jiří Dvořák


[a,b,c,d] [a,[b,c],d] []

Vnitřní reprezentace seznamu odpovídá složenému termu .(t1, [t2, … , tn])

kde . (tečka) je speciální binární funktor, jehož prvním argumentem je první prvek seznamu a druhým argumentem je zbytek seznamu. Tato struktura je tedy analogií lispovské tečky-dvojice. Na rozdíl od Lispu atom nil nevyjadřuje prázdný seznam. Prázdný seznam se v Prologu dá vyjádřit pouze takto: [] Další analogií tečky dvojice je zápis [1.prvek seznamu |zbytek seznamu]

Tento způsob zápisu je možno zobecnit tak, že před znakem | se může nacházet i více prvků seznamu. Seznam [t1,t2, … ,tn]

je tedy možno zapsat také těmito způsoby: [t1|[t2, … ,tn]] [t1,t2|[t3, … ,tn]] [t1,t2,t3|[t4, … ,tn]] ... [t1,t2, … ,tn|[]]

Například seznam [a,b,c,d] můžeme zapsat také takto: [a|[b,c,d]] [a,b|[c,d]] [a,b,c|[d]] [a,b,c,d|[]]

V podkapitole 2.5 jsme definovali funkci Lispu pro spojení dvou seznamů (viz str. 18). Podívejme se, jak se tento problém vyřeší v Prologu. % Vztah spoj(X,Y,Z) znamena, ze Z je spojenim seznamu X a Y spoj([],X,X). spoj([H|T],X,[H|NT]):- spoj(T,X,NT).

Predikát spoj má o jeden argument více, než lispovská funkce Spoj, protože se jedná o definici vztahu mezi zadanými seznamy a výsledným seznamem. Dále si ve druhé klauzuli povšimněme - 59 -

Jiří Dvořák


důležité možnosti Prologu používat definice vzorem argumentu. Dalším rozdílem oproti Lispu je to, že predikát spoj můžeme použít „v obou směrech“, jak ukazují následující příklady. ?-spoj([a,b],[c,d],X). X=[a,b,c,d] ?-spoj([a,b],X,[a,b,c,d]). X=[c,d] ?-spoj(X,[c,d],[a,b,c,d]). X=[a,b] ?-spoj(X,Y,[a,b,c,d]). X=[], Y=[a,b,c,d]; X=[a], Y=[b,c,d]; X=[a,b], Y=[c,d]; X=[a,b,c], Y=[d]; X=[a,b,c,d], Y=[]; no

Další příklady práce se seznamy: •

Test, zda X je prvkem daného seznamu clen(X,[X|_]). clen(X,[_|Zbytek]):- clen(X,Zbytek).

V tomto příkladu si povšimněme použití anonymní proměnné. •

Obrácení seznamu na nejvyšší úrovni pomocí predikátu spoj obrat([],[]). obrat([X|L],R):- obrat(L,S),spoj(S,[X],R).

•

Efektivnejsi verze obraceni seznamu pomocí koncové rekurze obrat1(T,R):- obrat2(T,[],R). obrat2([],P,P). obrat2([H|T],P,R):- obrat2(T,[H|P],R).

•

Generování seznamu čísel ze zadaného intervalu od_do(M,N,[]):- M>N. od_do(M,N,[M|K]):- M=
•

Převod prvků libovolně strukturovaného seznamu do jedné úrovně - 60 -

Jiří Dvořák


zplosti1([],[]). zplosti1([H|T],Lst):- zplosti1(H,Lh),zplosti1(T,Lt), spoj(Lh,Lt,Lst). zplosti1(X,[X]).

Nedostatkem této verze je to, že při opakovaném vyhodnocováni vytváří víceúrovňové seznamy. Tento nedostatek může být odstraněn pomocí typového predikátu atomic (viz str. 63). Úlohy na procvičení

a) Pomocí predikátu clen definujte predikát pro přidání prvku X do seznamu bez opakování (viz s. 84). b) Definujte predikát pro přidání prvku X na konec seznamu (viz s. 84). c) Definujte predikát pro odstranění jednoho výskytu prvku X ze seznamu (viz s. 84). d) Definujte predikát pro získání posledního prvku seznamu (viz s. 84). e) Definujte predikát pro odstranění posledního prvku seznamu (viz s. 84). f) Definujte predikáty pro získání posledního prvku seznamu a odstranění posledního prvku seznamu pomocí predikátu pro přidání prvku na konec seznamu (viz s. 84). g) Definujte predikát pro určení délky seznamu (viz s. 84).

4.9 Operátorová notace Prolog dovoluje při zápisu aritmetických výrazů používat namísto důsledné funkcionální prefixové notace také obvyklou notaci infixovou. Tato možnost se však neomezuje pouze na standardní aritmetické a číselné relační operátory, neboť Prolog poskytuje i prostředky, pomocí nichž může uživatel zavést své vlastní binární nebo unární operátory a používat je při zápisu struktur. Je třeba zdůraznit, že zavedení operátoru rozšiřuje výhradně možnosti vstupní syntaxe termů Prologu. S definovaným operátorem není spojena žádná operace, která by se měla provádět s příslušnými argumenty. Operátorová notace dává uživateli pouze možnost učinit program nebo data v Prologu čitelnější. Definované operátory se chápou jako jiné funktory s tím, že při jejich použití se vyjadřuje složený term jinou notací, než která platí pro běžné funktory. Definice nových operátorů se provádí pomocí speciálních klauzulí nazývaných direktivy. Direktiva definující operátor se musí systému Prolog zadat dříve, než se tento operátor použije v nějakém výrazu. Direktiva má tento tvar: :–op(precedence,typová_specifikace,operátor).

Jména operátorů musejí být atomy, jejich precedence se vyjadřuje číselně a přípustný rozsah je zpravidla implementačně závislý (typicky od 1 do 1200). V Prologu platí zásada, že čím je větší hodnota precedence, tím je slabší vazba mezi operátorem a jeho argumenty. Precedence operátorů a typová specifikace musejí být určeny proto, aby bylo možné rozpoznat strukturu výrazu s několika operátory.

- 61 -

Jiří Dvořák


Druhy typových specifikací: •

pro infixové operátory: xfx, xfy, yfx

•

pro prefixové operátory: fx, fy

•

pro postfixové operátory: xf, yf

Kódy x a y označují argumenty, kód f definovaný operátor. Kódy x a y určují asociativnost zaváděného operátoru podle následující konvence. Pro každý složený term se jeho precedencí rozumí precedence jeho hlavního funktoru. Jednoduchý objekt nebo výraz v závorkách má precedenci 0. Symbol x představuje argument s precedencí ostře menší než je precedence zaváděného operátoru f, symbol y představuje argument s precedencí menší nebo rovnou precedenci operátoru f. Typová specifikace xfx pro nějaký operátor θ znamená, že není povolen zápis a θ b θ c. Specifikace yfx znamená, že při unifikaci termu a θ b θ c s termem P θ Q se na proměnnou P naváže term a θ b a na proměnnou Q term c. Příklad zavedení operátorů: :-op(600,xfx,pije). :-op(600,xfx,hraje). :-op(500,yfx,i). :-op(700,yfx,a). karel pije pivo. robert hraje golf. tonda pije rum i pivo a jana hraje karty.

Na základě takto zavedených faktů můžeme pokládat následující dotazy: ?- X pije pivo. X = karel ?- robert hraje X. X = golf ?- tonda pije X a Z hraje karty. X = rum i pivo, Z = jana

Následující tabulka ukazuje precedence a typové specifikace standardních operátorů Prologu.

- 62 -

Jiří Dvořák


Precedence specifikace operátory 1200

xfx

:–

1200

fx

:– , ? –

1100

xfy

;

1000

xfy

,

700

xfx

= , is , < , > , =< , >= , = = , =\= , \= = , =:=

500

yfx

+, –

500

fx

+ , – , not

400

yfx

* , / , div

300

xfx

mod

4.10 Typové predikáty Proměnné v Prologu nemají definovaný typ a tedy je v době výpočtu možné proměnnou vázat na datový objekt libovolné povahy. Standardní tzv. typové predikáty umožňují rozeznat typ navázaného datového objektu. integer(X)

… uspěje, když X je navázáno na celé číslo

atom(X)

… uspěje, když X je navázáno na atom

constant(X) … uspěje, když X je navázáno na konstantu (číslo nebo atom) compound(X) … uspěje, když X je navázáno na složený term

Pokud má konkrétní dialekt Prologu zavedeny ještě další typy dat (např. reálná čísla), pak pro ně má také odpovídající typový predikát. Namísto constant se lze setkat také s predikátem atomic stejného významu a místo compound(X) lze použít not atomic(X). Příklady: integer(123). yes atom(123). no atom(jan). yes atomic(123). yes atomic(bod(1,1)).

- 63 -

Jiří Dvořák


no compound(rodic(max,ruda)). yes.

Následující příklad ukazuje převod prvků libovolně strukturovaného seznamu do jedné úrovně pomocí predikátů atomic a spoj (viz str. 59). zplosti2([],[]). zplosti2([H|T],Lst):-zplosti2(H,Lh),zplosti2(T,Lt), spoj(Lh,Lt,Lst). zplosti2(X,[X]):-atomic(X),X\==[].

4.11 Rozklad a vytváření termů Predikát =..

Standardní predikát (operátor) =.. umožňuje převést každý term do podoby, kterou má zápis funkce v Lispu – tedy do tvaru seznamu, jehož prvním prvkem je hlavní funktor termu a dalšími prvky jsou jeho argumenty. Operátor se používá podle schématu Term =.. Seznam

Převod lze provádět v obou směrech. Příklady: ?- bod(1,2) =.. X. X = [bod,1,2] ?- a+b =..X. X = [+,a,b] ?- X =.. [a,b,c,d]. X = a(b,c,d) Predikáty arg a functor

Pomocí predikátů functor/3 a arg/3 lze odděleně získat buď samotný funktor termu, nebo libovolný z jeho argumentů. Cíl functor(Term,F,Arita)

uspěje, pokud je v termu Term hlavním funktorem F s četností Arita . Příklady: ?- functor(bod(1,2),F,N). F = bod, N = 2 ?- functor(a+b,F,N).

- 64 -

Jiří Dvořák


F = +, N = 2 ?- functor([a,b,c],F,N). F = ., N = 2 ?- functor(jana,F,N). F = jana, N = 0

Cíl arg(N,Term,Arg)

uspěje, pokud N-tým argumentem termu Term je Arg. Tento predikát musí být vždy užit s prvými dvěma proměnnými nastavenými. Příklady: ?- arg(2,rodic(jana,karel),X). X = karel ?- arg(1,a+b+c,X). X = (a+b) ?- arg(2,[a,b,c],X). X = [b,c]

Výsledek druhého dotazu odpovídá tomu, že operátor + má typovou specifikaci yfx.

4.12 Meta-logické predikáty Meta-logické predikáty jsou takové standardní prostředky Prologu, které přesahují rámec vymezený predikátovou logikou prvního řádu. Prostřednictvím těchto predikátů se můžeme dotazovat na okamžitý stav vyhodnocení cílů, pracovat s proměnnými (a ne jen s jejich hodnotami) jako objekty jazyka a dokonce předávat k vyhodnocení jako cíle dynamicky vytvořené struktury. Predikáty var a nonvar

Standardní prologovské predikáty var/l a nonvar/l provádějí rozlišení, zda proměnná je nastavena na konkrétní datový objekt či nikoliv. Cíl var(X)

uspěje, právě když proměnná X není nastavena na žádný datový objekt. Příklad: ?- var(X). yes ?- X=Z,Z=23,var(X). no

- 65 -

Jiří Dvořák


Cíl nonvar(X)

uspěje, právě když proměnná X je nastavena na nějaký datový objekt. Predikát nonvar můžeme využít pro takovou, definici vztahu bratr, která zajistí efektivní vyhodnocení nezávisle na tom, který z argumentů bude v dotazu zadán. bratr(X,Y):-nonvar(X),muz(X),rodic(Z,X),rodic(Z,Y),X\=Y. bratr(X,Y):-nonvar(Y),rodic(Z,Y),rodic(Z,X),muz(X),X\=Y. Predikáty == a \==

Binární predikáty == a \== umožňují zjistit, zda jsou či nejsou dvě proměnné vázány na identický objekt. X == Y

uspěje pokud X a Y jsou identické konstanty, identické proměnné, nebo struktury s identickým funktorem, četností a po řadě identickými argumenty. X \== Y

selže právě tehdy, jsou-li X a Y identické termy. Následující příklad ukazuje, jak můžeme v Prologu chápat vztah stejné: stejne1(X,X).

%unifikovatelne

stejne2(X,Y):- X==Y.

%identicke

Predikát call

V Prologu stejně jako v Lispu mají program i data stejnou syntaxi. V Lispu je možné jakýkoliv dynamicky vytvořený symbolický výraz považovat za „program“ a vyhodnotit jej pomocí eval. V Prologu k tomuto účelu slouží standardní predikát call. Při vyhodnocení cíle call (X) musí být hodnotou argumentu vyhodnotitelný cíl; systém pak vyhodnotí tento cíl a jeho výsledek je i výsledkem cíle call (X). Hlavní použití predikátu call spočívá v možnosti interpretace dynamicky vytvářených termů, které se např. zadávají interaktivně v době výpočtu programu. Příklad: eval_list(L):- X=..L, call(X). ?- eval_list([is,Z,2*3]). Z = 6 ?- eval_list([spoj,[a,b],[c,d],X]). X = [a, b, c, d]

Predikát spoj je definován na str. 59.

- 66 -

Jiří Dvořák


4.13 Řez Řez je standardní predikát, který se zapisuje znakem ! (vykřičník) jako jeden z podcílů v těle pravidla. Pomocí řezu můžeme zabránit tomu, aby se při vyhodnocení cíle zbytečně zkoušela použít pravidla, o nichž je předem známo, že již k řešení nevedou. Řez tedy redukuje prohledávací prostor prologovského programu tak, že dynamicky odřezává celé neužitečné podstromy. Význam řezu je možné popsat pouze pomocí procedurální sémantiky programu, takže jeho použitím se od sebe může velmi nebezpečně vzdálit deklarativní a procedurální sémantika. V souvislosti s tím se rozlišují dva typy řezu: •

Zelený řez neovlivňuje výslednou množinu řešení cíle a odřezává tedy jen větve neobsahující potenciální řešení,

•

Červený řez zvyšuje efektivnost programu za cenu nesouladu mezi deklarativní a procedurální sémantikou.

Řez má následující sémantiku: •

bezpodmínečně uspěje,

•

fixuje všechny vazby proměnných provedené od unifikace nadřazeného cíle s hlavou pravidla, v němž se řez nachází,

•

dojde-li v těle pravidla za řezem k selhání nějakého podcíle, které nejde napravit návraty do podcílů vpravo od řezu, znamená to současně i selhání nadřazeného cíle – žádná další pravidla se pro něj již neuplatní.

Působením řezu se tedy odstřihnou všechna možná řešení podcílů nacházejících se nalevo od něj a možnost použití všech pravidel dané procedury, která následují za pravidlem obsahujícím řez. Na druhé straně se jím neovlivňuje možné navracení v podcílech nacházejících se napravo od něj. Jakmile by však mělo dojít ke zpětnému návratu před řez, provede se výstup z celé procedury se signalizací neúspěchu cíle. Příklady: •

Přidání prvku do seznamu bez opakování clen(X,[X|L]). clen(X,[Y|L]):- clen(X,L). pridej(X,L,L):- clen(X,L),!. pridej(X,L,[X|L]).

•

Definice vztahu různé ruzne1(X,X):- !,fail. ruzne1(X,Y).

%neunifikovatelne

ruzne2(X,Y):- X\==Y.

%neidenticke

- 67 -

Jiří Dvořák


4.14 Negace Negace je v Prologu vyjádřena standardním predikátem not a její význam můžeme ilustrovat pomocí takto definovaného predikátu neplatí: neplati(X):- call(X),!,fail. neplati(X).

kde fail je standardní predikát, který nelze splnit. Cíl not(X) tedy selže, pokud je cíl X prologovsky splnitelný, a naopak cíl not(X) bude úspěšný, pokud cíl X splnit nelze. Nemožnost splnění cíle může ovšem v Prologu vyvolat zacyklení a pak se zacyklí i vyhodnocení negace, místo aby uspělo. K potížím s negací nedojde, pokud se při vyhodnocení nevyskytují v negovaném cíli nenastavené proměnné. Pozn.: Funktor not je standardně definován jako unární prefixový operátor se stejnou preferencí jakou mají binární operátory + a –, takže není třeba jeho argument dávat do závorek. Příklad: Přidání prvku X do seznamu bez opakování clen(X,[X|L]). clen(X,[Y|L]):- clen(X,L). pridej_bez_opak(X,L,L):- clen(X,L). pridej_bez_opak(X,L,[X|L]):- not clen(X,L).

4.15 Práce s databází Predikáty consult a reconsult

Tyto predikáty zajišťují vstup programu ze souboru. consult(F)

Vyhodnocení tohoto cíle způsobí načtení klauzulí všech procedur ze souboru F a jejich uložení do databáze. Stejným způsobem lze načíst procedury z několika souborů, pravidla se ukládají do databáze v tom pořadí, v jakém se četla. Namísto několika volání predikátu consult je možné uvést v jeho argumentu seznam jmen souborů obsahujících program. reconsult(F)

Vyhodnocení tohoto cíle má podobný účinek s tím rozdílem, že všechny procedury predikátů uvedené v souboru F nahradí případné dosud platné procedury z databáze. Predikáty assert a retract

Tyto predikáty umožňují explicitní práci s databází. assert(C)

Tento cíl uspěje pouze jednou a jako vedlejší efekt doplní klauzuli C do databáze a to v závislosti na implementaci buď jako první nebo jako poslední v odpovídající proceduře. Predikát asserta

- 68 -

Jiří Dvořák


doplňovanou klauzuli umístí jako první klauzuli příslušné procedury a predikát assertz ji umísí jako poslední. Klauzule C se zapisuje takto: nebo (pravidlo)

fakt

přičemž fakt ani pravidlo nejsou zakončeny tečkou. Příklad: Určení bratra bez opakování bratr_bez_opak(X,Y):bratr(X,Y),not(nalezen(X,Y)),asserta(nalezen(X,Y)).

Cíl retract(C)

uspěje při nalezení prvé klauzule v databázi, která se unifikuje s klauzulí C, a z databáze ji vypustí. Při opakovaném vyhodnocení uspěje, pokud se v databázi nachází další taková klauzule. Predikát retractall vypustí všechny takové klauzule najednou. Klauzule C se zapisuje stejně jako v predikátu assert. Predikát clause

Predikát clause zajišťuje nedestruktivní přístup ke klauzulím databáze. Při vyhodnocení cíle clause(Hlava,Tělo)

s nastavenou hodnotou proměnné Hlava se hledá v databázi klauzule, jejíž hlava se unifikuje s hodnotou prvního argumentu. Tělo této klauzule se pak unifikuje s druhým argumentem. Při unifikaci faktů se za tělo považuje predikát true. Klauzule z databáze nelze hledat pomocí jejich těla. Při zpětném navracení uspěje predikát clause tolikrát, kolikrát je možné unifikovat klauzuli z databáze se dvojicí argumentů. Při každé unifikaci klauzule se vytváří nová sada proměnných. Predikát bagof

Tento predikát umožňuje získat všechna možná řešení současně. bagof(X,P,L)

Vyhodnocením tohoto cíle se vytvoří seznam L všech objektů X takových, že je cíl P splněn (mezi X a P by měla existovat nějaká vazba vyjádřená společnými proměnnými). Příklad: Určení všech bratrů bez opakování bratr_bez_opak(X,Y):bratr(X,Y),not(nalezen(X,Y)), asserta(nalezen(X,Y)). vsichni_bratri1(X,L):bagof(Y,bratr_bez_opak(Y,X),L), retractall(nalezen(Y,X)),!. Predikát setof setof(X,P,L)

- 69 -

Jiří Dvořák


Funguje podobně jako bagof, avšak seznam L je uspořádaný a bez případných duplicit. Uspořádání je pro atomy abecední, pro čísla podle hodnoty, a pro složené termy se řídí hlavním funktorem (případně nejvyšším rozdílným funktorem nebo argumentem zleva). Příklad: Určení všech bratrů bez opakování vsichni_bratri2(X,L):-setof(Y,bratr(Y,X),L). Predikát findall findall(X,P,L)

Funguje podobně jako bagof s tím rozdílem, že do seznamu L se dostanou všechny hodnoty X, které splňují cíl P pro libovolné hodnoty jeho volných proměnných.

4.16 Vstup a výstup Systém předpokládá existenci aktuálního vstupního souboru (standardně klávesnice) a aktuálního výstupního souboru (standardně obrazovka terminálu). Při provádění základních operací vstupu a výstupu není třeba explicitně specifikovat, o jaké zařízení (soubor) se jedná. Základní operace vstupu a výstupu předpokládají sekvenční způsob přístupu k datům souborů. Soubory mají standardní textový charakter. Pokud mají zpracovávaná data tvar vyhovující syntaxi termů, používají se pro jejich vstup a výstup standardní predikáty read a write. Jestliže je třeba vycházet z obecněji strukturovaných dat, pak jsou k dispozici standardní predikáty get, get0 a put pro vstup a výstup znaků. Přesměrování vstupu see(Jméno_souboru)

Tento predikát se splní, je-li daným jménem určen existující soubor. V tom případě je vedlejším efektem otevření příslušného souboru a přesměrování vstupu na tento soubor. Klávesnice má pro účely této identifikace stanoveno dohodnuté jméno user. seeing(F)

Vyhodnocením tohoto cíle se proměnná F nastaví na jméno aktuálního vstupního souboru. seen

Tento predikát způsobí zavření aktuálního vstupního souboru a přepnutí vstupu na standardní vstupní soubor. Přesměrování výstupu tell(Jméno_souboru)

Tento predikát přesměruje výstup na určený výstupní soubor. Obrazovka má pro účely této identifikace stanoveno dohodnuté jméno user. telling(F)

Vyhodnocením tohoto cíle se proměnná F nastaví na jméno aktuálního výstupního souboru. told

- 70 -

Jiří Dvořák


Tento predikát způsobí uzavření aktuálního výstupního souboru a přepnutí výstupu na standardní výstupní soubor. Vstup termů read(X)

Tento predikát způsobí načtení dalšího termu z aktuálního vstupního souboru (každý term zde musí být zakončen tečkou a mezerou nebo přechodem na nový řádek). Přečtený term se pak unifikuje s argumentem X a pokud je jím nenastavená proměnná, provede se nastavení X na právě přečtený term. Pokud unifikace nebyla úspěšná, cíl read(X) selže a to způsobí zpětný návrat a požadavek na splnění předchozího cíle, neboť read samotný je deterministický predikát a pro každé vyhodnocení poskytuje jen jedno řešení nebo selhání. Speciální situace nastane, pokud se při pokusu o vstup termu dosáhlo konce vstupního souboru – v takovém případě se proměnná X nastaví na hodnotu end_of_file. Výstup termů write(X)

Tento predikát způsobí výstup termu X na aktuální výstupní soubor. Term se zobrazí ve standardní podobě odpovídající syntaktické definici termů. Pro ovládání tvaru výstupu jsou k dispozici následující predikáty: tab(N)

provede zápis N mezer nl

způsobí přechod na nový řádek Vstup a výstup znaků get0(C)

Provede se vstup jednoho znaku z aktuálního vstupního souboru přičemž proměnná C se nastaví na číselnou hodnotu ASCII kódu přečteného znaku. get(C)

Vyhodnocením tohoto predikátu se čtecí pozice ve vstupním souboru posune až za první tisknutelný znak a číselná hodnota ASCII kódu tohoto znaku se stane hodnotou proměnné C. put(C)

Do aktuálního výstupního souboru se provede záznam znaku, jehož ASCII kód má číselnou hodnotu C.

4.17 Cykly Iterativní operace je možné v Prologu provádět prostřednictvím koncové rekurze. Prolog má ale pro vyjádření iterace ještě další možnost, která se podobá repeat-until cyklu v imperativním - 71 -

Jiří Dvořák


programování. Opakování se v těchto cyklech vyvolává selháním a jsou užitečné pouze ve spojení s predikáty, které mají nějaký vedlejší účinek. Nalezení všech možných řešení zadaného cíle se může zajistit takto: vsechna_reseni(C,X):call(C),write(X),nl,fail. vsechna_reseni(C,X).

Proměnná X se musí vyskytovat v cíli C. Příklad (vztah predek je definován na str. 47): vsichni_predci(predek(X,Y),X):call(predek(X,Y)),write(X),nl,fail. vsichni_predci(predek(X,Y),X). Predikát repeat

Predikát repeat je při volání okamžitě splněn a je také vždy splněn při navracení. Tento predikát se chová tak, jako by byl definován programem repeat. repeat:-repeat.

Cyklus s podmínkou: repeat,C1,C2, … ,Cn,Podm,!.

C1, C2, … , Cn jsou cíle, které se mají splnit a Podm je podmínka ukončení cyklu. Příklad: vstup_a_vypis:repeat,write('Zadej cislo:'), nl,read(N),N1 is 10*N, write(N1),nl,N<0,!.

- 72 -

Jiří Dvořák


5. Využití jazyka Prolog pro řešení úloh umělé inteligence 5.1 Přehled aplikací Kniha [1] popisuje aplikace Prologu v následujících oblastech UI: •

heuristické hledání

•

expertní systémy a reprezentace znalostí

•

plánování

•


•

strojové učení

•

hraní her

V knize [13] jsou ukázky použití Prologu při řešení následujících problémů: •

strategie prohledávání

•

plánování

•

implementace pravidlového expertního systému

•

implementace sémantických sítí a rámců

•

strojové učení

•


V knize [5] jsou ukázky použití Prologu pro prohledávání a pro zpracování přirozeného jazyka). Kniha [20] obsahuje popis implementace prohledávání. V knize [19] jsou uvedeny ukázky použití Prologu pro hraní her a tvorbu expertního systému. Významnou a častou aplikací Prologu je tvorba expertních systémů. Této problematice jsou věnovány např. knihy [3] a [15]. Příkladem implementace exxpertního systému v Prologu je systém FLEX firmy Logic Programming Associates. Jedná se programové prostředí, umožňující používat pravidla a rámce pro reprezentaci znalostí a dopředné a zpětné řetězení pro inferenci. Další aplikace Jazyka Prolog je možno najít na stránkách firem Amzi!® a Applied Logic Systems, Inc.

5.2 Příklad využití Prologu pro tvorbu expertního systému Vyhodnocovací mechanismus Prologu funguje vlastně jako inferenční mechanismus zpětného řetězení v pravidlovém expertním systému, kdy se postupuje od cílových hypotéz k výchozím faktům. Na rozdíl od Lispu tedy při aplikaci Prologu pro tvorbu expertního systému není nutné programovat žádný infernční mechanismus a prologovský program může představovat bázi znalosí a bázi faktů. Příklad použití Prologu pro tvorbu jednoduchého expertního systému popsaný v této podkapitole vychází z knihy [1] a je rozšířen o možnost komunikace s uživatelem.

- 73 -

Jiří Dvořák


Jedná se o systém, který diagnostikuje příčiny mokra v domě. Zkoumány jsou tři místnosti: hala, koupelna a kuchyně. Z haly vedou dveře do koupelny a do kuchyně. V kuchyni se nachází okno. Situaci můžeme popsat pomocí následujících pravidel: unik_vody_v_koupelne :- hala_mokra, kuchyne_sucha. problem_v_kuchyni :- hala_mokra, koupelna_sucha. zadna_voda_zvenku :- not dest; okno_zavrene. unik_vody_v_kuchyni :- problem_v_kuchyni, zadna_voda_zvenku.

Počáteční fakty: hala_mokra. koupelna_sucha. okno_zavrene.

Systému můžeme pokládat dotazy ?- unik_vody_v_koupelne. no ?- unik_vody_v_kuchyni. yes

Nedostatkem tohoto systému je skutečnost, že uživatel musí zadat všechna relevantní fakta ještě před zahájením procesu usuzování. Fakta by se měla zadávat interaktivně v dialogu s expertním systémem v okamžiku, kdy jsou zapotřebí. Uvedený nedostatek můžeme odstranit definováním dotazovací procedury ask: ask(X):- known(ano,X),!. ask(X):- known(_,X),!,fail. ask(X):- write(X),write('?(ano/ne):'), read(Y),asserta(known(Y,X)),Y=ano.

Pak musíme doplnit do výše uvedeného programu tato pravidla: hala_mokra:- ask(hala_mokra). kuchyne_sucha:- ask(kuchyne_sucha). koupelna_sucha:- ask(koupelna_sucha). dest:-ask(dest). okno_zavrene:- ask(okno_zavrene). Nová syntaxe pravidel a faktů

Dalším nedostatkem výše uvedeného systému je špatná čitelnost znalostí, vyplývající z použití prologovské syntaxe. Předpokládejme, že bychom chtěli používat následující tvar pravidel, který je pro pravidlové expertní systémy obvyklejší:

- 74 -

Jiří Dvořák


if podmínka then závěr

Podmínka může být složena z jednoduchých podmínek nebo jejich negací spojených pomocí spojek and a or, přičemž negace je zapsána pomocí operátoru ne. Tuto notaci nám umožní zavedení nových operátorů :-op(800,fx,if). :-op(700,xfx,then). :-op(300,xfy,or). :-op(200,xfy,and). :-op(100,fx,ne).

Fakta budeme zapisovat následovně: fact(tvrzení).

Pak mohou být pravidla popisující příčiny mokra v domě přepsána takto: if hala_mokra and kuchyn_sucha then unik_vody_v_koupelne. if hala_mokra and koupelna_sucha then problem_v_kuchyni. if ne dest or okno_zavrene then zadna_voda_zvenku. if problem_v_kuchyni and zadna_voda_zvenku then unik_vody_v_kuchyni. Interpret pro novou syntaxi is_true(P):- ask(P). is_true(ne P):- not ask(P). is_true(P):- if Podmínka then P, is_true(Podmínka). is_true(P1 and P2):- is_true(P1),is_true(P2). is_true(P1 or P2):- is_true(P1);is_true(P2).

Příklad dotazu: ?- is_true(unik_vody_v_koupelne).

Procedura ask musí být upravena následovně: ask(X):- known(ano,X),!. ask(X):- known(_,X),!,fail. ask(X):- atomic(X), not if Podminka then X, write(X),write('?(ano/ne): '), read(Y),asserta(known(Y,X)),Y=ano.

Pro opětovné použití expertního systému je nutné doplnit predikát reset: reset:- retractall(known(_,_)).

- 75 -

Jiří Dvořák


Mechanismus dopředného řetězení forward:- new_derived_fact(P),!, write('Odvozeno:'),write(P),nl, assert(known(ano,P)),forward; write('Zadna dalsi fakta:'). new_derived_fact(Zaver):- if Podm then Zaver, not known(ano,Zaver),composed_fact(Podm). composed_fact(Podm):- ask(Podm). composed_fact(ne Podm):- not ask(Podm). composed_fact(Podm1 and Podm2):composed_fact(Podm1),composed_fact(Podm2). composed_fact(Podm1 or Podm2):composed_fact(Podm1);composed_fact(Podm2). Vysvětlovací mechanismus :-op(800,xfx,<=).

explain(P):- known(ano,P), write(known(ano,P)), nl. explain(ne P):- known(ne,P), write(known(ne,P)), nl. explain(P):- if Podm then P, write(P <= Podm),nl,explain(Podm). explain(P1 and P2):- explain(P1),explain(P2). explain(P1 or P2):- explain(P1);explain(P2).

Predikát explain poskytne vysvětlení, jak systém při vyhodnocení dotazu is_true(P) dospěl k závěru, že P platí. Neúspěch při vyhodnocení tohoto dotazu vysvětlí následující predikát why_fails. why_fails(P):- known(ne,P), write(known(ne,P)), nl. why_fails(ne P):- known(ano,P), write(known(ano,P)), nl. why_fails(P):- if Podm then P, write(P <= Podm),nl,why_fails(Podm). why_fails(P1 and P2):- why_fails(P1);why_fails(P2). why_fails(P1 or P2):- why_fails(P1),why_fails(P2).

Příklady dotazů: ?- explain(unik_vody_v_koupelne). ?- why_fails(unik_vody_v_koupelne).

- 76 -

Jiří Dvořák


Zpracování neurčitosti :-op(900,xfx,::).

% Operator pro zadani jistoty pravidla

certainty(P,Jist):-ask(P,Jist). certainty(ne P,Jist):-ask(P,J),Jist is 1-J. certainty(P,Jist):if Podm then P :: J1, certainty(Podm,J2), Jist is J1*J2. certainty(Podm1 and Podm2,Jist):certainty(Podm1,Jist1), certainty(Podm2,Jist2), Jist is min(Jist1,Jist2). certainty(Podm1 or Podm2,Jist):certainty(Podm1,Jist1), certainty(Podm2,Jist2), Jist is max(Jist1,Jist2). % Interface ask(X,J):-known(X,J),!. ask(X,J):-atomic(X), not if Podminka then X :: _, write(X),write(' ?jistota: '), read(J),asserta(known(X,J)).

Předpokládáme, že stupně jistoty pravidel a faktů nabývají hodnot z intervalu 〈0; 1〉. Příklad pravidel: if hala_mokra and kuchyn_sucha then unik_vody_v_koupelne :: 0.8. if hala_mokra and koupelna_sucha then problem_v_kuchyni :: 0.9. if not dest or okno_zavrene then zadna_voda_zvenku :: 1. if problem_v_kuchyni and zadna_voda_zvenku then unik_vody _v_kuchyni :: 1.

Příklad dotazu: ?- certainty(unik_vody_v_koupelne,X).

- 77 -

Jiří Dvořák


Literatura [1]

Bratko, I. Prolog Programming for Artificial Intelligence. Wokingham, England, AddisonWesley 1990.

[2]

Bahrami, A. Designing Artificial Intelligence Based Software. Wilmslow, Sigma Press 1988.

[3]

Callear, D. Prolog Programming for Students. London, Thomson 1994.

[4]

Charniak, E. et al. Artificial Intelligence Programming. Hillsdale, New Jersey, LEA Publishers 1987.

[5]

Clocksin, W.F. and Mellish, C.S. Programming in Prolog. Berlin, Springer-Verlag 1996.

[6]

Deransart, P., Ed-Dbali, A. Cervoni, L. Prolog: The Standard. Berlin, Springer-Verlag 1996.

[7]

Eisenbach, S. (ed.). Functional Programming: Languages, Tools and Architectures. Chichester, England, Ellis Horwood Limited 1987.

[8]

Grillmeyer, O. Exploring Computer Science with Scheme. Berlin, Springer-Verlag 1998.

[9]

Jirků, P. a kol. Programování v jazyku Prolog. Praha, SNTL 1991.

[10] Kalaš, I. Iné programovanie – stretnutie s jazykom Lisp. Bratislava, Alfa 1990. [11] Kolář, J. Jazyky pro umělou inteligenci. Skripta. Praha, ČVUT 1994. [12] Koschmann, T.D. The Common Lisp Companion. New York, John Wiley & Sons 1990. [13] Luger, G.F. Artificial Intelligence. Structures and strategies for Complex Problem Solving. Harlow, Addison-Wesley 2002. [14] Mařík, V. a kol. Umělá inteligence 2. Praha, Academia 1997. [15] Merrit, D. Building Expert Systems in Prolog. Berlin, Springer-Verlag 1989. [16] Molnár, L. a Návrat, P. Programovanie v jazyku Lisp. Bratislava, Alfa 1988. [17] Polák, J. Prolog. Praha, Grada 1992. [18] Queinnec, Ch. Lisp in Small Pieces. Cambridge University Press 1996. [19] Sterling, L. and Shapiro, E. The Art of Prolog. Cambridge, Massachusets, MIT Press 1994. [20] Spivey, M. An Introduction to Logic Programming through Prolog. London, Prentice Hall 1996. [21] Thomson, S. Miranda: The Craft of Functional Programming. Wokingham, England, Addison-Wesley 1995. [22] Wilensky, R. LISPcraft. New York, Norton, 1984. [23] Winstanley, G. Program Design for Knowledge Based Systems. Wilmslow, Sigma Press 1987. [24] Winston, P.H. and Horn, B.K.P. Lisp. Reading, Massachusets, Addison-Wesley 1981.

- 78 -

Jiří Dvořák


Seznam internetových adres Funkcionální programovací jazyky

Franz Inc_Home Page http://www.franz.com/ BBTech Corporation http://www.bbtech.com/ Haskell http://www.haskell.org/ Miranda http://www.engin.umd.umich.edu/CIS/course.des/cis400/miranda/miranda.html New York University Natural Language Computing Project Downloading Free Software http://dce.felk.cvut.cz/lisp/nclp/free.html NYU Natural Language Computing -- LISP Tutorial http://dce.felk.cvut.cz/lisp/nclp/lisp.html Scheme http://swiss.csail.mit.edu/projects/scheme/ Xanalys LispWorks http://www.lispworks.com/ XLISP Home Page http://www.mv.com/ipusers/xlisper/ XLISP-PLUS Home Page http://almy.us/xlisp.html Logické programovací jazyky

Amzi!® http://www.amzi.com/ Amzi! Logic Explorer http://www.amzi.com/share.htm Applied Logic Systems, Inc. http://www.als.com/als.html Cetus Links OO Prolog http://www.cetus-links.org/oo_prolog.html ECLiPSe http://www.icparc.ic.ac.uk/eclipse/ Gödel http://www.cs.bris.ac.uk/~bowers/goedel.html Interactive Prolog Guide http://kti.ms.mff.cuni.cz/~bartak/prolog/ Logic Programming Associates http://www.lpa.co.uk/ LPA Prolog http://www.lpa.co.uk/ Mercury http://www.cs.mu.oz.au/research/mercury/ Merritt, D. Building Expert Systems in Prolog http://www.amzi.com/ExpertSystemsInProlog/index.htm Nilsson, U. and Maluszynski, J. Logic, Programming and Prolog http://www.ida.liu.se/~ulfni/lpp/ Quintus Prolog http://www.quintus.com/products/prolog/ Read Adventure in Prolog on-line http://www.amzi.com/AdventureInProlog/index.htm SICStus Prolog 3 http://www.sics.se/sicstus.html Strawberry Prolog http://www.dobrev.com/ SWI-Prolog http://www.swi-prolog.org/ Visual Prolog http://www.visual-prolog.com/ - 79 -

Jiří Dvořák


Příloha A: Přehled definovaných jmen Lispu and

22

mapl

29

append

19

maplist

28

apply

24

member

20

atom

15

minusp

22

boundp

21

nconc

31

car

13

not

22

cdr

13

null

20

close

35

numberp 21

cond

15

open

35

cons

14

or

22

defmacro

30

plusp

22

defun

16

princ

35

do

25

print

35

dolist

26

prog1

27

dotimes

26

prog2

27

eq

15

progn

27

equal

20

progv

27

eval

23

putprop

34

funcall

24

quote

12

gensym

34

read

35

get

34

remprop

34

last

19

reverse

20

length

19

rplaca

31

let

27

rplacd

31

lambda

29

setf

32

list

19

setq

13

listp

21

symbolp

21

mapc

28

terpri

35

mapcan

32

zerop

22

mapcar

28

mapcon

32 - 80 -

Jiří Dvořák


Příloha B: Přehled definovaných jmen a operátorů Prologu =

51

is

57

==

66

nl

71

=..

64

nonvar

65

\=

51

not

68

\==

66

op

61

arg

64

put

71

assert

68

read

71

atom

63

reconsult

68

atomic

63

repeat

72

bagof

69

retract

68

call

66

see

70

clause

69

seeing

70

compound

63

seen

70

constant

63

setof

69

consult

68

tab

71

fail

68

tell

70

findall

70

telling

70

functor

64

told

70

get

71

var

65

get0

71

write

71

integer

63

- 81 -

Jiří Dvořák


Příloha C: Výsledky úloh na procvičení Úlohy 2.5

a) (defun Abs (X) (cond ((< X 0) (- 0 X)) (T X)))

b) (defun Max (X Y) (cond ((>= X Y) X) (T Y) ))

c) (defun Delka (S) (cond ((Prazdny S) 0) (T (+ 1 (Delka (cdr S)))) ))

d) (defun Posl (X) (cond ((Prazdny X) nil) ((Prazdny (cdr X)) (car X)) (T (Posl(cdr X))) ))

e) (defun BezPosl (X) (cond ((Prazdny X) nil) ((Prazdny (cdr X)) nil) (T (cons (car X) (BezPosl (cdr X)))) ))

Úlohy 2.7

a) (defun Clen (X S) (cond ((null S) nil) ((equal X (car S)) S) (T (Clen X) (cdr S))) ))

- 82 -

Jiří Dvořák


Úlohy 2.9

a) (defun fact (n) (fact_kr n 1)) (defun fact_kr (n acc) (cond ((zerop n) acc) (t (fact_kr (- n 1) (* n acc))) ))

b) (defun fakt (n) (do ((i n (- i 1)) (m 1 (* m i))) ((zerop i) m)))

c) (defun sum-list (num-list) (do ((x num-list (cdr x)) (s 0 (+ s (car x)))) ((null x) s))) ;Jina verze (defun sum1-list (num-list) (setq s 0) (do ((x num-list (cdr x))) ((null x) s) (setq s (+ s (car x)))))

Úlohy 4.7

a) % Z je maximem z cisel X a Y max(X,Y,Z):-Z>=X,Z>=Y,Z=:=X. max(X,Y,Z):-Z>=X,Z>=Y,Z=:=Y. % Jednodussi formulace max(X,Y,X):-X>=Y. max(X,Y,Y):-X
b) gcd(N,N,N). gcd(M,N,D):-M>N,M1 is M-N, gcd(M1,N,D).

- 83 -

Jiří Dvořák


gcd(M,N,D):-M
a) pridej(X,L,L):-clen(X,L). pridej(X,L,[X|L]).

b) pridej_na_konec([],X,[X]). pridej_na_konec([H|T],X,[H|NT]):- pridej_na_konec(T,X,NT).

c) zrus(X,[X|L],L). zrus(X,[Zac|Zb],[Zac|L]):-zrus(X,Zb,L).

d) posl([X],X). posl([X,Y|T],Z):-posl([Y|T],Z).

e) bezposl([],[]). bezposl([H|T],[H|NT]):-bezposl(T,NT).

f) posl(L,X):-pridej_na_konec(_,X,L). bezposl(L,NL):-pridej_na_konec(NL,_,L).

g) delka([],0). delka([X|Y],N):- delka(Y,N1), N is N1+1.

- 84 -

Jazyky pro umělou inteligenci

Recommend Documents