Not clear on how this Prolog depth first search (DFS) method code works

Question

Today a teacher gave us this code on prolog:

dfs_paths(tree(X, void, void), [X]) :- !.
dfs_paths(tree(X, L, _R), [X|Xs])   :- dfs_paths(L, Xs).
dfs_paths(tree(X, _L, R), [X|Xs])   :- dfs_paths(R, Xs).
    
tree(A) :-
   A = tree(i,
          tree(A,
          tree(la,void,void),
          tree(sa,void,void)
       ),
   tree(b,
      tree(lb,void,void),
      tree(sb,void,void)
    )).

He told us that code is a way to work DFS method on prolog, but we didn't receive more information about how the code works on each line.

I'm a newbie using prolog and I'm trying to understand this code

Thanks guys!

Update: this is the tree

Answer 1

Apparently we want to all the paths from the tree root to one of its leaves by backtracking.

First, the declaration of the tree has to be corrected:

The tree is a term built/written as follows (N.B. every text element is lowercase otherwise we would be writing down variables instead of constants):

tree(i,
     tree(a,
          tree(la,void,void),
          tree(sa,void,void)),
     tree(b,
          tree(lb,void,void),
          tree(sb,void,void))).

And we can store is simply by declaring a fact that holds this tree as argument

tree_storage(
   tree(i,
        tree(a,
             tree(la,void,void),
             tree(sa,void,void)),
        tree(b,
             tree(lb,void,void),
             tree(sb,void,void)))
).

Now the "visit code"

dfs_paths(+Tree,?Path)

which builds (or verifies) a path Path through the tree given by Tree.

If the first argument looks like a leaf node (i.e. is built using functor tree with 3 arguments, and the constant void on argument positions 2 and 3, the the path is just the name of the node:

dfs_paths(tree(X, void, void), [X]).

There is no need to cut (!) at all.

Otherwise, if the left branch of the tree is non-void, then the possibility is offered to recursively generate a path by going down the left branch, and prepend the name of the root tree node, i.e. X. We don't care about visiting the right branch here. To make the compiler not complain, the placeholder for the right branch is written with a _ in front:

dfs_paths(tree(X, L, _R), [X|Xs]) :- dif(L,void), dfs_paths(L, Xs).

Otherwise, if the right branch of the tree is non-void, then the possibility is offered to recursively generate a path by going down the right branch, and prepend the name of the root tree node, i.e. X. We don't care about visiting the left branch here. To make the compiler not complain, the placeholder for the left branch is written with a _ in front:

dfs_paths(tree(X, _L, R), [X|Xs]) :- dif(R,void), dfs_paths(R, Xs).

Putting this together and adding a format/2 statement to print what's going on, we see that Prolog tries all possibilites by applying the three rules to the "tree" term:

dfs_paths(tree(X, void, void), [X]) :-
   format("At leaf '~q'~n",[X]).
dfs_paths(tree(X, L, _R), [X|Xs]) :- 
   dif(L,void), 
   format("Going down left at inner node '~q'~n",[X]),
   dfs_paths(L, Xs).
dfs_paths(tree(X, _L, R), [X|Xs]) :- 
   dif(R,void),
   format("Going down right at inner node '~q'~n",[X]),
   dfs_paths(R, Xs).

tree_storage(
   tree(i,
        tree(a,
             tree(la,void,void),
             tree(sa,void,void)),
        tree(b,
             tree(lb,void,void),
             tree(sb,void,void)))
).

run(Path) :-
   tree_storage(Tree),    % Tree is our predefined tree
   dfs_paths(Tree,Path).   % A Path is some path through that tree

Now run this:

?- run(Path).
Going down left at inner node 'i'
Going down left at inner node 'a'
At leaf 'la'
Path = [i,a,la] ;
Going down right at inner node 'a'
At leaf 'sa'
Path = [i,a,sa] ;
Going down right at inner node 'i'
Going down left at inner node 'b'
At leaf 'lb'
Path = [i,b,lb] ;
Going down right at inner node 'b'
At leaf 'sb'
Path = [i,b,sb] ;
false.