Prolog | |
Datum první verze | 1972 |
---|---|
Paradigma | Logické programování |
Autor | Alain Colmerauer , Philippe Roussel |
Ovlivněno | Plánovač ( v ) |
Přípona souboru | pl, pro a P |
Prolog je řeč o logickém programování . Název Prolog je zkratka PROGRAMATION v LOGIC. Vytvořili jej Alain Colmerauer a Philippe Roussel kolem roku 1972 v Luminy v Marseille. Cílem bylo vytvořit programovací jazyk, ve kterém by byla definována logická pravidla očekávaná od řešení, a nechat kompilátor, aby jej transformoval do posloupnosti instrukcí. Jedním z očekávaných přínosů bylo zvýšení snadnosti údržby aplikací, přidání nebo odstranění pravidel v průběhu času, které nevyžadují opětovné přezkoumání všech ostatních.
Prolog se používá v umělé inteligenci a při počítačovém lingvistickém zpracování (zejména v přirozených jazycích ). Jeho pravidla syntaxe a sémantika jsou jednoduchá a považována za jasná (jedním ze sledovaných cílů bylo poskytnout nástroj lingvistům neznalým počítačové vědy). První výsledky získané s Prologem vyvolaly po určitou dobu, v 80. letech, výzkum páté generace, hardwaru a softwaru, počítačů (s názvem Japonská pátá generace kvůli důležitému závazku MITI na projektu). Vynaložené úsilí bylo důležité, dopad skromnější, Prolog zůstal jedním jazykem mimo jiné v rozsahu programátora.
Prolog je založen na výpočtu predikátů prvního řádu ; ve své původní verzi je však omezen pouze na přijímání Hornových klauzulí (moderní verze Prologu přijímají složitější predikáty, zejména při léčbě negace selháním ). Provedení programu Prolog je účinně aplikací dokazovací věty řešením prvního řádu. Základními pojmy jsou sjednocení , rekurze a zpětné sledování . Algoritmus rozlišení Prologu je založen na rozšíření rozlišení SLD .
V Prologu můžeme vytvořit znalostní základnu v neurčitém pořadí, protože se počítají pouze vztahy v přítomnosti a ne jejich sekvence psaní. Prolog pak může vyřešit řadu logických problémů souvisejících s takovou znalostní základnou (pojem deduktivní databáze), problém podobný hledání řešení (nebo několika) v labyrintu zavedených omezení.
Prolog nepoužívá psaní dat v obvyklém smyslu programovacích jazyků . Ve skutečnosti nedělá skutečný rozdíl mezi daty programu a samotným programem (princip deklarativního programování i funkčního programování). Jeho lexikální prvky, nazývané termíny , zahrnují následující typy.
Konstantní texty tvoří atomy . Atom je obvykle tvořen řetězcem písmen, čísel a podtržítků ( _), počínaje malým písmenem . Chcete-li zavést nealfanumerický atom, obklopte ho apostrofy: '+' je tedy atom, + operátor).
Aktuální implementace Prologu nerozlišují mezi celými čísly a plováky.
Proměnné se zadávají pomocí sady písmen, čísel a podtržítka a začínají velkým písmenem .
Tak X3 as Unit_Price jsou jména přípustných proměnných.
Prolog není nezbytně nutný programovací jazyk ; proměnná tedy není kontejnerem, kterému je přiřazena hodnota, ale představuje (jako v matematice v X> 0 ) pro ni v rámci omezení množinu přípustných hodnot.
Původně nedefinované pole proměnné je specifikováno sjednocením kolem omezení. Jakmile je proměnná sjednocena, její hodnotu již nelze upravit ve stejné hodnotící větvi. Nicméně, backtracking umožňuje vrátit se k tomuto sjednocení v rámci úsilí o hledání přípustných hodnot (nebo nové přípustných hodnot) v rámci vyčerpávajícího zkoumání.
Anonymní proměnná je psán s podtržítkem (_). Jakákoli proměnná, jejíž název začíná podtržítkem, je také anonymní proměnnou. Je to jako x nebo y algebry fiktivní proměnná sloužící jako prostředník výpočtu.
Prolog může představovat složitá data pouze ve složených termínech . Složený výraz se skládá z hlavy (nazývané také funktor ), kterou musí být atom, a parametrů bez omezení typu. Počet parametrů nazývaných arity termínu je však významný. Složený výraz je identifikován podle jeho hlavy a jeho arity a obvykle je psán jako funktor / arity.
Příklady složených výrazů:
Seznam není izolovaným datovým typem, ale je definován rekurzivní konstrukcí (pomocí funktoru .arity 2, takže je na úrovni interní reprezentace složený termín):
První prvek, nazývaný hlava, je H , následovaný obsahem zbytku seznamu, označeného jako T nebo ocas. Seznamu [1, 2, 3] . '' By být reprezentovány interně ( 1 '', ( 2 '', ( 3 , []))) syntaxe zkrácený je [ H | T ], který se většinou používá pro stavební pravidla. Celý seznam lze zpracovat působením na první prvek a poté na zbytek seznamu rekurzí , jako v LISP .
Pro pohodlí programátora je možné seznamy sestavovat a dekonstruovat různými způsoby.
Řetězce jsou obvykle psány jako posloupnost znaků obklopených apostrofy. Často jsou interně zastoupeni seznamem kódů ASCII.
Programování v Prologu je velmi odlišná od programování v imperativním jazykem . V Prologu poskytujeme znalostní základnu faktů a pravidel; pak je možné vznést požadavky na znalostní bázi.
Základní jednotkou Prologu je predikát , který je definován jako true. Predikát se skládá z hlavy a řady argumentů. Například :
chat(tom).Tady je „kočka“ hlavou a „tom“ je argument. Tady je několik jednoduchých požadavků, na které se můžete zeptat tlumočníka Prologu na základě této skutečnosti:
?- chat(tom). oui. ?- chat(X). X = tom; fail.V tomto druhém příkladu na otázku „cat (X)“ navrhuje tlumočník odpověď „X = tom“ sjednocující proměnnou „X“ s atomem „tom“. V Prologu je to úspěch . Po této první odpovědi se uživatel může zeptat, zda existují další odpovědi, pomocí „; »(Symbol disjunkce), zde tlumočník odpovídá, že žádné nenajde. Toto hledání dalších řešení je založeno na nedeterministickém modelu provádění (ve smyslu nedeterminismu nedeterministických automatů) se zpětnou vazbou o různých bodech výběru a zkoumání neprozkoumaných alternativ.
?- chat(vim). fail.V tomto posledním příkladu na otázku „chat (vim)“ tlumočník odpovídá, že tuto skutečnost nedokáže, v Prologu jde o selhání. Za předpokladu, že jsou známa všechna fakta ( hypotéza uzavřeného světa ), to znamená, že „vim“ není kočka.
Predikáty jsou obvykle definovány k vyjádření faktů, které program o světě ví. Ve většině případů vyžaduje použití predikátů určitou konvenci. Například sémantika následujících dvou predikátů není okamžitá:
pere(marie, pierre). pere(pierre, marie).V obou případech je „otec“ hlavou, zatímco „marie“ a „pierre“ jsou argumenty. V prvním případě je však Mary na prvním místě v seznamu argumentů a ve druhém je to Peter (na pořadí v seznamu argumentů záleží). První případ je příkladem definice v pořadí sloveso-předmět-předmět a lze jej číst pomocným slovem „mít“: Marie má pro otce Pierra, druhý sloveso-předmět-předmět a lze jej číst pomocí pomocná „bytost“: Pierre je otcem Marie. Protože Prolog nerozumí přirozenému jazyku, jsou obě verze, pokud jde o; je však důležité přijmout konzistentní programové standardy pro stejný program. Obecně se používá spíše pomocné „bytí“.
Například s tím souhlasíme
famille(pierre, marie, [arthur, bruno, charlotte]).znamená, že Pierre a Marie jsou otcem a matkou 3 dětí: Arthur, Bruno a Charlotte; „rodina“ je potom tříčlenný predikát, přičemž poslední je seznam jakéhokoli (případně nulového) počtu dětí.
Některé predikáty jsou zabudovány do jazyka a umožňují programu Prolog provádět rutinní činnosti (jako je numerické hodnocení, vstup / výstup , funkce grafického uživatelského rozhraní a obecně komunikují s počítačovým systémem). Například pro zápis na obrazovce lze použít predikát zápisu . Proto
write('Bonjour').zobrazí na monitoru slovo „Hello“. Přísně vzato, takové predikáty se netýkají logického programování, jejich funkčnost je založena výhradně na jejich vedlejších účincích.
Ostatní predikáty zabudované do jazyka mají přirozenou logiku a jsou součástí knihoven . Používají se ke zjednodušení vývoje zapouzdřením obecného zpracování, jako jsou například algoritmy zpracování seznamu.
Nakonec jsou další predikáty vyššího řádu a používají se k řízení provádění tlumočníků Prologu (například dynamické přidávání / odebírání pravidel a faktů, opuštění volitelných bodů, shromažďování výsledků dotazu.)
Pozn. - Bez předdefinovaných predikátů se Prolog někdy nazývá Pure Prolog (podle normy ISO v angličtině : definitivní Prolog).
Druhým typem pokynů v Prologu je pravidlo. Příklad pravidla je:
lumière(on) :- interrupteur(on).„: -“ znamená „pokud“; toto pravidlo označuje, že světlo (zapnuto) je pravdivé, pokud je zapnuto (zapnuto). Pravidla mohou také používat proměnné jako:
père(X,Y) :- parent(X,Y), mâle(X).znamená, že X je otcem Y, pokud X je rodič Y a X je muž, kde „,“ označuje spojení.
Mohli bychom mít totéž:
parent(X, Y) :- père(X, Y) ; mère(X, Y).znamená, že X je rodič Y, pokud X je rodič Y nebo X je rodič Y, kde „;“ označuje alternativu.
Faktem je zvláštní případ pravidla. Následující dva řádky jsou skutečně ekvivalentní:
a. a :- true.Když tlumočník obdrží požadavek, vyhledá pravidla (včetně faktů), jejichž levá část může být sjednocena s požadavkem, a provede toto sjednocení s prvním nalezeným pravidlem. Například mít tento kód Prolog:
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).Výsledkem je, že následující požadavek je vyhodnocen jako pravdivý:
?- frère_ou_sœur(sally, erica). oui.Tlumočník dosáhne tohoto výsledku spojením pravidla sibling_or_sister (X, Y) sjednocením X s sally a Y s erica . To znamená, že požadavek lze rozšířit na parent (Z, sally) , parent (Z, erica) . Srovnání této konjunkce je dosaženo pohledem na všechny možné rodiče Sally . Nicméně, rodič (Trude, výpad) nevede k životaschopné řešení, protože v případě, Trude nahradí Z , rodiče (Trude, Erica), budou muset být pravda, a žádná taková skutečnost (nebo jakékoli pravidlo, které může uspokojit, že) je je přítomen. Místo toho je Tom nahrazen Z a Erica a Sally se přesto zdají být sourozenci .
Čistá logická negace v Prologu neexistuje, spoléháme se na negaci neúspěchem , což je podle implementací Prologu uvedeno jinak (notaci přijmeme podle klíčového slova not(prédicat)). Při negaci selháním je negace predikátu považována za pravdivou, pokud vyhodnocení predikátu vede k selhání (není ověřitelné).
V Prologu je negace neúspěchem založena na hypotéze uzavřeného světa: vše, co je pravdivé, je známé nebo prokazatelné z toho, co je známo v konečném čase.
Viz příklad níže:
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,_)). %trueProlog je logický jazyk, takže si teoreticky nemusíte dělat starosti s jeho prováděním. Někdy je však rozumné vzít v úvahu, jak odvozovací algoritmus funguje, aby se zabránilo tomu, aby program Prolog trval příliš dlouho.
Například můžeme napsat kód, který spočítá počet prvků v seznamu.
elems([],0). elems([H|T], X) :- elems(T, Y), X is Y + 1.Jednoduše to znamená:
V tomto případě existuje jasný rozdíl mezi případy předchůdce pravidel. Ale zvažte případ, kdy se musíte rozhodnout, zda budete pokračovat v hraní v kasinu;
miser(X) :- avoirargent(X). miser(X) :- avoircrédit(X), NOT avoirargent(X).Pokud máte peníze, sázíte dál. Pokud jste ztratili vše, co si potřebujete půjčit, nebo pokud ne ... už žádné sázení. havemoney (X) může být velmi drahá funkce, například pokud má přístup k vašemu bankovnímu účtu přes internet. Ale je to stejné i pro úvěr .
Teoreticky mohou implementace Prologu vyhodnotit tato pravidla v libovolném pořadí, takže jste mohli psát;
miser(X) :- avoircrédit(X), NOT avoirargent(X). miser(X) :- avoirargent(X).Což je dobré, protože tyto dvě možnosti se vzájemně vylučují. Kontrola, zda můžete získat půjčku, však není nutná, pokud víte, že máte peníze. Implementace Prologu také v praxi nejprve otestují pravidlo, které jste napsali jako první . Pomocí operátoru vyjmutí můžete tlumočníkovi říct, aby přeskočil druhou možnost, pokud je první dostatečná. Například:
miser(X) :- avoirargent(X), !. miser(X) :- avoircrédit(X), NOT avoirargent(X).Tomu se říká operátor zelené zastávky . The ! jednoduše řekne tlumočníkovi, aby přestal hledat alternativu. Všimli jste si však, že pokud potřebujete peníze, musí vyhodnotit druhé pravidlo, a bude. Vyhodnocení toho, zda máte v druhém pravidle peníze, je docela zbytečné, protože víte, že žádné nemáte, a to z prostého důvodu, že jinak by se druhé pravidlo nevyhodnocovalo. Také můžete změnit kód na:
miser(X) :- avoirargent(X), !. miser(X) :- avoircrédit(X).Tomu se říká operátor červeného zastavení , protože je to nebezpečné. Nyní jste závislí na správném umístění operátoru zastavení a pořadí pravidel, abyste určili jejich logický význam. Pokud jsou pravidla smíšená, můžete nyní použít svou kreditní kartu, než utratíte své volné peníze.
Místo toho byste napsali:
miser(X) :- avoirargent(X), ! ; avoircrédit(X).který zní: vsadit X, buď mám tyto peníze předem, nebo jinak mám potřebný kredit.
Obecně platí, že Prolog neukládá status parametrům predikátu: nejsou to „dané“ nebo „výsledky“, nebo dokonce parametry „dané / výsledky“, jejich stav je a priori irelevantní a bude definován podle dotazů, a někdy se používají předdefinované.
To často umožňuje definici reverzibilních predikátů: uzavřené dotazy, poskytující výsledky z dat, mohou být invertovány do otevřených dotazů a hledat data vedoucí k pozitivnímu výsledku.
věk (kapitán, 45 let) je true nebo false; věk (kapitán, X) se zeptá, jaký je věk X kapitána, věk (X, 45) se zeptá, kterému X je 45 let.Tato možnost se používá v generátoru / akceptoru výše.
Vezměme binární stromy s uzlem f a listem 0 nebo 1.
symetrique(0,0). symetrique(1,1). symetrique(f(A,B),f(Y,X)):-symetrique(A,X), symetrique(B,Y).Standardní použití tohoto predikátu je typu:
?- symetrique(f(f(0,1),1),R). R = f(1,f(1,0))Ale můžeme mít také:
?- symetrique(A,f(f(0,1),1)). A = f(1,f(1,0))Jako programovací jazyk se Prolog vyznačuje:
Prolog se od začátku zaměřoval na oblast relačních databází , kterým poskytuje velkou flexibilitu, pokud jde o dotazy, jakmile jsou odečitatelné ze skutečností: stávají se tak deduktivními databázemi . Základna faktů v rodinném stylu (otec, matka, seznam dětí) bude tedy schopna s několika pravidly odpovědět na různé genealogické otázky.
Kromě toho může Prolog nabídnout také systém dotazů společných pro sadu vzájemně závislých databází; kombinací dostupných základních vztahů získáváme služby virtuální databáze kombinující tyto databáze, a tím i značné obohacení možných požadavků.
Jazykové zpracování je v Prologu možné na základě formálních gramatik .
AKCEPTOR / 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]).DIALOG:
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 demandesouvisející ANALYZÁTOR
% 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édemmentDIALOG:
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))) .Kde '???' označují chyby nebo omezení programu.
Jazykové aplikace Prologu byly zjednodušeny a zesíleny použitím DCG ( Definite Clause Grammar (en) ) (Pereira & Warren, 1980).
Odtud můžete použít Prolog pro automatický nebo poloautomatický překlad .
Jednoduchý analyzátor častěji umožní použití pseudo-přirozených dotazů pro dotazování relačních databází.
A priori zajímavé aplikace Prolog by mohly mít nadměrné časy provádění kvůli základní kombinatorice. Prolog a logické programování daly vzniknout programového proudu kombinujícího většinu specifiky Prolog a příspěvky programování s omezujícími podmínkami vést s Prolog IV (1996) do Logické programování (PLC). Účinná při kombinatorických problémů, a to zejména v CAD , operační výzkum a hry.
Lze například stanovit, že n proměnných sdílejících doménu s n hodnotami se vzájemně vylučuje, čímž se snižuje počet případů z n ^ n na n !. Například pro n = 10 z 10 miliard na 3,6 milionu.
V roce 1980, japonský projekt 5 th generace (in) dal velké naděje do paralelizace Prologu, které čelí skutečnost, že Prolog je gramatická inspirace, jeho logické spojky nejsou komutativní. Použití pravidel však lze přizpůsobit v režimu potrubí, který lze v případě potřeby přerušit. Buď pravidlo:
musicienGrec(X) :- musicien(X), grec(X).Jakmile Prolog najde hudebníka, může zkontrolovat, zda je to Řek, v takovém případě se jedná o první odpověď. Proto lze ověřit národnost hudebníka, zatímco pokračuje hledání dalších hudebníků známých systému. Tento proces je o to účinnější, když vyhledávání začíná nejselektivnějším predikátem: to je případ, kdy systém zná méně hudebníků než Řeků.
Prolog umožňuje uvažování indukcí, a tak poskytuje možnost kontroly domněnek. Jeho schopnost zpracovávat stromy, které mohou reprezentovat vzorce, umožňuje jeho použití v algebře .
Kromě čistě aplikací Prolog umožnila možnost kombinovat Prolog s tradičními jazyky od roku 1985 poskytovat mnoho aplikací s inteligentními moduly, jako jsou expertní moduly. Při srovnatelném výkonu tak tyto moduly zvyšují flexibilitu a relevanci aplikací.