Learning Pilog - 4: Recursion
Tags: picolisp, lisp, functional, logic
Published: 2022-06-13 14:16:47

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](http://www.let.rug.nl/bos/lpn//lpnpage.php?pageid=online).

-------------------------

### 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))
```


----------------

![giphy.gif](https://cdn.hashnode.com/res/hashnode/image/upload/v1635351747926/pt2fhV0Hu.gif)

-------------------------


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:
1. it has eaten ``@X`` or 
2. 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](https://picolisp-blog.hashnode.dev/binary-tree-traversal-part-1)).


-------------------------

### 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

----------------------------

![train.jpg](https://cdn.hashnode.com/res/hashnode/image/upload/v1635355359862/8CZSBelJT.jpeg)

---------------------------

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   
<a href="https://unsplash.com/@roland_loesslein?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText">Roland Lösslein</a> on <a href="https://unsplash.com/s/photos/train?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText">Unsplash</a>