barbie's notes - PROLOG - Part 8


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]

Strings

A String is a list of characters’ ASCII codes:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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:

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

Unification operator

The infix operator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

* ```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!