Prolog

# Prolog

Overview
Prolog is a general purpose logic programming
Logic programming
Logic 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 intelligence
Artificial intelligence
Artificial 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 linguistics
Computational linguistics
Computational 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 logic
First-order logic
First-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 logic
Formal logic
Classical or traditional system of determining the validity or invalidity of a conclusion deduced from two or more statements...

, and unlike many other programming language
Programming language
A 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 declarative
Declarative programming
In 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 Colmerauer
Alain Colmerauer
Alain 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 Marseille
Marseille
Marseille , 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...

, France
France
The 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.
Discussion

Encyclopedia
Prolog is a general purpose logic programming
Logic programming
Logic 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 intelligence
Artificial intelligence
Artificial 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 linguistics
Computational linguistics
Computational 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 logic
First-order logic
First-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 logic
Formal logic
Classical or traditional system of determining the validity or invalidity of a conclusion deduced from two or more statements...

, and unlike many other programming language
Programming language
A 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 declarative
Declarative programming
In 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 Colmerauer
Alain Colmerauer
Alain 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 Marseille
Marseille
Marseille , 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...

, France
France
The 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 processing
Natural language processing
Natural 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 proving
Automated theorem proving
Automated 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 system
Expert system
In 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 system
Control system
A 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 interface
Graphical user interface
In 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 resolution
Resolution (logic)
In 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 programming
Imperative programming
In 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 type
Data type
In 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
Floating point
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 integer
Integer
The 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
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
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 Unicode
Unicode
Unicode 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

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 operator
Operator (programming)
Programming 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 conjunction
Logical conjunction
In 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 disjunction
Logical disjunction
In 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).

?- 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/output
Input/output
In 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 resolution
Resolution (logic)
In 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 resolution
SLD resolution
SLD 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 backtracking
Backtracking
Backtracking 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:

mother_child(trude, sally).

father_child(tom, sally).
father_child(tom, erica).
father_child(mike, tom).

sibling(X, Y) :- parent_child(Z, X), parent_child(Z, Y).

parent_child(X, Y) :- father_child(X, Y).
parent_child(X, Y) :- mother_child(X, Y).

This results in the following query being evaluated as true:

?- sibling(sally, erica).
Yes

This is obtained as follows: Initially, the only matching clause-head for the query `sibling(sally, erica)` is the first one, so proving the query is equivalent to proving the body of that clause with the appropriate variable bindings in place, i.e., the conjunction `(parent_child(Z,sally), parent_child(Z,erica))`. The next goal to be proved is the leftmost one of this conjunction, i.e., `parent_child(Z, sally)`. Two clause heads match this goal. The system creates a choice-point and tries the first alternative, whose body is `father_child(Z, sally)`. This goal can be proved using the fact `father_child(tom, sally)`, so the binding `Z = tom` is generated, and the next goal to be proved is the second part of the above conjunction: `parent_child(tom, erica)`. Again, this can be proved by the corresponding fact. Since all goals could be proved, the query succeeds. Since the query contained no variables, no bindings are reported to the user. A query with variables, like:

?- father_child(Father, Child).

enumerates all valid answers on backtracking.

Notice that with the code as stated above, the query `?- sibling(sally, sally).` also succeeds. One would insert additional goals to describe the relevant restrictions, if desired.

### Loops and recursion

Iterative algorithms can be implemented by means of recursive predicates.

### Negation

The built-in Prolog predicate `\+/1` provides negation as failure, which allows for non-monotonic
Non-monotonic logic
A non-monotonic logic is a formal logic whose consequence relation is not monotonic. Most studied formal logics have a monotonic consequence relation, meaning that adding a formula to a theory never produces a reduction of its set of consequences. Intuitively, monotonicity indicates that learning a...

reasoning. The goal `\+ legal(X)` in the rule

illegal(X) :- \+ legal(X).

is evaluated as follows: Prolog attempts to prove the `legal(X)`. If a proof for that goal can be found, the original goal (i.e., `\+ legal(X)`) fails. If no proof can be found, the original goal succeeds. Therefore, the `\+/1` prefix operator is called the "not provable" operator, since the query `?- \+ Goal.` succeeds if Goal is not provable. This kind of negation is sound if its argument is "ground" (i.e. contains no variables). Soundness is lost if the argument contains variables and the proof procedure is complete. In particular, the query `?- illegal(X).` can now not be used to enumerate all things that are illegal.

### Hello world

An example of a query:

?- write('Hello world!'), nl.
Hello world!
true.

?-

### Compiler optimization

Any computation can be expressed declaratively as a sequence of state transitions. As an example, an optimizing compiler with three optimization passes could be implemented as a relation between an initial program and its optimized form:

program_optimized(Prog0, Prog) :-
optimization_pass_1(Prog0, Prog1),
optimization_pass_2(Prog1, Prog2),
optimization_pass_3(Prog2, Prog).

or equivalently using DCG
Definite clause grammar
A definite clause grammar is a way of expressing grammar, either for natural or formal languages, in a logic programming language such as Prolog. DCGs are usually associated with Prolog, but similar languages such as Mercury also include DCGs...

notation:

program_optimized --> optimization_pass_1, optimization_pass_2, optimization_pass_3.

### Quicksort

The Quicksort sorting algorithm, relating a list to its sorted version:

partition([], _, [], []).
partition([X|Xs], Pivot, Smalls, Bigs) :-
( X @< Pivot ->
Smalls = [X|Rest],
partition(Xs, Pivot, Rest, Bigs)
; Bigs = [X|Rest],
partition(Xs, Pivot, Smalls, Rest)
).

quicksort([]) --> [].
quicksort([X|Xs]) -->
{ partition(Xs, X, Smaller, Bigger) },
quicksort(Smaller), [X], quicksort(Bigger).

## Design patterns

A design pattern
Design pattern (computer science)
In software engineering, a design pattern is a general reusable solution to a commonly occurring problem within a given context in software design. A design pattern is not a finished design that can be transformed directly into code. It is a description or template for how to solve a problem that...

is a general reusable solution to a commonly occurring problem in software design
Software design
Software design is a process of problem solving and planning for a software solution. After the purpose and specifications of software are determined, software developers will design or employ designers to develop a plan for a solution...

. In Prolog, design patterns go under various names: skeletons and techniques, cliches, program schemata, and logic description schemata. An alternative to design patterns is higher order programming.

## Higher-order programming

By definition, first-order logic
First-order logic
First-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...

does not allow quantification over predicates. A higher-order predicate is a predicate that takes one or more other predicates as arguments. Prolog already has some built-in higher-order predicates such as `call/1`, `findall/3`, `setof/3`, and `bagof/3`. Furthermore, since arbitrary Prolog goals can be constructed and evaluated at run-time, it is easy to write higher-order predicates like `maplist/2`, which applies an arbitrary predicate to each member of a given list, and `sublist/3`, which filters elements that satisfy a given predicate, also allowing for currying
Currying
In mathematics and computer science, currying is the technique of transforming a function that takes multiple arguments in such a way that it can be called as a chain of functions each with a single argument...

.

To convert solutions from temporal representation (answer substitutions on backtracking) to spatial representation (terms), Prolog has various all-solutions predicates that collect all answer substitutions of a given query in a list. This can be used for list comprehension. For example, perfect numbers equal the sum of their proper divisors:

perfect(N) :-
between(1, inf, N), U is N // 2,
findall(D, (between(1,U,D), N mod D =:= 0), Ds),
sumlist(Ds, N).

This can be used to enumerate perfect numbers, and also to check whether a number is perfect.

## Modules

For programming in the large
Programming in the large
In software development, programming in the large and programming in the small describe two different approaches to writing software. The terms were coined by Frank DeRemer and Hans Kron in their 1975 paper "Programming-in-the large versus programming-in-the-small" Fred Brooks identifies that the...

, Prolog provides a module system
Modular programming
Modular programming is a software design technique that increases the extent to which software is composed of separate, interchangeable components called modules by breaking down program functions into modules, each of which accomplishes one function and contains everything necessary to accomplish...

. The module system is standardised by ISO. However, not all Prolog compilers support modules and there are compatibility problems between the module systems of the major Prolog compilers. Consequently, modules written on one Prolog compiler will not necessarily work on others.

## Parsing

There is a special notation called definite clause grammar
Definite clause grammar
A definite clause grammar is a way of expressing grammar, either for natural or formal languages, in a logic programming language such as Prolog. DCGs are usually associated with Prolog, but similar languages such as Mercury also include DCGs...

s (DCGs). A rule defined via `-->/2` instead of `:-/2` is expanded by the preprocessor (`expand_term/2`, a facility analogous to macros in other languages) according to a few straightforward rewriting rules, resulting in ordinary Prolog clauses. Most notably, the rewriting equips the predicate with two additional arguments, which can be used to implicitly thread state around, analogous to monads
In functional programming, a monad is a programming structure that represents computations. Monads are a kind of abstract data type constructor that encapsulate program logic instead of data in the domain model...

in other languages. DCGs are often used to write parsers or list generators, as they also provide a convenient interface to list differences.

## Meta-interpreters and reflection

Prolog is a homoiconic language and provides many facilities for reflection
Reflection (computer science)
In computer science, reflection is the process by which a computer program can observe and modify its own structure and behavior at runtime....

. Its implicit execution strategy makes it possible to write a concise meta-circular evaluator
Meta-circular evaluator
A meta-circular evaluator is a special case of a self-interpreter in which the existing facilities of the parent interpreter are directly applied to the source code being interpreted, without any need for additional implementation...

(also called meta-interpreter) for pure Prolog code. Since Prolog programs are themselves sequences of Prolog terms (`:-/2` is an infix operator
Operator (programming)
Programming 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...

) that are easily read and inspected using built-in mechanisms (like `read/1`), it is easy to write customized interpreters that augment Prolog with domain-specific features.

## Turing completeness

Pure Prolog is based on a subset of first-order predicate logic
Predicate logic
In mathematical logic, predicate logic is the generic term for symbolic formal systems like first-order logic, second-order logic, many-sorted logic or infinitary logic. This formal system is distinguished from other systems in that its formulae contain variables which can be quantified...

, Horn clauses, which is Turing-complete
Turing completeness
In computability theory, a system of data-manipulation rules is said to be Turing complete or computationally universal if and only if it can be used to simulate any single-taped Turing machine and thus in principle any computer. A classic example is the lambda calculus...

. Turing completeness of Prolog can be shown by using it to simulate a Turing machine:

turing(Tape0, Tape) :-
perform(q0, [], Ls, Tape0, Rs),
reverse(Ls, Ls1),
append(Ls1, Rs, Tape).

perform(qf, Ls, Ls, Rs, Rs) :- !.
perform(Q0, Ls0, Ls, Rs0, Rs) :-
symbol(Rs0, Sym, RsRest),
once(rule(Q0, Sym, Q1, NewSym, Action)),
action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
perform(Q1, Ls1, Ls, Rs1, Rs).

symbol([], b, []).
symbol([Sym|Rs], Sym, Rs).

action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs).
action(stay, Ls, Ls, Rs, Rs).
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).

left([], [], Rs0, [b|Rs0]).
left([L|Ls], Ls, Rs, [L|Rs]).

A simple example Turing machine is specified by the facts:

rule(q0, 1, q0, 1, right).
rule(q0, b, qf, 1, stay).

This machine performs incrementation by one of a number in unary encoding: It loops over any number of "1" cells and appends an additional "1" at the end. Example query and result:

?- turing([1,1,1], Ts).
Ts = [1, 1, 1, 1] ;

This illustrates how any computation can be expressed declaratively as a sequence of state transitions, implemented in Prolog as a relation between successive states of interest.

### ISO Prolog

The ISO Prolog standard consists of two parts. ISO/IEC 13211-1, published in 1995, aims to standardize the existing practices of the many implementations of the core elements of Prolog. It has clarified aspects of the language that were previously ambiguous and leads to portable programs. ISO/IEC 13211-2, published in 2000, adds support for modules to the standard. The standard is maintained by the ISO/IEC JTC1/SC22
SC22
SC22, or to give it its full title ISO/IEC JTC1/SC22 Programming languages, their environments and system software interfaces, is the international standardization subcommittee for programming languages, their environments and system software interfaces...

/WG17 working group. ANSI X3J17 is the US Technical Advisory Group for the standard.

### Compilation

For efficiency, Prolog code is typically compiled to abstract machine code, often influenced by the register-based Warren Abstract Machine
Warren abstract machine
In 1983, David H. D. Warren designed an abstract machine for the execution of Prolog consisting of a memory architecture and an instruction set. This design became known as the Warren Abstract Machine and has become the de facto standard target for Prolog compilers.-Purpose:The purpose of...

(WAM) instruction set. Some implementations employ abstract interpretation
Abstract interpretation
In computer science, abstract interpretation is a theory of sound approximation of the semantics of computer programs, based on monotonic functions over ordered sets, especially lattices. It can be viewed as a partial execution of a computer program which gains information about its semantics In...

to derive type and mode information of predicates at compile time, or compile to real machine code for high performance. Devising efficient implementation methods for Prolog code is a field of active research in the logic programming community, and various other execution methods are employed in some implementations. These include clause binarization and stack-based virtual machines.

### Tail recursion

Prolog systems typically implement a well-known optimization method called tail call optimization (TCO) for deterministic predicates exhibiting tail recursion or, more generally, tail calls: A clause's stack frame is discarded before performing a call in a tail position. Therefore, deterministic tail-recursive predicates are executed with constant stack space, like loops in other languages.

### Term indexing

Finding clauses that are unifiable with a term in a query is linear in the number of clauses. Term indexing
Term indexing
In computer science, term indexing is the task of creating an index of terms and clauses in a collection.Many operations in automatic theorem provers require search in hugecollections of terms and clauses. Such operations typically fall into...

uses a data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...

that enables sublinear-time lookups. Indexing only affects program performance, it does not affect semantics.

### Tabling

Some Prolog systems, (BProlog
BProlog
B-Prolog is a high-performance implementation of the standard Prolog language with several extended features including matching clauses, action rules for event handling, finite-domain constraint solving, arrays and hash tables, declarative loops, and tabling. First released in 1994, B-Prolog is now...

, XSB
XSB
XSB is the name of a dialect of the Prolog programming language and its implementation developed at Stony Brook University in collaboration with the Katholieke Universiteit Leuven, the New University of Lisbon, Uppsala University and software vendor XSB, Inc....

and Yap), implement a memoization
Memoization
In computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs...

method called tabling, which frees the user from manually storing intermediate results.

### Implementation in hardware

During the Fifth Generation Computer Systems project, there were attempts to implement Prolog in hardware with the aim of achieving faster execution with dedicated architectures. Furthermore, Prolog has a number of properties that may allow speed-up through parallel execution. A more recent approach has been to compile restricted Prolog programs to a field programmable gate array. However, rapid progress in general-purpose hardware has consistently overtaken more specialised architectures.

## Criticism

Although Prolog is widely used in research and education, Prolog and other logic programming languages have not had a significant impact on the computer industry in general. Most applications are small by industrial standards, with few exceeding 100,000 lines of code. Programming in the large
Programming in the large
In software development, programming in the large and programming in the small describe two different approaches to writing software. The terms were coined by Frank DeRemer and Hans Kron in their 1975 paper "Programming-in-the large versus programming-in-the-small" Fred Brooks identifies that the...

is considered to be complicated because not all Prolog compilers support modules, and there are compatibility problems between the module systems of the major Prolog compilers. Portability of Prolog code across implementations has also been a problem, but developments since 2007 have meant: "the portability within the family of Edinburgh/Quintus derived Prolog implementations is good enough to allow for maintaining portable real-world applications."

Software developed in Prolog has been criticised for having a high performance penalty compared to conventional programming languages. However, advances in implementation methods have reduced the penalties to as little as 25%-50% for some applications.

## Extensions

Various implementations have been developed from Prolog to extend logic programming capabilities in numerous directions. These include types
Type system
A type system associates a type with each computed value. By examining the flow of these values, a type system attempts to ensure or prove that no type errors can occur...

, modes, constraint logic programming (CLP), object-oriented logic programming (OOLP), concurrency, linear logic
Linear logic
Linear logic is a substructural logic proposed by Jean-Yves Girard as a refinement of classical and intuitionistic logic, joining the dualities of the former with many of the constructive properties of the latter...

(LLP), functional and higher-order logic
Higher-order logic
In mathematics and logic, a higher-order logic is a form of predicate logic that is distinguished from first-order logic by additional quantifiers and a stronger semantics...

programming capabilities, plus interoperability with knowledge bases:

### Types

Prolog is an untyped language. Attempts to introduce types date back to the 1980s, and as of 2008 there are still attempts to extend Prolog with types. Type information is useful not only for type safety
Type safety
In computer science, type safety is the extent to which a programming language discourages or prevents type errors. A type error is erroneous or undesirable program behaviour caused by a discrepancy between differing data types...

but also for reasoning about Prolog programs.

### Modes

The syntax of Prolog does not specify which arguments of a predicate are inputs and which are outputs. However, this information is significant and it is recommended that it be included in the comments. Modes provide valuable information when reasoning about Prolog programs and can also be used to accelerate execution.

### Constraints

Constraint logic programming extends Prolog to include concepts from constraint satisfaction
Constraint satisfaction
In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution to a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a vector of variables that satisfies all constraints.The techniques used in...

. A constraint logic program allows constraints in the body of clauses, such as: `A(X,Y) :- X+Y>0.` It is suited to large-scale combinatorial optimisation problems. and is thus useful for applications in industrial settings, such as automated time-tabling and production scheduling. Most Prolog systems ship with at least one constraint solver for finite domains, and often also with solvers for other domains like rational numbers.

### Higher-order programming

HiLog and λProlog extend Prolog with higher-order programming features. ISO Prolog now supports the built-in predicates `call/2`, `call/3`, ... which facilitate higher-order programming and lambda abstractions.

maplist(_Cont, [], []).
maplist(Cont, [X1|X1s], [X2|X2s]) :-
call(Cont, X1, X2),
maplist(Cont, X1s, X2s).

### Object-orientation

Logtalk
Logtalk
Logtalk is an object-oriented logic programming language that extends the Prolog language with a feature set suitable for programming in the large. It provides support for encapsulation and data hiding, separation of concerns and enhanced code reuse...

is an object-oriented logic programming language that can use most Prolog implementations as a back-end compiler. As a multi-paradigm language, it includes support for both prototypes and classes.

Oblog
Oblog
Oblog is a small, portable, Object-oriented extension to Prolog by Margaret McDougall of EdCAAD, University of Edinburgh....

is a small, portable, object-oriented extension to Prolog by Margaret McDougall of EdCAAD, University of Edinburgh.

### Graphics

Prolog systems that provide a graphics library
Graphics library
A graphics library is a program library designed to aid in rendering computer graphics to a monitor. This typically involves providing optimized versions of functions that handle common rendering tasks. This can be done purely in software and running on the CPU, common in embedded systems, or being...

are SWI-prolog, Visual-prolog and B-Prolog.

### Concurrency

Prolog-MPI is an open-source SWI-Prolog
SWI-Prolog
SWI-Prolog is an open source implementation of the programming language Prolog, commonly used for teaching and semantic web applications.It has a rich set of features, libraries forconstraint logic programming,multithreading,unit testing,GUI,...

extension for distributed computing over the Message Passing Interface
Message Passing Interface
Message Passing Interface is a standardized and portable message-passing system designed by a group of researchers from academia and industry to function on a wide variety of parallel computers...

. Also there are various concurrent Prolog programming languages.

### Web programming

Some Prolog implementations, notably SWI-Prolog, support server-side
Server-side
Server-side refers to operations that are performed by the server in a client–server relationship in computer networking.Typically, a server is a software program, such as a web server, that runs on a remote server, reachable from a user's local computer or workstation...

web programming with support for web protocols, HTML
HTML
HyperText Markup Language is the predominant markup language for web pages. HTML elements are the basic building-blocks of webpages....

and XML
XML
Extensible Markup Language is a set of rules for encoding documents in machine-readable form. It is defined in the XML 1.0 Specification produced by the W3C, and several other related specifications, all gratis open standards....

. There are also extensions to support semantic web
Semantic Web
The Semantic Web is a collaborative movement led by the World Wide Web Consortium that promotes common formats for data on the World Wide Web. By encouraging the inclusion of semantic content in web pages, the Semantic Web aims at converting the current web of unstructured documents into a "web of...

formats such as RDF
Resource Description Framework
The Resource Description Framework is a family of World Wide Web Consortium specifications originally designed as a metadata data model...

and OWL
Web Ontology Language
The Web Ontology Language is a family of knowledge representation languages for authoring ontologies.The languages are characterised by formal semantics and RDF/XML-based serializations for the Semantic Web...

. Prolog has also been suggested as a client-side
Client-side
Client-side refers to operations that are performed by the client in a client–server relationship in a computer network.Typically, a client is a computer application, such as a web browser, that runs on a user's local computer or workstation and connects to a server as necessary...

language.

Cedar is a free and basic Prolog interpreter. From version 4 and above Cedar has a FCA (Flash Cedar App) support. This provides a new platform to programing in Prolog through ActionScript
ActionScript
ActionScript is an object-oriented language originally developed by Macromedia Inc. . It is a dialect of ECMAScript , and is used primarily for the development of websites and software targeting the Adobe Flash Player platform, used on Web pages in the form of...

.

### Other

• F-logic
F-logic
F-logic is a knowledge representation- and ontology language. F-logic combines the advantages of conceptual modeling with object-oriented, frame-based languages and offers a declarative, compact and simple syntax, as well as the well-defined semantics of a logic-based language.Features include,...

extends Prolog with frames/objects for knowledge representation
Knowledge representation
Knowledge representation is an area of artificial intelligence research aimed at representing knowledge in symbols to facilitate inferencing from those knowledge elements, creating new elements of knowledge...

.
• OW Prolog has been created in order to answer Prolog's lack of graphics and interface.

## Interfaces to other languages

Frameworks exist which can bridge between Prolog and other languages:
• The Logic Server API allows both the extension and embedding of Prolog in C, C++, Java, VB, Delphi, .NET and any language/environment which can call a .dll or .so. It is implemented for Amzi! Prolog Amzi! Prolog + Logic Server but the API specification can be made available for any implementation.
• JPL is a bi-directional Java Prolog bridge which ships with SWI-Prolog by default, allowing Java and Prolog to call each other respectively. It is known to have good concurrency support and is under active development.
• InterProlog, a programming library bridge between Java and Prolog, implementing bi-directional predicate/method calling between both languages. Java objects can be mapped into Prolog terms and vice-versa. Allows the development of GUIs
Graphical user interface
In 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...

and other functionality in Java while leaving logic processing in the Prolog layer. Supports XSB
XSB
XSB is the name of a dialect of the Prolog programming language and its implementation developed at Stony Brook University in collaboration with the Katholieke Universiteit Leuven, the New University of Lisbon, Uppsala University and software vendor XSB, Inc....

, SWI-Prolog
SWI-Prolog
SWI-Prolog is an open source implementation of the programming language Prolog, commonly used for teaching and semantic web applications.It has a rich set of features, libraries forconstraint logic programming,multithreading,unit testing,GUI,...

and YAP.
• Prova
Prova
Prova is an open source programming language that combines Prolog with Java.- Description :Prova is a rule-based scripting system that is used for middleware. The language combines imperative and declarative programming by using a prolog syntax that allows calls to Java functions...

provides native syntax integration with Java, agent messaging and reaction rules. Prova positions itself as a rule-based scripting (RBS) system for middleware. The language breaks new ground in combining imperative
Imperative programming
In computer science, imperative programming is a programming paradigm that describes computation in terms of statements that change a program state...

and declarative programming
Declarative programming
In 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...

.
• PROL An embeddable Prolog engine for Java. It includes a small IDE and a few libraries.
• GNU Prolog for Java is an implementation of ISO Prolog as a Java library (gnu.prolog)
• Ciao
Ciao (programming language)
Ciao is a general-purpose programming language which supports logic, constraint, functional, higher-order, and object-oriented programming styles. Its main design objectives are high expressive power, extensibility, safety, reliability, and efficient execution....

provides interfaces to C, C++, Java, and relational databases.

## History

The name Prolog was chosen by Philippe Roussel as an abbreviation for (French
French language
French is a Romance language spoken as a first language in France, the Romandy region in Switzerland, Wallonia and Brussels in Belgium, Monaco, the regions of Quebec and Acadia in Canada, and by various communities elsewhere. Second-language speakers of French are distributed throughout many parts...

for programming in logic
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...

). It was created around 1972 by Alain Colmerauer
Alain Colmerauer
Alain 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...

with Philippe Roussel, based on Robert Kowalski
Robert Kowalski
Robert "Bob" Anthony Kowalski is a British logician and computer scientist, who has spent most of his career in the United Kingdom....

's procedural interpretation of Horn clause
Horn clause
In mathematical logic, a Horn clause is a clause with at most one positive literal. They are named after the logician Alfred Horn, who first pointed out the significance of such clauses in 1951...

s. It was motivated in part by the desire to reconcile the use of logic as a declarative knowledge representation language with the procedural representation of knowledge that was popular in North America in the late 1960s and early 1970s. According to Robert Kowalski
Robert Kowalski
Robert "Bob" Anthony Kowalski is a British logician and computer scientist, who has spent most of his career in the United Kingdom....

, the first Prolog system was developed in 1972 by Alain Colmerauer and Phillipe Roussel. The first implementations of Prolog were interpreters, however, David H. D. Warren
David H. D. Warren
David H. D. Warren is a computer scientist .In the 1970s and 1980s he worked primarily on logic programming and in particular the programming language Prolog. Warren wrote the first compiler for Prolog...

created the Warren Abstract Machine
Warren abstract machine
In 1983, David H. D. Warren designed an abstract machine for the execution of Prolog consisting of a memory architecture and an instruction set. This design became known as the Warren Abstract Machine and has become the de facto standard target for Prolog compilers.-Purpose:The purpose of...

, an early and influential Prolog compiler which came to define the "Edinburgh Prolog" dialect which served as the basis for the syntax of most modern implementations.

Much of the modern development of Prolog came from the impetus of the Fifth Generation Computer Systems project (FGCS), which developed a variant of Prolog named Kernel Language
KL1
KL1, or Kernel Language 1 is an experimental AND-parallel version of KL0 developed for the ICOT Fifth Generation Computer project. KL1 is an implementation of Flat GHC , making it a parallelised Prolog variant.-External links:* , home of the KLIC KL1 to C compiler - last update circa 1999-Further...

for its first operating system
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...

.

Pure Prolog was originally restricted to the use of a resolution
Resolution (logic)
In 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...

theorem prover with Horn clause
Horn clause
In mathematical logic, a Horn clause is a clause with at most one positive literal. They are named after the logician Alfred Horn, who first pointed out the significance of such clauses in 1951...

s of the form:

H :- B1, ..., Bn.

The application of the theorem-prover treats such clauses as procedures:

to show/solve H, show/solve B1 and ... and Bn.

Pure Prolog was soon extended, however, to include negation as failure, in which negative conditions of the form not(Bi) are shown by trying and failing to solve the corresponding positive conditions Bi.

Subsequent extensions of Prolog by the original team introduced constraint logic programming abilities into the implementations.

• Comparison of Prolog implementations
Comparison of Prolog implementations
The following Comparison of Prolog implementations provides a reference for the relative feature sets and performance of different implementations of the Prolog computer programming language.-Main features:-Operating system and Web-related features:...

• Logico-linguistic modeling
Logico-linguistic modeling
Logico-linguistic modeling is a method for building knowledge-based systems with a learning capability using Conceptual Models from Soft systems methodology, modal predicate logic and the Prolog artificial intelligence language.- Overview:...

. A method for building knowledge-based system that uses Prolog.

### Related languages

• The Gödel language is a strongly typed implementation of concurrent constraint logic programming
Concurrent constraint logic programming
Concurrent constraint logic programming is a version of constraint logic programming aimed primarily at programming concurrent processes rather than solving constraint satisfaction problems...

. It is built on SICStus Prolog.
• Visual Prolog
Visual Prolog
Visual Prolog, also formerly known as PDC Prolog and Turbo Prolog, is a strongly typed object-oriented extension of Prolog. As Turbo Prolog it was marketed by Borland, but it is now developed and marketed by the Danish firm Prolog Development Center that originally developed it...

, formerly known as PDC Prolog and Turbo Prolog, is a strongly typed
Data type
In 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...

object-oriented
Object-oriented programming
Object-oriented programming is a programming paradigm using "objects" – data structures consisting of data fields and methods together with their interactions – to design applications and computer programs. Programming techniques may include features such as data abstraction,...

dialect of Prolog, which is very different from standard Prolog. As Turbo Prolog it was marketed by Borland, but it is now developed and marketed by the Danish firm PDC (Prolog Development Center) that originally produced it.
• Datalog
Datalog
Datalog is a query and rule language for deductive databases that syntactically is a subset of Prolog. Its origins date back to the beginning of logic programming, but it became prominent as a separate area around 1977 when Hervé Gallaire and Jack Minker organized a workshop on logic and databases...

is a subset of Prolog. It is limited to relationships that may be stratified and does not allow compound terms. In contrast to Prolog, Datalog is not Turing-complete.
• CSC
Computer Sciences Corporation
Computer Sciences Corporation is an American information technology and business services company headquartered in Falls Church, Virginia, USA...

GraphTalk is a proprietary implementation of Warren's Abstract Machine, with additional object-oriented properties.
• In some ways Prolog is a subset of Planner. The ideas in Planner were later further developed in the Scientific Community Metaphor
Scientific community metaphor
In computer science, the Scientific Community Metaphor is a metaphor used to aid understanding scientific communities. The first publications on the Scientific Community Metaphor in 1981 and 1982 involved the development of a programming language named Ether that invoked procedural plans to...

.
• AgentSpeak
AgentSpeak
AgentSpeak is an agent-oriented programming language. It is based on logic programming and the BDI architecture for autonomous agents...

is a variant of Prolog for programming agent behavior in multi-agent system
Multi-agent system
A multi-agent system is a system composed of multiple interacting intelligent agents. Multi-agent systems can be used to solve problems that are difficult or impossible for an individual agent or a monolithic system to solve...

s.

• Patrick Blackburn, Johan Bos, Kristina Striegnitz, Learn Prolog Now!, 2006, ISBN 1-904987-17-6.
• Ivan Bratko
Ivan Bratko
Dr. Ivan Bratko is a Slovene computer scientist.Bratko received his Ph.D. in 1978 from the University of Ljubljana. He is a D. Sc. Professor of Computer and Information Science at the Faculty of Computer and Information Science at the University of Ljubljana...

, PROLOG Programming for Artificial Intelligence, 2000, ISBN 0-201-40375-7.
• William F. Clocksin, Christopher S. Mellish: Programming in Prolog: Using the ISO Standard. Springer, 5th ed., 2003, ISBN 978-3540006787. (This edition is updated for ISO Prolog. Previous editions described Edinburgh Prolog.)
• William F. Clocksin: Clause and Effect. Prolog Programming for the Working Programmer. Springer, 2003, ISBN 978-3540629719.
• Alain Colmerauer and Philippe Roussel, The birth of Prolog, in The second ACM SIGPLAN conference on History of programming languages, p. 37-52, 1992.
• Michael A. Covington, Donald Nute, Andre Vellino, Prolog Programming in Depth, 1996, ISBN 0-13-138645-X.
• Michael A. Covington, Natural Language Processing for Prolog Programmers, 1994, ISBN 0-13-62921
• Robert Smith, John Gibson, Aaron Sloman
Aaron Sloman
Aaron Sloman is a philosopher and researcher on artificial intelligence and cognitive science. He is the author of several papers on philosophy, epistemology and artificial intelligence...

: 'POPLOG's two-level virtual machine support for interactive languages', in Research Directions in Cognitive Science Volume 5: Artificial Intelligence, Eds D. Sleeman and N. Bernsen, Lawrence Erlbaum Associates, pp 203–231, 1992.
• Leon Sterling
Leon Sterling
Prof. Leon Sterling is dean of the Faculty of Information and Communication Technologies at Swinburne University of Technology in Melbourne. Until the start of 2010, he was a professor at the University of Melbourne's department of Computer Science and Software Engineering.He is co-author along...

and Ehud Shapiro
Ehud Shapiro
Ehud Shapiro is an Israeli computer scientist at the Weizmann Institute of Science. He received his Ph.D from Yale for his dissertation entitled "Algorithmic Program Debugging" which was an ACM distinguished dissertation for 1982. He has been an exponent of the Prolog computer language and logic...

, The Art of Prolog: Advanced Programming Techniques, 1994, ISBN 0-262-19338-8.
• Robert Kowalski, The Early Years of Logic Programming, CACM January 1988.
• ISO/IEC 13211: Information technology — Programming languages — Prolog. International Organization for Standardization
International Organization for Standardization
The International Organization for Standardization , widely known as ISO, is an international standard-setting body composed of representatives from various national standards organizations. Founded on February 23, 1947, the organization promulgates worldwide proprietary, industrial and commercial...

, Geneva.
• Richard O'Keefe
Richard O'Keefe
Dr Richard A. O'Keefe is a computer scientist, currently working in Department of Computer Science at the University of Otago in Dunedin, New Zealand....

, The Craft of Prolog, ISBN 0-262-15039-5.
• David H D Warren, Luis M. Pereira and Fernando Pereira, Prolog - the language and its implementation compared with Lisp. ACM SIGART Bulletin archive, Issue 64. Proceedings of the 1977 symposium on Artificial intelligence and programming languages, pp 109 – 115.