What does & # 8594; mean in the prologue?

Question

What does --> mean in Prolog?

Could you give one specific example and explain how it works?

Answer 1

hardmath has already explained a lot. But the more fascinating thing about DCG is that although the → / 2 syntax offers context-free grammars, it's actually more. You can also model more complex languages ​​with attributes that are just parameters for non-terminals.

Here is a DCG that generates and accepts the language L = {a ^ nb ^ nc ^ n}. 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 uses the so-called auxiliary conditions (*) covered by {}, it is a regular code, alternating in DCG. And for the bidirectional use of DCG, we used CLP (FD) instead of the usual arithmetic. Here are some examples 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 go around the state. They allow the form of Monads in Prolog. Just replace the input list and output list with the input state and output state.

Bye

(*) Early publication of DCG:

Pereira, F.K.N. and Warren, DHD (1980):
Certain cluster grammars for language analysis -
Formalism review and comparison with
Extended Transition Networks, North Holland
Publishing Company, Artificial Intelligence, 13, 231 - 278

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

Answer 2

The --> symbol --> used in many Prolog implementations to create Declarative Clause (DCG) grammar rules that take the form:

 head --> body. 

similar to the usual 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 shortcut for creating rules that link lists to different Prolog structures. Often, DCG rules are used for a rather limited purpose of list analysis.

The question asked here is to give a simple usage example --> , in other words, showing how DCG rules work in a simple case. The head of the DCG rule is effectively a predicate of the underlying Prolog rule with two additional arguments that are a list of differences, namely one list presented as a longer list, minus some end part of this longer list.

Here's a DCG example taken from the DCI SWI-Prolog tutorial adapted by Anne Oborn from the Marcus Trisk textbook cited in a comment by Boris :

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

To distinguish this from the usual Prolog predicate, we denote this as//0 , but it is equivalent to the normal Prolog predicate with two additional arguments. We can query the basic Prolog predicate directly by providing two additional arguments:

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

This succeeds because the difference between the two lists (which is again an empty list) is in the order as//0 . Also:

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

succeeds because the difference between the two lists is [a] , which is quite consistent with recursion with as//0 .

Another way to use as//0 is the built-in predicate Prolog phrase/2 , which takes a DCG header as a first argument and a list as a second argument. In this case, phrase/2 will generate lists matching as//0 :

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

etc. until you complete a successful request by clicking on return.

This example also works with Amzi! Prologue with slight differences in output.