**There is logic behind everything and every rule. We sometimes negate this but every thing and every happening has a logic and reason behind it.**

## PROLOG Internals

In my last post I wrote about **cut**, **fail** and **repeat**. This time I am going to expand the understanding on internals and data structures.

Terms can be constants, variables or a structure.

- A
*constant*may be an*atom*or a*number*- which can be an integer or real number. We defined*atom*some posts ago. :) - A
*variable*is a string of letters, digits and / or underscores starting with a upper-case letter or an underscore. - A
*structure*represents an atomic preposition of predicates. Structures have the form`blub(t1,t2,t3,...,tn)`

where blub is our*atom*and t1,t2,…,tn are our parameters. n is also the arity of our term.

Keep in mind: there is no type declaration in PROLOG. The interpreter will figure it out for you. :)

### Lists

The lists are build of the structure .(H,T) and the atom []. For example, the list `[a,b,c]`

is represented by the term `.(a,.(b,.(c,[])))`

. A built-in list notation is also available, which defines the head and the tail of the list, as [H,T]. For example, our `[a,b,c] = .(a,.(b,.(c,[]))) = [a|[b,c]] = [a,b|[c]] = [a,b,c|[]] = [a,b,c]`

### Strings

A String is a list of characters’ ASCII codes: `"PROLOG" = [80,82,79,76,79,71]`

or `"barbie" = [98, 97, 114, 98, 105, 101].`

Important: Strings are always declared with double quotes. ‘PROLOG’ != “PROLOG” :)

## Run time =)

No, you don’t need to run! But how a program actually works in PROLOG? How can PROLOG solve **ALL OUR PROBLEMS** (Ok, maybe exaggerating a bit, but let’s say 95% of our problems!). If you look a PROLOG code, it is nothing more than a set of Horn clauses. All facts, rules and questions are stated in a `.pl`

file and that’s it! The magic word here is *inference*.

### Inference

Let’s assume we want to prove `? G1, G2, ..., Gn`

. PROLOG is going to check clause per clause from the beginning to the end of the file until it finds a rule which the *head* **unifies** with out first goal `G1`

. This *unification* will substitute (the generic unifier) g.

We have three possibilities:

`C :- P1, ..., Pm`

is the found rule. g is so that`C g = G1 g.`

is true. Now PROLOG will continue with`? P1g, P2g,...,Pmg, G2g, ..., Gng`

.`F`

is found. g is so that`F g = G1 g`

and PROLOG will continue with`? G2g, ..., Gng`

.- Nothing is found. PROLOG returns
*false*.

- Nothing is found. PROLOG returns

The proving algorithm terminates, when there is nothing more to prove - the goal is empty - or the prove fails. The interpreter answers the initial question instantiating the substitutions for the variables in the question itself.

The proving algorithm runs

top down,depth firstand makes use ofbacktracking.

### Operators

It is possible to declare functions like prefix, posfix or infix operators, connecting it to a precedence. It follows the pattern:

`:- op(precedence, type, name)`

### Unification operator

The infix operator `=`

is responsible for establishing the unification relation between two operators.

`T1=T2`

is true if, and only if, a substitution g exists, which when applied to both terms T1 and T2, both are literally equal, this means`T1g==T2g`

.- Two functions unify only if the main atoms of the two terms are equal and have the same arity, and the arguments unify themselves respectively.
- A variable unifies with any term and generates the respectively an instance.
- Two atoms unify if, and only if, the are exactly the same.

### Occurs-Check

Swi-Prolog and Sistus allow the unification of a variable with a term where this variable *occurs*. That means, it is possible to create recursion or cycles. Formally, this is something not desirable but the occurs-check is performance expensive. In swi-Prolog it is standard on and in Sistus is standard off.

Example of output:

```
% Without occurs-check
?- X = f(X).
X = f(f(f(f(f(f(f(f(f(f(...)))))))))) ?
% With occurs-check
?- X = f(X).
X = f(X).
```

I am pretty sure, this is an huge amount of information to process! Next blog post will be more hands on: Debugging!