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.
Áttekinté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 például 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 (például adott literálkiválasztó stratégia alkalmazása egy másikhoz képest adott program esetén kedvezőtlen hatással lehet a végeredményre, például végtelen ciklusba eshet a program).
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.
A Prolog működése
A programnak (szoftvernek) meg kell adnunk egy célformulát (célklózt), ezután 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 .
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 (például 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-as é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.
Szintaxis Term és funktor 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).
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.
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ól ké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.
Egyszerű termek
Az egyszerű vagy atomi termek a következő félék lehetnek:
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 darab í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 (Például '+' 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'
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
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.
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 t1, t2,...,tn 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: Létezik az üres lista (melynek egy eleme sincs), melyet többnyire a nil vagy [] atom szokott jelezni. 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: Művelet Leírás 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
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 karaktersorozatokként írhatunk le. A füzéreket többnyire az egyes karakterek listájaként ábrázolják a futtatókörnyezetek.
Ö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