Что значит -> означает в прологе?

Question

Что делает --> в Prolog?

Не могли бы вы привести один конкретный пример и объяснить, как он работает?

Answer 1

Символ --> используется во многих реализациях Пролога для создания декларативного Clause грамматики (DCG) правила, которые принимают форму:

head --> body. 

по аналогии с обычными правилами Пролога:

head :- body. 

В факт, что каждое правило DCG может быть переведено в нормальное правило Prolog (и является внутренним), но синтаксис DCG служит удобным и очень мощным сокращением для создания правил, которые связывают списки с различными структурами Prolog. Часто правила DCG используются для довольно ограниченной цели анализа списков.

Заданный здесь вопрос состоит в том, чтобы дать простой пример использования -->, другими словами, показывая, как правила DCG работают в простом случае. Глава правила DCG эффективно является предикатом лежащего в основе правила Prolog с двумя дополнительными аргументами, которые представляют собой список разностей , а именно один список, представленный как более длинный список за вычетом некоторой конечной части этого более длинного списка.

Вот пример DCG взят из SWI-Prolog DCG tutorial адаптированной Энн Ogborn из учебника Маркус Tříska given in Boris's Comment:

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

Чтобы отличить это от нормального Прологе предикат мы будем обозначать это as//0, но это эквивалентно нормальный предикат Пролога с двумя дополнительными аргументами. Мы можем запросить лежащий в основе Пролог предикат непосредственно снабжая два дополнительных аргумента:

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

Это преуспевает, потому что разница между этими двумя списками (что опять-таки пустой список) в порядке согласно as//0. Также:

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

успешно, так как разница между этими двумя списками есть [a], который хорошо рекурсия с as//0.

Другой способ использования as//0 со встроенным предикатом Prolog phrase/2, который принимает в качестве первого аргумента заголовок DCG и как второй аргумент списка. В этом случае phrase/2 будет генерировать списки, которые удовлетворяют as//0:

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

и так далее, пока вы не завершите запрос успешно ударяя возврат.

Этот пример также работает с Amzi! Пролог с незначительными различиями в производительности.

Answer 2

hardmath уже много объяснил. Но более увлекательная вещь о DCG заключается в том, что, хотя синтаксис ->/2 предлагает контекстно-свободные грамматики, это на самом деле больше. Можно также моделировать более сложные языки благодаря атрибутам, которые являются просто параметрами для нетерминалов.

Вот DCG, который генерирует и принимает язык L = {a^n b^n c^n}.DCG гласит:

:- 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) --> []. 

выше код делает использование так называемых дополнительных условий (*), охватываемых {}, это нормальный код перемежаются в DCG. И для двунаправленного использования DCG мы использовали CLP (FD) вместо обычной арифметики. Вот несколько примеров работает в SWI-Пролог:

?- 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] 

Но на практике DCGs также часто из-за их способности пропускать вокруг государства. Они позволяют форме Монад в Прологе. Просто замените список ввода и список вывода на состояние ввода и состояние вывода.

Bye

(*) ранний документ содействия DCG является:

Pereira, F.C.N. и Уоррен, D.H.D. (1980):
Определённые Параграф грамматик для языка анализа -
обследования формализма и сравнения с
Augmented Transition Networks, North-Holland
Publishing Company, Искусственный интеллект, 13, 231 - 278

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