# Learning Pilog - 7: Cuts and Negations

Welcome to the last part of the Prolog Crash Course. Today we will talk about Cuts and Negations.

This post is based on [this tutorial](http://www.let.rug.nl/bos/lpn//lpnpage.php?pagetype=html&pageid=lpn-htmlch10).

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


### What is a "Cut"?

In the previous posts, we saw several examples of Prolog's backtracking behaviour. In some examples, we needed a lot of steps to travel the whole search tree. This can be inefficient, for example in cases where we **know** that there is only a single legitimate solution and no need to search further.

The **cut** operator ``T`` is designed to control the backtracking behaviour in order to increase efficiency. Let's look at an example.

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

We define a predicate ``maxi/3``: the first two arguments define a range of numbers, and the third argument is equal to the maximum value of these two.  In other words, this fact should return ``T``:

```
: (? (maxi 5 1 5))
-> T
```

while these ones are ``NIL``:

```
: (? (maxi 2 3 2))
-> NIL
: (? (maxi 2 3 5))
-> NIL
```

Of course we can also query the maximum:

```
: (? (maxi 2 3 @Max))
 @Max=3
-> NIL
```

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


Now let's define ``maxi``. We want to compare two numbers ``@X`` and ``@Y``. To do this, we can call a PicoLisp function. The corresponding clause has three parts:
- the ``^`` symbol in the CAR,
- the PicoLisp program body in the CDDR,
- the variable to which the result is unified in the CADR.

```
(be maxi (@X @Y @Y)
   (^ @ (<= @X @Y)) )  

(be maxi (@X @Y @X)
   (^ @ (> @X @Y)) )
```
We don't really care for the result as such, this is why the variable ``@`` is anonymous.

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

Prolog tests two cases: first if ``@X <= @Y``, and then if ``@X>@Y``. Where is the problem? 

Our definition is not wrong, but it is unefficient. If the first clause already returns ``T``, there is actually no need to test for the second condition. The first and second clause are mutually **exclusive**. In this case, the **cut operator** comes in handy.

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

With the following notation, we can tell Prolog to stop if the first clause evaluates to ``T``:

```
(be maxi (@X @Y @Y)
   (^ @ (<= @X @Y))
   T)
```

This type of cut is called a **green cut**, because there is no influence on the program output itself if you remove the cut symbol ``T``. 

On the other hand, **red cuts** are cuts that causes a program change. These cuts can be dangerous and need to be tested well.

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


### Negation as a failure

There are [two kinds of negations](https://en.wikipedia.org/wiki/Negation_as_failure) in formal logic. *Strong negation* means that a statement is considered as false only if it can be proven to be false. On the other hand, *weak negation* means that if a statement cannot be proven true, it is considered as false. Latter one is also called **negation as a failure**.

*(In Prolog, this is implemented as **negation as failure** operator and can be written as ``\+``)*.

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

Why do we need it? We can implement it to describe "except" statements, such as: "Mary likes all animals except insects". In Pilog, we can implement it using the cut operator and the built-in predicate ``(fail)``:

```
# Mary likes all animals except insects.
(be likes (Mary @X)
   (insect @X)
   T
   (fail) )

(be likes (Mary @X)
   (animal @X) )
```

where animals are:

```
(be animal (@X) (insect @X))
(be animal (@X) (pet @X))
(be animal (@X) (cattle @X))

(be insect (Spider))
(be pet (Cat))
(be pet (Dog))
(be cattle (Cow))
```

Let's test it:

```
: (? (likes Mary Cat))
-> T

: (? (likes Mary Spider))
-> NIL
```

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

Congratulations, with this post we have finished the Pilog introduction. In the next posts, we will see how we can embed it into PicoLisp and use it for database queries.

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

# Sources
http://www.let.rug.nl/bos/lpn//lpnpage.php?pagetype=html&pageid=lpn-htmlch10