prologdcg

Prolog parse tree generation fails


I have the following prolog rules.

b(b(true)) --> [true].
b(b(false)) --> [false].
b(b(E,[=],E)) --> e(E),[=],e(E).
b(b([not],B)) --> [not],b(B).
e(e(I)) --> i(I).
e(e(N)) --> n(N).
e(e(N,O,E)) --> n(N),o(O),e(E).
e(e(I,O,E)) --> i(I),o(O),e(E).
o(o(+)) --> [+].
o(o(-))--> [-].
o(o(*))--> [*].
o(o(/)) --> [/].
i(i(x)) --> [x].
i(i(y)) --> [y].
i(i(z)) --> [z].
i(i(u)) --> [u].
i(i(v)) --> [v].
n(n(0)) --> [0].
n(n(1)) --> [1].
n(n(2)) --> [2].
n(n(3)) --> [3].
n(n(4)) --> [4].
n(n(5)) --> [5].
n(n(6)) --> [6].
n(n(7)) --> [7].
n(n(8)) --> [8].
n(n(9)) --> [9].

But I dunno why

[6] 26 ?- b(A,[x,=,4],[]).
false

fails. I tried to debug the code. 4 is not getting matched with n(n(4)). I couldn't understand wat the problem is.


Solution

  • (You would have received an answer much earlier if you would have used the tag instead)

    So, how can we localize the error? Let's start with your query:

    ?- phrase(b(A),[x,=,4]).
       false.
    

    Bad!
    Shall I really fire up a trace/debugger?
    What you are currently asking is: What are the solutions for A for a well-formed sentence.
    Alas, there is none.

    Can't we ask Prolog a more general question?
    So, dear Prolog - at least - do you know any sentence?
    Please say a word!

    ?- phrase(b(A),L).
       A = b(true), L = [true]
    ;  A = b(false), L = [false]
    ;  ... .
    

    So there is something - I will remove the A, because we want to see the sentences, first.

    ?- phrase(b(_),L).
       L = [true]
    ;  L = [false]
    ;  L = [x,=,x]
    ;  L = [y,=,y]
    ;  L = [z,=,z]
    ;  L = [u,=,u]
    ;  L = [v,=,v]
    ;  L = [0,=,0]
    ;  L = [1,=,1]
    ;  L = [2,=,2]
    ;  L = [3,=,3]
    ;  L = [4,=,4]
    ;  L = [5,=,5]
    ;  L = [6,=,6]
    ;  L = [7,=,7]
    ;  L = [8,=,8]
    ;  L = [9,=,9]
    ;  L = [0,+,x,=,0,+,x]
    ;  ... .
    

    Do you see a pattern here?
    Maybe we can refine this.
    What are the sentences of length 3 you know of?

    ?- L = [_,_,_], phrase(b(_),L).
      L = [x,=,x]
    ;  L = [y,=,y]
    ;  L = [z,=,z]
    ;  L = [u,=,u]
    ;  L = [v,=,v]
    ;  L = [0,=,0]
    ;  L = [1,=,1]
    ;  L = [2,=,2]
    ;  L = [3,=,3]
    ;  L = [4,=,4]
    ;  L = [5,=,5]
    ;  L = [6,=,6]
    ;  L = [7,=,7]
    ;  L = [8,=,8]
    ;  L = [9,=,9]
    ;  L = [not,not,true]
    ;  L = [not,not,false]
    ;  false.
    

    In other words: There are no other three word sentences than those.
    Now, do you get it?
    There is a rule for sentences with =:

    b(b(E,[=],E)) -->
       e(E),[=],e(E).
    

    It requires that the expression on the left-hand side is the same as the expression on the right-hand side. Therefore only those sentences above.


    When debugging a Prolog program, there is much less need to type (on the keyboard) test data than in other languages. Instead, use variables to let Prolog fill-in-the-variables. After all, Prolog is much faster on that than we are ; and it does not suffer CTS.