Deklaratív programozás

3. Prolog kis házi feladat

2005. december 13.

A kis házi feladat beadása nem kötelező.

A feladat

Adatfának nevezünk egy olyan Prolog struktúrát, amely vagy adatlevél vagy adatág. Az adatlevél egy l/1 funktorú Prolog struktúra, és egyetlen eleme van: az első argumentuma. Az adatág egy b/1 funktorú Prolog-struktúra, melynek argumentuma egy adatfákból álló Prolog lista. Az adatág elemei a benne levő adatfák elemei, a listának megfelelő sorrendben. Formálisan:

type adatfa ---> l(adatlevelelem) ; b(adatfalista).
type adatlevelelem == any.
type adatfalista == list(adatfa).

A feladat: egy egészekből álló adatfának meg kell keresni azon elemeit, melyek kisebbek az őket közvetlenül követő elemnél. Megírandó egy program Prolog nyelven, amely tartalmazza az agban/2 eljárást, melynek jelentése a következő:

% agban(+A,?X) pontosan akkor igaz, ha X olyan eleme az A adatfának,
% amely az őt A-ban közvetlenül követő elemnél kisebb. Csak akkor
% működik helyesen, ha A tömör, egészekből álló adatfa. A lehetséges
% X-eket az A-belihez képest fordított sorrendben sorolja fel.

Egy példamegoldás (khf-pl3.pl), amely csak néhány egyszerű struktúrájú adatfára működik helyesen:

agban(b([l(X),l(Y)]), X) :- X < Y.

A jobbrekurzív eljárások kevesebb memóriát igényelnek, mint az egyéb rekurzív eljárások, ezért a feladat megoldása során jobbrekurzív eljárások írása ajánlott, ám ez nem kötelező, a pontozásba nem számít bele.

Példák

Az alábbi példák olyan formában adottak, hogy azok a .pl fájl végére írhatók, és ha a SICStus a programot - goal failed üzenet (az SWI-Prolog pedig Goal (directive) failed üzenet) nélkül betölti, akkor a program a megadott példákra helyesen működik.

:- \+ agban(l(42), X). % az utolsó elemet nem követi senki
:- findall(X,agban(b([l(4),l(5)]),X),L), L==[4].
:- \+ agban(b([l(5),l(4)]), X). % 5 nem jó, mert 5 >= 4; a 4-et nem követi senki
:- findall(X,agban(b([b([l(4)]),b([]),l(5)]),X),L), L==[4].
   % a 4 jó, mert kisebb az őt követő 5-nél
:- findall(X,agban(b([l(11),l(22),b([l(33),l(34)])]),X),L),
   L==[33,22,11].
:- findall(X,agban(b([l(11),l(22),b([l(5)]),b([l(44)])]),X),L),
   L==[5,11]. % 5 < 44; 11 < 22
:- findall(X,agban(b([l(1),b([]),l(22),b([l(44),l(30)])]),X),L),
   L==[22,1]. % 22  < 44; 1 < 22
:- findall(X,agban(b([b([l(33)]),b([]),l(22),b([b([]),l(44),l(55)])]),X),L),
   L==[44,22]. % 44 < 55; 22 < 44

Otthoni tesztkörnyezet

A fejlesztés közbeni tesztelésre a SICStus Prolog vagy az SWI-Prolog ajánlott. Érdemes a fenti példákat a megoldás (.pl fájl) végére írni, hogy a megoldás minden újratöltésekor tesztesetként lefussanak. Ha a teszteseteket külön fájlba szeretnénk írni, akkor hasznos lehet az alábbi segédprogram (teszt3.pl):

:- consult('khf-pl3').
% ide kell írni a fenti példákat (,,:-''-vel kezdődő hívások)

Ha ezt a programot a környezet hiba és figyelmeztetés nélkül betölti (pl. a sicstus -l teszt3.pl vagy a

swipl -s
teszt3.pl

parancs hatására), akkor a khf-pl3.pl-ben nincs szintaktikai hiba, és a teszt3.pl-ben leírt három teszteset is hibátlanul fut le. Ha - goal failed vagy

Goal (directive)
failed

üzenetet kapunk, akkor az adott tesztesetre a program hibásan működik.

Tudnivalók a beadásról

A programot az Elektronikus Tanársegéd segítségével Weben keresztül lehet beadni, a HF beadás menüpont alatt. agban.pl néven kell beküldeni a megoldás Prolog forráskódját. A névben meg kell különböztetni a kis- és nagybetűket. A beadási határidő 2005. december 31., szombat 24:00.

A vizsgaosztályzat megállapításakor a határidőre beadott, helyesen megoldott kis házi feladatért plusz 1 pont jár (a 100 pontból).