Prolog programozási nyelv

A Wikipédiából, a szabad lexikonból.

A Prolog egy programozási nyelv, melyet Alain Colmerauer fejlesztett ki 1972-ben, a Prolog név a francia eredetű programmation en logique (logikai programozás) kifejezés rövidítése. Az első logikai programozási nyelvnek tekinthető. A Prolog egy megadott logikai formuláról (célformula) képes eldönteni, hogy logikai következménye-e formulák egy adott halmazának. Utóbbi formulák és a célformula a program bemenete, a kimenet pedig a válasz, hogy következik-e a célformula a többi formulából.

Röviddel Colmauer után Szeredi Péter is kifejlesztett egy Prolog interpretert Magyarországon.

Tartalomjegyzék 1 Áttekintés 1.1 A Prolog mint logikai gép 1.2 A Prolog mint programozási nyelv 1.3 A Prolog működése 1.4 A Prolog alkalmazásai 2 Szintaxis 2.1 Term és funktor 2.1.1 Term és típus 2.1.2 Funktor 2.1.3 Egyszerű és összetett term 2.2 Egyszerű termek 2.2.1 Atom 2.2.2 Szám 2.2.3 Változó 2.2.4 Lista 2.2.5 Füzér (string) 2.3 Összetett termek (klózok) 2.3.1 Tények 2.3.2 Szabályok 2.4 További beépített parancsok 2.4.1 Metapredikátumok 2.4.2 Interpreter vezérlőparancsok 2.4.3 Interface parancsok 3 Az interpreter működése - a LUSH-eljáráscsalád 3.1 A LUSH/BEL, azaz SLD-stratégia algoritmusa 3.1.1 Az algoritmus leírása 3.1.2 Rezolúció a Prologban 3.1.3 Visszalépés 3.1.4 Példa: családfakutatás 3.2 A levezetésgráf 3.3 Vágás 4 Szemantika 4.1 A negációkezelés 5 Példák 5.1 Helló, világ! 6 Prolog rendszerek 7 Hivatkozások 7.1 Külső hivatkozások 7.1.1 Áttekintés 7.1.2 Szakmai és matematikai részletek 7.2 Irodalom

[szerkesztés] Áttekintés

[szerkesztés] A Prolog mint logikai gép

A Prolog eredetileg (és a szakma úgy tartja, ma is) egyszerű felépítésű és könnyen használható nyelv volt; célközönségét kezdetben az „informatikában járatlan nyelvészek” képezték. A szintaxis és szemantika leginkább a matematikai logika egy ágának, az elsőrendű logikának a szimbólum- és gondolatvilágára épül: a Prolog nyelv kifejezései általában elsőrendű logikai kifejezéseknek feleltethetőek meg. A Prolog azonban nem az elsőrendű logika számítógépes megvalósítása, azzal csak átfedésben van.

• Egyrészt nem képes az egész elsőrendű logika rendszerének és eredményeinek kezelésére, csak annak egy részét, a Horn-logikát képes visszaadni különféle okok ^{(1., 2.)} miatt;
• másrészt a logikai negációt és az univerzális kvantifikációt sem képes teljes mértékben, szemantikailag hűen kezelni; nincsenek erre szolgáló beépített eszközei;
• viszont bizonyos eszközei (elsősorban az (ön)rekurzív predikátum-definíciók, a dinamikus klózok és az olyan beépített algoritmusok, mint a vágás alkalmazása) révén meg túl is szárnyalja az elsőrendű logikát, az ún. fixpontlogika területére vezetve a gyanútlan felhasználót.

Ezek a jellemzők szükségképp leszűkítik a Prolog alkalmazhatóságát a nem-algoritmizált, elméleti matematikai levezetőrendszerekkel szemben. A korlátok egy része szintaktikai vagy deklaratív jellegű; tehát a lineáris inputrezolúcióra és a Horn-klózokra vonatkozó szintaktikai megkötés okozza őket (emiatt pl. nincs beépítve a negáció, a logikai ekvivalencia és az univerzális kvantifikáció kezelése, bár kreatív módon alkalmazva egyes lehetőségeket, e korlátok bizonyos mértékben csökkenthetőek, tágíthatóak). A korlátok egy másik része már szemantikai jellegű, ide tartoznak a programot működtető eljárás algoritmizálásából adódó, a program beállításában megnyilvánuló ún. procedurális korlátok (pl. adott literálkiválassztó stratégia alkalmazása egy másikhoz képest adott program esetén kedvezőtlen hatással lehet a végeredményre, pl. végtelen ciklusba eshet a program).

[szerkesztés] A Prolog mint programozási nyelv

Az informatikában használt nyelvosztályzás szerint a Prolog deklaratív (nem imperatív, nem procedurális) nyelv. Ez azt jelenti, hogy a programozónak azt kell leírnia, hogy a megadott adatokból mit kellene kiszámítani (és a Program azt jelzi vissza, lehetséges-e ez); és nem azt az algoritmust, hogy az adatokból hogyan kellene kiszámítani valamit.

Ezen kívül sem eljárások, sem objektumok, sem adattípusok nem vagy nem olyan kifejezetten találhatóak benne, mint más nyelvekben (amikor ilyenekről beszélünk, az inkább metaforikus értelmű).

A Prolog nyelvének is megvan a maga jelkészlete, ábécéje, az ezekből képezett kifejezéseket (némileg pontatlanul) termeknek nevezzük. A Prolog forrásprogramok legtöbb sora egy olyan logikai kifejezés (formula, a Prolog-tudomány nyelvezetében összetett term - avagy (program)klóz); melyet a program alkalmazása során általában speciális implikációs formulának értelmezünk. Matematikailag, elméleti szempontból minden ilyen a kifejezést (programklózt) lehetséges és célszerű Horn-klóznak tekinteni. A Prolog verziók legtöbbje képes ezeken kívül numerikus és szöveges kifejezések kezelésére is, de a logikai (forrás)programok „lelkét” a programklózok alkotják; maga a logikai (forrás)program tehát felfogható úgy, mint egy rendezett elsőrendű klózhalmaz (illetve mint e halmaz klózaiból képezett egyetlen konjunktív normálforma). Bővebben ld. a szintaxis c. részt.

[szerkesztés] A Prolog működése

A programnak (szoftvernek) meg kell adnunk egy célformulát (célklózt), ezután a a program (szoftver) ellenőrzi, hogy a célklóz a logikai (forrás)program logikai következményei közt van-e. A döntési eljárás az elsőrendű logika egyik levezető módszere, a lineáris inputrezolúció, ennek algoritmizált számítógépes megvalósításait LUSH-nak (Linear (input)resolution with Unrestricted Selection function for Horn clauses; Lineáris (input)rezolúció Kötetlen (literál)kiválasztó eljárással Horn-klózokra) nevezzük. A LUSH egy egész eljáráscsalád, futtatás előtt a programozó adja meg, hogy milyen meghatározottabb beállításokkal (paraméterekkel) működjön; ennek hatására némileg módosul a futtatókörnyezet által végrehajtott algoritmus.

Ily módon tehát a Prolog az automatikus tételbizonyítás egy, fent említett korlátai ellenére a tapasztalatok szerint nagy számítóerejű megvalósítása. A további alapvető, működését leíró fogalmak az illesztőhelyettesítés (unifikáló helyettesítés, unifikáció, faktorizáció), a tail recursion és a visszalépés (backtracking).

Mindezekről bővebben lentebb .

[szerkesztés] A Prolog alkalmazásai

A Prologot gyakran használják mesterségesintelligencia-alkalmazások megvalósítására, illetve a számítógépes nyelvészet eszközeként (különös tekintettel a természetes nyelvfeldolgozásra, melyre eredetileg tervezték). A kutatások egyik fontos támogatója és gerjesztője volt az a tény, hogy a Prolog-variánsokat (pl. a Kernel Nyelvet) operációs rendszerként használó számítógépek előállítására, az ún. Ötödik Generációs Számítógéprendszer-Projektre az 1980-s években elég nagy hangsúlyt fektettek (elsősorban japán kezdeményezésre), bár mára az eredeti kutatás szinte teljesen leállt. Manapság a fő kutatási terület a nyelv felhasználása adatbáziskezelő programként.

[szerkesztés] Szintaxis

[szerkesztés] Term és funktor

[szerkesztés] Term és típus

A Prolog nem alkalmaz a hagyományos informatikai értelemben „adattípusokat” úgy, ahogyan az más programnyelvekben szokásos. Ehelyett inkább „lexikai elemekről” beszélhetünk. A Prologban mind az adatokat, mind a végrehajtandó programot termek (ti. kifejezés, terminus) formájában írjuk le. Ez a nyelv egyetlen, összetett adatokat megjeleníteni képes struktúrája. Ezek tekintendőek a Prolog programozási nyelv szavainak.

Egy összetettebb Prolog kifejezés egy névből, és a névhez rendelt adott számú egyszerűbb kifejezésből, argumentumból áll (az argumentumok újabb Prolog kifejezések).

[szerkesztés] Funktor

A kifejezés nevéből és argumentumszámából képezett rendezett pár a kifejezés funktora. Hogy egy adott kifejezést adatként vagy végrehajtandó programként kezel-e a futtatókörnyezet, csupán attól függ, hogy milyen kontextusban szerepel. Ez a rugalmasság lehetővé teszi, hogy egy Prolog programból magát a programot dinamikusan, futás közben módosítsuk.

[szerkesztés] Egyszerű és összetett term

A termek tehát a Prolog nyelvének szabályosan képzett, értelmesnek (a program interpretere által értelmezhetőnek) tekinthető, a nyelv szintaktikája alapján jólképzett kifejezései.

• Lehetnek egyszerű termek, melyek a legkisebb értelmes kifejezések (ezek részeit a Prolog nem érti, de magát a kifejezést már igen).
• A termek lehetnek összetett termek is, melyek végső soron az egyszerű termekből (közvetve esetleg más összetett termekből) épülnek fel.

[szerkesztés] Egyszerű termek

Az egyszerű vagy atomi termek a következő félék lehetnek:

[szerkesztés] Atom

Az atomok szövegkonstansok: betűk, számok, egyéb írásjelek sorozatai, kezdőbetűjük mindig kisbetű (sohasem nagybetű vagy aláhúzásjel, mert ezekkel a változók nevei kezdődnek) . Az egy hosszúságú atomok (1 db. írásjelből állóak) neve, mint minden programozási nyelvben, itt is karakter.

Tetszőleges karakterekből (a szóközt is beleértve) létrehozható atom, ha aposztrófokkal zárjuk közre (Pl. '+' atom, míg + egy beépített aritmetikai operátor; 'X' egy atom, de X egy változó). Az atomokat - az aposztrófok között megadottak kivételével - szóközök határolják, így ha atomként szóközjelet akarunk megjeleníteni, akkor egy másik jellel kell jelölni (általában _ jellel).

Példák atomokra:

atom másik_atom 'Minden aposztrófok közti karaktersor is atom' ' ' '+' 'X' '3'

[szerkesztés] Szám

A számokon belül a legtöbb Prolog nyelvjárás megkülönbözteti ugyan a lebegőpontos és az egész számokat, azonban mivel a Prolog nem erősen típusos programozási nyelv, a két ábrázolásmód felcserélhető és keverhető az aritmetikai kifejezésekben. Számos Prolog változatban az egész számok méretére nincs is felső korlát. Az ilyen egészszám-ábrázolás szokásos neve bignum (az angol „big numbers”, azaz „nagy számok” kifejezésből). Példák:

12 34.45 1e-12 5934875492834759384573451234987653

[szerkesztés] Változó

A változó nagybetűvel (vagy aláhúzásjellel) kezdődő, alfanumerikus karakterből és a _ aláhúzásjelből felépíthető stringekkel jelölt „adattípus”. Az imperatív programozási paradigmájú nyelvektől eltérően, a Prolog környezetben a változóknak csak egyszer tudunk a program élete során értéket adni. Nevezetes még a névtelen változó (ld. lentebb), egy „bármilyen változót” jelenthető joker-karakter, amit egyetlen aláhúzásjel (_) jelöl. Ennek a változónak minden előfordulása, új, ún. friss változót vezet be a programban. Akkor használatos, amikor az adott változó értékére nem vagyunk kíváncsiak; ilyenkor megspórolható egy változónév kigondolása, és helytakarékosabb is. Példák:

X Yb0_1a _idiamin4 _

Ha egy Prolog változó egy eljárás lefutása során „értéket kapott” (ez az unifikáló illesztés végrehajtása során történik), akkor - amíg visszalépés nem történik - a változó értéke megmarad. Ebben eltérés mutatkozik az imperatív programnyelvektől, és így a Prolog változó a matematikai „ismeretlen” fogalmához áll közel.

[szerkesztés] Lista

Termek és típus véges sorozatát listának (list) nevezzük. A listák jelölése általában

[t1, t2, ... , tn]

alakban történhet (általános alak), ahol   t₁, t₂,...,t_n   a lista elemei.

A Prolog lista nem önálló adattípus, hanem '.'/2 funktorú kifejezések láncolt listája, ahol a funktor első argumentuma mindig a lista fejét, azaz első elemét, a második pedig a lista farkát, azaz az eggyel rövidebb listát jelenti. Tehát például az

[1, 2, 3]

alakú lista valójában az

'.'(1, '.'(2, '.'(3, [])))

láncolt listát jelenti.

A listákat ezért általános alakjuk helyett a következő rekurzióval is megadhatjuk:

1. Létezik az üres lista (melynek egy eleme sincs), melyet többnyire a nil vagy [] atom szokott jelezni.
2. ha T lista és H term, akkor [H|T]-vel jelöljük a H termet első elemként tartalmazó azon listát, melynek többi elemei rendre a T elemei. Ennek megfelelően az első, H elem neve a lista feje, a régebbi T lista pedig a bővített lista farka. Ez a jelölés a '.'(H, T) belső felépítésű Prolog listát takarja.

Ezen kívül még több lehetőségünk is van listák építésére és kezelésére:

• Elemek felsorolása: [abc, 1, f(x), Y, g(A,rst)]
• Egy elem hozzáadása: [abc | L1]
• Több elem hozzáadása: [abc, 1, f(x) | L2]
• Termkiterjesztés: '.'(abc, '.'(1, '.'(f(x), '.'(Y, '.'(g(A,rst), [])))))

A legtöbb Prolog fordító tartalmaz beépített listakezelő műveleteket:

member	elem keresése listában
del	elem törlése listából
length	listahossz megadása
last	utolsó listaelem meghatározása
conc	listák egyesítése (konkatenáció)
cikl	különféle ciklusszervezési lehetőségek

[szerkesztés] Füzér (string)

A legtöbb Prolog megvalósításban használhatunk füzéreket, amelyeket kettős idézőjelek közé írt karatkersorozatokként írhatunk le. A füzéreket többnyire az egyes karakterek listájaként ábrázolják a futtatókörnyezetek.

[szerkesztés] Összetett termek (klózok)

Az összetett termek, avagy programklózok atomi termekből mint argumentumokból képezett, szintaktikailag implikációs vagy annak tekinthető kifejezések, melyeket az interpreter logikailag mint Horn-klózokat kezel.

Programklóznak általában az

A :- B1, B2, ... , Bn

alakú kifejezéseket nevezzük, ahol   A és B₁, B₂, ... , B_n   egyszerű termek. Amint a Horn-klóz cikkben írva van, logikai szempontból ezt a kifejezést a következő normálforma alakú kifejezésre fordíthatjuk le:

  A∨¬B1∨¬B2∨...∨¬Bn     (*)

A Prologban három eset képzelhető el:

1. Az A „üres” atom (azaz a :- jel bal oldalára nem írunk semmit sem), tehát a (*) formula valamennyi atomja negált. Ekkor a klóz a célklóz.
2. A nem üres, de n=0, azaz a :- jel jobb oldalán semmi sem áll, tehát a klóz egyetlen negálatlan állításból, „atomi tényből” áll. Ilyenkor magát a :- implikációjelet sem írjuk ki. Az ilyen klózok a tények.
3. Sem A nem üres, sem pedig az n nem nulla, tehát a :- jel mindkét oldalán áll atom (és bal oldalán egyetlen egy atom), azaz a (*) formula tartalmaz pontosan egy negálatlan és legalább egy negált atomot. Ezek a klózok a definit klózok, vagy szabályok.

A programklózoknak tehát, a célklózon kívül, két fő fajtája a tények, illetve a szabályok .

[szerkesztés] Tények

A tények (facts)

atom(a1,a2,...,an)

alakú, egy fejnek nevezett atomból és valahány argumentumból álló kifejezések. Az argumentumok többféle típusúak lehetnek. A kifejezés nevéből és az aritásából álló megjelölést (rendezett párt) a kifejezés funktorának nevezzük.

A „fej” atomot általában mint predikátumnevet szokás értelmezni, tehát például az

barát(dani,tomi)

alakú tény azt fejezné ki, hogy a „dani” atommal és a „tomi” atommal jelölt egyedek „barát”-ok (természetesen ez az értelmezésmód nem kötelező, bonyolultabb programokban sokszor inkább jelentés nélküli, egy-két betűs predikátumneveket használnak; csupán hozzájárul a program jobb érthetőségéhez).

Ennélfogva lehetséges, hogy több ténynek is azonos atom legyen a feje, mint pl. az a következő hat darab tény némelyikében látható:

barát(dani,tomi) barát(ági,jani) kutya(blöki) kutya(dodi) barát(blöki,tomi) barát(blöki,dodi)

Egy adott logikai (forrás)programban az összes tény halmazát néha szokás az adott program adatbázisának nevezni.

[szerkesztés] Szabályok

A szabályok (rules) - melyek logikai kifejezésként Horn-klózok - szintént összetett termek, funktoruk ':-'/2, ahol a fejet és a törzset a :- operátor választja el egymástól. A törzset alkotó, veszsővel elválasztott, illetve a fejet alkotó egyszerű kifejezést a szabály literáljainak is nevezzük. A tényállításokat alkotó egyszerű kifejezések is literálok, egy tény tehát egyetlen literálból áll.

Példák szabályokra:

névfej(1,atom,X) :- nevtorzs1(uj,uj), nevtorzs2(x,Y,z) , ... , stb kif(beágyazott(0),arg)

Nagyjából itt is elmondható, ami a tények esetében, tehát hogy legegyszerűbb esetben a szabályokat mint állításokat, predikátumokat értelmezzük. Pl.

nagyapja(X,Y) :- apja(X,Z),apja(Z,Y) n(X,Y) :- a(X,Z),a(Z,Y)

A legegyszerűbb e klózokat tehát úgy kiolvasni, hogy „Ha valaki (X) apja a fiának (Y) és a fiú is apja az unokának (Z), akkor ezt a valakit (X-et) az unoka (Z) nagyapjának nevezzük”. Tehát ez bizonyos értelemben a „nagyapja(... , ...)” predikátum „definíciója” - ez magyarázza a „definit” jelzőt a „definit programklóz” kifejezésben (a hagyományos, köznapi és matematikai logikával szemben az a különbség, hogy a Prologban nincs beépített eszköz a „csak akkor” reláció ábzáolására, tehát ezt más módon kell megoldani). Természetesen a fenti klózoknak másféle predikátumot is tekinthetünk az értelmezésének, a megoldandó problémától és a programozó szándékaitól függően.

A Prologban egy eljárás (szokás partíciónak is nevezni) olyan klózok összessége, amelyek feje és argumentumszáma (azaz melyek funktora) megegyezik. Lehetséges azonos nevű, de különböző argumentumszámú eljárások definiálása.

[szerkesztés] További beépített parancsok

[szerkesztés] Metapredikátumok

Ezen predikátumok segítségével a felhasználó képes a Prolog termek osztályzására, és így a Prolog nyelv metanyelvét képezik:

var(X)	X változó
nonvar(X)	X nem változó
atomic(X)	X konstans
compound(X)	X összetett kifejezés (struktúra)
atom(X)	X egyszerű kifejezés (atom)
number(X)	X szám
integer(X)	X egész („típusú”) számérték
float(X)	X lebegőpontosan ábrázolt szám

[szerkesztés] Interpreter vezérlőparancsok

• A fail (kudarc) parancs, melyet az összetett termekbe mint literált lehet beírni, az SLD-algoritmus visszalépését vezérli a levezetésgráfban. Hasonló a mindig igaznak számító true predikátum.
• A cut (vágás) parancs hatására a levezetésgráf bizonyos ágain az SLD-algoritmus nem megy végig. Ez is a visszalépések szabályzása útján hat.

[szerkesztés] Interface parancsok

A futtatott program és a környezet (felhasználó, perifériák, számítógép) közti kommunikációt segítik.

• write - szöveg kiírása a képernyőre. Használata: write(atom), ahol az atom betűsor helyére valamilyen atom helyettesíthető. Ld. még a példákat.

[szerkesztés] Az interpreter működése - a LUSH-eljáráscsalád

A LUSH betűszó feloldása: Linear (input)resolution with Unrestricted Selection function for Horn clauses, azaz kb.„Lineáris rezolúció Több (literál)kiválasztási eljárással Horn-klózokra”. Ez azt jelenti, hogy az interpreter a program klózain, melyek Horn-klózok, lineáris (input)rezolúciót hajt végre, amely nem determinisztikus eljárás, hanem minden lépésben esetleg több literál közül egyet választ ki, és hogy milyen szabály (azaz literálkiválasztási eljárás) szerint, azt a felhasználó állíthatja be a program futtatásakor. Tehát önmagában a LUSH eljárás, minthogy indeterminisztikus, nem egy algoritmus. A literálkiválasztó stratégia rögzítésével viszont az lesz.

A Prologban legtöbbször használt literálválasztó stratégia a Robert Kowalski által kidolgozott ún. SLD-stratégia, amelynek során a rezolválandó mellékklózból a program mindig a klóz legbalra eső alkalmas (kirezolválható) literálját választja ki (ha van ilyen, ha nincs, akkor a program egy másik mellékklózt választ, ha pedig nincs, akkor kudarc jelzésével véget ér a futása). Ezt magyarítva terminológiában BEL-stratégiának (balról az első literál) nevezhetnénk. Haználható még a JEL-stratégia is (jobbról az első literál), de ez végtelen futásba viheti a programot (az újabb Prolog verziókban ezt a problémát általában már kiküszöbölik). Mivel az SLD-algoritmus nem képes a negáció kezelésére, ezt több negációkezelő stratégiával egészítették ki. Lásd negációkezelés.

[szerkesztés] A LUSH/BEL, azaz SLD-stratégia algoritmusa

[szerkesztés] Az algoritmus leírása

E ciklikus algoritmus a lineáris inputrezolúció egy megvalósítása. Bármely ciklusa végrehajtásakor, az ún. visszalépések végrehajthatósága miatt, szükség van az előző lépések során végrehajtott lépésekről (gyakorlatilag az összes előforduló központi klózról és mellékklózról) való információ tárolására .

1. Kezdetben az aktuális célklóz a program eredeti célklóza.
2. Ha az aktuális célklóz az üres klóz, akkor pozitív eredménnyel vége a programnak: rezolúciós cáfolatot kaptunk, a célklóz következménye a program többi klózának. Ekkor a 6. lépés következik, egyébként (ha nem üres klóz az aktuális) a következő, azaz 3. lépés.
3. Az aktuális célklózból kiválasztja balról az első literált, ez az aktuális literál.
4. Ha van olyan partíció, amely az aktuális literállal kezdődik, akkor e partíció legelső (az előző lépések során még ki nem választott) klózát kiválasztjuk. Ha nincs ilyen partíció, vagy ennek már nincs kiválasztható klóza, akkor a 6. lépés következik, egyébként az 5. lépés.
5. Illesztjük a kiválasztott partíció kiválasztott klózát az aktuális klózzal és képezzük az így kapott két klóz elsőrendű (más néven bináris) rezolvansét. Ez lesz az új aktuális célklóz, és visszalépünk a 2. lépésre. Egyébként (ha az illesztés vagy a rezolúció nem hajtható végre), a választás "kudarcos"-nak minősül, és visszalépünk a 4. lépéshez.
6. Ha az aktuális célklóz az eredeti célklóz, az algoritmusnak vége. Egyébként pedig a jelenlegi aktuális célklóz törlődik, és az azt megelőző aktuális célklóz lesz újra az aktuális célklóz. Ekkor pedig visszalépünk a 3. lépésbe.

Ez az algoritmus a levezetésgráf (lentebb) „mélységben először” bejárási stratégiájának felel meg.

[szerkesztés] Rezolúció a Prologban

A program mindig, minden lépésben a

 :- C₁,C₂,...,C_n

alakú aktuális célklózt rezolválja valamely

A :- B₁,B₂,...,B_m

alakú programklózzal (illetve esetleg egy programklóz ún. alapelőfordulásával, ami azt jelenti, hogy a klóz néhány változóiba a programban előforduló konstansok lettek helyettesítve. Ilyen helyettesítések az ún. illesztés avagy faktorizálás során következik be ).

[szerkesztés] Visszalépés

[szerkesztés] Példa: családfakutatás

Szemléltetes, köznapi formában adott a következő szabály: „Ha valaki apja másvalakinek, és e másvalaki is apja még valakinek, akkor az elsőként említett valaki nagyapja a harmadikként említett mégvalakinek.” Álljon egy program ebből a szabályból, és egy családfarészletet leíró adatbázisból, mely családban egy István nevű ősnek két fia van, Dániel és Nándor, Dánielnek pedig van még egy fia, István2. Le tudja-e vezetni a Prolog, hogy István nagyapja Péternek?

Program „Családfa” nagyapja(X,Y) :- apja(X,Z),apja(Z,Y). apja(istván, dániel). apja(istván, nándor). apja(dániel,istván2). apja(nándor,péter). Cél:  :- nagyapja(istván,péter)

A programkonstansok most keresztnevek, de a helyesírási konvenciótól eltérően nem írhatjuk őket nagybetűvel, hisz akkor változókat jelentenének.

Nyilvánvaló, hogy érvényes nagyapja(istván,péter). A program - SLD-stratégia beállítása esetén - a következő lépéseket fogja végrehajtani az első sikeres levezetésig: adjuk meg neki célklózként a levezetendő állítás negáltját, azaz a  :- nagyapja(istván,péter). predikátumot (emlékeztetünk: ha a :- jel bal oldalán áll egy literál, az jelenti a literál tagadását).

A program indulásakor az aktuális célklóz az eredetileg megadott,  :- nagyapja(istván,péter). A Prolog generál egy új aktuális célklózt úgy, hogy megkeresi a programban mint klózlistában az első olyan klózt, ami az aktuális célklóz bal első literáljával rezolválható. Az aktuális célklóz nem üres, ezért a programklózok között felülről lefelé haladva megkeressük azt a partíciót, amely az aktuális célklóz balról az első literáljának fejével kezdődik, tehát keresgélünk az nagyapja/2 funktorú predikátumok közt. Tehát a „nagyapa” fejjel rendelkező predikátumokból álló partíció legelső (még fel nem dolgozott, azaz az aktuális célklózzal rezolválni még nem próbált) elemét választjuk ki, ez lesz az aktuális mellékklóz. Az első (és egyetlen) ilyen predikátum a megfelelő partícióban: nagyapja(X,Y) :- apja(X,Z),apja(Z,Y). . Ezt választjuk ki, és ezzel próbáljuk az aktuális célklózt rezolválni. Mivel ez változókat tartalmaz, ha van az akutális célklózban olyan változóhely, mely konstanssal van behelyettesÍtve, akkor a mellékklózban is behelyettesítjük a megfelelő változókat. Ez az illesztés (unifikáció, faktorizáció etc.) Ennek eredményeképp (X helyébe "istván", Y helyébe "péter" kerül) kapjuk a nagyapja(istván,péter) :- apja(istván,Z),apja(Z,péter). mellékklózt. Képezzük az elsőrendű rezolvenst. Ez nem más, mint  :-  apja(istván,Z),apja(Z,péter). . Ez lesz az új aktuális célklóz. Most végrehajtjuk az eddigi lépéseket újra ezzel a célklózzal.

Az eddigi és további lépések táblázat formájában:

1.	2.	3.	4.	5.	6.	7.
lépés	aktuális célklóz	mellék- klóz	illeszt- hető	illesztés	rezol- vendusok	rezolvens
1.	2.	3.	4.	5.	6.	7.

Kiválasztjuk a bal első literálját: apja(istván, Z).

1. Az aktuális célklóz nem üres, tehát nem vagyunk készen. Bal első literálja apja(..., ...), tehát az „apja” partícióban keresgélünk mellékklóz után.
   1. A legelső klóz az apja/2 partícióban apja(istván, dániel). . Ez lesz az új mellékklóz.
   2. Illesztünk: Z := dániel, tehát a célklóz apja  :- apja(istván,dániel),apja(dániel,péter). alapformáját rezolváljuk az apja(istván, dániel). alapformulával. Az eredmény:  :- apja(dániel,péter). . Ez lesz az új aktuális célklóz.
2. Ez nem üres, tehát nem vagyunk kész. Kiválasztjuk a bal első literált, és keresgélünk a megfelelő funktorú partícióban.
   1. Az egyetlen klóz, amit elvileg illeszteni lehetne a fenti aktuális célklózzal, az a  :- apja(dániel,péter). célklóz negáltja, apja(dániel,péter). . Ez nem szerepel az adatbázisban (egyáltalán, a programban sem). Nincs az aktuális célklózzal illeszthető klóz. Ez azt jelenti, hogy az aktuális célklóz kudarcos, a program visszalép az előző aktuális célklózhoz, ami tehát

 :- apja(istván,Z),apja(Z,péter). .

1. Ez nem üres, tehát nem vagyunk készen. Bal első literálját kiválasztjuk. Ennek funktora apja/2 . Keresünk a célklózhoz még feldolgozatlan mellékklózt az "apja" fejű klózokból álló partícióban. Mivel a partíció legelső klózát már feldolgoztuk, kudarcos eredménnyel, most választjuk a második klózát, ez apja(istván, nándor). .
   1. Illesztünk: Z := nándor. Az illesztett klózok  :- apja(istván,nándor),apja(nándor,péter). és apja(istván, nándor). .
   2. Képezzük az illesztett klózok rezolvensét:  :- apja(nándor,péter). . Ez az új aktuális célklóz.
2. Ez nem üres. Bal első literáljához illeszthető klózt keresünk, ami tehát csak apja(nándor,péter). lehet.

[szerkesztés] A levezetésgráf

[szerkesztés] Vágás

[szerkesztés] Szemantika

A Prolog rekurzív logikai formulákat kezelni képes rendszer. Az ilyen rendszerek vizsgálatának leggyakoribb matematikai eszköze az ún. fixpontlogika.

A programnyelv-szemantika a programok mint egy programnyelv kifejezéseinek értelmezésével, a program jelentésének vizsgálatával foglalkozik. Ezen belül

• az első, a deklaratív szemantika vizsgálja, hogy a programot mint formulahalmazt értelmezve, milyen logikai következmények vonhatóak le belőle.
• a második, az eljárásszemantika (procedurális szemantika) vizsgálja, hogy a program mint algoritmikusan megvalósított kalkulus milyen (azaz pl. milyen korlátai vannak a lineáris inputrezolúciónak)
• a harmadik, a kiszámítási szemantika pedig, hogy a klóz- illetve literálsorrendnek milyen szerepe van a program futásában.

[szerkesztés] A negációkezelés

A Prolog célklóza szükségképp

 :- C1, C2 , ... , Cn

alakú, ami tudniillik olyan programklózt akar jelenteni, mely nem tartalmaz pozitív literált, vagyis a :- implikációjeltől balra eső, konklúzió szerepű literál az üres klóz (üres literál). Tehát logikai formulákkal a következő Horn-klózról van szó:

¬C1∨¬C2∨...∨¬Cn

A Prolog leíró nyelvében nem szerepel negáció, hiszen egy literál negációját úgy fejezzük ki, hogy amikor a formulát programklóz alakba írjuk, a :- jel jobb oldalára essen. A célklóz pedig attól célklóz, hogy a klóz minden literálja a jobb oldalán van. Tehát a Prolog csak olyan célklózok kezelésére képes, melyeknek nincs negálatlan, a :- jel bal oldalára eső literáljuk, és ezért nem képes az elsőrendű logika apparátusához hasonlóan kezelni tetszőleges formula negációját.

Az SLD-t a hetvenes években Robert Kowalski dolgozta ki. Mivel nem képes a negáció kezelésére, többen is továbbfejlesztették módszerét a negációkezelés valamilyen megoldására. Az első ilyen próbálkozás Clark SLDNF-módszere (SLD with negation as finite failure, kb. SLD-eljárás a negáció végesen kudarcos levezetésként való értelmezésével). Ezt ma is használják a Prologban. Meg kell jegyeznünk, hogy ez nemcsak hogy nem szemantikailag hű kezelése a negációnak, de bizonyos esetekben végtelen ciklusba is viheti a programot. Ezen kívül még rengeteg eljárást kidolgoztak és dolgoznak (SLS, SLT, CAW stb.), ezek közül még a CAW használatos leginkább a megvalósult Prolog verziókban.

A negációkezelésre két módszert szoktak beépíteni:

• A zárt világ feltételezés módszere (CWA, closed world assumption)
• A negáció mint kudarc módszer (NF, negation as failure).

[szerkesztés] Példák

[szerkesztés] Helló, világ!

A Helló, Világ!-program a következőképp fest a Prolog nyelven:

write('Helló, világ!'),nl.

[szerkesztés] Prolog rendszerek

• MProlog
• Quintus Prolog
• PDC Visual Prolog
• GNU Prolog

[szerkesztés] Hivatkozások

[szerkesztés] Külső hivatkozások

[szerkesztés] Áttekintés

• Prologika (Makány György írása a Sulinet oldalán
• Prolog fogalomtár
• Szabó Péter leírása a Prologról (PostScript)
• Példafeladatok Prologra, megoldással
• Interjú Szeredi Péterrel
• A logikai programozás története
• Prolog verziók egy jegyzéke
• Deklaratív programozás On-line jegyzetek és szakirodalom

[szerkesztés] Szakmai és matematikai részletek

(az alábbi linkek angol nyelvű PDF-dokumentumokra mutatnak)

• Alan Colmaeuer a Prolog történetéről (PDF)
• Hurokellenőrzési módszerek a Prolog számára (PDF)
• A Prolog (procedurális) szemantikája

[szerkesztés] Irodalom

• Pásztorné Varga Katalin – Várterész Magda: A matematikai logika alkalmazásszemléletű tárgyalása, Panem, Bp., 2003. ISBN 963-545-364-7
• Szeredi Péter - Benkő Tamás: Deklaratív programozás. Bevezetés a logikai programozásba. Oktatási segédlet, 2004.