Home CPSC 401

Prolog Programming

Overview

Prolog is a logic programming language. Logic programming languages:

The Prolog language is not widely used, but is important in some areas. It has also had an affect on languages like SQL and LINQ.


Predicate Calculus

Programming paradigms are based on underlying mathematical models of computation.
ParadigmModel
ImperativeTuring Machines
FunctionalLambda Calculus
LogicPredicate Calculus

Predicate logic is based on propositions. Examples:


man(bob).
man(fred).
like(bob, steak).

Propositions do not have any intrinsic meaning. The last could mean bob likes steak, is steak, or has steak. The only meaning is what we decide.

Propositions can be used in 2 contexts:

  1. As a statement.
  2. As a query.

More complicated propositions can be formed using the operators:

In predicate logic, these work the same way as they do in traditional languages.

There are also other operators:

The implication operator is used to express propositions such as:


likes(bob, steak) :- man(bob).

The "if" portion is on the right, and the "then" is on the left.

The universal quantifier means "for all" and is used with a variable. If we wanted to express that all men like steak:

ⱯX likes(X, steak) :- man(X).
We could also express mathematical statements:

ⱯX greater(X + 1, X).
ⱯXY equal(X + Y, Y + X).
The existential quantifier "there exists". If we wanted to express the fact that at least one man like steak:

∃X likes(X, steak) && man(X).

Automatic Proofs

Given a set of propositions that are stated to be true, and a query, we would like to be able to mechanically decide if the query follows from the propositions.

This was a large area of research in early computer science and several mathematical theorems have been proved with the help of computers.

This works in part by expanding propositions. For example, if we have the propositions assumed to be true:


ⱯX likes(X, steak) :- man(X).
man(bob).
Then we could plug bob in for X and deduce that:

likes(bob, steak).
Is also true.

Automatic proofs can also take advantage of logical rules. For example, if we have the rules


P :- Q.
R :- P.
Then we can also infer the rule:

R :- Q.

Given a large set of propositions, with multiple variables, this problem becomes very difficult.

Proving general propositions is intractable, but the problem is made much easier by restricting ourselves to horn clauses. There are two forms of horn clauses:

Prolog programs are composed of only Horn clauses. Almost all propositions can be expressed in terms of Horn clauses.


Prolog Terms

Prolog is the most popular logic programming language. Confusingly, there are two different syntaxes: We will look at examples using the Edinburgh syntax.

Prolog code looks almost exactly like the predicate logic examples, except that "and" is done with the comma instead of ampersand.

Prolog has two basic terms:

Prolog also supports integers, floats, lists and strings. Prolog binds values to variables at runtime.

SWI Prolog is installed on cs and can be launched as:


$ swipl -s file.pl
Where file.pl contains clauses assumed to be true. We then can ask queries of Prolog from the shell.

Facts

Headless Horn clauses are also called facts in Prolog. For example:


male(bob).
male(charles).

father(bob, charles).

These facts are stated as true and will be used for inferences.


Rules

Headed Horn clauses are also called rules. For example:


parent(X, Y) :- mother(X, Y).
parent(X, Y) :- father(X, Y).

Here, X and Y are logical variables. The universal quantifier is implied in Prolog.

As with a headed Horn clause, there can be multiple terms on the right:


sibling(X, Y) :- parent(P, X), parent(P, Y), X \= Y.

The and between them is implicit.

How can we write a rule for deciding if a person is a brother or sister of another?



How can we write a rule for deciding if a person is a son or daughter of another?




Queries

Prolog takes facts and rules as input, and then allows us to perform queries. In the family example, we can perform simple queries such as:


male(bob).
male(alice).
male(george).

Prolog will respond to these as either true or false. False simply means it cannot be proven to be true.

How would we ask Prolog if Bob is Claire's father?

We can also have queries with variables in them such as:


brother(X, claire).

Here, Prolog will try to determine a value for X that would make the statement true. It will only report one, even if there are multiple. If there are none, false will be returned.

How can we ask who Alice's daughter is?



We can use as many variables as needed. So to ask for a sibling pair, we could say:

sibling(X, Y).

Simple Calculations

Prolog has arithmetic and comparison operators for simple calculations:

We can use Prolog as a calculator by making math queries:


X is 6 * 7.
X is (3 + 4) * 2.
X is sqrt(100).
We can also make rules using operators: For exmaple to test if a number is larger than another:

larger(X, Y) :- X > Y.

This will return either true or false. If we wanted to return some calculation, we would need a variable for Prolog to infer a value for:


% if X >= Y, then X is the max
max(X, Y, X) :- X >= Y.

% if X is less, than Y is the max
max(X, Y, Y) :- X < Y.

How can we write a rule to infer the absolute value of a number?




Say we are measuring MPG for vehicles and have facts on the distances cars went and how many gallons of gas they comsumed:


distance(a, 20.4).
distance(b, 28.3).
distance(c, 22.6).

consumed(a, 1.3).
consumed(b, 1.5).
consumed(c, 1.0).
How could we write a rule called "mpg" that infers the MPG of any car?



More complex calculations are also possible with Prolog. The "is" operation assigns a constant variable. For example, the following two rules calculate factorials:


-- base case
fact(0, 1).

-- we specify the  form of the answer only
fact(N, R) :- fact(N1, R1), N is N1 + 1, R is R1*N.

How Prolog Works

Prolog does not execute at all like traditional languages. Instead of following instructions one by one until the end, it starts with the facts and expands out until it reaches the goal.

During this time it may have to backtrack from a path that does not reach the goal.

We can see this in SWI Prolog with the trace command:


trace.


Conclusion

Despite how different Prolog is, it's a Turing complete language.

Due to the fact that it is inefficient and relatively difficult to reason about, it is only used in certain areas:

Copyright © 2018 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.