# Prolog

## Overview

- Created in the 1970s
- Prolog = “PROgramming in LOGic”
- There are many different implementations, e.g. SWI-Prolog and GNU Prolog
- Prolog is a
*logic programming language*and*declarative*in nature - Prolog is
*turing-complete*(turing.pl)

## Example Program (Reference)

- A Prolog program consists of
*predicates*which define*relations*between arguments

```
% move(N,X,Y,Z) - move N disks from peg X to peg Y, with peg Z being the
% auxilliary peg
%
% Strategy:
% Base Case: One disc - To transfer a stack consisting of 1 disc from
% peg X to peg Y, simply move that disc from X to Y
% Recursive Case: To transfer n discs from X to Y, do the following:
Transfer the first n-1 discs to some other peg X
Move the last disc on X to Y
Transfer the n-1 discs from X to peg Y
move(1,X,Y,_) :-
write('Move top disk from '),
write(X),
write(' to '),
write(Y),
nl.
move(N,X,Y,Z) :-
N>1,
M is N-1,
move(M,X,Z,Y),
move(1,X,Y,_),
move(M,Z,Y,X).
```

- A clause consists of a
*head*and a*body*

```
% a simple clause
Head :- Body.
```

- This means: if
`Body`

is true, then`Head`

is true - Since Prolog is declarative, we specify the result we are interested in and not the concrete steps to compute a result
- We are not concerned
*how*Prolog finds these results

## Logical Foundations of Prolog

- Prolog is based on first-order predicate logic
- A Prolog program is a sequence of Horn clauses
- Prolog uses resolution internally

Resolution is based on the idea of proof by contradiction: To prove a logical consequence of a set of axioms, we assume the opposite of what we want to prove, and show that this contradicts the axioms which we take for granted

- There are different evaluation strategies for resolution

## Syntax

### Terms

- Prolog is
*dynamically typed*and has a single data type called the*term* - All data and programs are represented by terms
- Terms are either
*atoms*, numbers, variables or*compound*terms - Atoms and numbers are sometimes grouped together and called
*atomic terms*

### Atoms

- An atom is just a name that can serve multiple purposes
- It consists of a sequence of letters, if it contains spaces, you need to use quotes
- Uppercase atoms must also be put into quotes, otherwise they would be treated as variables

### Compound Terms

- Consist of a
*functor*(a Prolog atom) and a number of*arguments*(Prolog terms) enclosed in parentheses and separated by commas

### Predicates

- Each predicate has
- Name: which is an
*atom* - Zero or more Arguments: is an arbitrary term

- Name: which is an
- A predicate with name
`Pred`

and`N`

arguments is denoted by`Pred/N`

- That notation is called a
*predicate indicator* `N`

is called the*arity*of the predicate- A predicate is defined by a collection of
*clauses* - A clause is either a
*rule*or a*fact* - Clauses denote logical alternatives: If
*any*clause is true, then the whole predicate is true

### Rules

- A rule is of the form
`Head :- Body.`

- The notation of the head of a rule depends on the number of arguments:
- If the predicate has zero arguments, then the head is only the name of the predicate
- If a predicate has
`N`

arguments, then the head is written as`PredName(Arg1, Arg1, ...)`

- The body of each rule is a Prolog
*goal* - A goal is a
*term*that denotes the predicate and its arguments - Rules can be
*recursive*

### Facts

- A fact is written as
`Head.`

- This is equivalent to the rule
`Head :- true.`

- A fact is always true

### Queries

- After a Prolog program is compiled, you submit queries to the interpreter
- A query has the same structure as the body of a rule
- It is a sequence of predicates separated by commas and terminated by a dot

`?- small(X), green(X), smily(X).`

## References

- The Power of Prolog by Markus Triska
- SWI-Prolog manual
- Intro to Prolog by Ulle Endriss