Bc. Vojtěch Hordějčuk

„Určitě se vám už někdy stalo, že jste napsali program a on vám nefungoval.” - F. Zavoral

Domů » Wiki » Programovací jazyky » Jazyk PROLOG

Jazyk PROLOG

Programovací jazyk PROLOG pochází z Francie a poprvé se objevil kolem roku 1972. Je založený na matematické disciplíně zvané logika a proto je velmi abstraktní – programátor se nemusí zabývat přesným výpočetním procesem, zapisuje pouze pravidla.

  • program = množina axiomů
  • výpočet = důkaz platnosti výrazu na základě uvedených axiomů

Interpretery PROLOGu jsou většinou konzolové aplikace. Programování probíhá následovně:

  • vytvoření souboru s axiomy
  • spuštění konzole PROLOGu
  • načtení souboru příkazem [soubor].
  • pokládání dotazů

Základní syntaxe

Každý axiom končí tečkou. Každá proměnná začíná velkým písmenem (nebo podtržítkem). Existuje speciální proměnná _, která se při výpočtu nebere v potaz (prostě se „zahodí“). Axiomy, které mají platit současně, se oddělejí čárkou = AND. Axiomy, ze kterých má platit alespoň jeden, se oddělují středníkem = OR. Operátor if se zapisuje jako :-.

Seznamy

Další běžnou strukturou v jazyce PROLOG jsou seznamy. Seznam je uspořádaná množina datových struktur. Seznam je uzavřen hranatými závorkami a jednotlivé prvky jsou odděleny čárkou. Prázdný seznam se zapisuje jako [].

[a,b,c]
[concert,dream theater,[john,peter,tamara,debora]]

zdrojový kód (PROLOG) - zobrazit (58 znaků)

PROLOG dále umožňuje oddělit první prvek (head) a zbytek (tail) seznamu pomocí speciálního symbolu – svislítka (|). Rozdělíme-li například seznam [prvni,druhy,tre­ti] jako [H|T], bude H = prvni a T = [druhy,treti].

Řešené příklady

Kdo má co rád?

Jan má rád Marii, víno a hry. Marie má také ráda víno. Co má rád Jan? Kdo má rád víno?

likes(jan,marie).
likes(jan,vino).
likes(jan,zpev).
likes(marie,vino).

zdrojový kód (PROLOG) - zobrazit (70 znaků)

Co má rád Jan?

?- likes(jan,X).

zdrojový kód (PROLOG) - zobrazit (16 znaků)

Výsledek:

X = marie ;
X = vino ;
X = zpev

zdrojový kód (PROLOG) - zobrazit (31 znaků)

Kdo má rád víno?

?- likes(X,vino).

zdrojový kód (PROLOG) - zobrazit (17 znaků)

Výsledek:

X = jan ;
X = marie

zdrojový kód (PROLOG) - zobrazit (19 znaků)

Kdo je šťastný?

Uršula je krásná. Norbert je krásný a bohatý. Berta je bohatá a silná. Pierre je silný a krásný. Bruno je hodný a silný. Všem mužům se líbí krásné ženy. Všichni bohatí muži jsou šťastní. Štastný je každý muž, kterému se líbí žena, které se líbí i on. Štastná je každá žena, které se líbí muž, kterému se líbí i ona. Bertě se líbí všichni muži, kterým se líbí i ona. Uršule se líbí všichni muži, kteří jsou buď bohatí a hodní, nebo krásní a silní. Kdo je šťastný?

woman(ursula).
woman(bertha).
man(norbert).
man(pierre).
man(bruno).
rich(norbert).
rich(bertha).
strong(bertha).
strong(pierre).
strong(bruno).
nice(pierre).
nice(norbert).
nice(ursula).
kind(bruno).
happy(X) :- man(X),rich(X).
happy(X) :- man(X),like(X,Y),woman(Y),
like(Y,X).
happy(X) :- woman(X),like(X,Y),man(Y),like(Y,X).
like(X,Y) :- man(X),woman(Y),nice(Y).
like(bertha,X) :- man(X),like(X,bertha).
like(ursula,X) :- man(X),like(X,ursula),(rich(X),kind(X);nice(X),strong(X)).

zdrojový kód (PROLOG) - zobrazit (483 znaků)

Dotaz:

?- happy(X).

zdrojový kód (PROLOG) - zobrazit (12 znaků)

Výsledek:

X = norbert ;
X = pierre ;
X = ursula ;
no

zdrojový kód (PROLOG) - zobrazit (42 znaků)

Největší společný dělitel

Napište predikát gcd(A,B,C), který do proměnné C přiřadí největší společný dělitel přirozených čísel A a B.

gcd(A,A,A).
gcd(A,B,Result) :- A<B, C is B-A, gcd(A,C,Result).
gcd(A,B,Result) :- A>B, gcd(B,A,Result).

zdrojový kód (PROLOG) - zobrazit (103 znaků)

Najdi největší společný dělitel čísel 1554 a 883.

?- gcd(1554, 883, X).

zdrojový kód (PROLOG) - zobrazit (21 znaků)

Výsledek:

X = 1 ;
no

zdrojový kód (PROLOG) - zobrazit (10 znaků)

Počet dní mezi dvěma daty

Napište predikát interval(D1-M1-Y1,D2-M2-Y2,X), který do proměnné X přiřadí počet dní mezi daty D1-M1-Y1 a D2-M2-Y2 (včetně posledního dne). Predikát musí počítat s přestupnými roky. Pro zjednodušení předpokládejte, že první datum (D1-M1-Y1) je dřívější než druhé datum (D2-M2-Y2).

/* pravidla pro přestupné roky */

leapYear(Y) :- A is Y mod 4, B is Y mod 100, A=0, B\=0.
leapYear(Y) :- A is Y mod 400, A=0.

/* počet dní v roce */

daysInYear(Y,X) :- X is 366, leapYear(Y).
daysInYear(Y,X) :- X is 365, not(leapYear(Y)).

/* počet dní od začátku roku */

days(D-1,X)  :- X is D.
days(D-2,X)  :- X is D+31.
days(D-3,X)  :- X is D+31+28.
days(D-4,X)  :- X is D+31+28+31.
days(D-5,X)  :- X is D+31+28+31+30.
days(D-6,X)  :- X is D+31+28+31+30+31.
days(D-7,X)  :- X is D+31+28+31+30+31+30.
days(D-8,X)  :- X is D+31+28+31+30+31+30+31.
days(D-9,X)  :- X is D+31+28+31+30+31+30+31+31.
days(D-10,X) :- X is D+31+28+31+30+31+30+31+31+30.
days(D-11,X) :- X is D+31+28+31+30+31+30+31+31+30+31.
days(D-12,X) :- X is D+31+28+31+30+31+30+31+31+30+31+30.

daysFromStart(D-M-Y,X) :- days(D-M,A),
                          ((leapYear(Y), M>2, X is A+1);
                           X is A).

/* počet dní mezi dvěma roky */

daysBetweenYears(Y,Y,0).
daysBetweenYears(Y1,Y2,X) :- A is Y1+1,
                             daysInYear(Y1,B),
                             daysBetweenYears(A,Y2,C),
                             X is B+C.

/* stejný den */

interval(D-M-Y,D-M-Y,1).

/* stejný měsíc */

interval(D1-M-Y,D2-M-Y,X) :- X is abs(D2-D1)+1.

/* stejný rok */

interval(D1-M1-Y,D2-M2-Y,X) :- daysFromStart(D1-M1-Y,A),
                               daysFromStart(D2-M2-Y,B),
                               X is abs(B-A)+1.

/* obecný dotaz */

interval(D1-M1-Y1,D2-M2-Y2,X) :- daysBetweenYears(Y1,Y2,A),
                                 daysFromStart(D1-M1-Y1,B),
                                 daysFromStart(D2-M2-Y2,C),
                                 X is A+C-B.

zdrojový kód (PROLOG) - zobrazit (1673 znaků)

Kolik dní se nachází mezi daty 21.2.1998 a 22.10.2009?

?- interval(21-2-1998,22-10-2009,X).

zdrojový kód (PROLOG) - zobrazit (36 znaků)

Výsledek:

X = 4261 .

zdrojový kód (PROLOG) - zobrazit (10 znaků)

Hlavička a zbytek seznamu

Napište predikát head(L,H), který do proměnné H přiřadí hlavičku seznamu L a predikát tail(L,T), který do proměnné T přiřadí zbytek seznamu L.

head([H|_],H).
tail([_|T],T).

zdrojový kód (PROLOG) - zobrazit (29 znaků)

Vyhledávání v seznamu

Napište predikát ison(A,L), který platí právě když se prvek A nachází v seznamu L. K řešení využijte rekurze.

Prohledávaný seznam se v každém kroku rozdělí na hlavičku a zbytek, přičemž nejprve se ověří, zda se hlavička nerovná hledanému prvku. Pokud ne, proces se opakuje rekurzivně pro zbytek seznamu. Dosáhne-li PROLOG během vyhledávání konce seznamu, skončí vyhledávání bez výsledku.

ison(A,[A|_]).
ison(A,[_|Tail] :- ison(A,Tail).

zdrojový kód (PROLOG) - zobrazit (47 znaků)

Umocnění seznamu

Napište predikát square(L1,L2), který jako parametr přijme seznam celých čísel L1 a vytvoří seznam L2 obsahující hodnoty ze seznamu L1 umocněné na druhou.

square([],[]).
square([H|T],[R1|R2]) :- R1 is H*H, square(T,R2).

zdrojový kód (PROLOG) - zobrazit (64 znaků)

Najdi rozdíly seznamů

Napište predikát diff(L1,L2,L3), který vytvoří seznam L3 obsahující prvky ze seznamu L1, které se nenachází v seznamu L2.

ison(A,[A|_]).
ison(A,[_|Tail] :- ison(A,Tail).

diff(L,[],L).
diff([],_,[]).
diff([H|T],L,[H|R]) :- not(ison(H,L)), diff(T,L,R).
diff([_|T],L,R) :- diff(T,L,R).

zdrojový kód (PROLOG) - zobrazit (161 znaků)

Výběr ze zásobníků

Napište predikát pick(N,B,Star­t,Left), který vybere určitý počet prvků ze zadaného zásobníku. N je počet prvků k odebrání, B je index zásobíku. Start je seznam nezáporných celých čísel udávající původní počet prvků v každém zásobníku. Seznam Left je výsledný seznam, který vznikne ze seznamu Start odebráním N prvků ze zásobníku s indexem B. Omezení je následující: počet prvků v každém zásobníku nesmí být záporný. Pokud chce uživatel vybrat více prvků, než je v zásobníku k dispozici, program musí skončit bez výsledku.

pick(N,0,[Pick|X],[Picked|X]) :- Picked is Pick-N,Picked>=0.
pick(N,I,[H|T],[HL|TL]) :- J is I-1,HL is H,!,pick(N,J,T,TL).

zdrojový kód (PROLOG) - zobrazit (122 znaků)

Reference