Prolog - Recursive with facts

Question

Firstly, I want to mention that this question was asked in a previous exam but I don't quite understand the answer. I just need someone to shed some light.

The code is decribed as follow :

state( 1, f, 2 ).
state( 2, o, 3 ).
state( 2, l, 4 ).
state( 3, n, 5 ).
state( 3, r, 6 ).
state( 4, o, 7 ).
state( 5, d, 8 ).
state( 6, t, 9 ).
state( 6, m, 10 ).
state( 7, u, 11 ).
state( 8, u, 12 ).
state( 10, e, 13 ).

find_( Y1, [ L | ES ], X ) :-
    state( Y1, L, Y2 ),
    find_( Y2, ES, X ).
find_( Y, [], Y ).

Let's say we call find_(1, Z, 9) the answer will be Z = [f,o,r,t].

Before the recursive call, is it going to unify with all possible value for Y2 ? If so, why the answer is not including the l from the second unification for state( 2, l, 4).

I've tried the trace mode, but that didn't help me much.

Thanks.

Guy Coder Guy Coder · Accepted Answer · 2018-04-18T21:48:53

If you draw the state facts as a graph of nodes and edges you get.

Now the query ask for a path from 1 to 9 and the result is a list of the edges from 1 to 9. They are colored green. The edges are f,o,r,t.

Sometimes trying to understand the problem as Prolog is harder than trying to understand the problem in a different manner. As I often note when stuck one option that often helps is to get out a pen and paper.

Before the recursive call, is it going to unify with all possible value for Y2 ?

No. Prolog unifies the predicates/facts in the order they are written and then backtracks to the next one upon failure. So state(2,o,3) is tried first and succeeds for which the answer is printed. Then because there is a choice point for state(2,_,_) for which state(2,l,4) is then selected. However this eventually fails and thus is not included as a separate answer.

TL;DR

I built the graph using graphviz dot with the file

so_question_07.gv

digraph so_question_07 {


    node_01 [label="1", color="green", fontcolor="green"];
    node_02 [label="2", color="green", fontcolor="green"];
    node_03 [label="3", color="green", fontcolor="green"];
    node_04 [label="4"];
    node_05 [label="5"];
    node_06 [label="6", color="green", fontcolor="green"];
    node_07 [label="7"];
    node_08 [label="8"];
    node_09 [label="9", color="green", fontcolor="green"];
    node_10 [label="10"];
    node_11 [label="11"];
    node_12 [label="12"];
    node_13 [label="13"];

    color=black;

    node_01 -> node_02 [label="f",shape=oval, color="green", fontcolor="green"];
    node_02 -> node_03 [label="o",shape=oval, color="green", fontcolor="green"];
    node_02 -> node_04 [label="l",shape=oval];
    node_03 -> node_05 [label="n",shape=oval];
    node_03 -> node_06 [label="r",shape=oval, color="green", fontcolor="green"];
    node_04 -> node_07 [label="o",shape=oval];
    node_05 -> node_08 [label="d",shape=oval];
    node_06 -> node_09 [label="t",shape=oval, color="green", fontcolor="green"];
    node_06 -> node_10 [label="m",shape=oval];
    node_07 -> node_11 [label="u",shape=oval];
    node_08 -> node_12 [label="u",shape=oval];
    node_10 -> node_13 [label="e",shape=oval];
}

Here is a simple batch file to covert the gv file to an svg

SET PATH="C:\Program Files (x86)\Graphviz2.38\bin";PATH=%PATH%

dot -Tsvg so_question_07.gv -o so_question_07.svg

Prolog - Recursive with facts

1 Answers