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.
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.
Keep in mind: there is no type declaration in PROLOG. The interpreter will figure it out for you. :)
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]
A String is a list of characters’ ASCII codes:
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_.
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__.
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)
The infix operator
* ```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.
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:
% 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!