HOME

TheInfoList



OR:

Prolog is a
logic programming Logic programming is a programming paradigm which is largely based on formal logic. Any program written in a logic programming language is a set of sentences in logical form, expressing facts and rules about some problem domain. Major logic pro ...
language associated with
artificial intelligence Artificial intelligence (AI) is intelligence—perceiving, synthesizing, and inferring information—demonstrated by machines, as opposed to intelligence displayed by animals and humans. Example tasks in which this is done include speech re ...
and computational linguistics. Prolog has its roots in
first-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
, a
formal logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premis ...
, and unlike many other
programming language A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language. The description of a programming ...
s, Prolog is intended primarily as a declarative programming language: the program logic is expressed in terms of relations, represented as facts and
rules Rule or ruling may refer to: Education * Royal University of Law and Economics (RULE), a university in Cambodia Human activity * The exercise of political or personal control by someone with authority or power * Business rule, a rule pert ...
. A
computation Computation is any type of arithmetic or non-arithmetic calculation that follows a well-defined model (e.g., an algorithm). Mechanical or electronic devices (or, historically, people) that perform computations are known as ''computers''. An es ...
is initiated by running a ''query'' over these relations. The language was developed and implemented in Marseille, France, in 1972 by
Alain Colmerauer Alain Colmerauer (24 January 1941 – 12 May 2017) was a French computer scientist. He was a professor at Aix-Marseille University, and the creator of the logic programming language Prolog. Early life Alain Colmerauer was born on 24 January 194 ...
with Philippe Roussel, based on
Robert Kowalski Robert Anthony Kowalski (born 15 May 1941) is an American-British logician and computer scientist, whose research is concerned with developing both human-oriented models of computing and computational models of human thinking. He has spent mo ...
's procedural interpretation of
Horn clause In mathematical logic and logic programming, a Horn clause is a logical formula of a particular rule-like form which gives it useful properties for use in logic programming, formal specification, and model theory. Horn clauses are named for the log ...
s at
University of Edinburgh The University of Edinburgh ( sco, University o Edinburgh, gd, Oilthigh Dhùn Èideann; abbreviated as ''Edin.'' in post-nominals) is a public research university based in Edinburgh, Scotland. Granted a royal charter by King James VI in 15 ...
. Prolog was one of the first logic programming languages and remains the most popular such language today, with several free and commercial implementations available. The language has been used for
theorem proving Automated theorem proving (also known as ATP or automated deduction) is a subfield of automated reasoning and mathematical logic dealing with proving mathematical theorems by computer programs. Automated reasoning over mathematical proof was a maj ...
, expert systems,
term rewriting In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewrite engines, or red ...
,
type system In computer programming, a type system is a logical system comprising a set of rules that assigns a property called a type to every "term" (a word, phrase, or other set of symbols). Usually the terms are various constructs of a computer progr ...
s, and
automated planning Automation describes a wide range of technologies that reduce human intervention in processes, namely by predetermining decision criteria, subprocess relationships, and related actions, as well as embodying those predeterminations in machines ...
, as well as its original intended field of use,
natural language processing Natural language processing (NLP) is an interdisciplinary subfield of linguistics, computer science, and artificial intelligence concerned with the interactions between computers and human language, in particular how to program computers to pro ...
. See also
Watson (computer) IBM Watson is a question answering, question-answering computer system capable of answering questions posed in natural language, developed in IBM's DeepQA project by a research team led by principal investigator David Ferrucci. Watson was named a ...
.
Modern Prolog environments support the creation of
graphical user interface The GUI ( "UI" by itself is still usually pronounced . or ), graphical user interface, is a form of user interface that allows users to interact with electronic devices through graphical icons and audio indicator such as primary notation, inste ...
s, as well as administrative and networked applications. Prolog is well-suited for specific tasks that benefit from rule-based logical queries such as searching
database In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases sp ...
s,
voice control A voice-user interface (VUI) makes spoken human interaction with computers possible, using speech recognition to understand spoken commands and answer questions, and typically text to speech to play a reply. A voice command device is a device con ...
systems, and filling templates.


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(s) may refer to: Common meanings * Resolution (debate), the statement which is debated in policy debate * Resolution (law), a written motion adopted by a deliberative body * New Year's resolution, a commitment that an individual mak ...
refutation In argumentation, an objection is a reason arguing against a premise, argument, or conclusion. Definitions of objection vary in whether an objection is always an argument (or counterargument) or may include other moves such as questioning. An ...
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 In mathematics and computer science, computer algebra, also called symbolic computation or algebraic computation, is a scientific area that refers to the study and development of algorithms and software for manipulating mathematical expressions ...
, and language parsing applications. Because Prolog allows impure
predicates Predicate or predication may refer to: * Predicate (grammar), in linguistics * Predication (philosophy) * several closely related uses in mathematics and formal logic: **Predicate (mathematical logic) **Propositional function **Finitary relation, ...
, checking the
truth value In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values (''true'' or '' false''). Computing In some progr ...
of certain special predicates may have some deliberate
side effect In medicine, a side effect is an effect, whether therapeutic or adverse, that is secondary to the one intended; although the term is predominantly employed to describe adverse effects, it can also apply to beneficial, but unintended, consequence ...
, such as printing a value to the screen. Because of this, the programmer is permitted to use some amount of conventional
imperative programming In computer science, imperative programming is a programming paradigm of software that uses statements that change a program's state. In much the same way that the imperative mood in natural languages expresses commands, an imperative program c ...
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 In computer science and computer programming, a data type (or simply type) is a set of possible values and a set of allowed operations on it. A data type tells the compiler or interpreter how the programmer intends to use the data. Most progra ...
is the ''term''. Terms are either ''
atom Every atom is composed of a nucleus and one or more electrons bound to the nucleus. The nucleus is made of one or more protons and a number of neutrons. Only the most common variety of hydrogen has no neutrons. Every solid, liquid, gas, and ...
s'', ''numbers'', ''variables'' or ''compound terms''. * An atom is a general-purpose name with no inherent meaning. Examples of atoms include x, red, 'Taco', and 'some atom'. * Numbers can be floats or
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s. ISO standard compatible Prolog systems can check the Prolog flag "bounded". Most of the major Prolog systems support arbitrary length integer numbers. * 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 () is the number of arguments or operands taken by a function, operation or relation in logic, mathematics, and computer science. In mathematics, arity may also be named ''rank'', but this word can have many other meanings in mathematics. In ...
. An atom can be regarded as a compound term with
arity Arity () is the number of arguments or operands taken by a function, operation or relation in logic, mathematics, and computer science. In mathematics, arity may also be named ''rank'', but this word can have many other meanings in mathematics. In ...
zero. An example of a compound term is person_friends(zelda, om,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, by []. For example, [1,2,3] or [red,green,blue]. * ''Strings'': A sequence of characters surrounded by quotes is equivalent to either a list of (numeric) character codes, a list of characters (atoms of length 1), or an atom depending on the value of the Prolog flag double_quotes. For example, "to be, or not to be".ISO/IEC 13211-1:1995 Prolog, 6.3.7 Terms - double quoted list notation.
International Organization for Standardization The International Organization for Standardization (ISO ) is an international standard development organization composed of representatives from the national standards organizations of member countries. Membership requirements are given in Ar ...
, Geneva.
ISO Prolog provides the atom/1, number/1, integer/1, and float/1 predicates for
type-checking In computer programming, a type system is a logical system comprising a set of rules that assigns a property called a type to every "term" (a word, phrase, or other set of symbols). Usually the terms are various constructs of a computer progra ...
.


Rules and facts

Prolog programs describe relations, defined by means of clauses. Pure Prolog is restricted to
Horn clauses In mathematical logic and logic programming, a Horn clause is a logical formula of a particular rule-like form which gives it useful properties for use in logic programming, formal specification, and model theory. Horn clauses are named for the log ...
. 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
logical operator In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary ...
,/2 (meaning an arity 2 operator with name ,) denotes
conjunction Conjunction may refer to: * Conjunction (grammar), a part of speech * Logical conjunction, a mathematical operator ** Conjunction introduction, a rule of inference of propositional logic * Conjunction (astronomy), in which two astronomical bodies ...
of goals, and ;/2 denotes
disjunction In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor S ...
. 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/output In computing, input/output (I/O, or informally io or IO) is the communication between an information processing system, such as a computer, and the outside world, possibly a human or another information processing system. Inputs are the signals ...
, 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.


Execution

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(s) may refer to: Common meanings * Resolution (debate), the statement which is debated in policy debate * Resolution (law), a written motion adopted by a deliberative body * New Year's resolution, a commitment that an individual mak ...
refutation of the negated query. The resolution method used by Prolog is called
SLD resolution SLD resolution (''Selective Linear Definite'' clause 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 Give ...
. 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 is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it d ...
. 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 Negation as failure (NAF, for short) is a non-monotonic inference rule in logic programming, used to derive \mathrm~p (i.e. that ~p is assumed not to hold) from failure to derive ~p. Note that \mathrm ~p can be different from the statement \neg p ...
, which allows for non-monotonic reasoning. The goal \+ illegal(X) in the rule legal(X) :- \+ illegal(X). is evaluated as follows: Prolog attempts to prove illegal(X). If a proof for that goal can be found, the original goal (i.e., \+ illegal(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 In physics, sound is a vibration that propagates as an acoustic wave, through a transmission medium such as a gas, liquid or solid. In human physiology and psychology, sound is the ''reception'' of such waves and their ''perception'' by the ...
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 ?- legal(X). now cannot be used to enumerate all things that are legal.


Programming in Prolog

In Prolog, loading code is referred to as ''consulting''. Prolog can be used interactively by entering queries at the Prolog prompt ?-. If there is no solution, Prolog writes no. If a solution exists then it is printed. If there are multiple solutions to the query, then these can be requested by entering a semi-colon ;. There are guidelines on good programming practice to improve code efficiency, readability and maintainability. Here follow some example programs written in Prolog.


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 In computing, an optimizing compiler is a compiler that tries to minimize or maximize some attributes of an executable computer program. Common requirements are to minimize a program's execution time, memory footprint, storage size, and power cons ...
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 notation: program_optimized --> optimization_pass_1, optimization_pass_2, optimization_pass_3.


Quicksort

The
quicksort Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. Overall, it is slightly faster than ...
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]) --> , quicksort(Smaller), [X], quicksort(Bigger).


Design patterns of Prolog

A design pattern (computer science), design pattern is a general reusable solution to a commonly occurring problem in software design. Some design patterns in Prolog are skeletons, techniques, cliches, program schemata, logic description schemata, and higher order programming.


Higher-order programming

A higher-order predicate is a predicate that takes one or more other predicates as arguments. Although support for higher-order programming takes Prolog outside the domain of first-order logic, which does not allow quantification over predicates, ISO Prolog now has some built-in higher-order predicates such as call/1, call/2, call/3, 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. 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 A list comprehension is a syntactic construct available in some programming languages for creating a list based on existing lists. It follows the form of the mathematical ''set-builder notation'' (''set comprehension'') as distinct from the use of ...
. For example,
perfect numbers In number theory, a perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. For instance, 6 has divisors 1, 2 and 3 (excluding itself), and 1 + 2 + 3 = 6, so 6 is a perfect number. T ...
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. As another example, the predicate maplist applies a predicate P to all corresponding positions in a pair of lists: maplist(_, [], []). maplist(P, [X, Xs], [Y, Ys]) :- call(P, X, Y), maplist(P, Xs, Ys). When P is a predicate that for all X, P(X,Y) unifies Y with a single unique value, maplist(P, Xs, Ys) is equivalent to applying the
map A map is a symbolic depiction emphasizing relationships between elements of some space, such as objects, regions, or themes. Many maps are static, fixed to paper or some other durable medium, while others are dynamic or interactive. Although ...
function in
functional programming In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that ...
as Ys = map(Function, Xs). Higher-order programming style in Prolog was pioneered in
HiLog HiLog is a programming logic with higher-order syntax, which allows arbitrary terms to appear in predicate and function positions. However, the model theory of HiLog is first-order. Although syntactically HiLog strictly extends first order logic, Hi ...
and λProlog.


Modules

For
programming in the large In software engineering, programming in the large and programming in the small refer to two different aspects of writing software, namely, designing a larger system as a composition of smaller parts, and creating those smaller parts by writing li ...
, Prolog provides a
module system Modular programming is a software design technique that emphasizes separating the functionality of a program into independent, interchangeable modules, such that each contains everything necessary to execute only one aspect of the desired function ...
. 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 A definite clause grammar (DCG) is a way of expressing grammar, either for natural or formal languages, in a logic programming language such as Prolog. It is closely related to the concept of attribute grammars / affix grammars from which Prolog ...
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 other languages. DCGs are often used to write parsers or list generators, as they also provide a convenient interface to difference lists.


Meta-interpreters and reflection

Prolog is a
homoiconic In computer programming, homoiconicity (from the Greek words ''homo-'' meaning "the same" and ''icon'' meaning "representation") is a property of some programming languages. A language is homoiconic if a program written in it can be manipulated as ...
language and provides many facilities for
reflection Reflection or reflexion may refer to: Science and technology * Reflection (physics), a common wave phenomenon ** Specular reflection, reflection from a smooth surface *** Mirror image, a reflection in a mirror or in water ** Signal reflection, in ...
. Its implicit execution strategy makes it possible to write a concise
meta-circular evaluator In computing, a meta-circular evaluator (MCE) or meta-circular interpreter (MCI) is an interpreter which defines each feature of the interpreted language using a similar facility of the interpreter's host language. For example, interpreting a lambd ...
(also called ''meta-interpreter'') for pure Prolog code: solve(true). solve((Subgoal1,Subgoal2)) :- solve(Subgoal1), solve(Subgoal2). solve(Head) :- clause(Head, Body), solve(Body). where true represents an empty conjunction, and clause(Head, Body) unifies with clauses in the database of the form Head :- Body. Since Prolog programs are themselves sequences of Prolog terms (:-/2 is an infix operator) that are easily read and inspected using built-in mechanisms (like read/1), it is possible to write customized interpreters that augment Prolog with domain-specific features. For example, Sterling and Shapiro present a meta-interpreter that performs reasoning with uncertainty, reproduced here with slight modifications: solve(true, 1) :- !. solve((Subgoal1,Subgoal2), Certainty) :- !, solve(Subgoal1, Certainty1), solve(Subgoal2, Certainty2), Certainty is min(Certainty1, Certainty2). solve(Goal, 1) :- builtin(Goal), !, Goal. solve(Head, Certainty) :- clause_cf(Head, Body, Certainty1), solve(Body, Certainty2), Certainty is Certainty1 * Certainty2. This interpreter uses a table of built-in Prolog predicates of the form builtin(A is B). builtin(read(X)). % etc. and clauses represented as clause_cf(Head, Body, Certainty). Given those, it can be called as solve(Goal, Certainty) to execute Goal and obtain a measure of certainty about the result.


Turing completeness

Pure Prolog is based on a subset of first-order
predicate logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
,
Horn clauses In mathematical logic and logic programming, a Horn clause is a logical formula of a particular rule-like form which gives it useful properties for use in logic programming, formal specification, and model theory. Horn clauses are named for the log ...
, which is
Turing-complete In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally universal if it can be used to simulate any ...
. 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, 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( Ls Ls, Rs, 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 Ts). Ts = , 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.


Implementation


ISO Prolog

The
ISO ISO is the most common abbreviation for the International Organization for Standardization. ISO or Iso may also refer to: Business and finance * Iso (supermarket), a chain of Danish supermarkets incorporated into the SuperBest chain in 2007 * Iso ...
Prolog standard consists of two parts. ISO/IEC 13211-1,ISO/IEC 13211: Information technology — Programming languages — Prolog.
International Organization for Standardization The International Organization for Standardization (ISO ) is an international standard development organization composed of representatives from the national standards organizations of member countries. Membership requirements are given in Ar ...
, Geneva.
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. There are three corrigenda: Cor.1:2007, Cor.2:2012, and Cor.3:2017. ISO/IEC 13211-2, published in 2000, adds support for modules to the standard. The standard is maintained by the ISO/IEC JTC1/
SC22 ISO/IEC JTC 1/SC 22 Programming languages, their environments and system software interfaces is a standardization subcommittee of the Joint Technical Committee ISO/IEC JTC 1 of the International Organization for Standardization (ISO) and the Inte ...
/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 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 (WAM) and has become the ''de facto'' standard ...
(WAM) instruction set. Some implementations employ abstract interpretation 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 In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recur ...
(TCO) for deterministic predicates exhibiting
tail recursion In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recur ...
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 In computer science, a term index is a data structure to facilitate fast lookup of terms and clauses in a logic program, deductive database, or automated theorem prover. Overview Many operations in automatic theorem provers require search in hu ...
uses a
data structure In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...
that enables sub-linear-time lookups. Indexing only affects program performance, it does not affect semantics. Most Prologs only use indexing on the first term, as indexing on all terms is expensive, but techniques based on ''field-encoded words'' or '' superimposed codewords'' provide fast indexing across the full query and head.


Hashing

Some Prolog systems, such as WIN-PROLOG and SWI-Prolog, now implement hashing to help handle large datasets more efficiently. This tends to yield very large performance gains when working with large corpora such as
WordNet WordNet is a lexical database of semantic relations between words in more than 200 languages. WordNet links words into semantic relations including synonyms, hyponyms, and meronyms. The synonyms are grouped into '' synsets'' with short definition ...
.


Tabling

Some Prolog systems, ( B-Prolog,
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 ve ...
,
SWI-Prolog SWI-Prolog is a free implementation of the programming language Prolog, commonly used for teaching and semantic web applications. It has a rich set of features, libraries for constraint logic programming, multithreading, unit testing, GUI, inte ...
,
YAP Yap ( yap, Waqaab) traditionally refers to an island group located in the Caroline Islands of the western Pacific Ocean, a part of Yap State. The name "Yap" in recent years has come to also refer to the state within the Federated States of Micr ...
, and Ciao), implement a memoization method called ''tabling'', which frees the user from manually storing intermediate results. Tabling is a
space–time tradeoff A space–time trade-off or time–memory trade-off in computer science is a case where an algorithm or program trades increased space usage with decreased time. Here, ''space'' refers to the data storage consumed in performing a given task (RA ...
; execution time can be reduced by using more memory to store intermediate results:
Subgoals encountered in a query evaluation are maintained in a table, along with answers to these subgoals. If a subgoal is re-encountered, the evaluation reuses information from the table rather than re-performing resolution against program clauses.
Tabling can be extended in various directions. It can support recursive predicates through SLG-resolution or linear tabling. In a multi-threaded Prolog system tabling results could be kept private to a thread or shared among all threads. And in incremental tabling, tabling might react to changes.


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 A field-programmable gate array (FPGA) is an integrated circuit designed to be configured by a customer or a designer after manufacturinghence the term '' field-programmable''. The FPGA configuration is generally specified using a hardware d ...
. However, rapid progress in general-purpose hardware has consistently overtaken more specialised architectures.
Sega is a Japanese multinational corporation, multinational video game and entertainment company headquartered in Shinagawa, Tokyo. Its international branches, Sega of America and Sega Europe, are headquartered in Irvine, California and London, r ...
implemented Prolog for use with the Sega AI Computer, released for the Japanese market in 1986. Prolog was used for reading
natural language In neuropsychology, linguistics, and philosophy of language, a natural language or ordinary language is any language that has evolved naturally in humans through use and repetition without conscious planning or premeditation. Natural languages ...
inputs, in the
Japanese language is spoken natively by about 128 million people, primarily by Japanese people and primarily in Japan, the only country where it is the national language. Japanese belongs to the Japonic or Japanese- Ryukyuan language family. There have been ma ...
, via a touch pad.


Limitations

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.Logic programming for the real world. Zoltan Somogyi, Fergus Henderson, Thomas Conway, Richard O'Keefe. Proceedings of the ILPS'95 Postconference Workshop on Visions for the Future of Logic Programming. Most applications are small by industrial standards, with few exceeding 100,000 lines of code.
Programming in the large In software engineering, programming in the large and programming in the small refer to two different aspects of writing software, namely, designing a larger system as a composition of smaller parts, and creating those smaller parts by writing li ...
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. In particular, Prolog's non-deterministic evaluation strategy can be problematic when programming deterministic computations, or when even using "don't care non-determinism" (where a single choice is made instead of backtracking over all possibilities). Cuts and other language constructs may have to be used to achieve desirable performance, destroying one of Prolog's main attractions, the ability to run programs "backwards and forwards". Prolog is not purely declarative: because of constructs like the cut operator, a procedural reading of a Prolog program is needed to understand it. The order of clauses in a Prolog program is significant, as the execution strategy of the language depends on it. Other logic programming languages, such as
Datalog Datalog is a declarative logic programming language. While it is syntactically a subset of Prolog, Datalog generally uses a bottom-up rather than top-down evaluation model. This difference yields significantly different behavior and properties ...
, are truly declarative but restrict the language. As a result, many practical Prolog programs are written to conform to Prolog's depth-first search order, rather than as purely declarative logic programs.


Extensions

Various implementations have been developed from Prolog to extend logic programming capabilities in numerous directions. These include
types Type may refer to: Science and technology Computing * Typing, producing text via a keyboard, typewriter, etc. * Data type In computer science and computer programming, a data type (or simply type) is a set of possible values and a set of allo ...
, modes,
constraint logic programming Constraint logic programming is a form of constraint programming, in which logic programming is extended to include concepts from constraint satisfaction. A constraint logic program is a logic program that contains constraints in the body of clau ...
(CLP), object-oriented logic programming (OOLP), concurrency, linear logic (LLP), functional and
higher-order logic mathematics and logic, a higher-order logic is a form of predicate logic that is distinguished from first-order logic by additional quantifiers and, sometimes, stronger semantics. Higher-order logics with their standard semantics are more express ...
programming capabilities, plus interoperability with
knowledge base A knowledge base (KB) is a technology used to store complex structured and unstructured information used by a computer system. The initial use of the term was in connection with expert systems, which were the first knowledge-based systems. ...
s:


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 In computer science, type safety and type soundness are the extent to which a programming language discourages or prevents type errors. Type safety is sometimes alternatively considered to be a property of facilities of a computer language; that i ...
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 Constraint logic programming is a form of constraint programming, in which logic programming is extended to include concepts from constraint satisfaction. A constraint logic program is a logic program that contains constraints in the body of clau ...
extends Prolog to include concepts from
constraint satisfaction In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution through a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a set of values for th ...
. 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 Scheduling is the process of arranging, controlling and optimizing work and workloads in a production process or manufacturing process. Scheduling is used to allocate plant and machinery resources, plan human resources, plan production processes an ...
. Most Prolog systems ship with at least one constraint solver for finite domains, and often also with solvers for other domains like rational numbers.


Object-orientation

Flora-2 Flora-2 is an open source semantic rule-based system for knowledge representation and reasoning. The language of the system is derived from F-logic, HiLog, W. Chen, M. Kifer and D.S. Warren (1993)''HiLog: A Foundation for Higher-Order Logic Programm ...
is an object-oriented knowledge representation and reasoning system based on
F-logic F-logic ( frame 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 wel ...
and incorporates
HiLog HiLog is a programming logic with higher-order syntax, which allows arbitrary terms to appear in predicate and function positions. However, the model theory of HiLog is first-order. Although syntactically HiLog strictly extends first order logic, Hi ...
,
Transaction logic Transaction Logic is an extension of predicate logic that accounts in a clean and declarative way for the phenomenon of state changes in logic programs and databases. This extension adds connectives specifically designed for combining simple action ...
, and
defeasible reasoning In philosophical logic, defeasible reasoning is a kind of reasoning that is rationally compelling, though not deductive reasoning, deductively valid. It usually occurs when a rule is given, but there may be specific exceptions to the rule, or su ...
.
Logtalk Logtalk is an object-oriented logic programming language that extends and leverages the Prolog language with a feature set suitable for programming in the large.Paulo Moura (2003). Logtalk: Design of an Object-Oriented Logic Programming Language. ...
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 is a small, portable, object-oriented extension to Prolog by Margaret McDougall of EdCAAD, University of Edinburgh.
Objlog Objlog was a frame-based language combining objects and Prolog II from CNRS, Marseille, France. References

* "The Inheritance Processes in Prolog", C. Chouraki et al., GRTC/187bis/Mars 1987 (CNRS) * Prolog programming language family {{C ...
was a frame-based language combining objects and Prolog II from CNRS, Marseille, France. Prolog++ was developed by
Logic Programming Associates Logic Programming Associates (LPA) is a company specializing in logic programming and artificial intelligence software. LPA was founded in 1980 and is widely known for its range of Prolog compilers and more recently for VisiRule. LPA was esta ...
and first released in 1989 for MS-DOS PCs. Support for other platforms was added, and a second version was released in 1995. A book about Prolog++ by Chris Moss was published by Addison-Wesley in 1994.
Visual Prolog Visual Prolog, previously 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 PDC that originally crea ...
is a multi-paradigm language with interfaces, classes, implementations and object expressions.


Graphics

Prolog systems that provide a
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 runn ...
are
SWI-Prolog SWI-Prolog is a free implementation of the programming language Prolog, commonly used for teaching and semantic web applications. It has a rich set of features, libraries for constraint logic programming, multithreading, unit testing, GUI, inte ...
,
Visual Prolog Visual Prolog, previously 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 PDC that originally crea ...
, WIN-PROLOG, and B-Prolog.


Concurrency

Prolog-MPI is an open-source
SWI-Prolog SWI-Prolog is a free implementation of the programming language Prolog, commonly used for teaching and semantic web applications. It has a rich set of features, libraries for constraint logic programming, multithreading, unit testing, GUI, inte ...
extension for distributed computing over the Message Passing Interface. Also there are various concurrent Prolog programming languages.


Web programming

Some Prolog implementations, notably
Visual Prolog Visual Prolog, previously 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 PDC that originally crea ...
,
SWI-Prolog SWI-Prolog is a free implementation of the programming language Prolog, commonly used for teaching and semantic web applications. It has a rich set of features, libraries for constraint logic programming, multithreading, unit testing, GUI, inte ...
and Ciao, support
server-side In the client–server model, server-side refers to programs and operations that run on the server. This is in contrast to client-side programs and operations which run on the client. General concepts Typically, a server is a computer applicati ...
web programming Web development is the work involved in developing a website for the Internet (World Wide Web) or an intranet (a private network). Web development can range from developing a simple single static page of plain text to complex web applications, ...
with support for web protocols,
HTML The HyperText Markup Language or HTML is the standard markup language for documents designed to be displayed in a web browser. It can be assisted by technologies such as Cascading Style Sheets (CSS) and scripting languages such as JavaSc ...
and
XML Extensible Markup Language (XML) is a markup language and file format for storing, transmitting, and reconstructing arbitrary data. It defines a set of rules for encoding documents in a format that is both human-readable and machine-readable ...
. There are also extensions to support semantic web formats such as RDF and
OWL Owls are birds from the order Strigiformes (), which includes over 200 species of mostly solitary and nocturnal birds of prey typified by an upright stance, a large, broad head, binocular vision, binaural hearing, sharp talons, and feathers a ...
. Prolog has also been suggested as a
client-side Client-side refers to operations that are performed by the client in a client–server relationship in a computer network. General concepts Typically, a client is a computer application, such as a web browser, that runs on a user's local comput ...
language. In addition Visual Prolog supports
JSON-RPC JSON-RPC is a remote procedure call protocol encoded in JSON. It is similar to the XML-RPC protocol, defining only a few data types and commands. JSON-RPC allows for notifications (data sent to the server that does not require a response) and for m ...
and
Websockets WebSocket is a computer communications protocol, providing full-duplex communication channels over a single TCP connection. The WebSocket protocol was standardized by the IETF as in 2011. The current API specification allowing web applications ...
.


Adobe Flash

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 programming in Prolog through
ActionScript ActionScript is an object-oriented programming language originally developed by Macromedia Inc. (later acquired by Adobe). It is influenced by HyperTalk, the scripting language for HyperCard. It is now an implementation of ECMAScript (meaning i ...
.


Other

*
F-logic F-logic ( frame 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 wel ...
extends Prolog with frames/objects for knowledge representation. *
Transaction logic Transaction Logic is an extension of predicate logic that accounts in a clean and declarative way for the phenomenon of state changes in logic programs and databases. This extension adds connectives specifically designed for combining simple action ...
extends Prolog with a logical theory of state-changing update operators. It has both a model-theoretic and procedural semantics. * 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: * Th
LPA Intelligence Server
allows the embedding o

within C, C#, C++, Java, VB, Delphi, .Net, Lua, Python and other languages. It exploits the dedicated string data-type which LPA Prolog provides * 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! Prolo
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 (recursively). It is known to have good concurrency support and is under active development.
InterProlog
a programming library bridge between
Java Java (; id, Jawa, ; jv, ꦗꦮ; su, ) is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea to the north. With a population of 151.6 million people, Java is the world's List ...
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 and other functionality in Java while leaving logic processing in the Prolog layer. Supports
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 ve ...
, with support for
SWI-Prolog SWI-Prolog is a free implementation of the programming language Prolog, commonly used for teaching and semantic web applications. It has a rich set of features, libraries for constraint logic programming, multithreading, unit testing, GUI, inte ...
and
YAP Yap ( yap, Waqaab) traditionally refers to an island group located in the Caroline Islands of the western Pacific Ocean, a part of Yap State. The name "Yap" in recent years has come to also refer to the state within the Federated States of Micr ...
planned for 2013. *
Prova {{other uses 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 ...
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 and declarative programming.
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 provides interfaces to C, C++, Java, and relational databases.
C#-Prolog
is a Prolog interpreter written in (managed) C#. Can easily be integrated in C# programs. Characteristics: reliable and fairly fast interpreter, command line interface, Windows-interface, builtin DCG, XML-predicates, SQL-predicates, extendible. The complete source code is available, including a parser generator that can be used for adding special purpose extensions.
A Warren Abstract Machine for PHP
A Prolog compiler and interpreter in PHP 5.3. A library that can be used standalone or within Symfony2.1 framework which was translated fro
Stephan Buettcher's
work in Java which can be found ere
tuProlog
is a light-weight Prolog system for distributed applications and infrastructures, intentionally designed around a minimal core, to be either statically or dynamically configured by loading/unloading libraries of predicates. tuProlog natively supports multi-paradigm programming, providing a clean, seamless integration model between Prolog and mainstream object-oriented languages—namely Java, for tuProlog Java version, and any .NET-based language (C#, F#..), for tuProlog .NET version.


History

The name ''Prolog'' was chosen by
Philippe Roussel Philippe is a masculine sometimes feminin given name, cognate to Philip. It may refer to: * Philippe of Belgium (born 1960), King of the Belgians (2013–present) * Philippe (footballer) (born 2000), Brazilian footballer * Prince Philippe, Count o ...
as an abbreviation for ' ( French for ''programming in
logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
''). It was created around 1972 by
Alain Colmerauer Alain Colmerauer (24 January 1941 – 12 May 2017) was a French computer scientist. He was a professor at Aix-Marseille University, and the creator of the logic programming language Prolog. Early life Alain Colmerauer was born on 24 January 194 ...
with Philippe Roussel, based on
Robert Kowalski Robert Anthony Kowalski (born 15 May 1941) is an American-British logician and computer scientist, whose research is concerned with developing both human-oriented models of computing and computational models of human thinking. He has spent mo ...
's procedural interpretation of
Horn clause In mathematical logic and logic programming, a Horn clause is a logical formula of a particular rule-like form which gives it useful properties for use in logic programming, formal specification, and model theory. Horn clauses are named for the log ...
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 Anthony Kowalski (born 15 May 1941) is an American-British logician and computer scientist, whose research is concerned with developing both human-oriented models of computing and computational models of human thinking. He has spent mo ...
, the first Prolog system was developed in 1972 by Colmerauer and Phillipe Roussel. The first implementation of Prolog was an interpreter written in Fortran by Gerard Battani and Henri Meloni.
David H. D. Warren David H. D. Warren is a computer scientist who worked primarily on logic programming and in particular the programming language Prolog in the 1970s and 1980s. Warren wrote the first compiler for Prolog, and the Warren Abstract Machine execution ...
took this interpreter to
University of Edinburgh The University of Edinburgh ( sco, University o Edinburgh, gd, Oilthigh Dhùn Èideann; abbreviated as ''Edin.'' in post-nominals) is a public research university based in Edinburgh, Scotland. Granted a royal charter by King James VI in 15 ...
, and there implemented an alternative front-end, which came to define the “Edinburgh Prolog” syntax used by most modern implementations. Warren also implemented the first compiler for Prolog, creating the influential DEC-10 Prolog in collaboration with Fernando Pereira. Warren later generalised the ideas behind DEC-10 Prolog, to create the
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 (WAM) and has become the ''de facto'' standard ...
. European AI researchers favored Prolog while Americans favored Lisp, reportedly causing many nationalistic debates on the merits of the languages. 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'' for its first
operating system An operating system (OS) is system software that manages computer hardware, software resources, and provides common services for computer programs. Time-sharing operating systems schedule tasks for efficient use of the system and may also in ...
. Pure Prolog was originally restricted to the use of a
resolution Resolution(s) may refer to: Common meanings * Resolution (debate), the statement which is debated in policy debate * Resolution (law), a written motion adopted by a deliberative body * New Year's resolution, a commitment that an individual mak ...
theorem prover with
Horn clause In mathematical logic and logic programming, a Horn clause is a logical formula of a particular rule-like form which gives it useful properties for use in logic programming, formal specification, and model theory. Horn clauses are named for the log ...
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 Negation as failure (NAF, for short) is a non-monotonic inference rule in logic programming, used to derive \mathrm~p (i.e. that ~p is assumed not to hold) from failure to derive ~p. Note that \mathrm ~p can be different from the statement \neg p ...
, 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 Constraint logic programming is a form of constraint programming, in which logic programming is extended to include concepts from constraint satisfaction. A constraint logic program is a logic program that contains constraints in the body of clau ...
abilities into the implementations.


Use in industry

Prolog has been used in Watson. Watson uses IBM's DeepQA software and the Apache
UIMA UIMA ( ), short for Unstructured Information Management Architecture, is an OASIS standard for content analytics, originally developed at IBM. It provides a component software architecture for the development, discovery, composition, and deplo ...
(Unstructured Information Management Architecture) framework. The system was written in various languages, including Java, C++, and Prolog, and runs on the SUSE Linux Enterprise Server 11 operating system using Apache Hadoop framework to provide distributed computing. Prolog is used for
pattern matching In computer science, pattern matching is the act of checking a given sequence of tokens for the presence of the constituents of some pattern. In contrast to pattern recognition, the match usually has to be exact: "either it will or will not be ...
over natural language parse trees. The developers have stated: "We required a language in which we could conveniently express pattern matching rules over the parse trees and other annotations (such as named entity recognition results), and a technology that could execute these rules very efficiently. We found that Prolog was the ideal choice for the language due to its simplicity and expressiveness." Prolog is being used in the Low-Code Development Platform
GeneXus GeneXus is a Low Code, cross-platform, knowledge representation-based development tool, mainly oriented towards enterprise-class applications for web applications, smart devices, and the Microsoft Windows platform. GeneXus uses mostly declar ...
, which is focused around AI. Open source
graph database A graph database (GDB) is a database that uses graph structures for semantic queries with nodes, edges, and properties to represent and store data. A key concept of the system is the '' graph'' (or ''edge'' or ''relationship''). The graph rel ...
TerminusDB TerminusDB is an open source knowledge graph and Document-oriented database, document store. It is used to build versioned data products. It is a Native (computing), native Version control, revision control database that is architecturally simil ...
is implemented in prolog. TerminusDB is designed for collaboratively building and curating
knowledge graph The Google Knowledge Graph is a knowledge base from which Google serves relevant information in an infobox beside its search results. This allows the user to see the answer in a glance. The data is generated automatically from a variety of sou ...
s.


See also

*
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. Portability There are Prolog implementations that are ...
*
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 logic programming languages such as Prolog. Overview Logico-li ...
. A method for building knowledge-based system that uses Prolog. * Answer set programming. A fully declarative approach to logic programming. *
Association for Logic Programming The Association for Logic Programming (ALP) was founded in 1986. Its mission is "to contribute to the development of Logic Programming, relate it to other formal and also to humanistic sciences, and to promote its uses in academia and industry al ...


Related languages

* The Gödel language is a strongly typed implementation of
concurrent constraint logic programming Concurrent constraint logic programming is a version of constraint logic programming aimed primarily at programming concurrent processes rather than (or in addition to) solving constraint satisfaction problems. Goals in constraint logic programming ...
. It is built on SICStus Prolog. *
Visual Prolog Visual Prolog, previously 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 PDC that originally crea ...
, formerly known as PDC Prolog and Turbo Prolog, is a strongly typed
object-oriented Object-oriented programming (OOP) is a programming paradigm based on the concept of " objects", which can contain data and code. The data is in the form of fields (often known as attributes or ''properties''), and the code is in the form of p ...
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 is a declarative logic programming language. While it is syntactically a subset of Prolog, Datalog generally uses a bottom-up rather than top-down evaluation model. This difference yields significantly different behavior and properties ...
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 In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally universal if it can be used to simulate any ...
. * Mercury is an offshoot of Prolog geared toward software engineering in the large with a static, polymorphic type system, as well as a mode and determinism system. * GraphTalk is a proprietary implementation of Warren's Abstract Machine, with additional object-oriented properties. * In some ways Prolog is a subset of
Planner Planner may refer to: * A personal organizer (book) for planning * Microsoft Planner * Planner programming language * Planner (PIM for Emacs) * Urban planner * Route planner * Meeting and convention planner * Japanese term for video game designer ...
. The ideas in Planner were later further developed in the
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 langu ...
. *
AgentSpeak AgentSpeak is an agent-oriented programming language. It is based on logic programming and the belief–desire–intention software model (BDI) architecture for ( cognitive) autonomous agents. The language was originally called AgentSpeak(L), but ...
is a variant of Prolog for programming agent behavior in
multi-agent system A multi-agent system (MAS or "self-organized system") is a computerized system composed of multiple interacting intelligent agents.Hu, J.; Bhowmick, P.; Jang, I.; Arvin, F.; Lanzon, A.,A Decentralized Cluster Formation Containment Framework f ...
s. * Erlang began life with a Prolog-based implementation and maintains much of Prolog's unification-based syntax.
Pilog
is a declarative language built on top of
PicoLisp PicoLisp is a programming language, a dialect of the language Lisp. It runs on operating systems including Linux and others that are ''Portable Operating System Interface'' (POSIX) compliant. Its most prominent features are simplicity and minimalis ...
, that has the semantics of Prolog, but uses the syntax of Lisp.


References


Further reading

* * Ivan Bratko, ''Prolog Programming for Artificial Intelligence'', 4th ed., 2012,
Book supplements and source code
* William F. Clocksin, Christopher S. Mellish: ''Programming in Prolog: Using the ISO Standard''. Springer, 5th ed., 2003, . ''(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, . * Michael A. Covington, Donald Nute, Andre Vellino, ''Prolog Programming in Depth'', 1996, . * Michael A. Covington, ''Natural Language Processing for Prolog Programmers'', 1994, * M. S. Dawe and C.M.Dawe, ''Prolog for Computer Sciences'', Springer Verlag 1992. * ''ISO/IEC 13211: Information technology — Programming languages — Prolog''.
International Organization for Standardization The International Organization for Standardization (ISO ) is an international standard development organization composed of representatives from the national standards organizations of member countries. Membership requirements are given in Ar ...
, Geneva. * Feliks Kluźniak and Stanisław Szpakowicz (with a contribution by Janusz S. Bień). ''Prolog for Programmers''. Academic Press Inc. (London), 1985, 1987 (available under a
Creative Commons Creative Commons (CC) is an American non-profit organization and international network devoted to educational access and expanding the range of creative works available for others to build upon legally and to share. The organization has release ...
license at ). . * Richard O'Keefe, ''The Craft of Prolog'', . * Robert Smith, John Gibson,
Aaron Sloman Aaron Sloman is a philosopher and researcher on artificial intelligence and cognitive science. He held the Chair in Artificial Intelligence and Cognitive Science at the School of Computer Science at the University of Birmingham, and before that ...
: '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 Professor Leon Sterling is a career academic with a distinguished academic record. After completing a PhD at the Australian National University, he worked for 15 years at universities in the UK, Israel and the United States. He returned to Austr ...
and
Ehud Shapiro Ehud Shapiro ( he, אהוד שפירא; born 1955) is a multi-disciplinary scientist, artist, entrepreneur and Professor of Computer Science and Biology at the Weizmann Institute of Science. With international reputation, he made fundamental cont ...
, ''The Art of Prolog: Advanced Programming Techniques'', 1994, . * 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. {{Authority control 1972 in computing Declarative programming languages Dynamically typed programming languages Logic programming languages Pattern matching programming languages Programming languages created in 1972 Programming languages with an ISO standard Prolog programming language family Homoiconic programming languages