# Prolog Programming for Artificial Intelligence (4th Edition) (International Computer Science Series)

This Month Stack Overflow 1

It isn't giving me that output and I don't know why.

``````?- solve(a,S).
S = [g, b, a] ;
``````

The problem is not the answer the code gives, but I believe in your understanding of either how the algorithm works or the layout of the graph from the facts.

Using paper and pen to work on a problem before converting it to code is a wise decision.

Here is the graph in a visual form with the root (`a`) at the top.

``````        a               Level 0
/     \
b         c          Level 1
/   \     /   \
g     f   r     e       Level 2
``````

Notice that the shortest path from `a` to `g` is `a`,`b`,`g` and not `a`,`b`,`c`,`g` as you expect. Even though `c` is connected to `a`, it is not on the path from `a` to `g` and so is not part of the solution.

You are correct in that with Breadth First Search (BFS) you start at `Level 0` then process ALL the nodes connected to it, which are shown at `Level 1`. Then do the same for each node in `Level 1` creating `Level 2` before repeating again for each new level.

In processing each node, BFS just looks for any node connected to that current node that it has not visited already and records any information it needs in a table or other data structure. If your example included weights on each vertex then the cost to get to the current node being processed would be recorded with the current node in the data structure. Visiting a node for processing a node is not the same as visiting a node as part of the shortest path from one node to another.

Another way to think about this is that both BFS and Depth First Search (DFS) should both give the same answers, the difference is in the algorithm. If you use DFS on this you will get the same answer of `a`,`b`, and `g`, without `c`.

``````dfs_1(N,N,[N]).
dfs_1(Start,End,[Start|Rest] ) :-
s(Start,Next),
dfs_1(Next,End,Rest).

?- dfs_1(a,g,Path).
Path = [a, b, g] ;
false.
``````

From comment:

Okay, I see, so the actual working of the algorithm is as I printed it including c, but then when it wants to print the final path, it will exclude c since it's not on the path.

I would not agree with that.

In running the query with trace on in SWI-Prolog

``````line   1   [trace] 133 ?- solve_1(a,S).
line   2      Call: (8) solve_1(a, _12870)
line   3      Call: (9) breadthfirst_1([[a]], _12870)
line   4      Call: (10) goal_1(a)
line   5      Fail: (10) goal_1(a)
line   6      Redo: (9) breadthfirst_1([[a]], _12870)
line   7   ^  Call: (10) bagof([_13076, a],  (s(a, _13076), \+member(_13076, [a])), _13134)
line   8      Call: (17) s(a, _13076)
line   9      Exit: (17) s(a, b)
line  10      Call: (17) lists:member(b, [a])
line  11      Fail: (17) lists:member(b, [a])
line  12      Redo: (17) s(a, _13076)
line  13      Exit: (17) s(a, c)
line  14      Call: (17) lists:member(c, [a])
line  15      Fail: (17) lists:member(c, [a])
line  16   ^  Exit: (10) bagof([_13076, a], user:(s(a, _13076), \+member(_13076, [a])), [[b, a], [c, a]])
line  17      Call: (10) lists:append([], [[b, a], [c, a]], _13216)
line  18      Exit: (10) lists:append([], [[b, a], [c, a]], [[b, a], [c, a]])
line  19      Call: (10) breadthfirst_1([[b, a], [c, a]], _12870)
line  20      Call: (11) goal_1(b)
line  21      Fail: (11) goal_1(b)
line  22      Redo: (10) breadthfirst_1([[b, a], [c, a]], _12870)
line  23   ^  Call: (11) bagof([_13198, b, a],  (s(b, _13198), \+member(_13198, [b, a])), _13256)
line  24      Call: (18) s(b, _13198)
line  25      Exit: (18) s(b, g)
line  26      Call: (18) lists:member(g, [b, a])
line  27      Fail: (18) lists:member(g, [b, a])
line  28      Redo: (18) s(b, _13198)
line  29      Exit: (18) s(b, f)
line  30      Call: (18) lists:member(f, [b, a])
line  31      Fail: (18) lists:member(f, [b, a])
line  32   ^  Exit: (11) bagof([_13198, b, a], user:(s(b, _13198), \+member(_13198, [b, a])), [[g, b, a], [f, b, a]])
line  33      Call: (11) lists:append([[c, a]], [[g, b, a], [f, b, a]], _13350)
line  34      Exit: (11) lists:append([[c, a]], [[g, b, a], [f, b, a]], [[c, a], [g, b, a], [f, b, a]])
line  35      Call: (11) breadthfirst_1([[c, a], [g, b, a], [f, b, a]], _12870)
line  36      Call: (12) goal_1(c)
line  37      Fail: (12) goal_1(c)
line  38      Redo: (11) breadthfirst_1([[c, a], [g, b, a], [f, b, a]], _12870)
line  39   ^  Call: (12) bagof([_13338, c, a],  (s(c, _13338), \+member(_13338, [c, a])), _13396)
line  40      Call: (19) s(c, _13338)
line  41      Exit: (19) s(c, r)
line  42      Call: (19) lists:member(r, [c, a])
line  43      Fail: (19) lists:member(r, [c, a])
line  44      Redo: (19) s(c, _13338)
line  45      Exit: (19) s(c, e)
line  46      Call: (19) lists:member(e, [c, a])
line  47      Fail: (19) lists:member(e, [c, a])
line  48   ^  Exit: (12) bagof([_13338, c, a], user:(s(c, _13338), \+member(_13338, [c, a])), [[r, c, a], [e, c, a]])
line  49      Call: (12) lists:append([[g, b, a], [f, b, a]], [[r, c, a], [e, c, a]], _13490)
line  50     Exit: (12) lists:append([[g, b, a], [f, b, a]], [[r, c, a], [e, c, a]], [[g, b, a], [f, b, a], [r, c, a], [e, c, a]])
line  51      Call: (12) breadthfirst_1([[g, b, a], [f, b, a], [r, c, a], [e, c, a]], _12870)
line  52      Call: (13) goal_1(g)
line  53      Exit: (13) goal_1(g)
line  54      Exit: (12) breadthfirst_1([[g, b, a], [f, b, a], [r, c, a], [e, c, a]], [g, b, a])
line  55      Exit: (11) breadthfirst_1([[c, a], [g, b, a], [f, b, a]], [g, b, a])
line  56      Exit: (10) breadthfirst_1([[b, a], [c, a]], [g, b, a])
line  57      Exit: (9) breadthfirst_1([[a]], [g, b, a])
line  58      Exit: (8) solve_1(a, [g, b, a])
line  59   S = [g, b, a] ;
line  60      Redo: (12) breadthfirst_1([[g, b, a], [f, b, a], [r, c, a], [e, c, a]], _12870)
line  61   ^  Call: (13) bagof([_13484, g, b, a],  (s(g, _13484), \+member(_13484, [g, b, a])), _13542)
line  62      Call: (20) s(g, _13484)
line  63      Fail: (20) s(g, _13484)
line  64   ^  Fail: (13) bagof([_13484, g, b, a], user:(s(g, _13484), \+member(_13484, [g, b, a])), _13548)
line  65      Redo: (12) breadthfirst_1([[g, b, a], [f, b, a], [r, c, a], [e, c, a]], _12870)
line  66      Call: (13) breadthfirst_1([[f, b, a], [r, c, a], [e, c, a]], _12870)
line  67      Call: (14) goal_1(f)
line  68      Fail: (14) goal_1(f)
line  69      Redo: (13) breadthfirst_1([[f, b, a], [r, c, a], [e, c, a]], _12870)
line  70   ^  Call: (14) bagof([_13484, f, b, a],  (s(f, _13484), \+member(_13484, [f, b, a])), _13542)
line  71      Call: (21) s(f, _13484)
line  72      Fail: (21) s(f, _13484)
line  73   ^  Fail: (14) bagof([_13484, f, b, a], user:(s(f, _13484), \+member(_13484, [f, b, a])), _13548)
line  74      Redo: (13) breadthfirst_1([[f, b, a], [r, c, a], [e, c, a]], _12870)
line  75      Call: (14) breadthfirst_1([[r, c, a], [e, c, a]], _12870)
line  76      Call: (15) goal_1(r)
line  77      Fail: (15) goal_1(r)
line  78      Redo: (14) breadthfirst_1([[r, c, a], [e, c, a]], _12870)
line  79   ^  Call: (15) bagof([_13484, r, c, a],  (s(r, _13484), \+member(_13484, [r, c, a])), _13542)
line  80      Call: (22) s(r, _13484)
line  81      Fail: (22) s(r, _13484)
line  82   ^  Fail: (15) bagof([_13484, r, c, a], user:(s(r, _13484), \+member(_13484, [r, c, a])), _13548)
line  83      Redo: (14) breadthfirst_1([[r, c, a], [e, c, a]], _12870)
line  84      Call: (15) breadthfirst_1([[e, c, a]], _12870)
line  85      Call: (16) goal_1(e)
line  86      Fail: (16) goal_1(e)
line  87      Redo: (15) breadthfirst_1([[e, c, a]], _12870)
line  88   ^  Call: (16) bagof([_13484, e, c, a],  (s(e, _13484), \+member(_13484, [e, c, a])), _13542)
line  89      Call: (23) s(e, _13484)
line  90      Fail: (23) s(e, _13484)
line  91   ^  Fail: (16) bagof([_13484, e, c, a], user:(s(e, _13484), \+member(_13484, [e, c, a])), _13548)
line  92      Redo: (15) breadthfirst_1([[e, c, a]], _12870)
line  93      Call: (16) breadthfirst_1([], _12870)
line  94      Fail: (16) breadthfirst_1([], _12870)
line  95      Fail: (15) breadthfirst_1([[e, c, a]], _12870)
line  96      Fail: (14) breadthfirst_1([[r, c, a], [e, c, a]], _12870)
line  97      Fail: (13) breadthfirst_1([[f, b, a], [r, c, a], [e, c, a]], _12870)
line  98      Fail: (12) breadthfirst_1([[g, b, a], [f, b, a], [r, c, a], [e, c, a]], _12870)
line  99      Fail: (11) breadthfirst_1([[c, a], [g, b, a], [f, b, a]], _12870)
line 100      Fail: (10) breadthfirst_1([[b, a], [c, a]], _12870)
line 101      Fail: (9) breadthfirst_1([[a]], _12870)
line 102      Fail: (8) solve_1(a, _12870)
line 103   false.
``````

At

``````line   7   ^  Call: (10) bagof([_13076, a],  (s(a, _13076), \+member(_13076, [a])), _13134)
``````

it shows the result of visiting the start node `a` which is just the path `a` and in a list of known paths is `[a]`.

at

``````line  16   ^  Exit: (10) bagof([_13076, a], user:(s(a, _13076), \+member(_13076, [a])), [[b, a], [c, a]])
``````

for path `[a]` a new list is created by using the item at the head of the list and visiting one of it's neighbors that have not been visited and adding that new path into a new list.

So with with path `[a]` and using the item at the head of the list `a` visit one of its neighbors `s(a,b)` and add that new path into a new list, `[[b,a]]`.

with with path `[a]` and using the item at the head of the list `a` visit one of its neighbors `s(a, c).` and add that new path into a new list, `[[b,a],[c,a]]`.

at

``````line  32   ^  Exit: (11) bagof([_13198, b, a], user:(s(b, _13198), \+member(_13198, [b, a])), [[g, b, a], [f, b, a]])
``````

for path `[b, a]` a new list is created by using the item at the head of the list and visiting one of it's neighbors that have not been visited and adding that new path into a new list.

So with with path `[b, a]` and using the item at the head of the list `b` visit one of its neighbors `s(b, g).` and add that new path into a new list, `[[g, b, a]]`.

with path `[b, a]` and using the item at the head of the list `b` visit one of its neighbors `s(b, f).` and add that new path into a new list, `[[g, b, a], [f, b, a]]`.

Notice that the answer `[g, b, a]` is now in the new list but it does not have `c` in the path.

At

``````line  50     Exit: (12) lists:append([[g, b, a], [f, b, a]], [[r, c, a], [e, c, a]], [[g, b, a], [f, b, a], [r, c, a], [e, c, a]])
``````

all of the paths have been created

``````[[g, b, a], [f, b, a]], [[r, c, a], [e, c, a]], [[g, b, a], [f, b, a], [r, c, a], [e, c, a]]
``````

by using all of the `s/2` facts and still the path with the answer `[g, b, a]` has no `c` in it.

Why the change from conc/3 to append/3 ?

Even though it is not one of your questions I need to answer it for others that read this question, especially people learning Prolog on their own for the first time.

This is my version of the events related to `conc/3` and `append/3` if there is another story about it do tell; I will even ask it as a posted question if need be.

One of the best if not the best books for introductory learning/teaching Prolog is "Prolog Programming for Artificial Intelligence" By Ivan Bratko. (WorldCat) (Amazon).

When first learning Prolog, people tend to spend their life in the list data structure and get a healthy diet of `append/3` but in the book he chose to have the students create their own version of `append/3` and named it `conc/3`. So through out the book is the use of `conc/3` and hardly any use of `append/3`. Now those people are use to `conc/3` and start writing code with it, posting it, etc. and it is very infectious, and you happen to have caught it. So I gave your code the remedy.

Problem of reversing the output.

When recursion is used to solve a problem it typically stores the intermediate result on the stack. Depending on the order on the stack the results are in the correct order, or in a reversed order.

There are a few ways to get the results to be returned from recursion in the correct order.

For most beginners it is to get the results and than if need be just reverse the results. For Prolog if the result is a list then reverse/2 works.

``````?- reverse([g, b, a],R).
R = [a, b, g].
``````

The predicates for reverse/2

``````?- listing(reverse/2).
lists:reverse(A, B) :-
reverse(A, [], B, B).

true.

?- listing(reverse/4).
lists:reverse([], A, A, []).
lists:reverse([B|A], C, D, [_|E]) :-
reverse(A, [B|C], D, E).

true.
``````

When you get into larger problems constantly reversing the result even between different predicate calls starts to add up time. This is especially true in functional programming.

Another way is by passing an accumulator. To demonstrate this I will use this simpler version of reverse.

``````reverse_2(L,Result) :-
accumulator_reverse(L,[],Result).
accumulator_reverse([],A,A).
accumulator_reverse([H|T],A,Result) :-
accumulator_reverse(T,[H|A],Result).
``````

The first clause initializes the accumulator to an empty list `[]` for use with `accumulator_reverse/3`

``````reverse_2(L,Result) :-
accumulator_reverse(L,[],Result).
``````

The other two clauses just recursively process a list with this clause being the base case

``````accumulator_reverse([],A,A).
``````

which is when the input list is empty (`[]`) and

this clause

``````accumulator_reverse([H|T],A,Result) :-
accumulator_reverse(T,[H|A],Result).
``````

to take the list apart `[H|T]` (AKA deconstruct) and append the head `H` to the accumulator `[H|A]` (AKA construct).

As the list is processed through

``````accumulator_reverse([H|T],A,Result) :-
accumulator_reverse(T,[H|A],Result).
``````

the original list gets smaller and smaller because the head is always being removed from the list and the accumulator grows because the head from the list is always being added to the accumulator. Since the order in which list is deconstructed, (front to back) and the accumulator is constructed (back to front) the list becomes reversed.

Normally when you look at refactored Prolog code if you see recursion and a base case that looks like

``````base([],A,A)
``````

where one of the arguments is an empty list or bottom, and two other parameters are the same, but one is bound when the call is made and the other is unbound when the call is made, look to see if accumulator passing has been factored into the code.

Some prolog books have chapters on how to implement ExpSys on it. I don't know much about this field, but in case you have nothing better ..