% UItwerking Tentamen Programmeren in Prolog % 7 juni 2002 % Joris Hulstijn % SCORE: I: 10 + 15, II:15+5, III:10+5+5, IV:15+5, +10 EXTRA % CIJFER = SCORE * 1.1 (CORRECTIEFACTOR) % Opgave I: Kennisrepresentatie % A. /* Optreden ::= optreden( Artiest of Groep:: String, * sleutel, Podium in [helium, neon, krypton, xenon], Datum :: DatumType BeginTijd :: UU:MM, EindTijd :: UU:MM, met UU in [0 .. 23], MM in [0 .. 59] ) NB Een alternatieve sleutel is de combinatie van datum, podium en begintijd. DatumType ::= date( Weekdag in [maandag .. zondag], DD in [1 .. 31], MM in [1 .. 12], YYYY in [1800 .. 2200] ) */ optreden( 'Macy Gray', helium, date(vrijdag, 25,5,2002), 22:15, 23:30 ). optreden( 'Recloose', xenon, date(vrijdag, 25,5,2002), 22:30, 0:00 ). optreden( 'De la Soul', helium, date(zaterdag,26,5,2002), 22:15, 23:15 ). % B. % 1. Hoe laat begint het optreden van Macy Gray? % ?- optreden( 'Macy Gray', _Podium, _Date, HoeLaat, _Eind ). % of beter nog met selector functie! % ?- begintijd('Macy Gray', HoeLaat). begintijd(Groep, Begin) :- optreden(Groep, _Podium, _Date, Begin, _Eind ). % 2. Geef een lijst van alle optredens op het Xenon podium. podium(Groep, Podium) :- optreden(Groep, Podium, _Date, _Begin, _Eind ). % ?- findall( Optreden, podium(Optreden, xenon), Lijst). % 3. Hoe lang duurt het optreden van Wyclef Jean? % ?- duur('Wyclef jean', Duur). % duur(+Groep, -Duur) % geeft duur in uren en minuten (alleen in minuten is ook goed) % NB. een optreden kan tot de volgende dag duren (voor bonuspunten :) duur(Groep, DuurUU1:DuurMM) :- begintijd(Groep, Begin), eindtijd(Groep, Eind), inminuten(Begin, BeginMin), inminuten(Eind, EindMin), DuurMin is EindMin - BeginMin, DuurUU is (DuurMin // 60), DuurMM is (DuurMin mod 60), (DuurUU < 0,!,DuurUU1 is DuurUU + 24 % if-then-else ; DuurUU1 is DuurUU). % inminuten(+Tijd, -InMinuten) % geeft tijdstip als het aantal minuten sinds middernacht. inminuten(UU:MM, InMinuten) :- InMinuten is 60*UU + MM. eindtijd(Groep, Eind) :- optreden(Groep, _Podium, _Date, _Begin, Eind ). datum(Groep, Date) :- optreden(Groep, _Podium, Date, _Begin, _Eind ). % 4. Wie speelt er vrijdag om 11 uur op het Helium podium? % ?- optreden(Groep, helium, date(vrijdag, _, _,_), Begin, Eind ). % tussen(21:00, Begin, Eind). % % of beter nog % % ?- podium(Groep, helium), % datum(Groep, date(vrijdag, _, _,_)), % begintijd(Groep,Begin), % eindtijd(Groep, Eind), % tussen(21:00, Begin, Eind). % tussen(+Moment, +Begin, +Eind) % slaagt indien Moment tussen de tijdstippen Begin en Eind inligt. tussen(Moment, Begin, Eind):- inminuten(Moment, MomentMin), inminuten(Begin, BeginMin), inminuten(Eind, EindMin), BeginMin < MomentMin, EindMin > MomentMin. % 5. Hoeveel optredens zijn er op vrijdag? % ?- findall( Groep, datum(Groep, date(vrijdag,_,_,_)), Lijst), % length(Lijst, Hoeveel). %--------------------------------------------------------------------- % Opgave 2: Cut % A remove(X, [X|Rest], Rest). remove(X, [_Y|Rest], Rest1) :- remove(X,Rest,Rest1). % 1. resultaat queries % ?- remove(X, [1,2,3], L). % X = 1 % L = [2, 3] ; % No % ?- remove(2, L, [1,3]). % L = [2, 1, 3] ; % No % 2. Het is een rode cut, want (1) als je 'm weghaalt, % verandert de betekenis. (remove1 is remove zonder cut) % % ?- remove1(X, [1,2,3], L). % X = 1 % L = [2, 3] ; % X = 2 % L = [3] ; <- na doorvragen, niet [1,3] zoals verwacht % X = 3 % L = [] % ?- remove(2, L, [1,3]). % L = [2, 1, 3] ; % L = [_G286, 2, 1, 3] ; ... <- na doorvragen, niet [1,2,3] etc als verw % NB. Dit is dus geen echte remove, omdat ie de kop Y niet 'doorgeeft' % Een 'echte' remove, ziet er zo uit: remove_echt(X, [X|Rest], Rest). remove_echt(X, [Y|Rest], [Y|Rest1]) :- % <- let op Y|Rest1 remove_echt(X,Rest,Rest1). % 3. % Ja en nee. Ja dat kan, met behulp van een expliciete X \= Y, % maar eigenlijk is negatie (dus ook \=) intern gedefinierd met een % cut-fail combinatie. Dus dan heb je toch een cut nodig. remove2(X, [X|Rest], Rest). remove2(X, [Y|Rest], Rest1) :- X \= Y, del1(X,Rest,Rest1). % ?- remove2(X,[1,2,3],L). % X = 1 % L = [2, 3] ; % No % B. Definitie Matching match(S,T) :- % geval 1: S en T zijn beide constant (atomic) constant(S), % dwz getal of atom constant(T), % dan moet S == T (identiek) S == T. match(S,T) :- % geval 2: S of T is een variabele var(S), % dan wordt substitutie S/T of T/S toegevoegd S = T. match(S,T) :- var(T), T = S. match(S,T) :- % geval 3: S en T zijn samengesteld S =.. [FunctorS| ArgsS], T =.. [FunctorT| ArgsT], FunctorS == FunctorT, match(ArgsS,ArgsT). % dan moet de functor identiek zijn % en moeten de argumenten ook matchen (recursie) % -------------------------------------------------------------------- % Opgave III: Lijsten % A % ?- turnover( [ [11,12,13], [21,22,23], [31,32,33]], L). % L = [[33, 32, 31], [23, 22, 21], [13, 12, 11]] % turnover( +Matrix, -TurnedMatrix ) % 2pt algemene opzet (stopcond); % 4pt structuur turn (buitenste loop) % 4pt reverse (binnenste loop) Je MOET een definitie van reverse geven % eenvoudigste: mbv standaard predicaat reverse\2 turnover([],[]). turnover([L|Ls], Rs_R) :- turnover(Ls,Rs), reverse(L,R), append(Rs,[R],Rs_R). % let op: achteraan!, let op [ ] % basis idee: reverse1([],[]). reverse1([H|T],Rev) :- reverse1(T,T1), append(T1,[H],Rev). % let op: achteraan, let op [ ] % mooier: allebei met staart recursie turnover1( Matrix, Diagonal) :- turn(Matrix, [], Diagonal). turn([], Temp,Temp). turn([L|Ls], Temp, Rev):- % Temp: extra argument voor tussenresultaat reverselist(L,R), turn(Ls, [R|Temp], Rev). % reverselist(+List, -ReversedList) reverselist(L,R) :- rev(L,[],R). rev([], Temp,Temp). rev([H|T], Temp, Rev):- rev(T, [H|Temp], Rev). % B.1 convert(?Number, ?PlusMinL) % 5 pt: 1 stopcie, daarna 1 pt voor + ->, - ->, <- + <- - ieder % Het MOET zo vanwege de rekenkundige functies convert(0, []):-!. % Num -> List convert(Num, ['+'|Rest]) :- number(Num), % geen variabele (Num > 0), Num1 is Num - 1, convert(Num1, Rest). convert(Num, ['-'|Rest]) :- number(Num), (Num < 0), Num1 is Num + 1, convert(Num1, Rest). % List -> Num convert(Num, ['-'|Rest]) :- convert(Num1, Rest), Num is Num1 - 1. convert(Num, ['+'|Rest]) :- convert(Num1, Rest), Num is Num1 + 1. % C.2 add(+PlusMinL1, +PlusMinL2, -PlusMinSum) % De eenvoudige (flauwe) oplossing (wel goed voor 5 pt): add(L1, L2, L) :- convert(N1, L1), convert(N2, L2), plus(N1, N2, N), % of N is N1 + N2 (werkt niet 2 kanten op) convert(N,L). % MOET % mooier is: add([],L,L). add([+|T1],[-|T2],S) :- % streep tegen elkaar weg add(T1,T2,S). add([-|T1],[+|T2],S) :- add(T1,T2,S). add([Sign|T],L,[Sign|S]) :- % anders geef door add(T,L,S). % -------------------------------------------------------------------- % opgave IV % Grammatica session --> login, actions, logout. actions --> action, actions. actions --> []. action --> [ edit ], filename. action --> [ copy ], filename, filename. filename --> [FileName], {atom(FileName)}. login --> [ login ], account. logout --> [ logout ]. account --> [joris];[frank];[bas]. /* 1. session([login, frank, logout, logout], [logout]). Yes session _______|___________ | | | login actions logout / \ | | | account [] | | | | [login] [frank] [logout] die dubbele ..logout], [logout] is geen prbleem vanwege difference lists. 2. session([login, frank, edit, 'word.doc', copy, 'word.doc', 'Tmp', edit, 'Temp', logout], []). Yes session________________________________________ / \_________ \__________>> / \ actions / / \______________ / | actions / | / \_________________ login action __ action ____ / \ / \ / | \ | account | filename | filename filename | | | | | | | [login] [frank] [edit]['word.doc'] [copy] ['word.doc'] ['Tmp'] >>______________________________ \ ____________ logout actions | / \ | __ action \ | / | [ ] | | filename | | | | [edit] ['Temp'] [logout] 3. phrase(session, [login, joris, copy, xyz, edit, 'Tmp', edit,'Tmp2', logout], []). % no, 2E argument copy ontbreekt % NB. Phrase\3 is een standaard Prolog predicaat voor het aanroepen % van een grammatica. DAar ligt het niet aan (-1 verkeerde motivatie). 4. phrase(actions, [], []). Yes actions NB. zonder session, en zonder phrase | [] 5. session([login, frank, copy, xyz, abc, edit, login, copy, login, abc, logout],[logout]). No, de 'logouts' aan het eind heffen elkaar op; daardoor ontbreekt er een logout expressie. (def difference list) */ % B. % Grammatica session1 --> login1, actions, logout. login1 --> [ login ], [Account], [password], [PassWord], { password(Account, PassWord) }. % deze hoeft niet perse, maar is wel leuk natuurlijk login1 --> [ login ], [Account], [password], [PassWord2], [try, again], login1, { password(Account, PassWord), PassWord \= PassWord2 }. password(joris, xyz). password(frank, abc). password(bas, klm). /* Bijv. ?- session1([login,frank,password, zxc, try, again, login,joris,password, xyz, edit, 'word.doc', copy, 'word.doc', 'Tmp', edit, 'Temp', logout], []). Yes */ % Of met unificatie (vgl persoon - getal) login2 --> [ login ], [Account], password(Account). password(joris) --> [xyz]. password(frank) --> [abc]. password(bas) --> [klm].