# Prolog

Prolog is a declarative programming language based on logical inference. It is the main example of a language in the logic programming paradigm.

tuProlog.zip

Extract the contents of the zip file, and double-click the file bin/2p.jar to start the Prolog interpreter. Or, cd to the bin directory and run the command

java -jar 2p.jar


in a shell window.

## Atoms

Symbols:

Note: names of symbols must be written in lower-case letters.

Numbers:

1 2 3

## Relations

A relation is a table of facts. Here is a father relation

 homer bart homer lisa homer maggie grandpa homer grandpa herb

The first item in each tuple of the relation represents a person who is a father. The second item is a person who is a child of that father.

Relations can thus be formed as a collection of explicit facts, called ground truths. Each fact is a tuple belonging to the relation. In Prolog, we specify ground truths as

relation ( list of atoms )

Here are some ground truths:

## Inference rules

An inference rule allows new facts to be inferred from existing facts.

General form:

conclusion :- hypothesis.

Facts and inference rules may use variables. A variable is a name, in upper-case letters, which stands for some possible member of a tuple in a relation.

Example: X is Y’s paternal grandfather if there exists Z such that X is Z’s father, and Z is Y’s father:

Note that X, Y, and Z are all variables, and the comma means “and” in the sense of a logical conjunction.

We can describe a paternal grandmother in a similar way:

Here is a possible set of inference rules:

Note the definition of the inference rule defining the siblings relation:

The semicolon means “or” in the sense of logical disjunction. That is because two people are siblings if either they share the same father or mother. Also, the \= operator means “not equals”, preventing any person from being considered to be his or her own sibling. (Prolog allows the same value to be bound to multiple variables.)

## Queries

We can type in a potential fact, and based on the ground truths and the available inference rules, Prolog will attempt to find a derivation that proves that the fact is true.

Example:

This query is true because a ground truth matching the query exists.

The query

is false because this fact cannot be derived using the available ground truths and inference rules.

In general, answering a query requires constructing a chain of inferences. For example, the query

is true because the facts

are ground truths, enabling the query

to be true if marge is substituted for the variable Q in the rule defining the samemother relation. This, in turn, is sufficient to deduce that

is true.

A more interesting query

is true because

implies

which is sufficient to deduce that

is true. Note that the query

is false, because there is no derivation for this fact.

## Queries with unknowns

The real power of Prolog can be seen when a query contains one or more variables, which represent unknowns: for each variable, Prolog will attempt to find a value which can be substituted for the variable in order to make the query true.

For example, the query:

yes.
X / grandpa
Solution: paternal_grandfather(grandpa,bart)


showing that grandpa can be substituted for the variable X in order to make the query true.

Note that a query with variables could lead to multiple solutions. For example, the query

yields two solutions, one where lisa is substituted for X, and one where maggie is substituted for X.

## Declarative programming

Prolog is a declarative programming language because we never specify how we want a computation to be performed. We simply use ground truths and inference rules to describe a problem, and allow the inference algorithm to deduce a solution.

Declarative programming is nice because it allows us to specify a problem at a higher level.

Other declarative programming languages:

• Makefiles, a language for directing the compilation of software
• SQL, the database query language

The language for Makefiles is especially interesting because, like Prolog, it is a logic programming language.