state

Ready. Push Step to start animating a Jalog (Prolog) program.
By: Mikko Levanto and Ari Okkonen 2019
Jalog home: https://jalogteam.github.io/

The goal is instantiated creating a variable for each variable name in the clause. Variable names begin with an uppercase letter or underscore. Variables are local and not visible outside of the clause. In this example variable Route₁ is created for the name Route and likewise Len₁ for Len. (In this visualization the subscripts are used to differentiate different variable instances with the same name.) After instantiation the execution of the instantiated clause is started. First the predicate route is called.

Predicate route is called with the following parameters:...

The database is searched for a matching clause. The head of the first clause of route is compared to the call.

The first parameter of the called predicate is compared to the call. Because it is a variable, it matches and can be unified: the variable Town will be replaced with the value oulu everywhere in the clause.

The second parameter of the called predicate is compared to the call. Because it is a definite value and different from the value in the call it does not match. So, the head of the clause does not match the call. The database will be searched for next clause of the route predicate.

The head of the second clause of route is compared to the call.

The first parameter of the called predicate is compared to the call. Because it is a variable, it matches and can be unified: the variable Town1 will be replaced with the value oulu everywhere in the clause.

The second parameter of the called predicate is compared to the call. Because it is a variable, it matches and can be unified: the variable Town2 will be replaced with the value joensuu everywhere in the clause.

The third parameter of the called predicate is compared to the call. Because it is a variable, it matches and can be unified: the variable ToTown1 will be replaced with the value [] (i.e., an empty list) everywhere in the clause.

The fourth parameter of the called predicate is compared to the call. Because the call has a variable at this position it matches and can be unified: the variable Route in the calling clause will be replaced with the expression [oulu|FromTown1₂] everywhere in the calling clause.

The first matching clause of route is the second one. It is instantiated, and the parameters are unified.

The second clause of route matches, it is instantiated, and the parameters are unified. The unified expressions (including single variables and values) are compared. If the expressions are equivalent or they can be made equivalent substituting their variables with the corresponding expression from the other side and eveluating the arithmetic expressions, then the unification succeeds. If the unification fails, the clause fails. However, in this case the unification succeeds.

Next subgoal (≈statement): The expressions on both sides of the equal sign are unified. In the unification the variable ToTownX₂ is replaced by the value in the right side.

Variable unified. An empty list at the end of a list is implicit and need not to be shown.
Next the predicate connected is called.

The first clause of connected is instantiated.

Searching a road from oulu.

The second clause of connected is instantiated.

Searching a road to oulu.

Found a road from kajaani to oulu.

Connection from oulu to kajaani found.

Here the argument of the operator not is executed first. The not succeeds if its argument fails but fails if the argument succeeds.
Here it is used to check that kajaani is not visited yet.

kajaani is not in the beginning of the path already travelled. Therefore, the first clause of member does not match.

not succeeds, if the argument fails.

Ok. kajaani is not visited.
Next trying to find a route from kajaani. The predicate route will be called recursivey. The first clause does not match, so the second clause will be instantiated with new variables.

Do we find a route from kajaani to joensuu without visiting oulu?

Here the same list is written in two ways: on the left as comma separated members, on the right the first member as head and, after vertical bar, rest as tail.
Where we can go from kajaani?

Searching a road from kajaani.

Found a road to oulu.

Be sure the route does not include oulu already to avoid looping!

Is oulu in the list?

Yes, oulu is in the list.

member succeeded, so not fails: A place already visited does not apply.

After a fail execution goes backwards. Next the connected is redone in order to find another connection.

When redoing, the instance of connect that was executed last is returned to the top of the stack. The execution is started from the end of the clause.
Next the predicate road is redone: Another road from kajaani?

No other roads from kajaani. All variables that have given value in the failed predicate lose their values.

Road to kajaani?

Yes, from joensuu.

Found a 230 km connection between kajaani and joensuu.

Travelled via joensuu already?

joensuu is not at the beginnig of the list.

Is joensuu in the rest of the list?

joensuu is not the next of the list.

Is joensuu in the rest of the list?

No clause of member matches to the call: No, joensuu is not in the list.

Call to member failed, so, this clause fails too.

The not operator changes success to fail and vv. OK. Not in the loop. Go on!

Do we have a route from joensuu to joensuu? Can our program sort it out?

Yes! There is 0 kilometers from joensuu to joensuu!

Total length from kajaani to our destination joensuu...

Total length from oulu to our destination joensuu...

OUTPUT

[oulu, kajaani, joensuu] total length 413 km

STACK

⏩ road(joensuu, kajaani, 230).  % 230 km road connection from Joensuu to Kajaani

⏩ road(kajaani, oulu, 183).  % 183 km road connection from Kajaani to Oulu

⏩ member(H, [H|_]).  % 1

⏩ member(X, [_|T]) :- % 2
⏩   member(X, T). →

⏩ member(X, [_|T]) :- % 2
⏩   member(X, T). →

⏩ connected(Town1, Town2, Length) :- % 2
⏩   road(Town2, Town1, Length). →

⏩ connected(oulu, TownX₂, Length1₂) :- % 1
⏩   road(oulu, TownX₂, Length1₂). →

⏩ route(Town₉, Town₉, _, [Town₉], 0).  % 1

⏩ route(kajaani, joensuu, [oulu|[]], [kajaani|FromTown1₆], Length2₂) :-  % 2
⏩   ToTownX₆ = [kajaani|[oulu]],
⏩   connected(kajaani, TownX₆, Length1₆), → 
⏩   not(member(TownX₆, ToTownX₆)), →   
⏩   route(TownX₆, joensuu, ToTownX₆, FromTown1₆, Length2₆), →
⏩   Length2₂ = Length1₆ + Length2₆.

⏩ route(Town1₂, Town2₂, ToTown1₂, [Town1₂|FromTown1₂], Len₂) :-  % 2
⏩   ToTownX₂ = [Town1₂|ToTown1₂],
⏩   connected(Town1₂, TownX₂, Length1₂), → 
⏩   not(member(TownX₂, ToTownX₂)), →   
⏩   route(TownX₂, Town2₂, ToTownX₂, FromTown1₂, Length2₂), →  
⏩   Len₂ = Length1₂ + Length2₂.

⏩ route(Town, Town, _, [Town], 0).  % 1

⏩ :- route(oulu, joensuu, [], Route₁, Len₁), →   
⏩   writeln(Route₁, ", total length ", Len₁, " km").

DATABASE

  road(joensuu, kajaani, 230). % 230 km road connection from Joensuu to Kajaani
  road(kajaani, oulu, 183). % 183 km road connection from Kajaani to Oulu


  member(H, [H|_]). % 1

  member(X, [_|T]) :- % 2
    member(X, T).

  
  connected(Town1, Town2, Length) :- % 1
    road(Town1, Town2, Length).

  connected(Town1, Town2, Length) :- % 2
    road(Town2, Town1, Length).


  route(Town, Town, _, [Town], 0). % 1

  route(Town1, Town2, ToTown1, [Town1|FromTown1], Length) :- % 2
    ToTownX = [Town1|ToTown1],
    connected(Town1, TownX, Length1), 
    not(member(TownX, ToTownX)),   
    route(TownX, Town2, ToTownX, FromTown1, Length2), 
    Length = Length1 + Length2.
   
   
  :- route(oulu, joensuu, [], Route, Len),
    writeln(Route, ", total length ", Len, " km").