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

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

1 2 3 4 5 6

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]

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 exagerating a bit, but let't 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 clausel per clausel 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_.

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 first__ and makes use of __backtracking__.

### Operators

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

* ```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 respectivelly. * A variable unifies with any term and generates the respectivetelly 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 cicles. Formally, this is something not desirable but the occurs-check is performance expensive. In swi-Prolog it is standart on and in Sistus is standard off.

Example of output:

``` bash % 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!