Recursive travel

You have a lot to learn about logic programming. :wink:

In other programming languages, they return a result, and the result holds a value.

Prolog is a logic programming language which means that the only result of a predicate is true or false. However, Prolog can also bind a free/unbound variable.

Now if we run the query (predicate) and press Enter after the first result, it does not show true, but the value bound to the variable Path.

?- travel_01(valmont,raglan,Path).
Path = [(start, valmont),  (car, saarbruecken),  (train, frankfurt),  (plane, bangkok),  (plane, auckland),  (car, hamilton),  (car, raglan)] .

If you add this predicate

travel_01_a(X,Y) :-
    travel_01(X,Y,_).

which will just take the result of the previous query and not show the Path value, you will get

?- travel_01_a(valmont,raglan).
true .

Which is what you seek, true.

So the code I gave you that returned

Path = [(start, valmont),  (car, saarbruecken),  (train, frankfurt),  (plane, bangkok),  (plane, auckland),  (car, hamilton),  (car, raglan)] .

was returning true but SWI-Prolog was not displaying true. When I suppressed the display of the bound variables, then SWI-Prolog showed the result of just the predicate.

1 Like

Haha, so true. I started today.

Thank you for the explanation, I think I need to let it marinate it in my brain for a while.

1 Like

Many here do not speak English as a native language and so using such phrases/metaphors might cause them confusion. I myself use such phrases/metaphors often but when I do I find the definition that explains it so the others are not confused.

marinate as opposed to marinate

Sorry, it is not considered as a difficult word in my language (I am not a native English speaker either) so I did not think about that.
It is a cusine term and means put your vegetable in a sauce overnight. By extension, thinking/pondering a long time over an idea.

No need to be sorry Just giving some friendly advise.

Since you are just learning and using LPN, you may not know this, but many others before you have used LPN to learn Prolog and have posted their notes on GitHub, (example)

You can search GitHub for Learn Prolog Now (search)

Their answers may be more in line with what you seek as they don’t know all of the Prolog options available to them. :smiley:

1 Like

This is the exact same word in two different dictionaries. The definition in urban dictionary is bound to be a metaphor.

Now that I mentioned it, I remembered:
metafores

1 Like

Here a simpler solution without lists, if you want to learn this later (it does not return transportation mode) :slight_smile:

anyPath(X, Y) is recursive, which takes a while to understand (it took me several months); i think there is a good explanation on learn prolog now.

byCar(auckland,hamilton).
byCar(hamilton,raglan).
byCar(valmont,saarbruecken).
byCar(valmont,metz).

byTrain(metz,frankfurt).
byTrain(saarbruecken,frankfurt).
byTrain(metz,paris).
byTrain(saarbruecken,paris).

byPlane(frankfurt,bangkok).
byPlane(frankfurt,singapore).
byPlane(paris,losAngeles).
byPlane(bangkok,auckland).
byPlane(singapore,auckland).
byPlane(losAngeles,auckland).

directPath(X, Y):-
    byCar(X, Y);
    byTrain(X, Y);
    byPlane(X, Y).
anyPath(X, Y):-
    directPath(X, Y).
anyPath(X, Y):-
    directPath(X, Z),
    anyPath(Z, Y).
3 Likes

@JCR Yes, recursion is still hurting my brain. But at the same time it’s so beautiful :rose:!

@EricGT I traced through your code this morning, very very neat. Please allow me to take some more of your time with some last questions!

travel_01(X,Y,Path) :-
    travel_01_helper(X,Y,[(start,X)],Path0),
    reverse(Path0,Path).

So you assign the current location to Path0, and the one we are seeking to Path?
When does transportation mode is becoming to Path?

travel_01_helper(X,Y,Path0,[(Mode,Y)|Path0]) :-
    (
        (byCar(X,Y),Mode = car)
    ;
        (byTrain(X,Y),Mode = train)
    ;
        (byPlane(X,Y),Mode = plane)
    ),
    \+ member((_,Y),Path0).

I don’t understand this syntas +, even though I checked the Prolog dictionary:
https://www.swi-prolog.org/pldoc/man?predicate=\%2B/1

Also, I don’t really get what gets saved in the first occurence of Path0 (outside of the list), and Path0 inside of the list.

travel_01_helper(X,Y,Path0,[(Mode,Y)|Path0]) :-

Thank you in advance for any answer. There is a lot going on for me in that recursion…

\+ is logical not. e.g.
if the predicate result is true then use not true, which is false.
if the predicate result is false then use not false, which is true.

member((_,Y),Path0). can be understood as follows.

Path0 will look like [(start, valmont), (car, saarbruecken), (train, frankfurt), (plane, bangkok)] which is a list.
Each item in the list will be (Mode, Location) and (_,Y) is a pattern to match against each item in the list. member/2 will do the matching of the pattern against each item in the list.

Y is the Location, e.g. valmont, most recently added to the end of the list, so member((_,Y),Path0) reads the predicate is true when the the Location in Y is the same as any Location in Path0. Which means that if the last location added matches any in the current path then the result is true. But \+ is not so, when the last location added already exist in the list is found, then the line \+ member((_,Y),Path0) will return false and the entire clause will fail.

travel_01_helper(X,Y,Path0,[(Mode,Y)|Path0]) :-
    (
        (byCar(X,Y),Mode = car)
    ;
        (byTrain(X,Y),Mode = train)
    ;
        (byPlane(X,Y),Mode = plane)
    ),
    \+ member((_,Y),Path0).`

so the next clause will be tried

travel_01_helper(X,Z,Path0,Path) :-
    (
        (byCar(X,Y),Mode = car)
    ;
        (byTrain(X,Y),Mode = train)
    ;
        (byPlane(X,Y),Mode = plane)
    ),
    travel_01_helper(Y,Z,[(Mode,Y)|Path0],Path).

Ask more questions if that is still not clear.

1 Like

The easiest way to find this out is to use either trace/0 or gtrace/0. Since gtrace/0 is rather complex being a GUI, I will just use trace for this example.

?- trace.
true.

[trace]  ?- travel_01(valmont,frankfurt,Path).
   Call: (10) travel_01(valmont, frankfurt, _4260) ? creep
   Call: (11) travel_01_helper(valmont, frankfurt, [(start, valmont)], _4520) ? 

As you can see trace has shown the call to travel_01_helper/4 with the arguments used as input bound, and the augment used as output unbound. _4520 is a system generated variable which is unbound.

For simple goals, trace/0 can be used with protocol/1. See: Wiki: How to - protocol/1


?- set_prolog_flag(color_term,false).
true.

?- current_prolog_flag(color_term,X).
X = false.

?- working_directory(_,"C:/Users/Eric/Documents/Prolog").
true.

?- leash(-all),visible(+all).
true.

?- protocol("./trace_output.txt").
true.

?- trace.
true.

[trace]  ?- travel_01(valmont,frankfurt,Path).
   Call: (10) travel_01(valmont, frankfurt, _596)
   Unify: (10) travel_01(valmont, frankfurt, _596)
   Call: (11) travel_01_helper(valmont, frankfurt, [(start, valmont)], _856)
   Unify: (11) travel_01_helper(valmont, frankfurt, [(start, valmont)], [(_842, frankfurt),  (start, valmont)])
   Call: (12) byCar(valmont, frankfurt)
   Fail: (12) byCar(valmont, frankfurt)
   Redo: (11) travel_01_helper(valmont, frankfurt, [(start, valmont)], [(_842, frankfurt),  (start, valmont)])
   Call: (12) byTrain(valmont, frankfurt)
   Fail: (12) byTrain(valmont, frankfurt)
   Redo: (11) travel_01_helper(valmont, frankfurt, [(start, valmont)], [(_842, frankfurt),  (start, valmont)])
   Call: (12) byPlane(valmont, frankfurt)
   Fail: (12) byPlane(valmont, frankfurt)
   Redo: (11) travel_01_helper(valmont, frankfurt, [(start, valmont)], _856)
   Unify: (11) travel_01_helper(valmont, frankfurt, [(start, valmont)], _856)
   Call: (12) byCar(valmont, _852)
   Unify: (12) byCar(valmont, saarbruecken)
   Exit: (12) byCar(valmont, saarbruecken)
   Call: (12) _850=car
   Exit: (12) car=car
   Call: (12) travel_01_helper(saarbruecken, frankfurt, [(car, saarbruecken),  (start, valmont)], _868)
   Unify: (12) travel_01_helper(saarbruecken, frankfurt, [(car, saarbruecken),  (start, valmont)], [(_854, frankfurt),  (car, saarbruecken),  (start, valmont)])
   Call: (13) byCar(saarbruecken, frankfurt)
   Fail: (13) byCar(saarbruecken, frankfurt)
   Redo: (12) travel_01_helper(saarbruecken, frankfurt, [(car, saarbruecken),  (start, valmont)], [(_854, frankfurt),  (car, saarbruecken),  (start, valmont)])
   Call: (13) byTrain(saarbruecken, frankfurt)
   Unify: (13) byTrain(saarbruecken, frankfurt)
   Exit: (13) byTrain(saarbruecken, frankfurt)
   Call: (13) _854=train
   Exit: (13) train=train
   Call: (13) lists:member((_860, frankfurt), [(car, saarbruecken),  (start, valmont)])
   Unify: (13) lists:member((_860, frankfurt), [(car, saarbruecken),  (start, valmont)])
   Fail: (13) lists:member((_860, frankfurt), [(car, saarbruecken),  (start, valmont)])
   Redo: (12) travel_01_helper(saarbruecken, frankfurt, [(car, saarbruecken),  (start, valmont)], [(train, frankfurt),  (car, saarbruecken),  (start, valmont)])
   Exit: (12) travel_01_helper(saarbruecken, frankfurt, [(car, saarbruecken),  (start, valmont)], [(train, frankfurt),  (car, saarbruecken),  (start, valmont)])
   Exit: (11) travel_01_helper(valmont, frankfurt, [(start, valmont)], [(train, frankfurt),  (car, saarbruecken),  (start, valmont)])
   Call: (11) lists:reverse([(train, frankfurt),  (car, saarbruecken),  (start, valmont)], _596)
   Unify: (11) lists:reverse([(train, frankfurt),  (car, saarbruecken),  (start, valmont)], _596)
   Exit: (11) lists:reverse([(train, frankfurt),  (car, saarbruecken),  (start, valmont)], [(start, valmont),  (car, saarbruecken),  (train, frankfurt)])
   Exit: (10) travel_01(valmont, frankfurt, [(start, valmont),  (car, saarbruecken),  (train, frankfurt)])
Path = [(start, valmont),  (car, saarbruecken),  (train, frankfurt)] .

[trace]  ?- nodebug.
true.

?- noprotocol.
true.

?- 
1 Like

The details can be seen by using trace/0 with protocol/1 as noted in the earlier post. Here I will just explain the details without showing the code or the trace.

The predicate travel_01_helper/4 is entered on the first line with the first three arguments bound, so [(Mode,Y)|Path0] is not fully bound but, Y and Path0 are bound because they were bound when the predicate was entered.

Next there are thee possibilities for the next statement because of the use of ;. When one of the three predicates, e.g. byCar(X,Y) succeeds/returns true, then the next predicate is called, e.g. Mode = car and via unification =/2, the unbound variable Mode is bound to the value.

In the example Mode = car, =/2 is used as an infix operator as opposed to a prefix operator.

?- Mode = car.
Mode = car.

?- =(Mode,car).
Mode = car.

If you want to look at other somewhat simple Prolog examples see RosettaCode - Prolog

For other useful links see: Useful Prolog references

1 Like

Hello again!

I still need time to process (= think about it).

You wrote:

Can you please elaborate (=explain more). Why would the whole close fail if we happened to already have traversed Valmont? Could we not have traversed Valmont by car to Amsterdam, and later in the list traversed Valmont again but by plane, to Hambourg?

Also, which English words am I supposed to explain? What is the rule of thumb?

2 Likes

The rule of thumb I use when explaining English words/phrases is that if a standard dictionary (Merriam-Webster) defines it one way and I am using it a way not defined in a standard dictionary but one that is typically found in a dictionary like urban dictionary then I typically link to the urban dictionary definition, or where the definition as I mean is defined.

Don’t worry about it so much as if someone doesn’t understand you, they will post a question. I just like to do it because it is easy and I know how hard it is sometimes to understand a language when you are not a native speaker.

1 Like

A clause will contain a head and possibly a body. A head without a body is a fact.

In the clause

travel_01_helper(X,Y,Path0,[(Mode,Y)|Path0]) :-
    (
        (byCar(X,Y),Mode = car)
    ;
        (byTrain(X,Y),Mode = train)
    ;
        (byPlane(X,Y),Mode = plane)
    ),
    \+ member((_,Y),Path0).

The head is

travel_01_helper(X,Y,Path0,[(Mode,Y)|Path0])

and the body is

    (
        (byCar(X,Y),Mode = car)
    ;
        (byTrain(X,Y),Mode = train)
    ;
        (byPlane(X,Y),Mode = plane)
    ),
    \+ member((_,Y),Path0).

Now to help in understanding how a body of a clause works, here are examples that are very simple and get more complex.

Remember that with logic,
if any part of and expression is false, the entire expression is false
if any part of or expression is true, the entire expression is true

Remember that in Prolog
, means logical and
; means logical or
\+ means logical not
() group logical expressions.

When SWI-Prolog returns a result that ends with . there are no more possible answers. When SWI-Prolog returns a result that ends with ; there are more possible answers, so press the space bar to continue seeing them.

Prolog will keep seeking more answers as long as there is a possible way for the clause (logic) to be true.

Example clauses. Results of running follow.

% true
clause_1 :-
    true.

 % false
 clause_2 :-
    false.

 % true and true
 clause_3 :-
    true,
    true.

 % true and false
 clause_4 :-
    true,
    false.

% false and true
clause_5 :-
   false,
   true.

 % true or true
 clause_6 :-
    true;
    true.

 % true or true but done with predicates other than true which output to the screen when executed.
clause_7 :-
    format('1',[]);
    format('2',[]).

 % true or false
 clause_8 :-
    true;
    false.

 % false or true
 clause_9 :-
    false;
    true.

 % false or false
 clause_10 :-
    false;
    false.

% not true
clause_11 :-
    \+ true.

% not false
clause_12 :-
    \+ false.

% true or true or false.
clause_13 :-
    true ; true ; false.

% true or false or true
clause_14 :-
    true ; false ; true.

% false or true or true
clause_15 :-
    false ; true ; true.

% (true or false or false) and true
clause_16 :-
    (true ; false ; false) , true.

% (true or false or false) and false
clause_17 :-
    (true ; false ; false) , false.

% (true or false or false) and not true
clause_18 :-
    (true ; false ; false) , \+ true.

Results of running.

% true
?- clause_1.
true.

% false
?- clause_2.
false.

% true and true
?- clause_3.
true.

% true and false
?- clause_4.
false.

% false and true
% Prolog failed on the first part of the and so there was no need to do the second part as the result will always be false.
?- clause_5.
false.

% true or true
% Prolog will try and give you all the true solutions. In this case there are two and they are both true. See next example
?- clause_6.
true ;
true.

% true or true but using format/1.
?- clause_7.
1
true ;
2
true.

% true or false
% Prolog was successful on the first part of the or, so then it did the next part and failed.
% Prolog will keep seeking more answers as long as there is a possible way for the clause (logic) to be true.
?- clause_8.
true ;
false.

% false or true
% Prolog failed on the first part of the or but continued to the next part of the or and succeeded.
% Prolog will keep seeking more answers as long as there is a possible way for the clause (logic) to be true.
?- clause_9.
true.

% false or false
% Prolog failed on the first part of the or but continued to the next part of the or and failed also, so the result is false.
?- clause_10.
false.

% not true
?- clause_11.
false.

% not false
?- clause_12.
true.

% true or true or false.
% Prolog succeeded on the first part of the or, continued to the second part of the or which succeeded, and failed on the third part of the or.
% Prolog will keep seeking more answers as long as there is a possible way for the clause (logic) to be true.
?- clause_13.
true ;
true ;
false.

% true or false or true
% Prolog succeeded on the first part of the or, continued to the second part of the or which failed (which was not reported to the screen), and succeeded on the third part of the or.
% Prolog will keep seeking more answers as long as there is a possible way for the clause (logic) to be true.
?- clause_14.
true ;
true.

% false or true or true
% Prolog failed on the first part of the or (which was not reported to the screen), continued to the second part of the or which succeeded, and succeeded on the third part of the or.
?- clause_15.
true ;
true.

% (true or false or false) and true
% Prolog succeeded on the first part (true or false or false) using the first true, continued to the second part of the and which succeeded.
?- clause_16.
true ;
true.

% (true or false or false) and false
% Prolog succeeded on the first part (true or false or false) using the first true, continued to the second part of the and which failed.
% This is just a more complex version of clause_4.
?- clause_17.
false.

% (true or false or false) and not true
% Prolog succeeded on the first part (true or false or false) using the first true, continued to the second part of the and which succeeded, but then applied not to the second part which was true, which resulted in false which made the entire clause false.
% This is just a more complex version of clause_17.
% This clause is like the one you asked about in the question.
?- clause_18.
false.

Remember that logic expressions are expressions and just like math expressions, there are some substitutions that can be done that will not change the meaning of the code. However in Prolog there are also changes that can dramatically change the meaning of the code.

In other words, the only thing that matters to Prolog when it evaluates the statements in a clause are the statements/predicates are seen as a logic expression and the expression has to evaluate to true. All the rest is side-effects of binding values to variables. So when you ask about the values concerning the location names, those don’t matter if the logic of the clause results in false. Only when the logic of a clause is true will the binding of the variables be returned.


@DaJa

When I wrote the code you are reviewing in detail I wrote it more to show that your O-O should have been -O. I knew the code was not the best but did not expect you to examine in such detail.

Here is a much better version that if you plan to study in detail would be better for you.

travel_02(X,Y,Path) :-
    travel_02_helper(X,Y,[(start,X)],Path0),
    reverse(Path0,Path).

travel_02_mode(X,Y,Mode) :-
    (
        (byCar(X,Y),Mode = car)
    ;
        (byTrain(X,Y),Mode = train)
    ;
        (byPlane(X,Y),Mode = plane)
    ).

% base case
travel_02_helper(X,X,Path,Path).

% recursive case
travel_02_helper(X,Z,Path0,Path) :-
    travel_02_mode(X,Y,Mode),
    \+ member((_,Y),Path0),
    travel_02_helper(Y,Z,[(Mode,Y)|Path0],Path).

It returns the same results as the earlier version, but as I noted, logic expressions are like math expressions and certain substitutions are allowed.

?- travel_02(valmont,raglan,Path).
Path = [(start, valmont),  (car, saarbruecken),  (train, frankfurt),  (plane, bangkok),  (plane, auckland),  (car, hamilton),  (car, raglan)] ;
Path = [(start, valmont),  (car, saarbruecken),  (train, frankfurt),  (plane, singapore),  (plane, auckland),  (car, hamilton),  (car, raglan)] ;
Path = [(start, valmont),  (car, saarbruecken),  (train, paris),  (plane, losAngeles),  (plane, auckland),  (car, hamilton),  (car, raglan)] ;
Path = [(start, valmont),  (car, metz),  (train, frankfurt),  (plane, bangkok),  (plane, auckland),  (car, hamilton),  (car, raglan)] ;
Path = [(start, valmont),  (car, metz),  (train, frankfurt),  (plane, singapore),  (plane, auckland),  (car, hamilton),  (car, raglan)] ;
Path = [(start, valmont),  (car, metz),  (train, paris),  (plane, losAngeles),  (plane, auckland),  (car, hamilton),  (car, raglan)] ;
false.
1 Like

You are such a nice person to have taken all this time and effort to explain basic concepts and write beautiful code :bowing_woman:!

Thank you!

I went through it and I think I start to grasp how the recursive calls are bouncing back and forth.

  1. I noticed that if I delete the below part of
reverse(Path0,Path).

the code is not printing. I looked up reverse/2, and it should just reverse two atoms or lists. Why does reverse/2 does the printing of the path?

  1. When the code calls \+member, is it an example of what is called negation as failure?
Call: (15) lists:member((_6100, hamilton), [(plane, auckland),  (plane, bangkok),  (train, frankfurt),  (car, saarbruecken),  (start, valmont)]) ? creep
Fail: (15) lists:member((_6100, hamilton), [(plane, auckland),  (plane, bangkok),  (train, frankfurt),  (car, saarbruecken),  (start, valmont)]) ? creep
  1. A question more specific to this code: why do we need this clause? Can’t we go twice through the same place with different vehicles? Could the list members be:
 [(plane, auckland),  (plane, bangkok), .... some other places...., (car, aukland)]

or does it not make logical sense at all?

I assume you mean \+ member.

Negation, including negation-as-failure, can be a rather large topic. For now, you might consider this definition of not_member(*):

not_member(_, []).
not_member(X, [Y|Ys]) :-
    X \= Y,  % or: \+ X = Y
    not_member(X, Ys).

(this can be derived from the definition of “member”:

member(X, [X|_]).
member(X, [_|Ys]) :- member(X, Ys).

).

These uses of \+ and \= depend on the arguments being “sufficiently ground”. For example X=1, \+ member(X, [2,3,4]) works as expected but \+ member(X, [2,3,4]), X=1 doesn’t. (There are ways to fix this, but that’s a somewhat more advanced topic.)

(*) Yes, this definition of not_member is not optimal, but it suffices for now.

reverse/2 is not doing the printing of the paths.

What

reverse(Path0,Path).

does is to take in the bound variable Path0 which is a list and the unbound variable Path , and reverses the list in Path0 creating a new path and then binds the new path to the variable Path.

When Path is then returned to

travel_02(X,Y,Path) :-

in

travel_02(X,Y,Path) :-
    travel_02_helper(X,Y,[(start,X)],Path0),
    reverse(Path0,Path).

because the clause succeeded, Prolog returns the result of the query/goal to the Toplevel which displays the values bound to the unbound values when the goal was executed, in this case Path


In Prolog variables are immutable meaning they can only be bound to a value once.

So how do you change the value of something that can only have a value assigned to it once?

You create a new variable which is unbound, then using the old value make the change and bind the new value to a new variable.

In Prolog the style of doing this is to use the same variable name, e.g. Path. When you want to pass in a value, change it and pass out the change with a predicate the custom is to name the in coming value with a variable name that ends with 0 then for each change in the predicate use the next number, e.g. Path1, Path2, etc. For the value being returned the name is not given a number, e.g. Path.

When you removed the line

reverse(Path0,Path)

you broke the path for the variable, so the result from

travel_02_helper(X,Y,[(start,X)],Path0),

which was

Path0

was not returned to

travel_02(X,Y,Path)

If you want to remove the line

reverse(Path0,Path)

then you have to change the line

travel_02_helper(X,Y,[(start,X)],Path0)

to

travel_02_helper(X,Y,[(start,X)],Path)
1 Like

To avoid an infinite loop. In other words, if just these facts where in the code

byBus(auckland,hamilton).
byBus(hamilton,auckland).

and this code is used

travel_03(X,Y,Path) :-
    travel_03_helper(X,Y,[(start,X)],Path0),
    reverse(Path0,Path).

travel_03_mode(X,Y,Mode) :-
    (byBus(X,Y),Mode = bus).

travel_03_helper(X,X,Path,Path).
travel_03_helper(X,Z,Path0,Path) :-
    travel_03_mode(X,Y,Mode),
    travel_03_helper(Y,Z,[(Mode,Y)|Path0],Path).

and this query run

?- travel_03(X,Y,Path).
X = Y,
Path = [(start, Y)] ;
X = auckland,
Y = hamilton,
Path = [(start, auckland),  (bus, hamilton)] ;
X = Y, Y = auckland,
Path = [(start, auckland),  (bus, hamilton),  (bus, auckland)] ;
X = auckland,
Y = hamilton,
Path = [(start, auckland),  (bus, hamilton),  (bus, auckland),  (bus, hamilton)] ;
X = Y, Y = auckland,
Path = [(start, auckland),  (bus, hamilton),  (bus, auckland),  (bus, hamilton),  (bus, auckland)] 

then the path could go from auckland to hamilton then from hamilton to auckland and keep repeating. Prolog would never be able to return an answer; it is stuck in this loop.


I am so use to doing graph traversal routines that I automatically add in the condition to avoid loops. Upon checking the data as given at LPN, they avoid the loop problem by not creating connections that can form a loop. The real world is not like this; this was a contrived exercise to teach recursion. I never tried the code without the statement.

travel_04(X,Y,Path) :-
    travel_04_helper(X,Y,[(start,X)],Path0),
    reverse(Path0,Path).

travel_04_mode(X,Y,Mode) :-
    (
        (byCar(X,Y),Mode = car)
    ;
        (byTrain(X,Y),Mode = train)
    ;
        (byPlane(X,Y),Mode = plane)
    ).

travel_04_helper(X,X,Path,Path).
travel_04_helper(X,Z,Path0,Path) :-
    travel_04_mode(X,Y,Mode),
    % \+ member((_,Y),Path0),
    travel_04_helper(Y,Z,[(Mode,Y)|Path0],Path).
?- travel_04(valmont,raglan,Path).
Path = [(start, valmont),  (car, saarbruecken),  (train, frankfurt),  (plane, bangkok),  (plane, auckland),  (car, hamilton),  (car, raglan)] ;
Path = [(start, valmont),  (car, saarbruecken),  (train, frankfurt),  (plane, singapore),  (plane, auckland),  (car, hamilton),  (car, raglan)] ;
Path = [(start, valmont),  (car, saarbruecken),  (train, paris),  (plane, losAngeles),  (plane, auckland),  (car, hamilton),  (car, raglan)] ;
Path = [(start, valmont),  (car, metz),  (train, frankfurt),  (plane, bangkok),  (plane, auckland),  (car, hamilton),  (car, raglan)] ;
Path = [(start, valmont),  (car, metz),  (train, frankfurt),  (plane, singapore),  (plane, auckland),  (car, hamilton),  (car, raglan)] ;
Path = [(start, valmont),  (car, metz),  (train, paris),  (plane, losAngeles),  (plane, auckland),  (car, hamilton),  (car, raglan)] ;
false.

but as shown, and as you have quested, it is not needed for this exercise.

If you look at graph traversal pseudocode you will see that it also checks to see if a node/location was previously visited (label v as explored), and if so, does not go through the node/location again.

1 Like

Do not think of it as bouncing back and forth, think of it as pushing a new context on a stack with new variables for the called goal/predicate.

If you look at the trace output


[trace]  ?- travel_01(valmont,frankfurt,Path).
   Call: (10) travel_01(valmont, frankfurt, _596)
   Unify: (10) travel_01(valmont, frankfurt, _596)
   Call: (11) travel_01_helper(valmont, frankfurt, [(start, valmont)], _856)
   Unify: (11) travel_01_helper(valmont, frankfurt, [(start, valmont)], [(_842, frankfurt),  (start, valmont)])
   Call: (12) byCar(valmont, frankfurt)
   Fail: (12) byCar(valmont, frankfurt)
   Redo: (11) travel_01_helper(valmont, frankfurt, [(start, valmont)], [(_842, frankfurt),  (start, valmont)])
   Call: (12) byTrain(valmont, frankfurt)
   Fail: (12) byTrain(valmont, frankfurt)
   Redo: (11) travel_01_helper(valmont, frankfurt, [(start, valmont)], [(_842, frankfurt),  (start, valmont)])
   Call: (12) byPlane(valmont, frankfurt)
   Fail: (12) byPlane(valmont, frankfurt)
   Redo: (11) travel_01_helper(valmont, frankfurt, [(start, valmont)], _856)
   Unify: (11) travel_01_helper(valmont, frankfurt, [(start, valmont)], _856)
   Call: (12) byCar(valmont, _852)
   Unify: (12) byCar(valmont, saarbruecken)
   Exit: (12) byCar(valmont, saarbruecken)
   Call: (12) _850=car
   Exit: (12) car=car
   Call: (12) travel_01_helper(saarbruecken, frankfurt, [(car, saarbruecken),  (start, valmont)], _868)
   Unify: (12) travel_01_helper(saarbruecken, frankfurt, [(car, saarbruecken),  (start, valmont)], [(_854, frankfurt),  (car, saarbruecken),  (start, valmont)])
   Call: (13) byCar(saarbruecken, frankfurt)
   Fail: (13) byCar(saarbruecken, frankfurt)
   Redo: (12) travel_01_helper(saarbruecken, frankfurt, [(car, saarbruecken),  (start, valmont)], [(_854, frankfurt),  (car, saarbruecken),  (start, valmont)])
   Call: (13) byTrain(saarbruecken, frankfurt)
   Unify: (13) byTrain(saarbruecken, frankfurt)
   Exit: (13) byTrain(saarbruecken, frankfurt)
   Call: (13) _854=train
   Exit: (13) train=train
   Call: (13) lists:member((_860, frankfurt), [(car, saarbruecken),  (start, valmont)])
   Unify: (13) lists:member((_860, frankfurt), [(car, saarbruecken),  (start, valmont)])
   Fail: (13) lists:member((_860, frankfurt), [(car, saarbruecken),  (start, valmont)])
   Redo: (12) travel_01_helper(saarbruecken, frankfurt, [(car, saarbruecken),  (start, valmont)], [(train, frankfurt),  (car, saarbruecken),  (start, valmont)])
   Exit: (12) travel_01_helper(saarbruecken, frankfurt, [(car, saarbruecken),  (start, valmont)], [(train, frankfurt),  (car, saarbruecken),  (start, valmont)])
   Exit: (11) travel_01_helper(valmont, frankfurt, [(start, valmont)], [(train, frankfurt),  (car, saarbruecken),  (start, valmont)])
   Call: (11) lists:reverse([(train, frankfurt),  (car, saarbruecken),  (start, valmont)], _596)
   Unify: (11) lists:reverse([(train, frankfurt),  (car, saarbruecken),  (start, valmont)], _596)
   Exit: (11) lists:reverse([(train, frankfurt),  (car, saarbruecken),  (start, valmont)], [(start, valmont),  (car, saarbruecken),  (train, frankfurt)])
   Exit: (10) travel_01(valmont, frankfurt, [(start, valmont),  (car, saarbruecken),  (train, frankfurt)])
Path = [(start, valmont),  (car, saarbruecken),  (train, frankfurt)] .

Notice that the numbers in () are going up each time a call is made to the same predicate and then go down when the predicate is exited. When I was learning to look at trace output I would indent the output to line up the numbers in the (), then it was easier to understand.

Also notice that with each call to the same predicate, the unbound variables get a different system generated variable.

Call: (11) travel_01_helper(valmont, frankfurt,[(start, valmont)],_856)
Call: (12) travel_01_helper(saarbruecken, frankfurt, [(car, saarbruecken),  (start, valmont)], _868)

Notice that the unbound variable Path in each call for

travel_02_helper(X,Z,Path0,Path)

is a different system generated variable, e.g.

_856 and _868