# Learning Pilog - 4: Recursion 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 )``: ``` : (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. ``(? ( ))``. 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 ````, 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 Roland Lösslein on Unsplash