In the last post, we discussed briefly the backtracking search algorithm. Let's explore this topic a little further as it's an important concept in Pilog programming.
This post is based on this tutorial.
A recursive example
Let's illustrate the concept of recursion on a little silly example. Let's say we define two rules for @X "digesting" @Y: either @X has just eaten @Y, or @X has eaten something that has eaten @Y.
(be is_digesting (@X @Y)
(just_ate @X @Y) )
(be is_digesting (@X @Y)
(just_ate @X @Z)
(is_digesting @Z @Y) )
Now let's travel up a whole food chain. A mosquito has been biting John. That mosquito got then eaten by a frog who got eaten by a stork.
(be just_ate (Mosquito (blood John)))
(be just_ate (Frog Mosquito ))
(be just_ate (Stork Frog))
Now, what is the Stork digesting? Let's ask Pilog!
: (? (is_digesting Stork @X))
@X=Frog
@X=Mosquito
@X=(Blood John)
-> NIL
The stork is digesting a frog, a mosquito, and John's blood. Bon appetit!
The order matters
The digestion example was pretty straightforward. However, one thing needs to be understood when we talk about recursion: The order matters - not for the underlying logic, but for the computation in Pilog.
We said, something is digesting @X if:
- it has eaten
@X or
- has eating something that has eaten
@X.
From logic point of view, we could also reverse 1. and 2., and nothing will change.
(be is_digesting (@X @Y)
(just_ate @X @Z)
(is_digesting @Z @Y) )
(be is_digesting (@X @Y)
(just_ate @X @Y) )
The output is the same as in the previous question, just top-down: We get the lowest level first.
: (? (is_digesting Stork @X))
@X=(Blood John)
@X=Frog
@X=Mosquito
-> NIL
Why? Because Pilog is checking if there is a successor ((just_ate @X @Z)) before it checks the direct connection (just_ate @X @Y). This corresponds to a different traversal in a tree search (some examples can be found in the PicoLisp example of this Rosetta code task).
How NOT To Do It
Now let's try another variant which also seems okay from logic point of view:
(be is_digesting (@X @Y)
(is_digesting @Z @Y)
(just_ate @X @Z) )
(be is_digesting (@X @Y)
(just_ate @X @Y) )
What is different? Instead of checking first if an item @Z has been eaten by @X, we check if @Z is digesting @Y. We run our same query again - unfortunately, this calculation never terminates!
: (? (is_digesting Stork @X))
@X=Frog
@X=Mosquito
@X=(blood John)
Instead of terminating, the REPL keeps on printing empty lines and we have to cancel with ^C. Let's trace it again to see what is happening. Again, we can print out the current rules with (rules <predicate(s)>):
: (rules 'is_digesting 'just_ate)
1 (be is_digesting (@X @Y) (just_ate @X @Y))
2 (be is_digesting (@X @Y) (is_digesting @Z @Y) (just_ate @X @Z))
1 (be just_ate (Mosquito (blood John)))
2 (be just_ate (Frog Mosquito))
3 (be just_ate (Stork Frog))
Now we start the query in trace mode, i.e. (? <predicate(s)> (<predicate> <args>)). The beginning looks OK:
: (? is_digesting just_ate (is_digesting Stork @X))
1 (is_digesting Stork @Y)
3 (just_ate Stork Frog)
@X=Frog
@X is unified with Frog due to the first clause of is_digesting and the third clause of the just_ate predicate.
2 (is_digesting Stork @Y)
1 (is_digesting @X @Y)
1 (just_ate Mosquito (blood John))
2 (just_ate Frog Mosquito)
3 (just_ate Stork Frog)
@X=Mosquito
Then the Mosquito is found using the second rule of the is_digesting predicate, which is looking for an @Y that is currently being digested. The Mosquito is digested by the frog (Rule 2). Similarly, (blood John) is also found.
However, if we then press <Enter>, we get a neverending loop of printouts of the following lines:
2 (is_digesting @X @Y)
1 (is_digesting @X @Y)
1 (just_ate Mosquito (blood John))
2 (just_ate Frog Mosquito)
3 (just_ate Stork Frog)
2 (just_ate Frog Mosquito)
3 (just_ate Stork Frog)
3 (just_ate Stork Frog)
What is happening? Like in the examples above, Pilog is trying to find something that "just ate" @Y. But since there is no termination condition for the loop, Pilog tries to recursively replace @Y by something that is "not Stork" in order to find a solution, and gets into an infinite loop.
This is called left recursion and is the root cause of our problem.
Example: Travel plans
Now let's use recursion to solve this little task: Using Pilog to tell us if we can get from A to B using the pre-defined resources.
(be directTrain (Saarbruecken Dudweiler))
(be directTrain (Forbach Saarbruecken))
(be directTrain (Freyming Sorbach))
(be directTrain (StAvold Freyming))
(be directTrain (Fahlquemont StAvold))
(be directTrain (Metz Fahlquemont))
(be directTrain (Nancy Metz))
Obviously, we can directly travel between two cities if there is a direct train.
(be travelBetween (@X @Y)
In case there is no direct train, we can solve it by recursion: We search for another station @Z that is reachable from @X, and check if that station @Z is connected to @Y:
(be travelBetween (@X @Y)
(directTrain @X @Z)
(travelBetween @Z @Y))
Now let's quickly consider what happens if we implement the other way round. Probably if there's a train from X to Y, then there should also be a train from Y to X, right?
So does that mean that we can do something like this - expanding our previous example by simply swapping @X and @Y in each line?
(be travelBetween (@X @Y)
(directTrain @X @Y))
(be travelBetween (@Y @X)
(directTrain @Y @X))
...
Unfortunately not. Since we can go in both directions, we can end up in infinite loops, travelling between X and Y and neever getting any further.
In order to implement something like this, we need to be able to "cut" a search tree after a given result - we will discuss in a further post how to do this.
In the next post, we will see how to work with lists in Pilog, a concept that we also frequently see in "normal" PicoLisp.
Sources
http://www.let.rug.nl/bos/lpn//lpnpage.php?pageid=online
https://giphy.com/gifs/TreehouseDirect-max-and-ruby-maxandruby-maxruby-MxUDoGG7IJg1qWpQay
Roland Lösslein on Unsplash
