Deklaratív programozás

4. Prolog kis házi feladat (1.1)

2004. április 28.

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

Bevezetés

Feladatunkban Prolog kifejezéseket kell átalakítani. A kifejezések tetszőlegesek lehetnek (a kifejezésben például tetszőleges helyen előfordulhatnak változók), sem hosszukra, sem mélységükre nincsen korlátozás. Ilyen kifejezés például az f(empty(1),node([1,2,4],empty,1-A),1-2,alma) struktúra.

Az átalakítás lényege, hogy bizonyos zárt, változókat nem tartalmazó listákat becsomagolunk, amennyiben azok megfelelnek egy előzetesen megadott kritériumnak. Például, amennyiben az [1,2,3] lista jó lista, akkor az f(a,3,[1,2,3],3+1) kifejezés átalakítottja az f(a,3,jo([1,2,3]),3+1) kifejezés. A becsomagolandó listák tetszőleges mélységben fordulhatnak elő. Egy, már becsomagolt kifejezés belsejében nem kell újabb részkifejezést becsomagolni.

Egy változókat nem tartalmazó lista akkor jó, ha egy előre megadott részlegesen paraméterezett eljárás igaz minden elemére. Ez utóbbit, a konvenciónak megfelelően úgy értjük, hogy a listaelemmel, mint utolsó paraméterrel paraméterezzük fel a megadott részlegesen paraméterezett eljárásunkat (lásd előadásfóliák, call eljárás, II. rész 119-122. oldal). Amennyiben a listaelem például az 5 szám, és a megadott eljárás (nulla aritású) a pozitiv, akkor a pozitiv(5) hívás sikerességét vizsgáljuk. Amennyiben a megadott eljárás a nagyobb(3), akkor a nagyobb(3,5) célsorozatot hívjuk meg. Feltehetjük, hogy a megadott eljárások sosem jeleznek hibát: vagy sikerülnek vagy meghiúsulnak.

Amennyiben egy lista változó(ka)t tartalmaz, akkor a kimenő kifejezésben változatlan formában kell megadnunk azt. Ugyanez igaz üres listák esetén is.

A feladat

Írjon egy olyan szuro/3 Prolog meta eljárást, amely az első argumentumában megadott kifejezést átalakít a második argumentumában megadott szűrőpredikátumnak megfelelően. Az eredményt a harmadik argumentumban adja vissza. Az elvárt eljárás fejkommentje:

% szuro(+Kif,:Szuro,-Ujkif): UjKif előáll Kif-ből Szuro felhasználásával

Tegyük fel, hogy például az alábbi eljárások definiáltak (a teszteléshez egészen másokat is használhatunk):

pozitiv(A):-
     number(A),
     A>0.
nagyobbmintegy(A):-
     number(A),
     A>1.
nagyobb(A,B):-
     B@>A.
paratlan(A):-
     number(A),
     1 is A mod 2.

Futási példák

| ?- szuro([],pozitiv,E).
E = [] ? ;
no

| ?- szuro([1,2,3,4],pozitiv,E).  
E = jo([1,2,3,4]) ? ;
no

| ?- szuro([1,2,3,4],nagyobbmintegy,E).
E = [1,2,3,4] ? ;
no

| ?- szuro(f(a,B,[1,2,3,4]),pozitiv,E).
E = f(a,B,jo([1,2,3,4])) ? ;
no

| ?-  szuro(f(a,B,[3,f(1,[3,3]),4]),nagyobb(2),E). % már becsomagolt belsejében nem csomagolunk, listaelem nem csak szám lehet
E = f(a,B,jo([3,f(1,[3,3]),4])) ? ;
no

| ?- szuro(g(f(a,B,[1,1,1]),t([1|_],[2],[1,A,1]),[1]),paratlan,E).
E = g(f(a,B,jo([1,1,1])),t([1|_A],[2],[1,A,1]),jo([1])) ? ;
no

| ?- szuro([1,2,3,g([1,2])],pozitiv,E). % listán belül is lehet jó lista, de ezt nem kell külön kezelni :)
E = [1,2,3,g(jo([1,2]))] ? ;
no

| ?- szuro([1,2|_],pozitiv,E). % nyílt végű lista!
E = [1,2|_A] ? ;
no

A programot Prolog nyelven kell elkészíteni.

Beadás, tudnivalók

A programot az Elektronikus Tanársegéd segítségével Weben keresztül lehet beadni, a HF beadás menüpont alatt. Ez a negyedik Prolog kis házi feladat, ezért khf-pl4.pl néven kell beküldeni a megoldást. A névben meg kell különböztetni a kis- és nagybetuket.

A programok készülhetnek MS DOS vagy MS Windows alatt is, de Linux operációs rendszer alatt is muködniük kell. A beadási határidő május 3., hétfő 24:00.

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