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.
| Paradigm | Model |
| Imperative | Turing Machines |
| Functional | Lambda Calculus |
| Logic | Predicate 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:
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).
ⱯX greater(X + 1, X).
ⱯXY equal(X + Y, Y + X).
∃X likes(X, steak) && man(X).
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).
likes(bob, steak).
Automatic proofs can also take advantage of logical rules. For example, if we have the rules
P :- Q.
R :- P.
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:
Headless
A simple proposition such as:
man(bob).
likes(bob, steak).
!likes(bob, salad).
Headed
A proposition with a simple proposition that is implied by a set of propositions anded together:
likes(X, steak) :- man(X).
eats(steak, X) :- likes(steak, X) && hungry(X).
Prolog programs are composed of only Horn clauses. Almost all propositions can be expressed in terms of Horn clauses.
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 the CPSC server and can be launched as:
$ swipl -s file.pl
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.
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?
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?
sibling(X, Y).
We can use Prolog as a calculator by making math queries:
X is 6 * 7.
X is (3 + 4) * 2.
X is sqrt(100).
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, X, Y) :- X >= Y.
% if X is less, than Y is the max
max(Y, X, 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).
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.
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.
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 © 2024 Ian Finlayson | Licensed under a Creative Commons BY-NC-SA 4.0 License.