Prolog

• instance logického výpočetního paradigma
  • program = databáze faktů a pravidel + cíl
  • výpočet = dokazování cíle metodou SLD rezoluce
  • výsledek = pravda/nepravda a hodnoty volných proměnných, pro které je cíl dokazatelný
  • Prolog - jediný programovací jazyk

SWI-Prolog

• Relativně úplná implementace Prologu
• Freeware
• https://www.swi-prolog.org/
• interpret swipl
• Veškeré povely ukončeny tečkou.

Základní povely

• Ukončení prostředí: halt.
• Nápověda: help.
• Načtení souboru jmeno.pl: consult(jmeno) nebo [jmeno]
• Databáze fakt a pravidel uvedena v externím souboru.
• Cíle zadávány skrze interpret

Notace fakt

• Fakta začínají malým písmenem a končí tečkou.
• Fakta jsou konstanty (nulární relace) a n-ární relace.
• Počet parametrů udáván u jména za lomítkem: jmeno/N

tohleJeFakt.
tohleTaky(parametr1,parametr2,...,parametrN).
fakt /* a /* zanoreny */ komentar */ .

Proměnné

• Jména začínají velkým písmenem nebo podtržítkem.
• Je možné je využít v dotazech
• Interpreter se pokusí najít vyhovující přiřazení

?- kamaradi(vincenc,X).
X = kvido ; (; = uživatel není spokojený s výsledkem)
X = ferenc. (. = není další možnost)

Databáze s pravidly

• Zápis: clovek(X) :- zena(X).
• Význam: Pokud platí zena(X), pak platí clovek(X)

Disjunkce

• Zápis: clovek(X) :- zena(X); muz(X)
• Alternativní zápis

clovek(X) :- zena(X).
clovek(X) :- muz(X).

• Význam: (zena(X) ∨ muz(X)) → clovek(X)

Konjunkce

• Zápis: unikat(X) :- zena(X), muz(X).
• Význam: (zena(X) ∧ muz(X)) → clovek(X)

Termy - základní stavební kameny

• Atomy.
• Čísla.
• Proměnné.
• Strukturované termy.

Atomy

• Řetězce začínající malým písmenem, obsahující písmena číslice a znak podtržítko.
• Libovolné řetězce uzavřené v jednoduchých uvozovkách.
• atom/1 - Pravda pokud paramter je nestrukturovaným atomem.

Čísla

• Desetinné číslo zapisujeme tečkou.
• Porovnávání s aritmetickým vyhodnocením pomocí =:=

?- 4 =:= 3+1
true

• Aritmetické vyhodnocení a přiřazení pomocí is

?- A is 2*3
A = 6.

• number/1 - Pravda, pokud je parametr číslo.
• float/1 - Pravda, pokud je parametr desetinné číslo-
• =\=/2 - Aritmetické neekvivalence.

Strukturované termy

• Funktor (název relace) následovaný sekvencí argumentů.
• Argumenty se uvádějí v závorkách, oddělené čárkou.
• Mezi funktorem a seznamem argumentů nesmí být mezera
• Je možná rekurze.

Arita

• Počet argumentů strukturovaného termu. funktor/N
• Stejný funktor s jinou aritou označuje jiný term.

Unifikace

• Dva termy jsou unifikovatelné, pokud jsou identické, anebo je možné zvolit hodnoty proměnných použitých v unifikovaných termech tak, aby po dosažení těchto hodnot byly termy identické.

Operátor =/2

• Realizuje unifikaci v Prologu.
• Lze zapisovat infixově.
• Binární operátor ne-unifikace \=, tj. ve standardní notaci \=/2.

Výsledek unifikace

• Ano/Ne
• Unifikační přiřazení do proměnných (substituce).

Kontrola sebe výskytu

• Pokud se samostatná proměnná vyskytuje jako podvýraz v druhém.
• unify_with_occurs_check

Seznamy

• sekvence prvků (mohou být typově různé)
• Pro dekompozici na hlavu a tělo se používá znak |
• Hlavu lze zobecnit na neprázdnou konečnou sekvenci prvků.
• Seznam: [jedna,dva|zbytek] = [1,2,3,4]
• Můžeme použít pouze jedno |

Anonymní proměnná

• _, nelze odkázat v jiném místě programu
• V unifikaci, neklade žádné omezení.
• [_,X,_,Y|_]

Od funkcí k relacím

• Místo f(A) = B použijme r(A,B)

Funkce na seznamech

• length(L,I) je pravda pokud délka L má hodnotu I
• Prázdný seznam má délku 0.
• is_list/1 = Pravda, pokud parametr je seznam.
• member(X,L) = Je-li X prvkem seznamu L
• append(L1,L2,L3) = pravda, pokud seznam L3 je zřetězením L1 a L2

Syntaktická ekvivalence - operátor ==

?- 4 == 3+1
false.

?- 3+1 == 3+1
true.

Aritmetika

Typy

• Celá čísla - integer
  • Nativní typ, knihovna GMP
• Desetinná čísla - float
  • nativní typ, double z C
• racionální čísla - rational
  • reprezentované s využitím složeného termu rdiv(N,M)
  • Výsledek vrácená operátorem is/2 je kanonizován, tj. M je kladné a M a N nemají společného dělitele.
• Konverze a unifikace
• rdiv(N,1) se konvertuje na celé číslo N.
• Automatická konverze ve směru od celých čísel k desetinným
• Riziko vyvolání vyjimky přetečení.
• Čísla různých typů se neunifikují.

Řezy

• backtracking
• chceme kontrolovat výpočet prologu - vyhnout se nekonečným řešením, …

Operátor !/0

• Vždy jako podcíl uspěje
• Ovlivňuje způsob výpočtu = vedlejší efekt
• Eliminuje další volby, které by Prolog udělal při procházení výpočetního stromu, a to od okamžiku unifikace podcíle s levou stranou pravidla, ve kterém se predikát ! vyskytuje, až do místa výskytu !.

Upnutí

• při naražení na ! se jiná fakta a pravidla neberou v potaz

Prořezání

při řešní podcíle, při operátoru ! se předchozí unifikace fixují

Zelené řezy

• pro lepší efektivitu

Červené řezy

• odstranění operátoru se mění sémantiku program