IX. Programozás Prologban

Elsõ nekifutás: a Prolog elemei

A Prolog mesterséges intelligencia feladatok megoldására alkotott nyelv. A mesterséges intelligencia programok bizonyos típusú problémákat oldanak meg, melyek elsõ pillantásra emberi intuíciót igényelnek, bár némelyiküknek már létezik pontosan algoritmizálható megoldása is. Sok mesterséges intelligencia problémának azonban ma még nem ismert a pontos megoldása, és a programokban nagy szerepet játszanak az emberi tapasztalatokból leszûrt, nem bizonyított (heurisztikus) szabályok.

A Prolog nyelvre jellemzõ, hogy a programozónak nem megoldási algoritmust kell adnia, hanem a feladat megoldásához szükséges tényeket és szabályokat kell betáplálnia, melyek segítségével a Prolog önállóan jut el a végkövetkeztetésig.

A Prolog nyelvnek sok változata létezik, ebben a jegyzetben a Turbo Prolog szintaktikáját fogom használni. A tények és szabályok leírásában természetesen minden Prolog megegyezik.

A Prolog a matematikai logikára épül. A tények és szabályok megadása után a rendszernek feltehetõ egy eldöntendõ kérdés. A kérdés állítás formájában fogalmazandó meg, és a Prolog megadja, hogy az állítás igaz-e vagy hamis, illetve, hogy milyen esetekre igaz. Ha a betáplált tények és szabályok ismeretében ez nem dönthetõ el, a Prolog az állítást hamisnak veszi (ez egyáltalán nem nyilvánvaló! Pl. „A Szíriusz kis zöld emberkéi szeretik a tejbegrízt." igaz-e vagy hamis?).

A Prologban a szövegeket nem szükséges idézõjelbe tenni, de akkor nem kezdõdhetnek nagybetûvel és nem tartalmazhatnak szóközt. A nagybetûs szövegek a Prolog paramétereit jelzik.

A Turbo Prolog program szerkezete:

DOMAINS {típusdeklarációk}
   név=típus
   ...
PREDICATES {a szabályok paraméterei típusának megadása}
   szabály(paramétertípusok)
   ...
CLAUSES {a szabályok, végükön ponttal}
   szabály.
   ...
[GOAL] {nem interaktív mód esetén az eldöntendõ állítás}
   ...

Nézzünk egy Prolog programot:

DOMAINS
   s=symbol
PREDICATES
   hal(s)
   vanneki(s,s)
CLAUSES
   hal(ponty).
   hal(csuka).
   vanneki(ponty,pikkely).

A symbol típus tetszõleges kisbetûvel kezdõdõ, szóközmentes szöveget jelent. Egyéb típusok: integer, real, char, string. Ha a GOAL szekció hiányzik, a Prolog interaktív módban vár a kérdés beírására. A program lényegi része a CLAUSES azonosító után következik, a továbbiakban ezzel foglalkozuk.

A szabály neve után zárójelben adtuk meg a szabály paramétereit. Minden sor azt adja meg, hogy egy szabály milyen esetben teljesül, vagyis pl. a hal(valami) állítás mikor igaz. Ezen szabályok alapján feltehetjük a kérdést (?-lel jelölöm a kérdés promptját, ez Turbo Prologban Goal:):

? hal(egér)
? hal(ponty)
? hal(X)

Az elsõ kérdésre a válasz No, a másodikra Yes, a harmadikra X=ponty, X=csuka. A válasz a következõképpen született: a Prolog az elsõ esetben megvizsgált minden hal(...) szabályt. Sehol nem talált egyezést, így a válasz hamis. A második esetben talált egyezést,a válasz igaz. A harmadik esetben a kérdés szabad paramétert tartalmazott (olyan paraméter, amely még nem kapott értéket). A hal(...) szabályok vizsgálatánál a Prolog meghatározta, hogy X mely értékeire teljesülhet az állítás. Ez a Prolog mûködésének egyik kulcsa, a mintaillesztés. Ennek során a szabad paraméterek értéket kapnak.

1. feladat: mi lesz a válasz a következõ kérdésekre:
Vanneki(ponty,A), Vanneki(A,pikkely), Vanneki(A,szárny), Vanneki(X,Y)?

A _ (aláhúzás) olyan érték, amely mindenre illeszthetõ („akármi"). A hal(_) értéke Yes.

A tényeken kívül megadhatunk összetettebb szabályokat. Pl. az utolsó szabály helyett:

vanneki(X,pikkely) :- hal(X).

:- helyett használható if is. Ez a szabály azt mondja ki, hogy valaminek akkor van pikkelye, ha arra a valamire teljesül, hogy hal. Vanneki szabály kiértékeléséhez a Prolog megvizsgálja a hal szabályokat, és mintaillesztés segítségével egyezést keres.

Vanneki(csiga,pikkely) kiértékelésekor vanneki(X,pikkely) szabálynál illesztési lehetõséget vesz észre, elvégzi X=csiga illesztést, majd megvizsgálja hal(X) feltételt. X most már nem szabad paraméter, tehát a Prolog a hal(csiga) állítást értékeli ki. Nem talál egyezést, így a válasz No.

Vanneki(A,pikkely) kiértékelésekor vanneki(X,pikkely) ismét egyezést mutat, X=A illesztéssel. Így X továbbra is szabad paraméter marad (mivel A szabad paraméter), és hal(A) vizsgálata következik. Két megoldást kapunk A-ra.

= operátor kétféleképpen mûködik. érték = érték esetben megvizsgálja a két érték egyezését, és igaz vagy hamis eredményt ad. szabad paraméter = érték esetben mintaillesztõként mûködik, és az értéket értékül adja a szabad paraméternek, mely ettõl fogva nem lesz szabad, értékként mûködik. szabad paraméter = szabad paraméter esetben a baloldali paraméternek értékül adja a jobboldalit, mégpedig úgy, hogy a továbbiakban a baloldali helyett a jobboldalit használja (név szerinti paraméterátadás), ld. X=A illesztést elõbb. Az = operátor mûködése nem szimmetrikus, és nem használható érték = paraméter formában, ugyanis mindig a baloldalnak adja értékül a jobboldalt.

Egészítsük ki a szabályokat hal(angolna). sorral. Mivel az angolnának nincs pikkelye, a Vanneki szabály módosul. Valaminek van pikkelye, ha hal, és nem angolna. Ebben segít a not(érték) szabály, mely a benne lévõ állítás igazság-értékét fordítja meg:

vanneki(X,pikkely):- hal(X), not(X=angolna).

A not-on belül már nem mûködik a mintaillesztés, csak helyben kiértékelhetõ állításokat tartalmazhat, vagyis nem tartalmazhat szabad paramétereket. Ezért a két feltétel sorrendje nem cserélhetõ fel, mire a kiértékelés a not-ra kerül, X már értéket kapott.

A , (vesszõ) helyett and is használható, logikai és kapcsolatot jelent. Egy szabályon belül több, vesszõvel elválasztott rész-állítás lehet. A Prolog a következõképpen dolgozza fel az ilyen szabályokat: balról jobbra haladva mindegyik állításra keres megoldást. Példánkban tegyük fel a Vanneki(X, pikkely) kérdést. hal(X)-re talált X=ponty megoldást. Ezután a következõ állításra lép: not(X=angolna). Mivel a ponty=angolna tényleg hamis, ez az állítás is teljesül. A szabálynak vége, X=ponty kiírható. Ezután a Prolog visszalép, és keresi a következõ jó megoldást. X=csuka is megfelel. Végül X=angolna helyettesítéssel lép tovább, not(angolna=angolna) most nem teljesül. Ezért a Prolog visszalép eggyel, és újabb megoldást keres hal(X)-re. Nincs több, így leáll.

Látható, hogy az összes jó megoldás meghatározásához a Prolog a backtrack algoritmusát használta: ha egy lépés jó, jobbra lép a következõ feltételhez, ha nem, visszalép eggyel, és keresi a következõ jó megoldást (ld. V. fejezet).

Az egymás után következõ, azonos nevû szabályok egymással vagy kapcsolatban állnak. Ha egy szabály kiértékelését a Prolog backtrack kereséssel befejezte, a következõ szabályra lép (hogyan teljesülhet még az állítás).

2. feladat: Milyen megoldásokat ír ki a Prolog, és milyen sorrendben?
? hal(X), hal(Y), not(X=Y)

3. feladat: miért hibás az abszolútérték következõ megvalósítása, és hogyan kellene helyesen leírni?
   abs(X,Y):- X>=0, Y=X.
   abs(X,Y):- Y=-X.

Ha nem akarjuk, hogy a Prolog visszalépjen, hogy a többi lehetõséget megvizsgálja, használhatjuk a ! jelet, mely visszalépés esetén leállítja a kiértékelést. A fenti program lehetséges kijavítása:
   abs(X,Y):- X>=0, !, Y=X.
   abs(X,Y):- Y=-X.
Így ha X>=0, de Y=X nem teljesül, nem lép vissza, hogy a következõ sorban rossz megoldást találjon.

A rekurzió természetes velejárója a Prolog programozásának, hiszen ciklus egyáltalán nincs benne. (ld. a III. fejezetet!) Nézzük meg a faktoriális megvalósítását:

fakt(0,1).
fakt(A,B):- Z=A-1, fakt(Z,E), B=E*A, !.

A Prolog csak logikai (igaz/hamis végeredményû) függvényeket ismer. A faktoriális-függvényt úgy kell megfogalmaznunk, hogy „mikor teljesül, hogy A faktoriálisa B?" Ha a Prolog már talált egy megoldást, meg kell akadályoznunk, hogy Z=A-1 helyettesítést újból végrehajtva a végtelen visszalépés hibát okozzon, ez a szerepe !-nek. Továbbá, a két szabály sorrendje sem mindegy: ha a második szabályt tettük volna elõre, az, mivel minden esetben illeszthetõ, szintén végtelen rekurziót okozott volna.

4. feladat: készítsd el Prologban a hatványozás függvényét (természetesen csak egész kitevõkre, az alap lehet real)!

Egy leszármazási sort írnak le a következõ típusú tények. A gyereket mindig az apánál jelezzük (feltételezzük, hogy minden gyerek boldog házasságban jött világra):
   gyereke(apa,gyerek)
   felesege(apa,anya)

A közvetlen leszármazott definíciója:
   leszarm(F,GY):- gyereke(F,GY).
   leszarm(F,GY):- felesege(A,F), gyereke(A,GY).

5. feladat: írd meg az Utod(F,U) függvényt (F-nek U közvetlen vagy nem közvetlen leszármazottja). Töltsd föl tényekkel az adatbázist, és teszteld!

6. feladat: írd meg és teszteld a következõ függvényeket!
   Anyja(F,GY) (F anyja GY-nek)
   Anya(F) (F valakinek (_) az anyja)
   Rokon(X,Y) (X-nek és Y-nak van közös õse)
   Testver(X,Y) (X és Y szülei közösek)
   Unoka(F,GY) (F-nek GY unokája)
   Utod2(F,GY,N) (F-nek GY N-edik generációs utódja)

Második nekifutás: mûveletek listákkal

A Prolog jellemzõ adatszerkezete a lista. A DOMAINS szekcióban a lista típusa alaptípus*-gal jelölt (pl. symbol*). Lista kétféleképpen adható meg: [elem, elem,...], vagy [elem, elem... | maradéklista] (ld. a III. fejezet LOGO-beli listáit). Mintaillesztésnél a lista egyes komponenseire külön-külön lehet illeszteni, pl. [a,b,c] listára [E|L] illesztésével E=a, L=[b,c] lesz az eredmény. Példa lista elemszámára:

DOMAINS
   l=symbol*
PREDICATES
   elemszam(l,integer)
CLAUSES
   elemszam([],0).
   elemszam([_|L],N):- elemszam(L,X), N=X+1.

Figyeljük meg _ használatát paraméter helyett. Szabad paraméter használata felesleges lett volna, mert az illesztett értéket sehol nem használnánk fel. ! használatára viszont nem volt szükség az ismételt rekurzió elkerülésére, mert az üres lista nem illeszthetõ a második szabályra.

1. feladat: írd meg eleme(elem,lista) függvényt, mely eldönti, a lista tartalmaz-e egy bizonyos elemet!

Vizsgáljuk meg, mi a hiba a következõ szabályban (hanyszor(elem,lista,szám), a lista szám-szor tartalmaz egy elemet):
   hanyszor(_,[],0).
   hanyszor(S,[E|L],N):- S=E, hanyszor(S,L,X), N=X+1.
   hanyszor(S,[_|L],N):- hanyszor(S,L,N).

Ha egy paraméter illeszkedik a 2. szabályra, az illeszkedni fog a harmadikra is. A jó megoldás után ezért a Prolog rossz megoldásokat is fog találni, kisebb számokkal, egészen 0-ig. Ez elkerülhetõ, ha a 3. szabályra csak akkor kerül sor, ha a 2. nem teljesült. Tehát a 3. szabály helyesen:
   hanyszor(S,[E|L],N):- not(E=S), hanyszor(S,L,N).
De ehelyett használhatjuk a !-et a 2. szabály végén (így ha a 2. szabály teljesül, több szabályt nem keres a Prolog). A szabályok feldolgozása gyorsítható, ha a 2. szabályban az E=S feltételt már a mintaillesztésnél feldolgozzuk. Így a 2. szabály:
   hanyszor(S,[S|L],N):- hanyszor(S,L,X), N=X+1.

2. feladat: írj függvényt, mellyel megadható egy lista valahányadik eleme! Ugyanezzel a függvénnyel megadható az is, hogy egy elem hányadikként szerepel a listában.
hanyadik(lista,elem,sorszám)

3. feladat: készíts függvényt, mellyel meghatározható egy számokat tartalmazó lista elemeinek összege!

Nézzük meg, hogyan lehet lista valahányadik elemét kivenni a listából:
   kivesz([_|L],1,L).
   kivesz([E|L],N,[E|L2]):- M=N-1, kivesz(L,M,L2).

4. feladat: készíts függvényt, mely két listát egy harmadikká kapcsol össze!

Látható, hogy a lista-mûveletek lényege (rekurzió, visszavezetés maradéklistára) azonos a LOGO-nál látottakkal, csupán logikai függvényként kell megfogalmazni.

Nézzünk most egy összetettebb példát: a repulo(varos,varos) tények megadják, hogy mely városok között van közvetlen repülõgép-összeköttetés. Ha A és B össze van kötve, a tények között nem szerepel repulo(B,A), de azért azt is élnek kell venni. Ezért definiáljuk a közvetlen járatra vonatkozó szabályt:
   jarat(A,B):- repulo(A,B).
   jarat(A,B):- repulo(B,A).
Ezután megfogalmazzuk, hogy mikor lehet eljutni egyik városból a másikba: ha van köztük közvetlen járat, vagy az egyikbõl el lehet jutni egy olyan közbensõ városba, amelybõl el lehet jutni a másikba:
   eljut(A,B):- jarat(A,B).
   eljut(A,B):- jarat(A,X), eljut(X,B).
Vigyázat: a leszármazási fánál ez a módszer mûködött. Ez azonban általános gráf bejárása, és mindenképpen el kell kerülnünk a köröket, különben végtelen rekurzió állhat elõ. Tehát a klasszikus gráfbejáró algoritmushoz hasonlóan itt is tárolnunk kell, hogy hol jártunk. Ez listában történik. A program mélységi keresést végez.
   eljut(A,B,L):- jarat(A,B), not eleme(B,L).
   eljut(A,B,L):- jarat(A,X), not eleme(X,L), L2=[X|L], eljut(A,B,L2).

A függvény hívása eljut(város,város,[]) formában történik.

Harmadik nekifutás: barátságosabb programok

A Prolog programban szerepelhet egy GOAL szekció is, mely a kiértékelendõ kifejezést tartalmazza. Ekkor a Prolog nem interaktív módban fut, vagyis nem tesz fel kérdést. A Turbo Prolog ebben az üzemmódjában csak egy jó megoldást keres, és azután nem lép vissza. A felhasználói felülethez a Prolog tartalmaz olyan függvényeket, melyeken a kiértékelés „átlép", és mellékhatásuk miatt lényegesek (pl. kiírnak valamit). Ilyenek:

• write(kifejezés) (kiírás)
• readln(szabad paraméter) (string típusú értéket olvas a paraméterbe)
• readint(szabad paraméter) (integer típusú értéket olvas a paraméterbe)
• nl (sort emel)

Klasszikus példa: a program számokat kér be, kiírja a reciprokukat, kivéve a 0-t, mert akkor leáll. A végtelen ciklust végtelen rekurzióval oldottuk meg.

PREDICATES
   megold
CLAUSES
   megold:- readint(X), not(X=0), Z=1/X, write(Z), nl, megold.
GOAL
   megold

Végül nézzük meg, hogyan lehet az összes megoldást kiíratni GOAL üzemmódban.

GOAL
   eleme(E,[a,b,c,d,e]), write(E), nl

Ekkor a program csak a lista elsõ elemét írja ki, mert az elsõ megoldásnál leáll. A Prolog FAIL függvénye mindig No-ra értékelõdik ki, ezt használhatjuk arra, hogy attól a ponttól visszalépjen, mintha nem talált volna megoldást. A következõ javítással a program kiírja a lista összes elemét:
   eleme(E,[a,b,c,d,e]), write(E), nl, Fail

A vagy kapcsolatot (or, vagy pontosvesszõ) arra használhatjuk, hogy megtakarítsuk vele az azonos függvényfejre való ismételt mintaillesztést. Az elõzõ rész Jarat függvénye ennek felhasználásával:
   jarat(A,B):- repulo(A,B); repulo(B,A).

Ez pontosan úgy mûködik, mint az elõzõ oldali változat.