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.

## Top comments (0)