# Introduction

This page provides a very brief overview of prolog. For more documentation look at the documentation page. Also be aware that this introduction is only my explanation, so don't take it as 100% truth.

First of all, prolog is a programming language in the family of languages called logic programming languages. This means that it is very different from imperative or functional programming, so you should read this with an open mind and try to forget some of the things you already know.

# Logic

What does it mean to be a logic programming language? Well, it means that the programs written in it can be understood as logical rules and results can be inferred from those rules. This leads to a very declarative way of writing code which is often much cleaner than what could be written in C for example.

It also means that in prolog we don't write code to tell the computer what to do, we write code to express the facts and relations about a problem, and the prolog system then uses those facts and rules to infer the result.

# Example

To calculate the length of a list in an imperative language like C, the following code would work.

```typedef struct List List; struct List { int element; List *next; }; int length(List *list) { int len = 0; for(; list != nil; list = list->next) len++; return len; } ```

It is very clear that the `length` function takes a list as input and then runs a loop which increments `len` until the end of the list is reached.

Compare this to the prolog code below which is a prolog predicate with arity 2, also sometimes called `length/2` to describe the name and the arity.

```length([], 0). length([_|Tail], N) :- length(Tail, TailLength), N is TailLength + 1. ```

This code is written in a declarative style and it doesn't express how the length of the list is found, it expresses what the length of a list is. The code consists of two clauses: a fact and a rule.

The fact `length([], 0).` describes that the length of an empty list (`[]`) is zero.

The rule

```length([_|Tail], N) :- length(Tail, TailLength), N is TailLength + 1. ```

describes that the length of a non-empty list with head `_` (we don't care about the head), and tail `Tail` has then length `N` if:

1. The length of the tail is `TailLength` and
2. `N` is `TailLength` plus one.

The rule consists of a head `length([_|Tail), N)` and two goals separated by a comma which means and.

# Wait, is the output just the last parameter?

No, in general much prolog code describes relations between the parameters. The length predicate from before as an example of that, but it could just as well be used to check if a list has a given length, by providing an input for both arguments.

# Queries

When `pprolog` is run it presents a toplevel where queries can be entered. The queries are like questions that the prolog system tries to answer. It does this by looking in the prolog database which initially consists of the predicates which are part of the standard library. Since `length/2` is part of the standard library, we could ask

```?- length([1,2,3,a,b,c], Len). ```

And it would respond

```Len = 6. ```

In general, if a word starts with an uppercase letter it is a variable like `Len`, `Hello`, `X` and `Y`, and otherwise it is an atom which just represents itself.

To show that `length/2` can be used in multiple ways, consider the query

```?- length([1,2], 4). ```

What do you think it will say? The result is

```false. ```

because it is not possible for the system to infer the the length of the list `[1,2]` is `4` using any of the rules in the prolog database. The steps the system takes in calculating this result are:

1. The fact `length([],0)` is tried first but it fails to unify (more on that later) with the query since the empty list does not unify with our non-empty list, and 0 does not unify with 4.
2. The rule with the head `length([_|Tail], N)` is chosen at it unifies with our query giving the variables `Tail = ` and `N = 4`.
3. The first goal is `length(Tail, TailLength)` and with the value of `Tail` that becomes `length(, TailLenght)`. As in step 1, the first fact does not unify with this goal since `[]` does not unify with ``.
4. The second rule unifies with our goal and the variables become `Tail = []` and `N = TailLength`. Note that it is perfectly valid to assign two unassigned variables to each other in prolog, and this just means that they should now be considered the same, and when one of them is unified with a concrete value, the other will get that value too.
5. The first subgoal is tried again and this time it matches the first rule since `[]` unifies with `[]`, and `0` unifies `TailLength` with the side effect that both `TailLength` and `N` is now 0.
6. We go back to step 4 and continue with subgoal 2 which says that `N` is `TailLength + 1` and N is therefore 1.
7. We go back to step 3 and continue with subgoal 2 which says that `N` is `TailLength + 1` but this fails since `N` at this point was 4 and `TailLength` is 1, but the fact `4 = 1 + 1` is false. Since there are no more rules or facts to try, the whole query fails.

(that explanation was a mess)

# Unification

say wut, like pattern matching but works both ways.