Co oznacza -> znaczy w prologu?

Question

Co oznacza --> w Prolog?

Czy możesz podać konkretny przykład i wyjaśnić, jak to działa?

Answer 1

Symbol --> jest stosowany w wielu implementacjach prologowych tworzyć deklaratywnej klauzula gramatyki (DCG) zasady, które przyjmują postać:

head --> body. 

jako analogiczną do normalnych zasad prologowych:

head :- body. 

W Fakt, że każda reguła DCG może zostać przetłumaczona na normalną regułę Prolog (i jest wewnętrznie), ale składnia DCG służy jako wygodny i bardzo silny skrót do tworzenia reguł, które odnoszą listy do różnych struktur Prolog. Często zasady DCG są używane do dość ograniczonego celu analizowania list.

Podane tutaj pytanie dotyczy prostego przykładu użycia -->, innymi słowy pokazania, w jaki sposób zasady DCG działają w prostym przypadku. Szef reguły DCG jest faktycznie predykatem podstawowej reguły Prolog z dwoma dodatkowymi argumentami, które reprezentują listę różnicową, a mianowicie jedna lista jest reprezentowana jako dłuższa lista minus część końcowa tej dłuższej listy.

Oto przykład DCG zaczerpnięte z SWI-Prolog DCG tutorial przystosowanym przez Ann Ogborn z samouczka przez Markusa Triska given in Boris's Comment:

as --> [ ].   % empty list is okay 
as --> [a], as.  % list [a|T] is okay iff T is okay 

aby odróżnić to od normalnego Prolog predykatu oznaczymy to as//0, ale to jest równoważne z normalny predykat Prologu z dwoma dodatkowymi argumentami. Możemy kwerendy stanowiącego podstawę Prolog predykatu bezpośrednio poprzez dostarczanie dwóch dodatkowych argumentów:

?- as([ ],[ ]). 
true 

się powiedzie, ponieważ różnica pomiędzy tymi dwoma listami (co jest znowu pusta lista) jest w porządku według as//0. Też:

?- as([a],[ ]). 
true 

powiedzie się, ponieważ różnica pomiędzy tymi dwoma listami jest [a], który jest w porządku przez rekursji z as//0.

Innym sposobem użycia as//0 jest wbudowany predykat Prologu phrase/2, który jako pierwszy argument przyjmuje nagłówek DCG, a jako drugi argument - listę. W tym przypadku phrase/2 wygeneruje list, które spełniają as//0:

?- phrase(as, Ls). 
Ls = '[]' ; 
Ls = [a] ; 
Ls = [a, a] ; 
Ls = [a, a, a] ; 

i tak dalej, aż do zakończenia zapytania pomyślnie trafiając zwrotu.

Ten przykład działa również z Amzi! Prolog z niewielkimi różnicami w wynikach.

Answer 2

hardmath już wiele wyjaśnił. Ale bardziej fascynujące w DCG jest to, że chociaż składnia ->/2 sugeruje gramatykę bezkontekstową, to w rzeczywistości jest bardziej. Można również modelować bardziej złożone języki dzięki atrybutom, które są po prostu parametrami dla nie-terminali.

Oto DCG, który generuje i akceptuje język L = {a^n b^n c^n}.DCG brzmi:

:- use_module(library(clpfd)). 

start(N) --> as(N), bs(N), cs(N). 

as(N) --> {N #> 0, M #= N-1}, [a], as(M). 
as(0) --> []. 

bs(N) --> {N #> 0, M #= N-1}, [b], bs(M). 
bs(0) --> []. 

cs(N) --> {N #> 0, M #= N-1}, [c], cs(M). 
cs(0) --> []. 

Powyższy kod umożliwia zastosowanie tak zwanych warunkach pomocniczych (*) przyjętej {} jest normalnie kod przeplatane do DCG. Aby umożliwić dwukierunkowe wykorzystanie DCG, używaliśmy CLP (FD) zamiast zwykłej arytmetyki. Oto kilka przykładów biegnie w SWI-Prolog:

?- phrase(start(X),[a,a,a,b,b,b,c,c,c]). 
X = 3 
?- phrase(start(3),Y). 
Y = [a,a,a,b,b,b,c,c,c] 

ale w praktyce DCGs są również często ze względu na ich zdolność do podejmowania całego państwa. Pozwalają one na formę monad w Prologu. Wystarczy zastąpić listę wejściową i listę wyjściową stanem wejściowym i stanem wyjściowym.

Bye

(*) Wczesnym papier promowanie DCG jest:

Pereira, F.C.N. i Warren, D.H.D. (1980):
Wyraźne Gramatyki klauzulą ​​Language Analysis -
sondażu formalizmu i porównania z
Augmented Transition Networks, North-Holland
Publishing Company, sztuczna inteligencja, 13, 231 - 278

http://cgi.di.uoa.gr/~takis/pereira-warren.pdf