Deklaratív programozás

2. Prolog kis házi feladat

V1.2, 2006. december 12.

A feladat

Írjon olyan Prolog eljárást subst/3 néven, amely egy tetszőleges Prolog kifejezésben adott kifejezések minden előfordulását kicseréli adott más kifejezésekre! A cserék megadására egy Kulcs-Érték párokból álló lista szolgál.

Pontosítások:

A kulcsok egyediek, azaz a "kulcs" pozícíóban csupa különböző (\==) kifejezés áll.
Csak akkor kell egy kifejezést lecserélni, ha az teljesen azonos egy kulcs-kifejezéssel.
Mindig a lehető legbővebb kifejezést kell lecserélni.
A cseréket párhuzamosan végezzük el, azaz a lecserélt kifejezésekben további cseréket nem szabad végezni.

A subst/3 eljárás specifikációja a következő:

% subst(+Exp,+SubL,?SubExp): Exp kifejezésben a SubL kulcs-érték listában
%                            előírt cseréket elvégezve SubExp-et kapjuk.

Hasznos tudnivalók a feladathoz:

Struktúrák felbontására az univ beépített eljárás (=..) szolgál.
Egy kulcs és egy részstruktúra egyezésének vizsgálatához az (==) operátor használata ajánlott, mivel a kulcsokban szerepelhetnek akár behelyettesítetlen változók is.

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

| ?- [subst].
% consulting /home/drotos/dp/khf2/subst.pl...
% consulted /home/drotos/dp/khf2/subst.pl in module user, 0 msec 1080 bytes
yes
| ?- subst(2*x + 3*y + 4*x*y, [x-1, y-2], E).
E = 2*1+3*2+4*1*2 ? ;
no
| ?- subst(f(x,y), [x-b, f(x,y)-a], E). % f(x,y) bővebb, mint x
E = a ? ;
no
| ?- subst(2*x + 3*y + 4*x*y, [4*x*y-(X+1)], E).
E = 2*x+3*y+(X+1) ? ;
no
| ?- subst(f(15,14,X,[g(2,X),g(X,2)]), [g(2,X)-e(2,X), X-5, g(X,2)-g(x,3)], E).
E = f(15,14,5,[e(2,X),g(x,3)]) ? ;
no

Otthoni tesztkörnyezet

A fejlesztés közbeni tesztelésre a SICStus Prolog vagy az SWI-Prolog ajánlott. Hasznos lehet még az alábbi segédprogram (másolja ki és mentse el substtest.pl néven):

:- consult('subst').
:- bagof(E, subst(2*x + 3*y + 4*x*y, [x-1, y-2], E), S), S == [2*1+3*2+4*1*2].
:- bagof(E, subst(f(x, y), [x-b, f(x,y)-a], E), S), S == [a].
:- bagof(E, subst(2*x + 3*y + 4*x*y, [(4*x*y)-(X+1)], E), S), S == [2*x+3*y+(X+1)].
:- bagof(E, subst(f(15, 14, X, [g(2,X), g(X,2)]), [g(2,X)-e(2,x), X-5, g(X,2)-g(x,3)], E), S),
                                                             S == [f(15,14,5,[e(2,x),g(x,3)])].
:- bagof(E, subst(c(X,x)/d(y,X), [c(_,_)-42, X-Y, x-X*Y], E), S), S == [c(Y,X*Y)/d(y,Y)].

Ha a substtest.pl programot a környezet hiba nélkül betölti (pl. a sicstus -l substtest.pl vagy az swipl -s substtest.pl parancs hatására), akkor a subst.pl-ben nincs szintaktikai hiba, és a substtest.pl-ben leírt tesztesetek is hibátlanul futottak le.

Tudnivalók a beadásról

A kis házi feladat beadását, jóllehet nem kötelező, a tárgy minden hallgatójának nagyon ajánljuk.

A programot az Elektronikus Tanársegéd segítségével weben keresztül lehet beadni, a HF beadás menüpont alatt. A beadási határidő 2006. december 20., szerda 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.