using assertz() and retract() in breadth-first search

Question

I am trying to write breadth-first search in SWI Prolog using assertz() and retract(). I am having some issues though and I was hoping for some guidance. My guess is I'm doing something stupid.

:- dynamic paths/1.

bfs_solve(Solution) :-
  initial_state(Start),
  assertz(paths([[Start]])),
  breadthfirst(Solution).

breadthfirst([Node | Path]) :-
  retract(paths([[Node | Path] | _])),
  goal(Node).

breadthfirst(Solution) :-
  retract(paths([Path | RestPaths])),
  extend(Path, NewPaths),
  conc(RestPaths, NewPaths, Paths1),
  assertz(paths(Paths1)),
  breadthfirst(Solution).

extend([Node | Path], NewPaths) :-
  bagof([NewNode, Node | Path],
  (s(Node, NewNode), \+ member(NewNode, [Node | Path])),
  NewPaths),
  !.

extend(Path, []).

initial_state([1, 2, 3, 4, 5]).
goal([0, 0, 0, 0, 0]).

% Function 's' is not detailed here as it is irrelevant to this problem

member(X, [X | Tail]).
member(X, [Head | Tail]) :-
  member(X, Tail).

conc([], L, L).
conc([X | L1], L2, [X | L3]) :-
  conc(L1, L2, L3).

The problem is that as soon as the goal check happens in breadthfirst/1, it retracts the initial state from the database, so by the time it gets to the second definition of breadthfirst/1 (where the extend/2 function is called), there is nothing left to retract, causing execution to stop.

What am I missing here?

Thanks!

Usual reminder: You can step through your program, to see exactly what is happening and where it is going wrong, using e.g. `trace.` - https://www.swi-prolog.org/pldoc/man?section=debugger — brebs, Aug 09 '23 at 16:40
Looks similar to https://www.youtube.com/watch?v=xH-AZonBywI - don't need `assertz`. — brebs, Aug 09 '23 at 17:13
Thanks for the tips @brebs! However I'm aware of the standard way of doing breadth-first search in Prolog using dynamic lists. The idea is to not use dynamic lists, but rather a static queue, hence the use of assertz and retract. — Gerhardus Carinus, Aug 09 '23 at 17:32
Do not use the database for a queue. It is way easier to use a list. See for example [this Q/A](https://stackoverflow.com/questions/31918227/difference-lists-in-prolog-and-mutable-variables) — TA_intern, Aug 10 '23 at 05:20

score 0 · Answer 1 · answered Aug 10 '23 at 10:58

You might be able to figure out your mistakes if you wrapped your calls to assert* and retract* inside a couple of predicates that implement a queue. What do you need for a queue?

Initialize an empty queue
push to the back
pop from the front

(do you also need to be able to push to the front, or look at the top without popping?)

I am assuming that you want to keep this stateful and global? (why use the database otherwise?) In this case you can choose to call your queue queue/1 and then:

:- dynamic queue/1.

empty_queue :-
    retractall(queue(_)).

push_back(Back) :-
    assertz(queue(Back)).

pop_front(Front) :-
    once(queue(F0)), % first fact matched to a free variable
    once(retract(queue(F0))), % retract exactly once the matched fact
    Front = F0.

A simple test, I push [a, b, c], pop out twice, so it should be 'a', then 'b', and print the rest of the queue, should be [c]:

?- empty_queue,
   push_back(a),
   push_back(b),
   push_back(c),
   pop_front(X0),
   pop_front(X1),
   forall(queue(A), format("~w~n", [A])).
c
X0 = a,
X1 = b.

(the whole queue is on the first line of the output)

To show that we only pop the top:

?- empty_queue,
   push_back(a),
   push_back(b),
   push_back(a),
   pop_front(X),
   forall(queue(A), format("~w~n", [A])).
b
a
X = a.

So it seems to work.

slago · Answer 2 · 2023-08-12T07:12:41.697

I assume you know that using a dynamic predicate is not the best approach to solving the problem. Anyway, a possible solution using dynamic predicate is as follows:

:- dynamic paths/1.

solve(Solution) :-
    initial(State),
    assertz(paths([[State]])),
    bfs(Solution).

bfs(Solution) :-
    retract(paths([[Node|Path]|Paths])),
    writeln(queue: [[Node|Path]|Paths]),
    (   goal(Node)                          % if
    ->  reverse([Node|Path], Solution)      % then
    ;   extend([Node|Path], NewPaths),      % else
        append(Paths, NewPaths, Paths1),
        assertz(paths(Paths1)),
        bfs(Solution) ).

extend([Node|Path], NewPaths) :-
    findall([NewNode,Node|Path],
            (s(Node, NewNode), \+ member(NewNode, [Node|Path])),
            NewPaths).

initial(1).
goal(5).
s(1, 2).
s(1, 3).
s(2, 1).
s(2, 4).
s(3, 4).
s(4, 5).

Example:

?- solve(S).
queue:[[1]]
queue:[[2,1],[3,1]]
queue:[[3,1],[4,2,1]]
queue:[[4,2,1],[4,3,1]]
queue:[[4,3,1],[5,4,2,1]]
queue:[[5,4,2,1],[5,4,3,1]]
S = [1, 2, 4, 5].

using assertz() and retract() in breadth-first search

2 Answers2