Neprocedurální programováníProlog 1.přednáška

Jan Hric KTI MFF UK

URL: http://ktiml.ms.mff.cuni.cz/~hric/vyuka.htm -> Neproceduralni programovani

Jan.Hric@mff.cuni.cz (hric@mbox.ms.mff.cuni.cz)

ver. 2010b

Druhy písma

- Times - vysvětlení, definice, (zdroj. kod) - Courier - zdrojaky, vystupy doplňky - Arial - rezervováno

Tento text je velky 32 Tento text je velky 28

Tento text je velky 24 Tento text je velky 20

Tento text je velky 18 Tento text je velky 16

Obsah, …

Logické programování - Prolog Funkcionální programování – (Scheme/Lisp), Haskell Vyuka: 2/2 Zk,Z

zápočtový program(+dok+test.data), zkouška

2010: test Prolog (50%) 8. týden, test Hs (50%) poslední týden

1-90%, 2-80%, 3-65% , další termíny: P+Hs

Implementace: SWI-Prolog, … a jiné http://www.swi-prolog.org Windows, Unix

Literatura - Prolog

Ivan Bratko: Prolog Programming for Artificial Intelligence, Addison Wesley 1986

L. Sterling, E. Shapiro: The Art of Prolog, 1986 W.F. Clocksin, C.S. Mellish: Programming in Prolog,

Springer-Verlag, Berlin, 1987 (3. vyd.) Petr Jirků a kol.: Programovaní v jazyku Prolog,

SNTL, Praha 1991 Jiří Polák: Prolog, Grada, Praha 1993 Učební texty, příklady: http://ksvi.ms.mff.cuni.cz/~kryl/ http://ktiml.ms.mff.cuni.cz/~bartak/

Prolog: Motivační příklad

% levá rotace bin. stromu levaRotace( % jméno procedury t( T1, X, t(T2,Y,T3)) , % vstup t( t(T1,X,T2), Y, T3) ). % vystup Idea: Strom odpovídajíci tvarem 1. argumentu se

transformuje na tvar podle 2. arg. Srovnání s proc. jazyky: cca. 4 přiřazení (+testy) při

implementaci jednosměrnými pointry Ošetřený je zde pouze případ, kdy prvky X a Y existují

Datové struktury: termy (obsahují interně: jednosměrné pointry)

Logické programování

Prolog je nejvýznamnějším nejrozšířenějším reprezentantem log. prog.

Je založený na matematických principechPredikátová logika 1. řádu (relace, termy)Rezoluční princip (hledání řešení)Unifikace (předávání par., dosazování do prom. – substituce)

Deklarativní programování – co se má spočítatvs. Procedurální prog. – jak se to má spočítat (oddělilo se: programování s omezujícími podmínkami –

constraint programming )Př.: soustava 2 rovnic o 2 neznámých, …

Převod do vyřešeného tvaru.V LP: implikace: pokud platí p(X), potom platí q(X,Y).

Filozofie práce

Spustí se prostředí, prompt ?-

Připravíte si zdrojové kódy pomocí lib. editoru v souboru a.pl , .pl je typická přípona

(Znovu)načtete soubor do databáze.

příkazem anebo přes menu

Zadáte dotaz, cíl (s konkrétními daty).

Systém vrací výsledky (vypočítané substituce), postupně na žádost (backtrackingem), na obrazovku.

Výsledků může být několik, žádný, (nekonečně)

(Najdete chybu a vývojový cyklus opakujete.)

Základní ovládání

% příkazy v interaktivním prostředí, na prompt ?- ?- halt. % ukončení práce ?- consult(soubor). %načtení souboru do databáze ?- [soubor]. % dtto; taktéž z menu;

Standardní přípona: .pl [’c:\adr\s.pl’]. % plné jméno nutně v apostrofech

?- listing. % výpis predikátů z databáze Př. ?- rodic(adam, X). % stejná syntax otázek ?- levaRotace(t(nil,1,t(t(nil,3,nil),5,nil)), X). X= t(t(nil,1,t(nil,3,nil)),5,nil)

ProgramProgram se skládá z procedur s určitým jménem a četností% predikát, resp. procedura rodic/2 rodic(anna,bohus). % jeden fakt procedury rodic/2 rodic(adam,bohus). % význam: Adam je rodicem

Bohuse rodic(anna,bara). rodic(adam,bara). rodic(bohus,cyril). rodic(bozena,cyril). prarodic(X,Y):- rodic(X,Z), rodic(Z,Y).

% pravidlo prarodic/2

Každý fakt i pravidlo je ukončeno tečkou (s nasledující mezerou).Konstanty začínají malými písmeny, proměnné velkými.Bez deklarací (procedur, konstant, promenných).

Dynamické typování (za běhu) /* víceřádkové komentáře */

Dotazy (cíle) a odpovědi 1

- konvence: pro odlišení cíle a programu: cíle mají prompt ?-

?- rodic(anna,bara). % dotaz bez proměnných yes ?- rodic(anna,zuzana). no - vyhodnocení probíhá prohledáním databáze - každý dotaz je vyhodnocován samostatně

Dotazy 2

?- rodic(anna,X). X=bohus ; % středník je žádost o další

řešení X=bara ; no - postupné vypsání všech (nalezených) řešení

Možnost zacyklení (při složitejších programech)

- při výpočtu se do proměnných substituují (dosazují) hodnoty (konstanty i složené hodnoty)

- po nalezení řešení se vypisují hodnoty (právě) všech proměnných z dotazu Při výpočtu vznikají i jiné proměnné

Dotaz 3

- složená otázka, čárka má význam and ?- rodic(anna,X),rodic(X,cyril). X=bohus %<CR>, pokud nechci další řešení

Proměnné můžou být v lib. argumentu

- víc proměnných: ?- rodic(anna,X),rodic(X,Y). X=bohus Y=cyril ; no

Pravidla - pravidlo pro proceduru prarodic/2 prarodic(P,X) :- % hlava pravidla rodic(P,R), % tělo pravidla, má dva cíle rodic(R,X).

- pro libovolnou (forall) substituci proměnných P a X: hlava platí, pokud existuje R tak, že platí všechny cíle v těle.

- všechny výskyty stejné proměnné nabývají stejnou hodnotu v rámci jednoho pravidla nebo faktu.

- fakt je pravidlo s prázdným tělem

- anonymní proměnná Na hodnotě nezáleží, různé výskytu mohou mít různou

hodnotu, v odpovedi na dotaz se nevypisuje

dite(X) :- rodic(_,X).

Další procedury

sourozenec(S,X):- %S je sourozenec X

rodic(R,S),rodic(R,X),S\=X. X\=Y - nerovnost hodnot

vlSourozenec(S,X):-

rodic(R1,S),rodic(R1,X),S\=X,

rodic(R2,S),rodic(R2,X),R1\=R2.

teta(T,X):- zena(T),sourozenec(T,R), rodic(R,X).

zena(anna). zena(bara). muz(adam). muz(bohus). - na pořadí definic predikátů nezáleží

Varianta definic:

pohlavi(zena,anna). pohlavi(muz,adam).

DC: upravte definici teta/2

- Procedura může mít několik pravidel

clovek(X):- zena(X).

clovek(X):- muz(X).

- Ekvivalentní zápis:

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

Středník má význam logické spojky or

neorientovanaHrana(Graf,X,Y):-

hrana(Graf, X,Y)

; hrana(Graf, Y,X).

Backtracking

Příklad … ?- prarodic(adam,X). Cíle se vyhodnocují zleva. Pravidla a fakty v databázi se prohledávají shora Strategie prohledávání je do hloubky

Neúplná, hrozí zacyklení

Paměťově efektivní

Při použití pravidla nebo faktu se proměnné přejmenují Tj. každé použití klauzule pracuje s vlastní sadou prom.

Rozsah platnosti proměnných je jedno pravidlo

Rekurze% P je vlastní předek Xpredek(P,X):- rodic(P,X).predek(P,X):- rodic(P,P1), predek(P1,X).- nejsou rozlišeny vstupní a výstupní argumenty- možné dotazy:?- predek(adam,X).?- predek(Y,cyril).?- predek(Predek,Potomek1),predek(Predek,Potomek2).Dobrý styl:

nerekurzivní klauzule nejdřív (tj. koncové podmínky)rekurzivní volání v klauzuli nakonec

- různá efektivita variant (a případně zacyklení)predek(P,X):- predek(P1,X), rodic(P,P1). % cyklípredek(P,X):- rodic(P,X).

Rekurze a rekurzivní datové struktury

% predek s dosvědčující cestou (včetně hraničních P a X)

predek2(P,X,[P,X]) :- rodic(P,X).

predek2(P,X,[P|Ps]):- rodic(P,P1), predek2(P1,X,Ps).

volání

?- predek2(adam,cyril,PP).

PP = [adam,bohus,cyril]

%PP = ’.’(adam,’.’(bohus,’.’(cyril,[])))

Prolog 2.přednáška

Jan Hric KTI MFF UK

URL: http://kti.ms.mff.cuni.cz/~hric/

Syntaktické části pgm

Program se skládá z procedur Procedury ... z faktů a pravidel (klauzulí) Pravidlo ... z hlavy a těla, odděleno :- Fakt má prázdne tělo Tělo ... z cílů (volání procedur) oddělených , - čárkou

ve významu and - a ; - středníkem ve významu or (...) a:- b,c;d,e. je a:-(b,c);(d,e).

Hlava a cíl ... ze jména procedury a argumentů - termů

Datové struktury - termy

termy - složené struktury (funkční symbol a args.) - seznamy a řetězce (spec. syntax)

- jednoduché - proměnné - konstanty - atomy - čísla

program a d.s. se neliší syntaxí-strukturou, ale “polohou” a významem

Lexikální elementy

atomy : 1. alfanum. posl. s _ uvedeny malým písm.

2. posl. (někt.) spec. znaků (kromě ()!,;[ ] | )

3. posl. znaků v apostrofech

proměnné - alfanum. s _ uvedeny Velkým p. nebo _ speciálně : anonymní proměnná _ (podtržítko)

struktury: datum(1999, ‘září’, 09) funktor je (syntakticky) atom, argumenty jsou termy

Speciálně: funktor (tj. funkční symbol) není proměnná: X(A,b) špatně

př: funktor datum, 3 argumenty vynecháno : seznamy, operátory, operátorová vs termová , a (

v Prologu nejsou (explicitní uživatelské) typy a deklarace

Proměnné

logické proměnné nabývají hodnotu substitucí - jednorázově

proměnná se naváže na term

při návratu (backtrackingu) se uvolňují a můžou nabýt opět další hodnotu

p. v klauzuli se při každém jejím použití přejmenovávají

rozsah je lokální v klauzuli nebo v počátečním cíli

proměnné obsažené v počátečním cíli se vypisují jako řešení

(alokují se automaticky díky přejmenování)

Složené d.s. 1.

analogie k záznamu (se schovanými pointry na arg.) výběr složek (argumentů) je polohou, ne jménem

není pole (většinou nevadí) Procházení celé struktury (seznamu) rekurzivně

Stromové vyhled. strukt. – penalizace O(log n) pro přímý přístup

syntax vs. semantika d.s. datum(1999,9,9) vs. d(9,9,1999) (vs. [9,9,1999]) d(rok(2010),mes(9),den(8)), [d(9),m(9),r(1999)], [d-9,m-9,r-1999]

předběžně: operátory - interní struktura: nic nového ?- display(3*x+4*y). +(*(3,x),*(4,y))yes

Práce s d.s.

struktura datum(Rok,Měsíc,Den)

get_rok(datum(R,_,_),R). % analogicky pro měsíc a den

set_rok(R,datum(_R,M,D),datum(R,M,D)). ?- ..., /*Dat1*/ set_rok(1999,Dat1,Dat2), /*Dat2*/ ...

mk_datum(R,M,D,datum(R,M,D)). %konstruktor destruktor není potřeba: 1) automatická správa paměti, 2) ^get…

nebo: get_datum(rok,datum(R,_,_),R).

get_datum(mesic,datum(_,M,_),M). % ... převedení na přístup pomocí jména složky (analogicky k záznamům)

ADT – Abstraktní Datový Typ: selektory – get_, konstruktory – mk_

set_rok/3, … jsou odvozené

Př: Faktoriál, Eukleidův alg. fakt(0,1). % ?- fakt(5,FF). fakt(N,F):- N>0, N1 is N-1, fakt(N1,F1), % špatně: fakt(N-1,F1) F is N*F1. gcd(X,X,X). % ?- gcd(13,8,NSD). gcd(X,Y,V):- X>Y, X1 is X-Y, gcd(X1,Y,V). gcd(X,Y,V):- X<Y, Y1 is Y-X, gcd(Y1,X,V).

typická struktura rekurze: stráž, předvýpočet, rekurze, postvýpočet

Správnost programu taky vzhledem k backtrackingu Program vydá pouze správné řešení (a skončí)

is je aritmetické vyhodnocení

Celkový pohled

prohledávání stromu výpočtu backtrackingem prohledávání = dynamická konstrukce

strom: vrcholy jsou ohodnocené cíly, s vybraným cílem k řešení (nejlevějším); hrany klauzulemi

syn je rezolventa otce a hrany (pokud se podařila), substituce se zapamatuje

hledá se: vrchol(-y) s prázdným cílem, nalezená substituce se vypíše pouze proměnné z dotazu, tj. relevantní pro uživatele

Unifikace

jediný způsob předávání parametrů a přístupu na složky struktur (v čistém Prologu) unifikujeme argumenty v cíli s (přejm.) argumenty v hlavě

je “nesměrová” výsledek je neúspěch nebo (úspěch a) substituce

Věta: Pokud ex. subs., pak ex. jedna nejobecnější (mgu - most general unifier)

termy jsou unifikovatelné, pokud existuje substituce za proměnné taková, že po substituci jsou termy stejné unifikovatelné termy bez proměnných musí být stejné

Unifikace - algoritmus Unifikujeme termy S a T: 1. S a T jsou konstanty: Jsou unifikovatelné, pokud jsou stejné 2.1 S je prom., T je lib. term: Jsou unifikovatelné. Substituce se

rozšíří, prom. S nabyde hodnotu T (i pro zbytek algoritmu/d.s.). (v teorii: T neobsahuje prom. S - vznik cyklických struktur)

2.2 symetricky pro Ta S. 3. S a T jsou struktury: Jsou unifikovatelné, pokud 3.a mají stejný funktor a počet argumentů, a současně 3.b odpovídající si dvojice argumentů jsou unifikovatelné 4. Jinak nejsou unifikovatelné (konstanta a struktura)

př: f(a,X,g(X,Y)) a f(Z,h(Z,U),g(V,V) Z/a,X/h({Z=}a,U),V/{X=}h(a,U),Y/{V=X=}...

Deklarativní vs. procedurální význam

Deklarativní význam klauzule: p:- q,r. “p” je pravdivé, pokud “q” a “r” je pravdivé. Z platnosti “q” a “r” vyplývá “p”.

(klauzule jako logické implikace, chceme odvodit cíl z prázdných předpokladů)

(rezoluce: z p <- q&r a q <- s&t odvoď p <- s&t&r) (zpětné řetězení: co ješte zbývá dokázat, aby platilo p ?)

Deklarativní význam popisuje vztahy mezi vstupy a výstupy, zajímá nás dokazatelnost cíle (a substituce). V teorii: k programu se přidá negace cíle a hledá se spor.

Deklarativně správný program (vzhledem k zamýšlenému významu) nevydá nesprávné řešení. (Je parciálně správný, t.j. může se zacyklit ...)

Deklarativní vs. procedurální význam

Procedurálně: Pro vyřešení “p” vyřeš nejprve “q” a pak “r”.

Určuje, jak se výsledek počítá, zahrnuje v sobě strategii prohledávání.

Některé vestavěné predikáty mají pouze procedurální význam. Bez nich: čistý Prolog

Bere do úvahy konečnost (zda se řešení najdou dřív, než se zacyklí), pořadí a násobnost řešení, ...

Používá se při optimalizaci, deklarativně správný program nemusí být rychlý. Paretovo pravidlo 80-20: 80% důsledků je z 20% příčin (v software

často i 90-10): 80% času se stráví v 20% kódu, 80% funkcionality je v 20% specifikací, (různých) 20% zákazníků má 80% požadavků a dává 80% příjmů, 20% programátorů vyrobí 80% kódu (a 80% chyb) … (Původně: rozložení bohatství v ekonomice)

Murphyho rada: Program se optimalizuje, až když selžou všechny pokusy učinit ho správným. (Máloco stojí za optimalizaci)

Rekurzivní d.s.

nemáme pole unární repr. čísel: s(s(s(0))), ale používáme hw. impl

seznamy: d(1,d(3,d(5,nic))) idea speciální syntax: [1,3,5]=[Hlava|Telo]

substituce: Hlava/1, Telo/[3,5]

speciální syntax (‘.’/2) místo d/2 .,(1,.(3,.(5,[])))

[] místo nic (vyslov ‘nil’)

zápisy stejného seznamu: [1,3,5] [1,3,5|[]] [1|[3|[5|[]]]] [1|[3,5]] obvykle v rekurzi

Jiné struktury

binární stromy prázdný ... v (jako void)

neprázdný ...L,hodn,R: t/3 t(t(v,1,v),2,t(v,3,v))

Logické formule Spojky and/2, or/2, non/1, imp/2, ekv/2 Konstanty true/0, false/0 Proměnné var/1, argument je jméno proměnné

Rozlišujte: proměnné prologovské a doménové

ekv(imp(var(x),var(y)), or(non(var(x)),var(y)) )

Při vhodné definici binárních operátorů: (var(x) imp var(y)) ekv (non var(x) or var(y)) X1 ekv X2

Autotest

lze použít strukturu pro binární stromy i pro binární vyhledávací stromy ?

navrhněte d.s. pro (vyhledávací) 2-3 stromy (právě 2;3 syny (a klíče) nebo list s 1 hodnotou)

navrhněte d.s. pro n-arní stromy (1 hodnota a 0-n následníků)

navrhněte (jednu!) strukturu pro stroj Aho-Corasicková

Unární aritmetika

lt(0,s(Y)). % strukturální rekurze podle 1.arg lt(s(X),s(Y)) :- lt(X,Y). % lt/2 je pouze test, bez výst. arg. plus(0,Y,Y). % plus(+,+,?) plus(s(X),Y,s(Z)) :- plus(X,Y,Z). % s(X)+Y=s(X+Y) =s(Z) krat(0,Y,0). krat(s(X),Y,Z) :- krat(X,Y,Z1), plus(Y,Z1,Z). % … a vyhodnocení (eval) – schované v knihovně eval(X+Y,V) :- eval(X,VX), eval(Y,VY), plus(VX,VY,V). eval(X*Y,V) :- eval(X,VX), eval(Y,VY), krat(VX,VY,V). eval(X,X) :- X=0 ; X=s(_). % nedokonale ?- eval(s(s(0))*s(0)+s(0),V).

Příklad: rodic/2

r(anna, bohus). %fakt, prázdne tělo r(adam, bohus). r(bohus,cecilie). %procedura r/2, predikat prarodic(X,Y):-r(X,Z), r(Z,Y). %pravidlo /* hlava tělo */ je_rodic(X):- r(X,_). %anon. prom. rodice(D,R1,R2):-r(R1,D),r(R2,D),R1\=R2. % =/2 rovnost, vyvolání unifikace % \=/2 nerovnost

Tok dat - příklad definice rodic/2 predek(X,X). % 1. varianta predek(X,Y):- rodic(X,Z), predek(Z,Y).

predek(X,X). % 2. varianta predek(X,Y):- rodic(Z,Y), predek(X,Z).

volání p(+,+), p(+,-), p(-,+), p(-,-) stejné 1.lepší 2.lepší ?- p(adam,X) vs. ?- p(X,cyril) vhodnost závisí na zamýšleném (příp. obvyklém) použití

jiné varianty (přehození cílů, klauzulí) jsou horší

Složené d.s. 2.

par(odpor(r1,1200), sekv(par(odpor(r2,1000), kond(c1,0.001) ), odpor(r3,1500) )) odpor(odpor(_,V),V). odpor(sekv(O1,O2),V):- odpor(O1,V1), odpor(O2,V2), odporsekv(V1,V2,V). %...ostatní případy nestandardní pohled: program, který prochází

strukturou, definuje její význam (jeden z významů) strukturální rekurze

r1

r2 r3

c1

Zobecnění faktoriálu

...