Bevezető | |
Az első változat kelte | 1972 |
---|---|
Paradigma | Logikai programozás |
Szerző | Alain Colmerauer , Philippe Roussel |
Befolyásolta | Tervező ( be ) |
Fájlkiterjesztés | pl, pro és P |
Prolog egy nyelv a logikai programozás . A név Prolog egy betűszó az PROGRAMMATION a logika. Ez hozta létre Alain Colmerauer és Philippe Roussel körül 1972 a Luminy, Marseille. A cél egy olyan programozási nyelv létrehozása volt, amelyben meghatározták a megoldástól elvárt logikai szabályokat, és hagyta, hogy a fordító utasítássorozattá alakítsa át. A várt előnyök egyike az alkalmazások karbantartásának megkönnyítése, a szabályok hozzáadása vagy törlése volt az idő múlásával, amely nem igényelte az összes többi felülvizsgálatát.
A Prologot a mesterséges intelligenciában és a számítógépes nyelvi feldolgozásban (elsősorban a természetes nyelvekben ) használják. A szintaktikai szabályok és szemantika egyszerű és tisztának tekinthető (az egyik a kitűzött célok az volt, hogy egy eszköz nyelvészek tudatlan számítástechnika). Az első, a Prolog által elért eredmények egy ideig, az 1980-as években arra késztették a számítógépek ötödik generációjának, hardverének és szoftverének kutatását (a japán ötödik generációnak hívták, mivel a MITI fontos szerepet vállalt a projektben). A vállalt erőfeszítések fontosak voltak, a hatás szerényebb, a Prolog egy nyelv marad a többi között a programozó tartományában.
A Prolog az elsőrendű predikátumok kiszámításán alapul ; kezdeti változatában azonban csak a Horn-klauzulák elfogadására korlátozódik (a Prolog modern változatai bonyolultabb predikátumokat fogadnak el, különösen a negáció kudarcokkal történő kezelésével ). A Prolog program végrehajtása gyakorlatilag a bizonyító tétel alkalmazása elsőrendű felbontással. Az alapvető fogalmak az egyesítés , a rekurzió és a visszalépés . A Prolog felbontási algoritmusa az SLD felbontás kiterjesztésén alapul .
A Prologban meghatározhatatlan sorrendben tudunk felépíteni egy tudásbázist, mivel csak a jelenlétben lévő kapcsolatok számítanak, és nem az írásuk sorrendje. Ezután a Prolog képes megoldani egy ilyen tudásbázissal (deduktív adatbázis fogalma) kapcsolatos logikai problémák sorozatát , amely hasonló a megoldás (vagy több) kereséséhez a megállapított korlátok labirintusában.
A Prolog nem a programozási nyelvek szokásos értelmében használja az adatbevitelt . Valójában nem tesz valódi különbséget a program adatai és maga a program között (a deklaratív programozás és a funkcionális programozás elve ). Lexikai elemei, az úgynevezett kifejezések a következő típusokat ölelik fel.
Az állandó szövegek atomokat alkotnak . Az atom általában betűkből, számokból és aláhúzásokból ( _) áll, egy kisbetűvel kezdve . Ha nem alfanumerikus atomot akarunk bevezetni, vegyük körül aposztrófokkal: így a '+' atom, + operátor).
A Prolog jelenlegi megvalósításai nem tesznek különbséget egész számok és lebegők között.
A változók betűk, számok és aláhúzások segítségével kerülnek megadásra, és nagybetűvel kezdődnek .
Így az X3 mint Unit_Price az elfogadható változók neve.
A Prolog nem elengedhetetlen programozási nyelv ; a változó tehát nem olyan konténer, amelyhez értéket rendelünk, hanem a megszorítások keretein belül reprezentálja (mint a matematikában az X> 0 értéket ).
A változó eredetileg definiálatlan mezőjét a korlátok körüli egyesítés adja meg. Miután a változó egységes, annak értéke már nem módosítható ugyanazon értékelési ágon belül. A visszalépés azonban lehetővé teszi, hogy egy kimerítő feltárás keretében visszatérjen az egyesüléshez az elfogadható értékek (vagy új elfogadható értékek) keresésének részeként .
Az anonim változó aláhúzással (_) íródik . Bármely változó, amelynek neve aláhúzással kezdődik, szintén névtelen változó. Az algebra x-jéhez vagy y- jéhez hasonlóan ez a dummy változó, amely a számítás közvetítőjeként szolgál.
A Prolog csak összetett adatokat képviselhet összetett értelemben . Az összetett kifejezés egy fejből (más néven functorról ) áll, amelynek atomnak kell lennie, és paraméterekből, típuskorlátozás nélkül. A paraméterek száma, az úgynevezett kifejezés aritása azonban jelentős. Az összetett kifejezést a feje és arituma alapján azonosítják, és általában functor / aritásként írják.
Példák az összetett kifejezésekre:
A lista nem izolált adattípus, hanem rekurzív konstrukcióval definiálva (a .2. aritás funkcióját használva , tehát a belső reprezentáció szintjén összetett kifejezés):
Az első, fejnek nevezett elem H , majd a lista többi részének tartalma, amelyet T vagy farokként jelölünk . Az [1, 2, 3] listát belsőleg "." ( 1 , '. "( 2 ,'." ( 3 , []))) ábrázolnánk. A szintaxis rövidítése a [ H | T ], amelyet leginkább építési szabályokra használnak. A lista egésze feldolgozható az első elemre, majd a lista többi részére történő rekurzióval , mint a LISP-ben .
A programozó kényelme érdekében a listákat különféle módon lehet összeállítani és dekonstruálni.
A húrokat általában karakterek sorozataként írják, aposztrófok veszik körül. Gyakran belsőleg képviseli őket az ASCII kódok listája.
A Prolog programozása nagyon különbözik az imperatív nyelvű programozástól . A Prologban a tények és szabályok tudásbázisát tápláljuk ; akkor lehetőség van kérelmeket tenni a tudásbázisra.
A Prolog alapegysége az állítmány , amelyet igaznak definiálunk. Az állítmány egy fejből és számos argumentumból áll. Például :
chat(tom).Itt a „macska” a fej, és a „tom” az érv. Íme néhány egyszerű kérés, amelyet e tény alapján kérhet a Prolog tolmácsától:
?- chat(tom). oui. ?- chat(X). X = tom; fail.Ebben a második példában a „cat (X)” kérdésre az tolmács az „X = tom” választ javasolja, amely egyesíti az „X” változót a „tom” atomig. A Prologban ez siker . Az első válasz után a felhasználó megkérdezheti, hogy vannak-e más válaszok a "; »(A disszjunkció szimbóluma), itt a tolmács azt válaszolja, hogy nem talál ilyet. Ez a más megoldások keresése egy nem-determinisztikus végrehajtási modellen alapul (a nem-determinisztikus automaták nem-determinizmusának értelmében), a visszacsatolással a különböző választási pontokra és a feltáratlan alternatívák feltárására.
?- chat(vim). fail.Ebben az utolsó példában a „chat (vim)” kérdésre a tolmács azt válaszolja, hogy ezt a tényt nem tudja bizonyítani, a Prologban ez kudarc. Ha feltételezzük, hogy minden tény ismert (a zárt világ hipotézise ), ez azt jelenti, hogy a „vim” nem macska.
Az előrejelzéseket általában olyan tények kifejezésére definiálják, amelyeket a program ismer a világról. A legtöbb esetben az állítmányok használata némi egyezményt igényel. Például a következő két predikátum szemantikája nem azonnali:
pere(marie, pierre). pere(pierre, marie).Mindkét esetben az „apa” a fő, míg a „marie” és a „pierre” az érvek. Az első esetben azonban Mária az első az argumentumlistában, a második pedig Péter (az argumentumlista sorrendje számít). Az első eset az ige-tárgy-szubjektum sorrendjében definiálható példa, és olvasható a „volna” segédlettel: Marie apja Pierre-nek, a második pedig az ige-szubjektum-objektum és a kisegítő „lény”: Pierre Mary apja. Mivel a Prolog nem érti a természetes nyelvet, mindkét változat helyes, ami őt illeti; ugyanakkor fontos, hogy ugyanazon programhoz következetes programozási szabványokat fogadjanak el. Általában inkább a kisegítő „lényt” használják.
Például ebben egyetértünk
famille(pierre, marie, [arthur, bruno, charlotte]).azt jelenti, hogy pierre és marie 3 gyermek apja és anyja: arthur, bruno és charlotte; A "család" ekkor egy 3 tagú állítmány, az utolsó a gyermekek esetleges (esetleg nulla) számának felsorolása.
Egyes predikátumok beépülnek a nyelvbe, és lehetővé teszik a Prolog program számára, hogy rutinszerű tevékenységeket hajtson végre (például numerikus kiértékelés, bevitel / kimenet , GUI funkcionalitás és általában kommunikáció a számítógépes rendszerrel). Például az írási predikátum használható a képernyő megjelenítésére. Ebből kifolyólag
write('Bonjour').megjeleníti a „Hello” szót a monitoron. Szigorúan véve az ilyen állítmányok nem kapcsolódnak a logikai programozáshoz, funkcionalitásuk kizárólag mellékhatásaikon alapul.
A nyelvbe épített többi állítmány logikai jellegű, és szerepel a könyvtárakban . Ezeket a fejlesztés egyszerűsítésére használják az általános feldolgozás, például a listafeldolgozó algoritmusok beágyazásával.
Végül más predikátumok magasabb rendűek, és a Prolog tolmácsok végrehajtásának ellenőrzésére szolgálnak (például szabályok és tények dinamikus hozzáadása / eltávolítása, a választási pontok elhagyása, a lekérdezés eredményeinek összegyűjtése.)
NB- Az előre definiált predikátumok nélkül a Prologot néha Pure Prolog-nak hívják ( az angol szabvány szerint : definite Prolog).
A Prolog utasításainak második típusa a szabály. Példaszabály:
lumière(on) :- interrupteur(on).A ": -" jelentése "ha"; ez a szabály azt jelzi, hogy a fény (be) igaz, ha a bekapcsolás igaz. A szabályok olyan változókat is használhatnak, mint:
père(X,Y) :- parent(X,Y), mâle(X).azt jelenti, hogy X egy Y apja, ha X Y szülője és X férfi, ahol a "," kötőszót jelöl.
Ugyanez lehet:
parent(X, Y) :- père(X, Y) ; mère(X, Y).azt jelenti, hogy X jelentése Y szülője, ha X Y szülője, vagy X Y szülője, ahol a ";" alternatívát jelöl.
A tény a szabály speciális esete. A következő két sor valóban egyenértékű:
a. a :- true.Amikor a tolmács megkeresést kap, megkeresi azokat a szabályokat (beleértve a tényeket is), amelyek bal oldala egyesíthető a kéréssel, és ezt az egyesítést az első megtalált szabálysal hajtja végre. Például ezzel a Prolog kóddal:
frère_ou_sœur(X,Y) :- parent(Z,X), parent(Z,Y), X \= Y. parent(X,Y) :- père(X,Y). parent(X,Y) :- mère(X,Y). mère(trude, sally). père(tom, sally). père(tom, erica). père(mike, tom).Ennek eredményeként a következő kérést igaznak értékeljük:
?- frère_ou_sœur(sally, erica). oui.A tolmács ezt az eredményt úgy éri el, hogy a testvér_vagy_ nővér (X, Y) szabályt úgy illeszti össze, hogy X- et egyesíti a sally-val és Y-t az ericával . Ez azt jelenti, hogy a kérés kiterjeszthető szülőre (Z, sally) , szülőre (Z, erica) . Ennek az összefüggésnek a megfeleltetése úgy érhető el, hogy megnézzük Sally összes lehetséges szülőjét . A szülő (trude, sally) azonban nem vezet életképes megoldáshoz, mert ha a trude helyettesíti a Z-t , akkor a szülőnek (trude, erica) igaznak kell lennie, és nincs ilyen tény (vagy bármilyen szabály, amely ezt kielégítheti) ajándék. Ehelyett tom helyettesíti a Z-t , és az erica és a sally ennek ellenére testvérnek tűnnek .
Tiszta logikai tagadás a Prologban nem létezik, a kudarc negatívumára támaszkodunk , amelyet a Prolog megvalósításai szerint másképp jegyezünk meg (a jelölést kulcsszóval fogjuk elfogadni not(prédicat)). A kudarc negatívumában az állítmány tagadását akkor tekintjük igaznak, ha az állítmány értékelése kudarchoz vezet (nem ellenőrizhető).
A Prologban a kudarc nélküli negáció a zárt világ hipotézisén alapszik: minden, ami igaz, ismeretes vagy kimutatható abból, ami egy véges idő alatt ismert.
Lásd az alábbi példát:
parent(jorge, andres). parent(andres, felipe). grandparent(X,Y) :- parent(X, Z), parent(Z, Y). ? grandparent(jorge,_). %true %il y a assez d'information pour dire que jorge a un grandparent connu. % Hypothèse du monde clos → il n'y a pas assez d'informations pour arriver à une conclusion -> false ? grandparent(andres,_). %false %Négation par l'échec appuyé sur l'hypothèse du monde clos ? not(grandparent(andres,_)). %trueA Prolog logikus nyelv, ezért elméletileg nem kell aggódnia a végrehajtása miatt. Néha azonban körültekintő figyelembe venni a következtetési algoritmus működését, megakadályozva, hogy a Prolog program túl sokáig tartson.
Például írhatunk kódot a listában szereplő elemek számának megszámolásához.
elems([],0). elems([H|T], X) :- elems(T, Y), X is Y + 1.Ez egyszerűen azt jelenti:
Ebben az esetben egyértelmű különbség van a szabályokban az előzményben szereplő esetek között. De vegye figyelembe azt az esetet, amikor el kell döntenie, hogy folytatja-e a kaszinóban való játékot;
miser(X) :- avoirargent(X). miser(X) :- avoircrédit(X), NOT avoirargent(X).Ha van pénze, folytatja a fogadást. Ha mindent elvesztett, amire szüksége van kölcsön, vagy ha nem ... nincs több tét. A havemoney (X) nagyon költséges funkció lehet, például, ha az interneten keresztül hozzáférhet bankszámlájához. De ugyanez vonatkozik a hitelre is .
Elméletileg a Prolog megvalósításai bármilyen sorrendben kiértékelhetik ezeket a szabályokat, így írhatta volna;
miser(X) :- avoircrédit(X), NOT avoirargent(X). miser(X) :- avoirargent(X).Ami jó, mert a két lehetőség kizárja egymást. Annak ellenőrzése azonban, hogy kaphat-e hitelt, nem szükséges, ha tudja, hogy van pénze. A gyakorlatban is a Prolog megvalósításai tesztelik azt a szabályt, amelyet először írtál . Használhatja a vágás operátort arra, hogy a tolmácsnak utasítsa a második opció kihagyását, ha az első elegendő. Például:
miser(X) :- avoirargent(X), !. miser(X) :- avoircrédit(X), NOT avoirargent(X).Ezt zöld stop operátornak hívják . A ! egyszerűen azt mondja a tolmácsnak, hogy hagyjon fel alternatívát. De észreveszi, hogy ha szüksége van a pénzre, akkor a második szabály értékeléséhez szüksége van rá, és meg is fogja. Annak értékelése, hogy van-e pénz a második szabályban, elég értelmetlen, mert tudja, hogy nincs, annak az egyszerű oknak az miatt, hogy különben a második szabályt nem értékelnék. Azt is megváltoztathatja a kódot, hogy:
miser(X) :- avoirargent(X), !. miser(X) :- avoircrédit(X).Ezt piros stop operátornak hívják , mert veszélyes ezt megtenni. Most függ a stop operátor helyes elhelyezésétől és a szabályok sorrendjétől, hogy meghatározza logikai jelentését. Ha a szabályok összekeverednek, most felhasználhatja hitelkártyáját, mielőtt elköltené tartalék pénzét.
Ehelyett azt írná:
miser(X) :- avoirargent(X), ! ; avoircrédit(X).amely így hangzik: X fogadásához vagy megvan ez a pénz előre, vagy egyébként megvan a szükséges hitel.
Általánosságban a Prolog nem állapít meg állapotot az állítmány paraméterein: ezek nem „adott” vagy „eredmények”, sőt „adott / eredmények” paraméterek, állapotuk a priori lényegtelen és a lekérdezések szerint kerül meghatározásra, és néha előre definiáltakat használnak.
Ez gyakran lehetővé teszi a reverzibilis predikátumok meghatározását: a zárt lekérdezések, amelyek az adatok eredményeit szolgáltatják, invertálhatók nyílt lekérdezésekké, keresve az adatokat, amelyek pozitív eredményhez vezetnek.
életkor (kapitány, 45) igaz vagy hamis; age (kapitány, X) megkérdezi, hogy mi a kapitány X kora , age (X, 45) azt kérdezi, hogy melyik X 45 éves.Ezt a lehetőséget a fenti generátor / akceptor használja.
Vegyük az f csomópontú, 0 vagy 1 levélű bináris fákat.
symetrique(0,0). symetrique(1,1). symetrique(f(A,B),f(Y,X)):-symetrique(A,X), symetrique(B,Y).Ennek az állítmánynak a szokásos használata a következő:
?- symetrique(f(f(0,1),1),R). R = f(1,f(1,0))De rendelkezhetünk:
?- symetrique(A,f(f(0,1),1)). A = f(1,f(1,0))Programozási nyelvként a Prolog a következőkkel különböztethető meg:
A Prolog a kezdetektől fogva a relációs adatbázisok területére összpontosított , amelyhez nagy rugalmasságot biztosít a lekérdezések terén, amint levonhatók a tényekből: így deduktív adatbázisokká válnak . Így egy családi stílusú ténybázis (Apa, Anya, ListOfChildren) néhány szabállyal képes lesz megválaszolni a különböző genealógiai kérdéseket.
Ezen túlmenően a Prolog kínálhat egy lekérdezési rendszert is, amely közös az egymástól függő adatbázisok együttesében; a rendelkezésre álló alapkapcsolatok kombinálásával megszerezzük egy virtuális adatbázis szolgáltatásait, amelyek ezeket az adatbázisokat ötvözik, így jelentősen gazdagodnak a lehetséges kérések.
A nyelvi feldolgozás a Prologban lehetséges a hivatalos nyelvtanok alapján .
ELFOGADÓ / GENERÁTOR
% générateur de phrases acceptables gen(X):- phrase(X), writeln(X), fail; writeln('---------'). % % accepteur % syntaxe phrase([S, V|Suite]):- sujet(S), verbe(V), ( Suite=[]; Suite=[C], complement(C)). sujet(S):- est1(S, pronom); est1(S, nom). verbe(V) :- est1(V, present). complement(C):- est1(C,nom); est1(C,adverbe). % emploi lexique est1(Mot, Cat):- dico(Cat, L),dans(Mot, L). dans(X, [Y|Z]):- X = Y ; dans(X, Z). dico(nom, [andre, marie, pierre, sylvie]). dico(pronom, [il, elle, on]). dico(present, [aime, chante, charme, ennuie, observe]). dico(adverbe, [bien, fort, mal, peu]).PÁRBESZÉD:
1 ?- phrase([pierre, aime, sylvie]). true . % phrase acceptée 2 ?- phrase([elle, chante]). true . % phrase acceptée 3 ?- phrase([on, danse]). false. % ''danse'' est inconnu 4 ?- phrase([il, X]). X = aime ; X = chante ; X = charme ; X = ennuie ; X = observe ; false. % phrases acceptées (énumérées par relance) 5 ?- gen([il, X]). [il,aime] [il,chante] [il,charme] [il,ennuie] [il,observe] --------- true. % génération en bloc des phrases conformes à la demandeegy kapcsolódó ELEMZŐ
% analyse grammaticale % syntaxe analyse([S,V], ph(AS, AV)):- sujet(S, AS), verbe(V, AV). analyse([S, V, C], ph(AS, gv(AV, AC))):- sujet(S, AS), verbe(V, AV), complement(C, AC). sujet(S, sujet(pronom, S)):- est1(S, pronom). sujet(S, sujet(nom, S)) :- est1(S, nom). sujet(S, sujet('???', S)). verbe(V,verbe(present, V)) :- est1(V, present). verbe(V,verbe('???', V)). complement(C, comp(nom, C)):- est1(C,nom). complement(C, comp(adv, C)):- est1(C,adverbe). complement(C, comp('???', C)). % même partie lexique que précédemmentPÁRBESZÉD:
1 ?- analyse([sylvie, chante], A). A = ph(sujet(nom, sylvie), verbe(present, chante)) . 2 ?- analyse([pierre, aime, sylvie], A). A = ph(sujet(nom, pierre), gv(verbe(present, aime), comp(nom, sylvie))) . 3 ?- analyse([tu, bois], A). A = ph(sujet(???, tu), verbe(???, bois)). 4 ?- analyse([il, chante, faux], A). A = ph(sujet(pronom, il), gv(verbe(present, chante), comp(???, faux))) .hol a '???' a program hibáit vagy korlátait jelöli.
A Prolog nyelvi alkalmazásait egyszerűsítették és kibővítették a DCG-k használatával ( Definite Clause Grammar (en) ) (Pereira & Warren, 1980).
Innen a Prologot használhatja automatikus vagy félautomata fordításhoz .
Gyakrabban egy egyszerű elemző lehetővé teszi az áltermészetes lekérdezések használatát a relációs adatbázisok lekérdezéséhez.
A priori érdekes Prolog alkalmazások végrehajtása túl hosszú lehet a mögöttes kombinatorika miatt. A Prolog és a logikai programozás olyan programozási mozgást hozott létre, amely ötvözi a Prolog legtöbb sajátosságát és a Constraint Programming hozzájárulását ahhoz, hogy a Prolog IV-vel (1996) együtt a Constraint Logic Programming (PLC) felé vezesse . Hatékony kombinatív problémákban, különösen a CAD , műveletek kutatása és játékok.
Valójában előírhatjuk, hogy n változó, amelyek n értékű tartományt osztanak meg, kizárják egymást, csökkentve az esetek számát n ^ n-ről n-re! Például n = 10 esetén 10 milliárdról 3,6 millióra.
1980-ban a japán projekt 5 th generációs (in) tette nagy reményeket a párhuzamosítását Prolog, amelyek szembesültem azzal a ténnyel, hogy a Prolog grammatikus inspiráció, a logikus csatlakozók nem kommutatív. A szabályok használata azonban csővezeték módban is alkalmazható, szükség esetén megszakítható. Vagy a szabály:
musicienGrec(X) :- musicien(X), grec(X).Amint Prolog talál egy zenészt, ellenőrizheti, hogy görög-e, ebben az esetben ez az első válasz. Ezért a zenész nemzetiségének ellenőrzése elvégezhető, amíg a rendszer által ismert más zenészek után kutatnak. Ez a folyamat annál hatékonyabb, ha a keresés a legszelektívebb predikátummal kezdődik: ez az eset áll fenn, ha a rendszer kevesebb zenészt ismer, mint a görögöket.
A Prolog lehetővé teszi az indukcióval történő érvelést, és ezáltal lehetőséget ad a sejtések ellenőrzésére. A képleteket reprezentáló fák feldolgozásának képessége lehetővé teszi az algebra használatát .
A pusztán a Prolog-alkalmazásokon túl a Prolog és a hagyományos nyelvek kombinálásának lehetősége az 1985-ös évektől lehetővé tette számos alkalmazás intelligens modulokkal , például szakértői modulokkal való ellátását . Összehasonlítható teljesítmény alapján ezek a modulok így növelik az alkalmazások rugalmasságát és relevanciáját.