Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Prolog

Prolog je logický programovací jazyk. Název Prolog pochází z francouzského programmation en logique (logické programování). Byl vytvořen Alainem Colmerauerem v roce 1972 jako pokus vytvořit programovací jazyk, který by umožňoval vyjadřování v logice místo psaní počítačových instrukcí. Prolog patří mezi tzv. deklarativní programovací jazyky, ve kterých programátor popisuje pouze cíl výpočtu, přičemž přesný postup, jakým se k výsledku program dostane, je ponechán na libovůli systému.

Prolog je využíván především v oboru umělé inteligence a v počítačové lingvistice (obzvláště zpracování přirozeného jazyka, pro nějž byl původně navržen). Syntaxe jazyka je velice jednoduchá a snadno použitelná pravě proto, že byl původně určen pro počítačově nepříliš gramotné lingvisty.

Prolog je založen na predikátové logice prvního řádu (konkrétně se omezuje na Hornovy klauzule). Běh programu je pak představován aplikací dokazovacích technik na zadané klauzule. Základními využívanými přístupy jsou unifikace, rekurze a backtracking.

Interpret Prologu se snaží nalézt nejobecnější substituci, která splní daný cíl - tzn. nesubstituuje zbytečně, pokud nemusí (použití interních proměnných - _123 atd.). Za dvě proměnné může být substituována jedna interní proměnná (např. při hledání svislé úsečky - konstantní X souřadnice) - tomu se říká unifikace proměnných. Pro proměnnou, jejíž hodnota může být libovolná, se v prologu užívá znak _.

Datové typy v prologu se nazývají termy. Základním datovým typem jsou atomy (začínají malým písmenem, nebo se skládají ze speciálních znaků (`+ - * / ...`, nebo jsou to znakové řetězce (`'text'`)). Dále jsou v prologu čísla (v komerčních implementacích i reálná), proměnné (velké písmeno) a struktury (definované rekursivně - pomocí funktoru dané arity a příslušným počtem termů, které jsou jeho argumenty - `okamzik(datum(1,1,1999),cas(10,10))`). Posledním typem proměnných jsou seznamy, které jsou probírány později.

Základní principy:

Programování v Prologu se výrazně liší od programování v běžných procedurálních jazycích jako např. C. Program v prologu je databáze faktů a pravidel (dohromady se faktům a pravidlům paradoxně říká procedury), nad kterými je možno klást dotazy formou tvrzení, u kterých Prolog zhodnocuje jejich pravdivost (dokazatelnost z údajů obsažených v databázi).

Například lze do databáze uložit fakt, že Monika je dívka:

    dívka(monika).

Poté lze dokazatelnost tohoto faktu prověřit otázkou, na kterou Prolog odpoví yes (ano):

    ?- dívka(monika).
    yes.

Také se lze zeptat na všechny objekty, o kterých je známo, že jsou dívky (středníkem požadujeme další výsledky):

    ?- dívka(X).
    X = monika;
    no.

Pravidla (závislosti) se zapisují pomocí implikací, např.

    syn(A,B) :- rodič(B,A), muž(A).

Tedy: pokud B je rodičem A a zároveň je A muž, pak A je synem B. První části pravidla (tj. důsledku) se říká hlava a všemu co následuje za symbolem `:-` (tedy podmínkám, nutným pro splnění hlavy) se říká tělo. Podmínky ke splnění mohou být odděleny buď čárkou (pak jde o konjunkci, musejí být splněny všechny), nebo středníkem (disjunkce), přičemž čárky mají větší prioritu.

Příklad:

Typickou ukázkou základů programování v Prologu jsou rodinné vztahy.

    sourozenec(X,Y) :- rodič(Z,X), rodič(Z,Y).
    rodič(X,Y) :- otec(X,Y).
    rodič(X,Y) :- matka(X,Y).
    muž(X) :- otec(X,_).
    žena(X) :- matka(X,_).
    matka(marie,monika).
    otec(jiří,monika).
    otec(jiří,marek).
    otec(michal,tomáš).

Prázdný seznam je označen atomem , neprázdný se tvoří pomocí funktoru `'.'` (tečka) - `.(Hlava,Tělo)`. V praxi se to (naštěstí ;-)) takhle složitě rekurzivně zapisovat nemusí, stačí napsat `[a,b,c...]`, resp `[Začátek | Tělo]`, kde začátek je výčet prvků (ne seznam) stojících na začátku definovaného seznamu, a tělo je (rekurzivně) seznam (např. `[a,b,c|[]]`).

Aritmetické výrazy se samy o sobě nevyhodnocují, dokud jim to někdo nepřikáže. Takže např. predikát `5*1 = 5` by selhal. Vyhodnocení se vynucuje pomocí operátoru is (pomocí = by došlo jen k unifikaci) - není to ale ekvivalent `=` z jiných jazyků. Tento operátor se musí použít na nějakou volnou proměnnou a aritmetický výraz, s jehož hodnotou bude tato proměnná dále svázaná (jako např. `X is 5*1,X=5` uspěje).

Důležitý je i operátor řezu (značíme vykřičníkem). Tento predikát okamžitě uspěje, ale při tom zakáže backtrackování přes sebe zpět. (`prvek1(X,[X|L]):-!. prvek1(X,[_|L]):-prvek1(X,L).` - je-li prvek nalezen, je zakázán návrat = najde jen první výskyt prvku). Dále je důležitá negace (`not(P):- P, !, fail. not(P).` - uspěje, pokud se nepodaří cíl P splnit). Řez tedy umožňuje ovlivňovat efektivitu prologovských programů, definovat vzájemně se vylučující použití jednotlivých klauzulí procedury, definovat negaci atd.