Prolog is a general purpose
logic programmingLogic programming is, in its broadest sense, the use of mathematical logic for computer programming. In this view of logic programming, which can be traced at least as far back as John McCarthy's [1958] advice-taker proposal, logic is used as a purely declarative representation language, and a...
language associated with
artificial intelligenceArtificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
and
computational linguisticsComputational linguistics is an interdisciplinary field dealing with the statistical or rule-based modeling of natural language from a computational perspective....
.
Prolog has its roots in
first-order logicFirst-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...
, a
formal logicClassical or traditional system of determining the validity or invalidity of a conclusion deduced from two or more statements...
, and unlike many other
programming languageA programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
s, Prolog is
declarativeIn computer science, declarative programming is a programming paradigm that expresses the logic of a computation without describing its control flow. Many languages applying this style attempt to minimize or eliminate side effects by describing what the program should accomplish, rather than...
: the program logic is expressed in terms of relations, represented as facts and rules. A computation is initiated by running a
query over these relations.
The language was first conceived by a group around
Alain ColmerauerAlain Colmerauer is a French computer scientist.After completing his Ph.D. at the University of Grenoble, he spent 1967–1970 as Assistant Professor at the University of Montreal, where he created Q-Systems, one of the earliest linguistic formalisms used in the development of the TAUM-METEO machine...
in
MarseilleMarseille , known in antiquity as Massalia , is the second largest city in France, after Paris, with a population of 852,395 within its administrative limits on a land area of . The urban area of Marseille extends beyond the city limits with a population of over 1,420,000 on an area of...
,
FranceThe French Republic , The French Republic , The French Republic , (commonly known as France , is a unitary semi-presidential republic in Western Europe with several overseas territories and islands located on other continents and in the Indian, Pacific, and Atlantic oceans. Metropolitan France...
, in the early 1970s and the first Prolog system was developed in 1972 by Colmerauer with Philippe Roussel.
Prolog was one of the first logic programming languages, and remains among the most popular such languages today, with many free and commercial implementations available. While initially aimed at
natural language processingNatural language processing is a field of computer science and linguistics concerned with the interactions between computers and human languages; it began as a branch of artificial intelligence....
, the language has since then stretched far into other areas like
theorem provingAutomated theorem proving or automated deduction, currently the most well-developed subfield of automated reasoning , is the proving of mathematical theorems by a computer program.- Decidability of the problem :...
,
expert systemIn artificial intelligence, an expert system is a computer system that emulates the decision-making ability of a human expert. Expert systems are designed to solve complex problems by reasoning about knowledge, like an expert, and not by following the procedure of a developer as is the case in...
s, games, automated answering systems, ontologies and sophisticated
control systemA control system is a device, or set of devices to manage, command, direct or regulate the behavior of other devices or system.There are two common classes of control systems, with many variations and combinations: logic or sequential controls, and feedback or linear controls...
s. Modern Prolog environments support creating
graphical user interfaceIn computing, a graphical user interface is a type of user interface that allows users to interact with electronic devices with images rather than text commands. GUIs can be used in computers, hand-held devices such as MP3 players, portable media players or gaming devices, household appliances and...
s, as well as administrative and networked applications.
Syntax and semantics
In Prolog, program logic is expressed in terms of relations, and a computation is initiated by running a
query over these relations. Relations and queries are constructed using Prolog's single data type, the
term. Relations are defined by
clauses. Given a query, the Prolog engine attempts to find a
resolutionIn mathematical logic and automated theorem proving, resolution is a rule of inference leading to a refutation theorem-proving technique for sentences in propositional logic and first-order logic...
refutation of the negated query. If the negated query can be refuted, i.e., an instantiation for all free variables is found that makes the union of clauses and the singleton set consisting of the negated query false, it follows that the original query, with the found instantiation applied, is a logical consequence of the program. This makes Prolog (and other logic programming languages) particularly useful for database, symbolic mathematics, and language parsing applications. Because Prolog allows impure predicates, checking the truth value of certain special predicates may have some deliberate side effect, such as printing a value to the screen. Because of this, the programmer is permitted to use some amount of conventional
imperative programmingIn computer science, imperative programming is a programming paradigm that describes computation in terms of statements that change a program state...
when the logical paradigm is inconvenient. It has a purely logical subset, called "pure Prolog", as well as a number of extralogical features.
Data types
Prolog's single
data typeIn computer programming, a data type is a classification identifying one of various types of data, such as floating-point, integer, or Boolean, that determines the possible values for that type; the operations that can be done on values of that type; the meaning of the data; and the way values of...
is the
term. Terms are either
atoms,
numbers,
variables or
compound terms.
- An atom is a general-purpose name with no inherent meaning. Examples of atoms include
x
, blue
, 'Taco'
, and 'some atom'
.
- Numbers can be floats
In computing, floating point describes a method of representing real numbers in a way that can support a wide range of values. Numbers are, in general, represented approximately to a fixed number of significant digits and scaled using an exponent. The base for the scaling is normally 2, 10 or 16...
or integerThe integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s.
- Variables are denoted by a string consisting of letters, numbers and underscore characters, and beginning with an upper-case letter or underscore. Variables closely resemble variables in logic in that they are placeholders for arbitrary terms.
- A compound term is composed of an atom called a "functor" and a number of "arguments", which are again terms. Compound terms are ordinarily written as a functor followed by a comma-separated list of argument terms, which is contained in parentheses. The number of arguments is called the term's arity
In logic, mathematics, and computer science, the arity of a function or operation is the number of arguments or operands that the function takes. The arity of a relation is the dimension of the domain in the corresponding Cartesian product...
. An atom can be regarded as a compound term with arity zero. Examples of compound terms are truck_year('Mazda', 1986)
and 'Person_Friends'(zelda,[tom,jim])
.
Special cases of compound terms:
- A List is an ordered collection of terms. It is denoted by square brackets with the terms separated by commas or in the case of the empty list,
[]
. For example [1,2,3]
or [red,green,blue]
.
- Strings: A sequence of characters surrounded by quotes is equivalent to a list of (numeric) character codes, generally in the local character encoding
A character encoding system consists of a code that pairs each character from a given repertoire with something else, such as a sequence of natural numbers, octets or electrical pulses, in order to facilitate the transmission of data through telecommunication networks or storage of text in...
, or UnicodeUnicode is a computing industry standard for the consistent encoding, representation and handling of text expressed in most of the world's writing systems...
if the system supports Unicode. For example, "to be, or not to be"
.
Rules and facts
Prolog programs describe relations, defined by means of clauses. Pure Prolog is restricted to Horn clauses. There are two types of clauses: facts and rules. A rule is of the form
Head :- Body.
and is read as "Head is true if Body is true". A rule's body consists of calls to predicates, which are called the rule's
goals. The built-in predicate
,/2
(meaning a 2-arity
operatorProgramming languages typically support a set of operators: operations which differ from the language's functions in calling syntax and/or argument passing mode. Common examples that differ by syntax are mathematical arithmetic operations, e.g...
with name
,
) denotes
conjunctionIn logic and mathematics, a two-place logical operator and, also known as logical conjunction, results in true if both of its operands are true, otherwise the value of false....
of goals, and
;/2
denotes
disjunctionIn logic and mathematics, a two-place logical connective or, is a logical disjunction, also known as inclusive disjunction or alternation, that results in true whenever one or more of its operands are true. E.g. in this context, "A or B" is true if A is true, or if B is true, or if both A and B are...
. Conjunctions and disjunctions can only appear in the body, not in the head of a rule.
Clauses with empty bodies are called
facts. An example of a fact is:
cat(tom).
which is equivalent to the rule:
cat(tom) :- true.
The built-in predicate
true/0
is always true.
Given the above fact, one can ask:
is tom a cat?
?- cat(tom).
Yes
what things are cats?
?- cat(X).
X = tom
Clauses with bodies are called
rules. An example of a rule is:
animal(X):- cat(X).
If we add that rule and ask
what things are animals?
?- animal(X).
X = tom
Due to the relational nature of many built-in predicates, they can typically be used in several directions. For example,
length/2
can be used to determine the length of a list (
length(List, L)
, given a list
List
) as well as to generate a list skeleton of a given length (
length(X, 5)
), and also to generate both list skeletons and their lengths together (
length(X, L)
). Similarly,
append/3
can be used both to append two lists (
append(ListA, ListB, X)
given lists
ListA
and
ListB
) as well as to split a given list into parts (
append(X, Y, List)
, given a list
List
). For this reason, a comparatively small set of library predicates suffices for many Prolog programs.
As a general purpose language, Prolog also provides various built-in predicates to perform routine activities like
input/outputIn computing, input/output, or I/O, refers to the communication between an information processing system , and the outside world, possibly a human, or another information processing system. Inputs are the signals or data received by the system, and outputs are the signals or data sent from it...
, using graphics and otherwise communicating with the operating system. These predicates are not given a relational meaning and are only useful for the side-effects they exhibit on the system. For example, the predicate
write/1
displays a term on the screen.
Evaluation
Execution of a Prolog program is initiated by the user's posting of a single goal, called the query. Logically, the Prolog engine tries to find a
resolutionIn mathematical logic and automated theorem proving, resolution is a rule of inference leading to a refutation theorem-proving technique for sentences in propositional logic and first-order logic...
refutation of the negated query. The resolution method used by Prolog is called
SLD resolutionSLD resolution is the basic inference rule used in logic programming. It is a refinement of resolution, which is both sound and refutation complete for Horn clauses.-The SLD inference rule:...
. If the negated query can be refuted, it follows that the query, with the appropriate variable bindings in place, is a logical consequence of the program. In that case, all generated variable bindings are reported to the user, and the query is said to have succeeded. Operationally, Prolog's execution strategy can be thought of as a generalization of function calls in other languages, one difference being that multiple clause heads can match a given call. In that case, the system creates a choice-point, unifies the goal with the clause head of the first alternative, and continues with the goals of that first alternative. If any goal fails in the course of executing the program, all variable bindings that were made since the most recent choice-point was created are undone, and execution continues with the next alternative of that choice-point. This execution strategy is called chronological
backtrackingBacktracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c as soon as it determines that c cannot possibly be completed to a valid solution.The classic textbook example...
. For example: