What does --> mean in Prolog?
Could you provide one concrete example and explain how it works?
5
votes
2 Answers
4
votes
hardmath has already explained a lot. But the more fascinating thing about DCG is, that although the -->/2 syntax suggests context free grammars, its actually more. One can also model more complex languages thanks to attributes, which are simply parameters to the non-terminals.
Here is a DCG that generates and accepts the language L = {a^n b^n c^n}. The DCG reads as follows:
:- 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) --> [].
The above code makes use of a so called auxiliary conditions(*), embraced by {}, this is normal code interspersed into the DCG. And to allow bidirectional use of the DCG we were using CLP(FD) instead of ordinary arithmetic. Here are some example runs in 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]
But in practice DCGs are also often found because of their ability to pass around state. They allow a form of monads in Prolog. Just replace the input list and the output list with input state and output state.
Bye
(*) An early paper promoting DCG is:
Pereira, F.C.N. and Warren, D.H.D. (1980):
Definite Clause Grammars for Language Analysis –
A Survey of the Formalism and a Comparison with
Augmented Transition Networks, North-Holland
Publishing Company, Artificial Intelligence, 13, 231 – 278
0
votes
The symbol --> is used in many Prolog implementations to create Declarative Clause Grammar (DCG) rules, which take the form:
head --> body.
as analogous to normal Prolog rules:
head :- body.
In fact every DCG rule can be translated into a normal Prolog rule (and is, internally), but the DCG syntax serves as a convenient and very powerful shorthand for creating rules that relate lists to a variety of Prolog structures. Often DCG rules are used for a fairly limited purpose of parsing lists.
The Question posed here is to give a simple example of the use of -->, in other words showing how DCG rules work in a simple case. The head of a DCG rule is effectively a predicate of an underlying Prolog rule with two extra arguments that represent a difference list, namely one list represented as a longer list minus some trailing portion of that longer list.
Here's a DCG example taken from the SWI-Prolog DCG tutorial adapted by Ann Ogborn from the tutorial by Markus Triska given in Boris's Comment:
as --> [ ]. % empty list is okay
as --> [a], as. % list [a|T] is okay iff T is okay
To distinguish this from a normal Prolog predicate we denote this as//0, but it is equivalent to a normal Prolog predicate with two additional arguments. We can query the underlying Prolog predicate directly by supplying the two additional arguments:
?- as([ ],[ ]).
true
This succeeds because the difference between the two lists (which is again an empty list) is okay according to as//0. Also:
?- as([a],[ ]).
true
succeeds because the difference between the two lists is [a], which is okay by recursion with as//0.
Another way to use as//0 is with the built-in Prolog predicate phrase/2, which takes as a first argument a DCG head and as a second argument a list. In this case phrase/2 will generate lists that satisfy as//0:
?- phrase(as, Ls).
Ls = '[]' ;
Ls = [a] ;
Ls = [a, a] ;
Ls = [a, a, a] ;
and so on, until you terminate the query successfully by hitting return.
This example also works with Amzi! Prolog with only minor differences in output.
