A Prolog programozási nyelv

Utasítások, vezérlési szerkezetek

Utasítások

Egyszerű állítások

Egy egyszerű állítás felfogható, mint valamiféle reláció az objektumok között. Ezt a relációt a predikátuma és az argumentumszáma azonosítja, ennek megfelelően ugyanazon predikátum segítségével több állítást is megfogalmazhatunk, méghozzá több különböző reláció esetében is. Ezeket az állításokat természetesen igaznak tekintjük, ezért akár axiómáknak is hívhatnánk őket. Logikai szempontból pedig ezek az egységklózok.

nem_oszthato( 5, 0 ). egyenlo( 2 * 2, 5 ). paros_szam(12).

A harmadik példára tekintve elmondhatjuk, hogy ha egy objektum valamely tulajdonságát szeretnénk kifejezni, akkor erre legalkalmasabb az egyargumentumú reláció. Természetesen nem csak a felhasználó definiálhat ilyen predikátumot, hanem minden Prolog-implementáció tartalmaz előre definiált predikátumokat is. A predikátumokat nevükkel és aritásukkal jellemezhetjük, név/aritás formájában. Az aritás egy predikátum argumentumainak száma. Egy relációt több állítás is meghatározhat, ilyenkor beszélünk unióról.

Például a szülője/2 reláció az anyja/2 és az apja/2 relációk uniója:

szülője(X,Y) :- anyja(X,Y). szülője(X,Y) :- apja(X,Y).

Lekérdezések

Ahhoz, hogy a Prolog-interpreter (vagy compiler) eldönthesse bizonyos állítás (cél) igazságértékét, deklarálni kell egy lekérdezést a programszövegben, amely részcéljai között szerepel a kérdéses állítás. Egyáltalán ha azt akarjuk, hogy a programunk valahol elkezdje a futását, akkor szükséges egy lekérdezés deklarálása is. Például (az előbbi példát folytatva):

?- egyenlo(5,5).

lekérdezésre a rendszer egy "No"-val fog válaszolni, ugyanis a lekérdezésben megfogalmazott állítást egyik korábban deklarált állításra sem tudta illeszteni. Továbbá a:

?- nem_oszthato(5,X), write(X).

kérdésre a válasz "Yes" lesz, ugyanis a 0 konstanst az X változóval helyettesítve (amit meg lehet tenni) illeszteni tudjuk a keresett részcélt. Ez tulajdonképpen azt jelenti, hogy a Prolog-fordító el tudja dönteni, hogy létezik-e olyan X melyre teljesül a fenti állítás, és ez az objektum a 0. Mindezeknek az lesz a hatása, hogy az X változó a 0 konstanssal példányosul, és az adott mondat (itt maga a lekérdezés) törzsének hátralevő részében az X változóhivatkozás a 0 konstanst fogja jelenteni. Tehát a "write" beépített predikátum illesztésének a hatására a képernyőre a 0 szám fog kerülni.

Általánosítás

A gyakorlatban sokszor van szükség több hasonló fajtájú állítás megfogalmazásra (paraméteres állítás). Például:

nem_oszthato( X, 0 ). % egyik szám sem osztható 0-val

Ekkor a következő lekérdezésre természetesen "Yes" a válasz:

?- nem_oszthato( 231234, 0 ).

Sőt az első argumentumba bármit is írva (és nem csak egész konstanst!) a válasz pozitív lesz. Az ilyen paraméteres állítások segítségével tudunk továbbá univerzálisan kvantált formulákat Prolog-ban interpretálni.

Levezetési szabályok

Nyilván egy Prolog-programnak nem kell tartalmaznia az összes olyan állítást, melyek pozitív megválaszolására képes. Sok állítás igazságértéke kikövetkeztethető a többi állítás felhasználásával (rezolúció). Például ne kelljen megadnunk egy rendezési relációt objektumok bizonyos halmazán úgy, hogy az összes lehetséges párosítást felsoroljuk. Helyette nagyon sok állítást kiválthatunk, ha deklaráljuk a tranzitivitási tulajdonságot axiómaként. Tehát:

r(a,b). r(b,c). r(c,d). r(d,e). r(X,Y) :- r(X,Z), r(Z,Y).

És itt az utolsó deklaráció már egy levezetési szabály (mondat). A mondat törzsében található célokat alapvetően a "," karakter határolja el, mely a logikai és-nek felel meg. Sokszor szükségünk lehet ennek párjára (a logikai vagy-ra). Ezt úgy oldhatjuk meg ha azonos fejjel szétbontjuk mondatunkat további mondatokra, mely szemantikailag - az illesztés szabályai miatt szintén a logikai vagy-nak fog megfelelni. A mondatokat - akár a természetes nyelvekben a pont (".") karakter terminálja.

Végrehajtási mechanizmus

Egy Prolog programra kétféle szemantika adható: tekinthetjük logikai formulák halmazaként (deklaratív értelmezés), vagy algoritmusként (procedurális értelmezés). Bár a deklaratív értelmezés alapján megállapítható a program helyessége, csak a procedurális értelmezésből dönthető el, hogy nem kerül-e végtelen ciklusba, és a nyelv nem-deklaratív elemei is megnehezítik a logikai értelmezést. A procedurális szemlélet szerint a Prolog programban szereplő, azonos nevű és argumentumszámú klózok egy eljárást alkotnak. Az eljárást meghatározó név/argumentumszám párost az eljárás funktorának nevezzük. Ha az eljárás több klózból áll, ezeket eljárásváltozatoknak nevezzük. Minden lekérdezés megfelel egy eljáráshívásnak. A paraméterátadás egy kétirányú mintaillesztés segítségével történik, amit egyesítésnek hívunk. Abban a sorrendben próbáljuk az eljáráshívást az eljárásváltozatokkal egyesíteni, amelyben azokat a programban definiáltuk; egy ilyen egyesítési kísérlet neve redukciós lépés. A redukciós lépés sikeres, ha a hívás és a klóz feje változó-behelyettesítéssel azonos alakra hozható, ekkor a célsorozatban (a célvezérelt keresésből átvett fogalom; a célsorozatban tartjuk nyilván a még meg nem vizsgált feltételeket, kezdetben megegyezik a lekérdezéssel) a változó-behelyettesítések után az első elemet az illesztett klóz törzsére cseréljük le (ha a klóz tényállítás volt, az első elemet töröljük). A végrehajtási mechanizmus a visszalépéses keresésen alapszik, az algoritmus pszeudokódja (CS a pillanatnyi célsorozat, I az aktuális klóz sorszáma az eljáráson belül):

  1. (Kezdeti beállítások:) A verem kezdetben legyen üres, CS := kezdeti célsorozat
  2. (Beépített eljárások:) Tekintsük a CS célsorozat első hívását. Ha ez beépített eljárásra vonatkozik, akkor hajtsuk végre az eljárást:
    1. Ha a végrehajtás sikertelen, akkor menjünk a 6. lépésre.
    2. Ha a végrehajtás sikeres, akkor végezzük el a beépített eljárás által esetleg kiváltott behelyettesítéseket a CS sorozaton, hagyjuk el az első hívást, és az így kapott célsorozatot tekintsük a továbbiakban CS-nek. Ezután folytassuk a 5. lépéssel.
  3. (Klózszámláló kezdőértékezése:) Legyen I = 1.
  4. (Redukciós lépés:) Itt CS első hívása nem beépített. Tekintsük a híváshoz tartozó eljárásdefiníciót, legyen az ebben levő klózok száma N.
    1. Ha I > N, akkor menjünk a 6. lépésre.
    2. Tekintsük a definíció I-edik klózát és kíséreljünk meg egy redukciós lépést erre a klózra és a CS célsorozatra.
    3. Ha a redukciós lépés sikertelen, akkor I := I+1, és (változatlan CS mellett) ismételjük a 4. lépést.
    4. Itt a redukciós lépés sikeres. Ha I < N (nem utolsó klóz), akkor mentsük el a verem tetejére a (CS, I) párt.
    5. A redukciós lépés eredményeként kapott célsorozatot tekintjük CS-nek.
  5. (Siker:) Ha CS üres sorozat, akkor a végrehajtási algoritmus sikeresen véget ért, egyébként folytassuk a 2. lépésnél.
  6. (Sikertelenség:) Ha a verem üres, akkor a végrehajtás sikertelenül véget ért.
  7. (Visszalépés:) Ha a verem nem üres, akkor leemeljük a verem tetején levő (CS, I) párt, ebből visszaállítjuk a CS és I változók értékét. Ezután I := I+1, és folytatjuk a 4. lépésnél.

Siker esetén az alkalmazott helyettesítésekből nyerjük a megoldást; ha az esetleges további megoldásokra is kíváncsiak vagyunk, a végrehajtást folytatnunk kell a 7. ponttal.

Egy prolog program végrehajtása tekinthető keresési fájának visszalépéses bejárásának is. A keresési fa gyökere az eredeti cél, csúcsai a levezetés során előállított célsorozatok, élei a célredukciós lépések és levelei az üres célsorozatok, a megoldáslevelek, vagy ahol a részcél nem redukálható, a fail-levelek. Minden megoldáslevélhez az eredeti kérdés egy-egy megoldása tartozik. A prolog végrehajtási mechanizmusa – mint a fentebbi leírásból is kiolvasható – legbal részcélkiválasztási módszer, vagyis mindig az első részcélt választjuk ki, és ezt próbáljuk helyettesíteni vagy egyesíteni. Tehát a Prolog gép visszalépéses kereséssel bejárja a keresési fát, ennek ágait természetesen nem építi fel előre, és visszalépéskor le is bontja, ezzel optimalizálva a futó program memóriaigényét.

A vágó utasítás

Előfordul, hogy a gyorsabb futás érdekében, szűkíteni kívánjuk a keresési teret. Ilyenkor jön jól a beépített !/0 vágó utasítás. Használatát piros és zöld vágás szerint különböztetjük meg. A vágó akkor piros, ha a keresési teret ténylegesen módosítjuk, például érvényes megoldásokat vágunk le a keresési fából. Zöld a vágó akkor, ha használatakor nem vágunk le egyetlen megoldást sem, ekkor csak a programot informáljuk arról, hogy arra ne is keressen megoldást.

A vágóval kijelentjük, hogy egy klóznak csupán az első megoldása érdekel minket (hiszem minden más választási pontot megszüntettünk), másrészt elkötelezzük magunkat egy adott klóz választása mellett. Alább kép példát láthatunk piros és zöld vágásra. Az első példában azért piros színű a vágás, mert teljesen mindegy, hányszor van benne X az Ys listában (remélhetőleg legfeljebb egyszer), mindenképp ugyan azt kell csinálni, folytatni kell a két lista összakapcsolását X kihagyásával. Itt tehát más lehetséges megoldások választási pontjait vágjuk le a keresési fáról. Második példánkban zöld színű a vágás, hiszen egy számról mindig egyértelműen eldönthető, hogy kisebb-e, mint nulla, és ha így van, még csak gondolnunk sem szabad arra, hogy abszolútértéke esetleg önmaga lenne.

% piros vágó unió2([],Ys,Ys). unió2([X|Xs],Ys,Zs) :- member(X,Ys), !, unió2(Xs,Ys,Zs). unió2([X|Xs],Ys,[X|Us]) :- unió2(Xs,Ys,Us).
% zöld vágó abs(X,Y) :- X<0, !, Y is -X. abs(x,X).

Ha nem használjuk kellő körültekintéssel a vágót, hibás működést tapasztalhatunk, és bár azt hisszük, jól írtuk meg a predikátumunk, mégis mi voltunk a hibásak. A következő példán keresztül egy ilyen esetet mutatunk be két szám maximumának meghatározásán keresztül.

% hibás vágóhasználat max(X,Y,X) :- X>=Y, !. max(X,Y,Y).

Ha végiggondoljuk, láthatjuk, hogy a probléma akkor jelentkezik, ha azt akarjuk leelenőrizni, hogy a második paraméterben adott érték e a kettő közül a nagyobbik. Ekkor, mivel az első és a harmadik paraméter a második állításban egyezik meg, programunk úgy véli (és joggal) hogy az oldja meg a feladatot, még akkor is, ha valójában Y a kisebbik. A probléma okát könnyebben megtalálhatjuk, ha szétbontjuk az első predikátumot: max(X,Y,Z) :- Z=X, X>=Y, s!. Látató tehát, hogy nem csak akkor hiúsul meg az első állításunk, ha X kisebb, mint Y, hanem akkor is, ha X és Z nem illeszthető.

Abban az esetben, ha a hibás predikátumunkat lecseréljük a következőre, nem futunk köbbé ebbe a hibába, mert előbb elenőrizzük le a két szám viszonyát, majd csak miután levágtunk minden más választási pontot próbáljuk meg X-et és Z-t illeszteni.
 max(X,Y,Z) :- X>=Y, !, Z=X.

Egyesítési algoritmus

Az egyesítési algoritmus szolgál annak eldöntésére, hogy két kifejezéssorozat milyen változó-behelyettesítések mellett felel meg egymásnak. Legyenek A1 ... AN és B1 ... BN az egyesítendő sorozatok:

  1. Ha N>1, akkor megkíséreljük az A1 és B1 egyelemű sorozatok egyesítését. Ezután elvégezzük a kapott behelyettesítést az A2 , . . . , AN , ill. B2 , . . . , BN sorozatokon, majd megkíséreljük ezeket a sorozatokat is egyesíteni. Az eredő egyesítés akkor és csak akkor sikeres, ha mindkét rész-egyesítés sikeres. A eredményezett behelyettesítést úgy kapjuk meg, hogy a kapott két behelyettesítés eredőjét vesszük. A továbbiakban feltételezhetjük, hogy N=1.
  2. Ha A1 és B1 azonos változók vagy konstansok, akkor az egyesítés sikeres, üres behelyettesítéssel.
  3. Egyébként, ha A1 változó, akkor az egyesítés sikeres az A1 = B1 behelyettesítéssel.
  4. Egyébként, ha B 1 változó, akkor az egyesítés sikeres a B1 = A1 behelyettesítéssel.
  5. Ha A1 és B1 azonos nevű és argumentumszámú összetett kifejezések, akkor rekurzívan meghívjuk az egyesítési algoritmust A1 és B1 argumentumainak sorozatára. Egyesítésük akkor és csak akkor sikeres, ha az argumentum-sorozatok egyesítése sikerül.
  6. Minden más esetben az egyesítés meghiúsul.

Megjegyzés: az egyesítés fogalmának tételbizonyításbeli definíciója szerint, valahányszor egy X = Y behelyettesítést hajtunk végre, ellenőrizni kell, hogy az X változó előfordul-e az Y kifejezés belsejében. Ez az ún. előfordulás-ellenőrzés (occurs check)). Ha az előfordulás-ellenőrzés sikeres, akkor, az egyesítésnek elvben meg kell hiúsulnia. Hatékonysági okokból a legtöbb Prolog elhagyja ezt a vizsgálatot.

Vezérlőszerkezetek, vezérlésmódosítás

Vezérlőszerkezetek

A tiszta Prologban procedurális értelemben vett vezérlési szerkezetek nem találhatók meg, ám adhatunk logikai programozásbeli interpretációt mindegyikre.

A modern Prolog segítséget nyújt a procedurális vezérlőszerkezetek megvalósításában előre definiált operátorok, predikátumok segítségével.

A hagyományos értelemben vett eljárásfogalom sem ismert, itt igazából az egyes predikátumok illesztése jelenti egy-egy "alprogram" hívását. Visszatérési érték fogalma sem ismert, a predikátum egyes argumentumai lehetnek az alábbiak:

Vezérlésmódosítás

A tiszta Prolog nyelvben nem tudunk megfogalmazni tagadást, pedig sok esetben szükségünk lehet rá. Például, hogy két term nem illeszthető (A/=B), nem tudjuk megfogalmazni, csak azt, hogy illeszthető-e (A=B), azaz negatív információt nem tudunk kikövetkeztetni programunkből, legfeljebb azt, hogy egy adott állítás következik-e belőle.

Azonban, ha feltehető, hogy egy állítás akkor igaz, ha következik a programból, azaz, ha bizonyítható, akkor egy állítás negáltja akkor igaz, ha nem bizonyítható. Ha ekkor rendelkezni tudnánk arról, hogy mi történjen egy sikeres, ill. sikertelen célsorozat esetén, eszközt kaphatnánk a tagadás megvalósítására.

repeat/0 - a ciklus

Mint említettük, a ciklust kétféleképp is megvalósíthatunk. Az egyik megoldás a rekurzió, amit a nyelv alapban támogat. Második lehetőségünk egy kis trükk bevonásával egy repeat-until formájú ciklust kapunk azzal a megkötéssel, hogy a ciklusmag két lefutása között minden változó érvényét veszti. A trükk lényege az alábbi repeat predikátum-deklaráció, és a vágó (!) utasítás.

repeat. repeat :- repeat.

A repeat mindig igaz, de használata választási pontot illeszt a keresési fába. Egy meghiúsult cél utáni visszalépéskor az újabb választási ponton a Prolog ugyan azt a célsorozatot hajtja végre, és ez így ismétlődik, míg világ a világ - vagy ha le nem vágjuk a további választási pontokat.

Míg a rekurzió mindenre jó, néha az erőforrásokra tekintettel célszerűbb a repeat ciklust használni. Az egyik ilyen terület lehet a Generate and Test megoldáskeresés, hiszen itt nem kell megtartanunk minden téves eredményt, elég csak azt biztosítanunk, hogy a ciklusmag determinisztikusan működik és előbb vagy utóbb minden megoldást előállít. Így, ha létezik megoldás, programunk azt biztosan megtalálja, és sikeresen fejezi be futását. Ezt a megoldást mindig dinamikus predikátumokkal együtt használjuk, hogy tudjuk, hol tartunk és feljegyezzük az eddigi részeredményeinket. A repeat-tel nagyrészt azonban felhasználói felületeket hozunk létre, melyek sémáját az alábbi két példa is követi.

getval(X) :- repeat, write('Please enter a number:\n'), catch(getnat(X),S,(write(S),fail)), !. hanoi :- repeat, getval(X), ( hanoi(X,Sl) -> write(Sl),ln ; write('There is no solution.\n') ), wantexit, !.

Az első példában úgy olvasunk be egy egész számot (getnat/1), hogy közben figyelünk az esetleges kivételekre is, így, ha esetleg valami baj történne, és kivételt kapnánk (ld: 15. fejezet), akkor sincs semmi baj, hiszen a ciklus újból lefut, és ezt addig ismétli, míg minden simán nem megy. A második példában föl is használjuk a számbeolvasónkat, és a következő pontban tárgyalt elágazási sémát is, hogy csupán akkor lépjünk ki, ha nemvárt esemény történik, illetve ha azt a felhasználó úgy kívánja (wantexit/0). Ekkor, mivel már csak a vágó utasítás van hátra, hogy a cél sikeres legyen, a Prolog végrehajtja, és minden további (mostmár fölösleges) választási pontot levág.

Feltételes célok - az elágazás

A feltételes célok az egyik legfontosabb vezérlésmódosító eszköz. Segítségével elágazásokat hozhatunk létre, akár csak Formája: 

( if -> then
; else
)

Az if, a then és az else tetszőleges Prolog célsorozatok lehetnek. Ha az if célsorozat sikeres, a then célsorozat kerül végrehajtásra, és ennek megoldásai adják a megoldást, különben az else kerül végrehajtásra és rendelkezik az eredmény felől.

A feltételes célok egymásba is ágyazhatók:

  ( if1 -> then1
  ; if2 -> then2
  ; else
  )

Ezen túl a következő speciális megoldások is megengedettek:

  ( if -> then )

vagy

  ( if -> then
  ; fail
  )

esetleg

  ( if -> then
  ; true
  )

A fail és a true beépített eljárások, melyek hívása mindig meghiúsul, ill. sikeres. Az első két speciális megoldás tulajdonképpen egyenértékű, mivel az elsőnek nincs else ága, így ott megoldások sincsenek, ugyanúgy, mintha fail állna ott. Ezek után a bevezetőben említett problémát (hogy két term nem illeszthető) már könnyedén meg tudjuk oldani:

% A/=B :- A nem illeszthető B-vel A/=B :- ( A = B -> fail ; true ).

Ez alapján már csak egy kis lépés az általánosításban, hogy feltételes célok felhasználásával a tagadás közös sémáját megfogalmazhassuk. A tagadás e formája meta-predikátumnak tekinthető a Prologban. A meta-predikátum olyan predikátum, melynek formális paramétere a szabálytörzsben is megjelenő metacél (itt: P). Ekkor P-t meta-argumentumnak nevezzük. Ha P sikeres, esetleges választási pontjait a feltételes szerkezet levágja, majd az else ágon a true hajtódik végre és a hívás sikeres lesz. 

not(P) :-
    ( P -> fail
    ;true
    ).

például:

nőtlen_hallgató(X) :- hallgató(X), not(nős(X)).

Figyelembe kell vennünk azonban, hogy a tagadás ilyen megfogalmazása nem igazi logikai tagadás. Ez könnyen belátható, ha végiggondoljuk, hogy a not(P) pontosan akkor sikeres, ha a P cél meghiúsul (azaz P-nek egyetlen megoldása sem adódik). Valójában a zárt világ feltételezést vesszük alapul, mikor így tagadunk. Általában igaz, hogy a Prolog tagadás logikai értelemben vett helyességének elégséges feltétele, hogy a negált cél a meghívás pillanatában ne tartalmazzon változót, és keresési fája véges legyen.