Otázka PROG č.1 - Logický program - struktura, základní pojmy, datová struktura seznam, práce s databází Prologu. Hlavní odlišnosti oproti procedurálnímu programování, možnosti použití neprocedurálního programovacího jazyka.

Prolog je jazyk pro programování symbolických výpočtů. Jeho název, odvozený ze slov PROgramování v LOGice, naznačuje, že jazyk vychází z principů matematické logiky. Jeho úspěch byl podnětem pro vznik nové disciplíny matematické informatiky – logického programování, což je perspektivní styl programování na vyšší abstraktní úrovni.

Prolog je také strojovým jazykem nejmodernějších počítačů. Má doposud specifické oblasti použití - umělou inteligenci, znalostní inženýrství, atp.

Historie

Jazyk Prolog vznikl v r. 1972 ve Francii na univerzitě v Luminy (Marseille). První verzi jazyka vytvořili A. Colmerauer a P. Roussel jako prostředek pro efektivní odvozování logických důsledků z určité třídy formulí predikátové logiky. K významnému obratu došlo v r. 1981. Způsobil ho japonský projekt počítačů 5.generace, kde byl Prolog zvolen jako základní jazyk logického procesoru centrální jednotky počítače. Vyvolalo to vlnu zájmu o Prolog a metody logického programování. Prolog se začal rychle prosazovat vedle jiných jazyků pro symbolické výpočty (např. Lisp).

K čemu se používá Prolog

Od počátku byl Prolog využíván při zpracování přirozeného jazyka (francouštiny) a pro symbolické výpočty v různých oblastech umělé inteligence. Používá se v databázových a expertních systémech, při počítačové podpoře specializovaných činností, např. při projektování (CAD – Computer Aided Design) nebo výuce (CAI – Computer Aided Instruction), i v klasických úlohách symbolických výpočtů, jako je návrh a konstrukce překladačů, a to nejen jako prostředek vhodný pro reprezentaci a zpracování znalostí, ale i jako nástroj pro řešení úloh.

Porovnání s jinými jazyky

Prolog je konverzační jazyk nové generace programovacích jazyků, která by měla usnadnit tvorbu programů co nejširšímu okruhu uživatelů. Snaží se odstranit část rutiny při programování a tím si zajistit místo vedle osvědčených jazyků jako Fortran, Cobol a Pascal.

Uživatel Prologu se může více soustředit na popis vlastností relací, tedy na otázku co se má vypočítat, aniž by byl na každém kroku nucen řešit detaily spojené s otázkou jak to udělat a kam uložit získané výsledky.

V Prologu nejsou příkazy pro řízení běhu výpočtu ani příkazy pro řízení toku dat. Chybějí prostředky pro programování cyklů, větvení apod. a nepoužívá se přiřazovací příkaz. S tím souvisí i rozdílná úloha proměnných. Proměnná v Prologu označuje po dobu výpočtu objekt, který vyhovuje určitým podmínkám. Jeho vymezení se při výpočtu upřesňuje.

Průběh výpočtu je v Prologu řízen jeho interpretem na základě znění programu. Programátor může chod výpočtu ovlivnit řídícími příkazy v mnohem menší míře než u jiných jazyků.

I když byl původně Prolog navržen jako jazyk specializovaný na symbolické výpočty, moderní implementace směřují k obecnějšímu použití.

Logickým programem budeme rozumět posloupnost faktů (nepodmíněných příkazů) (H.) a pravidel (podmíněných příkazů) (H:-A1,A2, ..., An.)

Datové typy

Konstanty, proměnné a struktury souhrnně označujeme jako termy. Každá implementace jazyka Prolog obsahuje řadu tzv. vestavěných predikátů (procedury nabízené tou kterou implementací jazyka Prolog), které jsou ze syntaktického hlediska také považovány za termy. Konstanta nebo proměnná se nazývá atomický term. Atomickými termy jsou tedy jak jednoduchá jména objektů, tak i čísla a proměnné. Z atomických termů můžeme vytvářet i složitější výrazy, které se nazývají struktury.

Proměnné

Začínají velkým písmenem nebo speciálním symbolem “_” (podtržítko) a jsou tvořeny libovolnou posloupností písmen, číslic a znaku “_”. Proměnnou je také samotný znak “_”. Takovou proměnnou nazýváme anonymní proměnná, která je obdobou zájmen cokoli nebo kdokoli. Její zvláštností je to, že každý její výskyt představuje jinou proměnnou, tedy výraz p(_,_) je totéž co p(X,Y), nikoli p(X,X). Hodnoty anonymních proměnných se v dialogu uživateli nevypisují.

Klauzule

Programování v Prologu spočívá v deklarování faktů o objektech a relacích mezi objekty, v definování pravidel o objektech a relacích platících mezi nimi a v zodpovídání dotazů. Klauzule jsou výrazy jazyka, pomocí nichž se zapisují nepodmíněné příkazy – fakta, podmíněné příkazy, které vyjadřují pravidla a výrazy, které mají tvar dotazu – cílové klauzule. Fakta – nepodmíněné příkazy Nepodmíněné příkazy vyjadřují fakt o relaci. Fakta jsou vztahy, které mají jméno, za nímž následuje výčet objektů, kterých se vztah týká. Objekty jsou odděleny čárkami a jejich výčet je uzavřen do kulatých závorek. Každý fakt je ukončen tečkou. Pokud fakt neobsahuje proměnné, hovoříme o tzv. základním faktu. Př.: /* fakta uložena v databázi, která vyjadřují, že osoba M je matkou X a Y */ matka(M, X). matka(M, Y). Podmíněný příkaz je oddělen znaménkem implikace ”:-” na dvě části, ukončený tečkou. Část vlevo od dvojznaku se nazývá hlava pravidla, napravo od něho je tělo pravidla. Př.: sourozenci(X,Y) :- matka(M,X), matka(M,Y). Program může obsahovat dotazy, kterým říkáme cílové klauzule. Cílové klauzule v textu programu nesmějí obvykle obsahovat proměnné, na něž není vázaná hodnota.

Otázka (cílová klauzule) začíná dvojicí znaků ”?-” a končí tečkou. Na cílovou klauzuli položenou v průběhu dialogu uživatele se systémem nejsou kladena žádná omezení týkající se proměnných v ní obsažených. Dotaz, který neobsahuje proměnné se nazývá základní otázka. Odpověď (řešení), kterou systém vrací, je buď „yes“, „no“, nebo výpis hodnot proměnných obsažených v otázce (kromě hodnot anonymních proměnných -> ty se v dialogu uživateli nevypisují). Jelikož databáze v Prologu nemůže obsahovat negativní data, chápeme odpověď „no“ dvěma způsoby, a to: záporná odpověď nebo neexistující odpověď. př.: /* dotaz na hledání společné matky */ ?- matka(M,X), matka(M,Y).

Predikáty

To co jsme dříve nazývali procedurou můžeme přesněji popsat jako všechny klauzule začínající stejným funktorem a mající shodný počet argumentů. Mohou mít stejné jméno struktury a různý počet argumentů. Proto se často uvádí jméno procedury spolu s počtem jejích argumentů (tj. aritou). Procedury (jinými slovy predikáty) existují standardní (označované jako vestavěné predikáty). To jsou procedury, které jsou implementovány přímo v systému. Dále jsou procedury, které si uživatel definuje sám. Program je pak tvořen z jednotlivých procedur, které se skládají z příkazů. Příkazy jsou nepodmíněné (tj. fakta) a podmíněné (tj. pravidla). Jedná se jen o jiné chápání – výklad – posloupností klauzulí.

Seznamové struktury

Velice častou datovou strukturou používanou v symbolických výpočtech jsou seznamy. Prolog chápe seznamy jako běžné prologovské struktury, tj. termy s funktorem a argumenty, a také tak s nimi zachází. Seznam je tvořen posloupností prvků (tj. libovolných termů) oddělených čárkami a uzavřených do hranatých závorek []. Prvkem seznamu tedy může být konstanta, proměnná či struktura. Seznam je určitou strukturou, která se však vyjadřuje jiným způsobem. Př.: [tohle, je, prvni, seznam, jen_z_konstant, 1] [druhy, seznam, [je, [slozitejsi], obsahuje(strukturu)]] Pro vytváření seznamů v Prologu existuje předdefinovaný funktor ”.” (tečka), který je definován jako dvouargumentový funktor (”.” je jménem struktury, označením vestavěného predikátu). Seznam se skládá z hlavy a těla (zbytku seznamu). Hlavou seznamu může být cokoli – atom, seznam, libovolný term, ale tělem seznamu je vždy seznam. Př.: . (Hlava, Tělo) Jedinou výjimkou je prázdný seznam, který neobsahuje žádné prvky: je reprezentován degenerovaným stromem [], který se nedá rozložit na dvě části. Proto prázdný seznam nemá hlavu ani tělo. Ve skutečnosti se jedná o vyčleněný atom. Př.: /* prázdný seznam */ []

Zápis seznamů

Seznamy lze zapisovat různými způsoby, Prolog však každý seznam interpretuje interně jako strukturu. V Prologu se k zápisu seznamu používá binární funktor ”.”. Jako syntaktická pomůcka se zavádí “|” svislá (někdy přerušovaná) čára, která odděluje hlavu seznamu od těla seznamu. Mezi zvláštnosti seznamů patří to, že programátor má k dispozici speciální seznamovou notaci, která je přehlednější a uživatelsky pohodlnější. Všechny tyto zápisy jsou ekvivalentní. Př.: /* zápis čtyřprvkového seznamu pomocí funktoru ”.” / . (a, . (b, . (c, . (d, [] ))) / zápis čtyřprvkového seznamu pomocí funktoru ”.”, jestliže chápeme ”.” jako infixový operátor / (a . (b . (c . (d . [] ))) / zápis čtyřprvkového seznamu pomocí “|” / [a | [b, c, d]] / zápis čtyřprvkového seznamu pomocí seznamové notace / [a,b,c] Z praktických důvodů se dovoluje používat svislou čáru k oddělení prvé části seznamu (tj. za druhou, třetí a další položkou) od zbytku seznamu, který musí být vždy seznam. Hlavou seznamu je i v tomto případě pouze první položka seznamu. Př.: / následující zápisy označují tentýž seznam, hlavou seznamu je i v těchto příkladech „a“ / [a, b, c, d] [a | [b, c, d]] [a , b | [c, d]] [a , b, c | [d]] [a , b, c, d | [] ] Př.: / naopak tento příklad není seznamem, protože za symbolem “|” musí následovat opět seznam */ [a | b]

Operace se seznamy

Seznamy jsou nejdůležitější struktury používané v Prologu. Mezi základní procedury pro práci s nimi patří append, member, length, delete, aj.

append /* používá se pro spojování seznamů / member / používá se pro určování příslušnosti prvku k seznamu / length / určuje délku seznamu, tj. počet prvků seznamu / delete; / odstraňuje prvek ze seznamu */

Seznam je rekurzivně definovaná datová struktura, také procedury s ním pracující jsou rekurzivní.

Řízení databáze

Nejdůležitějšími predikáty pro řízení databáze jsou predikáty assert a retract. Umožňují ukládat klauzule do databáze nebo je z ní odstraňovat. Užitečným predikátem pro práci s databázi je i predikát listing a clause. assert /* ukládá klauzule do databáze / asserta / ukládá klauzule do databáze na začátek / assertz / ukládá klauzule do databáze na konec / retract / odstraní z databáze klauzuli / retractall / odstraní z databáze všechny klauzule / listing / způsobuje výpis klauzulí v databázi / clause / hledá klauzule podle kterých může unifikovat klauzule */

Řízení průchodu programem

! (řez) představuje klíčové rozhodnutí překročí-li jej zpracovávání, už se nejde vrátit lze jej využít k zefektivnění výpočtu - nenutíme Prolog, aby se navracel o mnoho podcílů zpět, pokud víme, že tak nenajde nová řešení. dva typy řezů červený - pokud jej z programu smažu, bude program pracovat chybně zelený - pokud jej smažu, může dojít ke snížení efektivity, ale funkce programu se nezmění fail nikdy nesplněný predikát nelze se přes něj dostat repeat při průchodu programem blokuje návrat nekonečný cyklus:

repeat
  write('Pracuji'), nl,

fail. Příklady řezů

pocitej:-
  repeat,
  write('Zadej cislo mensi nez 100'),
  read(S),
  S<100,!,
  faktorial(S).

Zde je řez použit k oddělení načítání čísla, které má být menší než 100,od výpočtu faktoriálu. (Samotný predikát faktoriál v ukázce neuvádíme). Pokud se z nějakého důvodu nepodaří faktoriál vypočítat, Prolog se nebude vracet k novému načítání čísla a rovnou skončí. Jak vidíte, řezem je možné ovlivnit průběh výpočtu tak, že zamezíme zbytečným návratům. Kromě toho lze ale řezem zabránit i nežádoucímu pohybu dopředu, přesněji řečeno zbytečnému vykonávání alternativních větví pravidla.

zjisti1(A):-0 is A mod 2, write(‘cislo je sude’),nl,!. zjisti1(A):-1 is A mod 2, write(‘cislo je liche’),nl.

Pravidlo má zjistit, zda argument A je sudé, nebo liché číslo. Pokud se vykoná první větev pravidla - tedy číslo bude sudé - Prolog už nebude zkoumat, jestli je číslo liché. Předchozí variantu je možné zkrátit takto:

zjisti2(A):-0 is A mod 2, write(‘cislo je sude’),nl,!. zjisti2(A):-write(‘cislo je liche’)

Všimněte si, že kdybychom z pravidla zjisti1 odstranili řez, na jeho fungování by se nic nezměnilo (tzv. zelený řez). Avšak kdybychom řez vynechali v pravidle zjisti2, program by nefungoval (tzv. červený řez). Jak by se projevila chyba, kdybychom odstranili řez z predikátu zjisti2 ? Pro sudá čísla by pravidlo vracelo dvě řešení - hlášení, že číslo je sudé i že je liché. Pro lichá čísla by predikát fungoval dobře, neboť jeho první část by se nespustila. Odlišujeme tedy dva druhy řezů: zelený řez, který je možné odstranit, aniž by se tím změnilo fungování programu červený řez, který nelze odstranit bez poškození programu