I'm working on writing a DCG that would take strings in the form of u2v where u and v do not have to be of equal length and the number of 0's in u must be the same as the number of 1's in v.
So far I've been able to write several grammars that work on paper but when I code them and try a query I typically end up with a loop somewhere. This is the closest I've been able to get:
s-->[2].
s-->u,[0],n.
s-->u,s,v.
n-->s,[1],v.
u-->[1],u.
u-->[].
v-->[0],v.
v-->[].
I can get the correct answers for the query s([0,1,1,2,0,0,1,0],N). which would be:
N = [] ;
N = [0]
But it doesn't terminate with false after as it should. Instead it just repeats those answers. My knowledge of Prolog is pretty limited and I've been mostly self teaching from LPN, so I'm guessing this is more an issue of me not understanding how Prolog evaluates these kinds of things. If someone could explain why it won't terminate, that would be most helpful.
What an interesting problem!
What immediately comes to mind for me is that you want to utilize the structure of your grammar. For instance, to match parentheses you have to do something along the lines of this:
expr --> [].
expr --> ['('], expr, [')'].
That way, either you have whatever goes between parens, or you have a left and a right paren, every time.
I don't see an obvious way to achieve this kind of breakdown with this problem. There might be a way, but I don't see what it is. However, DCGs have the almost-supernatural ability to propagate information around between different locations in the parse, thanks to the way Prolog's variables work, and that's by creating parameters to the DCG rules, like so:
rule(Stuff) --> ...
Anyway, the next snafu is that you're wanting to count something, which means arithmetic might be involved. However! We can cheat a little bit by using Peano numbers, since all we really care about is that they happen to equal each other on both sides, we don't really need to pass the result back to the user.
Without further ado, here's the solution I came up with:
u2v --> u2v(_).
u2v(N) --> u(N), [2], v(N).
u(0) --> [].
u(s(N)) --> [0], u(N).
u(N) --> [X], { member(X, [1,2,3,4,5,6,7,8,9]) }, u(N).
v(0) --> [].
v(s(N)) --> [1], v(N).
v(N) --> [X], { member(X, [0,2,3,4,5,6,7,8,9]) }, v(N).
I'm sure there are nicer ways to write this code (there may even be totally superior approaches) but this one does seem to work in my limited testing. It would even generate, except for the pesky unbounded recursion on both sides.
The crux of the solution is this line:
u2v(N) --> u(N), [2], v(N).
In fact, you don't need to keep the N, but I found it useful for debugging. The essential thing here is that u(N) matches v(N). Then both u//1 and v//1 have the same structure: first, a base-case of matching nothing, then an inductive case that matches the desired number and increments the count, Peano-style (0, s(0), s(s(0)), s(s(s(0))), ...), and then an alternate inductive case that matches the other digits and propagates the previous count forward.
It would probably be possible to do this with succ/2 instead of this, but I worry about where one would need to place the bit of pure Prolog to make it go. Going this route with Peano seemed simpler to me. (There's probably even a clpfd approach.)
Anyway, I hope this helps!
It looks to me like the OP is assuming that only 0s, 1s and 2s occur in the input. On that assumption, here is a variant of Daniel Lyons' suggestion:
u2v --> u(N),[2],v(N).
u(0) --> [].
u(N) --> [1], u(N).
u(N) --> [0], u(N1), { N1 #= N - 1 }.
v(0) --> [].
v(N) --> [0], v(N).
v(N) --> [1], v(N1), { N1 #= N - 1 }.
The OP's test case produces this in SWI-Prolog 7.6.4:
?- phrase(u2v, [0,1,1,2,0,0,1,0]).
true ;
false.
I confess that I am too new at this to understand why I don't just get 'true.' as the result.
