Prolog - Prolog

Prolog je logický programovací jazyk spojený s umělou inteligencí a výpočetní lingvistikou .

Prolog má své kořeny v logice prvního řádu , formální logice , a na rozdíl od mnoha jiných programovacích jazyků je Prolog určen především jako deklarativní programovací jazyk: logika programu je vyjádřena ve vztazích , reprezentována jako fakta a pravidla . Výpočet je iniciováno spuštěním dotazu nad těmito vztahy.

Jazyk byl vyvinut a implementován v Marseille ve Francii v roce 1972 Alainem Colmerauerem s Philippe Rousselem na základě procedurální interpretace klauzulí Horn Roberta Kowalského .

Prolog byl jedním z prvních logických programovacích jazyků a dnes zůstává nejpopulárnějším takovým jazykem, k dispozici je několik bezplatných i komerčních implementací. Jazyk byl použit pro dokazování vět , expertní systémy , přepisování termínů , typové systémy a automatizované plánování , stejně jako jeho původní zamýšlená oblast použití, zpracování přirozeného jazyka . Moderní prostředí Prolog podporují vytváření grafických uživatelských rozhraní i administrativních a síťových aplikací.

Prolog je vhodný pro specifické úkoly, které těží z logických dotazů založených na pravidlech, jako je vyhledávání v databázích , systémy hlasového ovládání a vyplňování šablon.

Syntaxe a sémantika

V Prologu je logika programu vyjádřena relacemi a výpočet je zahájen spuštěním dotazu přes tyto vztahy. Vztahy a dotazy jsou konstruovány pomocí jediného datového typu Prolog, výrazu . Vztahy jsou definovány klauzulemi . Vzhledem k dotazu se modul Prolog pokusí najít vyvrácení rozlišení negovaného dotazu. Pokud lze negovaný dotaz vyvrátit, tj. Je nalezena instance pro všechny volné proměnné, díky níž je spojení klauzulí a sady singletonů sestávajících z negovaného dotazu nepravdivé, vyplývá z toho, že původní dotaz s aplikovanou nalezenou instancí je logický důsledek programu. Díky tomu je Prolog (a další logické programovací jazyky) zvláště užitečný pro databáze, symbolickou matematiku a aplikace pro analýzu jazyků. Protože Prolog umožňuje nečisté predikáty , může mít kontrola pravdivosti určitých speciálních predikátů záměrný vedlejší účinek , například tisk hodnoty na obrazovku. Z tohoto důvodu může programátor použít určité množství konvenčního imperativního programování, když je logické paradigma nepohodlné. Má čistě logickou podmnožinu, nazývanou „čistý Prolog“, a také řadu extralogických funkcí.

Typy dat

Jediným datovým typem Prologu je termín . Pojmy jsou buď atomy , čísla , proměnné nebo složené výrazy .

• Atom je název pro všeobecné použití bez vlastní význam. Příklady atomů zahrnují x, red, 'Taco', a 'some atom'.
• Čísla mohou být plovoucí nebo celá . Systémy Prolog kompatibilní se standardem ISO mohou kontrolovat příznak Prolog „ohraničený“. Většina hlavních systémů Prolog podporuje celočíselná čísla libovolné délky.
• Proměnné jsou označeny řetězcem skládajícím se z písmen, číslic a podtržítek a začínají velkým písmenem nebo podtržítkem. Proměnné se logicky velmi podobají proměnným v tom, že jsou zástupnými symboly pro libovolné výrazy.
• Sloučenina termín se skládá z atomu nazývá „funktor“ a řada „argumenty“, které jsou opět podmínek. Složené výrazy se obvykle zapisují jako funktor následovaný seznamem argumentů oddělených čárkami, který je obsažen v závorkách. Počet argumentů se nazývá arita pojmu . Atom lze považovat za složený termín s nulovou arititou . Příkladem složeného výrazu je person_friends(zelda,[tom,jim]).

Zvláštní případy složených výrazů:

• Seznam je objednaný soubor podmínek. Je označen hranatými závorkami s výrazy oddělenými čárkami nebo v případě prázdného seznamu znakem []. Například, [1,2,3]nebo [red,green,blue].
• Řetězce : Sekvence znaků obklopená uvozovkami je ekvivalentní buď seznamu (číselných) kódů znaků, seznamu znaků (atomy délky 1) nebo atomu v závislosti na hodnotě příznaku Prolog double_quotes. Například "to be, or not to be".

ISO Prolog poskytuje atom/1, number/1, integer/1a float/1predikáty pro typu kontroly .

Pravidla a fakta

Programy Prolog popisují vztahy definované pomocí klauzulí. Pure Prolog je omezen na klauzule Horn . Existují dva typy klauzulí: fakta a pravidla. Pravidlo je ve formě

Head :- Body.

a čte se jako „Hlava je pravdivá, pokud je tělo pravdivé“. Tělo pravidla se skládá z volání predikátů, kterým se říká cíle pravidla . Vestavěný logický operátor ,/2 (což znamená arity 2 operátora se jménem ,) označuje konjunkci cílů, a ;/2označuje disjunkci . Spojení a rozpojení se mohou objevit pouze v těle, nikoli v hlavě pravidla.

Klauzule s prázdnými těly se nazývají fakta . Příkladem skutečnosti je:

cat(crookshanks).

což je ekvivalentní pravidlu:

cat(crookshanks) :- true.

Vestavěný predikát true/0je vždy pravdivý.

Vzhledem k výše uvedenému faktu se lze ptát:

je gauners kočka?

 ?- cat(crookshanks).
 Yes

jaké věci jsou kočky?

 ?- cat(X).
 X = crookshanks

Klauzule s těly se nazývají pravidla . Příkladem pravidla je:

animal(X) :- cat(X).

Pokud přidáme toto pravidlo a zeptáme se, jaké věci jsou zvířata?

 ?- animal(X).
 X = crookshanks

Vzhledem k relační povaze mnoha vestavěných predikátů je lze obvykle použít v několika směrech. Lze například length/2použít k určení délky seznamu ( length(List, L)daný seznam List) a také ke generování kostry seznamu o dané délce ( length(X, 5)) a také ke generování koster seznamu a jejich délek dohromady ( length(X, L)). Podobně append/3lze použít jak k připojení dvou seznamů ( append(ListA, ListB, X)daných seznamů ListAa ListB), tak k rozdělení daného seznamu na části ( append(X, Y, List)daný seznam List). Z tohoto důvodu pro mnoho programů Prolog stačí poměrně malá sada predikátů knihovny.

Prolog jako obecný jazyk také poskytuje různé vestavěné predikáty k provádění rutinních činností, jako je vstup/výstup , pomocí grafiky a jiné komunikace s operačním systémem. Tyto predikáty nemají vztahový význam a jsou užitečné pouze pro vedlejší efekty, které v systému vykazují. Predikát například write/1zobrazuje na obrazovce výraz.

Provedení

Provedení programu Prolog je zahájeno odesláním uživatele jediného cíle, nazývaného dotaz. Logicky se modul Prolog pokusí najít vyvrácení rozlišení negovaného dotazu. Metoda rozlišení používaná Prologem se nazývá rozlišení SLD . Pokud lze negovaný dotaz vyvrátit, vyplývá z toho, že dotaz s příslušnými proměnnými vazbami je logickým důsledkem programu. V takovém případě jsou uživateli generovány všechny generované proměnné vazby a dotaz je údajně úspěšný. Operačně lze strategii provádění Prologu chápat jako zobecnění volání funkcí v jiných jazycích, přičemž jedním rozdílem je, že danému volání může odpovídat více hlav klauzulí. V takovém případě systém vytvoří bod volby, sjednotí cíl s klauzulí vedoucí první alternativy a pokračuje v cílech této první alternativy. Pokud se některý cíl během provádění programu nezdaří, všechny variabilní vazby, které byly vytvořeny od vytvoření posledního bodu výběru, budou vráceny zpět a provádění pokračuje další alternativou tohoto bodu výběru. Tato strategie provádění se nazývá chronologické zpětné sledování . Například:

mother_child(trude, sally).
 
father_child(tom, sally).
father_child(tom, erica).
father_child(mike, tom).
 
sibling(X, Y)      :- parent_child(Z, X), parent_child(Z, Y).
 
parent_child(X, Y) :- father_child(X, Y).
parent_child(X, Y) :- mother_child(X, Y).

Výsledkem je, že následující dotaz bude vyhodnocen jako pravdivý:

 ?- sibling(sally, erica).
 Yes

Toho dosáhneme následovně: Zpočátku je jedinou odpovídající klauzulí klauzule pro dotaz sibling(sally, erica)první, takže prokázání dotazu je ekvivalentní prokázání těla této klauzule s příslušnými proměnnými vazbami na místě, tj. Spojkou (parent_child(Z,sally), parent_child(Z,erica)). Další cíl, který je třeba dokázat, je z této spojky úplně vlevo, tj parent_child(Z, sally). Tomuto cíli odpovídají dvě klauzule. Systém vytvoří bod výběru a vyzkouší první alternativu, jejíž tělo je father_child(Z, sally). Tento cíl může být prokázán pomocí skutečnosti father_child(tom, sally), takže vazba Z = tomje generován a další cíle, které mají být prokázáno, je druhá část výše uvedeného spojení: parent_child(tom, erica). Opět to lze dokázat odpovídající skutečností. Protože všechny cíle lze prokázat, dotaz uspěje. Protože dotaz neobsahoval žádné proměnné, nejsou uživateli hlášeny žádné vazby. Dotaz s proměnnými, jako například:

?- father_child(Father, Child).

vyjmenovává všechny platné odpovědi při zpětném sledování.

Všimněte si, že s kódem, jak je uvedeno výše, dotaz ?- sibling(sally, sally).také uspěje. V případě potřeby by bylo možné vložit další cíle k popisu příslušných omezení.

Smyčky a rekurze

Iterační algoritmy lze implementovat pomocí rekurzivních predikátů.

Negace

Vestavěný predikát Prolog \+/1poskytuje negaci jako selhání , což umožňuje nemonotónní uvažování. Cíl \+ illegal(X)v pravidle

legal(X) :- \+ illegal(X).

se hodnotí následovně: Prolog se pokouší dokázat illegal(X). Pokud lze pro tento cíl najít důkaz, původní cíl (tj. \+ illegal(X)) Selže. Pokud nelze najít žádný důkaz, původní cíl uspěje. Proto se \+/1provozovatel prefix se nazývá „provable“ operátor, protože dotaz ?- \+ Goal.úspěšný, pokud cíl není prokazatelný. Tento druh negace je zdravý, pokud je jeho argument „pozemní“ (tj. Neobsahuje žádné proměnné). Správnost je ztracena, pokud argument obsahuje proměnné a je dokončen proces kontroly. Zejména dotaz ?- legal(X).nyní nelze použít k výčtu všech věcí, které jsou legální.

Programování v Prologu

V Prologu se načítání kódu označuje jako poradenství . Prolog lze použít interaktivně zadáním dotazů na výzvu Prolog ?-. Pokud neexistuje řešení, píše Prolog no. Pokud řešení existuje, vytiskne se. Pokud existuje více řešení dotazu, pak je lze požadovat zadáním středníku ;. Existují pokyny pro správnou programovací praxi ke zlepšení účinnosti, čitelnosti a udržovatelnosti kódu.

Zde postupujte podle několika příkladů programů napsaných v Prologu.

Ahoj světe

Příklad dotazu:

?- write('Hello World!'), nl.
Hello World!
true.

?-

Optimalizace kompilátoru

Jakýkoli výpočet lze vyjádřit deklarativně jako posloupnost stavových přechodů. Jako příklad by mohl být implementován optimalizační kompilátor se třemi optimalizačními průchody jako vztah mezi počátečním programem a jeho optimalizovanou formou:

program_optimized(Prog0, Prog) :-
    optimization_pass_1(Prog0, Prog1),
    optimization_pass_2(Prog1, Prog2),
    optimization_pass_3(Prog2, Prog).

nebo ekvivalentně pomocí DCG notace:

program_optimized --> optimization_pass_1, optimization_pass_2, optimization_pass_3.

Rychlé řazení

Quicksort třídící algoritmus, které se týkají seznamu na své vytříděného verzi:

partition([], _, [], []).
partition([X|Xs], Pivot, Smalls, Bigs) :-
    (   X @< Pivot ->
        Smalls = [X|Rest],
        partition(Xs, Pivot, Rest, Bigs)
    ;   Bigs = [X|Rest],
        partition(Xs, Pivot, Smalls, Rest)
    ).
 
quicksort([])     --> [].
quicksort([X|Xs]) -->
    { partition(Xs, X, Smaller, Bigger) },
    quicksort(Smaller), [X], quicksort(Bigger).

Návrhy prologu

Návrhový vzor je obecný znovu použitelný řešení běžně se vyskytující problém v návrhu softwaru . Některé návrhové vzory v Prologu jsou kostry, techniky, klišé, programová schémata, schémata logického popisu a programování vyššího řádu .

Programování vyššího řádu

Predikát vyššího řádu je predikát, který jako argument bere jeden nebo více dalších predikátů. Ačkoliv podpora pro programování vyššího řádu trvá Prolog mimo oblast logiky prvního řádu, která neumožňuje kvantifikaci přes predikáty, ISO Prolog má nyní nějaký vestavěný vyššího řádu predikáty, jako je call/1, call/2, call/3, findall/3, setof/3a bagof/3. Kromě toho, protože libovolné cíle Prologu lze konstruovat a vyhodnocovat za běhu, je snadné psát predikáty vyššího řádu jako maplist/2, které aplikují libovolný predikát na každého člena daného seznamu a sublist/3které filtrují prvky, které splňují daný predikát , také umožňující kari .

Chcete-li převést řešení z časové reprezentace (substituce odpovědí na zpětné sledování) na prostorovou reprezentaci (termíny), má Prolog různé predikáty všech řešení, které shromažďují všechny substituce odpovědí daného dotazu v seznamu. Toho lze využít k porozumění seznamu . Například dokonalá čísla se rovnají součtu jejich správných dělitelů:

 perfect(N) :-
     between(1, inf, N), U is N // 2,
     findall(D, (between(1,U,D), N mod D =:= 0), Ds),
     sumlist(Ds, N).

To lze použít k výčtu dokonalých čísel a také ke kontrole, zda je číslo dokonalé.

Jako další příklad predikát maplistpoužije predikát Pna všechny odpovídající pozice ve dvojici seznamů:

maplist(_, [], []).
maplist(P, [X|Xs], [Y|Ys]) :-
   call(P, X, Y),
   maplist(P, Xs, Ys).

Když Pje predikát, že pro všechny X, P(X,Y)sjednocuje Ys jediným jedinečnou hodnotu, maplist(P, Xs, Ys)je ekvivalentní k aplikování mapu funkce ve funkčním programování jako Ys = map(Function, Xs).

Programovací styl vyššího řádu v Prologu byl propagován v HiLog a λProlog .

Moduly

Pro programování ve velkém poskytuje Prolog modulový systém . Systém modulů je standardizován ISO. Ne všechny kompilátory Prolog podporují moduly a mezi systémy modulů hlavních kompilátorů Prolog jsou problémy s kompatibilitou. V důsledku toho moduly napsané na jednom kompilátoru Prolog nemusí nutně fungovat na ostatních.

Analýza

Existuje speciální notace, která se nazývá gramatiky určitých klauzulí (DCG). Pravidlo definované -->/2místo namísto :-/2je rozšířeno preprocesorem ( expand_term/2zařízení analogické makrům v jiných jazycích) podle několika jednoduchých pravidel přepisování, což má za následek běžné klauzule Prologu. Nejpozoruhodnější je, že přepis vybaví predikát dvěma dalšími argumenty, které lze použít k implicitnímu navlečení stavu kolem, analogicky k monádám v jiných jazycích. DCG se často používají k zápisu analyzátorů nebo generátorů seznamů, protože také poskytují pohodlné rozhraní pro seznamy rozdílů.

Meta-tlumočníci a reflexe

Prolog je homoikonický jazyk a poskytuje mnoho možností k zamyšlení . Jeho implicitní strategie spouštění umožňuje napsat stručný meta-kruhový vyhodnocovač (nazývaný také meta-interpret ) pro čistý kód Prologu:

solve(true).
solve((Subgoal1,Subgoal2)) :- 
    solve(Subgoal1),
    solve(Subgoal2).
solve(Head) :- 
    clause(Head, Body),
    solve(Body).

kde truepředstavuje prázdnou spojku a clause(Head, Body)sjednocuje se s klauzulemi v databázi formuláře Head :- Body.

Protože programy Prolog jsou samy sekvencemi výrazů Prologu ( :-/2je operátorem infixu ), které lze snadno číst a kontrolovat pomocí vestavěných mechanismů (jako read/1), je možné psát přizpůsobené tlumočníky, které rozšiřují Prolog o funkce specifické pro doménu. Například Sterling a Shapiro představují meta-interpret, který provádí uvažování s nejistotou, reprodukované zde s mírnými úpravami:

solve(true, 1) :- !.
solve((Subgoal1,Subgoal2), Certainty) :-
    !,
    solve(Subgoal1, Certainty1),
    solve(Subgoal2, Certainty2),
    Certainty is min(Certainty1, Certainty2).
solve(Goal, 1) :-
    builtin(Goal), !, 
    Goal.
solve(Head, Certainty) :-
    clause_cf(Head, Body, Certainty1),
    solve(Body, Certainty2),
    Certainty is Certainty1 * Certainty2.

Tento tlumočník používá tabulku vestavěných predikátů prologu formuláře

builtin(A is B).
builtin(read(X)).
% etc.

a klauzule reprezentované jako clause_cf(Head, Body, Certainty). Vzhledem k tomu je lze nazvat solve(Goal, Certainty)provedením Goala získáním míry jistoty ohledně výsledku.

Turingova úplnost

Pure Prolog je založen na podmnožině predikátové logiky prvního řádu , klauzule Horn , která je Turingova-úplná . Turingovu úplnost Prologu lze ukázat pomocí simulace Turingova stroje:

turing(Tape0, Tape) :-
    perform(q0, [], Ls, Tape0, Rs),
    reverse(Ls, Ls1),
    append(Ls1, Rs, Tape).
 
perform(qf, Ls, Ls, Rs, Rs) :- !.
perform(Q0, Ls0, Ls, Rs0, Rs) :-
    symbol(Rs0, Sym, RsRest),
    once(rule(Q0, Sym, Q1, NewSym, Action)),
    action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
    perform(Q1, Ls1, Ls, Rs1, Rs).
 
symbol([], b, []).
symbol([Sym|Rs], Sym, Rs).
 
action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs).
action(stay, Ls, Ls, Rs, Rs).
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).
 
left([], [], Rs0, [b|Rs0]).
left([L|Ls], Ls, Rs, [L|Rs]).

Jednoduchý příklad Turingova stroje je specifikován fakty:

rule(q0, 1, q0, 1, right).
rule(q0, b, qf, 1, stay).

Tento stroj provádí inkrementaci o jedno z čísel v unárním kódování: Smyčkuje přes libovolný počet buněk „1“ a na konec připojí další „1“. Příklad dotazu a výsledku:

?- turing([1,1,1], Ts).
Ts = [1, 1, 1, 1] ;

To ukazuje, jak lze jakýkoli výpočet deklarativně vyjádřit jako posloupnost přechodů stavů, implementovaných v Prologu jako vztah mezi po sobě jdoucími stavy zájmu.

Implementace

ISO prolog

ISO norma Prolog se skládá ze dvou částí. ISO/IEC 13211-1, publikovaná v roce 1995, si klade za cíl standardizovat stávající postupy mnoha implementací základních prvků Prologu. Objasnilo aspekty jazyka, které byly dříve nejednoznačné a vedou k přenosným programům. Existují tři opravy: Cor.1: 2007, Cor.2: 2012 a Cor.3: 2017. ISO/IEC 13211-2, publikovaná v roce 2000, přidává do modulu podporu modulů. Standardní je udržován ISO / IEC JTC1 / SC22 pracovní skupiny / WG17. ANSI X3J17 je americká technická poradní skupina pro tento standard.

Sestavení

Z důvodu efektivity je kód Prolog obvykle kompilován do abstraktního strojového kódu, často ovlivňovaného registrovou sadou instrukcí Warren Abstract Machine (WAM). Některé implementace využívají abstraktní interpretaci k odvození informací o typu a režimu predikátů v době kompilace nebo kompilace do skutečného strojového kódu pro vysoký výkon. Vymýšlení efektivních implementačních metod pro kód Prolog je oblastí aktivního výzkumu v komunitě logického programování a v některých implementacích jsou použity různé další způsoby provádění. Patří sem binarizace klauzule a virtuální stroje založené na zásobníku .

Rekurze ocasu

Systémy Prolog typicky implementují dobře známou optimalizační metodu nazvanou TCO ( call call optimization ) pro deterministické predikáty vykazující rekurzi ocasu nebo obecněji volání ocasu: Rámeček klauzule klauzule je vyřazen před provedením volání v poloze ocasu. Proto jsou deterministické rekurzivní predikáty prováděny s konstantním prostorem zásobníku, jako smyčky v jiných jazycích.

Indexování termínů

Hledání klauzulí, které jsou unifikovatelné s termínem v dotazu, je lineární v počtu klauzulí. Terminační indexování používá datovou strukturu, která umožňuje sublineární časová vyhledávání. Indexování ovlivňuje pouze výkon programu, neovlivňuje sémantiku. Většina Prologů používá indexování pouze na prvním výrazu, protože indexování všech výrazů je drahé, ale techniky založené na slovech zakódovaných v poli nebo překrývajících se kódových slov poskytují rychlé indexování v celém dotazu a hlavičce.

Hashování

Některé systémy Prolog, jako například WIN-PROLOG a SWI-Prolog, nyní implementují hašování, které pomáhá efektivněji zpracovávat velké soubory dat. Při práci s velkými korpusy, jako je WordNet, to obvykle přináší velmi velké zvýšení výkonu .

Podávání tabulek

Některé Prolog systémy, ( B-Prolog , XSB , SWI-Prolog , YAP a Ciao ), implementovat memoization metodu nazvanou stolů , které zbavují uživatele ruční ukládání mezivýsledků. Tabling je časoprostorový kompromis ; dobu provádění lze zkrátit použitím více paměti k uložení průběžných výsledků:

Dílčí cíle vyskytující se při vyhodnocování dotazů jsou udržovány v tabulce spolu s odpověďmi na tato dílčí cíle. Pokud se znovu objeví dílčí cíl, vyhodnocení znovu použije informace z tabulky, nikoli znovu provede řešení proti klauzulím programu.

Tabling lze prodloužit v různých směrech. Může podporovat rekurzivní predikáty pomocí rozlišení SLG nebo lineárního tablingu. Ve vícevláknovém systému Prolog mohly být výsledky tabelování uchovávány jako soukromé pro vlákno nebo sdílené mezi všemi vlákny. A v přírůstkových tabulkách může tabulka reagovat na změny.

Implementace v hardwaru

Během projektu Páté generace počítačových systémů došlo k pokusům implementovat Prolog do hardwaru s cílem dosáhnout rychlejšího provádění s vyhrazenými architekturami. Prolog má navíc řadu vlastností, které mohou umožnit zrychlení prostřednictvím paralelního spouštění. Novějším přístupem bylo kompilovat omezené programy Prolog do pole programovatelných hradel . Rychlý pokrok v hardwaru pro všeobecné použití však důsledně předběhl specializovanější architektury.

Omezení

Ačkoli je Prolog široce používán ve výzkumu a vzdělávání, Prolog a další logické programovací jazyky neměly významný dopad na počítačový průmysl obecně. Většina aplikací je podle průmyslových standardů malá a několik překračuje 100 000 řádků kódu. Programování ve velkém je považováno za komplikované, protože ne všechny překladače Prolog podporují moduly a mezi systémy modulů hlavních překladačů Prolog jsou problémy s kompatibilitou. Přenositelnost kódu Prolog napříč implementacemi byla také problémem, ale vývoj od roku 2007 znamenal: „přenositelnost v rámci rodiny implementací Prologu odvozených z Edinburghu/Quintusu je dostatečně dobrá, aby umožňovala udržování přenosných aplikací v reálném světě“.

Software vyvinutý v Prologu byl kritizován kvůli vysoké penalizaci výkonu ve srovnání s konvenčními programovacími jazyky. Zejména nedeterministická hodnotící strategie Prologu může být problematická při programování deterministických výpočtů nebo dokonce při použití „nezáleží na nedeterminismu“ (kde se místo zpětného sledování všech možností provádí jediná volba). K dosažení požadovaného výkonu může být nutné použít škrty a jiné jazykové konstrukce, které zničí jednu z hlavních atrakcí Prologu, schopnost spouštět programy „dozadu a dopředu“.

Prolog není čistě deklarativní: kvůli konstrukcím, jako je operátor cut , je pro jeho pochopení nutné procedurální čtení programu Prolog. Pořadí klauzulí v programu Prolog je významné, protože na něm závisí strategie provádění jazyka. Jiné logické programovací jazyky, jako například Datalog , jsou skutečně deklarativní, ale omezují jazyk. Výsledkem je, že mnoho praktických programů Prolog je napsáno tak, aby odpovídalo pořadí hledání hloubky prvního Prologu , nikoli jako čistě deklarativní logické programy.

Rozšíření

Z Prologu byly vyvinuty různé implementace k rozšíření možností logického programování v mnoha směrech. Patří sem typy , režimy, logické programování s omezením (CLP), objektově orientované logické programování (OOLP), souběžnost, lineární logika (LLP), funkce logického programování a logiky vyššího řádu plus interoperabilita se znalostními bázemi :

Typy

Prolog je netypový jazyk. Pokusy o zavedení typů pocházejí z 80. let minulého století a od roku 2008 stále existují pokusy rozšířit Prolog o typy. Informace o typu jsou užitečné nejen pro bezpečnost typu, ale také pro úvahy o programech Prolog.

Režimy

Syntaxe Prologu neurčuje, které argumenty predikátu jsou vstupy a které jsou výstupy. Tyto informace jsou však významné a doporučujeme je zahrnout do komentářů. Režimy poskytují cenné informace při zvažování programů Prolog a lze je také použít k urychlení provádění.

Omezení

Logické programování omezení rozšiřuje Prolog tak, aby zahrnoval koncepty z uspokojení omezení . Program s logikou omezení umožňuje omezení v těle klauzulí, jako například: A(X,Y) :- X+Y>0. Je vhodný pro rozsáhlé problémy kombinatorické optimalizace, a je tedy užitečný pro aplikace v průmyslovém prostředí, jako je automatické vytváření tabulek času a plánování výroby . Většina systémů Prolog je dodávána s alespoň jedním omezovačem omezení pro konečné domény a často také s řešiči pro jiné domény, jako jsou racionální čísla.

Objektová orientace

Flora-2 je objektově orientovaný systém reprezentace znalostí a uvažování založený na F-logice a zahrnuje HiLog , transakční logiku a proveditelné uvažování .

Logtalk je objektově orientovaný logický programovací jazyk, který může použít většinu implementací Prologu jako back-end kompilátor. Jako jazyk s více paradigmaty obsahuje podporu pro prototypy i třídy.

Oblog je malé, přenosné, objektově orientované rozšíření Prologu od Margaret McDougall z EdCAAD, University of Edinburgh.

Objlog byl rámcový jazyk kombinující objekty a Prolog II od CNRS, Marseille, Francie.

Prolog ++ byl vyvinut společností Logic Programming Associates a poprvé vydán v roce 1989 pro počítače MS-DOS. Byla přidána podpora pro další platformy a druhá verze byla vydána v roce 1995. Knihu o Prolog ++ od Chris Moss vydalo nakladatelství Addison-Wesley v roce 1994.

Visual Prolog je víceparadigmatický jazyk s rozhraními, třídami, implementacemi a výrazy objektů.

Grafika

Systémy Prolog, které poskytují grafickou knihovnu, jsou SWI-Prolog , Visual Prolog , WIN-PROLOG a B-Prolog .

Konkurence

Prolog-MPI je open-source rozšíření SWI-Prolog pro distribuované výpočty přes rozhraní pro předávání zpráv . Existují také různé souběžné programovací jazyky Prolog.

Webové programování

Některé implementace Prologu, zejména Visual Prolog , SWI-Prolog a Ciao , podporují webové programování na straně serveru s podporou webových protokolů, HTML a XML . Existují také rozšíření pro podporu sémantických webových formátů, jako jsou RDF a OWL . Prolog byl také navržen jako jazyk na straně klienta . Visual Prolog navíc podporuje JSON-RPC a Websockety .

Adobe Flash

Cedar je bezplatný a základní tlumočník Prologu. Od verze 4 a výše má Cedar podporu FCA (Flash Cedar App). To poskytuje novou platformu pro programování v Prologu pomocí ActionScriptu .

jiný

• F-logic rozšiřuje Prolog o rámce/objekty pro reprezentaci znalostí .
• Transakční logika rozšiřuje Prolog o logickou teorii stavových operátorů aktualizace. Má jak modelovou teoretickou, tak procedurální sémantiku.
• OW Prolog byl vytvořen s cílem reagovat na nedostatek grafiky a rozhraní Prologu.

Rozhraní do jiných jazyků

Existují rámce, které mohou překlenout mezi Prologem a jinými jazyky:

• LPA Intelligence Server umožňuje vkládání LPA Prolog pro Windows v C, C #, C ++, Java, VB, Delphi, .NET, Lua, Python a jiné jazyky. Využívá vyhrazený datový typ řetězce, který poskytuje LPA Prolog
• Rozhraní Logic Server API umožňuje jak rozšíření, tak vložení Prologu do jazyků C, C ++, Java, VB, Delphi, .NET a jakéhokoli jazyka/prostředí, které lze volat .dll nebo .so. Je implementován pro Amzi! Prolog Amzi! Prolog + Logic Server, ale specifikaci API lze zpřístupnit pro jakoukoli implementaci.
• JPL je obousměrný most Java Prolog, který je standardně dodáván se softwarem SWI-Prolog, což umožňuje vzájemné volání jazyků Java a Prolog (rekurzivně). Je známo, že má dobrou podporu souběžnosti a je v aktivním vývoji.
• InterProlog , most programovací knihovny mezi Javou a Prologem, implementující obousměrné volání predikátu/metody mezi oběma jazyky. Objekty Java lze mapovat do výrazů Prolog a naopak. Umožňuje vývoj GUI a dalších funkcí v Javě a ponechává logické zpracování ve vrstvě Prolog. Podporuje XSB , s podporou SWI-Prolog a YAP plánovanou na rok 2013.
• Prova poskytuje integraci nativní syntaxe s Javou, zasíláním zpráv agentům a pravidly reakce. Prova se staví jako skriptovací systém (RBS) založený na pravidlech pro middleware. Jazyk přináší nové základy v kombinaci imperativního a deklarativního programování .
• PROL Integrovatelný engine Prolog pro Javu. Obsahuje malé IDE a několik knihoven.
• GNU Prolog for Java je implementací ISO Prolog jako knihovny Java (gnu.prolog)
• Ciao poskytuje rozhraní pro C, C ++, Java a relační databáze.
• C#-Prolog je překladač Prolog napsaný v (spravovaném) C#. Lze snadno integrovat do programů C#. Charakteristika: spolehlivý a poměrně rychlý tlumočník, rozhraní příkazového řádku, rozhraní Windows, vestavěný DCG, predikáty XML, predikáty SQL, rozšiřitelné. K dispozici je kompletní zdrojový kód včetně generátoru analyzátoru, který lze použít k přidávání rozšíření pro speciální účely.
• Warrenův abstraktní stroj pro PHP Kompilátor a překladač Prolog v PHP 5.3. Knihovna, kterou lze použít samostatně nebo v rámci Symfony2.1, která byla přeložena z práce Stephana Buettchera v Javě, kterou najdete [zde stefan .buettcher .org /cs /wam /index .html ]
• tuProlog je lehký systém Prolog pro distribuované aplikace a infrastruktury, záměrně navržený kolem minimálního jádra, který má být buď staticky nebo dynamicky konfigurován načítáním/vykládáním knihoven predikátů. tuProlog nativně podporuje programování s více paradigmaty a poskytuje čistý, bezproblémový integrační model mezi Prologem a mainstreamovými objektově orientovanými jazyky-jmenovitě Java, pro verzi Java tuProlog, a jakýkoli jazyk založený na .NET (C#, F#..), pro tuProlog. NET verze.

Dějiny

Název Prolog zvolil Philippe Roussel jako zkratku pro programmation en logique ( francouzština pro programování v logice ). Byl vytvořen kolem roku 1972 Alainem Colmerauerem s Philippem Rousselem na základě procedurální interpretace Hornových doložek Roberta Kowalského . Částečně to bylo motivováno touhou sladit používání logiky jako deklarativního jazyka reprezentace znalostí s procedurální reprezentací znalostí, které byly populární v Severní Americe na konci 60. a na začátku 70. let. Podle Roberta Kowalského byl první systém Prolog vyvinut v roce 1972 Colmerauerem a Phillipe Rousselem. První implementací Prologu byl tlumočník napsaný ve Fortranu Gerardem Battani a Henri Meloni. David HD Warren vzal tohoto tlumočníka do Edinburghu a tam implementoval alternativní front-end, který definoval syntaxi „Edinburgh Prolog“ používanou většinou moderních implementací. Warren také implementoval první kompilátor pro Prolog a vytvořil vlivný DEC-10 Prolog ve spolupráci s Fernandem Pereirou. Warren později zobecnil myšlenky za DEC-10 Prolog, aby vytvořil Warren Abstract Machine .

Evropští vědci AI upřednostňovali Prolog, zatímco Američané upřednostňovali Lisp , což údajně vyvolávalo mnoho nacionalistických debat o výhodách jazyků. Hodně z moderního vývoje Prologu pocházelo z podnětu projektu Páté generace počítačových systémů (FGCS), který pro svůj první operační systém vyvinul variantu Prologu s názvem Kernel Language .

Pure Prolog byl původně omezen na použití prověrky věty o rozlišení s klauzulemi Horn ve tvaru:

H :- B1, ..., Bn.

Aplikace věty považuje takové doložky za postupy:

to show/solve H, show/solve B1 and ... and Bn.

Čistý Prolog byl brzy rozšířen, aby zahrnoval negaci jako selhání , ve kterém jsou negativní podmínky formy ne (B _i ) ukázány pokusem a neúspěchem vyřešit odpovídající pozitivní podmínky B _i .

Následná rozšíření Prologu původním týmem zavedla do implementací schopnosti logiky programování omezení .

Použití v průmyslu

Prolog byl použit ve Watsonu . Watson používá software DeepQA společnosti IBM a rámec Apache UIMA ( Unstructured Information Management Architecture). Systém byl napsán v různých jazycích, včetně jazyků Java, C ++ a Prolog, a běží na operačním systému SUSE Linux Enterprise Server 11 využívajícím rámec Apache Hadoop k poskytování distribuovaných počítačů. Prolog se používá pro párování vzorů nad stromy analyzovanými přirozeným jazykem. Vývojáři uvedli: „Vyžadovali jsme jazyk, ve kterém bychom mohli pohodlně vyjadřovat pravidla shody vzorů nad stromy analýzy a dalšími anotacemi (například výsledky rozpoznávání pojmenovaných entit), a technologií, která by mohla tato pravidla velmi efektivně provádět. Zjistili jsme, že Prolog byla ideální volbou pro jazyk díky jeho jednoduchosti a expresivitě. “ Prolog je používán v Low-Code Development Platform GeneXus , která se zaměřuje na AI. Open source grafová databáze TerminusDB je implementována v prologu. TerminusDB je navržen pro společné vytváření a správu grafů znalostí .

Viz také

• Porovnání implementací Prologu
• Logicko-lingvistické modelování . Metoda pro budování systému založeného na znalostech, který používá Prolog.
• Programování sady odpovědí . Plně deklarativní přístup k logickému programování.
• Asociace pro logické programování

Související jazyky

• Jazyk Gödel je silně typovaná implementace souběžného programování logiky omezení . Je postaven na SICStus Prolog.
• Visual Prolog , dříve známý jako PDC Prolog a Turbo Prolog, je silně typovaný objektově orientovaný dialekt Prologu, který se velmi liší od standardního Prologu. Jako Turbo Prolog byl uveden na trh společností Borland, ale nyní jej vyvíjí a prodává dánská firma PDC (Prolog Development Center), která jej původně vyrobila.
• Datalog je podmnožinou Prologu. Je omezena na vztahy, které mohou být stratifikované a neumožňuje složené termíny. Na rozdíl od Prologu není Datalog dokončen Turingem .
• Merkur je odnož Prologu zaměřená na softwarové inženýrství ve velkém se statickým systémem polymorfního typu a také režimem a systémem determinismu.
• GraphTalk je patentovaná implementace Warrenova abstraktního stroje s dalšími objektově orientovanými vlastnostmi.
• V některých ohledech je Prolog podmnožinou Planneru . Myšlenky v Planneru byly později dále rozvinuty v metaforě Vědecké komunity .
• AgentSpeak je variantou Prologu pro programování chování agentů v systémech s více agenty .
• Erlang začal život implementací založenou na Prologu a udržuje velkou část syntaxe založené na sjednocení Prologu.
• Pilog je deklarativní jazyk postavený na PicoLispu , který má sémantiku Prologu, ale používá syntaxi Lispu.

Reference

Další čtení