CODEWITHSUNDEEP
prologdcgsuccessor-arithmetics
RHK-S8
RHK-S8

Reputation: 329

Can someone explain how to do unification to get the answer in a definite clause grammar?

I am trying to understand the concept of unification within definite clause grammar, is someone able to explain step by step how one gets from the following DCG to the answer.

s --> symbols(Sem,a), symbols(Sem,b).

symbols(s(end),S) --> [S].
symbols(s(Sem),S) --> [S], symbols(Sem,S).

The answer produces aaabbb, but i have been searching the web for ages to try and find how you get this answer, i would be forever grateful if someone could explain this in a few steps, or at least show the working out, so i can see what is happening.

A similar example can be found on the wikipedia page for DCG's, except it produces aaabbbccc.

Thanks

Upvotes: 1

Views: 117

Answers (2)

false
false

Reputation: 10142

Start by asking about all possible sentences. You could, for example take the most general query:

?- phrase(s,L).
   L = [a,b]
;  L = [a,a,b,b]
;  L = [a,a,a,b,b,b]      % this is your example
;  L = [a,a,a,a,b,b,b,b]
; ... .

In general, however, this method might enumerate answers/solutions in an unfair manner ; thereby hiding shorter examples. To ensure that you will find all solutions ordered by length:

?- length(L,N), phrase(s,L).

In this case, there is no difference. But think of adding the rule symbol(0,_) --> []. after all the other rules. L = [] would not show in the first query, it is "hidden by infinitely many solutions", but it would show as first solution in the second one.

So before trying to understand the more complex example you gave, consider [a, b] since it is the simplest example.

Another approach is to dissect the query phrase(s, L) and consider each of its constituents:

?- phrase(symbols(Sem,a),L).
   Sem = s(0), L = [a]
;  Sem = s(s(0)), L = [a,a]
;  Sem = s(s(s(0))), L = [a,a,a]
;  ... .

So this part plus the same with b describes the entire sentence.

Upvotes: 2

danielp
danielp

Reputation: 1187

The predicate symbols takes N times S from the list. But the N is not encoded as "normal" numbers, they are encoded like numbers in peano arithmetic: end is 0 (usually 0 is used instead of end) and s(N) means N+1.

The clause

symbols(s(end),S) --> [S].

takes one element S. We can interpret s(end) as a term representing the number one.

The clause

symbols(s(Sem),S) --> [S], symbols(Sem,S).

takes one element S and recursively calls symbols with the same element. Again, we interpret s(Sem) as a number: Then it means: To take N+1 (s(Sem)) elements S, first take one S, then recursively take N elements S.

The predicate s just takes a number of as, then the same number of bs.

The first solution is actually ab because symbols(Sem,a) matches with the first rule and unifies Sem with s(end). Then symbols(s(end),b) is called and the only matching rule is the first one.

Upvotes: 1

Related Questions