Deklaratív Programozás 1. Prolog gyakorlat 2024 október 15. "V" Témakör: Prolog végrehajtás =============================== Az alábbi V1-V4 feladatokhoz definiáljuk egy személy felmenőjét a következő két állítással: X felmenője Y, ha Y X egyik szülőjének felmenője. X felmenője X. Tekintse a fenti definíciót megvalósító és a "szülője" kapcsolatot is leíró alábbi Prolog programot. % f(X, Y): X felmenője Y. f(X, Y) :- sz(X, S), f(S, Y). % (f1) f(X, X). % (f2) % sz(X, Y): X szülője Y. sz(a, b). % (sz1) sz(a, c). % (sz2) sz(c, d). % (sz3) V1. Rajzolja fel a | ?- f(a, V). (1) kérdéshez tartozó keresési fát! A keresési fa alapján írja le, hogy a Prolog rendszer erre a kérdésre milyen válaszokat ad, és milyen sorrendben adja ezeket! V2. (szorgalmi, otthoni feladat) Rajzolja fel a | ?- f(U, V). kérdéshez tartozó keresési fát; ennek alapján írja le, hogy a Prolog rendszer erre a kérdésre milyen válaszokat ad, és milyen sorrendben adja ezeket! V3. Adja meg, hogy az (1) kérdésre milyen sorrendben kapjuk meg a válaszokat, ha a fenti programban az (f1) és (f2) klózok sorrendjét megcseréljük! V4. (szorgalmi, otthoni feladat) Mi történik az (1) kérdés futtatásakor, ha az (f1) és (f2) klózok ebben a sorrendben követik egymást, de az (f1) klóz törzsében levő két hívás sorrendjét megcseréljük? Megoldását ellenőrizheti a Tau Prolog segítségével, ld. http://tau-prolog.org/sandbox/, a Derivation tree visualization fül kiválasztásával. "P". Témakör: programok írása ============================= A programozási feladatok megoldásaként olyan Prolog eljárást kell írnia, amely megfelel az adott fejkommentnek. Bármely feladat megoldásához felhasználhat korábbi sorszámú feladatokban definiált eljárásokat. Ha ilyeneken kívül is szükséges segédeljárás definiálása, azt külön jelezzük. Természetesen más esetben is használhat segédeljárást. Minden segédeljáráshoz írjon fejkommentet! Nem használhat olyan eljárásokat, amelyek a SICStus rendszerben csak a lists (vagy más) könyvtár betöltésével érhetőek el. Nem használhatja a mellékhatásos beépített eljárásokat, valamint az alábbi listakezelő eljárásokat: append/3, member/2, memberchk/2, nonmember/2. Hibakezeléssel nem kell foglalkoznia: a megírt eljárásoknak csak a fejkomment által megadott argumentumértékek esetén kell az előírt módon viselkedniük. A fejkommentekben használt ún. input/output módjelölések magyarázata: *: az argumentum tömör bemenő, azaz nem lehet változó, és nem is tartalmazhat változót; +: az argumentum bemenő, azaz nem lehet változó, de tartalmazhat változót (természetesen csak akkor, ha az argumentum egy struktúra); -: az argumentum kimenő, azaz változó; ?: az argumentum lehet kimenő és bemenő is. Segédlet az aritmetikai beépített eljárásokról ---------------------------------------------- (BIP = Built-In Predicate = beépített predikátum) Artimetikai kifejezések: Egy aritmetikai kifejezés (AKif) az azt tartalmazó BIP végrehajtásakor már kötelezően - tömör (ground) kell legyen, azaz behelyettesítetlen változót nem tartalmazhat - csak számokból és megengedett aritmetikai függvényekből állhat - A legfontosabb kétargumentumú függvények: +, -, *, / (a / mindenképpen lebegőpontos eredményt ad), // (egész-osztás, 0 felé kerekít), rem (maradék, // szerint) Aritmetikai BIP-ek: X is AKif: Az AKif aritmetikai kifejezés értékét egyesíti X-szel, pl. | ?- X = 2, Y is X+1. ==> X = 2, Y = 3 ? ; no | ?- Y is X+1, X = 2. ==> Instantiation error | ?- 3 is 2+1. ==> yes | ?- 1+3 is 6-2. ==> no (a bal oldalt nem értékeli ki!) | ?- X = 1, Y is (X-27) rem (X+2). ==> X = 1, Y = -2 ? ; no | ?- Kif = X/(X-1), X = 6, Y is Kif. ==> Kif = 6/(6-1), X = 6, Y = 1.2 ? ; no További aritmetikai BIP-ek: AKif1 < AKif2, AKif1 > AKif2, AKif1 =< AKif2 (vigyázat: nem <=), AKif1 >= AKif2, AKif1 =:= AKif2 (aritmetikailag egyenlő), AKif1 =\= AKif2 (aritmetikailag nem-egyenlő) ezek mindkét oldalt kiértékelik, és elvégzik a kért összehasonlítást Pl. | ?- 1+3 =:= 6-2. ==> yes | ?- 1+1 =\= 6/3. ==> no Prolog programozási feladatok ----------------------------- P1. Egészlista minden elemének növelése % lista_noveltje(*L0, -L): Az L egészlista úgy áll elő az L0 % egészlistából, hogy az utóbbi minden egyes elemét 1-gyel megnöveljük. | ?- lista_noveltje([1,5,2], L). L = [2,6,3] ? ; no P2. Egy lista utolsó elemének meghatározása % lista_utolso_eleme(*L, ?Ertek): Az L egészlista utolsó eleme Ertek. | ?- lista_utolso_eleme([5,1,2,8,7], E). E = 7 ? ; no | ?- lista_utolso_eleme([], E). no P3. Számtani sorozat generálása % seq(+N, +M, -L): Az L lista M-N+1 hosszú, elemei 1 különbségű % számtani sorozatot alkotnak, és L első eleme (ha van) N, ahol N % és M egész számok. | ?- seq(2, 4, L). L = [2,3,4] ? ; no | ?- seq(4, 2, L). no | ?- seq(4, 3, L). L = [] ? ; no | ?- seq(-4, -2, L). L = [-4,-3,-2] ? ; no P4. Számintervallum felsorolása % max(+N, ?X): X egy egész szám, melyre 0 < X =< N, ahol % N egy adott egész szám. % Az eljárás a fenti feltételeknek megfelelő összes számot sorolja % fel! Ez az eljárás nemdeterminisztikus, azaz többféleképpen % sikerülhet. A felsorolás sorrendjére nem teszünk megkötést. | ?- max(1,X). X = 1 ? ; no | ?- max(4,X). X = 4 ? ; X = 3 ? ; X = 2 ? ; X = 1 ? ; no | ?- max(4,3). yes | ?- max(4,5). no | ?- max(0,X). no | ?- max(-6,X). no P5. Egy lista adott n-edik elemének meghatározása (A listaelemeket 1-től kezdve számozzuk -- ez a további feladatokra is érvényes, ha nem mondunk mást.) % ennedik(+N, *L, -E): E az L lista N-edik eleme. | ?- ennedik(2, [a,b], E). E = b ? ; no | ?- ennedik(4, [a,b], E). no | ?- ennedik(-23, [a,b], E). no P6. Lista adott hosszúságú prefixuma Egy L n-elemű lista prefixumának nevezünk egy listát, ha az az L első k elemét tartalmazza (az L-beli sorrend megtartásával), ahol 0 =< k =< n. % prefixum(*Lista, +Hossz, -Pref): A Lista lista Hossz hosszúságú % prefixuma a Pref lista. | ?- prefixum([a,b,c,d,e], 3, Prefix). Prefix = [a,b,c] ? ; no P7. Lista adott helyen kezdődő szuffixuma Egy L lista szuffixumának nevezünk egy listát, ha az az L utolsó valahány elemét tartalmazza, az L-beli sorrend megtartásával. % szuffixum(*Lista, +Elozok, -Szuffixum): A Lista lista azon % szuffixuma a Szuffixum lista, amelyet Elozok számú listaelem előz % meg. | ?- szuffixum([a,b,c,d,e], 3, Sz). Sz = [d,e] ? ; no P8. Egy lista adott n-edik elemének a cseréje % ennedik_csere(+N, *L0, -E0, -L, +E): E0 az L0 lista N-edik eleme. L az % L0-ból úgy áll elő, hogy L0-nak az N-edik elemét E-re cseréljük. | ?- ennedik_csere(2, [a,b,c], E0, L, x). E0 = b, L = [a,x,c] ? ; no | ?- ennedik_csere(3, [u,v,w], E0, L, a). E0 = w, L = [u,v,a] ? ; no P9. Egy lista összes prefixumának felsorolása % prefixum(*L0, -L): L az L0 egészlista prefixuma. % Az eljárásnak az L változóban fel kell sorolnia a L0 összes % prefixumát. A felsorolás sorrendjére nem teszünk megkötést. | ?- prefixum([1,4,2], P). P = [1,4,2] ? ; P = [1,4] ? ; P = [1] ? ; P = [] ? ; no Gondolja meg, hogy a predikátum klózai sorrendjének változtatásakor hogyan változik a felsorolás sorrendje! P10. Részlista képzése % reszlista(*Lista, ?Resz, +Elotte, +Hossz): A Lista lista azon % (folytonos) részlistája Resz, amely előtt Elotte számú elem áll % és amelynek hossza Hossz. | ?- reszlista([a,b,c,d,e], Resz, 1, 3). Resz = [b,c,d] ? ; no | ?- reszlista([a,b,c,d,e], Resz, 3, 0). Resz = [] ? ; no | ?- reszlista([a,b,c,d,e], Resz, 6, 0). no P11. Egy lista elemeinek és és a hozzájuk tartozó indexeknek a felsorolása. A felsorolás sorrendjére nem teszünk megkötést. Segédeljárással jobbrekurzívvá tehető. % ennedik_f(-N, *L, -E): E az L lista N-edik eleme. | ?- ennedik_f(N, [a,x,p], E). N = 1, E = a ? ; N = 2, E = x ? ; N = 3, E = p ? ; no P12. Egy lista n-edik elemének a cseréje, ahol n nem feltétlenül adott. A felsorolás sorrendjére nem teszünk megkötést. % ennedik_csere_f(?N, *L0, ?E0, ?L, ?E): E0 az L0 lista N-edik eleme. % L az L0-ból úgy áll elő, hogy L0-nak az N-edik elemét E-re cseréljük. | ?- ennedik_csere_f(N. [a,b,c], E0, L, x). N = 1, E0 = a, L = [x,b,c] ? ; N = 2, E0 = b, L = [a,x,c] ? ; N = 3, E0 = c, L = [a,b,x] ? ; no P13. Részlisták felsorolása % reszlista_f(*Lista, ?Resz, ?Elotte, ?Hossz): A Lista lista azon % (folytonos) részlistája Resz, amely előtt Elotte számú elem áll % és amelynek hossza Hossz. Resz üres lista is lehet. % A felsorolás sorrendjére nem teszünk megkötést. % Itt kivételesen megengedjük az append eljárás használatát. | ?- reszlista_f([a,b], Resz, Elotte, Hossz). Resz = [], Elotte = 0, Hossz = 0 ? ; Resz = [a], Elotte = 0, Hossz = 1 ? ; Resz = [a,b], Elotte = 0, Hossz = 2 ? ; Resz = [], Elotte = 1, Hossz = 0 ? ; Resz = [b], Elotte = 1, Hossz = 1 ? ; Resz = [], Elotte = 2, Hossz = 0 ? ; no