Prolog Summary
SWI-Prolog is installed on the computers in the departmental PC Lab. It can also be downloaded from: You can find other resources about Prolog on the class home page, including links to tutorials.
Program Structure – Basic Symbols
A Prolog program consists of a text file containing symbols, or terms. There are three categories of terms:
- Constants: name object or relationships; can be either atoms or integers
- Atoms: a name (sometimes called an instance) or an operator.
A name starts with a lower case letter and can include letters, digits, and the underscore character. It refers to a specific entity or a specific relation: A name can also be a string, enclosed in single quote marks.
Operators consist of special characters, including :-, +, <. See the SWI Prolog help file for a list of operators that work for this version. - Variables: aren’t bound to any object or type until the resolution process begins.
Variables begin with an uppercase letter, or an underscore in some cases. - Structures: an atomic proposition: functor(parameter list)
A functor is typically a relation name, (sometimes called a predicate). The other components are arguments enclosed in parentheses: e.g., male(robert) is a structure that contains two atoms, male and robert. The functor is male, and the argument is robert. - List: a common data structure, composed of an ordered sequence of elements or terms, separated by commas, enclosed within [ ], ex: [a, b, c]
The elements may be any term: constant, variable, or structure, including another list.
Comments: Indicated by %. Causes the processor to ignore everything from the % to the end of the line.
Program Structure – Statement Types
A Prolog program consists of a collection of facts and rules (sometimes referred to as a database). Facts state relationships between objects; rules can be used to draw inferences from the facts. The user enters queries, or goal statements, and the language system tries to satisfy the goals using the facts and rules in its database.
All statements must end with a period!Facts
A fact is a logical predicate whose truth is asserted by its appearance in the program’s database.
Examples:
pet(john, dog).% asserts that john’s pet is a dog
female(jane).% asserts that jane is female
parent(mary, jane).% asserts that mary is the parent of jane
Note that the semantics of the statements is left to the programmer’s interpretation. For example, the first statement could mean that a pet dog is named john. The third statement could also mean that the parent of mary is jane.
Rules
A rule states a relation between propositions. It allows new propositions to be inferred from existing facts.
For example:
(1) grandparent(X,Y) :- parent(X,Z), parent(Z,Y).
or
(2) has_wings(X) :- bird(X).
The above rules could be interpreted as follows:
(1)X is a grandparent of Y if X is a parent of Z and Z is a parent of Y.
(2)If X is a bird then X has wings.
Rule syntax: “consequent :- antecedent”. The antecedent may be a conjunction of terms; where the comma represents a logical AND. All clauses must be true for the antecedent to be true. The consequent is called the head of the rule and the antecedent is the body.
Unification, Theorem Proving, and Backtracking
In the example rules, X, Y, and Z are variables. Unification is a process that tries to find values for X, Y and Z in the database that make all of the clauses (conditions) true, and therefore the rule, true. This is called theorem proving.
The conditions in the body of a rule are evaluated one-by-one in sequence. If any one condition cannot be satisfied at all, then the rule fails.
Prolog automatically uses backtracking to explore every path to a solution. For example, consider the grandparent rule from earlier.
grandparent(X,Y) :- parent(X,Z), parent(Z,Y).
Suppose the database contains the following facts:
parent(john, james).
parent(sara, susan).
parent(susan, john).
The theorem prover will first attempt to find facts in the database to support the first clause. The first fact that matches is
parent(john, james).
Variables X and Z will be instantiated with X = john and Z = james. The theorem prover will then try to prove the second clause by looking for a fact that matches:
parent(james, Y).
If it found a clause that matched, it would return that as an answer. In this case there is no matching clause, so Prolog will backtrack to the first clause and attempt to find another solution to try. Next, X and Z will be instantiated with X = sara and Z = susan. Prolog’s attempt the match parent (susan, Y) will succeed, and the result X = sara, Y = john will be returned.
Goals
Goals are often referred to as queries. When the interpreter is presented with a goal or query, it attempts to satisfy it. The answer it gives may be a yes or no, or it may contain instances from the database that satisfy the query. For example:
?- female(jane). % this query asks if jane is female.
yes
?- female(anna).
no% this only means there is no data to satisfy this query
?- female(X) % this query asks if there is a female
X = jane% and the response gives an instantiation
?- parent(X, jane)
X = mary % NOTE in swi-prolog, you must hit the “;” key when
X = paul % you want to see the next answer for X in succession
No% There are no more parents of jane in the database.
Special Features
The Cut
The Cut (!) provides explicit control over backtracking. It basically says, do not backtrack over me. It is very useful in situations where expressing negation is necessary. For example:
nonsibling(X,Y) :- sibling(X,Y), !, fail.
nonsibling(X,Y).
The first rule above says that if X and Y are siblings, then do not backtrack and cause this rule to fail. The second rule gives a “yes” answer if the first one fails. (Rules are evaluated in the order in which they are encountered in the database.)
Notice that you can express a rule as a set of alternatives by having two (or more) rules for the same predicate.
Lists
The symbol [] represents the empty list. Lists are represented as comma-separated symbols between the [], such as [dog, cat, x].
A list may be denoted as the head followed by “the rest of the list”. This is similar to the notion of CAR and CDR in LISP. Note that the head is the first element and the tail is always a list. A list expressed in this form looks like [Head | Tail], where Head and Tail are my variables representing the 2 portions of this list.
The following rules define what it means for an element to be a member of a list.
member(_ , []) :- fail. % nothing is a member of the empty list
member(X, [X | _] ).% assert that X is a member of the list
% if it is the first item in the list
member(X, [_ | Tail] ) :-%X is a member of the list if it appears
member (X, Tail).% in the tail of the list
In the above example, the _ symbol is used to represent a variable for which you do not care what the value is. It is anonymous, you don’t need its value to resolve any of the conditions.
Arithmetic in Prolog
Arithmetic in logic programming also uses the method of finding bindings for variables. Here we are finding a value to bind to numbers rather than just symbols. There is not a notion of a variable in the traditional sense; that is we don’t use variables to store partial results as we compute values.
For example:
length([], 0). % the length of the null list is 0
length([_ | T] , N) % the length of a list is N such that
:- length(T, NT), % NT is the length of the tail and
N is NT + 1.% N is equivalent to NT + 1
In other words, it is the interpreter’s job to find bindings for N and NT that make the conditions true. Note that some dialects of Prolog use the symbol = for this, N = NT + 1.
Miscellaneous Predicates
There are usually built-in predicates (rules, functors) supplied for screen i/o such as read, write, print, writeq. The predicate nl causes a new line to be written to the screen. The i/o predicates always return success.
SWI-Prolog Environment
When you start SWI-Prolog, it launches an interactive querying window. You will get the ?- prompt, which means it is ready to begin accepting queries.
?- [‘c:/temp/myprg.pl’].
The above command will load and compile the given file. Or, on the drop-down file menu select open and navigate to your file. It will load into the top window.
Some other query examples, assuming that length and member are implemented:
?- length([a,b,c], X).
X=3
yes
?- length([a, b, c], 3).
yes
?- member(d, [a,b,c]).
no
HELP:
To get the help index, enter the query: ?- help. This will launch a separate window that will allow you to search and browse for useful predicates. The very first predicates listed in the index will be the operators, such as comparisons and equality. Remember that numbers and strings will be treated a little bit differently depending on the operator you choose.
HALT:
To exit the SWI environment, type in the query: halt. This will close the window and stop prolog.
Prolog Summary1